Nested Multiple Erasure Correcting Codes for Storage Arrays

• US 20120221926A1
• Filed: 02/28/2011
• Published: 08/30/2012
• Est. Priority Date: 02/28/2011
• Status: Active Grant

• Current Assignee: SK Hynix Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Blaum, Mario, Hafner, James L., Hetzler, Steven R.
• Granted Patent: US 8,433,979 B2
• Time in Patent Office: Days
• US Class Current: 714/770
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 2211/1045 Nested RAID, i.e. implementing a RAID scheme in another RAID scheme
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: G06F 2211/1059 Parity-single bit-RAID5, i.e. RAID 5 implementations

Abstract

Embodiments of the invention relate to storing data in a storage array. An aspect of the invention includes receiving write data. The write data is arranged into “r” rows and “n” columns of pages, with each page including a plurality of sectors. The write data is encoded using a plurality of horizontal and vertical erasure correcting codes on the pages. The encoding allows recovery from up to t_r erasures in any one of the r rows, up to t_r-1 erasures in any one of the remaining r−1 rows, up to t_r-2 erasures in any one of the remaining r−2 rows, and so on, such that the encoding allows recovery from up to t₁ erasures in the last remaining row. Encoded write data is output from the encoding. The encoded write data is written as a write stripe across n storage devices in a storage array.

Claims

1. A method for storing data, the method comprising:

receiving write data;

arranging the write data in r rows and n columns of pages, each page comprising a plurality of sectors;

encoding the write data using a plurality of horizontal and vertical erasure correcting codes on the pages such that a first row contains t₁ parity pages with t₁≧

1, a second row contains t₂ parity pages with t₂≧

t₁, a third row contains t₃ parity pages with t₃≧

t₂, and so on, up to an rth row which contains t_r parity pages with t_r≧

t_r-1 and n>

t_r>

t₁ wherein the encoding allows recovery from up to t_r erasures in any one of the r rows, up to t_r-1 erasures in any one of the remaining r−

1 rows, up to t_r-2 erasures in any one of the remaining r−

2 rows, and so on, such that the encoding allows recovery from up to t₁ erasures in the last remaining row, and output from the encoding includes encoded write data;

writing the encoded write data as a write stripe across n storage devices in a storage array.

2. The method of claim 1, wherein t₁ of the parity pages in any row in the write stripe correspond to a t₁ erasure correcting code whose data pages are the remaining n−

t₁ pages in the row.

3. The method of claim 1, wherein at least one of the horizontal and vertical erasure correcting codes is a maximum distance separable (MDS) code.

4. The method of claim 3, wherein the MDS code allows recovery from up to two erasures, the MDS code dividing each page into z−

1 segments, z is a prime number, and the length n of the MDS code is at most z+1, wherein

a first parity page is computed as an exclusive or (XOR) of a first data page, a second data page multiplied by α

, a third data page multiplied by α

², a fourth data page multiplied by α

³, and so on, up to data page n−

2 multiplied by α

^n-3, where α

is a root of a polynomial of degree z−

1; and

a second parity page is computed as an XOR of the first n−

2 data pages with the first parity page.

5. The method of claim 4, wherein the polynomial is 1+x+x²+ . . . +x^z-1.

6. The method of claim 3, wherein the MDS code allows recovery from up to three erasures, the MDS code dividing each page into z−

1 segments, z is a prime number, and the length n of the code is at most z+1, wherein

a first parity page is computed as an XOR of a first data page, a second data page multiplied by α

², a third data page multiplied by α

⁴, a fourth data page multiplied by α

⁶, and so on, up to data page n−

3 multiplied by α

^2(n-4), where α

is a root of a polynomial of degree z−

1;

a second parity page is computed as an XOR of a first data page, a second data page multiplied by α

, a third data page multiplied by α

², a fourth data page multiplied by α

³, and so on, up to data page n−

3 multiplied by α

^n-4 and the first parity page multiplied by α

^n-3; and

