ERASURE CODE CALCULATION METHOD

Abstract

The present invention discloses an erasure code calculation method, including the following steps: S1) splitting original data, and building an original encoding matrix M; S2) acquiring a transverse exclusive OR encoding matrix M1; S3) acquiring a longitudinal exclusive OR encoding matrix M2; S4) acquiring an exclusive OR encoding matrix M3 according to the transverse exclusive OR encoding matrix M1 and the longitudinal exclusive OR encoding matrix M2; S5) transforming a data position of the transverse exclusive OR encoding matrix M1 to acquire a storage matrix M4; S6) judging whether storage nodes at which the last column of data of the storage matrix M4 is stored are damaged; S7) restoring the lost data according to a position 1 of the damaged node; and S8) restoring the lost data according to a position 2 of the damaged node. In the present invention, the operation is rapid, and calculation efficiency is high.

Claims

1. An erasure code calculation method, comprising the following steps: S1) acquiring original data to be stored; splitting the original data; and building an original encoding matrix M; S2) executing a transverse exclusive OR operation on the original encoding matrix M to acquire a transverse exclusive OR encoding matrix M1; S3) executing a longitudinal exclusive OR operation on the original encoding matrix M to acquire a longitudinal exclusive OR encoding matrix M2; S4) acquiring an exclusive OR encoding matrix M3 according to the transverse exclusive OR encoding matrix M1 and the longitudinal exclusive OR encoding matrix M2; S5) transforming a data position of the transverse exclusive OR encoding matrix M1 to acquire a storage matrix M4; and storing each column of data in the storage matrix M4 into storage nodes; S6) judging whether storage nodes at which the last column of data of the storage matrix M4 is stored are damaged; if so, entering a step S7); otherwise, entering a step S8); S7) acquiring a position 1 of the lost node; and restoring the lost data according to the position 1 of the lost node; and S8) acquiring a position 2 of the lost node; and restoring the lost data according to the position 2 of the lost node.

2. The erasure code calculation method according to claim 1, wherein the step S1) of splitting the original data and building the original encoding matrix M comprises steps: S11) splitting the original data into n data blocks, wherein each data block comprises k.sup.2 data; S12) setting splitting periods; and splitting the k.sup.2 data in each data block according to the splitting period, wherein each splitting period comprises k data; and S13) sequentially arranging the data in each splitting period in rows; and forming an original encoding matrix $M=\left[\begin{array}{ccccc}{D}_{11}& D_{12}& \mathrm{.Math.}& D_{1k-1}& D_{1k}\\ D_{21}& D_{22}& \mathrm{.Math.}& D_{2k-1}& D_{2k}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}\\ D_{x1}& D_{x2}& \mathrm{.Math.}& D_{\mathrm{xk}-1}& D_{xk}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}\\ D_{k1}& D_{k2}& \mathrm{.Math.}& D_{\mathrm{kk}-1}& D_{kk}\end{array}\right]$ of k rows and k columns, wherein D.sub.xk-1 represents the (k−1)th data of the xth splitting period.

3. The erasure code calculation method according to claim 2, wherein the step S2) of executing the transverse exclusive OR operation on the original encoding matrix M to acquire the transverse exclusive OR encoding matrix M1 comprises steps: S21) executing the exclusive OR operation on each row of data in the original encoding matrix M to acquire a transverse verification value set Cr={Cr.sub.1, Cr.sub.2, . . . , Cr.sub.x, . . . , Cr.sub.k−1, Cr.sub.k} wherein Cr.sub.x, represents the xth row of transverse verification values of the original encoding matrix M; Cr.sub.x=D.sub.x1xorD.sub.x2xorD.sub.x3 . . . D.sub.xk-1xorD.sub.xk; and xor is an exclusive OR symbol; S22) adding each transverse verification value in the transverse verification value set Cr into columns of the original encoding matrix M to acquire a transverse exclusive OR encoding matrix $M1=\left[\begin{array}{cccccc}{D}_{11}& D_{12}& \mathrm{.Math.}& D_{1k-1}& D_{1k}& C{r}_1\\ D_{21}& D_{22}& \mathrm{.Math.}& D_{2k-1}& D_{2k}& C{r}_2\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ D_{x1}& D_{x2}& \mathrm{.Math.}& D_{\mathrm{xk}-1}& D_{xk}& C{r}_x\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ D_{k1}& D_{k2}& \mathrm{.Math.}& D_{\mathrm{kk}-1}& D_{kk}& C{r}_k\end{array}\right]$ of k rows and k+1 columns.

