CN104838626B - A kind of coding, data reconstruction and the restorative procedure of general projection selfreparing code - Google Patents

Abstract

The present invention relates to an encoding method of a general projective self-repairing code, comprising the following steps: obtaining a data block to be stored; setting a basic finite field GF(q) whose size is q, and each data block is in the basic finite field The above is represented by a vector with length m; get the first finite field GF( _q ^t+1 ) and the second finite field GF(q ^m ), ; Construct the encoding vector V _i of the storage node i = {w ^i‑1 , w ^i‑1 v, w ^i‑1 v ² ,..., w ^i‑1 v ^t }, and the encoding vectors of the storage node i are respectively A set of bases for the t-expansion; wherein, i is a positive integer representing the number of storage nodes, i=1, 2,..., t; the coded data stored in the storage node of the data block is obtained. The present invention also relates to a method for data reconstruction and data restoration of the system using the above encoding method. Implementing the encoding, data reconstruction and repairing method of the universal projective self-repairing code of the present invention has the following beneficial effects: the repairing data is relatively simple, and the amount of downloaded data is small.

Description

Encoding, data reconstruction and repair method of a general projective self-repair code

technical field

The invention relates to the field of distributed network storage, more specifically, to a method for encoding, data reconstruction and repair of a general projective self-repair code.

Background technique

With the rapid increase of information generation, the storage system for effectively storing massive data has become more and more important. Distributed storage system has become an effective system for storing massive data due to its efficient scalability and high availability. However, in a distributed storage system, the storage nodes that store data are unreliable. In order to be able to provide reliable storage services by unreliable storage nodes, it is necessary to introduce redundancy into the storage system. The easiest way to introduce redundancy is to directly back up the original data. Although direct backup is simple, its storage efficiency and system reliability are not high, and the method of introducing redundancy through coding can improve its storage efficiency. In the current storage system, the encoding method generally adopts MDS (Maximum Distance Separable maximum distance separable) code, MDS code can achieve the best storage space efficiency, a (n, k) MDS error correction code needs to divide an original file into k modules of equal size, and generate n independent coding modules through linear coding, and store different modules by n nodes, and satisfy the MDS property (any k of n coding modules can reconstruct the original file). This encoding technique plays an important role in providing efficient network storage redundancy, especially for storing large files and archival data backup applications.

In a distributed storage system, the data of size B is stored in n storage nodes, and the size of data stored in each storage node is α. The data receiver only needs to connect and download the data of any k storage nodes among the n storage nodes to restore the original data B. This process is called the data reconstruction process. The RS code is a code word that satisfies the characteristics of the MDS code. When a storage node in the storage system fails, in order to maintain the redundancy of the storage system, it is necessary to recover the data stored in the failed node and store the data in a new node. This process is called a repair process. However, in the repair process, the RS code first needs to download the data of k storage nodes and restore the original data, and then encode the storage data of the failed node for the new node. It is obviously a waste of transmission bandwidth to decode the entire original data in order to recover the data of a storage node.

However, if the system node fails or the file is lost, the redundancy of the system will gradually decrease with time, so a mechanism is needed to ensure the redundancy of the system. The EC (Erasure Codes Error Correcting Code) code proposed in the document [R.Rodrigues and B.Liskov, "High Availability in DHTs: Erasure Coding vs. Replication", Workshop on Peer-to-Peer Systems (IPTPS) 2005.], the The code is more efficient in terms of storage overhead, but the communication overhead required to support redundancy recovery is also relatively large. Figure 1 shows that as long as the number of effective nodes d≥k in the system, the original file can be obtained from the existing nodes; Figure 2 shows the process of restoring the stored content of the failed node. It can be seen from Figure 1 and Figure 2 that the whole recovery process is: 1) first download data from k storage nodes in the system and reconstruct the original file; 2) recode the new module from the original file and store it in on the new node. The recovery process shows that the network load required to repair any failed node is at least the content stored by k nodes.

At the same time, in order to reduce the bandwidth used in the restoration process, the paper [A.G.Dimakis, P.G.Godfrey, M.J.Wainwright, K.Ramchandran, "Network coding for distributed storagesystems", IEEE Proc.INFOCOM, Anchorage, Alaska, May 2007.] utilizes network The idea of coding theory proposes regenerating codes (RGC, Regenerating Codes), and RGC codes also satisfy the characteristics of MDS codes. During the repairing process of the regenerative code, the new node needs to connect d storage nodes among the remaining storage nodes and download data of size β from the d storage nodes respectively, so the repair bandwidth of the RGC code is dβ. At the same time, the model of RGC code function repair is given and two kinds of optimal codes of RGC code are proposed: minimum storage regenerating code (MSR, Minimum-storage Regenerating) and minimum repair bandwidth regenerating code (MBR, Minimum-bandwidth Regenerating). The repair bandwidth of RGC code is better than that of RS code, but the repair process of RGC needs to connect d (d>k) storage nodes (d is called repair node). Additionally, repair nodes need to perform randomized linear network coding operations on the data they store. In order to satisfy that all code packets are independent of each other, the operation of the RGC code needs to be in a larger finite field.

Patent PCT/CN2012/071177 proposes an RGC code, in which only a small amount of data is needed to repair a lost coding module, and the entire file does not need to be reconstructed. The RGC code applies the idea of linear network coding, and uses the NC (Network Coding, network coding) attribute (that is, the maximum flow minimum cut) to improve the overhead required to repair a coding module. From the network information theory, it can be proved that the same data volume as the lost module can be used. The network overhead is enough to repair missing modules.

