Fast and low-RAM-footprint indexing for data deduplication

• US 9,053,032 B2
• Filed: 12/28/2010
• Issued: 06/09/2015
• Est. Priority Date: 05/05/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Sengupta, Sudipta, Debnath, Biplob, Li, Jin, Desai, Ronakkumar N., Oltean, Paul Adrian
• Primary Examiner(s): DUDEK JR, EDWARD J
• Application Number:
  US12/979,644
• Publication Number:
  US 20110276780A1
• Time in Patent Office: 1,624 Days
• Field of Search: 711/154, 711/E12.002, 707/692
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 16/1752 based on file chunks

Abstract

The subject disclosure is directed towards a data deduplication technology in which a hash index service'"'"'s index maintains a hash index in a secondary storage device such as a hard drive, along with a compact index table and look-ahead cache in RAM that operate to reduce the I/O to access the secondary storage device during deduplication operations. Also described is a session cache for maintaining data during a deduplication session, and encoding of a read-only compact index table for efficiency.

Claims

1. In a computing environment, method performed at least in part on at least one processor, comprising:

maintaining a session cache at a primary storage device for a deduplication session, the session cache including a bundle of entries comprising hash values computed from chunks of deduplicated file data, and for each hash value, associated metadata corresponding to a storage location of the chunk from which that hash value was computed;

writing the bundle of entries from the session cache in the primary storage device into a hash index maintained at a secondary storage device at the end of the deduplication session for subsequent use in locating existing chunks; and

updating a compact index table in the primary storage device as the bundle of entries is written from the session cache to the hash index, the compact index table including compact signatures representative of the hash values.

2. The method of claim 1 further comprising:

receiving a request to determine whether a hash value provided with the request corresponds to an existing chunk; and

accessing the session cache to perform a lookup based on a hash value computed for a chunk and return the metadata associated with that hash value if found in the session cache.

3. The method of claim 2 further comprising:

accessing the hash index to lookup the hash value if not found in the session cache.

4. In a computing environment, a system comprising:

a hash index maintained in a secondary storage device, in which entries of the hash index comprise hash values of deduplicated file chunks and associated chunk metadata with each hash value, the hash index updated by appending bundles of new entries from a session cache to the hash index;

a compact index table in a primary storage device that includes compact signatures representative of the hash values, and for each compact signature, a pointer to a corresponding hash value, metadata entry in the hash index; and

a hash index service configured to access the compact index table to look for up to one or more entries of the compact index table with corresponding compact signatures corresponding to a requested hash value to lookup, and if one or more matching compact signatures are matched, to follow each matching signature'"'"'s pointer to look for an entry in the hash index that possibly contains requested hash value.

5. The system of claim 4 wherein the compact index table corresponds to a subspace comprising a smaller subset of the hash index.

6. The system of claim 5 wherein the compact index table corresponds to a read-only mode.

7. The system of claim 6 further comprising an encoder that accesses the subspace to encode the compact index into a reduced memory-size compact index table.

8. The system of claim 4 wherein the hash index service is further configured to insert a new compact signature and pointer entry into the compact index table for a new hash value.

9. The system of claim 8 wherein the hash index service inserts the new compact signature and pointer entry into the compact index table by using a cuckoo hash-based algorithm to avoid hash collisions and locate an available slot in the compact index table, in which for each insert, up to n entries in the compact index table are evaluated, and if one of the entries is empty, the new compact signature and pointer is entered in a corresponding empty location, and if none of the n entries are empty, another compact signature and associated pointer that occupies another entry location, for up to a predetermined number of other compact signatures and associated pointers, is evaluated to determine via its hash value whether the other compact signature and pointer is able to be relocated to a new empty location, and if so, to relocate that other compact signature and pointer to the new empty location and replace that other compact signature and pointer'"'"'s former entry location with the new compact signature and pointer entry.

10. The system of claim 9 in which the relocation operation is executed a breadth-first search, a depth-first search, or via randomized selection until a predetermined number of possible relocation operations have been evaluated.

11. The system of claim 10 further comprising a spillover table, wherein the hash index service writes at least one other compact signature and pointer entry to a spillover table when the cuckoo hash-based algorithm fails to locate an available slot for the compact signature and pointer entry after a predetermined number of possible relocation operations have been unsuccessfully attempted.

12. One or more computer storage devices having computer-executable instructions, which in response to execution by a computer, cause the computer to perform steps comprising:

(a) maintaining a hash index in a secondary storage device, in which entries of the hash index comprise hash values and associated metadata with each hash value;

(b) maintaining a look-ahead cache in a primary storage device that includes hash values and metadata entries cached from the index table,

(c) maintaining a compact index table in a primary storage device that includes compact signatures representative of the hash values, and for each compact signature, a pointer to a corresponding hash value, metadata entry in the hash index;

(d) receiving a requested hash value in a request to return the metadata associated with the requested hash value or a not-found response;

(e) accessing the look-ahead cache to lookup the hash value, and if found in the look-ahead cache, including the metadata in the result and advancing to step (h);

(f) accessing the compact index table to lookup a compact signature corresponding to the requested hash value, and to include the not-found response and advance to step (h) if none of the compact signatures corresponding to the hash value and entries are found in the compact index table,

(g) following the pointer to look for an entry in the hash index that matches the requested hash value, and including the metadata associated with the hash value in the result if a match is found in the hash index, or including the not-found response if no match is found in the hash index; and

(h) returning the result in response to the request.

13. The one or more computer storage devices of claim 12 having further computer-executable instructions, comprising, maintaining a session cache that includes hash values and metadata entries cached during a data deduplication session for transferring into the hash index at the end of each deduplication session, and prior to step (f), accessing the session cache to lookup the requested hash value, and if found in the session cache, including the metadata in the result and advancing to step (h).

14. The one or more computer storage devices of claim 12 wherein the hash values and metadata entries correspond to deduplicated file chunks, and having further computer-executable instructions comprising, populating the look-ahead cache with one or more hash value, metadata entries based upon popularity of one or more corresponding chunks.

15. The one or more computer storage devices of claim 12 wherein the hash values and metadata entries correspond to deduplicated file chunks, and having further computer-executable instructions comprising, populating the look-ahead cache with one or more hash value, metadata entries based upon recent usage or frequency of usage, or both recent usage and frequency of usage, of one or more corresponding deduplication chunks.

16. The one or more computer storage devices of claim 12 wherein the hash values and metadata entries correspond to deduplicated file chunks, and having further computer-executable instructions comprising:

obtaining one or more neighbor hash index, metadata entries while following the pointer to look for an entry in the hash index, and adding the one or more neighbor hash index, metadata entries to the look-ahead cache.

17. The one or more computer storage devices of claim 16 wherein obtaining the one or more neighbor hash index, metadata entries comprises detecting a file boundary indicator in the hash index and obtaining the neighbor entries up to the file boundary indicator.

18. The one or more computer storage devices of claim 12 having further computer-executable instructions, comprising encoding the compact index into a reduced memory-size compact index table.

19. The one or more computer storage devices of claim 12 having further computer-executable instructions, comprising inserting a compact signature and pointer entry into the compact index table for a new hash value via a cuckoo hash-based algorithm to avoid hash collisions and locate an available slot in the compact index table.

20. The one or more computer storage devices of claim 12 having further computer-executable instructions, comprising limiting a number of times that the cuckoo hash-based algorithm unsuccessfully attempts to locate an available slot.