Out-of core similarity matching

• US 9,727,573 B1
• Filed: 09/10/2014
• Issued: 08/08/2017
• Est. Priority Date: 12/22/2011
• 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, Shilane, Philip N., Douglis, Frederick
• Primary Examiner(s): Gortayo, Dangelino
• Application Number:
  US14/482,589
• Time in Patent Office: 1,063 Days
• Field of Search: 707693, 707692, 707747, 707752
• CPC Class Codes: G06F 16/11 File system administration, e.g. details of archiving or snapshots file system backup G06F11/14
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

Abstract

A method for storing data in a data storage system by partitioning the data into a plurality of data chunks and generating representative data for each of the plurality of chunks by applying a predetermined algorithm to each chunk of the plurality of chunks. Subsequently, the representative data is compared and sorted. Representative data for base data chunks and representative data for other data chunks that can be stored relative to the base data chunks are identified by evaluating the sorted set of representative data. Finally, each of the other data chunks identified as those that can be stored relative to a base data chunk are stored in the data storage system as the difference between the data chunk and a base data chunk.

Claims

1. A computer-implemented method for data reduction, the method comprising:

in response to a request for compressing data in a data storage system, partitioning the data into a plurality of data chunks, including a target data chunk and a base data chunk;

generating representative data for the target data chunk and the base data chunk by applying a predetermined algorithm to the target data chunk and the base data chunk, the representative data including fingerprints of the target data chunk and the base data chunk and a plurality of features extracted from the target data chunk and the base data chunk, wherein each of the plurality of features is a value having a property that a probability of the target data chunk having same representative value as the base data chunk is proportional to data similarity of the target data chunk and the base data chunk;

sorting the representative data for the target data chunk and the base data chunk to form a sorted representative data list based on a first feature defined in the representative data for the target data chunk and the base data chunk; and

generating a delta data chunk as the difference between the target data chunk and the base data chunk where the representative data of the target chunk is proximate to the representative data of the base data chunk in the sorted representative data list.

2. The computer-implemented method of claim 1, wherein the representative data of the base data chunk is proximate to the representative data of the target data chunk such that the representative data of the base data chunk has one or more features that are identical to one or more corresponding features of the representative data of the target data chunk.

3. The computer-implemented method of claim 1, wherein the base data chunk is chosen based on an age comparison with the target data chunk.

4. The computer-implemented method of claim 1, wherein the base data chunk is chosen based on physical locality in the data storage system in relation to the target data chunk.

5. The computer-implemented method of claim 1, further comprising:

storing the delta data chunk and the base data chunk in the data storage system, wherein the delta data chunk and the base data chunk represent the target data chunk.

6. The computer-implemented method of claim 5, further comprising:

removing the target data chunk from the data storage system after the delta data chunk is generated.

7. The computer-implemented method of claim 1, further comprising:

transmitting the delta data chunk and the base data chunk to an auxiliary data storage system.

8. The computer-implemented method of claim 1, further comprising:

estimating the compression achievable of delta encoding the target data chunk relative to the base data chunk.

9. The computer-implemented method of claim 1, wherein sorting the representative data comprises:

dividing representative data of the plurality of data chunks into a plurality of bin files where representative data of the plurality of data chunks sharing common representative data are placed in a same bin file, each of the plurality of bin files sized to fit within a main memory of the data storage system;

reading into the main memory each of the plurality of bin files; and

comparing and sorting each of the plurality of bin files according to a first feature defined in representative data of the plurality of data chunks.

10. The computer-implemented method of claim 9, wherein sorting the representative data occurs for each feature of the representative data such that the representative data in the representative data list is first sorted based on the first feature of the plurality of data chunks and subsequently sorted based on a second feature of the plurality of data chunks, and

wherein during the sorting iteration using the first feature delta data chunks are generated for one or more pairs of data chunks that have identical first features and wherein during the sorting iteration using the second feature delta data chunks are generated for one or more pairs of data chunks that have identical second features.

11. The computer-implemented method of claim 10, further comprising:

removing, following generation of delta data chunks for one or more pairs of data chunks that have equal first features and prior to sorting the representative data list based on the second feature, the representative data from the representative data list for one of the data chunks in each pair of data chunks.

12. The computer-implemented method of claim 9, wherein representative data of the plurality of data chunks in the same bin file share the first feature,

wherein sorting the representative data occurs in each bin file using the first feature of the plurality of data chunks and secondarily based on a second feature of the plurality of data chunks, and

wherein delta data chunks are generated for one or more pairs of data chunks that have one or more of identical first features or identical second features.

13. The computer-implemented method of claim 12, further comprising:

sorting, following generating the delta data chunks for one or more pairs of data chunks that have identical first or second features, the representative data using the second feature; and

generating one or more pairs of delta data chunks for data chunks that have representative data with identical second features.

14. The computer-implemented method of claim 1, wherein generating representative data comprises:

inputting a data chunk into a collision-resistant hash function;

receiving from the hash function a hash value for the data chunk; and

assigning the hash value to the data chunk.

15. The computer-implemented method of claim 14, wherein generating representative data further comprises:

extracting one or more features from each of the plurality of data chunks; and

assigning the features to each of the plurality of data chunks so that representative data includes the one or more features and the hash value.

