REDUNDANT DISK ENCODING VIA ERASURE DECODING

• US 20140006850A1
• Filed: 03/04/2013
• Published: 01/02/2014
• Est. Priority Date: 06/29/2012
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Aliev, Artem Alexandrovich, Trifonov, Peter Vladimirovich
• Granted Patent: US 9,081,752 B2
• Time in Patent Office: Days
• US Class Current: 714/6.24
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/2053 where persistent mass storage functionality or persistent mass storage control functionality is redundant error detection or correction in information storage based on relative movement between record carrier and transducer G11B20/18
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations

Abstract

A method is provided of encoding data within a RAID stripe, the RAID stripe being spread across k data disks and r redundancy disks of a RAID group, r≧3, the RAID group having k+r disks, the k data disks and the r redundancy disks within the RAID stripe being distinct, such that, upon failure of any r disks of the k+r disks of the RAID group, the data can be fully recovered using the Forney algorithm. The method includes (a) partitioning the data into k data symbols, (b) storing each of the k data symbols to a respective data disk of the k data disks, (c) generating r Reed-Solomon redundancy symbols by applying the Forney algorithm to the k data symbols, and (d) storing each of the r Reed-Solomon redundancy symbols generated by the Forney algorithm to a respective redundancy disk of the r redundancy disks.

Claims

1. A method of encoding data within a RAID stripe, the RAID stripe being spread across k data disks and r redundancy disks of a RAID group of a data storage system, r≧

2, the RAID group having k+r disks, the k data disks and the r redundancy disks within the RAID stripe being distinct, such that, upon failure of any r disks of the k+r disks of the RAID group, the data can be fully recovered using the Forney erasure decoding algorithm, the method including;

partitioning the data into k data symbols;

storing each of the k data symbols to a respective data disk of the k data disks;

generating r Reed-Solomon redundancy symbols by applying the Forney erasure decoding algorithm to the k data symbols; and

storing each of the r redundancy symbols generated by the Forney erasure decoding algorithm to a respective redundancy disk of the r redundancy disks.

2. The method of claim 1 wherein generating the r redundancy symbols by applying the Forney erasure decoding algorithm includes:

assigning a unique virtual disk number to each of the r redundancy disks, each virtual disk number being drawn from a set of Q integers, Q>

k+r; and

applying the Forney erasure decoding algorithm to the k data symbols to generate the r Reed-Solomon redundancy symbols from a virtual Reed-Solomon codeword having Q symbols, the generated r Reed-Solomon redundancy symbols having location codes specified by the virtual disk numbers assigned to the r redundancy disks, the k data symbols and the r redundancy symbols forming a shortened Reed-Solomon code.

3. The method of claim 2 wherein:

Q=2^m−

1, m being an integer greater than 2, the set of Q integers including all integers from 0 to 2^m−

2, inclusive; and

assigning the unique virtual disk number to each of the r redundancy disks includes choosing r numbers from the set of Q integers, the r chosen numbers spanning a minimal number of cyclotomic cosets modulo 2^m−

1 over a Galois Field of order 2^m [GF(2^m)], the r chosen numbers being the assigned virtual disk numbers.

4. The method of claim 3 wherein applying the Forney erasure decoding algorithm to the k data symbols to generate the r Reed-Solomon redundancy symbols includes:

computing a message syndrome vector having r elements;

constructing a redundancy symbol evaluator polynomial based on the computed message syndrome vector; and

generating each of the r Reed-Solomon redundancy symbols by;

evaluating the redundancy symbol evaluator polynomial at r points within GF(2^m), each of the r points being determined with reference to a respective one of the assigned virtual disk numbers, wherein evaluating the redundancy symbol evaluator polynomial at the r points includes applying an inverse cyclotomic fast Fourier transform; and

multiplying each of the r evaluation results by a respective pre-computed factor, each pre-computed factor having been calculated with respect to a respective assigned virtual disk number and stored in memory, prior to performing the method.

5. The method of claim 4 wherein computing the message syndrome vector includes applying a direct cyclotomic fast Fourier transform.

6. The method of claim 5 wherein storing each of the k data symbols to its respective data disk of the k data disks includes assigning a unique virtual disk number to each of the k data disks, each virtual disk number being drawn from the set of Q integers, wherein assigning the unique virtual disk number to each of the k data disks includes choosing k numbers from the set of Q integers, the k chosen numbers spanning a minimal number of cyclotomic cosets over GF(2^m) exclusive of the cyclotomic cosets used in connection with assigning the virtual disk number to the r redundancy disks, the k chosen numbers being the assigned virtual disk numbers assigned to the k data disks.

7. The method of claim 4 wherein computing the message syndrome vector includes applying an inverse cyclotomic fast Fourier transform.

8. The method of claim 7 wherein storing each of the k data symbols to its respective data disk of the k data disks includes assigning a unique virtual disk number to each of the k data disks, each virtual disk number being drawn from the set of Q integers, wherein assigning the unique virtual disk number to each of the k data disks includes choosing k numbers from the set of Q integers, the k chosen numbers being consecutive integers exclusive of the virtual disk number assigned to the r redundancy disks, the k chosen numbers being the assigned virtual disk numbers assigned to the k data disks.

