Preferential selection of candidates for delta compression

• US 9,262,434 B1
• Filed: 11/13/2014
• Issued: 02/16/2016
• Est. Priority Date: 06/13/2012
• Status: Active Grant

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Shilane, Philip N., Wallace, Grant R., Huang, Mark L.
• Primary Examiner(s): Choi, Yuk Ting
• Application Number:
  US14/540,895
• Time in Patent Office: 460 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1756 based on delta files
• CPC Class Codes: H03M 7/3091 Data deduplication

Abstract

A computer-implemented method and system for improving efficiency in a delta compression process in a data storage system selects a data chunk to delta compress and generates a sketch for the selected data chunk. The method and system search for a set of candidate data chunks with a matching sketch and rank the set of candidate data chunks by degree of sketch matching. The set of candidate data chunks are tie-braked using location status data for each candidate and the selected data chunk is delta compressed with a selected candidate data chunk. The delta compressed selected data chunk is then stored in a data storage system.

Claims

1. A computer-implemented method for improving efficiency in a delta compression process in a data storage system, the method comprising:

selecting a data chunk to delta compress;

generating a sketch for the selected data chunk;

searching for a set of candidate data chunks using the sketch;

ranking the set of candidate data chunks by degree of sketch matching;

tie-breaking the set of candidate data chunks, where the set of candidate data chunks has an equal degree of sketch matching, including ranking a candidate data chunk stored in a cache higher than a candidate data chunk stored on a storage device, and, ranking a decompressed candidate data chunk higher than a compressed candidate data chunk having a same location status as the decompressed candidate data chunk;

delta compressing the selected data chunk with a selected candidate data chunk of the ranked set of candidate data chunks; and

storing the delta compressed selected data chunk in the data storage system.

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

generating a set of features for the selected data chunk.

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

searching an index of data chunks to identify the set of candidate data chunks by comparing features in the index with the set of features of the selected data chunk.

4. The method of claim 1, wherein ranking the set of candidates data chunks by degree of sketch matching further comprises:

ranking the set of candidates by a number of matching features between a candidate and the selected data chunk.

5. The method of claim 1, wherein the location status data indicates the location and status of the candidate 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.

7. The method of claim 1, wherein tie-breaking the set of candidate data chunks using location status data for each candidate orders the set of candidate data chunks based on access times to retrieve each candidate data chunk.

6. A computer-implemented method for improving efficiency in a delta compression process in a data storage system, the method comprising:

selecting a data chunk to delta compress;

generating a sketch for the selected data chunk;

searching for a set of candidate data chunks using the sketch;

ranking the set of candidate data chunks by degree of sketch matching;

tie-breaking the set of candidate data chunks, where the set of candidate data chunks has an equal degree of sketch matching, using location status data for each candidate data chunk, wherein the location status data indicates one or more of the location of a corresponding candidate data chunk in a set of memory devices or a compression status of the corresponding candidate data chunk, wherein the location status data indicates the location and status of the candidate 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, wherein tie-breaking the set of candidate data chunks using location status data for each candidate prefers a decompressed in a cache status over a compressed in a cache status, and wherein tie-breaking 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;

delta compressing the selected data chunk with a selected candidate data chunk; and

storing the delta compressed selected data chunk in the data storage system.

8. 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 improving efficiency in a delta compression process, the method comprising:

selecting a data chunk to delta compress;

generating a sketch for the selected data chunk;

searching for a set of candidate data chunks using the sketch;

ranking the set of candidate data chunks by degree of sketch matching;

tie-breaking the set of candidate data chunks, where the set of candidate data chunks has an equal degree of sketch matching, including ranking a candidate data chunk stored in a cache higher than a candidate data chunk stored on a storage device, and, ranking a decompressed candidate data chunk higher than a compressed candidate data chunk having a same location status as the decompressed candidate data chunk;

delta compressing the selected data chunk with a selected candidate data chunk of the ranked candidate data chunks; and

storing the delta compressed selected data chunk in a data storage system.

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

generating a set of features for the selected data chunk.

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

searching an index of data chunks to identify the set of candidate data chunks by comparing features in the index with the set of features of the selected data chunk.

11. The non-transitory computer-readable storage medium of claim 8, wherein ranking the set of candidates data chunks by degree of sketch matching further comprises:

ranking the set of candidates by a number of matching features between a candidate and the selected data chunk.

12. The non-transitory computer-readable storage medium of claim 8, wherein the location status data indicates the location and status of the candidate 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.

13. The non-transitory computer-readable storage medium of claim 8, wherein tiebreaking the set of candidate data chunks using location status data for each candidate orders the set of candidate data chunks based on access times to retrieve each candidate data chunk.

14. 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 improving efficiency in a delta compression process, the method comprising:

selecting a data chunk to delta compress;

generating a sketch for the selected data chunk;

searching for a set of candidate data chunks using the sketch;

ranking the set of candidate data chunks by degree of sketch matching;

tie-breaking the set of candidate data chunks, where the set of candidate data chunks has an equal degree of sketch matching, using location status data for each candidate data chunk, wherein the location status data indicates one or more of the location of a corresponding candidate data chunk in a set of memory units or a compression status of the corresponding candidate data chunk, wherein the location status data indicates the location and status of the candidate 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, wherein tiebreaking the set of candidate data chunks using location status data for each candidate prefers a decompressed in a cache status over a compressed in a cache status, wherein tiebreaking the set of candidates data chunks using location status data for each candidate prefers a compressed in a cache status over a compressed in a data storage status;

delta compressing the selected data chunk with a selected candidate data chunk; and

storing the delta compressed selected data chunk in a data storage system.

15. A delta compression system, comprising:

a delta processing module to delta compress a first set of data chunks; and

a cache to store a second set of data chunks;

a data storage system to store a third set of data chunks;

a preferential selection module coupled to the cache, data storage system and delta processing module, the preferential selection module to identify a candidate to serve as a base chunk for delta compression by ranking a set of candidate base chunks from the second set of data chunks and third set of data chunks by similarity to a data chunk from the first set of data chunks then tie-breaking a ranked set of candidate data chunks, where the set of candidate data chunks has an equal degree of sketch matching, tie-breaking comprises ranking a candidate data chunk stored in a cache higher than a candidate data chunk stored on a storage device, and, ranking a decompressed candidate data chunk higher than a compressed candidate data chunk having a same location status as the decompressed candidate data chunk;

the delta compression module configured to;

select a data chunk to compress from the first set of data chunks;

delta compress the selected data chunk with the identified candidate to serve as a base chunk for delta compression; and

store the delta compressed selected data chunk in the data storage system.

16. The delta compression system of claim 15, wherein the location status data indicates the location and status of the candidate 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.

17. A delta compression system comprising:

a delta processing module to delta compress a first set of data chunks; and

a cache to store a second set of data chunks;

a data storage system to store a third set of data chunks;

a preferential selection module coupled to the cache, data storage system and delta processing module, the preferential selection module to identify a candidate to serve as a base chunk for delta compression by ranking a set of candidate base chunks from the second set of data chunks and third set of data chunks by similarity to a data chunk from the first set of data chunks then tie-breaking a ranked set of candidate data chunks, where the set of candidate data chunks has an equal degree of sketch matching, using location status information, wherein the location status information indicates one or more of the location of a corresponding candidate data chunk in a set of memory devices or a compression status of the corresponding candidate data chunk, wherein the location status data indicates the location and status of the candidate 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, wherein tie-breaking the set of candidate data chunks using location status data for each candidate prefers a decompressed in a cache status over a compressed in a cache status, wherein tie-breaking 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.