Deduplication using sub-chunk fingerprints

• US 10,135,462 B1
• Filed: 06/13/2012
• Issued: 11/20/2018
• Est. Priority Date: 06/13/2012
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Wallace, Grant R., Shilane, Philip N., Huang, Mark L., Lee, Edward K., Li, Kai
• Primary Examiner(s): Thomas, Ashish K
• Assistant Examiner(s): Ohba, Mellissa M
• Application Number:
  US13/495,856
• Time in Patent Office: 2,351 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 2201/83 the solution involving signatures
• CPC Class Codes: H03M 7/3091 Data deduplication

Abstract

A computer-implemented method and system for deduplicating sub-chunks in a data storage system selects a data chunk to deduplicate and generates a sketch for the selected data chunk. A similar data chunk is searched for using the sketch. A set of fingerprints corresponding to sub-chunks of the similar data chunk is loaded. The set of fingerprints for the similar data chunk is compared to a set of fingerprints of the selected data chunk and the selected chunk is encoded as a set of references to identical sub-chunks of the similar data chunk and at least one unmatched sub-chunk.

Claims

1. A computer-implemented method for storing sub-chunks in a data storage system, the method comprising:

selecting a data chunk comprising sub-chunks, the selected data chunk having a set of fingerprints and a set of sketches corresponding to the sub-chunks of the selected data chunk;

generating a sketch for the selected data chunk;

searching a set of candidate data chunks using the sketch of the selected data chunk to identify a base data chunk;

ranking the set of candidate data chunks with at least a minimum degree of similarity by location status data, wherein the location status data indicates a location and status of the base data chunk as in any one of a compressed in a cache status, a decompressed in a cache status, or a compressed in a data storage status, and wherein ranking the set of candidate data chunks using location status data for each candidate prefers a compressed in a cache status over a compressed in a data storage status;

loading a set of fingerprints and a set of sketches corresponding to sub-chunks of a similar data chunk based on the ranking;

for each sub-chunk of the selected data chunk;

searching the set of fingerprints of the similar data chunk to find a match to the fingerprint of the sub-chunk;

encoding the sub-chunk as a reference to a sub-chunk of the similar data chunk, in response to determining that the fingerprint of the sub-chunk is identical to the fingerprint of the sub-chunk of the similar data chunk;

in response to determining that the fingerprint of the sub-chunk is not identical to a fingerprint in the set of fingerprints of the similar chunk;

searching the set of sketches of the similar data chunk corresponding to the sub-chunks of the similar data chunk to find a sketch that is similar to the sketch of the sub-chunk; and

delta-encoding the sub-chunk as a reference to a sub-chunk of the similar data chunk and delta-encoding metadata, in response to determining that the sketch of the sub-chunk is similar to the sketch of the sub-chunk of the similar data chunk;

otherwise, storing the sub-chunk in an unencoded form.

2. The method of claim 1, wherein generating the sketch further comprises:

performing a resemblance hash over the selected data chunk to generate the sketch of the selected chunk.

3. The method of claim 1, wherein searching the set of candidate data chunks further comprises:

searching an index of data chunks by using the selected chunk sketch as the query.

4. The method of claim 1, wherein loading the set of fingerprints further comprises:

retrieving the set of fingerprints from container meta data in a container of the similar data chunk.

5. The method of claim 1, further comprising:

generating a set of fingerprints and a set of sketches, for sub-chunks of the selected data chunk in a corresponding manner to fingerprints and sub-chunks of the similar data chunk.

6. The method of claim 1, wherein searching the set of fingerprints of the similar data chunk to find the match to the fingerprint of the sub-chunk comprises:

checking for identical fingerprints between the set of fingerprints of the similar data chunk and the set of fingerprints of the selected data chunk.

7. The method of claim 1, wherein the selected data chunk and the similar data chunk have any one of a variable size.

8. The method of claim 1, wherein the selected data chunk or the similar data chunk overlap at least one other data chunk.

9. The method of claim 1, wherein the generating sketch combines a plurality of hashing processes.

23. The method claim 1, wherein sub-chunks of the selected data chunks are in a different order than sub-chunks of the similar data chunk.

24. The method of claim 1, wherein the sub-chunks of the similar data chunk are of variable size.

25. The method of claim 1, wherein the sub-chunks of the similar data chunk are overlapping.

10. A non-transitory computer-readable storage medium having instructions stored therein, which when executed by a computer, cause the computer to perform a method, the method for storing sub-chunks in a data storage system, the method comprising:

selecting a data chunk comprising sub-chunks, the selected data chunk having a set of fingerprints and a set of sketches corresponding to the sub-chunks of the selected data chunk;

generating a sketch for the selected data chunk;

searching a set of candidate data chunks using the sketch of the selected data chunk to identify a base data chunk;

