CN103744750A - Method and device for recovering data - Google Patents

Abstract

An embodiment of the invention discloses a method and a device for recovering data. The method and the device in the embodiment of the invention have the advantages that second parity blocks are computed by means of exclusive-or operation on all data sub-blocks, slope lines which conform to preset slopes pass the data sub-blocks, redundant data can be set for an optional amount of data blocks, lost data can be recovered only by means of exclusive-or operation on corresponding sub-blocks in first parity blocks and the second parity blocks when the data are lost and need to be recovered by the aid of the redundant data, and accordingly the data recovery efficiency can be improved.

Description

A kind of data reconstruction method and device

Technical field

The present invention relates to field of computer technology, particularly relate to a kind of data reconstruction method and device.

Background technology

At present, by RAID(Redundant Array of Independent Disks, independent magnetic patch redundant array) technology carries out redundancy processing to storage data, and carries out data recovery by redundant data.In prior art, apply more RAID method and mainly contain: RDP(Row-Diagonal Parity, the verification of row diagonal line) and the even odd of EVENODD().

Figure 1 shows that the principle schematic that realizes of RDP.As shown in Figure 1, there are 4 blocks of data piece D0, D1, D2, D3 and 2 block check piece P and Q.Every blocks of data piece is divided into four sub-blocks, and the sub-block that D0 is divided into comprises: D00, D01, D02 and D03; The sub-block that D1 is divided into comprises: D10, D11, D12 and D13; The sub-block that D2 is divided into comprises: D20, D21, D22 and D23; The sub-block that D3 is divided into comprises: D30, D31, D32 and D33.D0-D3 sub-block is separately clapped into row in order, the sub-block array shown in composition diagram 1.Visible, the every a line in array can form a band (stripe), always has four band stripe0, stripe1, stripe2 and stripe3.Check block P comprises four sub-block: P0, P1, P2 and P3, and P0, P1, P2 and P3 are obtained through XOR by the sub-block in place band separately respectively.Check block Q comprises four sub-block: Q0, Q1, Q2 and Q3, wherein, Q0 is obtained by D00, D11, D22 and D33 XOR, and Q1 is obtained by D10, D21, D32 and P3 XOR, Q2 is obtained by D20, D31, P2 and D03 XOR, and Q3 is obtained by D30, P1, D02 and D13 XOR.When having dropout of data block, can utilize check block and remaining data block that the data of loss are recovered.

In RDP technology, tentation data piece number is M, and this technical requirement (M+1) must be prime number, that is: application RDP carries out in the process of data recovery, and the number of data block will be subject to certain restrictions; In addition, when data block number is M, require each data block must be divided into M piece sub-block, therefore, this technology application scenarios is very limited.In addition, in this technology, counting check block P needs XOR M* (M-1) inferior, and calculation check piece Q needs XOR M* (M-1) inferior, and it is inferior that calculation check piece needsXOR 2*M* (M-1) altogether.Visible, because calculated amount is large, the inefficiency that data are recovered.

Figure 2 shows that the principle schematic that realizes of EVENODD.As shown in Figure 2, there are five blocks of data piece D0, D1, D2, D3 and D4, and the algorithm by EVENODD two the check block P and the Q that calculate.Each data block is divided into four sub-blocks, and the sub-block that D0 is divided into comprises: D00, D01, D02 and D03; The sub-block that D1 is divided into comprises: D10, D11, D12 and D13; The sub-block that D2 is divided into comprises: D20, D21, D22 and D23; The sub-block that D3 is divided into comprises: D30, D31, D32 and D33; The sub-block that D4 is divided into comprises: D40, D41, D42 and D43.Sub-block array shown in Fig. 2 comprises four band: stripe0, stripe1, stripe2 and stripe3.Check block P comprises four sub-block: P0, P1, P2 and P3, and P0, P1, P2 and P3 are obtained through XOR by the sub-block in place band separately respectively.Different from RDP technology, EVENODD algorithm, when calculation check piece Q, need to carry out XOR corresponding data block and data block S, and herein, S is obtained through XOR by D40, D31, D22 and D13.In check block Q, Q0 is obtained by S, D41, D32, D23 and D00 XOR, and Q1 is obtained by S, D42, D33, D10 and D01 XOR, and Q2 is obtained by S, D43, D20, D11 and D02 XOR, and Q3 is obtained by S, D30, D21, D12 and D03 XOR.

In EVENODD technology, tentation data piece number is M, and it must be prime number that algorithm requires data block total number M, and therefore, this technology application scenarios is very limited.In addition, the required XOR of check block P is that (N-1) * (N-1) is inferior, calculating Q needs XOR (N-1) * (N-1) inferior, calculating S needs XOR (N-2) inferior, and, owing to calculating Q, need to use data block S, computational complexity is higher, will greatly affect the efficiency that data are recovered.

Visible, when existing application RAID technology is carried out data recovery, the number of data block is had to strict restriction, apply limited.

Summary of the invention

A kind of data reconstruction method and device are provided in the embodiment of the present invention, have made it possible to the data block of arbitrary number that redundant data is set, improved data and recover efficiency.

In order to solve the problems of the technologies described above, the embodiment of the invention discloses following technical scheme:

First aspect, provides a kind of data reconstruction method, comprising:

Obtain N the data block being stored on one or more memory devices, each data block is divided into M sub-block, all sub-blocks after decile are formed to the matrix distribution of N*M, wherein, N and M are the integer that is greater than 1, and N represents the line number of matrix, and M represents matrix column number;

Determine the set of row checking data, the set of described row checking data comprises M row checking data, and each row checking data is undertaken obtaining after XOR by all sub-blocks in each row;

Determine at least one oblique checking data set, each oblique checking data set comprises a plurality of oblique checking datas, and each oblique checking data value is for to carry out obtaining after XOR to all sub-blocks in the described matrix of the straight-line pass of the slope with preset:

When described preset slope is negative slope, during the N of usining is capable, the sub-block of each row is as a data block of straight line process, the all sub-blocks that absolute value are less than or equal in the described matrix of 1 one or more negative slope straight line process carry out XOR, obtain the value of each oblique checking data, wherein, it is 0 that the part that exceeds M row in N is capable is supplemented;

