CN110780813B - A Distributed Storage System Based on Subspace Codes on Binary Fields - Google Patents

Abstract

The invention discloses a distributed storage system based on subspace codes on a binary domain, which comprises the following steps of writing m original user data symbols into vectors in the form of x= (x) ₁ ,…，x _m ) ^T T represents the matrix transpose, performing the following encoding operation on node i:wherein B is _i A coding matrix representing node i; step 2: the generated code word y _i1 And y _i2 Stored on node i; step 3: step 1 and step 2 are performed on all m nodes until all nodes perform the encoding operation to generate and store the codeword. All operations of the invention are based on the binary domain F2, the constructed distributed storage system has simplicity and light weight, and the maximum distance attribute of the subspace storage code designed by the invention ensures that decoding can be finished by depending on the data stored on the least nodes, namely, the decoding bandwidth is reduced.

Description

A distributed storage system based on subspace codes over binary fields

Technical Field

The present invention relates to the technical field of computers and communication networks, and in particular to a distributed storage system based on subspace codes on a binary domain.

Background Art

Traditional data centers store customer data in a disk array in a room or a building. The advantage of this storage method is that it is easy to manage, but an obvious disadvantage is that as the business volume increases, the data center load increases sharply, and the bottleneck effect is obvious; another disadvantage of the data center is that the ability to respond to emergencies is fragile. Once disasters such as earthquakes and fires occur, the data center is damaged and user data cannot be restored, resulting in huge losses. With the rapid development of Internet technology, data storage methods have gradually changed from centralized to distributed. Unlike data centers, distributed storage systems store customer data in a number of disk drives or storage nodes that are separated and far apart in space. These disks may be distributed in various corners of a city, or located in various cities, or even in various countries. The biggest feature of distributed storage is that the communication load is distributed to various storage nodes, thereby effectively solving the bottleneck problem of data transmission. Distributed storage has replaced data centers as the mainstream storage technology in the market. Commercial distributed storage products include Dropbox, Microsoft OneDrive, Amazon S3, Baidu Cloud Disk, etc.

For a data storage system, customer data is always the first priority. The most important task and goal of the system is to protect and provide customers with the data they need, without data errors or data loss. To achieve this goal, a basic functional requirement for distributed storage systems is the recoverability of customer original data, that is, the customer's original data must be recoverable through the storage data stored on the distributed disk drives; another functional requirement is the repairability of storage data, that is, when a part of the storage nodes is damaged, resulting in the loss of the data stored on them, it must be possible to repair or reconstruct the lost storage data based on the data on the remaining surviving storage nodes.

The recoverability of customer original data and the repairability of system stored data are two functional requirements that are both different and interrelated. The simplest way to achieve these two functions is to replicate the storage, which is to store multiple copies of the customer original data intact on distributed disk drives. The data stored on the disk is the customer's original data. When some disks are damaged, the data lost on the damaged disk can be obtained by relying on the data copies stored on other valid disks. Therefore, replicated storage ensures the recoverability of customer original data and the repairability of system stored data. However, the storage efficiency of the above storage method that relies solely on replication is too low. Taking Figure 1 as an example, the replication storage in Figure 1(a) copies a binary source data character d ₁ into n copies and stores them on n disks respectively, with a storage efficiency of 1/n; Figure 1(b) uses parity storage, and the customer's original data includes n-1 binary characters d ₁ ,…,d _n-1 . These n-1 characters are used to generate a check character d _n through parity check, and then the n-1 original data characters and the check character are stored on n disks respectively. The storage efficiency of this storage method is (n-1)/n. When one of the n disk drives is damaged and the data stored on it is lost, the lost character can be repaired by relying on the parity check operation of the remaining n-1 characters.

It has been proven in theory and in engineering applications that the storage efficiency of data storage based on coding is much higher than that based on replication. The so-called distributed storage based on coding means that what is stored on the disk is not the original data of the customer, but the codeword data generated by the original data after some coding operation.