9. The method of claim 4 wherein:

Q is divisible by r;

choosing the r numbers from the set of Q integers, the r chosen numbers spanning a minimal number of cyclotomic cosets over GF(2^m), includes choosing the numbers iQ/r for each integer i from i=0 to i=r−

1, inclusive;

the redundancy symbol evaluator polynomial has degree r−

1; and

constructing the redundancy symbol evaluator polynomial based on the computed message syndromes of the r redundancy symbols includes assigning the redundancy symbol evaluator polynomial to be a summation of r monomial terms, each of the r monomial terms having a coefficient set to a respective element of the computed message syndrome vector.

10. The method of claim 4 wherein:

m=8; and

each data symbol and each redundancy symbol is 1 byte in size.

11. The method of claim 4 wherein the method further includes:

receiving a set of u update symbols to be stored within the data of the RAID stripe, u<

k, each update value corresponding to a respective data symbol of the k data symbols;

for each update symbol, calculating a difference between that update symbol and the corresponding respective data symbol;

computing an update message syndrome for each of the r redundancy symbols using the calculated difference for each update symbol;

constructing an update redundancy symbol evaluator polynomial based on the computed update message syndromes of the r redundancy symbols;

generating r Reed-Solomon update redundancy symbols by;

evaluating the update redundancy symbol evaluator polynomial at r points within GF(2^m), each of the r points being determined with reference to a respective one of the assigned virtual disk numbers, wherein evaluating the update redundancy symbol evaluator polynomial at the r points includes applying the inverse cyclotomic fast Fourier transform; and

multiplying each of the updated r evaluation results by the respective pre-computed factor;

storing each of the u update symbols to a respective data disk of the k data disks; and

incrementing each of the stored r redundancy symbols by the respective update redundancy symbol on the respective redundancy disk of the r redundancy disks.

12. The method of claim 1 wherein generating the r redundancy symbols by applying the Forney erasure decoding algorithm includes:

assigning a unique virtual disk number to each of the r redundancy disks, each virtual disk number being drawn from a set of Q values, Q>

k+r, Q=2^m, m being an integer greater than 2, the set of Q values including all integers from 0 to 2^m−

1, inclusive, and value −

∞

, wherein assigning the unique virtual disk number to each of the r redundancy disks includes choosing r numbers from the set of Q values, the r chosen numbers spanning a minimal number of cyclotomic cosets modulo 2^m−

1 over a Galois Field of order 2^m [GF(2^m)], the r chosen numbers being the assigned virtual disk numbers; and

applying the Forney erasure decoding algorithm to the k data symbols to generate the r Reed-Solomon redundancy symbols from a virtual Reed-Solomon codeword having Q symbols, the generated r Reed-Solomon redundancy symbols having location codes specified by the virtual disk numbers assigned to the r redundancy disks, the k data symbols and the r redundancy symbols forming a shortened Reed-Solomon code.

13. An apparatus comprising:

a set of k+r disks configured as a RAID group;

a host interface for receiving data storage commands; and

a storage processor, the storage processor being constructed and arranged to encode data received by the host interface within a RAID stripe, the RAID stripe being spread across k data disks and r redundancy disks of the RAID group, r≧

3, the k data disks and the r redundancy disks within the RAID stripe being distinct, such that, upon failure of any r disks of the k+r disks of the RAID group, the data can be fully recovered using the Forney erasure decoding algorithm, wherein the storage processor is configured to encode the data by;

partitioning the data into k data symbols;

storing each of the k data symbols to a respective data disk of the k data disks;

generating r Reed-Solomon redundancy symbols by applying the Forney erasure decoding algorithm to the k data symbols; and

storing each of the r Reed-Solomon redundancy symbols generated by the Forney erasure decoding algorithm to a respective redundancy disk of the r redundancy disks.

14. A computer program product comprising a tangible non-transitory computer-readable storage medium, the tangible non-transitory computer-readable storage medium storing instructions, which, when executed by a computer, cause the computer to encode data within a RAID stripe, the RAID stripe being spread across k data disks and r redundancy disks of a RAID group of a data storage system, r≧

3, the RAID group having k+r disks, the k data disks and the r redundancy disks within the RAID stripe being distinct, such that, upon failure of any r disks of the k+r disks of the RAID group, the data can be fully recovered using the Forney erasure decoding algorithm, wherein the computer, when encoding the data within the RAID stripe, is configured to;

partition the data into k data symbols;

store each of the k data symbols to a respective data disk of the k data disks;

generate r Reed-Solomon redundancy symbols by applying the Forney erasure decoding algorithm to the k data symbols; and

store each of the r Reed-Solomon redundancy symbols generated by the Forney erasure decoding algorithm to a respective redundancy disk of the r redundancy disks.