When described preset slope is positive slope, in the M of usining row, the data block of every a line is as a data block of straight line process, the all data blocks that are more than or equal in the described matrix of 1 one or more positive slope straight line process are carried out to XOR, obtain the value of each oblique checking data, wherein, it is 0 that the part that exceeds M row in N is capable is supplemented;

Wherein, the straight line of described preset slope comprises that one or more slopes are the straight line of 1/n, and n is not equal to 0 integer; When preset slope is one, slope is 1 or-1; When preset slope is while being a plurality of, first slope is that-1, second slope is not equal to first slope but absolute value equals the absolute value of first slope; The absolute value of the 3rd slope is less than the absolute value of second slope, and the 4th slope is not equal to the 3rd slope but equals the absolute value of the 3rd slope, the like;

When having described dropout of data block, utilize the set of described row checking data and described oblique checking data set that the sub-block in the data block of loss is recovered.

In conjunction with above-mentioned first aspect, in the possible implementation of the first, when preset slope is negative slope, during the N of usining is capable, the sub-block of each row is as a data block of straight line process, absolute value is less than or equal to all sub-blocks in the described matrix of 1 one or more negative slope straight line process, comprises following data block:

First sub-block be N capable in k column data piece, k is greater than 0 integer, k comprises M row is mended to the columns after 0 expansion;

Second sub-block is the capable k-|n| row of N-1;

The 3rd sub-block is the capable k-2|n| row of N-2;

The like, last piece sub-block is last by after above-mentioned rule calculating, also the sub-block in matrix.

In conjunction with one side face, in the possible implementation of the second, when preset slope is positive slope, in the M of usining row, the sub-block of every a line is as a data block of straight line process, be more than or equal to all sub-blocks in the described matrix of 1 one or more positive slope straight line process, comprise following data block:

First sub-block is the capable data block of m in M row, and m is greater than 0 integer, and m comprises the capable line number of mending after 0 expansion to N;

Second sub-block is the capable M+|n| row of m-1;

The 3rd sub-block is the capable M+2|n| row of m-2;

The like, last piece sub-block is last by after above-mentioned rule calculating, also the sub-block in matrix.

In conjunction with above-mentioned first aspect, to the possible implementation of the second, in the third possible implementation, described when having described dropout of data block with first, utilize the set of described row checking data and described oblique checking data set that the sub-block in the data block of loss is recovered, comprising:

When having L described dropout of data block, by the set of row checking data and (L-1) oblique checking data set corresponding to individual described preset slope, the sub-block in the L of a loss data block is recovered, L is more than or equal to 1 and be less than or equal to the positive integer of N.

In conjunction with one side face, the implementation possible with the third, in the 4th kind of possible implementation, described when having L described dropout of data block, use the set of row checking data and (L-1) oblique checking data set corresponding to individual described preset slope, sub-block in the L of a loss data block is recovered, comprising:

According to the priority of slope straight line corresponding to described (L-1) individual described preset slope order from high to low, recover successively the sub-block of the loss in first row;

While only remaininging the sub-block of a loss in described first row, utilize the sub-block that recovers last loss in described first row through the row checking data of described first row;

According to row order, successively the sub-block that remains the loss in (M-1) row is recovered;

Wherein, the mode of determining the priority of described slope straight line is:

Sub-block distance adjacent on slope straight line is far away, and the priority of this slope straight line is higher;

In identical two the slope straight lines of absolute value, the priority of the slope straight line that slope is negative value higher than slope on the occasion of the priority of slope straight line.

Second aspect, provides a kind of Data Recapture Unit, comprising:

Data block acquisition module, for obtaining N the data block being stored on one or more memory devices, each data block is divided into M sub-block, all sub-blocks after decile are formed to the matrix distribution of N*M, wherein, N and M are the integer that is greater than 1, and N represents the line number of matrix, and M represents matrix column number;

Row checking data set determination module, for determining the set of row checking data, the set of described row checking data comprises M row checking data, each row checking data is undertaken obtaining after XOR by all sub-blocks in each row;

Oblique checking data set determination module, for determining at least one oblique checking data set, each oblique checking data set comprises a plurality of oblique checking datas, and each oblique checking data value is for to carry out obtaining after XOR to all sub-blocks in the described matrix of the straight-line pass of the slope with preset:

When described preset slope is negative slope, during the N of usining is capable, the sub-block of each row is as a data block of straight line process, the all sub-blocks that absolute value are less than or equal in the described matrix of 1 one or more negative slope straight line process carry out XOR, obtain the value of each oblique checking data, wherein, it is 0 that the part that exceeds M row in N is capable is supplemented;

When described preset slope is positive slope, in the M of usining row, the data block of every a line is as a data block of straight line process, the all data blocks that are more than or equal in the described matrix of 1 one or more positive slope straight line process are carried out to XOR, obtain the value of each oblique checking data, wherein, it is 0 that the part that exceeds M row in N is capable is supplemented;

Wherein, the straight line of described preset slope comprises that one or more slopes are the straight line of 1/n, and n is not equal to 0 integer; When preset slope is one, slope is 1 or-1; When preset slope is while being a plurality of, first slope is that-1, second slope is not equal to first slope but absolute value equals the absolute value of first slope; The absolute value of the 3rd slope is less than the absolute value of second slope, and the 4th slope is not equal to the 3rd slope but equals the absolute value of the 3rd slope, the like;

Data block is recovered module, for when having described dropout of data block, utilizes the set of described row checking data and described oblique checking data set that the sub-block in the data block of loss is recovered.

In conjunction with above-mentioned second aspect, in the possible implementation of the first, when preset slope is negative slope, during the N of usining is capable, the sub-block of each row is as a data block of straight line process, absolute value is less than or equal to all sub-blocks in the described matrix of 1 one or more negative slope straight line process, comprises following data block:

First sub-block be N capable in k column data piece, k is greater than 0 integer, k comprises M row is mended to the columns after 0 expansion;

Second sub-block is the capable k-|n| row of N-1;

The 3rd sub-block is the capable k-2|n| row of N-2;

The like, last piece sub-block is last by after above-mentioned rule calculating, also the sub-block in matrix.

