MDS ARRAY CODES WITH OPTIMAL BUILDING

• US 20120278689A1
• Filed: 03/15/2012
• Published: 11/01/2012
• Est. Priority Date: 03/15/2011
• Status: Active Grant

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: Wang, Zhiying, Bruck, Jehoshua, Tamo, Itzhak
• Granted Patent: US 8,694,866 B2
• Time in Patent Office: Days
• US Class Current: 714/805
• 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 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 TF₂^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 a_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 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 a_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 TF₂^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 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