4. The erasure code calculation method according to claim 3, wherein the step S3) of executing the longitudinal exclusive OR operation on the original encoding matrix M to acquire the longitudinal exclusive OR encoding matrix M2 comprises steps: S31) executing exclusive OR operations on each column of data in the original encoding matrix M to acquire a longitudinal verification value set Cc={Cc.sub.1, Cc.sub.2, . . . , Cc.sub.x, . . . , Cc.sub.k−1, Cc.sub.k}, wherein Cc.sub.x represents the xth column of longitudinal verification values of the original encoding matrix M; Cc.sub.x=D.sub.1xxorD.sub.2xxorD.sub.3x . . . D.sub.k−1xxorD.sub.kx; S32) adding each longitudinal verification value in the longitudinal verification value set Cc into rows of the original encoding matrix M to acquire a longitudinal exclusive OR encoding matrix $M2=\left[\begin{array}{ccccc}{D}_{11}& D_{12}& \mathrm{.Math.}& D_{1k-1}& D_{1k}\\ D_{21}& D_{22}& \mathrm{.Math.}& D_{2k-1}& D_{2k}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}\\ D_{x1}& D_{x2}& \mathrm{.Math.}& D_{\mathrm{xk}-1}& D_{xk}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}\\ D_{k1}& D_{k2}& \mathrm{.Math.}& D_{\mathrm{kk}-1}& D_{kk}\\ C{c}_1& C{c}_2& \mathrm{.Math.}& C{c}_{k-1}& C{c}_k\end{array}\right]$ of k+1 rows and k columns.

5. The erasure code calculation method according to claim 4, wherein the step S4) of acquiring the exclusive OR encoding matrix M3 according to the transverse exclusive OR encoding matrix M1 and the longitudinal exclusive OR encoding matrix M2 comprises steps: S41) executing exclusive OR operations on all the longitudinal verification values in the longitudinal verification value set Cc to obtain a total verification value C=Cc.sub.1xorCc.sub.2xorCc.sub.3 . . . Cc.sub.k−1xorCc.sub.k; or executing exclusive OR operations on all the transverse verification values in the transverse verification value set Cr to obtain a total verification value C=Cr.sub.1xorCr.sub.2xorCr.sub.3 . . . Cr.sub.k−1xorCr.sub.k; and S42) acquiring an exclusive OR encoding matrix $M3=\left[\begin{array}{cccccc}{D}_{11}& D_{12}& \mathrm{.Math.}& D_{1k-1}& D_{1k}& {\mathrm{Cr}}_1\\ D_{21}& D_{22}& \mathrm{.Math.}& D_{2k-1}& D_{2k}& {\mathrm{Cr}}_2\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ D_{x1}& D_{x2}& \mathrm{.Math.}& D_{\mathrm{xk}-1}& D_{xk}& {\mathrm{Cr}}_x\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ D_{k1}& D_{k2}& \mathrm{.Math.}& D_{\mathrm{kk}-1}& D_{kk}& {\mathrm{Cr}}_k\\ C{c}_1& C{c}_2& \mathrm{.Math.}& C{c}_{k-1}& C{c}_k& C\end{array}\right]$ of k+1 rows and k+1 columns.

6. The erasure code calculation method according to claim 5, wherein the step S5) of transforming the data position of the transverse exclusive OR encoding matrix M1 to acquire the storage matrix M4 comprises steps: S51) setting bits of ring shift left for each row of data in the transverse exclusive OR encoding matrix M1; wherein the bit of ring shift left of the xth row is (x−1)*z and z is bit width of single data; and acquiring the bits of ring shift left for each row of data in the transverse exclusive OR encoding matrix M1, S52) performing ring shift left according to the bits of ring shift left for each row of data in the transverse exclusive OR encoding matrix M1 to acquire a dislocation arrangement matrix $M5=\left[\begin{array}{cccccc}{D}_{11}& D_{12}& \mathrm{.Math.}& D_{1k-1}& D_{1k}& C{r}_1\\ D_{22}& D_{23}& \mathrm{.Math.}& D_{2k}& C{r}_2& D_{21}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ D_{\mathrm{xx}}& D_{\mathrm{xx}+1}& \mathrm{.Math.}& D_{\mathrm{xk}-3}& D_{\mathrm{xk}-2}& D_{\mathrm{xx}-1}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ D_{kk}& C{r}_k& \mathrm{.Math.}& D_{\mathrm{kk}-3}& D_{\mathrm{kk}-2}& D_{\mathrm{kk}-1}\end{array}\right]$ of k rows and k+1 columns; and S53) adding each element in the longitudinal verification value set Cc into columns of the dislocation arrangement matrix M5 to acquire a storage matrix $M4=\left[\begin{array}{ccccccc}{D}_{11}& D_{12}& \mathrm{.Math.}& D_{1k-1}& D_{1k}& C{r}_1& {\mathrm{Cc}}_1\\ D_{22}& D_{23}& \mathrm{.Math.}& D_{2k}& C{r}_2& D_{21}& {\mathrm{Cc}}_2\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ D_{\mathrm{xx}}& D_{\mathrm{xx}+1}& \mathrm{.Math.}& D_{\mathrm{xk}-3}& D_{\mathrm{xk}-2}& D_{\mathrm{xx}-1}& {\mathrm{Cc}}_x\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ D_{kk}& C{r}_k& \mathrm{.Math.}& D_{\mathrm{kk}-3}& D_{\mathrm{kk}-2}& D_{\mathrm{kk}-1}& {\mathrm{Cc}}_k\end{array}\right]$ of k rows and k+2 columns.