The main idea of the RGC code is to use the MDS attribute. When some storage nodes in the network fail, it is equivalent to the loss of stored data. It is necessary to download information from existing valid nodes to make the lost data repair the lost data module and store it in on the new node. As time goes by, many original nodes may fail, and some regenerated new nodes can re-execute the regeneration process on themselves, and then generate more new nodes. Therefore, the regeneration process needs to ensure two points: 1) The failed nodes are independent of each other, and the regeneration process can be recursively recursive; 2) Any k nodes are enough to restore the original file.

Figure 3 describes the regeneration process when a node fails. In the distributed system, n storage nodes each store α data. When a node fails, the new node regenerates by downloading data from other d≥k surviving nodes. The download amount of each node is β, and each storage node i is represented by a pair of nodes X ⁱ _in and X ⁱ _out , which are connected by an edge whose capacity is the storage capacity of the node (ie α). The regeneration process is described by an information flow graph. Xin collects β pieces of data from any d available nodes _in the system. Through Store α data in X _out , and any receiver can access X _out . The maximum information flow from the source to the sink is determined by the minimum cut set in the graph. When the sink wants to reconstruct the original file, the size of this flow cannot be lower than the size of the original file.

There is a compromise between the storage capacity α of each node and the bandwidth γ needed to regenerate a node, so the minimum bandwidth reproduction code (MBR) and the minimum storage reproduction code (MSR) are introduced. For the minimum storage point, it can be known that each node stores at least M/k bits, so it can be deduced that in the MSR code When d takes the maximum value, that is, a newcomer communicates with all surviving n-1 nodes at the same time, the repair bandwidth γ _MSR is the smallest The MBR code has the minimum repair bandwidth, and it can be deduced that when d=n-1, the minimum repair load can be obtained

For the problem of node failure repair, three repair models are considered: precise repair: the failed module needs to be constructed correctly, and the restored information is the same as the lost one (the core technology is interference queue and NC); functional repair: the newly generated module can contain different For the data of lost nodes, as long as the repaired system supports the MDS code attribute (the core technology is NC); system partial precise repair: it is a hybrid repair model between precise repair and functional repair. In this hybrid model, for the system Nodes (storing unencoded data) require accurate recovery, that is, the restored information is the same as the information stored in the failed node. For non-system nodes (storage encoding modules), precise repair is not required, only functional repair is required so that the restored information can MDS code attributes are full (the core technology is interference queue and NC).

In order to apply the RGC code to the actual distributed system, even if it is not optimal, at least k nodes need to download data to repair the lost module, so even if the amount of data transmission required for the repair process is relatively low, the RGC code needs to be high. The protocol load and system design (NC technology) complexity to achieve. In addition, engineering solutions, such as lazy repair process, are not considered in the RGC code, so the repair load caused by temporary failure cannot be avoided. Finally, the NC-based RGC code encoding and decoding requires relatively large calculation overhead, which is one order higher than the traditional EC code.

Patent PCT/CN2012/083174 proposes a practical projective self-repair code encoding, data reconstruction and repair method. Practical Projective Self-repairing Codes (PPSRC, Practical Projective Self-repairing Codes) also have two typical properties of self-repairing codes: the missing coding module can download less than the entire file's data from other coding modules for repair; the missing coding module Repair from a given number of modules that only depends on how many modules are missing, not which modules are missing. These properties make the load of repairing a missing module relatively low. In addition, because all nodes in the system have the same status and load balance, different missing modules can be repaired independently and concurrently at different locations in the network.

In addition to meeting the above conditions, the codeword has the following characteristics: when a node fails, there are (n-1)/2 pairs of repair nodes to choose from; when (n-1)/2 nodes fail at the same time, We can still use 2 of the remaining (n+1)/2 nodes to repair the failed node.

The encoding and self-repairing process of PPSRC codes only involve XOR operations, unlike general self-repairing codes, whose encoding requires calculation of polynomials is relatively complex, and the computational complexity of PPSRC codes is less than that of PSRC codes (Projective Self-repairing Codes, projective self-repairing codes) code). At the same time, the repair bandwidth and repair nodes of PPSRC codes are better than MSR codes. The redundancy of the PPSRC code is controllable, suitable for general storage systems, and the reconstruction bandwidth of the PPSRC code is optimal. All in all, the PPSRC code effectively reduces the number of data storage nodes, reduces the redundancy of system data storage, and greatly improves the use value of practical self-repair codes.

However, PPSRC codes also have certain shortcomings. First of all, the encoding and decoding process of PPSRC codes is relatively complicated, the division of finite fields and their subfields requires a relatively large amount of computation, and the data reconstruction process is relatively cumbersome; secondly, in PPSRC codes, the coding module cannot be further divided, so repairing Encoding modules must also be indivisible. At the same time, the entire encoding and decoding process of the PPSRC code has high computational complexity, and although the redundancy is controllable, it is still quite large. Usually, the number of PPSRC code storage nodes is very large, which is completely unnecessary for relatively small files. These all increase the difficulty of implementing PPSRC codes in actual distributed storage systems, and the projective self-repairing codes are not universal.

Contents of the invention

