Construction of MBR (minimum bandwidth regenerating) codes and a method to repair the storage nodes

Patent metadata

Field	Value
Publication number	US-9722637-B2
Application number	US-201313996825-A
Country	US
Kind code	B2
Filing date	Mar 26, 2013
Priority date	Mar 26, 2013
Publication date	Aug 1, 2017
Grant date	Aug 1, 2017

Abstract

This invention gives a coding method of MBR (Minimum Bandwidth Regenerating) codes. The related method includes the following steps: equally divide the original file of size B into k(k+1)/2 blocks, obtaining the first packets; construct a symmetrical k×k system matrix S with these first packets; generate k ID codes, wherein each ID code contains k elements; obtain the coded packet through operations between one column of the system matrix and the ID code; repeat the above steps with (n−k) different columns of the system matrix separately to get the (n−k) coded packets; construct the (n−k)×k check matrix P with the column number g which is the serial number of the ID codes in the coded packet set P g ; store the rows of the system matrix and coded matrix to n nodes, each node stores one row. The present invention also involves a method to repair the failed nodes of the above coding scheme.

First claim

What is claimed is:

1. A coding method of Minimum Bandwidth Regenerating codes and repairing storage nodes in a distributed data storage system comprising the following steps:
A) equally dividing an original file in a distributed data storage system of size B averagely into k(k+1)/2 blocks, obtaining first packets denoted as c i =b i,1 b i,2 . . . b i,L , i=1, 2, . . . , k(k+1)/2;
B) constructing a symmetrical k×k system matrix S by using the first packets chosen sequentially according to serial number, and generating an upper-triangle of a distributed data storage system matrix by filling up the upper-triangle with the chosen first packets line by line successively according to an order of a column where elements of the system matrix are stored;
C) generating k ID codes, each of which contains k elements; adding a given number of zeros to a head or end of the first packet in a column of the system matrix, wherein the given number of zeroes is equal to a first element of a respective ID code, to get k second packets; operating on the k second packets to get a coded packet; repeating the above steps with the columns of the system matrix by using different ID codes to obtain k coded packets; arranging the k coded packets according to the serial number to get a coded packet set P g =p g,1 p g,2 . . . p g,k , where g=1, 2, . . . , n−k, p g,k is the coded packet obtained from the k-th ID code and the g-th column of the system; repeating the above steps with (n−k) different columns of the system matrix, to obtain (n−k) coded packet sets;
D) constructing a (n−k)×k check matrix P, each row of which is the successively arranged coded packet set P g ;
E) storing the first packets contained in each row of the system matrix to a storage node respectively, to get k system nodes; storing each row of the check matrix to a storage node, to get (n−k) check nodes, wherein n is the total amount of storage nodes;
F) confirming invalidation of the storage nodes, and deciding whether each failed node is a system node, if yes, executing step G); otherwise, executing step H);
G) downloading the f-th packet stored in each remained surviving system node i.e. the packet of the system node in the f-th column of the system matrix, to get (k−1) packets of the failed node, wherein f is the row number of the system matrix in which the failed node lies; f=1, 2, . . . , k; choosing the check node corresponding to the column and downloading data from the chosen node, operating on the data downloaded from the check node according to the ID codes; and then obtaining all the data of the failed node through combining the obtained data in the column of system matrix stored in the failed system node; storing the obtained data in a new node to replace the failed system node; and
H) getting the column number of the system matrix corresponding to the failed node, then downloading a packet from each system node to get the above mentioned column; coding the downloaded data with all the ID codes to get data stored in the failed node; storing the obtained data into a new node to replace the failed node.

2. The method of claim 1 , wherein the step C) further comprises the following steps:
C1) obtaining k ID codes;
C2) choosing an ID code and a column of the system matrix, adding the given number of zeros respectively to the heads or ends of the k first packets in the chosen column according to the maximum value of the elements in the chosen ID code and the element values of the ID code corresponding to the row number in which each first packet lies, to get k second packets; and then obtaining a coded packet through operations on the k second packets;
C3) repeating step C2) respectively for the chosen columns of the system matrix successively, by using different ID codes, until (n−k) coded packets are obtained; arranging the obtained coded packets to get a coded packet set; and
C4) choosing k different columns of the system matrix successively, and then repeating step C2) and step C3) by using the ID codes, to get (n−k) coded packet sets.

3. The method of claim 2 , wherein the step C1) further comprises the following steps:
C11) checking whether k is a prime number; if yes, executing step C12); otherwise, executing step C13);
C12) according to
( r 1 a ,r 2 a , . . . ,r k a )=(0, a, 2 a , . . . ,( n− 1) a )mod k, a= 1,2, . . . , k

 substituting a=1, 2, . . . , k into the sequence (0, a, 2a, . . . , (n−1)a) with a modulus of k respectively, obtaining (n−k) ID codes;
C13) finding the minimum prime number p that is larger than k, and according to
( r 1 a ,r 2 a , . . . ,r k a )=( a− 1,2 a− 1, . . . , ka− 1)mod p, a= 1,2, . . . , p− 1,

 substituting a=1, 2, . . . , p−1 respectively into the sequence (a−1, 2a−1, 2a, . . . , ka−1) with a modulus of p, obtaining (n−k) ID codes.

4. The method of claim 3 , wherein the step C2) further comprises:
C21) finding the maximum value of the ID codes, denoting as
r max =max( r 1 a ,r 2 a , . . . ,r n a )

C22) adding a given number of zeros to the head of the y-th first packet in the chosen column of the system matrix, wherein the given number equals to the y-th element value in the current ID code, while adding r max −r y a zeros to the end, to get a second packet, wherein y=1, 2, . . . , k; repeating the above steps successively for the other (k−1) first packets in the column according to a y equal to the packet's row number respectively, to get k second packets; g is the chosen column in the system matrix, and g is among 1, 2, . . . , n−k; and
C23) adding the k second packets together to get a coded packet p g,j which is generated by the current ID code; and p g,j denoting the coded packet obtained through operations between the g-th column in the system matrix and the j-th ID code.

5. The method of claim 4 , wherein the step C4) further comprises:
C41) choosing the next ID code which is adjacent to the ID code in the step C2);
C42) regarding the obtained ID code which step C41) chose as the current ID code, and then repeating step C2) and C3) until all the ID codes are used.

6. The methods of claim 5 , wherein the step B) further comprises:
B1) taking out the obtained first packets according to their serial number, then filling up the upper-triangle of the system matrix S line by line successively, according to the order of the columns which the elements in the system matrix lie in, to generate the upper-triangle

[

c
1

c
2

…

c
k

c

k
+
1

…

c

2
⁢

Assignees

• Univ Peking Shenzhen Graduate School
• Li Hui

Inventors

• Li Hui
• Hou Hanxu
• Zhu Bing

Classifications

• G06F11/1088 Primary

  Reconstruction on already foreseen single or plurality of spare disks · CPC title

• G06F2211/1028

  Distributed, i.e. distributed RAID systems with parity · CPC title

• H03M13/616 Primary

  Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations · CPC title

• G06F11/1076

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• H03M13/1515

  Reed-Solomon codes · CPC title