7. The erasure code calculation method according to claim 6, wherein the step S5) of storing each column of data in the storage matrix M4 into storage nodes comprises steps: S54) grouping the storage matrix M4 in columns, wherein each column is a group; totally k+2 data groups are formed and recorded as {G.sub.1, G.sub.2, . . . , G.sub.k+1, G.sub.k+2}; G.sub.k+1 represents the (k+1)th data group; and $G_{k+1}=\left[\begin{array}{c}{\mathrm{Cr}}_1\\ D_{21}\\ \mathrm{.Math.}\\ D_{\mathrm{xx}-1}\\ \mathrm{.Math.}\\ D_{\mathrm{kk}-1}\end{array}\right];$ S55) acquiring k+2 storage nodes; and recording the k+2 storage nodes as {Node.sub.1, Node.sub.2, . . . , Node.sub.k+, Node.sub.k+2}, wherein Node.sub.k+1 represents the (k+1)th storage node; and S56) respectively storing the k+2 data groups into storage nodes that correspond to subscripts of the data groups; and storing the (k+1)th data group into the (k+1)th storage node.

8. The erasure code calculation method according to claim 7, wherein in the step S7), the position 1 of the lost node is acquired; and the position 1 of the lost node is any one storage node in the first k+1 storage nodes and the (k+2)th storage node; the step of restoring the lost data according to the position 1 of the lost node comprises steps: S71) acquiring data in all undamaged storage nodes; arranging unlost data according to an arrangement manner of the exclusive OR encoding matrix M3; acquiring a decoding matrix M6; and acquiring positions of each row of lost data in the decoding matrix M6; S72) executing transverse exclusive OR operations on unlost data on the ith row of the decoding matrix M6 one by one in rows; acquiring respective transverse exclusive OR operation values C.sub.i of the unlost data on the ith row in rows; filling the values C.sub.i into the positions of the lost data on the ith row, wherein i∈{1, 2, . . . , k}; sequentially restoring all the lost data on the first k rows of the decoding matrix M6; and acquiring a first-k-row restoration matrix M7; S73) executing longitudinal exclusive OR operations on the jth column of the first-k-row restoration matrix M7; filling longitudinal exclusive OR operation values of the jth column into the (k+1)th row and the jth column of the decoding matrix M6, wherein j∈{1, 2, . . . , k, k+1}; and restoring all the lost data on the (k+1)th row of the decoding matrix M6.

9. The erasure code calculation method according to claim 8, wherein in the step S8), the positions 2 of the lost node are acquired; and the positions 2 of the lost node are any two storage nodes in the first k+1 storage nodes; the step of restoring the lost data according to the position 2 of the lost node comprises steps: S81) acquiring data in all undamaged storage nodes; arranging unlost data according to an arrangement manner of the exclusive OR encoding matrix M3; acquiring a decoding matrix M8; and acquiring positions of lost data in the decoding matrix M8; S82) executing transverse exclusive OR operations on the first k data on the (k+1)th row of the decoding matrix M8; acquiring a total verification value C; and filling the total verification value C into the (k+1)th row and the (k+1)th column of the decoding matrix M8; S83) acquiring a column in which only 1 lost data exists in the decoding matrix M8; selecting any column y of columns in which only 1 lost data exists; and acquiring a position P.sub.1 of the lost data in the yth column, wherein the position P.sub.1 of the lost data comprises a row number m.sub.1 and a column number n.sub.1; S84) executing longitudinal exclusive OR operations on the unlost data in the yth column one by one; and filling the longitudinal exclusive OR operation values of the unlost data in the yth column into the position P.sub.1 of the lost data in the yth column; S85) acquiring a position P.sub.2 of the lost data on the m.sub.1th row; executing transverse exclusive OR operations on the unlost data on the m.sub.1th row one by one; and filling transverse exclusive OR operation values of the unlost data on the m.sub.1th row into the position P.sub.2 of the lost data in the m.sub.1th row, wherein the position P.sub.2 of the lost data comprises a row number m.sub.1 and a column number n.sub.2; and S86) repeating the step S83); and restoring all the lost data in the decoding matrix M8 in sequence.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0064] FIG. 1 is a flow chart of an erasure code calculation method in Embodiment 1 of the present invention;

