Pre-cache similarity-based delta compression for use in a data storage system

• US 9,582,222 B2
• Filed: 02/06/2012
• Issued: 02/28/2017
• Est. Priority Date: 04/30/2009
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Yang, Qing, Ren, Jin
• Primary Examiner(s): Alsip, Michael
• Application Number:
  US13/366,846
• Publication Number:
  US 20120137061A1
• Time in Patent Office: 1,849 Days
• US Class Current: 1/1
• 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 2212/214 Solid state disk
• CPC Class Codes: G06F 2212/311 In host system
• CPC Class Codes: G06F 2212/312 In storage controller
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/068 Hybrid storage device
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A data storage caching architecture supports using native local memory such as host-based RAM, and if available, Solid State Disk (SSD) memory for storing pre-cache delta-compression based delta, reference, and independent data by exploiting content locality, temporal locality, and spatial locality of data accesses to primary (e.g. disk-based) storage. The architecture makes excellent use of the physical properties of the different types of memory available (fast r/w RAM, low cost fast read SSD, etc) by applying algorithms to determine what types of data to store in each type of memory. Algorithms include similarity detection, delta compression, least popularly used cache management, conservative insertion and promotion cache replacement, and the like.

Claims

1. A method comprising:

processing a data block in a data storage system with a processor, producing a plurality of signatures, wherein processing the data block comprises generating a signature for every two or more consecutive bytes of the data block;

determining similarity of the data block to at least one reference data block using at least a portion of the plurality of signatures; and

generating, with the processor, cache data that represents differences between the data block and the at least one reference data block;

wherein generating the signature for every two or more consecutive bytes of the data block comprises generating the signature for every three consecutive bytes of the data block, wherein the data block comprises a four kilo-byte (4 KB) block, and wherein a number of signatures from the data block is the plurality of signatures is 4K−

2.

2. The method of claim 1 wherein the determining similarity includes comparing signature occurrence data for the data block to signature occurrence data for the reference block.

3. The method of claim 1 wherein the determining similarity includes generating a wavelet transform for each data block and comparing a plurality of sub-signatures and wavelet transform coefficients of the wavelet transform for at least one data block and at least one reference block.

4. The method of claim 1 wherein the determining similarity includes producing a histogram of a portion of the plurality of signatures.

5. The method of claim 1 wherein the reference block comprises a block of data for which a calculated signature popularity exceeds a threshold.

6. The method of claim 5 wherein the threshold IS a reference block popularity threshold.

7. The method of claim 1 wherein the generating the cache data includes generating a delta block that includes differences between a plurality of data blocks and the at least one reference block and meta data that maps each data block to the at least one reference block.

8. The method of claim 1 wherein the generating the cache data includes generating a set of delta blocks that define differences between a plurality of data blocks and the at least one reference block and meta data that maps each data block to at least one reference block.

20. The method of claim 1, further comprising selecting the portion of the plurality of signatures based on a frequency of the signatures in the data block.

9. A method comprising:

processing a plurality of data blocks with a processor to produce a plurality of signatures that facilitate determining similarity of the plurality of data blocks in a data storage system;

calculating with the processor a signature heat map of a portion of the plurality of signatures to facilitate determining a reference block for similarity-based delta compression of pre-cache data; and

generating, with the processor, cache data that represents differences between a portion of the plurality of data blocks and the determined reference block;

wherein generating the signature for every two or more consecutive bytes of the data block comprises generating the signature for every three consecutive bytes of the data block, wherein the data block comprises a four kilo-byte (4 KB) block, and wherein a number of signatures from the data block is the plurality of signatures is 4K−

2.

10. The method of claim 9 wherein the signature heat map is a two-dimensional array of signature related data.

11. The method of claim 10 wherein the signature heat map is the two-dimensional array wherein a first dimension is the number of possible signature values and a second dimension is a number of sub-signatures.

12. The method of claim 10 wherein the signature heat map is the two dimensional array wherein a first dimension is the number of possible signature values and a second dimension is a number of active input/output (I/O) accesses associated with each possible signature value during a period of time.

13. The method of claim 9 further comprises storing the reference block in a cache memory of the data storage system.

14. The method of claim 9 further comprises storing the reference block in an SSD portion of a cache memory of the data storage system.

15. The method of claim 9 further comprises storing the reference block in a RAM portion of the cache memory of the data storage system.

16. The method of claim 9 further comprises storing the reference block in a HDD portion of the cache memory of the data storage system.

17. The method of claim 9 further comprises storing in an SSD portion of a cache memory of the data storage system a delta block comprising cache data that represents difference between a plurality of pre-cache data blocks and the determined reference block.

18. The method of claim 9 further comprises storing in a RAM portion of a cache memory of the data storage system a delta block comprising cache data that represents difference between a plurality of pre-cache data blocks and the determined reference block.

19. The method of claim 9 further comprises storing in an HDD portion of a cache memory of the data storage system a delta block comprising cache data that represents difference between a plurality of pre-cache data blocks and the determined reference block.