Nested Multiple Erasure Correcting Codes for Storage Arrays
First Claim
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 t1 parity pages with t1≧
1, a second row contains t2 parity pages with t2≧
t1, a third row contains t3 parity pages with t3≧
t2, and so on, up to an rth row which contains tr parity pages with tr≧
tr-1 and n>
tr>
t1 wherein the encoding allows recovery from up to tr erasures in any one of the r rows, up to tr-1 erasures in any one of the remaining r−
1 rows, up to tr-2 erasures in any one of the remaining r−
2 rows, and so on, such that the encoding allows recovery from up to t1 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 Assignments
0 Petitions
Accused Products
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 tr erasures in any one of the r rows, up to tr-1 erasures in any one of the remaining r−1 rows, up to tr-2 erasures in any one of the remaining r−2 rows, and so on, such that the encoding allows recovery from up to t1 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.
-
Citations
25 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 t1 parity pages with t1≧
1, a second row contains t2 parity pages with t2≧
t1, a third row contains t3 parity pages with t3≧
t2, and so on, up to an rth row which contains tr parity pages with tr≧
tr-1 and n>
tr>
t1 wherein the encoding allows recovery from up to tr erasures in any one of the r rows, up to tr-1 erasures in any one of the remaining r−
1 rows, up to tr-2 erasures in any one of the remaining r−
2 rows, and so on, such that the encoding allows recovery from up to t1 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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 t1 parity pages with t1≧
1, a second row contains t2 parity pages with t2≧
t1, a third row contains t3 parity pages with t3≧
t2, and so on, up to an rth row which contains tr parity pages with tr≧
tr-1 and n>
tr>
t1 wherein the encoding allows recovery from up to tr erasures in any one of the r rows, up to tr-1 erasures in any one of the remaining r−
1 rows, up to tr-2 erasures in any one of the remaining r−
2 rows, and so on, such that the encoding allows recovery from up to t1 erasures in the last remaining row, and output from the encoding includes encoded write data; andwriting the encoded write data as a write stripe across n storage devices in a storage array. - View Dependent Claims (12, 13, 14, 15)
-
-
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 t1 parity pages with t1≧
1, a second row contains t2 parity pages with t2≧
t1, a third row contains t3 parity pages with t3≧
t2, and so on, up to an rth row which contains tr parity pages with tr≧
tr-1 and n>
tr>
t1 wherein the encoding allows recovery from up to tr erasures in any one of the r rows, up to tr-1 erasures in any one of the remaining r−
1 rows, up to tr-2 erasures in any one of the remaining r−
2 rows, and so on, such that the encoding allows recovery from up to t1 erasures in the last remaining row, and output from the encoding includes encoded write data; andwriting the encoded write data as a write stripe across n storage devices in a storage array. - View Dependent Claims (17, 18, 19)
-
-
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 t1 parity pages with t1≧
1, a second row contains t2 parity pages with t2≧
t1, a third row contains t3 parity pages with t3≧
t2, and so on, up to an rth row which contains tr parity pages with tr≧
tr-1 and n>
tr>
t1;determining that the read stripe comprises at least one erased page and that one of the rows contains at most tr erasures, one of the r−
1 remaining rows contains at most tr-1 erasures, one of the r−
2 remaining rows contains at most tr-2 erasures, and so on, until determining that the last remaining row contains t1 erasures; andreconstructing 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. - View Dependent Claims (21, 22)
-
-
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 t1 parity pages with t1≧
1, a second row contains t2 parity pages with t2≧
t1, a third row contains t3 parity pages with t3≧
t2, and so on, up to an rth row which contains tr parity pages with tr≧
tr-1 and n>
tr>
t1;determining that the read stripe comprises at least one erased page and that one of the rows contains at most tr erasures, one of the r−
1 remaining rows contains at most tr-1 erasures, one of the r−
2 remaining rows contains at most tr-2 erasures, and so on, until determining that the last remaining row contains t1 erasures; andreconstructing 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. - View Dependent Claims (24, 25)
-
Specification