[0065] FIG. 2 is a flow chart of restoration of lost data according to a position 1 of a lost node in Embodiment 1 of the present invention; and

[0066] FIG. 3 is a flow chart of restoration of lost data according to a position 2 of a lost node in Embodiment 1 of the present invention.

DETAILED DESCRIPTION OF THE PRESENT INVENTION

[0067] To make purposes, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below in combination with drawings. It should be understood that, specific embodiments described herein are merely used for explaining the present invention, rather than limiting the present invention.

[0068] Embodiment 1 Assuming the quantity k of original data is equal to 6, then m is equal to 2, n is equal to k+m, and n is equal to 8. Totally 8 computers are connected through a network to form a cluster of 8 nodes; and the nodes are respectively named as Node.sub.1, Node.sub.2, Node.sub.3, Node.sub.4, Node.sub.5, Node.sub.6, Node.sub.7 and Node.sub.8.

[0069] As shown in FIG. 1, an erasure code calculation method includes the following steps:

[0070] S1) Original data to be stored was acquired; the original data was split; and an original encoding matrix M was built, wherein the S1) includes steps:

[0071] S11) the original data was split into n data blocks, wherein each data block included 36 data;

[0072] S12) splitting periods were set; and the 36 data in each data block were split according to the splitting period, wherein each splitting period included 6 data; and

[0073] S13) the data in each splitting period were sequentially arranged in rows; and an original encoding matrix

[00008]$M=\left[\begin{array}{cccccc}{D}_{11}& D_{12}& D_{13}& D_{14}& D_{15}& D_{16}\\ D_{21}& D_{22}& D_{23}& D_{24}& D_{25}& D_{26}\\ D_{31}& D_{32}& D_{33}& D_{34}& D_{35}& D_{36}\\ D_{41}& D_{42}& D_{43}& D_{44}& D_{45}& D_{46}\\ D_{51}& D_{52}& D_{53}& D_{54}& D_{55}& D_{56}\\ D_{61}& D_{62}& D_{63}& D_{64}& D_{\mathrm{kk}}& D_{66}\end{array}\right]$

of 6 rows and 6 columns was formed, wherein D.sub.56 represented the 6th data of the 5th splitting period.

[0074] S2) A transverse exclusive OR operation was executed on the original encoding matrix M; and a transverse exclusive OR encoding matrix M1 was acquired, wherein the S2) includes steps:

[0075] S21) the exclusive OR operation was executed on each row of data in the original encoding matrix M; and a transverse verification value set Cr={Cr.sub.1, Cr.sub.2, Cr.sub.3, Cr.sub.4, Cr.sub.5, Cr.sub.6} was acquired, wherein Cr.sub.4 represented the 4th row of transverse verification values of the original encoding matrix M; Cr.sub.4=D.sub.41xorD.sub.42xorD.sub.43xorD.sub.44xorD.sub.45xorD.sub.46; and xor was an exclusive OR symbol;

[0076] S22) each transverse verification value in the transverse verification value set Cr was added into columns of the original encoding matrix M; and a transverse exclusive OR encoding matrix

[00009]$M1=\left[\begin{array}{ccccccc}{D}_{11}& D_{12}& D_{13}& D_{14}& D_{15}& D_{16}& {\mathrm{Cr}}_1\\ D_{21}& D_{22}& D_{23}& D_{24}& D_{25}& D_{26}& {\mathrm{Cr}}_2\\ D_{31}& D_{32}& D_{33}& D_{34}& D_{35}& D_{36}& {\mathrm{Cr}}_3\\ D_{41}& D_{42}& D_{43}& D_{44}& D_{45}& D_{46}& {\mathrm{Cr}}_4\\ D_{51}& D_{52}& D_{53}& D_{54}& D_{55}& D_{56}& {\mathrm{Cr}}_5\\ D_{61}& D_{62}& D_{63}& D_{64}& D_{\mathrm{kk}}& D_{66}& {\mathrm{Cr}}_6\end{array}\right]$