In the prior art, in the distributed storage system based on encoding, as shown in FIG2 , firstly, the original data d ₁ ,…,d _k of the customer is sent to the encoder, and the output of the encoder is the codeword data c ₁ ,…, _cn , assuming that each original data or codeword data is composed of α characters on a finite field F _q ; secondly, the codeword data c ₁ ,…, _cn is distributedly stored in n disks. When the user wants to obtain the original data d ₁ ,…,d _k , the codeword data stored on a part of the nodes can be read from the n disks and sent to the decoder, and the original data can be obtained after decoding to ensure the recoverability of the user's original data; if a disk in the system is damaged and the codeword data stored thereon is lost, such as c _j , a part of the codeword data can be requested from some surviving disks to repair and rebuild c _j to ensure the recoverability of the stored data. Furthermore, the recoverability can also be extended to multiple disk nodes, that is, multiple failed disk nodes can be repaired at the same time. In order to decode and restore the user's original data, the decoder needs to read a part of the codeword data stored on the disk from the storage system. The amount of data that needs to be downloaded during the decoding process is called the decoding bandwidth or download bandwidth. In addition, in order to repair the storage data loss caused by the damage of a storage node, it is necessary to read a part of the codeword data from the remaining disks for repair. The amount of data that needs to be downloaded during the repair process is called the repair bandwidth. Decoding bandwidth and repair bandwidth are two performance evaluation index parameters of distributed coding storage systems. Different coding storage methods or systems have different decoding bandwidths and repair bandwidths. An efficient distributed coding storage system should use relatively small decoding bandwidths and repair bandwidths.

A typical example of a distributed coding storage system is the (n,k) erasure code. The original user data is d ₁ ,…,d _k . After being encoded by the erasure code, the generated codeword data c ₁ ,…, _cn is stored in n disks, and each codeword contains α characters. The (n,k) erasure code relies on any k codewords among the _n codewords c ₁ ,…,cn to recover the original data d ₁ ,…,d _k . Therefore, the decoding bandwidth of the (n,k) erasure code is equal to kα characters.

The decoding process and the repair process of the distributed coding storage system are two processes that are both different and related. On the one hand, the decoding process can replace the repair process. Taking the (n, k) erasure code as an example, in order to repair the codeword data loss caused by the failure of one or several nodes in the system, k nodes can be randomly selected from the remaining surviving nodes, and the k codeword data stored on them can be decoded to obtain the original data d ₁ ,…,d _k , and then the original data is applied to re-encode these failed nodes to generate the lost codeword data. This repair method is hereinafter referred to as the "decode first and then encode" repair method. Obviously, the decoding bandwidth and repair bandwidth of this repair process are equal. For the (n, k) erasure code, they are both equal to kα characters. However, for the single node failure problem, the above "decode first and then encode" repair process uses the repair bandwidth of kα characters just to repair the α characters stored on a single failed node, which is very inefficient. In order to improve the repair efficiency and reduce the repair bandwidth, researchers such as Dimakis proposed the concept of "regeneration code" based on network coding technology. The key point is to allow each node to operate on the codeword data stored internally to generate new data for reconstructing the damaged node.

Figure 3 shows a schematic diagram of a distributed storage system based on a regenerating code. The code is based on a finite field _Fq . The original data characters are ( _x1 , _x2 , _y1 , _y2 ). After being encoded by an erasure code, 8 code characters are generated and stored in 4 nodes respectively. Each node stores 2 code characters, as shown in Figure 3. It is not difficult to verify that the original data ( _x1 , _x2 , _y1 , _y2 ) can be restored by solving the linear equation by reading 4 code characters from any 2 nodes in Figure 3, thus ensuring the recoverability of the original data. For the repair problem of single node damage, without loss of generality, assume that node 2 is damaged, data β ₁ =x ₁ +y ₁ and β ₂ =2x ₂ +y ₂ are lost. If the "decode first and then encode" repair method is adopted, it is necessary to select any two nodes 1, 3, and 4, read the four code symbols, decode and parse (x ₁ , x ₂ , y ₁ , y ₂ ), and then re-encode node 2 to restore β ₁ , β _2. Therefore, the corresponding repair bandwidth of this method is 4 code symbols. However, if the network coding method shown in Figure 3 is used, the two symbols stored in nodes 1, 3, and 4 are encoded to generate three new symbols a, b, and c as shown in Figure 3. These three symbols can be used to construct two linearly independent equations through linear algebra operations as follows:

a+b＝β ₁ +β ₂

b+c＝2β ₁ -β ₂

Solving the equations yields β ₁ ,β ₂ . Therefore, the repair bandwidth corresponding to this repair method is equal to 3 symbols, which is smaller than the repair bandwidth of "decoding first and encoding later".

Similar to erasure codes, subspace codes can also be used for distributed storage. Hollmann proposed a theoretical framework for subspace storage codes, where the code parameter set is (m, n, α, k, r, β). Specifically, the subspace code U consists of an m-dimensional vector space over a finite field F _q The code U is composed of n α-dimensional subspaces U ₁ ,U ₂ ,…,U _n , where U is called the message space, subspaces U ₁ ,U ₂ ,…,U _n are called storage spaces, and α is called storage capacity. The subspace code U needs to meet the following decoding and repair requirements:

Decoding requirements: Randomly select k subspaces from U ₁ ,U ₂ ,…,U _n to form a set K. If the linear span of K is equal to the message space U, then K is called a decoding set that meets the decoding requirements. The size k of the smallest decoding set that meets the decoding requirements is called the decoding dimension of the subspace code U, and the corresponding decoding bandwidth is equal to kα.

Repair requirement: For any subspace U _i , a set R _i = {U _i1 ,U _i2 ,…,U _ir } consisting of r subspaces can be found from the remaining n-1 subspaces {U ₁ ,U ₂ ,…,U _n }/U _i , so that each U _ij has a β (β<α)-dimensional subspace The linear span of these r β-dimensional subspaces contains U _i , that is, R _i is called the repair set of subspace U _i , {V _i1 ,V _i2 ,…,V _ir } is called the repair space, and the corresponding repair bandwidth is equal to rβ.

More intuitively, the subspace storage code with parameters (m, n, α, k, r, β) can also be described as follows: the user's original data includes m symbols on the finite field _Fq , and the codeword data obtained after encoding is stored on n nodes. Each node stores α symbols, and the original data can be decoded by relying on the codeword symbols stored on any k nodes. For the single node failure problem, β symbols can be requested from each of the r valid nodes to repair the failed node, as shown in Figure 2.

Hollmann only gave a theoretical framework for subspace storage codes, but did not give an explicit construction method for subspace storage codes that meet the decoding and repair requirements. Therefore, a simple and efficient coding method is urgently needed to solve the above problems.

Summary of the invention

The purpose of the present invention is to provide a distributed storage system based on subspace codes on a binary field to solve the problems existing in the above-mentioned prior art and make the encoding process simple and efficient.

To achieve the above object, the present invention provides the following solution: a distributed storage system based on subspace codes on a binary field, the parameters of the subspace storage code on the binary field _F2 are Where m is equal to the number of symbols of the user's original data, and also equal to the number of storage nodes. α is 2, which means that each node only stores 2 code data symbols. The coded data symbols stored on each node can be decoded to obtain the original data symbols. The encoding process is as follows:

Step 1: Assume that m original user data symbols are message vectors x = (x ₁ , ..., x _m ) ^T , and the message space is Select m subspaces from all 2-dimensional subspaces of the message space U as storage spaces. The encoded codeword data symbols are stored on m nodes. Each node i stores 2 codeword data symbols. The formula of the encoding matrix Bi of node _i is as follows:

Wherein, _Bi is a (2×m)-dimensional matrix; bi _,1 is the row vector of the first row of the encoding matrix Bi of node _i , bi _,2 is the row vector of the second row of the encoding matrix _Bi of node i, m is equal to the number of characters of the user's original data, and is also equal to the number of storage nodes, and m is any positive integer greater than or equal to 3;

When m=3, _b1,1 =(1 0 0), _b1,2 =(0 1 0), we get:

When m=2i or m=2i+1, i≥2, the formula of the row vector _b1,1 of the first row of the encoding matrix _B1 of the first storage node is:

b _1,1 = (1 … 1 0 0 0 … 0), which contains i-1 1s and m-(i-1) 0s;

The formula for the row vector _b1,2 of the second row is:

b _{1, 2} = (0 1 ... 1 0 ... 0 0), which contains i 1s and mi 0s, so:

The two row vectors of the remaining m-1 encoding matrices are the cyclic right shifts of the two row vectors corresponding to B ₁ ;

The following formula is used to encode node i:

Wherein, _yi is a 2D codeword column vector stored on the i-th node; _yi1 and _yi2 are both codeword data symbols based on the finite field _Fq ;

Step 2: Store the generated codeword data symbols y _i1 and y _i2 on node i;

Step 3: Execute steps 1 and 2 on all m nodes until all nodes have performed the encoding operation and generated storage codewords;

The specific method of decoding is as follows:

Assuming that any chosen The serial numbers of the nodes are j ₁ ,…,j _k , the encoding matrices of the k nodes are B _j1 ,…,B _jk , and the codeword vectors stored by the k nodes are y _j1 ,…,y _jk . Each codeword vector is composed of two binary codeword data symbols on two finite fields F _q . Then the following formula is executed:

Since the construction method of the encoding matrix B can ensure that the coefficient matrix B = (B _j1 , ..., B _jk ) ^T has full column rank, it can be ensured that the original data symbol x = (x ₁ , ..., x _m ) ^T can be parsed using this formula.

Preferably, for the single node failure problem, 13 symbols are requested from each of the r valid nodes to repair the failed node; the selection method and indicator parameters of the repair method are as follows: Assuming that there are m original user data symbols, when m≥6, the storage system adopts a repair method of decoding first and then encoding, β＝2, the repair bandwidth is equal to When m=3, r=2, β=1, and the corresponding repair bandwidth is equal to 2; when m=4 or m=5, r=3, β=1, and the corresponding repair bandwidth is equal to 3. Therefore, when 3≤m≤5, the repair bandwidth is smaller than the repair bandwidth of decoding first and then encoding.

The present invention discloses the following technical effects:

1. The distributed storage system constructed by the present invention is simple and lightweight, and all operations are based on the binary field F2. The encoding process performs matrix multiplication on F2, and the decoding process performs Gaussian elimination of linear equations on F2. The mathematical operation is simple and occupies less memory.

2. By limiting the parameter α=2, that is, each node only stores 2 symbols, the complexity of encoding and decoding is further reduced.

3. The parameters of the invention are: Subspace code storage system, since the message space is m-dimensional space In order to meet the decoding requirements, that is, to rely on the linear expansion of any k subspaces to be equal to the message space U, the lower limit of k must be equal to Theoretically, it can be proved that the special arrangement of 0 and 1 in the coding matrix given in Table 1 of the present invention ensures that the decoding can be completed with any The data stored on each node can be decoded, that is, the coding matrix satisfies the maximum distance criterion, that is, the subspaces stored on each storage node have the maximum distance, which ensures that decoding can be completed with the data stored on the least nodes. Therefore, the lower limit of the decoding bandwidth is reached, that is, the minimum decoding bandwidth is achieved.

BRIEF DESCRIPTION OF THE DRAWINGS

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings required for use in the embodiments will be briefly introduced below. Obviously, the drawings described below are only some embodiments of the present invention. For ordinary technicians in this field, other drawings can be obtained based on these drawings without paying creative work.

FIG1 is a schematic diagram showing a comparison between two storage methods: copy storage and coded storage;

FIG2 is a schematic diagram of the principle of a distributed storage system based on coding;

FIG3 is an example of a storage system based on regeneration codes;

FIG4 is a schematic diagram of storage of the present invention;

FIG5 is a schematic diagram of a subspace code storage system based on m=3 on a binary domain obtained by using the present method;

FIG6 is a schematic diagram of a subspace code storage system based on m=4 on a binary domain obtained by using this method;

FIG7 is a schematic diagram of a subspace code storage system based on m=5 on a binary domain obtained by using the present method;

FIG8 is a schematic diagram of a subspace code storage system based on m=6 on a binary field obtained by using this method.

DETAILED DESCRIPTION

The following will be combined with the drawings in the embodiments of the present invention to clearly and completely describe the technical solutions in the embodiments of the present invention. Obviously, the described embodiments are only part of the embodiments of the present invention, not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by ordinary technicians in this field without creative work are within the scope of protection of the present invention.