In conjunction with above-mentioned second aspect, in the possible implementation of the second, when preset slope is positive slope, in the M of usining row, the sub-block of every a line is as a data block of straight line process, be more than or equal to all sub-blocks in the described matrix of 1 one or more positive slope straight line process, comprise following data block:

First sub-block is the capable data block of m in M row, and m is greater than 0 integer, and m comprises the capable line number of mending after 0 expansion to N;

Second sub-block is the capable M+|n| row of m-1;

The 3rd sub-block is the capable M+2|n| row of m-2;

The like, last piece sub-block is last by after above-mentioned rule calculating, also the sub-block in matrix.

In conjunction with above-mentioned second aspect, and first to the possible implementation of the second, in the third possible implementation, and when having L described dropout of data block,

Described data block is recovered module, specifically, by the set of row checking data and (L-1) oblique checking data set corresponding to individual described preset slope, the sub-block in the L of a loss data block is recovered, and L is more than or equal to 1 and be less than or equal to the positive integer of N.

In conjunction with above-mentioned second aspect, and the third possible implementation, in the 4th kind of possible implementation, described data block is recovered module, comprising:

The first recovery unit, for according to the priority of slope straight line corresponding to described (L-1) individual described preset slope order from high to low, recovers the sub-block of the loss in first row successively;

The second recovery unit, when only remaininging the sub-block of a loss when described first row, utilizes the sub-block that recovers last loss in described first row through the row checking data of described first row;

The 3rd recovery unit, for according to row order, recovers the sub-block that remains the loss in (M-1) row successively;

Wherein, the mode of determining the priority of described slope straight line is:

Sub-block distance adjacent on slope straight line is far away, and the priority of this slope straight line is higher;

In identical two the slope straight lines of absolute value, the priority of the slope straight line that slope is negative value higher than slope on the occasion of the priority of slope straight line.

In the embodiment of the present invention, the XOR that utilization meets between all sub-blocks of slope line process of preset slope calculates the second check block, can redundant data be set to the data block of arbitrary number, and there is loss of data, while utilizing redundant data to carry out the recovery of obliterated data, only by the XOR between the corresponding sub block in the first check block and the second check block, can realize, therefore, can improve data and recover efficiency.

Accompanying drawing explanation

In order to be illustrated more clearly in the embodiment of the present invention or technical scheme of the prior art, to the accompanying drawing of required use in embodiment or description of the Prior Art be briefly described below, apparently, for those of ordinary skills, do not paying under the prerequisite of creative work, can also obtain according to these accompanying drawings other accompanying drawing.

Fig. 1 be in prior art RDP realize principle schematic

Fig. 2 be in prior art EVENODD realize principle schematic;

Fig. 3 is the process flow diagram of a data reconstruction method embodiment provided by the invention;

Fig. 4 is the arrangement mode schematic diagram of each sub-block in the embodiment of the present invention;

Fig. 5 is the account form schematic diagram of row check block in the embodiment of the present invention;

Fig. 6 is the calculating schematic diagram of the oblique checking data set that in the embodiment of the present invention, slope is-1 o'clock;

Fig. 7 is that the part that exceeds M row in N is capable in the embodiment of the present invention supplements is 0 schematic diagram;

Fig. 8 is the calculating schematic diagram of the oblique checking data set that in the embodiment of the present invention, slope is+1 o'clock;

Slope straight line schematic diagram when Fig. 9 is six data blocks, five check blocks;

Figure 10-18 are the data block rejuvenation schematic diagram while losing 4 blocks of data piece in 5 data blocks;

Figure 19 is a Data Recapture Unit schematic diagram provided by the invention;

Figure 20 is a kind of Data Recapture Unit schematic diagram of realizing based on computer system provided by the invention.

Embodiment

In order to make those skilled in the art person understand better the technical scheme in the embodiment of the present invention, and the above-mentioned purpose of the embodiment of the present invention, feature and advantage can be become apparent more, below in conjunction with accompanying drawing, technical scheme in the embodiment of the present invention is described in further detail.

First, introduce a kind of data reconstruction method provided by the invention.

Referring to Fig. 3, be the flow process of a data reconstruction method embodiment provided by the invention, treatment scheme specifically can comprise:

Step 301, obtain N the data block being stored on one or more memory devices, each data block is divided into M sub-block, all sub-blocks after decile are formed to the matrix distribution of N*M, wherein, N and M are the integer that is greater than 1, and N represents the line number of matrix, and M represents matrix column number.

In this step, the data of data block in can corresponding a certain disk, can be also that certain file data is divided into several parts, each data block correspondence part wherein.Disk can be to be generally hard disk, for example: traditional mechanical hard disk, solid state hard disc (Solid State Disk, SSD) etc.

Each data block is divided into the sub-block of similar number, the sub-block of all data blocks is arranged as to the array format of N*M, wherein, N and M are the integer that is greater than 1, and N represents the line number of matrix, and M represents matrix column number.All sub-blocks of corresponding each data block are arranged in independently a line of array, and the reference position sub-block of each row is positioned at the first row of array.

As shown in Figure 4, be the arrayed mode of each sub-block in the embodiment of the present invention.Suppose to have 4 blocks of data piece: D0, D1, D2 and D3, every blocks of data piece is divided into four sub-blocks, and the sub-block that D0 is divided into comprises: D00, D01, D02 and D03; The sub-block that D1 is divided into comprises: D10, D11, D12 and D13; The sub-block that D2 is divided into comprises: D20, D21, D22 and D23; The sub-block that D3 is divided into comprises: D30, D31, D32 and D33.Respectively D0-D3 sub-block is separately arranged on to independently a line, head and the tail aligned in position between each row, that is: the reference position sub-block of each row is positioned at the first row of array.

Step 302, determine the set of row checking data, the set of described row checking data comprises M row checking data, and each row checking data is undertaken obtaining after XOR by all sub-blocks in each row.

In this step, order is carried out XOR by all sub-blocks in each row successively, and the operation result of each row is a row checking data, and M row checking data forms the set of row checking data.

