MDS array codes with optimal building

• US 8,694,866 B2
• Filed: 03/15/2012
• Issued: 04/08/2014
• Est. Priority Date: 03/15/2011
• Status: Active Grant

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: Tamo, Itzhak, Wang, Zhiying, Bruck, Jehoshua
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): ALSHACK, OSMAN M
• Application Number:
  US13/421,723
• Publication Number:
  US 20120278689A1
• Time in Patent Office: 754 Days
• Field of Search: 714/752, 714/786, 714/799, 714/785, 714/784, 714/770, 714/805, 714/769
• US Class Current: 714/770
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: H03M 13/033 Theoretical methods to calculate these checking codes
• CPC Class Codes: H03M 13/13 Linear codes

Abstract

MDS (maximum distance separable) array codes are widely used in storage systems to protect data against erasures. The rebuilding ratio problem is addressed and efficient parity codes are proposed. A controller as disclosed is configured for receiving configuration data at the controller that indicates operating features of the array and determining a parity code for operation of the array according to a permutation, wherein the configuration data specifies the array as comprising nodes defined by A=(a_i,j) with size r^m×k for some integers k,m, and wherein for T={v₀ , . . . , V_k-1} ⊂Z_r^m a subset of vectors of size k, where for each v=(v₁, . . . , v_m)∈T, gcd (v₁, . . . , v_m, r), where gcd is the greatest common divisor, such that for any l, 0≦l≦r−1, and v ∈T, the code values are determined by the permutation f_v^l:[0,r^m−1]→[0,r^m−1]by f_v^l(x)=x+lv.

Claims

1. A computer method of operating a controller of an array of storage nodes, the method comprising:

receiving configuration data at the controller that indicates operating features of the array; and

determining a parity code for operation of the array according to a permutation, wherein the configuration data specifies the array as comprising nodes defined by A=(a_i,j) with size r^m×

k for some integers k,m, and wherein for T={v₀, . . . , v<sub>k−

1</sub>} ⊂

Z_r^m a subset of vectors of size k, where for each v=(v₁, . . . , v_m) ∈

T, gcd(v₁, . . . , v_m,r), where gcd is the greatest common divisor, such that for any l, 0≦

l≦

r−

1, and v ∈

T, the code values are determined by the permutation f_v^l;

[0,r^m−

1]→

[0,r^m−

1] by f_v^l(x)=x+lv.

2. The computer method of claim 1, wherein A specified by the configuration data comprises A=(a_i,j), an array of size 2^m×

k for some integers k, m, and k≦

2^m, and wherein for T ∈

F₂^m is a subset of vectors of size k that does not contain the zero vector, and for v ∈

T the permutation is given by f_v;

[0,2^m−

1]→

[0,2^m−

1] by f_v(x)=x+v, where x is represented in its binary representation.

3. The computer method of claim 2, wherein for the permutations f₀, . . . , f_m and for sets X₀, . . . , X_m constructed by the vectors {e_i}_i+0^m, the set X₀ is modified to be X₀={x ∈

F₂^m;

x·

(1,1, . . . ,

     1)=0}.

4. The computer method of claim 2, further comprising generating an s-duplication code of the code values, such that generating the s-duplication code comprises assigning α

_i,j^(t)=1 for all i, j, t, such that for odd q, and s≦

q−

1 and assigning for all t∈

[0,s−

1]

5. The computer method of claim 3, wherein the code comprises a (k+2, k) MDS (maximum distance separable) array code, and the array has size 2^m×

(k+2), wherein the permutations are defined by f_j, j ∈

[0, k−

1] and for systematic information elements a_i,j, and for row and zigzag parity elements r_i and z_i, respectively, for i ∈

[0,2^m−

1], j ∈

[0, k−

1] and for row coefficients given by α

_i,j=1 for all i,j, and zigzag coefficients given by β

_i,j in some finite field F, the method further comprising;

for a single erasure,

(1) where one parity node is erased, rebuilding the row parity according to

6. A controller of an array of storage nodes, the controller comprising:

a host interface through which the controller communicates with a host computer;

a node interface through which the controller communicates with the array of storage nodes;

a processor that operates a controller application for;

receiving configuration data at the controller that indicates operating features of the array; and

determining a parity code for operation of the array according to a permutation, wherein the configuration data specifies the array as comprising nodes defined by A=(a_i,j) with size r^m×

k for some integers k,m, and wherein for T={v₀, . . . , v<sub>k−

1</sub>}⊂

Z_r^m a subset of vectors of size k, where for each v=(v₁, . . . , v_m)∈

T, gcd(v₁, . . . , v_m, r), where gcd is the greatest common divisor, such that for any l, 0≦

l≦

r−

1, and v ∈

T, the code values are determined by the permutation f_v^l;

[0, r^m−

1]→

[0,r^m−

1]by f_v^l (x)=x+lv.

7. The controller of claim 6, wherein A specified by the configuration data comprises A=(a_i,j), an array of size 2^m×

k for some integers k, m, and k≦

2^m, and wherein for T ⊂

F₂^m is a subset of vectors of size k that does not contain the zero vector, and for v ∈

T the permutation is given by f_v;

[0,2^m−

1]→

[0,2^m−

1]by f_v(x)=x+v, where x is represented in its binary representation.

8. The controller of claim 7, wherein for the permutations f₀, . . . , f_m and for sets X₀, . . . , X_m constructed by the vectors {e_i}_i=0^m, the set X₀ is modified to be X₀={x ∈

F₂^m;

x·

(1,1, . . . ,

     1)=0}.

9. The controller of claim 7, further comprising generating an s-duplication code of the code values, such that generating the s-duplication code comprises assigning α

_i,j^(t)=1 for all i, j, t, such that for odd q, and s≦

q−

1 and assigning for all t ∈

[0,s−

1]

10. The controller of claim 8, wherein the code comprises a (k+2, k) MDS (maximum distance separable) array code, and the array has size 2^m×

(k+2), wherein the permutations are defined by f_j, j ∈

[0,k−

1]and for systematic information elements α

_i,j, and for row and zigzag parity elements r_i and z_i, respectively, for i ∈

[0,2^m−

1], j ∈

[0,k−

1] and for row coefficients given by α

_i,j, =1 for all i, j , and zigzag coefficients given by β

_i,j in some finite field F, the method further comprising;

for a single erasure,

(1) where one parity node is erased, rebuilding the row parity according to