Systems and methods for predicting compressibility of data

• US 9,710,166 B2
• Filed: 04/16/2015
• Issued: 07/18/2017
• Est. Priority Date: 04/16/2015
• Status: Active Grant

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Pillay, Sanjay Ramakrishna, Subbarao, Sanjay, Huang, Wei
• Primary Examiner(s): CARDWELL, ERIC
• Application Number:
  US14/688,939
• Publication Number:
  US 20160306561A1
• Time in Patent Office: 824 Days
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0625 Power saving in storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Systems and methods for predicting the compressibility of data in a flash storage device are provided. One such method involves extracting byte intervals from the block of data, each of the byte intervals consisting of a preselected number of bytes, performing a hash function to map the byte intervals into a plurality of bins, the plurality of bins comprising one bin for each possible value of the byte intervals, incrementing a hit count each time more than one of the byte intervals is mapped into a single bin of the plurality of bins, and determining whether to compress the block of data based on a comparison of a ratio of the hit count to a total number of the byte intervals and a preselected threshold. This method may be implemented in hardware to ensure fast and efficient execution.

Claims

1. A method for predicting a compressibility of a block of data, comprising:

extracting byte intervals from the block of data, each of the byte intervals consisting of a preselected number of bytes;

performing a hash function to map the byte intervals into a plurality of bins, the plurality of bins comprising one bin for each possible value of the byte intervals;

incrementing a hit count each time more than one of the byte intervals is mapped into a single bin of the plurality of bins; and

determining whether to compress the block of data based on a comparison of a ratio of the hit count to a total number of the byte intervals and a preselected threshold,

wherein the performing the hash function to map the byte intervals into the plurality of bins comprises performing the hash function using less than a total number of bits in the preselected number of bytes.

2. The method of claim 1, wherein the preselected number of bytes for the byte intervals is two bytes.

3. The method of claim 1, further comprising:

if the ratio of the hit count to the total number of the byte intervals is greater than the preselected threshold, compressing the data block.

4. The method of claim 1, further comprising:

if the ratio of the hit count to the total number of the byte intervals is less than the preselected threshold, determining not to compress the data block.

5. The method of claim 1, wherein the block of data is a block in a flash storage device.

6. The method of claim 1, wherein the plurality of bins consists of one bin for each possible value of the byte intervals.

7. The method of claim 1, wherein the extracting byte intervals from the block of data comprises:

setting the plurality of bins to zero;

setting the hit count to zero; and

extracting byte intervals from the block of data.

8. The method of claim 7:

wherein the performing the hash function to map the byte intervals into the plurality of bins comprises;

setting, if a current bin of the plurality of bins mapped to a current byte interval of the byte intervals is not set to one, the current bin to one; and

wherein the incrementing the hit count each time more than one of the byte intervals is mapped into the single bin of the plurality of bins comprises;

incrementing, if the current bin mapped to the current byte interval is set to one, the hit count.

9. A system for predicting a compressibility of a block of data, comprising:

an extractor configured to extract byte intervals from the block of data, each of the byte intervals consisting of a preselected number of bytes;

a hash configured to map the byte intervals into a plurality of bins using less than a total number of bits in the preselected number of bytes, the plurality of bins comprising one bin for each possible value of the byte intervals;

a counter configured to increment a hit count each time more than one of the byte intervals is mapped into a single bin of the plurality of bins; and

a compression determiner configured to determine whether to compress the block of data based on a comparison of a ratio of the hit count to a total number of the byte intervals and a preselected threshold.

10. The system of claim 9, wherein the preselected number of bytes for the byte intervals is two bytes.

11. The system of claim 9, further comprising:

a compressor configured to compress the data block if the ratio of the hit count to the total number of the byte intervals is greater than the preselected threshold.

12. The system of claim 9, further comprising:

a compressor configured not to compress the data block if the ratio of the hit count to the total number of the byte intervals is less than the preselected threshold.

13. The system of claim 9, wherein the block of data is a block in a flash storage device.

14. The system of claim 9, wherein the plurality of bins consists of one bin for each possible value of the byte intervals.

15. The system of claim 9:

wherein the plurality of bins is initially set to zero; and

wherein the hit count is initially set to zero.

16. The system of claim 15:

wherein the system is configured to set, if a current bin of the plurality of bins mapped to a current byte interval of the byte intervals is not set to one, the current bin to one; and

wherein the counter is configured to increment, if the current bin mapped to the current byte interval is set to one, the hit count.