The array of sub-block shown in Fig. 4 of still take is example, and as shown in Figure 5, the data block of being passed by the dotted line with arrow will participate in an XOR account form of row checking data, and result of calculation is a row checking data.According to the row order in array in Fig. 5, all sub-blocks in each row are carried out to XOR, obtain respectively result of calculation P0, P1, P2 and P3, the set of P0, P1, P2 and P3 forms the set of row checking data, in the embodiment of the present invention, with P, represent the set of row checking data.

Step 303, determine at least one oblique checking data set, each oblique checking data set comprises a plurality of oblique checking datas, and each oblique checking data value is for to carry out obtaining after XOR to all sub-blocks in the described matrix of the straight-line pass of the slope with preset:

When described preset slope is negative slope, during the N of usining is capable, the sub-block of each row is as a data block of straight line process, the all sub-blocks that absolute value are less than or equal in the described matrix of 1 one or more negative slope straight line process carry out XOR, obtain the value of each oblique checking data, wherein, it is 0 that the part that exceeds M row in N is capable is supplemented;

When described preset slope is positive slope, in the M of usining row, the data block of every a line is as a data block of straight line process, the all data blocks that are more than or equal in the described matrix of 1 one or more positive slope straight line process are carried out to XOR, obtain the value of each oblique checking data, wherein, the part exceeding in M row being supplemented is 0;

Wherein, the straight line of described preset slope comprises that one or more slopes are the straight line of 1/n, and n is not equal to 0 integer; When preset slope is one, slope is 1 or-1; When preset slope is while being a plurality of, first slope is that-1, second slope is not equal to first slope but absolute value equals the absolute value of first slope; The absolute value of the 3rd slope is less than the absolute value of second slope, and the 4th slope is not equal to the 3rd slope but equals the absolute value of the 3rd slope, the like.

In the embodiment of the present invention, preset slope is 1/n, and n is not equal to 0 integer, that is: ± 1, ± 1/2, ± 1/3, ± 1/4 ... while the following describes positive negative slope, each negative slope straight line is through which sub-block in matrix.

(1) when preset slope is negative slope, during the N of usining is capable, the sub-block of each row is as a data block of straight line process, absolute value is less than or equal to all sub-blocks in the described matrix of 1 one or more negative slope straight line process, comprises following data block:

First sub-block be N capable in k column data piece, k is greater than 0 integer, k comprises M row is mended to the columns after 0 expansion;

Second sub-block is the capable k-|n| row of N-1;

The 3rd sub-block is the capable k-2|n| row of N-2;

The like, last piece sub-block is last by after above-mentioned rule calculating, also the sub-block in matrix.

The calculating schematic diagram that Figure 6 shows that the oblique checking data set that under this embodiment, slope is at-1 o'clock, herein, the Q of take represents the oblique checking data set that slope is at-1 o'clock.In Fig. 6, the sub-block that the slope straight line that is-1 by the slope with arrow passes will participate in an XOR, and result of calculation is each time an oblique checking data in Q.Wherein, tiltedly checking data Q0 is the backup of D30, tiltedly checking data Q1 is obtained by D20 and D31 XOR, tiltedly checking data Q2 is obtained by D10, D21 and D32 XOR, tiltedly checking data Q3 is obtained by D00, D11, D22 and D33 XOR, tiltedly checking data Q4 is obtained by D01, D12 and D23 XOR, and tiltedly checking data Q5 is obtained by D02 and D13 XOR, and tiltedly checking data Q6 is the backup of D03.The oblique checking data Q0-Q6 generating successively forms oblique checking data set Q.

It should be noted that, all sub-blocks in absolute value being less than or equal to the described matrix of each negative slope straight line process of 1 carry out in XOR process, and for the ease of calculating, it is 0 that the part that exceeds M row in need to N is capable is supplemented.As shown in Figure 7, when calculating Q4-Q6, respectively the part that exceeds 4 row in corresponding row being supplemented is 0.

(2), when preset slope is positive slope, in the M of usining row, the sub-block of every a line, as a data block of straight line process, is more than or equal to all sub-blocks in the described matrix of 1 one or more positive slope straight line process, comprises following data block:

First sub-block is the capable data block of m in M row, and m is greater than 0 integer, and m comprises the capable line number of mending after 0 expansion to N;

Second sub-block is the capable M+|n| row of m-1;

The 3rd sub-block is the capable M+2|n| row of m-2;

The like, last piece sub-block is last by after above-mentioned rule calculating, also the sub-block in matrix.

The calculating schematic diagram that Figure 8 shows that the oblique checking data set that under this implementation, slope is at+1 o'clock, herein, the R of take represents the oblique checking data set that slope is at+1 o'clock.In Fig. 8, the data block of being passed by the line with arrow will participate in an XOR, and result of calculation is an oblique checking data in R.Wherein, tiltedly checking data R0 is the backup of D00, and R1 is obtained by D10 and D01 XOR, R2 is obtained by D20, D11 and D02 XOR, and R3 is obtained by D30, D21, D12 and D03 XOR, and R4 is obtained by D31, D22 and D13 XOR, R5 is obtained by D32 and D23 XOR, and R6 is the backup of D33.The oblique checking data R0-R6 generating successively forms oblique checking data set R.

Equally, all data blocks that are more than or equal in the described matrix of each positive slope straight line process of 1 are carried out in XOR process, for the ease of calculating, it is 0 that the part that exceeds M row in need to N is capable is supplemented.

Slope straight line situation while having provided 6 data blocks (D0～D5), five check blocks in Fig. 9, five check blocks are followed successively by: P, Q, R, S and T.Q and R are symmetrical, slope be respectively-1 and 1, S and T be also symmetrical, slope is respectively-1/2 and 1/2.By that analogy, can obtain the arbitrarily oblique checking data that slope is 1/n.

Step 304, when having described dropout of data block, utilize the set of described row checking data and described oblique checking data set that the sub-block in the data block of loss is recovered.

In the embodiment of the present invention, utilize the set of row checking data and tiltedly checking data set, data block has been carried out to redundancy setting.When having data block loss of data, can utilize the set of row checking data and tiltedly checking data set, recover the sub-block of loss, and then, recover whole data block.