of 6 rows and 7 columns was acquired.

[0077] S3) A longitudinal exclusive OR operation was executed on the original encoding matrix M; and a longitudinal exclusive OR encoding matrix M2 was acquired, wherein the S3) includes steps:

[0078] S31) exclusive OR operations were executed on each column of data in the original encoding matrix M; and a longitudinal verification value set Cc={Cc.sub.1, Cc.sub.2, Cc.sub.3, Cc.sub.4, Cc.sub.5, Cc.sub.6} was acquired, wherein Cc.sub.4 represented the 4th column of longitudinal verification values of the original encoding matrix M; Cc.sub.4=D.sub.14 xorD.sub.24xorD.sub.34 xorD.sub.44 xorD.sub.54 xorD.sub.64.

[0079] S32) each longitudinal verification value in the longitudinal verification value set Cc was added into rows of the original encoding matrix M; and a longitudinal exclusive OR encoding matrix

[00010]$M2=\left[\begin{array}{cccccc}{D}_{11}& D_{12}& D_{13}& D_{14}& D_{15}& D_{16}\\ D_{21}& D_{22}& D_{23}& D_{24}& D_{25}& D_{26}\\ D_{31}& D_{32}& D_{33}& D_{34}& D_{35}& D_{36}\\ D_{41}& D_{42}& D_{43}& D_{44}& D_{45}& D_{46}\\ D_{51}& D_{52}& D_{53}& D_{54}& D_{55}& D_{56}\\ D_{61}& D_{62}& D_{63}& D_{64}& D_{65}& D_{66}\\ {\mathrm{Cc}}_1& {\mathrm{Cc}}_2& {\mathrm{Cc}}_3& {\mathrm{Cc}}_4& {\mathrm{Cc}}_5& {\mathrm{Cc}}_6\end{array}\right]$

of 7 rows and 6 columns was acquired.

[0080] S4) An exclusive OR encoding matrix M3 was acquired according to the transverse exclusive OR encoding matrix M1 and the longitudinal exclusive OR encoding matrix M2, including steps:

[0081] S41) exclusive OR operations were executed on all the longitudinal verification values in the longitudinal verification value set Cc so as to obtain a total verification value C=Cc.sub.1xorCc.sub.2xorCc.sub.3xorCc.sub.4xorCc.sub.5xorCc.sub.6; or exclusive OR operations were executed on all the transverse verification values in the transverse verification value set Cr so as to obtain a total verification value C=Cr.sub.1xorCr.sub.2xorCr.sub.3 . . . Cr.sub.k−1xorCr.sub.k;

[0082] S42) an exclusive OR encoding matrix

[00011]$M3=\left[\begin{array}{ccccccc}{D}_{11}& D_{12}& D_{13}& D_{14}& D_{15}& D_{16}& {\mathrm{Cr}}_1\\ D_{21}& D_{22}& D_{23}& D_{24}& D_{25}& D_{26}& {\mathrm{Cr}}_2\\ D_{31}& D_{32}& D_{33}& D_{34}& D_{35}& D_{36}& {\mathrm{Cr}}_3\\ D_{41}& D_{42}& D_{43}& D_{44}& D_{45}& D_{46}& {\mathrm{Cr}}_4\\ D_{51}& D_{52}& D_{53}& D_{54}& D_{55}& D_{56}& {\mathrm{Cr}}_5\\ D_{61}& D_{62}& D_{63}& D_{64}& D_{65}& D_{66}& {\mathrm{Cr}}_6\\ {\mathrm{Cc}}_1& {\mathrm{Cc}}_2& {\mathrm{Cc}}_3& {\mathrm{Cc}}_4& {\mathrm{Cc}}_5& {\mathrm{Cc}}_6& C\end{array}\right]$

of 7 rows and 7 columns was acquired.

[0083] S5) A data position of the transverse exclusive OR encoding matrix M1 was transformed to acquire a storage matrix M4; and each column of data was stored in the storage matrix M4 into storage nodes, including steps:

[0084] S51) bits of ring shift left for each row of data in the transverse exclusive OR encoding matrix M1 were set, wherein the bit of ring shift left of the xth row was (x−1)*z and z was bit width of single data; and the bits of ring shift left for each row of data in the transverse exclusive OR encoding matrix M1 were acquired;

[0085] S52) ring shift left was performed according to the bits of ring shift left for each row of data in the transverse exclusive OR encoding matrix M1; and a dislocation arrangement matrix

