Nested Multiple Erasure Correcting Codes for Storage Arrays

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;
• and
• writing the encoded write data as a write stripe across n storage devices in a storage array.

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;
• 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.

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;
• 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.