Prefetch data needed in the near future for delta compression

• US 9,026,740 B1
• Filed: 06/13/2012
• Issued: 05/05/2015
• Est. Priority Date: 06/13/2012
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Shilane, Philip N., Wallace, Grant R., Huang, Mark L.
• Primary Examiner(s): KROFCHECK, MICHAEL C
• Application Number:
  US13/495,795
• Time in Patent Office: 1,056 Days
• US Class Current: 711/137
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 12/0862 with prefetch

Abstract

A computer-implemented method and system for improving efficiency in a delta compression process selects a data chunk to delta compress and generate matching criteria for the selected data chunk. The method and system searches for a similar data chunk using the matching criteria and loads a best match data chunk from the search. Locality data for the best match data chunk is determined and a plurality of data chunks with matching locality data are pre-fetched.

Claims

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

selecting a data chunk to delta compress;

generating matching criteria for the selected data chunk;

identifying a set of similar data chunks using the matching criteria;

identifying a best match data chunk from the set of similar data chunks based on a degree of similarity to the selected data chunk and a speed at which each similar data chunk can be retrieved;

determining locality data for the best match data chunk; and

pre-fetching a plurality of data chunks with matching locality data for delta compressing data chunks subsequent to the selected data chunk.

2. The method of claim 1, further comprising:

adding the selected data chunk to a cache.

3. The method of claim 1, further comprising:

adding the pre-fetched plurality of data chunks to a cache.

4. The method of claim 1, wherein generating matching criteria for the selected data chunk further comprises:

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

5. The method of claim 1, wherein identifying the set of similar data chunks using the matching criteria comprises:

searching an index of sketches for data chunks in a data storage with matching sketches.

6. The method of claim 1, wherein the locality data is any one of stream order data, data chunk address data, temporal data, file data, container data, or similarity data.

7. The method of claim 1, pre-fetching the plurality of data chunks comprises:

loading the plurality of data chunks based on a set of references to the plurality of data chunks in a queue.

8. The method of claim 1, wherein the locality data is stream order data, wherein the plurality of pre-fetched data chunks are close to the best match data chunk in stream order.

9. 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 comprising:

selecting a data chunk to delta compress;

generating matching criteria for the selected data chunk;

identifying a set of similar data chunks using the matching criteria;

identifying a best match data chunk from the set of similar data chunks based on a degree of similarity to the selected data chunk and a speed at which each similar data chunk can be retrieved;

determining locality data for the best match data chunk; and

pre-fetching a plurality of data chunks with matching locality data.

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

adding the selected data chunk to a cache.

11. The non-transitory computer-readable storage medium of claim 9, further comprising:

adding the pre-fetched plurality of data chunks to a cache.

12. The non-transitory computer-readable storage medium of claim 9, wherein generating matching criteria for the selected data chunk further comprises:

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

13. The non-transitory computer-readable storage medium of claim 9, wherein identifying a set of similar data chunks using the matching criteria comprises:

searching an index of sketches for data chunks in a data storage with matching sketches.

14. The non-transitory computer-readable storage medium of claim 9, wherein the locality data is any one of stream order data, data chunk address data, temporal data, file data, container data or similarity data.

15. The non-transitory computer-readable storage medium of claim 9, pre-fetching the plurality of data chunks comprises:

loading the plurality of data chunks based on a set of references to the plurality of data chunks in a queue.

16. 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 pre-fetch module coupled to the cache, data storage system and delta processing module, the pre-fetch module to identify a best match data chunk and retrieve the third set of data chunks that match locality data with a selected data chunk from the first set of data chunks and to store the retrieved third set of data chunks in the cache for delta compressing data chunks subsequent to the selected data chunk,

wherein the pre-fetch module identifies the best match data chunk based on a degree of similarity to the selected data chunk and a speed at which each data chunk can be retrieved.

17. The storage system of claim 16, wherein the pre-fetch module performs a resemblance hash over the selected data chunk from the first set of data chunks to generate a sketch for the selected data chunk.

18. The storage system of claim 16, wherein the pre-fetch module searches an index of sketches for data chunks in the third set of data chunks in the data storage with matching sketches.

19. The storage system of claim 18, wherein the pre-fetch module stores the third set of data chunks based on a set of references to the third set of data chunks in a queue.