System and method for efficient horizontal maximum distance separable raid

• US 8,522,125 B1
• Filed: 04/11/2011
• Issued: 08/27/2013
• Est. Priority Date: 04/09/2010
• Status: Expired due to Fees

• Current Assignee: Jolly Seven, Series 70 of Allied Security Trust I (Allied Security Trust)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Feng, Jun, Chen, Yu
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Ahmed, Enam
• Application Number:
  US13/084,205
• Time in Patent Office: 869 Days
• Field of Search: 714/801
• US Class Current: 714/801
• CPC Class Codes: H03M 13/2921 wherein error correction coding involves a diagonal direction
• CPC Class Codes: H03M 13/293 with erasure setting

Abstract

In recent years, researchers have found that some XOR erasure codes lead to higher performance and better throughput in fault-tolerant distributed data storage applications. However, little consideration has been given to the advantages of parallel processing or hardware implementations taking advantage of the emergence of multi-core processors. An efficient horizontal MDS-like (Maximum Distance Separable) RAID-6 scheme, called EEO, is provided which significantly improves the performance of the decoding procedure in parallel implementations with little storage overhead. EEO is the fastest and most efficient double disk failure recovering algorithm in RAID-6, at the cost of only two more parity symbols. In practice, it is very useful for application where high decoding throughput is desired.

Claims

1. A method for decoding a parity-encoded data set, comprising:

receiving a chain of parity-encoded information having a plurality of information symbols and a plurality of parity symbols into at least one memory, each parity symbol being dependent on a plurality of information symbols of an original set of information symbols and each information symbol of the original set of information symbols contributing to a plurality of an original set of parity symbols, according to a parity algorithm, the plurality of information symbols and plurality of parity symbols being received from different containers;

processing the received parity-encoded data set using, with respect to each parity symbol, a plurality of parallel processing threads of an automated processor system, each thread being allocated a distinct portion of a parity-checking processing task to cover a predefined portion of the parity encoding space, less than the entirety, to determine a parity consistency of the received parity-encoded data set; and

generating an indicia of whether there is parity consistency.

2. The method according to claim 1, further comprising processing the received parity-encoded data set to correct at least two errors in the plurality of information symbols.

3. The method according to claim 1, wherein the plurality of parity symbols comprise two independent parity symbols calculated based on at least each respective information symbol.

4. The method according to claim 3, wherein each parity symbol is processed using two concurrent processing threads.

5. The method according to claim 4, wherein the plurality of processing threads recover erased information symbols, through computation of:

{(2mk,i),((2k+1)m,j), . . . },

{(−

2(k+1)m,i),−

2mk,j), . . . },

{(2mk,j),((2k+1)m,i), . . . },and

{(−

2(k+1)m,j),−

2mk,i), . . . },

wherein n is a number of rows of a data matrix, 0≦

k≦

(n−

1), and i and j are columns in which the information symbols are erased, and m=j−

i.

6. The method according to claim 1, wherein the automated processor system comprises a plurality of central processing units, each executing at least one processing thread.

7. The method according to claim 1, wherein the plurality of parity symbols c_i,0, c_i,1, . . . c_i,n are generated using the parity algorithm based on the information symbols d_t, where i=0, 1, . . . , n−

2, using;

8. At least one non-transitory computer readable medium storing therein instructions configured to control an automated data processing system to perform a method according to claim 1.

9. A method for encoding a parity-encoded data set, comprising:

receiving a plurality of information symbols dt;

calculating a plurality of parity symbols ci,0, ci,1, . . . ci,n using an automated processor configured to implement a parity algorithm based on the information symbols dt, where i=0, 1, . . . , n−

2, using;

10. The method according to claim 9, wherein the plurality of parity symbols comprises two parity symbols.

11. The method according to claim 9, further comprising processing the parity-encoded data set to determine a parity consistency.

12. The method according to claim 9, further comprising computing, using a different processing thread of an automated data processing system for each of:

{(2mk,i),((2k+1)m,j), . . . },

{(−

2(k+1)m,i),−

2mk,j), . . . },

{(2mk,j),((2k+1)m,i), . . . },and

{(−

2(k+1)m,j),−

2mk,i), . . . },

to recover erased information symbols, wherein n is a number of rows of a data matrix, 0≦

k≦

(n−

1), and i and j are columns in which the information symbols are erased, and m=j−

i.

13. The method according to claim 12, wherein each thread executes using a respectively different arithmetic logic unit.

14. The method according to claim 9, wherein the plurality of information symbols d_t comprise a table of (n−

1) rows and n columns, wherein n is prime, further comprising recovering from erasures in the i-th and j-th columns where 0≦

i<

j≦

n−