[00012]$M5=\left[\begin{array}{ccccccc}{D}_{11}& D_{12}& D_{13}& D_{14}& D_{15}& D_{16}& {\mathrm{Cr}}_1\\ D_{22}& D_{23}& D_{24}& D_{25}& D_{26}& {\mathrm{Cr}}_2& D_{21}\\ D_{33}& D_{34}& D_{35}& D_{36}& {\mathrm{Cr}}_3& D_{31}& D_{32}\\ D_{44}& D_{45}& D_{46}& {\mathrm{Cr}}_4& D_{41}& D_{42}& D_{43}\\ D_{55}& D_{56}& {\mathrm{Cr}}_5& D_{51}& D_{52}& D_{53}& D_{54}\\ D_{66}& {\mathrm{Cr}}_6& D_{61}& D_{62}& D_{63}& D_{64}& D_{65}\end{array}\right]$

of 6 rows and 7 columns was acquired; and

[0086] S53) each longitudinal verification value in the longitudinal verification value set Cc was added into columns of the dislocation arrangement matrix M5; and a storage matrix

[00013]$M4=\left[\begin{array}{cccccccc}{D}_{11}& D_{12}& D_{13}& D_{14}& D_{15}& D_{16}& {\mathrm{Cr}}_1& {\mathrm{Cc}}_1\\ D_{22}& D_{23}& D_{24}& D_{25}& D_{26}& {\mathrm{Cr}}_2& D_{21}& {\mathrm{Cc}}_2\\ D_{33}& D_{34}& D_{35}& D_{36}& {\mathrm{Cr}}_3& D_{31}& D_{32}& {\mathrm{Cc}}_3\\ D_{44}& D_{45}& D_{46}& {\mathrm{Cr}}_4& D_{41}& D_{42}& D_{43}& {\mathrm{Cc}}_4\\ D_{55}& D_{56}& {\mathrm{Cr}}_5& D_{51}& D_{52}& D_{53}& D_{54}& {\mathrm{Cc}}_5\\ D_{66}& {\mathrm{Cr}}_6& D_{61}& D_{62}& D_{63}& D_{64}& D_{65}& {\mathrm{Cc}}_6\end{array}\right]$

of 6 rows and 8 columns was acquired;

[0087] S54) the storage matrix M4 was grouped in columns, wherein each column was a group; totally 8 data groups were formed and recorded as {G.sub.1, G.sub.2, G.sub.3, G.sub.4, G.sub.5, G.sub.6, G.sub.7, G.sub.8}; G.sub.8 represented the 8th data group; and

[00014]$G_8=\left[\begin{array}{c}{\mathrm{Cc}}_1\\ {\mathrm{Cc}}_2\\ {\mathrm{Cc}}_3\\ {\mathrm{Cc}}_4\\ {\mathrm{Cc}}_5\\ {\mathrm{Cc}}_6\end{array}\right];$

[0088] S55) 8 storage nodes were acquired; and the 8 storage nodes were recorded {Node.sub.1, Node.sub.2, Node.sub.3, Node.sub.4, Node.sub.5, Node.sub.6, Node.sub.7, Node.sub.8}, wherein Node.sub.8 represents the 8th storage node; and

[0089] S56) the 8 data groups were respectively stored into storage nodes that corresponded to subscripts of the data groups; and the 8th data group was stored into the 8th storage node.

[0090] S6) Whether storage nodes at which the last column of data of the storage matrix M4 was stored were damaged was judged; if so, a step S7) was executed; otherwise, a step S8) was executed.

[0091] S7) The quantity m of the verification codes was equal to 2, i.e., two storage nodes were allowed to be damaged at most; when the damaged storage nodes included Node.sub.8, assuming that the Node.sub.8 and Node.sub.3 were damaged, the lost data were as shown in Table 1.

Table 1 Lost Data Table when the Damaged Storage Nodes Include Node.SUB.8

[0092]

TABLE-US-00001 TABLE 1 D.sub.11 D.sub.12 D.sub.13 D.sub.14 D.sub.15 D.sub.16 Cr.sub.1 Cc.sub.1 D.sub.22 D.sub.23 D.sub.24 D.sub.25 D.sub.26 Cr.sub.2 D.sub.21 Cc.sub.2 D.sub.33 D.sub.34 D.sub.35 D.sub.36 Cr.sub.3 D.sub.31 D.sub.32 Cc.sub.3 D.sub.44 D.sub.45 D.sub.46 Cr.sub.4 D.sub.41 D.sub.42 D.sub.43 Cc.sub.4 D.sub.55 D.sub.56 Cr.sub.5 D.sub.51 D.sub.52 D.sub.53 D.sub.54 Cc.sub.5 D.sub.66 Cr.sub.6 D.sub.61 D.sub.62 D.sub.63 D.sub.64 D.sub.65 Cc.sub.6