In order to make the above-mentioned objects, features and advantages of the present invention more obvious and easy to understand, the present invention is further described in detail below with reference to the accompanying drawings and specific embodiments.

4, the present invention provides a distributed storage system based on subspace codes on a binary domain, and the parameters generated by the method are The storage of the codewords of the subspace code on the storage nodes. The parameters of the subspace storage code on the binary field F ₂ are Where m is equal to the number of characters in the user's original data, and is also equal to the number of storage nodes. α is 2, indicating that there are 2 storage symbols. Indicates nodes, r is the number of valid nodes, β is the number of each request symbol in the valid node, the user's original data includes m symbols on the finite field _Fq , and the codeword data obtained after encoding is stored in m nodes, and each node i stores 2 symbols. The codewords stored on each node can be decoded to get the original data.

The encoding process is as follows: The input of the encoder is m binary symbols x = (x ₁ , ..., x _m ) ^T as the user's original data. The system includes a total of m storage nodes, denoted as node 1 to node m, each node corresponds to a (2×m)-dimensional encoding matrix, and the encoding matrix corresponding to node i is denoted as _Bi , The encoding matrix of the subspace code is shown in Table 1.

Table 1

(1) m = 3

(2) m = 4

(3) m = 5

(4) m = 6

(5) m = 7

(6) m = 8

(7) m = 9

By analogy, when m=2i or m=2i+1, (i≥2), the two row vectors of the encoding matrix _B1 should be:

The first row vector b _1,1 = (1 … 1 0 0 0 … 0) contains i-1 1s and m-(i-1) 0s.

The row vector b _1,2 =(0 1 … 1 0 0 … 0) of the second row contains i 1s and mi 0s.

The two row vectors of the remaining m-1 encoding matrices are respectively the cyclic right shifts of the _B1 row vector.

The encoding formula executed by node i is as follows:

B _i ·x=y _i =(y _i1 , y _i2 ) ^T (1)

The codeword generated by encoding node i is 2 binary code symbols _yi = ( _yi1 , _yi2 ) ^T , and these 2 binary code symbols are stored on node i. All m nodes are encoded to generate 2m code symbols in total, which are stored on m nodes respectively as shown in FIG4.

The decoding process of this method is as follows: This system relies on any The binary code symbols stored on each node can be decoded to recover the original data symbol x = (x ₁ , ..., x _m ) ^T . The input of the decoder is arbitrarily selected. The binary code symbols stored on the nodes. Without loss of generality, assume that the selected The serial numbers of the nodes are j ₁ ,…,j _k , the encoding matrices of these k nodes are B _j1 ,…,B _jk , the codeword vectors stored by these k nodes are y _j1 ,…,y _jk , and each codeword vector is composed of 2 binary code symbols, then there is the following relationship:

The necessary and sufficient condition for equation (2) to be solvable is that the coefficient matrix B = (B _j1 , ..., B _jk ) ^T has full column rank. Theoretically, it can be proved that for the coding matrix given in Table 1, this necessary and sufficient condition must be satisfied, so Gaussian elimination can be used to solve equation (2) and resolve the original data symbol x = (x ₁ , ..., x _m ) ^T .

This system can adopt the "decode first and then encode" repair process as follows: Since this system relies on any The 2k binary code symbols stored on each node can be decoded to restore the original data symbol x = (x ₁ , ..., x _m ) ^T , so the system can withstand and repair up to nodes fail at the same time. As long as the system still exists If there are valid nodes, the original data symbol x = (x ₁ , ..., x _m ) ^T can be first decoded and restored, and then the lost codewords can be re-encoded for the failed nodes. The repair bandwidth corresponding to this repair process is equal to However, it can be seen from the following embodiments that for the subspace storage code system using several special parameters (m=3, m=4, m=5) generated by the present invention, when only one node in the system fails, it is not necessary to use the "decoding first and then encoding" repair method, and the repair bandwidth can be less than The code characters will be described in detail in the specific embodiments.

Embodiment 1

