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

Patent metadata

Field	Value
Publication number	US-9606870-B1
Application number	US-201414230405-A
Country	US
Kind code	B1
Filing date	Mar 31, 2014
Priority date	Mar 31, 2014
Publication date	Mar 28, 2017
Grant date	Mar 28, 2017

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.

First claim

What is claimed is:

1. A method comprising:
splitting empty RAID stripes into sub-stripes;
storing pages into the sub-stripes based on a compressibility score;
reading pages from 1-stripes;
writing to a free location in a S-stripe compressed pages, wherein S>0;
testing each page for compressibility;
giving each page a compressibility score, S; and
finding S*N pages with the same compressibility score,
wherein each 1-stripe comprises N pages of data and K pages of parity, where K>1 and N>1 and N equals the number of disks minus K,
wherein each S-stripe comprises includes S*N+S*K sub-pages, and
wherein storing pages into the sub-stripes based on a compressibility score comprises storing pages with the same compressibility score in the same sub-stripe.

2. The method of claim 1 , wherein for 4 KB pages each 1-stripe consumes a total of 4*(N+K) KB of flash storage.

3. The method of claim 2 , wherein K equals 2.

4. The method of claim 2 , wherein S equals one of 1, 2, 4, or 8.

5. The method of claim 4 , wherein a 2-stripe comprises 2N+2K sub-pages of 2 KB,
wherein a 4-stripe comprises 4N+4K sub-pages of 1 KB, and
wherein an 8-stripe comprises 8N+8K sub-pages of 512 B.

6. An apparatus, comprising:
electronic hardware circuitry configured to:
split empty RAID stripes into sub-stripes;
store pages into the sub-stripes based on a compressibility score;
read pages from 1-stripes; and

write to a free location in a S-stripe compressed pages, wherein S>0;
test each page for compressibility;
give each page a compressibility score, S; and
find S*N pages with the same compressibility score,

wherein each 1-stripe comprises N pages of data and K pages of parity, where K>1 and N>1 and N equals the number of disks minus K,
wherein each S-stripe comprises includes S*N+S*K sub-pages, and
wherein storing pages into the sub-stripes based on a compressibility score comprises storing pages with the same compressibility score in the same sub-stripe.

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

8. The apparatus of claim 6 , wherein for 4 KB pages each 1-stripe consumes a total of 4*(N+K) KB of flash storage.

9. The apparatus of claim 8 , wherein K equals 2.

10. The apparatus of claim 8 , wherein S equals one of 1, 2, 4, or 8.

11. The apparatus of claim 10 , wherein a 2-stripe comprises 2N+2K sub-pages of 2 KB,
wherein a 4-stripe comprises 4N+4K sub-pages of 1 KB, and
wherein an 8-stripe comprises 8N+8K sub-pages of 512 B.

12. An article comprising:
a non-transitory computer-readable medium that stores computer-executable instructions, the instructions causing a machine to:
split empty RAID stripes into sub-stripes;
store pages into the sub-stripes based on a compressibility score;
read pages from 1-stripes;

write to a free location in a S-stripe compressed pages, wherein S>0;
test each page for compressibility;
give each page a compressibility score, S; and
find S*N pages with the same compressibility score,

wherein each 1-stripe comprises N pages of data and K pages of parity, where K>1 and N>1 and N equals the number of disks minus K,
wherein each S-stripe comprises includes S*N+S*K sub-pages, and
wherein storing pages into the sub-stripes based on a compressibility score comprises storing pages with the same compressibility score in the same sub-stripe.

13. The article of claim 12 , wherein for 4 KB pages each 1-stripe consumes a total of 4*(N+K) KB of flash storage.

14. The article of claim 13 , wherein K equals 2.

15. The article of claim 13 , wherein S equals one of 1, 2, 4, or 8.

16. The article of claim 15 , wherein a 2-stripe comprises 2N+2K sub-pages of 2 KB,
wherein a 4-stripe comprises 4N+4K sub-pages of 1 KB, and
wherein an 8-stripe comprises 8N+8K sub-pages of 512 B.

Assignees

• Emc Corp
• Emc Ip Holding Co Llc

Inventors

• Meiri David
• Kucherov Anton
• Shveidel Vladimir

Classifications

• G06F11/1076 Primary

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• G11C29/52

  Protection of memory contents; Detection of errors in memory contents · CPC title

• G11C2207/102

  Compression or decompression of data before storage · CPC title

• G06F2211/1014

  Compression, i.e. RAID systems with parity using compression techniques · CPC title

• G06F11/108

  Parity data distribution in semiconductor storages, e.g. in SSD · CPC title