The technical problem to be solved by the present invention is to provide a universal projective self-healing code encoding and data reconstruction with simple operation and low repair data cost in view of the above-mentioned defects of the prior art that are complex in operation and expensive in repairing and repair methods.

The technical solution adopted by the present invention to solve its technical problems is: construct a kind of coding method of general projective self-repairing code, it is characterized in that, comprises the steps:

A) Obtain the file that needs to be stored and the amount of data is B, and divide it into k data blocks, and each data block includes m data;

B) setting the size as the basic finite field GF(q) of q, each data block is represented by a vector of length m on the basic finite field; the m-dimensional vector space of the basic finite field is W, All subspaces of the W form a projective geometry PG(m-1,q); the (t+1)-dimensional subspace of the W is a t-space, and the set S of the t-space is a t-expansion; Obtain a first finite field GF(q ^t+1 ) and a second finite field GF(q ^m ) representing said vector space W, Among them, B, k, q, t and m are all positive integers, and t+1 divides m;

C) Obtain the cyclic multiplicative group GF(q ^m ) ^* representing the non-zero elements of the second finite field GF(q ^m ), w is its primitive element; obtain representing the first finite field GF(q ^t+1 ) cyclic multiplicative group GF(q ^t+1 ) ^* of non-zero elements, v is its primitive element; construct the encoding vector V _i ={w ^i-1 ,w ^i-1 v,w ^i-1 for storing node i v ² ,...,w ^i-1 v ^t }, the encoding vectors of the storage node i are respectively a set of bases of the t-expansion; wherein, i is a positive integer representing the number of storage nodes, i=1,2 ,...,t;

D) Multiply the encoding vector corresponding to each storage node i by a data block to obtain the encoded data of the data block stored in the storage node.

Furthermore, the method further includes the following step: the coded data obtained by multiplying the multiple data blocks by the coded data of each storage node are respectively stored in each storage node sequentially.

Furthermore, in the step D), the encoding vector is multiplied by the data block to perform an XOR operation on its corresponding binary number.

The present invention also relates to a data reconstruction method carried out in the storage system of the above-mentioned universal projective self-repair code encoding method, comprising the following steps:

1) select t-1 consecutive storage nodes equal to the data block data volume obtained after storing the file data volume or storing the file in equal parts;

J) Download the encoded data of the lth column in the selected storage node, where l is a positive integer, 1≤l≤(t+1);

K) Obtaining the decoding vectors of the selected storage nodes respectively, and computing with the encoded data downloaded, to obtain decoded data blocks;

L) Processing the respectively obtained decoded data blocks to obtain a storage file.

Furthermore, the decoding vector described in step K) is an inverse matrix of the encoding vectors of each storage node, which is obtained by obtaining the encoding vectors of each storage node and calculating its inverse.

Furthermore, the operation of the encoded data and the decoding matrix in step K) is to perform an XOR operation on the corresponding binary numbers.

Furthermore, in the step L), the data blocks obtained in the step K) are combined to obtain a storage file; the combination includes arranging the data blocks in a set order.

The present invention also relates to a method for data repair performed in the storage system of the above-mentioned universal projective self-repair code encoding method, comprising the following steps:

M) Confirm that a storage node has failed and obtain the code vector of the storage node, set the code vector of the failed storage node as v ₁ , v ₂ ,..., v _α ;

N) sequentially downloading at least one encoding vector from at least two unfailed storage nodes respectively, and calculating and obtaining the encoding vector of the failed storage node;

O) Store the obtained coded vectors representing the coded data of the failed node in the new storage node.

Further, said step N) further comprises:

N1) A non-failure node downloads its coding vector u ₁ , and another non-failure node downloads its coding vector u ₂ , where v ₁ =u ₁ +u ₂ ; the downloaded coding vector is calculated to obtain the invalidation store the vector v1 _of the nodes;

N2) downloading its coded vector u ₃ from yet another unfailed node, where v ₂ =u ₂ +u ₃ ; performing operations on the downloaded coded vector to obtain the coded vector v ₂ of the failed storage node;

N3) Select a new unfailed storage node and repeat step N2) until the code vector v _α of the failed storage node is obtained.

Furthermore, the operation in the step N) is an XOR operation for the corresponding binary number; the storage nodes of the encoded vectors downloaded for operation in the step N) are the same or different.

Implementing the encoding, data reconstruction and repairing method of the general projective self-repairing code of the present invention has the following beneficial effects: since the storage file is divided into data blocks, and the data blocks are encoded separately and the obtained mutually independent encoded data is stored in Multiple storage nodes, therefore, when repairing data, the subset of data blocks stored in each storage node can be downloaded separately to repair the failed storage node, the repair data is relatively simple, and the amount of downloaded data is small.

Description of drawings

FIG. 1 is a schematic diagram of data reconstruction of an EC code in the prior art;

Fig. 2 is a schematic diagram of repairing a failed storage node of an EC code in the prior art;

FIG. 3 is a schematic diagram of data reconstruction of an RGC code in the prior art;

Fig. 4 is an encoding flowchart in an embodiment of the encoding, data reconstruction and repairing method of the general projective self-repairing code of the present invention;

Fig. 5 is a schematic diagram of storage distribution of encoded data in a case in the embodiment;

Fig. 6 is the flowchart of data reconstruction in the described embodiment;

Fig. 7 is a flow chart of data restoration in the described embodiment;