[0093] The lost data were restored according to a position 1 of the lost nodes, that is, Node.sub.8 and Node.sub.3. As shown in FIG. 2, the S7) includes steps:

[0094] S71) data in all undamaged storage nodes were acquired; unlost data were arranged according to an arrangement manner of the exclusive OR encoding matrix M3; a decoding matrix M6 was acquired; and positions of each row of lost data in the decoding matrix M6 were acquired, wherein the positions of each row of lost data in the decoding matrix M6 were as shown in Table 2.

Table 2 Table for Each Row of Lost Data in the Decoding Matrix M6

[0095]

TABLE-US-00002 TABLE 2 D.sub.11 D.sub.12 D.sub.13 D.sub.14 D.sub.15 D.sub.16 Cr.sub.1 D.sub.21 D.sub.22 D.sub.23 D.sub.24 D.sub.25 D.sub.26 Cr.sub.2 D.sub.31 D.sub.32 D.sub.33 D.sub.34 D.sub.35 D.sub.36 Cr.sub.3 D.sub.41 D.sub.42 D.sub.43 D.sub.44 D.sub.45 D.sub.46 Cr.sub.4 D.sub.51 D.sub.52 D.sub.53 D.sub.54 D.sub.55 D.sub.56 Cr.sub.5 D.sub.61 D.sub.62 D.sub.63 D.sub.64 D.sub.65 D.sub.66 Cr.sub.6 Cc.sub.1 Cc.sub.2 Cc.sub.3 Cc.sub.4 Cc.sub.5 Cc.sub.6 C

[0096] S72) Transverse exclusive OR operations were executed on unlost data on the ith row of the decoding matrix M6 one by one in rows; respective transverse exclusive OR operation values C.sub.i of the unlost data on the ith row in rows were acquired; the values C.sub.i were filled into the positions of the lost data on the ith row, wherein i∈{1, 2, . . . , 6}; all the lost data on the first 6 rows of the decoding matrix M6 were sequentially restored; and a first-6-row restoration matrix M7 was acquired;

[0097] S73) longitudinal exclusive OR operations were executed on the jth column of the first-6-row restoration matrix M7; longitudinal exclusive OR operation values of the jth column were filled into the 7th row and the jth column of the decoding matrix M6, wherein j∈{1, 2, . . . , 7}; and all the lost data on the 7th row of the decoding matrix M6 were restored.

[0098] It can be seen from Table 2 that, in the first 6 rows of the decoding matrix M6, there was only 1 data lost in each row, and data in the 7th row were totally lost. The exclusive OR operations were executed on unlost data in each row of the first 6 rows of the decoding matrix M6, and then the lost data in each row can be restored. The lost data in each row were respectively D.sub.13, D.sub.24, D.sub.35, D.sub.46, Cr.sub.5 and D.sub.61; and these restored data are filled into corresponding positions of the decoding matrix M6. After the lost data in the first 6 rows of the decoding matrix M6 were filled, there was only 1 data lost in each column of the decoding matrix M6. Then, the exclusive OR operations were executed on the unlost data in each row, and the data in each row can be restored one by one. The lost data in each row were respectively Cc.sub.1, Cc.sub.2, Cc.sub.3, Cc.sub.4, Cc.sub.5, Cc.sub.6 and C; the restored data were filled into the corresponding positions; and finally the lost data were totally completely restored.

[0099] S8) When the damaged storage nodes did not include the Node.sub.8, assuming that positions 2 of the damaged nodes were Node.sub.3 and Node.sub.5, then the lost data were as shown in Table 3.

Table 3 Lost Data Table when the Damaged Storage Nodes do not Include Node.SUB.8

[0100]

TABLE-US-00003 TABLE 3 D.sub.11 D.sub.12 D.sub.13 D.sub.14 D.sub.15 D.sub.16 Cr.sub.1 Cc.sub.1 D.sub.22 D.sub.23 D.sub.24 D.sub.25 D.sub.26 Cr.sub.2 D.sub.21 Cc.sub.2 D.sub.33 D.sub.34 D.sub.35 D.sub.36 Cr.sub.3 D.sub.31 D.sub.32 Cc.sub.3 D.sub.44 D.sub.45 D.sub.46 Cr.sub.4 D.sub.41 D.sub.42 D.sub.43 Cc.sub.4 D.sub.55 D.sub.56 Cr.sub.5 D.sub.51 D.sub.52 D.sub.53 D.sub.54 Cc.sub.5 D.sub.66 Cr.sub.6 D.sub.61 D.sub.62 D.sub.63 D.sub.64 D.sub.65 Cc.sub.6