In the embodiment of the present invention, the XOR that utilization meets between the sub-block of each slope straight line process of preset slope calculates oblique checking data set, and, by all sub-blocks in each row, undertaken obtaining the set of row checking data after XOR, by oblique checking data set and the set of row checking data, the redundant data of formation to the data block of arbitrary number, and there is loss of data, while utilizing redundant data to carry out the recovery of obliterated data, only by the XOR between the corresponding checking data in redundant data, can realize, therefore, can improve data and recover efficiency.

In the embodiment of the present invention, tiltedly checking data adopts non-recurrence mode to calculate acquisition.Because the calculating of oblique checking data all takes pure XOR mode to generate according to specific slope, with respect to calculating the mode of check block according to establishing an equation in prior art, can greatly improve the computing velocity of check block.

When having described dropout of data block, utilize the set of described row checking data and described oblique checking data set that the sub-block in the data block of loss is recovered, this implementation specifically comprises:

When having L described dropout of data block, by the set of row checking data and (L-1) oblique checking data set corresponding to individual described preset slope, the sub-block in the L of a loss data block is recovered, L is more than or equal to 1 and be less than or equal to the positive integer of N.

In this implementation, when having the dropout of data block of some numbers, need the checking data set of similar number to carry out the recovery of obliterated data piece.For example: when having 2 dropout of data block, need the recovery of 2 data blocks that 2 checking data set lose, 2 checking datas comprise: the set of row checking data and 1 oblique checking data set that preset slope is corresponding, this preset slope can be+1 or-1, and corresponding oblique checking data set can be: Q or R; When having 5 dropout of data block, need the recovery of 5 data blocks that 5 checking data set lose, 5 checking datas comprise: the set of row checking data and 4 oblique checking data set that preset slope is corresponding, 4 oblique checking data set corresponding to preset slope comprise respectively: Q, R, S and T.

The following describes and utilize the set of row checking data and (L-1) oblique checking data set corresponding to individual described preset slope, in the process that the sub-block in the L of a loss data block is recovered, the priority selecting sequence of slope.Specific as follows:

According to the priority of slope straight line corresponding to described (L-1) individual described preset slope order from high to low, recover successively the sub-block of the loss in first row;

While only remaininging the sub-block of a loss in described first row, utilize the sub-block that recovers last loss in described first row through the row checking data of described first row;

According to row order, successively the sub-block that remains the loss in (M-1) row is recovered;

Wherein, the mode of determining the priority of described slope straight line is:

Sub-block distance adjacent on slope straight line is far away, and the priority of this slope straight line is higher;

In identical two the slope straight lines of absolute value, the priority of the slope straight line that slope is negative value higher than slope on the occasion of the priority of slope straight line.

The scene of losing 5 data blocks of still take is example, needs the recovery of 5 data blocks that 5 checking data set lose, and 5 checking data set comprise: row checking data set P and 4 oblique checking data set: Q, R, S and T.For S and T, because sub-block distance adjacent on the two slope straight line is distal to adjacent sub-block distance on Q and R slope straight line, the priority of S and T is higher than Q and R; The slope absolute value of Q and R is identical, the priority of the slope straight line that is negative value according to slope higher than slope on the occasion of the priority of slope straight line, the priority of Q is higher than the priority of R; And, owing to recovering according to row.While only remaininging the sub-block of a loss in these row that recover, utilize the row checking data through these row to recover this last sub-block to be recovered.By that analogy, according to row order, successively the sub-block of the loss in remaining columns is recovered.

Take that to lose 4 blocks of data pieces in 5 data blocks be example, by diagram, the rejuvenation of obliterated data piece is described.When losing 4 data blocks, need 4 checking data set: P, Q, R and S.The priority orders of Q, R and S is: S is higher than Q, and Q is higher than R, and rejuvenation is specific as follows:

(1) as shown in figure 10, with S0, recover D40, in figure, dash area sub-block represents to lose sub-block;

(2) as shown in figure 11, with S1, recover D41;

(3) as shown in figure 12, with Q1, recover D30;

(4) as shown in figure 13, with R1, recover D10;

(5) as shown in figure 14, with P0, recover D20;

So far, the sub-block full recovery that first row is lost is complete;

(6) as shown in figure 15, with S2, recover D42;

(7) as shown in figure 16, with Q2, recover D31;

(8) as shown in figure 17, with R2, recover D11;

(9) as shown in figure 18, with P1, recover D21;

So far, secondary series full recovery is complete.

In like manner, the three～ten this rule of leu can all be resumed out.

Corresponding with data reconstruction method embodiment provided by the invention, the present invention also provides a kind of Data Recapture Unit.

As shown in figure 19, be the embodiment of a kind of Data Recapture Unit provided by the invention, this device specifically can comprise:

Datablock acquisition module 1901, for obtaining N the data block being stored on one or more memory devices, each data block is divided into M sub-block, all sub-blocks after decile are formed to the matrix distribution of N*M, wherein, N and M are the integer that is greater than 1, and N represents the line number of matrix, and M represents matrix column number.

Row checking dataset determination module 1902, for determining the set of row checking data, the set of described row checking data comprises M row checking data, each row checking data is undertaken obtaining after XOR by all sub-blocks in each row.

Oblique checking data setdetermination module 1903, for determining at least one oblique checking data set, each oblique checking data set comprises a plurality of oblique checking datas, and each oblique checking data value is for to carry out obtaining after XOR to all sub-blocks in the described matrix of the straight-line pass of the slope with preset.

When described preset slope is negative slope, during the N of usining is capable, the sub-block of each row is as a data block of straight line process, the all sub-blocks that absolute value are less than or equal in the described matrix of 1 one or more negative slope straight line process carry out XOR, obtain the value of each oblique checking data, wherein, it is 0 that the part that exceeds M row in N is capable is supplemented;

When described preset slope is positive slope, in the M of usining row, the data block of every a line is as a data block of straight line process, the all data blocks that are more than or equal in the described matrix of 1 one or more positive slope straight line process are carried out to XOR, obtain the value of each oblique checking data, wherein, it is 0 that the part that exceeds M row in N is capable is supplemented;