Fig. 8 is a schematic diagram of repairing encoded data in a situation in the embodiment;

Fig. 9 is a comparison schematic diagram of the compromise curve of the repair node and the repair bandwidth of the GPRSC code and the MSR code under a situation in the embodiment;

Fig. 10 is a schematic diagram of comparison curves of repair nodes and repair bandwidths of GPRSC codes and MSR codes in another case in the embodiment.

detailed description

Embodiments of the present invention will be further described below in conjunction with the accompanying drawings.

As shown in Figure 4, in the embodiment of the encoding, data reconstruction and repairing method of the general projective self-repairing code of the present invention, the encoding method includes the following steps:

Step S41 obtains the data block: in this step, obtain the data block that needs to be stored, and this data block may be one of the data blocks obtained by dividing the file that needs to be stored and has a data volume of B into k parts. In this case, each data block includes m data, B=mk; it can also be that a file with a data volume of B has only one data block, in this case, the data volume of the data block is B; in multiple data blocks In this case, for the method in this embodiment, one by one according to the encoding method disclosed in this embodiment, one by one obtains a block of encoded data stored in each storage node, and stores the data in the corresponding storage node . Therefore, the encoded data stored on a node for each data block is independent of each other; at the same time, a data block is stored between the data items of the encoded data (the data includes multiple data items) stored on a storage node, It is also independent and unrelated.

Step S42 sets the basic finite field, and expresses the data block on the basic finite field, and then obtains the first finite field and the second finite field: in this step, define GF(q) to represent a finite field whose size is q, and W is The m-dimensional vector space of GF(q). Projective geometry PG(m-1,q) consists of all subspaces of W. Among them, the points of PG(m-1,q) are 1-dimensional subspaces, and the lines are 2-dimensional subspaces. It can be verified that there are (q ^m -1)/(q-1) points in PG(m-1, q), and there are (q ^m -1)(q ^m-1 -1)/(q ² -1)( q-1) lines. Any two different points are included in the same line, and any two different lines intersect at a point.

The (t+1)-dimensional subspace of W is usually called t-space. The t-expansion of PG(m-1,q) is the set S of t-spaces partitioning the points of PG(m-1,q). A necessary and sufficient condition for the existence of a t-extension of PG(m-1,q) is that t+1 divides m. Extended finite fields can construct t-extended, we use m-dimensional finite field GF(q ^m ) to represent the vector space W. In the extended finite field In , use GF(q ^m ) ^* to denote the non-zero elements of GF(q ^m ). Obviously GF(q ^m ) ^* is a cyclic multiplicative group. Wherein, B, k, q, t and m are all positive integers, and t+1 can divide m evenly.

Step S43 obtains the encoding vector of each storage node: in this step, w is a fixed generator of GF(q ^m ) ^* , and v is a generator of GF(q ^t+1 ) ^* , w and v are respectively Called primitive elements of GF(q ^m ) ^* and GF(q ^t+1 ) ^* . For any element z of GF(q ^m ) ^* , we use zGF(q ^t+1 ) ^* ＝{zx:x∈GF(q ^t+1 ) ^* } to represent the coset of GF(q ^m ) ^* . When i=0, 1, 2, ..., (q ^m –1)/(q ^t+1 –1) –1, the coset w ⁱ GF(q ^t+1 ) forms the PG(m, q) A t-expansion. Considering the practical application, the operation field of the code word is GF(2). A file of size B is divided into several data blocks of equal size, and the codec method of each data block is the same. Therefore, we only give the encoding and decoding method of one data block. Without loss of generality, consider that a data file contains only one data block with a size of B, which can be represented by elements on GF(2) with a length of B. Let t be a positive integer that satisfies (t+1) divisibility of B, N is a positive integer (2 ^B –1)/(2 ^t+1 –1), that is, GF(q ^B ) ^* in GF(q ^t+1 ) ^* the number of cosets. Let V ₁ ={1,v,v ² ,...,v ^t } be a set of basis of the vector space GF(2 ^t+1 ). For i=1,2,...,n, the coding vectors of node i are a set of t-expanded basis respectively, that is, V _i ={w ^i–1 ,w ^i–1 v,w ^i–1 v ² ,… ,w ^i–1 v ^t } is the encoding vector corresponding to node i, i=1,2,...,n. In this embodiment, in some cases, the above steps S42 and S43 may also be set first, and then the data blocks are divided according to the restrictions of steps S42 and S43. That is to say, in some cases, the above steps S42 and 43 may be performed first, and then step S41 is performed. These steps can be adjusted according to specific conditions.

Step S44 obtains the coded data stored in each storage node according to the coded vector obtained: in this step, the coded data stored by node i is the product of the data file and the coded vector w ^i–1 v ^j , j=0,1, 2,...,t. For all storage nodes, use the corresponding encoding vectors and data block operations to obtain the encoded data corresponding to the data block stored in the storage node (corresponding to the storage file when there is only one data block in the storage file). At this time, the product refers to the XOR operation of the binary numbers corresponding to the data file and the encoding vector.

In short, take a file with a data size of B (for simplicity, the file is not divided into blocks, and the fast codec of each file is the same), and use GF(2) for this file (without loss of generality, here q =2) A vector representation whose length is B; take a positive integer t to satisfy (t+1) divisibility of B. v is the primitive element of GF(2 ^t+1 ), construct the encoding vector V _i ＝{wi ^–1 ,wi ^–1 v,wi ^–1 v ² ,…, ^{wi– 1} v ^t }; node The coded data stored in i is the product of the data file and the coded vector w ^i–1 v ^j , j=0,1,2,...,t. The product refers to the XOR operation of the binary numbers corresponding to the data file and the encoding vector.

