Data reduction techniques in a flash-based key/value cluster storage

• US 10,055,161 B1
• Filed: 01/20/2016
• Issued: 08/21/2018
• Est. Priority Date: 03/31/2014
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Meiri, David, Kucherov, Anton, Shveidel, Vladimir
• Primary Examiner(s): Rutz, Jared I
• Assistant Examiner(s): Wu, Stephanie
• Application Number:
  US15/001,784
• Time in Patent Office: 944 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/2069 Management of state, configuration or failover
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0833 in combination with broadcast means (e.g. for invalidation or updating)
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 2201/85 Active fault masking without idle spares active fault masking without idle spare hardware where processing functionality is redundant G06F11/2035
• CPC Class Codes: G06F 2211/1014 Compression, i.e. RAID systems with parity using compression techniques
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
• CPC Class Codes: G06F 2212/683 Invalidation
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0661 Format or protocol conversion arrangements
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G11C 2207/102 Compression or decompression of data before storage
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents

Abstract

In one aspect, a method includes splitting empty RAID stripes into sub-stripes and storing pages into the sub-stripes based on a compressibility score. In another aspect, a method includes reading pages from 1-stripes, storing compressed data in a temporary location, reading multiple stripes, determining compressibility score for each stripe and filling stripes based on the compressibility score. In a further aspect, a method includes scanning a dirty queue in a system cache, compressing pages ready for destaging, combining compressed pages in to one aggregated page, writing one aggregated page to one stripe and storing pages with same compressibility score in a stripe.

Claims

1. A method, comprising:

reading pages from 1-stripes, wherein 1-stripes are not compressed;

storing compressed data in a temporary location;

reading j 1-stripes, where j is greater than or equal to one;

determining compressibility score, S, for each 1-stripe of j stripes; and

filling S-stripes based on the compressibility score by writing compressed pages to S-stripes corresponding to the compressibility score, S, comprising;

filling 8-stripes before 4-stripes if 8-stripes exist by locating 8N pages with a score greater than or equal to 8;

filling 4-stripes before 2-stripes if 4-stripes exits by locating 4N pages with a score greater than or equal to 4;

filling 2-stripes before 1-stripes if 2-stripes exist by locating 2N pages with a score greater than or equal to 2,

wherein N>

1 and N equals the number of disks minus K, and K is the number of parity disks where K>

1.

2. The method of claim 1, further comprising:

storing in the system'"'"'s data cache uncompressed; and

after the data reaches the persistent uncompressed data cache;

acknowledging the write to a user.

3. The method of claim 1, further comprising adding a queue for each compressibility score.

4. The method of claim 1, further comprising:

adding a queue; and

destaging smaller pages to one larger page using the queue.

5. The method of claim 1, further comprising assigning the S-stripes differing widths based on the compressibility score, S.

6. The method of claim 1, further comprising:

determining a page cannot be decompressed;

declaring the page as being corrupt;

using RAID mechanisms to rebuild the page;

fixing a corrupt page after the page is rebuilt;

returning correct data to a user; and

if the rebuild fails, returning an error message to the user.

7. An apparatus, comprising:

electronic hardware circuitry configured to;

read pages from 1-stripes, wherein 1-stripes are not compressed;

store compressed data in a temporary location;

read j 1-stripes, where j is greater than or equal to one;

determine compressibility score, S, for each 1-stripe of j stripes; and

fill S-stripes based on the compressibility score by writing compressed pages to S-stripes corresponding to the compressibility score, S, comprising;

fill 8-stripes before 4-stripes if 8-stripes exist by locating 8N pages with a score greater than or equal to 8;

fill 4-stripes before 2-stripes if 4-stripes exits by locating 4N pages with a score greater than or equal to 4;

fill 2-stripes before 1-stripes if 2-stripes exist by locating 2N pages with a score greater than or equal to 2,

wherein N>

1 and N equals the number of disks minus K, and K is the number of parity disks where K>

1.

8. The apparatus of claim 7, wherein the circuitry comprises at least one of a processor, a memory, a programmable logic device or a logic gate.

9. The apparatus of claim 7, further comprising circuitry to:

store in the system'"'"'s data cache uncompressed; and

after the data reaches the persistent uncompressed data cache;

acknowledge the write.

10. The apparatus of claim 7, further comprising circuitry to add a queue for a different compression level.

11. The apparatus of claim 7, further comprising circuitry to:

add a queue; and

destage smaller pages to one larger page using the queue.

12. The apparatus of claim 7, further comprising circuitry to assign stripes of different widths.

13. The apparatus of claim 7, further comprising circuitry to:

determine a page cannot be decompressed;

declare the page as being corrupt;

use RAID mechanisms to rebuild the page;

fix corrupt page after the page is rebuilt;

return correct data to a user; and

if the rebuild fails, return an error message to the user.

14. An article comprising:

a non-transitory computer-readable medium that stores computer-executable instructions, the instructions causing a machine to;

read pages from 1-stripes, wherein 1-stripes are not compressed;

store compressed data in a temporary location;

read j 1-stripes, where j is greater than or equal to one;

determine compressibility score, S, for each 1-stripe of j stripes; and

fill S-stripes based on the compressibility score by writing compressed pages to S-stripes corresponding to the compressibility score, S, comprising;

fill 8-stripes before 4-stripes if 8-stripes exist by locating 8N pages with a score greater than or equal to 8;

fill 4-stripes before 2-stripes if 4-stripes exits by locating 4N pages with a score greater than or equal to 4;

fill 2-stripes before 1-stripes if 2-stripes exist by locating 2N pages with a score greater than or equal to 2,

wherein N>

1 and N equals the number of disks minus K, and K is the number of parity disks where K>

1.

15. The article of claim 14, further comprising instructions causing the machine to:

store in the system'"'"'s data cache uncompressed; and

after the data reaches the persistent uncompressed data cache;

acknowledge the write.

16. The article of claim 14, further comprising instructions causing the machine to add a queue for a different compression level.

17. The article of claim 14, further comprising instructions causing the machine to:

add a queue; and

destage smaller pages to one larger page using the queue.

18. The article of claim 14, further comprising instructions causing the machine to assign stripes of different widths.

19. The article of claim 14, further comprising instructions causing the machine to:

determine a page cannot be decompressed;

declare the page as being corrupt;

use RAID mechanisms to rebuild the page;

fix a corrupt page after the page is rebuilt;

return correct data to a user; and

if the rebuild fails, return an error message to the user.