Fast and Low-RAM-Footprint Indexing for Data Deduplication

• US 20110276781A1
• Filed: 12/28/2010
• Published: 11/10/2011
• Est. Priority Date: 05/05/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Desai, Ronakkumar N., Debnath, Biplob, Oltean, Paul Adrian, Li, Jin, Sengupta, Sudipta
• Granted Patent: US 8,935,487 B2
• Time in Patent Office: Days
• US Class Current: 711/216
• 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 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/463 File
• CPC Class Codes: G06F 2212/466 Metadata, control data

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, a system comprising:

a log-structured hash index maintained in a secondary storage device, in which entries of the log-structured hash index comprise hash values of data chunks and associated metadata with each hash value, the hash index updated by appending new entries to the log-structured hash index; and

a hash index service configured to access the log-structured hash index to perform a lookup based on a hash value computed for a chunk and return the metadata associated with that hash value if found, or to return a not-found result if not found.

2. The system of claim 1 wherein the hash index is updated by using pages of entries when appending to the log-structured hash index.

3. The system of claim 1 wherein the hash index service is further configured to access a session cache in a primary storage device to lookup a hash value and return the metadata associated with that hash value if found in the session cache, so as to not need to access the log-structured hash index for the metadata if found in the session cache.

4. The system of claim 1 further comprising 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 position of a hash value, metadata entry in the log on secondary storage, wherein the hash index service is further configured to access the compact index table to lookup a compact signature corresponding to a requested hash value to lookup, and to return a not-found result if the compact signature is not found in the compact index table, and to follow the pointer to look for an entry in the log-structured hash index that possibly contains requested hash value if the compact signature is found in the compact index table.

5. The system of claim 4 wherein each compact signature comprises an M-bit length value derived from the hash value and a candidate position at which the hash value, metadata entry is possibly stored, wherein the candidate position corresponds to an N-bit length pointer.

6. The system of claim 4 wherein a plurality of entries in the compact index table are associated with the requested hash value, wherein the hash index service'"'"'s access of the compact index table includes evaluating the plurality of entries in the compact index table via their associated compact signatures, wherein each compact signature is matched to a hash value, and wherein the hash index service is configured to return a not-found result if all corresponding compact signatures are not found in the compact table, or for each compact signature that is found, to match to the requested hash value and to follow the pointer associated with that hash value to look for an entry in the log-structured hash index that possibly contains requested hash value, and to return a not-found result only if no pointer points to an entry that contains the requested hash value.

7. The system of claim 1 further comprising a look-ahead cache in a primary storage device that includes hash values and metadata entries cached from the log index table, wherein the hash index service is further configured to access the look-ahead cache to lookup a hash value and return the metadata associated with that hash value if found in the look-ahead cache, so as to not need to access the log-structured hash index for the metadata if found in the look-ahead cache.

8. The system of claim 7 wherein the look-ahead cache includes one or more hash value, metadata entries placed in the look-ahead cache based upon popularity of one or more corresponding deduplication chunks.

9. The system of claim 7 wherein the look-ahead cache includes one or more hash value, metadata entries placed in the look-ahead cache based upon recent usage of one or more corresponding deduplication chunks.

10. The system of claim 7 wherein the hash index service is further configured to obtain one or more neighbor hash index, metadata entries, one or more I/O operations, when accessing the log-structured index, and to add the one or more neighbor hash index, metadata entries to the look-ahead cache.

11. The system of claim 7 wherein the hash index service is further configured to obtain the one or more neighbor hash index, metadata entries up to a file boundary that corresponds to a deduplicated file, in which the one or more neighbor hash index, metadata entries each correspond to a deduplicated chunk of that file.

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

maintaining a hash index in a secondary storage device, in which entries of the hash index include hash values, each hash value being computed from a deduplicated data chunk, and being associated with metadata by which the deduplicated data chunk is locatable;

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

mapping each hash value to up to two or more entries in the compact index table, in which each entry contains a unique signature; and

accessing the compact index table to lookup a compact signature corresponding to a requested hash value provided in a request, and returning a not-found result in response to the request if none of the compact signatures are found in the compact index table, or following one or more pointers to determine whether an entry in the hash index contains the requested hash value if the compact signature is found in the compact index table.

13. The method of claim 12 wherein the compact signature is found in the compact index table, and further comprising, returning metadata associated with the requested hash value from the hash index in response to the request if the entry in the hash index found via the pointer is determined to contain the requested hash value, or returning a not-found result in response to the request.

14. The method of claim 12 further comprising, inserting a compact signature into the compact index table by using a cuckoo hash-based algorithm to avoid hash collisions.

15. The method of claim 14 further comprising, writing at least one compact signature to a spillover table instead of inserting the compact signature into the compact index table when all entries of the compact index table are occupied, or when a sufficient number of cuckoo relocations have been attempted, or both.

16. One or more computer-readable media having computer-executable instructions, which when executed perform steps, comprising,

maintaining a hash index in a secondary storage device, in which entries of the hash index include hash values, each hash value being computed from a deduplicated data chunk, and being associated with metadata by which the deduplicated data chunk is locatable;

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

accessing the look-ahead cache to lookup a requested hash value provided in a request, and returning metadata in response to the request if the requested hash value is found in the look-ahead cache.

17. The one or more computer-readable media of claim 16 having further computer-executable instructions, comprising if the requested hash value is not found in the look-ahead cache, accessing the hash index to look for the requested hash value.

18. The one or more computer-readable media of claim 17 wherein the hash index contains the requested hash value, and having further computer-executable instructions, comprising, loading the look-ahead cache with neighbor entries of the requested hash value.

19. The one or more computer-readable media of claim 18 wherein loading the look-ahead cache with neighbor entries of the requested hash value comprises, obtaining the neighbor entries up to a file boundary indicator detected in the hash index.

20. The one or more computer-readable media of claim 16 having further computer-executable instructions, comprising, populating the look-ahead cache with commonly accessed file chunks.