Elimination of duplicate objects in storage clusters
Digital objects within a fixed-content storage cluster use a page mapping table and a hash-to-UID table to store a representation of each object. For each object stored within the cluster, a record in the hash-to-UID table stores the object's hash value and its unique identifier (or portions thereof). To detect a duplicate of an object, a portion of its hash value is used as a key into the page mapping table. The page mapping table indicates a node holding a hash-to-UID table indicating currently stored objects in a particular page range. Finding the same hash value but with a different unique identifier in the table indicates that a duplicate of an object exists. Portions of the hash value and unique identifier may be used in the hash-to-UID table. Unneeded duplicate objects are deleted by copying their metadata to a manifest and then redirecting their unique identifiers to point at the manifest.
1. A method of detecting duplicates of a first digital object within a storage cluster, said method comprising:
receiving, within said storage cluster, a hash value of said first digital object and a unique identifier associated with said first digital object, said hash value falling within an address space made up of a plurality of non-overlapping ranges;
identifying a portion of said hash value whose value represents a first range of addresses within said address space;
accessing a page mapping table using said value indicated by said portion of said hash value to identify a computer node of said storage cluster, said page mapping table mapping each range of addresses of said address space to one of said computer nodes;
accessing a hash table of said computer node to determine whether said hash value and said unique identifier are represented in said hash table;
accessing a second digital object within said storage cluster when it is determined that said hash value is represented in an entry in said hash table but said unique identifier is not; and
comparing a hash value stored in association with said second digital object with said received hash value and determining that said second digital object is a duplicate of said first digital object when said hash values match.
2. A method as recited in claim 1 further comprising:
identifying a second unique identifier of said entry; and
accessing said second digital object using said second unique identifier.
3. A method as recited in claim 1 further comprising:
accessing said hash table using a first part of said hash value to determine whether said hash value is represented in said entry.
4. A method as recited in claim 1 further comprising:
determining that said hash value is represented by multiple entries in said hash table; and
for each of said multiple entries, accessing a digital object within said storage cluster having a unique identifier corresponding to each of said entries.
5. A method as recited in claim 1 further comprising:
identifying a second unique identifier of said entry; and
accessing said page mapping table using a portion of said second unique identifier to identify a computer node of said storage cluster having an index indicating the location of said second digital object within said storage cluster.
6. A method as recited in claim 1 further comprising:
identifying a second unique identifier of said entry; and
broadcasting a message to all computer nodes of said storage cluster to find said second digital object identified by said second unique identifier.
7. A method of storing a digital object in a storage cluster, said method comprising:
receiving said digital object at a first computer node within said storage cluster having a plurality of computer nodes;
calculating a hash value for said digital object that falls within an address space and storing said digital object on a disk of said first computer node, said address space made up of a plurality of non-overlapping ranges;
generating a unique identifier for said digital object;
identifying a portion of said hash value whose value represents a first range of addresses within said address space;
accessing a page mapping table using said value indicated by said portion of said hash value to identify a second computer node, said page mapping table mapping each range of addresses of said address space to one of said computer nodes;
sending said hash value and said unique identifier to said second computer node; and
storing at least a first part of said hash value and at least a first part of said unique identifier in a table on said second computer node to indicate that said digital object is present within said storage cluster.
8. A method as recited in claim 7 wherein for every digital object stored within said cluster having a hash value falling within said first range of addresses, said table stores a record indicating that said every digital object is stored within said cluster.
9. A method as recited in claim 7 wherein said storage cluster is a write-once read-many (WORM) fixed-content stored cluster.
10. A method as recited in claim 7 wherein said table maps said first part of said hash value to a plurality of unique identifiers.
11. A method as recited in claim 7 wherein said page mapping table and said table are located in RAM.
12. A method as recited in claim 7 wherein said unique identifier is generated using a hash function or by a random number generator.
13. A method as recited in claim 7 wherein said digital object has associated metadata indicating that said digital object is likely unique and that searching for duplicates of said digital object is unnecessary.