Wherein, the straight line of described preset slope comprises that one or more slopes are the straight line of 1/n, and n is not equal to 0 integer; When preset slope is one, slope is 1 or-1; When preset slope is while being a plurality of, first slope is that-1, second slope is not equal to first slope but absolute value equals the absolute value of first slope; The absolute value of the 3rd slope is less than the absolute value of second slope, and the 4th slope is not equal to the 3rd slope but equals the absolute value of the 3rd slope, the like;

Data block is recoveredmodule 1904, for when having described dropout of data block, utilizes the set of described row checking data and described oblique checking data set that the sub-block in the data block of loss is recovered.

Wherein, the data of data block in can corresponding a certain disk, can be also that certain file data is divided into several parts, each data block correspondence part wherein.Disk can be to be generally hard disk, such as: traditional mechanical hard disk, solid state hard disc etc.Each data block is divided into the sub-block of similar number, the sub-block of all data blocks is arranged as to the array format of N*M, wherein, N and M are the integer that is greater than 1, and N represents the line number of matrix, and M represents matrix column number.All sub-blocks of corresponding each data block are arranged in independently a line of array, and the reference position sub-block of each row is positioned at the first row of array.

In addition, order is carried out XOR by all sub-blocks in each row successively, and the operation result of each row is a row checking data, and M row checking data forms the set of row checking data.

In the embodiment of the present invention, the XOR that utilization meets between the sub-block of each slope straight line process of preset slope calculates oblique checking data set, and, by all sub-blocks in each row, undertaken obtaining the set of row checking data after XOR, by oblique checking data set and the set of row checking data, the redundant data of formation to the data block of arbitrary number, and there is loss of data, while utilizing redundant data to carry out the recovery of obliterated data, only by the XOR between the corresponding checking data in redundant data, can realize, therefore, can improve data and recover efficiency.

Above-mentioned preset slope is 1/n, and n is not equal to 0 integer, that is: ± 1, ± 1/2, ± 1/3, ± 1/4 ... while the following describes positive negative slope, each negative slope straight line is through which sub-block in matrix.

(1) when preset slope is negative slope, during the N of usining is capable, the sub-block of each row is as a data block of straight line process, absolute value is less than or equal to all sub-blocks in the described matrix of 1 one or more negative slope straight line process, comprises following data block:

First sub-block be N capable in k column data piece, k is greater than 0 integer, k comprises M row is mended to the columns after 0 expansion;

Second sub-block is the capable k-|n| row of N-1;

The 3rd sub-block is the capable k-2|n| row of N-2;

The like, last piece sub-block is last by after above-mentioned rule calculating, also the sub-block in matrix.

(2), when preset slope is positive slope, in the M of usining row, the sub-block of every a line, as a data block of straight line process, is more than or equal to all sub-blocks in the described matrix of 1 one or more positive slope straight line process, comprises following data block:

First sub-block is the capable data block of m in M row, and m is greater than 0 integer, and m comprises the capable line number of mending after 0 expansion to N;

Second sub-block is the capable M+|n| row of m-1;

The 3rd sub-block is the capable M+2|n| row of m-2;

The like, last piece sub-block is last by after above-mentioned rule calculating, also the sub-block in matrix.

When having L described dropout of data block, the specific implementation of utilizing described data block recovery module to carry out data recovery is: by the set of row checking data and (L-1) oblique checking data set corresponding to individual described preset slope, sub-block in the L of a loss data block is recovered, and L is more than or equal to 1 and be less than or equal to the positive integer of N.

Under this data recovery pattern, described data block is recovered module, specifically can comprise:

The first recovery unit, for according to the priority of slope straight line corresponding to described (L-1) individual described preset slope order from high to low, recovers the sub-block of the loss in first row successively;

The second recovery unit, when only remaininging the sub-block of a loss when described first row, utilizes the sub-block that recovers last loss in described first row through the row checking data of described first row;

The 3rd recovery unit, for according to row order, recovers the sub-block that remains the loss in (M-1) row successively;

Wherein, the mode of determining the priority of described slope straight line is:

Sub-block distance adjacent on slope straight line is far away, and the priority of this slope straight line is higher;

In identical two the slope straight lines of absolute value, the priority of the slope straight line that slope is negative value higher than slope on the occasion of the priority of slope straight line.

In the embodiment of the present invention, tiltedly checking data adopts non-recurrence mode to calculate acquisition.Because the calculating of oblique checking data all takes pure XOR mode to generate according to specific slope, with respect to calculating the mode of check block according to establishing an equation in prior art, can greatly improve the computing velocity of check block.

The present invention also provides a kind of Data Recapture Unit of realizing based on computer system, and as shown in figure 20, in specific implementation, the device of the embodiment of the present invention can comprise:processor 2001,storer 2002,bus 2003 andreceiver 2004; Wherein, describedprocessor 2001,storer 2002 andreceiver 2004 interconnect by describedbus 2003; Describedstorer 2002 is for storing computer executed instructions; Described receiver is for obtaining N the data block being stored on one or more memory devices, each data block is divided into M sub-block, all sub-blocks after decile are formed to the matrix distribution of N*M, wherein, N and M are the integer that is greater than 1, N represents the line number of matrix, and M represents matrix column number.

Describedprocessor 2001 is carried out the described computer executed instructions of describedstorer 2002 storages, carries out operation as follows:

Determine the set of row checking data, the set of described row checking data comprises M row checking data, and each row checking data is undertaken obtaining after XOR by all sub-blocks in each row;

Determine at least one oblique checking data set, each oblique checking data set comprises a plurality of oblique checking datas, and each oblique checking data value is for to carry out obtaining after XOR to all sub-blocks in the described matrix of the straight-line pass of the slope with preset:

When described preset slope is negative slope, during the N of usining is capable, the sub-block of each row is as a data block of straight line process, the all sub-blocks that absolute value are less than or equal in the described matrix of 1 one or more negative slope straight line process carry out XOR, obtain the value of each oblique checking data, wherein, it is 0 that the part that exceeds M row in N is capable is supplemented;

When described preset slope is positive slope, in the M of usining row, the data block of every a line is as a data block of straight line process, the all data blocks that are more than or equal in the described matrix of 1 one or more positive slope straight line process are carried out to XOR, obtain the value of each oblique checking data, wherein, it is 0 that the part that exceeds M row in N is capable is supplemented;