a third parity page is computed as an XOR of the n−

3 data pages with the first and second parity pages.

7. The method of claim 6, wherein the polynomial is 1+x+x²+ . . . +x^z-1.

8. The method of claim 1, wherein t_r is equal to two.

9. The method of claim 1, wherein t_r is equal to three.

10. The method of claim 1, wherein the storage devices are one of hard disk drives and flash drives.

11. A system for storing data in a storage array, the system comprising:

a storage array comprising a plurality of storage devices; and

an array controller configured for;

receiving write data;

arranging the write data in r rows and n columns of pages;

encoding the write data using a plurality of horizontal and vertical erasure correcting codes on the pages such that a first row contains t₁ parity pages with t₁≧

1, a second row contains t₂ parity pages with t₂≧

t₁, a third row contains t₃ parity pages with t₃≧

t₂, and so on, up to an rth row which contains t_r parity pages with t_r≧

t_r-1 and n>

t_r>

t₁ wherein the encoding allows recovery from up to t_r erasures in any one of the r rows, up to t_r-1 erasures in any one of the remaining r−

1 rows, up to t_r-2 erasures in any one of the remaining r−

2 rows, and so on, such that the encoding allows recovery from up to t₁ erasures in the last remaining row, and output from the encoding includes encoded write data; and

writing the encoded write data as a write stripe across n storage devices in a storage array.

12. The system of claim 11, wherein at least one of the horizontal and vertical erasure correcting codes is a maximum distance separable (MDS) code.

13. The system of claim 12, wherein the MDS code allows recovery from up to two erasures, the MDS code dividing each page into z−

1 segments, z is a prime number, and the length n of the code is at most z+1, wherein

a first parity page is computed as an exclusive or (XOR) of a first data page, a second data page multiplied by α

, a third data page multiplied by α

², a fourth data page multiplied by α

³, and so on, up to data page n−

2 multiplied by α

^n-3, where α

is a root of a polynomial of degree z−

1; and

a second parity page is computed as an XOR of the first n−

2 data pages with the first parity page.

14. The system of claim 12, wherein the MDS code allows recovery from up to three erasures, the MDS code dividing each page into z−

1 segments, z is a prime number, and the length n of the code is at most z+1, wherein

a first parity page is computed as an XOR of a first data page, a second data page multiplied by α

², a third data page multiplied by α

⁴, a fourth data page multiplied by α

⁶, and so on, up to data page n−

3 multiplied by α

^2(n-4), where α

is a root of a polynomial of degree z−

1;

a second parity page is computed as an XOR of a first data page, a second data page multiplied by α

, a third data page multiplied by α

², a fourth data page multiplied by α

³, and so on, up to data page n−

3 multiplied by α

^n-4 and the first parity page multiplied by α

^n-3; and

a third parity page is computed as an XOR of the n−

3 data pages with the first and second parity pages.

15. The system of claim 11, wherein the storage devices are one of hard disk drives and flash drives.

16. A computer program product for storing data in a storage array, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising computer readable program code configured for;

receiving write data;

arranging the write data in r rows and n columns of pages;

encoding the write data using a plurality of horizontal and vertical erasure correcting codes on the pages such that a first row contains t₁ parity pages with t₁≧

1, a second row contains t₂ parity pages with t₂≧

t₁, a third row contains t₃ parity pages with t₃≧

t₂, and so on, up to an rth row which contains t_r parity pages with t_r≧

t_r-1 and n>

t_r>

t₁ wherein the encoding allows recovery from up to t_r erasures in any one of the r rows, up to t_r-1 erasures in any one of the remaining r−

1 rows, up to t_r-2 erasures in any one of the remaining r−

2 rows, and so on, such that the encoding allows recovery from up to t₁ erasures in the last remaining row, and output from the encoding includes encoded write data; and

writing the encoded write data as a write stripe across n storage devices in a storage array.

17. The system of claim 16, wherein at least one of the horizontal and vertical erasure correcting codes is a maximum distance separable (MDS) code.