To be more specific, an example of B=8, n=10 and t=3 is given. The 8-bit data bits are represented by o ₁ , o ₂ , o ₃ , o ₄ , o ₅ , o ₆ , o ₇ , and o ₈ respectively. The 8bits of data are encoded and stored in 10 storage nodes, and each storage node stores t+1=4bits. The specific instructions are as follows:

bounded The generator polynomial of f(x)=x ⁸ +x ⁴ +x ³ +x ² +1, its multiplicative group The generator of is w, then Let v=w ¹⁷ , then the exponent of v and 0 form the subfield GF(2 ⁴ ). The encoding vector of storage node 1 is 1, v, v ² , v ³ , that is, N ₁ ={1, w ¹⁷ , w ³⁴ , w ⁵¹ }. The vector spaces stored by the other seven storage nodes are respectively N ₂ ={w,w ¹⁸ ,w ³⁵ ,w ⁵² }, N ₃ ={w ² ,w ¹⁹ ,w ³⁶ ,w ⁵³ }, N ₄ ={w ³ , w ²⁰ , w ³⁷ , w ⁵⁴ }, N ₅ ={w ⁴ , w ²¹ , w ³⁸ , w ⁵⁵ }, N ₆ ={w ⁵ , w ²² , w ³⁹ , w ⁵⁶ }, N ₇ ={ w ⁶ , w ²³ , w ⁴⁰ , w ⁵⁷ }, N ₈ ={w ⁷ , w ²⁴ , w ⁴¹ , w ⁵⁸ }, N ₉ ={w ⁸ , w ²⁵ , w ⁴² , w ⁵⁹ }, N ₁₀ = {w ⁹ , w ²⁶ , w ⁴³ , w ⁶⁰ }. The first eight elements are specified as 1=00000001, w=00000010, w ² =00000100, w ³ =00001000, w ⁴ =00010000, w ⁵ =00100000, w ⁶ =01000000, w ⁷ =10000000. Then for storage node 1, its encoding vector can be calculated, v=w ¹⁷ =w ⁷ +w ⁴ +w ³ , v ² =w ³⁴ =w ⁶ +w ³ +w ² +w, v ³ =w ⁵¹ = w ³ +w So the encoded data stored by the nodes are o ₁ , o ₄ +o ₅ +o ₈ , o ₂ +o ₃ +o ₄ +o ₇ and o ₂ +o ₄ respectively. Similarly, the data block storage conditions of other nodes can be calculated sequentially. FIG. 5 shows the distribution diagram of encoded data stored by GPSRC (10, 2) in this embodiment.

Through the construction process of the GPSRC code (General Projective Self-Repairing Codes, general projective self-repairing code) in this embodiment, it can be seen that the file B is stored in n nodes, and the amount of data stored in each node is (t+1) and The encoded vectors of data stored by each node are independent of each other. When k>2, neither the PSRC code nor the GPSRC code satisfies the MDS characteristic. It can be seen that the reconstruction process of the GPSRC code is different from the previous RS code, EC code and RGC code.

The consecutive B elements in any column of the coding matrix of GPSRC are independent of each other. It may be assumed that the data collectors downloaded the first coded data of nodes i, i+1,...,i+B respectively, and the coded vectors are respectively w ⁱ , w ⁱ⁺¹ ,...,w ^i+B–1 . If there are B coefficients c ₁ , c ₂ , . . . , c _B that are not all zero, such that c ₁ w ⁱ ₊ c ₂ w ^{i+1 +} . Then divide both sides of the above formula by w ⁱ , then get c ₁ +c ₂ w ^{1 +} …+c _B w B ^{– 1} is equal to 0, which is GF(2 The set of bases of ^B ) are contradictory.

Therefore, the method for reconstructing the data of the GPSRC code is: downloading the encoded data of column l of consecutive B storage nodes, 1≤l≤(t+1). We know that the consecutive B elements in any column of the encoding matrix are independent of each other, so B original data can be decoded, that is, the original data B can be recovered.

Referring to Fig. 6, the data reconstruction process of GPSRC code in the present embodiment is shown in Fig. 6, comprises the following steps:

Step S61 selects storage nodes equal to the data volume of the stored file or the data volume of the data block: in this step, among the t-1 storage nodes, select the data volume equal to the data volume of the stored file or the data volume of the data block obtained after the storage file is equally divided Storage nodes, for example, if the data in the file or data block is 8 bits, select 8 storage nodes. It is worth mentioning that if the storage file has only one data block, and it is B, then the number of storage nodes selected above is B; if the storage file is divided equally, the number of storage nodes above is the data quantity. No matter what happens, in this embodiment, these selected storage nodes must be continuous. In this embodiment, as an example, in the case where the storage file has only one data block and the amount of data in it is B, the number of storage nodes selected is B, where the value of B is the same as the amount of data B included in the storage file of.

Step S62 Download the lth column of encoded data in the selected storage nodes: in this step, download the lth column of encoded data of the B consecutive storage nodes in the above step, where 1≤l≤(t+1).