ranking the set of candidate data chunks with at least a minimum degree of similarity by location status data, wherein the location status data indicates a location and status of the base data chunk as in any one of a compressed in a cache status, a decompressed in a cache status, or a compressed in a data storage status, and wherein ranking the set of candidate data chunks using location status data for each candidate prefers a compressed in a cache status over a compressed in a data storage status;

loading a set of fingerprints and a set of sketches corresponding to sub-chunks of a similar data chunk based on the ranking;

for each sub-chunk of the selected data chunk;

searching the set of fingerprints for the similar data chunk to find a match to the fingerprint of the sub-chunk;

encoding the sub-chunk as a reference to a sub-chunk of the similar data chunk, in response to determining that the fingerprint of the sub-chunk is identical to the fingerprint of the sub-chunk of the similar data chunk;

in response to determining that the fingerprint of the sub-chunk is not identical to a fingerprint in the set of fingerprints of the similar chunk;

searching the set of sketches of the similar data chunk to find a sketch that is similar to the sketch of the sub-chunk of the selected data chunk; and

delta-encoding the sub-chunk as a reference to the sub-chunk of the similar data chunk and delta-encoding metadata, in response to determining that the sketch of the sub-chunk is similar to the sketch of the sub-chunk of the similar data chunk;

otherwise, storing the sub-chunk in an unencoded form.

11. The non-transitory computer-readable storage medium of claim 10, wherein generating the sketch further comprises:

performing a resemblance hash over the selected data chunk to generate a sketch of the selected chunk.

12. The non-transitory computer-readable storage medium of claim 10, wherein searching the set of candidate data chunks further comprises:

searching an index of data chunks by comparing sketches in each index entry with the sketch of the selected chunk.

13. The non-transitory computer-readable storage medium of claim 10, wherein loading the set of fingerprints further comprises:

retrieving the set of fingerprints from the container metadata in a container of the similar data chunk.

14. The non-transitory computer-readable storage medium of claim 10, further comprising:

generating a set of fingerprints and a set of sketches for sub-chunks of the selected data chunk that correspond to the fingerprints of the sub-chunks of the similar data chunk.

15. The non-transitory computer-readable storage medium of claim 10, wherein searching the set of fingerprints of the similar data chunk to find the match to the fingerprint of the sub-chunk comprises:

checking for identical fingerprints between the set of fingerprints of the similar data chunk and the set of fingerprints of the selected data chunk.

16. The non-transitory computer-readable storage medium of claim 10, wherein the selected data chunk and the similar data chunk have any one of a variable size.

17. The non-transitory computer-readable storage medium of claim 10, wherein the selected data chunk or the similar data chunk overlap at least one other data chunk.

18. The non-transitory computer-readable storage medium of claim 10, wherein the generating sketch combines a plurality of hashing processes.

19. A system, comprising:

a processor;

a memory; and

a storage module loaded in the memory and executed by the processor to perform operations, the operations including

selecting a data chunk comprising sub-chunks, the selected data chunk having a set of fingerprints and a set of sketches corresponding to the sub-chunks of the selected data chunk, the data chunk selected from a first set of data chunks,

generating a sketch for the data chunk of the selected data chunk,

searching a set of candidate data chunks using the sketch of the selected data chunk to identify a base data chunk,

ranking the set of candidate data chunks with at least a minimum degree of similarity by location status data, wherein the location status data indicates a location and status of the base data chunk as in any one of a compressed in a cache status, a decompressed in a cache status, or a compressed in a data storage status, and wherein ranking the set of candidate data chunks using location status data for each candidate prefers a compressed in a cache status over a compressed in a data storage status,

loading a set of fingerprints and a set of sketches corresponding to sub-chunks of a similar data chunk based on the ranking,

for each sub-chunk of the selected chunk;

searching the set of fingerprints for the similar data chunk to find a match to the fingerprint of the sub-chunk;

encoding the sub-chunk as a references to a sub-chunk of the similar data chunk, in response determining that the fingerprint of the sub-chunk is identical to the fingerprint of the sub-chunk of the similar data chunk,

in response to determining that the fingerprint of the sub-chunk is not identical to a fingerprint in the set of fingerprints of the similar chunk;

searching the set of sketches of the similar data chunk to find a sketch that is most similar to the sketch of the sub-chunk; and

delta-encoding the sub-chunk as a reference to a sub-chunk of the similar data chunk and delta-encoding metadata, in response to determining that the sketch of the sub-chunk is similar to the sketch of the sub-chunk of the similar data chunk;

otherwise, storing the sub-chunk in an unencoded form.

20. The system of claim 19, wherein the storage module searches an index of data chunks by comparing sketches in each index entry with the sketch of the selected chunk.

21. The system of claim 19, wherein the storage module retrieves the set of fingerprints from container metadata of a container of the similar data chunk for the sub-chunks of the similar data chunk.

22. The system of claim 19, wherein the storage module generates a set of fingerprints and a set of sketches for the selected data chunk that correspond to the fingerprints of the similar data chunk.