18. The system of claim 17, wherein the MDS code allows recovery from up to two erasures, the MDS code dividing each page into z−

1 segments, z is a prime number, and the length n of the code is at most z+1, wherein

a first parity page is computed as an exclusive or (XOR) of a first data page, a second data page multiplied by α

, a third data page multiplied by α

², a fourth data page multiplied by α

³, and so on, up to data page n−

2 multiplied by α

^n-3, where α

is a root of a polynomial of degree z−

1; and

a second parity page is computed as an XOR of the first n−

2 data pages with the first parity page.

19. The system of claim 17, wherein the MDS code allows recovery from up to three erasures, the MDS code dividing each page into z−

1 segments, z is a prime number, and the length n of the code is at most z+1, wherein

a first parity page is computed as an XOR of a first data page, a second data page multiplied by α

², a third data page multiplied by α

⁴, a fourth data page multiplied by α

⁶, and so on, up to data page n−

3 multiplied by α

^2(n-4), where α

is a root of a polynomial of degree z−

1;

a second parity page is computed as an XOR of a first data page, a second data page multiplied by α

, a third data page multiplied by α

², a fourth data page multiplied by α

³, and so on, up to data page n−

3 multiplied by α

^n-4 and the first parity page multiplied by a^n-3; and

a third parity page is computed as an XOR of the n−

3 data pages with the first and second parity pages.

20. A method for correcting erasures in a storage array, the method comprising:

receiving a read stripe from a plurality of n storage devices, the read stripe comprising a block of pages arranged in r rows and n columns with each column corresponding to one of the storage devices, the pages comprising data pages and parity pages, the parity pages generated using a plurality of horizontal and vertical erasure correcting codes, such that a first row contains t₁ parity pages with t₁≧

1, a second row contains t₂ parity pages with t₂≧

t₁, a third row contains t₃ parity pages with t₃≧

t₂, and so on, up to an rth row which contains t_r parity pages with t_r≧

t_r-1 and n>

t_r>

t₁;

determining that the read stripe comprises at least one erased page and that one of the rows contains at most t_r erasures, one of the r−

1 remaining rows contains at most t_r-1 erasures, one of the r−

2 remaining rows contains at most t_r-2 erasures, and so on, until determining that the last remaining row contains t₁ erasures; and

reconstructing the erased pages responsive to the block of pages and to the horizontal and vertical erasure codes, the reconstructing resulting in a recovered read stripe.

21. The method of claim 20, wherein at least one of the horizontal and vertical erasure correcting codes is a maximum distance separable code.

22. The method of claim 20, wherein t_m is equal to 2 or t_m is equal to 3.

23. A computer program product for correcting erasures in a storage array, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising computer readable program code configured for;

receiving a read stripe from a plurality of n storage devices, the read stripe comprising a block of pages arranged in r rows and n columns with each column corresponding to one of the storage devices, the pages comprising data pages and parity pages, the parity pages generated using a plurality of horizontal and vertical erasure correcting codes, such that a first row contains t₁ parity pages with t₁≧

1, a second row contains t₂ parity pages with t₂≧

t₁, a third row contains t₃ parity pages with t₃≧

t₂, and so on, up to an rth row which contains t_r parity pages with t_r≧

t_r-1 and n>

t_r>

t₁;

determining that the read stripe comprises at least one erased page and that one of the rows contains at most t_r erasures, one of the r−

1 remaining rows contains at most t_r-1 erasures, one of the r−

2 remaining rows contains at most t_r-2 erasures, and so on, until determining that the last remaining row contains t₁ erasures; and

reconstructing the erased pages responsive to the block of pages and to the horizontal and vertical erasure codes, the reconstructing resulting in a recovered read stripe.

24. The computer program product of claim 23, wherein at least one of the horizontal and vertical erasure correcting codes is a maximum distance separable code.

25. The computer program product of claim 23, wherein t_m is equal to 2 or t_m is equal to 3.