1, by commencing an iterative chain starting from imaginary point (n−

1, i) or (n−

1, j) with slope −

1 or 1 and then with slope 1 and −

1 alternatively, to traverse the sequence pair (n−

1−

k×

(2×

(j−

i)+1), j), (n−

1−

k×

2×

(j−

i), i), where 0≦

k≦

n−

1.

15. The method according to claim 14, wherein four iterative chains starting from (n−

1, i) and (n−

1, j) with slope 1 and slope −

1 respectively and then with slope −

1 and 1 alternatively are employed to recover the erasures of the i-th and j-th columns.

16. The method according to claim 15, wherein each of the four iterative chains executes in parallel in a separate processing thread using a respectively distinct arithmetic logic unit.

17. At least one non-transitory computer readable medium storing therein instructions configured to control an automated data processing system to perform a method according to claim 9.

18. A system configured to decode a parity-encoded data set, comprising:

a memory configured to store a chain of parity-encoded information having a plurality of information symbols and a plurality of parity symbols, each parity

symbol being dependent on a plurality of information symbols of an original set of information symbols and each information symbol of the original set of information symbols contributing to a plurality of an original set of parity symbols, according to a parity algorithm, the plurality of information symbols and plurality of parity symbols being received from different containers;

an automated data processor system configured to process the received parity-encoded data set using, with respect to each parity symbol, a plurality of parallel processing threads, each thread being allocated a distinct portion of a parity-checking processing task to cover a predefined portion of the parity encoding space, less than the entirety, to determine a parity consistency of the received parity-encoded data set; and

an output from the automated data processor system configured to generate an indicia of whether there is parity consistency.

19. The system according to claim 18, wherein the automated processor system is further configured to process the parity-encoded data set to correct at least two errors in the plurality of information symbols.

20. The system according to claim 18, wherein the plurality of parity symbols comprise two independent parity symbols derived based on at least each respective information symbol.

21. The system according to claim 20, wherein the system is configured to:

process each parity symbol using at least two concurrently active central processing units; and

recover erased information symbols, through computation of;

{(2mk,i),((2k+1)m,j), . . . },

{(−

2(k+1)m,i),−

2mk,j), . . . },

{(2mk,j),((2k+1)m,i), . . . },and

{(−

2(k+1)m,j),−

2mk,i), . . . },

wherein n is a number of rows of a data matrix, 0≦

k≦

(n−

1), and i and j are columns in which the information symbols are erased, and m=j−

i.

22. The system according to claim 18, wherein the plurality of parity symbols c_i,0, c_i,1, . . . c_i,n are generated by the automated processor system using the parity algorithm based on the information symbols d_t, where i=0, 1, . . . , n−

2, using;

23. A system configured to encode a parity-encoded data set, comprising:

at least one memory location configured to store a plurality of information symbols d_t;

an automated processor system configured to;

calculate a plurality of parity symbols c_i,0, c_i,1, . . . c_i,n using a parity algorithm based on the information symbols d_t, where i=0, 1, . . . , n−

2, using;

24. The system according to claim 23, wherein the plurality of parity symbols comprises two parity symbols, and the automated processor system is further configured to process the parity-encoded data set to determine a parity consistency.

25. The system according to claim 23, wherein the automated processor system comprises a plurality of arithmetic logic units, configured to compute, using a different concurrent processing thread in at least two different arithmetic processing units for each of:

{(2mk,i),((2k+1)m,j), . . . },

{(−

2(k+1)m,i),−

2mk,j), . . . },

{(2mk,j),((2k+1)m,i), . . . },and

{(−

2(k+1)m,j),−

2mk,i), . . . },

to recover erased information symbols, wherein n is a number of rows of a data matrix, 0≦

k≦

(n−

1), and i and j are columns in which the information symbols are erased, and m=j−

i.

26. The system according to claim 23, wherein the plurality of information symbols d_t comprise a table of (n−

1) rows and n columns, wherein n is prime, further comprising recovering from erasures in the i-th and j-th columns where 0≦

i<

j≦

n−

1, by commencing an iterative chain starting from imaginary point (n−

1, i) or (n−

1, j) with slope −

1 or 1 and then with slope 1 and −

1 alternatively, to traverse the sequence pair (n−

1−

k×

(2×

(j−

i)+1), j), (n−

1−

k×

2×

(j−

i), i), where 0≦

k≦

n−

1.

27. The system according to claim 26, wherein the automated processor system is configured to execute four concurrent iterative chains in parallel, in respectively different arithmetic logic units, starting from (n−

1, i) and (n−

1, j) with slope 1 and slope −

1 respectively and then with slope −

1 and 1 alternatively, to recover the erasures of the i-th and j-th columns.