Wherein, the straight line of described preset slope comprises that one or more slopes are the straight line of 1/n, and n is not equal to 0 integer; When preset slope is one, slope is 1 or-1; When preset slope is while being a plurality of, first slope is that-1, second slope is not equal to first slope but absolute value equals the absolute value of first slope; The absolute value of the 3rd slope is less than the absolute value of second slope, and the 4th slope is not equal to the 3rd slope but equals the absolute value of the 3rd slope, the like;

When having described dropout of data block, utilize the set of described row checking data and described oblique checking data set that the sub-block in the data block of loss is recovered.

In the embodiment of the present invention, processor can be central processing unit (central processing unit, CPU), special IC (application-specific integrated circuit, ASIC) etc.

Computer-readable storage medium can have program stored therein, and this program can comprise the part or all of step in each embodiment of method of the data transmission that the embodiment of the present invention provides while carrying out.Described storage medium can be magnetic disc, CD, read-only store-memory body (Read-Only Memory, ROM) or random store-memory body (Random Access Memory, RAM) etc.

Those of ordinary skills can recognize, unit and the algorithm steps of each example of describing in conjunction with embodiment disclosed herein, can realize with the combination of electronic hardware or computer software and electronic hardware.These functions are carried out with hardware or software mode actually, depend on application-specific and the design constraint of technical scheme.Professional and technical personnel can specifically should be used for realizing described function with distinct methods to each, but this realization should not thought and exceeds scope of the present invention.

Those skilled in the art can be well understood to, and for convenience and simplicity of description, the specific works process of the system of foregoing description, equipment and unit, can, with reference to the corresponding process in preceding method embodiment, not repeat them here.

In the several embodiment that provide in the application, should be understood that disclosed system, equipment and method can realize by another way.For example, apparatus embodiments described above is only schematic, for example, the division of described unit, be only that a kind of logic function is divided, during actual realization, can have other dividing mode, for example a plurality of unit or assembly can in conjunction with or can be integrated into another system, or some features can ignore, or do not carry out.Another point, shown or discussed coupling each other or direct-coupling or communication connection can be by some interfaces, the indirect coupling of equipment or unit or communication connection can be electrically, machinery or other form.

The described unit as separating component explanation can or can not be also physically to separate, and the parts that show as unit can be or can not be also physical locations, can be positioned at a place, or also can be distributed in a plurality of network element.Can select according to the actual needs some or all of unit wherein to realize the object of the present embodiment scheme.

In addition, each functional unit in each embodiment of the present invention can be integrated in a processing unit, can be also that the independent physics of unit exists, and also can be integrated in a unit two or more unit.

If described function usings that the form of SFU software functional unit realizes and during as production marketing independently or use, can be stored in a computer read/write memory medium.Understanding based on such, the part that technical scheme of the present invention contributes to prior art in essence in other words or the part of this technical scheme can embody with the form of software product, this computer software product is stored in a storage medium, comprise that some instructions are with so that a computer equipment (can be personal computer, server, or the network equipment etc.) or processor (processor) carry out all or part of step of method described in each embodiment of the present invention.And aforesaid storage medium comprises: various media that can be program code stored such as USB flash disk, portable hard drive, ROM (read-only memory) (ROM, Read-Only Memory), random access memory (RAM, Random Access Memory), magnetic disc or CDs.

The above; be only the specific embodiment of the present invention, but protection scope of the present invention is not limited to this, is anyly familiar with those skilled in the art in the technical scope that the present invention discloses; can expect easily changing or replacing, within all should being encompassed in protection scope of the present invention.Therefore, protection scope of the present invention should be as the criterion by the described protection domain with claim.

Claims (10)

1. a data reconstruction method, is characterized in that, comprising:

Obtain N the data block being stored on one or more memory devices, each data block is divided into M sub-block, all sub-blocks after decile are formed to the matrix distribution of N*M, wherein, N and M are the integer that is greater than 1, and N represents the line number of matrix, and M represents matrix column number;

Determine the set of row checking data, the set of described row checking data comprises M row checking data, and each row checking data is undertaken obtaining after XOR by all sub-blocks in each row;

Determine at least one oblique checking data set, each oblique checking data set comprises a plurality of oblique checking datas, and each oblique checking data value is for to carry out obtaining after XOR to all sub-blocks in the described matrix of the straight-line pass of the slope with preset:

When described preset slope is negative slope, during the N of usining is capable, the sub-block of each row is as a data block of straight line process, the all sub-blocks that absolute value are less than or equal in the described matrix of 1 one or more negative slope straight line process carry out XOR, obtain the value of each oblique checking data, wherein, it is 0 that the part that exceeds M row in N is capable is supplemented;

When described preset slope is positive slope, in the M of usining row, the data block of every a line is as a data block of straight line process, the all data blocks that are more than or equal in the described matrix of 1 one or more positive slope straight line process are carried out to XOR, obtain the value of each oblique checking data, wherein, it is 0 that the part that exceeds M row in N is capable is supplemented;

Wherein, the straight line of described preset slope comprises that one or more slopes are the straight line of 1/n, and n is not equal to 0 integer; When preset slope is one, slope is 1 or-1; When preset slope is while being a plurality of, first slope is that-1, second slope is not equal to first slope but absolute value equals the absolute value of first slope; The absolute value of the 3rd slope is less than the absolute value of second slope, and the 4th slope is not equal to the 3rd slope but equals the absolute value of the 3rd slope, the like;

When having described dropout of data block, utilize the set of described row checking data and described oblique checking data set that the sub-block in the data block of loss is recovered.

2. method according to claim 1, is characterized in that,

When preset slope is negative slope, during the N of usining is capable, the sub-block of each row is as a data block of straight line process, and absolute value is less than or equal to all sub-blocks in the described matrix of 1 one or more negative slope straight line process, comprises following data block:

First sub-block be N capable in k column data piece, k is greater than 0 integer, k comprises M row is mended to the columns after 0 expansion;

Second sub-block is the capable k-|n| row of N-1;

The 3rd sub-block is the capable k-2|n| row of N-2;

The like, last piece sub-block is last by after above-mentioned rule calculating, also the sub-block in matrix.

3. method according to claim 1, is characterized in that,

