MDS ERASURE CODE CAPABLE OF REPAIRING MULTIPLE NODE FAILURES

• US 20160274972A1
• Filed: 05/25/2016
• Published: 09/22/2016
• Est. Priority Date: 01/20/2015
• Status: Abandoned Application

• Current Assignee: Peking University Shenzhen Graduate School
• Original Assignee: Peking University Shenzhen Graduate School
• Inventors: SHUN, Kenneth W., HUANG, Zhihao, LI, Hui, HOU, Hanxu
• Application Number:
  US15/164,833
• Publication Number:
  US 20160274972A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 2211/109 Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation

Abstract

An MDS erasure code capable of repairing multiple node failures, being a C(k, r, p) code which stores original information data blocks and parity data blocks by constructing a (p−l)*(k+r) matrix, in which, p is a prime larger than both k and r, k is an arbitrary integer between 2 and p, and r is smaller than or equal to 5. Both an addition operation and a subtraction operation of the C(k, r, p) code are substituted by an XOR operation. An original data block is split into k columns of the original information data blocks with each column containing p−l bits. r columns of the parity data blocks that are linearly independent from one another are generated from the k columns of the original information data blocks. After being changed, the original information data blocks and the parity data blocks are linearly independent.

Claims

1. A maximum distance separable (MDS) erasure code capable of repairing multiple node failures, the erasure code being a C(k, r, p) code which stores original information data blocks and parity data blocks by constructing a (p−

l)*(k+r) matrix, in which, p is a prime larger than both k and r, k is an arbitrary integer between 2 and p, and r is smaller than or equal to 5;

wherein

both an addition operation and a subtraction operation of the C(k, r, p) code are substituted by an XOR operation;

an original data block is split into k columns of the original information data blocks with each column containing p−

l bits;

r columns of the parity data blocks that are linearly independent from one another are generated from the k columns of the original information data blocks; and

after being split, the original information data blocks and the parity data blocks are linearly independent.

2. The code of claim 1, comprising a construction process comprising:

A) splitting original data B into k original information data blocks with each data block containing L=p−

l bits;

B) constructing the parity data blocks; and

C) distributing a total n blocks of the original information data blocks and the parity data blocks to n nodes for storage.

3. The code of claim 2, wherein in A), the original information data blocks are represented by SS=(SS₀,SS₁,SS_k−

1), s<sub>p−

1,j</sub>=s_0,j+s_1,j+ . . . s<sub>p−

2,j</sub> is calculated to obtain S=(S₀, S₁, . . . S<sub>k−

1</sub>), in which j=0,1, . . . k−

1.

4. The code of claim 2, wherein in B), the parity data blocks are represented by CC=(CC₀, CC₁, . . . CC_r−

1), C_j=S₀+x^jS₁+x^j=2S₂+ . . . x<sup>j=(k−

1)</sup>S<sub>k−

1</sub>, c<sub>p−

1,j</sub>=c_0,j+c_1,j+ . . . c<sub>p−

2,j</sub>, in which j=0,1, . . . r−

1, multiplication by x<sup>j=(k−

1)</sup> represents cyclically shifting to the left, and + represents the XOR operation.

5. The code of claim 2, wherein in C), each node stores data, and the data stored in the nodes are represented by (SS₀,SS₁, . . . SS_k−

1, CC₀,CC₁, . . . CC<sub>r−

1</sub>).

6. The code of claim 1, further comprising a decoding process comprising:

collecting l parity data blocks and k−

l available original information data blocks when l originial information data blocks S_j fail;

substracting the k−

l available original information data blocks from each of the l parity data blocks to obtain l linear equations; and

calculating an inverse matrix of an encoding matrix corresponding to the l linear equations, and putting known data into the inverse matrix to finish decoding.

7. The code of claim 6, wherein the decoding process is capable of recovering five node failures.