Let m = 3, then the message space is a 3D space based on _F2 The user original data vector is x=(x ₁ , x ₂ , x ₃ ) ^T , x _i ∈ {0, 1}. According to the coding matrix given in Table 1, the coding calculation process of the codewords stored on the three storage nodes is as follows. The three storage nodes are shown in FIG5 .

Node 1:

Node 2:

Node 3:

First, let's examine the decoding problem. The four binary characters contained in any two nodes include the original data x ₁ , x ₂ , and x ₃ . Therefore, decoding can be done by any two nodes. The formula for the number of decoding nodes reaching the lower limit k is as follows:

Next, the repair problem is examined. In this embodiment, if any one node fails and the two binary characters stored on it are lost, one binary character can be requested from each of the other two nodes for repair, so the repair bandwidth is equal to two binary characters. This example constructs a subspace storage code with parameters (m, n, α, k, r, β) = (3, 3, 2, 2, 2, 1). By limiting the parameter α = 2, that is, each node only stores 2 symbols, the complexity of encoding and decoding is further reduced.

Embodiment 2

Let m = 4, then the message space is a 4-dimensional space based on _F2 The user original data vector is x=( _x1 , _x2 , _x3 , _x4 ) ^T , x _i∈ {0, 1}. According to the coding matrix given in Table 1, the coding calculation process of the codewords stored on the four storage nodes is as follows. The four storage nodes are shown in FIG6.

Node 1:

Node 2:

Node 3:

Node 4:

First, let's examine the decoding problem of the subspace storage code shown in Figure 6. This storage code occupies 4 storage nodes and stores a total of 8 binary characters. The formula for the lower limit value k of the number of decoding nodes in this example is as follows:

That is to say, the original data x ₁ , x ₂ , x ₃ , x ₄ can be decoded and parsed by using the four binary characters stored on any two storage nodes. To verify this, we select any two storage nodes, assuming that we select node 2 and node 4, and the four binary characters obtained are:

a ₁ =x ₂ , a ₂ =x ₃ +x ₄ , a ₃ =x ₄ , a ₄ =x ₁ +x ₂

Among them, x ₂ and x ₄ are naturally obtained, and there are

a ₁ + a ₄ = x ₂ + (x ₁ + x ₂ ) = x ₁

a ₂ +a ₃ =(x ₃ +x ₄ )+x ₄ =x ₃

Thus, all the original data x ₁ , x ₂ , x ₃ , x ₄ are decoded. If another group of 2 nodes is selected, a similar conclusion can be obtained.

Next, the repair problem of the subspace storage code shown in FIG6 is examined. In this embodiment, if any node fails and the two binary characters stored thereon are lost, one binary character can be requested from each of the remaining three nodes for repair, so the repair bandwidth is equal to three binary characters. Assuming that node 1 is damaged, in order to recover the data _x1 and _x2 + _x3 therein, _x2 , _x3 and _x1 + _x2 can be read from the remaining three nodes respectively, and the lost data _x1 and _x2 + _x3 can be recovered by simple algebraic operations based on _F2 . Similar conclusions can be drawn for the damage of nodes 2, 3 and 4. Therefore, this example constructs a subspace storage code with parameters (m, n, α, k, r, β) = (4, 4, 2, 2, 3, 1).

Embodiment 3

Let m = 5, then the message space is a 5-dimensional space based on F ₂ User original data vector x = (x ₁ , x ₂ , x ₃ , x ₄ , x ₅ ) ^T , x _i ∈ {0, 1}. According to the coding matrix given in Table 1, the coding calculation process of the codewords stored on the five storage nodes is as follows. The five storage nodes are shown in FIG7 .

Node 1:

Node 2:

Node 3:

Node 4:

Node 5:

First, let's examine the decoding problem of the subspace storage code shown in Figure 7. The storage code occupies 5 storage nodes and stores a total of 10 binary characters. The formula for the lower limit k of the number of decoding nodes in this example is as follows:

That is to say, the original data x ₁ , x ₂ , x ₃ , x ₄ , x ₅ can be decoded and parsed by using the 6 binary characters stored on any 3 storage nodes. To verify this, select any 3 storage nodes, assuming that node 1, node 3 and node 4 are selected, and the 6 binary characters obtained are:

a ₁ =x ₁ , a ₂ =x ₂ +x ₃ , a ₃ =x ₃ , a ₄ =x ₄ +x ₅ , a ₅ =x ₄ , a ₆ =x ₅ +x ₁

Among them, x ₁ , x ₃ and x ₄ are naturally obtained, and there are

a ₂ +a ₃ =(x ₂ +x ₃ )+x ₃ =x ₂

a ₄ +a ₅ =(x ₄ +x ₅ )+x ₄ =x ₅

Thus, all the original data x ₁ , x ₂ , x ₃ , x ₄ , x ₅ are decoded. If another group of 3 nodes is selected, a similar conclusion can be obtained.

Next, the repair problem of the subspace storage code shown in FIG7 is examined. In this embodiment, if any node fails and the two binary characters stored thereon are lost, any three nodes can be selected from the remaining four nodes, and one character can be read from each node to repair it. Specifically, if node 1 is damaged, x ₂ , x ₃ and x ₁ + x ₂ can be read from nodes 2, 3 and 5 respectively to repair it; if node 2 is damaged, x ₃ , x ₄ and x ₂ + x ₃ can be read from nodes 3, 4 and 1 respectively to repair it; if node 3 is damaged, x ₄ , x ₅ and x ₃ + x ₄ can be read from nodes 4, 5 and 2 respectively to repair it; if node 4 is damaged, x ₅ , x ₁ and x ₄ + x 5 can be read from nodes 5, 1 and 3 respectively to repair it; if node 5 is damaged, x ₁ , x ₂ and x ₁ + x ₅ can be read from nodes 1, 2 and ₄ respectively to repair it. Therefore, this example constructs a subspace storage code with parameters (m, n, α, k, r, β) = (5, 5, 2, 3, 3, 1).

Embodiment 4

Let m = 6, then the message space is a 6-dimensional space based on F ₂ User original data vector x = (x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ ) ^T , x _i ∈ {0, 1}. According to the coding matrix given in Table 1, the coding calculation process of the codewords stored on the 6 storage nodes is as follows. The 6 storage nodes are shown in FIG8 .

Node 1:

Node 2:

Node 3:

Node 4:

Node 5:

Node 6:

First, consider the decoding problem of the subspace storage code shown in Figure 8. The storage code occupies 6 storage nodes and stores a total of 12 binary characters. The formula for the lower limit value k of the number of decoding nodes in this example is as follows:

That is to say, the original data x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ can be decoded and parsed by using the 6 binary characters stored on any 3 storage nodes. To verify this, select any 3 storage nodes, assuming that node 1, node 3 and node 4 are selected, and the 6 binary characters obtained are:

a ₁ ＝x ₁ +x ₂ , a ₂ ＝x ₂ +x ₃ +x ₄ , a ₃ ＝x ₃ +x ₄ , a ₄ ＝x ₄ +x ₅ +x ₆ ,

a ₅ =x ₄ +x ₅ , a ₆ =x ₁ +x ₅ +x ₆ .

The decoding process is as follows:

a ₂ +a ₃ =x ₂ ;

a ₁ +x ₂ =x ₁ ;

a ₄ +a ₅ =x ₆ ;

a ₆ +x ₁ +x ₆ =x ₅ ;

a ₅ +x ₅ =x ₄ ;

a ₃ +x ₄ =x ₃ .

Thus, all the original data x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ are decoded. If another group of 3 nodes is selected, a similar conclusion will be obtained.

Next, the repair problem of the subspace storage code shown in Figure 8 is examined. For the repair problem of single node failure in this embodiment, only the "decoding first and then encoding" repair method can be used, that is, select any 3 nodes from the 5 surviving nodes, read the 6 codeword data stored therein, decode to obtain the original data _x1 , _x2 , _x3 , _x4 , _x5 , _x6 , and then use the encoding matrix of the failed node to re-encode to generate the lost 2 codeword data. Therefore, this example constructs a subspace storage code with parameters (m, n, α, k, r, β) = (6, 6, 2, 3, 3, 2). In general, when m≥6, the storage system established by this method also needs to use the "decoding first and then encoding" repair method, and the repair bandwidth is equal to

