Nested multiple erasure correcting codes for storage arrays

• US 8,433,979 B2
• Filed: 02/28/2011
• Issued: 04/30/2013
• 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.
• Primary Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US13/036,845
• Publication Number:
  US 20120221926A1
• Time in Patent Office: 792 Days
• Field of Search: 714/770, 714/5
• 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 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<sub>r−

1</sub> 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<sub>r−

1</sub> erasures in any one of the remaining r−

1 rows, up to t<sub>r−

2</sub> 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.

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

3. The system of claim 2, 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 α

<sup>n−

3</sup>, 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.

4. The system of claim 2, 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 α

<sup>2(n−

4)</sup>, 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 α

<sup>n−

4</sup> and the first parity page multiplied by α

<sup>n−

3</sup>; and

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

3 data pages with the first and second parity pages.

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