Step S63 calculates the encoded data downloaded by each storage node and its corresponding decoding vector to obtain its data block: since the data downloaded from each storage node is encoded data, it needs to be decoded and combined to obtain the encoded data stored in the original Store raw data for nodes. In this step, the downloaded coded data is respectively decoded according to the location of the storage node from which the data is obtained. Generally speaking, the encoding of each storage node is different, and when the encoding vectors used for encoding of each storage node are matched according to the positions of the stored data, the encoding matrix of the storage node is formed. The same is true for decoding, and there are also vectors or matrices for decoding. Since the consecutive B elements in any column of the encoding matrix are independent of each other, the original data can be decoded through the downloaded data and the decoding matrix. In practice, the decoded vector corresponding to the downloaded data in the decoded matrix is used. In this step, the decoding matrix is the inverse matrix of the encoding matrix of each storage node, and the decoding vector can be obtained from the decoding matrix according to the location of the encoded data. Therefore, in this step, the decoding vector is obtained by obtaining the encoding vector of each storage node and calculating its inverse. The operation of the encoded data and the decoding matrix is an XOR operation for its corresponding binary number.

Step S64 combines the obtained data blocks to obtain a storage file: integrate the decoded data to restore the original data B.

Referring to Fig. 7, Fig. 7 shows the process of data restoration in this embodiment, including the following steps:

Step S71 determines the failure storage node, and sets its coding data: in this step, it is determined whether a storage node fails, if a storage node fails, the coding matrix or coding matrix of the storage node can be obtained by its location (or node number). vector. In this step, when a storage node is determined to be invalid, its encoded data can be set to v ₁ , v ₂ , ..., v _α ; in the following steps, each data block in the above encoded data can be obtained one by one , store them in a new node after being combined, and the data restoration can be completed.

Step S72 Download at least one coded data from at least two storage nodes to repair the coded data of the failed storage node: In this step, download at least one coded data from at least two non-failed storage nodes respectively, and obtain the above steps respectively The coded data or coded data block of the set failure node. Specifically, in this embodiment, a non-failure node downloads its encoded data block u ₁ , and another non-failure node downloads its coded data block u ₂ , wherein the data downloaded by these two non-failure storage nodes exists The following relationship: v ₁ =u ₁ +u ₂ ; the downloaded encoded data block is operated to obtain the encoded vector v ₁ of the failed storage node. Download its coded vector u ₃ from yet another unfailed node, and match it with the coded data downloaded in the above steps, wherein, there is the following relationship between this yet another storage node and the data downloaded on the storage node that has already passed the coded data: v ₂ =u ₂ +u ₃ ; operate on the encoded data block to obtain the encoded vector v ₂ of the failed storage node. Afterwards, select a new unfailed storage node and repeat the above steps until the encoding vector v _α of the failed storage node is obtained. In this step, the operation between the above-mentioned coded data is an XOR operation for the corresponding binary number; in addition, in this step, the storage nodes of the coded data blocks downloaded for operation are the same or different, that is, in some In this case, one storage node can download two coded data and perform calculations. Of course, in some cases, a storage node can also choose to download multiple data blocks and perform calculations according to the situation.

Step S73 Get the encoded data of the failed storage node and store it in the new node: In this step, combine multiple encoded data blocks obtained in the above steps, and store them in a new storage node to complete data restoration .

In this embodiment, in the PSRC(n, k) code, there are n storage nodes in total, and each storage node stores a coded data amount of α. When a storage node _N1 fails, the data stored in the failed node _N1 can be recovered by selecting any one storage node and its corresponding another storage node and downloading the two storage nodes. In the GPSRC(n,k) code, when a storage node fails, then at most one data is downloaded from (α+1)=(t+2) storage nodes, and the repair bandwidth is (α+1)=(t +2).

An invalid data can be recovered by arbitrarily selecting the data of one node and correspondingly downloading a data of another node. Assuming that the coding vectors of a node’s missing data are v ₁ , v ₂ ,…, v _α , then the coding vector u ₁ of a node and the corresponding coding vector u ₂ of another node can be arbitrarily selected, so that v ₁ =u ₁ +u ₂ . Afterwards, an encoding vector for repairing v ₂ is selected as u ₂ and its corresponding encoding vector u ₃ such that v ₂ =u ₂ +u ₃ . In the same way, it can be obtained that v ₃ =u ₃ +u ₄ , ..., v _α =u _α +u _α+1 . Therefore, to repair the encoded vectors v ₁ , v ₂ , ..., v _α downloads the encoded vectors (u ₁ , u ₂ , ..., u _α+1 ) of at most (α+1) storage nodes, and the repair bandwidth is (α+ 1). At the same time, we call this restoration process the optimal bandwidth restoration procedure.

In the GPSRC(10, 2) code given in Figure 5, when node 1 fails, first download {u ₁ =00010100} of node 2 and the coded vector {u ₂ =00100000+00110101=00010101} of node 6, which can be repaired Vector {v ₁ =u ₁ +u ₂ =00000001}. According to the optimal bandwidth recovery process, downloading {u ₃ =01011010} of node 3, {u ₄ =01010000} of node 4 and {u ₅ =11001001} of node 7 can recover all the invalid data of node 1. The restoration process is {v ₁ =u ₁ +u ₂ , v ₃ =u ₁ +u ₃ , v ₄ =u ₄ +u ₃ , v ₂ =u ₅ +u ₄ +v ₁ }. The repair bandwidth is 5, and the repair node is 5. The repair bandwidth of other nodes is also 5.