When preset slope is positive slope, in the M of usining row, the sub-block of every a line, as a data block of straight line process, is more than or equal to all sub-blocks in the described matrix of 1 one or more positive slope straight line process, comprises following data block:

First sub-block is the capable data block of m in M row, and m is greater than 0 integer, and m comprises the capable line number of mending after 0 expansion to N;

Second sub-block is the capable M+|n| row of m-1;

The 3rd sub-block is the capable M+2|n| row of m-2;

The like, last piece sub-block is last by after above-mentioned rule calculating, also the sub-block in matrix.

4. according to the method described in any one in claim 1-3, it is characterized in that, described when having described dropout of data block, utilize the set of described row checking data and described oblique checking data set that the sub-block in the data block of loss is recovered, comprising:

When having L described dropout of data block, by the set of row checking data and (L-1) oblique checking data set corresponding to individual described preset slope, the sub-block in the L of a loss data block is recovered, L is more than or equal to 1 and be less than or equal to the positive integer of N.

5. method according to claim 4, it is characterized in that, described when having L described dropout of data block, use the set of row checking data and (L-1) oblique checking data set corresponding to individual described preset slope, sub-block in the L of a loss data block is recovered, comprising:

According to the priority of slope straight line corresponding to described (L-1) individual described preset slope order from high to low, recover successively the sub-block of the loss in first row;

While only remaininging the sub-block of a loss in described first row, utilize the sub-block that recovers last loss in described first row through the row checking data of described first row;

According to row order, successively the sub-block that remains the loss in (M-1) row is recovered;

Wherein, the mode of determining the priority of described slope straight line is:

Sub-block distance adjacent on slope straight line is far away, and the priority of this slope straight line is higher;

In identical two the slope straight lines of absolute value, the priority of the slope straight line that slope is negative value higher than slope on the occasion of the priority of slope straight line.

6. a Data Recapture Unit, is characterized in that, comprising:

Data block acquisition module, for obtaining N the data block being stored on one or more memory devices, each data block is divided into M sub-block, all sub-blocks after decile are formed to the matrix distribution of N*M, wherein, N and M are the integer that is greater than 1, and N represents the line number of matrix, and M represents matrix column number;

Row checking data set determination module, for determining the set of row checking data, the set of described row checking data comprises M row checking data, each row checking data is undertaken obtaining after XOR by all sub-blocks in each row;

Oblique checking data set determination module, for determining at least one oblique checking data set, each oblique checking data set comprises a plurality of oblique checking datas, and each oblique checking data value is for to carry out obtaining after XOR to all sub-blocks in the described matrix of the straight-line pass of the slope with preset:

When described preset slope is negative slope, during the N of usining is capable, the sub-block of each row is as a data block of straight line process, the all sub-blocks that absolute value are less than or equal in the described matrix of 1 one or more negative slope straight line process carry out XOR, obtain the value of each oblique checking data, wherein, it is 0 that the part that exceeds M row in N is capable is supplemented;

When described preset slope is positive slope, in the M of usining row, the data block of every a line is as a data block of straight line process, the all data blocks that are more than or equal in the described matrix of 1 one or more positive slope straight line process are carried out to XOR, obtain the value of each oblique checking data, wherein, it is 0 that the part that exceeds M row in N is capable is supplemented;

Wherein, the straight line of described preset slope comprises that one or more slopes are the straight line of 1/n, and n is not equal to 0 integer; When preset slope is one, slope is 1 or-1; When preset slope is while being a plurality of, first slope is that-1, second slope is not equal to first slope but absolute value equals the absolute value of first slope; The absolute value of the 3rd slope is less than the absolute value of second slope, and the 4th slope is not equal to the 3rd slope but equals the absolute value of the 3rd slope, the like;

Data block is recovered module, for when having described dropout of data block, utilizes the set of described row checking data and described oblique checking data set that the sub-block in the data block of loss is recovered.

7. device according to claim 6, is characterized in that,

When preset slope is negative slope, during the N of usining is capable, the sub-block of each row is as a data block of straight line process, and absolute value is less than or equal to all sub-blocks in the described matrix of 1 one or more negative slope straight line process, comprises following data block:

First sub-block be N capable in k column data piece, k is greater than 0 integer, k comprises M row is mended to the columns after 0 expansion;

Second sub-block is the capable k-|n| row of N-1;

The 3rd sub-block is the capable k-2|n| row of N-2;

The like, last piece sub-block is last by after above-mentioned rule calculating, also the sub-block in matrix.

8. device according to claim 6, is characterized in that,

When preset slope is positive slope, in the M of usining row, the sub-block of every a line, as a data block of straight line process, is more than or equal to all sub-blocks in the described matrix of 1 one or more positive slope straight line process, comprises following data block:

First sub-block is the capable data block of m in M row, and m is greater than 0 integer, and m comprises the capable line number of mending after 0 expansion to N;

Second sub-block is the capable M+|n| row of m-1;

The 3rd sub-block is the capable M+2|n| row of m-2;

The like, last piece sub-block is last by after above-mentioned rule calculating, also the sub-block in matrix.

9. according to the device described in any one in claim 6-8, it is characterized in that, when having L described dropout of data block,

Described data block is recovered module, specifically, by the set of row checking data and (L-1) oblique checking data set corresponding to individual described preset slope, the sub-block in the L of a loss data block is recovered, and L is more than or equal to 1 and be less than or equal to the positive integer of N.

10. device according to claim 6, is characterized in that, described data block is recovered module, comprising:

The first recovery unit, for according to the priority of slope straight line corresponding to described (L-1) individual described preset slope order from high to low, recovers the sub-block of the loss in first row successively;

The second recovery unit, when only remaininging the sub-block of a loss when described first row, utilizes the sub-block that recovers last loss in described first row through the row checking data of described first row;

The 3rd recovery unit, for according to row order, recovers the sub-block that remains the loss in (M-1) row successively;

Wherein, the mode of determining the priority of described slope straight line is:

Sub-block distance adjacent on slope straight line is far away, and the priority of this slope straight line is higher;

In identical two the slope straight lines of absolute value, the priority of the slope straight line that slope is negative value higher than slope on the occasion of the priority of slope straight line.

Images