[0101] The lost data were restored according to the position 2 of the lost nodes, i.e., Node.sub.3 and Node.sub.5. As shown in FIG. 3, the S8) includes steps:

[0102] S81) data in all undamaged storage nodes were acquired; unlost data were arranged according to an arrangement manner of the exclusive OR encoding matrix M3; a decoding matrix M8 was acquired; and positions of lost data in the decoding matrix M8 were acquired, wherein the positions of the lost data in each row of the decoding matrix M8 were as shown in Table 4.

Table 4 Lost Data Table in Each Row of the Decoding Matrix M8

[0103]

TABLE-US-00004 TABLE 4 D.sub.11 D.sub.12 D.sub.13 D.sub.14 D.sub.15 D.sub.16 Cr.sub.1 D.sub.21 D.sub.22 D.sub.23 D.sub.24 D.sub.25 D.sub.26 Cr.sub.2 D.sub.31 D.sub.32 D.sub.33 D.sub.34 D.sub.35 D.sub.36 Cr.sub.3 D.sub.41 D.sub.42 D.sub.43 D.sub.44 D.sub.45 D.sub.46 Cr.sub.4 D.sub.51 D.sub.52 D.sub.53 D.sub.54 D.sub.55 D.sub.56 Cr.sub.5 D.sub.61 D.sub.62 D.sub.63 D.sub.64 D.sub.65 D.sub.66 Cr.sub.6 Cc.sub.1 Cc.sub.2 Cc.sub.3 Cc.sub.4 Cc.sub.5 Cc.sub.6 C

[0104] S82) Transverse exclusive OR operations were executed on the first 6 data on the 7th row of the decoding matrix M8; a total verification value C was acquired; and the total verification value C was filled into the 7th row and the 7th column of the decoding matrix M8.

[0105] S83) A column in which there was only 1 lost data in the decoding matrix M8 was acquired; any column y of columns in which there was only 1 lost data was selected; and a position P.sub.1 of the lost data in the yth column was acquired, wherein the position P.sub.1 of the lost data included a row number m.sub.1 and a column number n.sub.1.

[0106] S84) Longitudinal exclusive OR operations were executed on the unlost data in the yth column one by one; and the longitudinal exclusive OR operation values of the unlost data in the yth column were filled into the position P.sub.1 of the lost data in the yth column.

[0107] S85) A position P.sub.2 of the lost data on the m.sub.1th row was acquired; transverse exclusive OR operations were executed on the unlost data on the m.sub.1th row one by one; and transverse exclusive OR operation values of the unlost data on the m.sub.1th row were filled into the position P.sub.2 of the lost data in the m.sub.1th row one by one, wherein the position P.sub.2 of the lost data includes a row number m.sub.1 and a column number n.sub.2.

[0108] S86) The step S83) was repeated; and all the lost data in the decoding matrix M8 were restored in sequence.

[0109] It can be seen from Table 4 that, data in the 7th row were integral; there were 2 data lost in each row of the first 6 rows; there was 1 data lost in the 2nd column and the 4th column; and there were 2 data lost in other columns. The 2nd column was selected; D.sub.52 was restored through residual unlost data in the column; then the data Cr.sub.5 was restored through the unlost data in the 5th row at which the D.sub.52 was located; by parity of reasoning, a row or column at which only 1 lost data existed was found; a sequence of the restored data may be D.sub.52, Cr.sub.5, Cr.sub.3, D.sub.35, D.sub.15, D.sub.13, D.sub.63, D.sub.61, D.sub.41, D.sub.46, D.sub.26 and D.sub.24; and finally the lost data were totally completely restored.

[0110] Through the above technical solutions of the present invention, beneficial effects of the present invention are as follows:

[0111] In the present invention, all the verification data are acquired by the exclusive OR operation only; when any two of the storage nodes are damaged, the data can be restored from the data in undamaged nodes; the operation is rapid; and the calculation efficiency is high.

[0112] The above are merely preferred embodiments of the present invention. It shall be indicated that, several improvements and modifications may be made by those ordinary skilled in the art without departing from the principles of the present invention. These improvements and modifications shall be regarded as the protection scope of the present invention.