As shown in Figure 8, the amount of data stored in node 1 can be obtained by XORing the data blocks of other nodes, specifically, N ₁ =N ₂ (o ₃ +o ₅ )+N ₃ (o ₂ +o ₄ +o ₅ +o ₇ )+N ₄ (o ₅ +o ₇ )+N ₆ (o ₁ +o ₃ +o ₅ )+N ₇ (o ₁ +o ₄ +o ₇ +o ₈ ). Then if node 1 fails, it is necessary to download the data block of node 2 (o ₃ +o ₅ ), the data block of node 3 (o ₂ +o ₄ +o ₅ +o ₇ ), and the data block of node 4 ( o ₅ +o ₇ ), the data block of node 6 (o ₁ +o ₃ +o ₅ ) and the data block of node 7 (o ₁ +o ₄ +o ₇ +o ₈ ) can repair the data stored in node 1. The recovery process of the data stored by other nodes is derived similarly to the representation of the first node.

An additional point here is that the original data blocks stored by each node can be different or different. Specifically, in order to repair the data blocks stored in node 9, it is necessary to select some data blocks from the data blocks stored in the first 8 nodes for XOR operation. However, the original data stored by these nodes cannot directly repair the lost data blocks of node 9. At this time, we need to simply XOR the data blocks stored in the previous nodes to repair them. For example, in order to repair the data block (o ₁ +o ₂ ) of node 9, the data block (o ₁ +o ₂ +o ₃ +o ₄ +o ₈ ), (o ₃ +o ₅ +o ₇ +o ₈ ) simple XOR to obtain the data block (o ₁ +o ₂ +o ₄ +o ₅ +o ₇ ). Simultaneously select the data blocks (o ₄ ) and (o ₅ +o ₇ ) of node 4 to obtain (o ₄ +o ₅ +o ₇ ) through simple XOR. So, (o ₁ +o ₂ )=(o ₁ +o ₂ +o ₄ +o ₅ +o ₇ )+(o ₄ +o ₅ +o ₇ ). In the same way, other data blocks of node 9 can be repaired, and the repair method of node 10 is also the same.

According to the above analysis, we give the general repair process of GPSRC. First, t coded data can be downloaded from two nodes separately, and t coded data of the failed node can be repaired; at the same time, we download one coded data and 2t coded data already downloaded to repair the remaining coded data of the failed node. The repair bandwidth of the above repair process is 2t+1, and the repair nodes are 3. Similarly, (t-1) coded data blocks can be downloaded from two nodes and two coded data blocks can be downloaded from the other two nodes. In this way, the repair bandwidth is 2t, and the number of repair nodes is 4. In the same way, the repair processes of other nodes can be derived, and these repair processes are collectively referred to as general repair processes. In the general repair process, there is a trade-off between repair bandwidth and repair node performance, and the trade-off function can be expressed as

γ+d=2t+4=2(1+B/k), for t+2≥d≥2

Among them, γ is the repair bandwidth, and d is the repair node. So the repair bandwidth can be expressed as

Figure 9 and Figure 10 show the compromise curves of GPSRC and MSR codes when parameters B=16, k=4 and B=32, k=4 respectively. It can be obtained that when the number of repair nodes is given, the repair bandwidth of GPSRC is smaller than that of MSR codes, and when the repair bandwidth is given, the number of repair nodes of GPSRC is also smaller than that of MSR codes. Therefore, it can be said that, in general, GPSRC is superior to MSR codes in repairing bandwidth and repairing node performance, although its cost is the loss of MDS characteristics.

The general projective self-repair code (GPSRC) in this embodiment differs from the RGC code in that the main idea of the RGC code is to use the MDS attribute. When some storage nodes in the network fail, it is necessary to download information from existing valid nodes to make Lost data repairs lost data modules and stores them on new nodes. The regeneration process needs to ensure two points: 1) The failed nodes are independent of each other, and the regeneration process can be recursively recursive; 2) Any k nodes are enough to restore the original file. To reconstruct any module in the RGC code, it needs to communicate with at least k other nodes. When only one module is lost, the minimum amount of communication required is to communicate with all active n-1 nodes, while the GPSRC code is more flexible. The repair node and the repair bandwidth can be compromised, and only need to communicate with at least 2 nodes.

The encoding of HSRC code needs to calculate the polynomial is relatively complex, and the system calculation complexity is relatively high. At the same time, in order to repair a specific failure node, once a node is randomly selected as a secondary node, there is only one node left to choose. The GPSRC code is different, and there are many repair schemes for repairing a failed node. Specifically, for a failed node, there is at least one node pair that can be repaired.

In this embodiment, the GPSRC code can be compromised in terms of repair nodes and repair bandwidth. During the implementation of the specific coding scheme, the benefits of less repair nodes and smaller repair bandwidth can be achieved, which is especially suitable for practical distributed storage systems. At the same time, the GPSRC code provides an effective redundancy repair scheme, specifically including: 1) the lost coding block can be directly downloaded to several subsets of other coding modules for repairing, and the downloaded data volume is less than the data volume of the entire file; 2) the lost A coded block can be repaired by a fixed number of coded modules, and the fixed number is only related to how many modules are lost in the system, but has nothing to do with which modules are lost. These properties make the overhead of repairing a missing module relatively low, while simultaneously repairing different missing modules independently and concurrently.