16. The computer-implemented method of claim 1, wherein the predetermined algorithm extracts one or more features from each of the plurality of data chunks.

17. A non-transitory computer-readable storage medium having instructions stored therein, which when executed by a computer, cause the computer to:

in response to a request for compressing data in a data storage system, partition the data into a plurality of data chunks, including a target data chunk and base data chunk;

generate representative data for the target data chunk and the base data chunk by applying a predetermined algorithm to the target data chunk and the base data chunk, the representative data including fingerprints of the target data chunk and the base data chunk and a plurality of features extracted from the target data chunk and the base data chunk, wherein each of the plurality of features is a value having a property that a probability of the target data chunk having same representative value as the base data chunk is proportional to data similarity of the target data chunk and the base data chunk;

sort the representative data for the target data chunk and the base data chunk to form a sorted representative data list based on a first feature defined in the representative data for the target data chunk and the base data chunk; and

generate a delta data chunk in the data storage system as the difference between the target data chunk and the base data chunk where the representative data of the target chunk is proximate to the representative data of the base data chunk in the sorted representative data list.

18. The non-transitory computer-readable storage medium of claim 17, wherein the representative data of the base data chunk is proximate to the representative data of the target data chunk such that the representative data of the base data chunk has one or more features that are identical to one or more corresponding features of the representative data of the target data chunk,

wherein sorting the representative data occurs for each feature of the representative data such that the representative data in the representative data list is first sorted based on a first feature of the plurality of data chunks and subsequently sorted based on a second feature of the plurality of data chunks, and

wherein during each sorting iteration delta data chunks are generated for one or more pairs of data chunks that have equal representative data, located proximally in the representative data list.

19. The non-transitory computer-readable storage medium of claim 17, wherein the base data chunk has a similar age as the target data chunk.

20. The non-transitory computer-readable storage medium of claim 17, wherein the non-transitory computer-readable storage medium stores further instructions which when executed by the computer, cause the computer to:

store the delta data chunk and the base data chunk in the data storage system, wherein the delta data chunk and the base data chunk represent the target data chunk.

21. The non-transitory computer-readable storage medium of claim 17, wherein the non-transitory computer-readable storage medium stores further instructions which when executed by the computer, cause the computer to:

transmit the delta data chunk and the base data chunk to an auxiliary data storage system.

22. The non-transitory computer-readable storage medium of claim 17, wherein the non-transitory computer-readable storage medium stores further instructions which when executed by the computer, cause the computer to:

estimate the compression achievable by delta encoding the target data chunk relative to the base data chunk.

23. The non-transitory computer-readable storage medium of claim 17, wherein the non-transitory computer-readable storage medium stores further instructions for sorting the representative data, which when executed by the computer, cause the computer to:

divide representative data of the plurality of data chunks into a plurality of bin files where representative data of the plurality of data chunks sharing common representative data are placed in a same bin file, each of the plurality of bin files sized to fit within main memory of the data storage system;

read into the main memory each of the plurality of bin files;

and compare and sort each of the plurality of bin files according to a feature defined in representative data of the plurality of data chunks.

24. The non-transitory computer-readable storage medium of claim 17, wherein the non-transitory computer-readable storage medium stores further instructions, which when executed by the computer, cause the computer to

remove the target data chunk from the data storage system after the delta data chunk is generated.

25. A data storage system, comprising:

a memory unit to store a chunk storage engine, a compression engine, a comparison and sorting module, a similarity matching module and a delta encoding module;

a processor coupled to the memory unit, the processor configured to execute the chunk storage engine, the compression engine, the comparison and sorting module, the similarity matching module, and the delta encoding module,

the chunk storage engine to partition data into a plurality of data chunks, including a target data chunk and a base data chunk,

the compression engine to generate representative data for the target data chunk and the base data chunk by applying a predetermined algorithm to the target data chunk and the base data chunk, the representative data including fingerprints of the target data chunk and the base data chunk and a plurality of features extracted from the target data chunk and the base data chunk, wherein each of the plurality of features is a value having a property that a probability of the target data chunk having same representative value as the base data chunk is proportional to data similarity of the target data chunk and the base data chunk,

the comparison and sorting module to sort the representative data for the target data chunk and the base data chunk based on similarity of a first feature defined in the representative data for the target data chunk and a first feature defined in the representative data for the base data chunk to form a sorted representative data list,

the similarity matching module to evaluate where representative data of the target chunk are proximate to representative data of the base data chunk in the sorted representative data list, and

the delta encoding module to generate a delta data chunk as the difference between the target data chunk and the base data chunk, wherein the delta data chunk and the base data chunk represent the target data chunk.

26. The data storage system of claim 25, wherein sorting the representative data by the comparison and sorting module comprises:

dividing representative data of the plurality of data chunks into a plurality of bin files where representative data of the plurality of data chunks sharing common representative data are placed in a same bin file, each of the plurality of bin files sized to fit within main memory of the data storage system;

reading into the main memory each of the plurality of bin files; and

comparing and sorting each of the plurality of bin files according to a feature defined in representative data of the plurality of data chunks.

27. The data storage system of claim 25, wherein the target data chunk is removed from the data storage system after the delta data chunk is generated.