In the description of the present invention, it should be understood that the terms "longitudinal", "lateral", "up", "down", "front", "back", "left", "right", "vertical", "horizontal", "top", "bottom", "inside" and "outside" etc., indicating orientations or positional relationships, are based on the orientations or positional relationships shown in the accompanying drawings, and are only for the convenience of describing the present invention, rather than indicating or implying that the device or element referred to must have a specific orientation, be constructed and operated in a specific orientation, and therefore should not be understood as a limitation on the present invention.

The embodiments described above are only descriptions of the preferred modes of the present invention, and are not intended to limit the scope of the present invention. Without departing from the design spirit of the present invention, various modifications and improvements made to the technical solutions of the present invention by ordinary technicians in this field should all fall within the protection scope determined by the claims of the present invention.

Claims (1)

1. A distributed storage system based on subspace codes on a binary field, characterized in that: the parameters of the subspace storage code on the binary field _F2 are (m, m, α, r, β), where m is equal to the number of symbols of the user's original data, and also equal to the number of storage nodes. α is 2, which means that each node only stores 2 code data symbols. The coded data symbols stored on each node can be decoded to obtain the original data symbols. The encoding process is as follows: Step 1: Assume that m original user data symbols are message vectors x = (x ₁ , ..., x _m ) ^T , and the message space is Select m subspaces from all 2-dimensional subspaces of the message space U as storage spaces. The encoded codeword data symbols are stored on m nodes. Each node i stores 2 codeword data symbols. The formula of the encoding matrix Bi of node _i is as follows: Wherein, _Bi is a (2×m)-dimensional matrix; bi _,1 is the row vector of the first row of the encoding matrix Bi of node _i , bi _,2 is the row vector of the second row of the encoding matrix _Bi of node i, m is equal to the number of characters of the user's original data, and is also equal to the number of storage nodes, and m is any positive integer greater than or equal to 3; When m=3, _b1,1 =(100), _b1,2 =(010), and we get: When m=2i or m=2i+1, i≥2, the formula of the row vector _b1,1 of the first row of the encoding matrix _B1 of the first storage node is: b _1,1 = (1…1 0 0 0…0), which contains i-1 1s and m-(i-1) 0s; The formula for the row vector _b1,2 of the second row is: b _{1, 2} = (0 1…1 0…0 0), which contains i 1s and mi 0s, so: The two row vectors of the remaining m-1 encoding matrices are the cyclic right shifts of the two row vectors corresponding to B ₁ ; The following formula is used to encode node i: Wherein, _yi is a 2D codeword column vector stored on the i-th node; _yi1 and _yi2 are both codeword data symbols based on the finite field _Fq ; Step 2: Store the generated codeword data symbols y _i1 and y _i2 on node i; Step 3: Execute steps 1 and 2 on all m nodes until all nodes have performed encoding operations and generated storage codewords; The specific method of decoding is as follows: Assume that any chosen The serial numbers of the nodes are j ₁ ,…,j _k , the encoding matrices of the k nodes are B _j1 ,…,B _jk , and the codeword vectors stored by the k nodes are y _j1 ,…,y _jk . Each codeword vector is composed of two binary codeword data symbols on two finite fields F _q . Then the following formula is executed: Since the construction method of the encoding matrix B can ensure that the coefficient matrix B = (B _j1 , ..., B _jk ) ^T has full column rank, it can be ensured that the original data symbol x = (x ₁ , ..., x _m ) ^T can be parsed by applying this formula; For the single node failure problem, β symbols are requested from each of the r valid nodes to repair the failed node. The selection method and indicator parameters of the repair method are as follows: Assuming that there are m original user data symbols, when m≥6, the storage system adopts the repair method of decoding first and then encoding, r= β＝2, the repair bandwidth is equal to When m=3, r=2, β=1, and the corresponding repair bandwidth is equal to 2; when m=4 or m=5, r=3, β=1, and the corresponding repair bandwidth is equal to 3. Therefore, when 3≤m≤5, the repair bandwidth is smaller than the repair bandwidth of decoding first and then encoding.