The GPSRC code not only satisfies the basic characteristics of PSRC, but also is more flexible in selecting the number of storage nodes. Compared with the previous coding scheme, the coding efficiency of GPSRC is higher. A GPSRC(n,k) code can repair a failed module by far less than k nodes, and in many cases a node has more than one repair capability, so the number of nodes required to repair a lost module is greatly reduced, thereby reducing The communication overhead of the system is reduced; the construction process, repair process and reconstruction process of the GPSRC code only involve the XOR operation, so the calculation complexity is very low, the calculation cost is very small, and it is suitable for the actual storage system; the GPSRC code can repair different modules concurrently , which greatly reduces the system repair delay, which makes GPSRC easy to implement and low repair cost.

The above-mentioned embodiments only express several implementation modes of the present invention, and the description thereof is relatively specific and detailed, but should not be construed as limiting the patent scope of the present invention. It should be pointed out that those skilled in the art can make several modifications and improvements without departing from the concept of the present invention, and these all belong to the protection scope of the present invention. Therefore, the protection scope of the patent for the present invention should be based on the appended claims.

Claims (10)

1. a kind of coding method of general projection selfreparing code, it is characterised in that comprise the following steps：

A) obtaining needs file store, that data volume is B, and be divided into k includes m number according to block, each data block According to；

B) the basic finite field gf (q) that size is q is set, each data block is m with length in the basic finite field Vector representation；The m- gts of the basic finite field are W, all subspaces composition projective geometry PG (m- of the W 1,q)；(t+1)-n-dimensional subspace n of the W is t- spaces, and the set S in the t- spaces extends for t-；Obtain the first finite field gf (q^t+1) and represent the second finite field gf (q of the vector space W^m),Wherein, B, k, Q, t and m is positive integer, t+1 aliquots m；

C) obtain and represent the second finite field gf (q^m) nonzero element circulation multiplicative group GF (q^m)^*, w is its primitive element；Obtain Represent the first finite field gf (q^t+1) nonzero element circulation multiplicative group GF (q^t+1)^*, v is its primitive element；Structure storage section Point i coding vector V_i={ w^i-1,w^i-1v,w^i-1v²,...,w^i-1v^t, memory node i coding vector is respectively that the t- expands One group of base of exhibition；Wherein, i be represent memory node number positive integer, i=1,2 ..., t；

D it) will be multiplied respectively with a data block corresponding to each memory node i coding vector, obtain the data block and be stored in this The coded data of memory node.

2. the coding method of general projection selfreparing code according to claim 1, it is characterised in that also include following step Suddenly：The coded data obtained after multiple data blocks are multiplied with the coded data of each memory node respectively is sequentially stored in respectively respectively Memory node.

3. the coding method of general projection selfreparing code according to claim 2, it is characterised in that the step D) in compile Code vector is multiplied with data block carries out XOR for its corresponding binary number.

4. a kind of carried out in the storage system using the coding method of general projection selfreparing code as described in claim 1 Data reconstruction method, it is characterised in that comprise the following steps：

I) select t-1 memory node in it is continuous, equal to the number obtained after storage file data volume or storage file decile According to block data volume memory node；

J the coded data of the l row in the memory node of the selection) is downloaded, l is positive integer, 1≤l≤(t+1)；

K the decoded vector of the memory node of the selection) is obtained respectively, the coded data computing downloaded with it, after obtaining decoding Data block；

L the decoded data block respectively obtained) is handled, obtains storage file.

5. data reconstruction method according to claim 4, it is characterised in that step K) described in decoded vector be each storage The inverse matrix of the coding vector of node, it asks its inverse to obtain after coding vector by obtaining each memory node.

6. data reconstruction method according to claim 5, it is characterised in that step K) described in coded data with decoding square The computing of battle array carries out XOR for its corresponding binary number.

7. data reconstruction method according to claim 6, it is characterised in that in the step L) in the combination step K) In obtained data block, obtain storage file；The combination includes arranging the data block according to setting order.

8. a kind of carried out in the storage system using the coding method of general projection selfreparing code as described in claim 1 Data reparation method, it is characterised in that comprise the following steps：

M) confirm that a memory node has failed and obtained the coding vector of the memory node, if the volume of the memory node of the failure Code vector is v₁, v₂..., v_α；

N at least one coding vector) is downloaded respectively by least two memory nodes not failed successively, and union obtains the mistake Imitate the coding vector of memory node；

O the coding vector of obtained multiple expression failure node coded datas) is stored in new memory node.

9. the method for data reparation according to claim 8, it is characterised in that the step N) further comprise：

N1 its coding vector u) is downloaded by a non-failure node₁, its coding vector u is downloaded by another non-failure node₂, wherein, v₁ =u₁+u₂；Computing is carried out to the coding vector of the download, obtains the coding vector v of failure memory node₁；

N2 its coding vector u) is downloaded by further non-failure node₃, wherein, v₂=u₂+u₃；The coding vector of the download is carried out Computing, obtain the coding vector v of failure memory node₂；

N3) the new memory node repeat step N2 that do not fail of selection), until obtaining the coding vector v of failure memory node_α。

10. the method for data reparation according to claim 9, it is characterised in that the step N) in computing for its is right The binary number answered carries out XOR；The step N) in download the coding vector for carrying out computing memory node it is identical or not It is identical.