WO2015010476A1 - 数据恢复方法、数据恢复设备和分布式存储系统 - Google Patents

数据恢复方法、数据恢复设备和分布式存储系统 Download PDF

Info

Publication number
WO2015010476A1
WO2015010476A1 PCT/CN2014/073383 CN2014073383W WO2015010476A1 WO 2015010476 A1 WO2015010476 A1 WO 2015010476A1 CN 2014073383 W CN2014073383 W CN 2014073383W WO 2015010476 A1 WO2015010476 A1 WO 2015010476A1
Authority
WO
WIPO (PCT)
Prior art keywords
data
data storage
diagonal
lost
storage node
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/CN2014/073383
Other languages
English (en)
French (fr)
Inventor
马晓慧
孙亚萍
陈海啸
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Huawei Technologies Co Ltd
Original Assignee
Huawei Technologies Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Huawei Technologies Co Ltd filed Critical Huawei Technologies Co Ltd
Priority to EP14733496.5A priority Critical patent/EP2854033B1/en
Priority to US14/331,485 priority patent/US9529675B2/en
Publication of WO2015010476A1 publication Critical patent/WO2015010476A1/zh
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65—Purpose and implementation aspects
    • H03M13/6502—Reduction of hardware complexity or efficient processing
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1076—Parity data used in redundant arrays of independent storages, e.g. in RAID systems
    • G06F11/1088—Reconstruction on already foreseen single or plurality of spare disks
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/25—Integrating or interfacing systems involving database management systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/27—Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/29—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
    • H03M13/2906—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes
    • H03M13/2918—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/29—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
    • H03M13/2906—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes
    • H03M13/2921—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes wherein error correction coding involves a diagonal direction
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/373—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2211/00—Indexing scheme relating to details of data-processing equipment not covered by groups G06F3/00 - G06F13/00
    • G06F2211/10—Indexing scheme relating to G06F11/10
    • G06F2211/1002—Indexing scheme relating to G06F11/1076
    • G06F2211/1028—Distributed, i.e. distributed RAID systems with parity

Definitions

  • the application is submitted to the Chinese Patent Office on July 26, 2013, and the application number is 201310320300. 3.
  • the invention name is "data recovery method, data recovery device and distributed storage system".
  • the priority of the Chinese Patent Application the entire contents of which is incorporated herein by reference.
  • the present invention relates to the field of computer technologies, and in particular, to a data recovery method, a data recovery device, and a distributed storage system.
  • BACKGROUND With the popularity of cloud computing technologies, cloud storage is becoming more and more close to people's lives. The number of cloud storage providers is also increasing year by year, and the number of suppliers in the industry has reached nearly 200. Data can be stored on remote cloud storage systems, thus greatly reducing the need for local storage. However, cloud storage still faces many problems: How to provide the highest reliability for user data at the lowest cost; How to ensure the security of user data, not being stolen, encrypted, etc.
  • an Erasure Code can be used instead of a copy.
  • the erasure code is a commonly used data redundancy error correction algorithm.
  • the most famous Erasure Code is Reed Solomon Code.
  • the check code can be obtained.
  • the CPU Central Processing Unit
  • the performance of the multiplication is very low, so the performance of the Reed Solomon Code algorithm is low.
  • the current data width of the Reed Solomon Code algorithm is up to 32 bits. The higher the bit width, the higher the performance and the performance is very limited.
  • EVEN0DD proposed by IBM in the early days is an algorithm with a redundancy of 2 (with two sets of parity data) for RAID (redundant array of independent disks) systems.
  • Cheng huang and l ihao xu proposed to extend it to a STAR algorithm with a redundancy of 3 (with three sets of parity data) (adding a check with a slope of -1).
  • a data recovery method including: in a case where a distributed storage system loses three node data, according to a non-lost check node and a data storage node Data, recovering data of the target data storage node in the three node data, the target data storage node determining according to symmetry of the lost data;
  • the target data storage node is data with the lost disk number in the middle. Recovering the data of the target data storage node in the three node data according to the data of the non-lost check node and the data storage node, including:
  • the verification data includes data of a horizontal check node, a diagonal check node, and an inverse diagonal check node;
  • the generating the diagonal adjustment factor and the inverse diagonal adjustment factor according to the verification data including:
  • ft is the diagonal adjustment factor
  • ⁇ is the first stripe unit data of the horizontal check node
  • ⁇ is the first strip of the diagonal check node Band data, which is the first stripe unit data of the inverse diagonal check node, 0 ⁇ i ⁇ p-2, p is greater than or equal to one of the data storage nodes The prime number of the number.
  • the diagonal adjustment factor, the inverse diagonal adjustment factor, the first horizontal parity data, the first diagonal parity data, and the first In the inverse diagonal check data the data of the data storage node whose lost disk number is in the middle is obtained by a crossover operation, including:
  • the stripe unit data of the storage node is converted into an exclusive OR of the two stripe unit data of the data storage node whose lost disc number is in the middle, and the data of the data storage node whose lost disc number is in the middle is obtained.
  • converting the stripe unit data of all the lost data storage nodes includes: formulating the data storage node with the lost disc number in the middle, and using the step size OffDis for x times XOR Summing, obtaining the data storage node formula in which the lost disk number is in the middle ® ) ⁇ increment + 2minDis> P ,, , if
  • system of cyclic equations obtained according to the formula of the intermediate data storage node is used to represent an exclusive OR of two data of the intermediate data storage node, and each formula of the system of cyclic equations has at most two Determining the data of the data storage node with the lost disk number in the middle, including:
  • the target data storage node is lost. And recovering data of the target data storage node in the three node data according to the data of the non-lost check node and the data storage node, including:
  • p is the disk number of the missing horizontal parity data, and p is greater than or equal to the number of data storage nodes Prime number.
  • the second diagonal check data is the second inverse diagonal check data, which is the first stripe unit data of the jth column data storage node, where r and s are the disk numbers of the lost data storage node. , is the number of data storage nodes, 0 ⁇ ⁇ ⁇ ⁇ '-1, 0 ⁇ r ⁇ s ⁇ p' ⁇ p, ⁇ > p is a modulo operation on p.
  • the XOR sum according to the diagonal adjustment factor and the inverse diagonal adjustment factor, the second diagonal check data, and the second inverse diagonal is verified, and the data of the one data storage node is obtained by using a symmetric elimination operation, including:
  • the stripe unit data of the two lost data storage nodes are transformed into two strips of a data storage node after the elimination processing
  • a data recovery device including: a target recovery unit, configured to recover a three-node data in a distributed storage system, according to a school that has not been lost Verifying data of the node and the data storage node, recovering data of the target data storage node in the three node data, the target data storage node determining according to symmetry of the lost data;
  • a downgrade recovery unit configured to downgrade and recover remaining lost data according to the restored data of the target data storage node.
  • the lost three node data packets In the case of data of three data storage nodes, the target data storage node is a data storage node whose lost disk number is in the middle; the target recovery unit includes:
  • An adjustment factor generating module configured to generate a diagonal adjustment factor and an inverse diagonal adjustment factor according to the verification data, where the verification data includes data of a horizontal check node, a diagonal check node, and an inverse diagonal check node;
  • a first check data generating module configured to generate first level check data, first diagonal check data, and first according to data of the data storage node that is not lost, the diagonal adjustment factor, and the level adjustment factor An inverse diagonal check data;
  • a cross operation module configured to optimize, according to the diagonal adjustment factor, the inverse diagonal adjustment factor, the first horizontal parity data, the first diagonal parity data, and the first inverse diagonal parity data
  • the crossover operation finds the data of the data storage node whose lost disk number is in the middle.
  • the adjustment factor generating module is specifically configured to: generate the diagonal adjustment factor by using a formula ⁇ ';
  • the diagonal adjustment factor is the inverse diagonal adjustment factor, which is the first strip unit data of the horizontal check node, and ⁇ is the first strip unit data of the diagonal check node , is the first stripe unit data of the inverse diagonal check node, Q ⁇ i ⁇ p-2, and p is a prime number greater than or equal to the number of data storage nodes.
  • the first horizontal parity data is the first diagonal parity data
  • the first inverse diagonal parity data is the data of the first stripe unit of the data storage node of the first column.
  • r, S , ⁇ are the disk number of the lost data storage node, which is the number of data storage nodes, 0 ⁇ j' ⁇ p'-l, 0 ⁇ r ⁇ s ⁇ t ⁇ p' ⁇ p , ⁇ > p is a modulo operation on p.
  • the cross operation module is specifically used to:
  • the stripe unit data of the storage node is converted into an exclusive OR of the two stripe unit data of the data storage node whose lost disc number is in the middle, and the data of the data storage node whose lost disc number is in the middle is obtained.
  • the cross operation module is further configured to: use a formula of the data storage node whose lost disk number is in the middle, and perform a k-time XOR for the step lengthDisDis Summing, obtaining the data storage node formula in which the disc number is in the middle
  • system of cyclic equations obtained according to the formula of the intermediate data storage node is used to represent an exclusive OR of two data of the intermediate data storage node, and each formula of the system of cyclic equations has at most two Determining the data of the data storage node with the lost disk number in the middle, including:
  • the target recovery unit in a case where the lost three node data includes data of a horizontal check node and two data storage nodes, the target recovery unit includes:
  • a factor exclusive OR module for generating data according to the diagonal check node and the inverse diagonal check node An exclusive OR of a diagonal adjustment factor and an inverse diagonal adjustment factor;
  • a second check data generating module configured to generate second diagonal check data and second inverse diagonal check data according to data of the data storage node that is not lost;
  • a symmetric elimination operation module configured to perform symmetric elimination operation according to the exclusive OR sum of the diagonal adjustment factor and the inverse diagonal adjustment factor, the second diagonal verification data, and the second inverse diagonal verification data The data of any one of the two data storage nodes that are lost is found.
  • An exclusive OR of a diagonal adjustment factor wherein, the diagonal adjustment factor is the inverse diagonal adjustment factor, ⁇ is the first strip unit data of the diagonal check node, and the inverse pair is The first stripe unit data of the corner check node, Q ⁇ i ⁇ p-2, p is the disc number of the lost horizontal check data, and p is a prime number greater than or equal to the number of data storage nodes.
  • the symmetric elimination operation module is specifically used to:
  • a distributed storage system including: a plurality of data storage nodes, a plurality of check nodes, and a data recovery device;
  • the data recovery device adopts a data recovery device of any one of the embodiments of the present invention.
  • the data recovery by using the verification data can ensure the effective utilization of the distributed system, such as the cloud storage storage space, to meet the performance requirements of the distributed storage system; and determine the target data storage node that is first restored according to the symmetry of the lost data. And recovering the lost three node data according to the check data and the unmissed data, which can improve the data recovery performance in the case where the distributed storage system loses three nodes of data.
  • the distributed system such as the cloud storage storage space
  • Figure la is a flowchart of a data recovery method according to Embodiment 1 of the present invention.
  • 11T is a schematic diagram of a check node in a data recovery method according to Embodiment 1 of the present invention.
  • FIG. 2a is a flowchart of a data offloading method according to Embodiment 2 of the present invention.
  • FIG. 2b is a schematic diagram of a crossover operation in a data offloading method according to Embodiment 2 of the present invention
  • FIG. 2c is a schematic diagram of cyclic XOR summation according to a step size in a data offloading method according to Embodiment 2 of the present invention
  • FIG. 2d is a cyclic XOR summation according to an optimized step size in a data offloading method according to Embodiment 2 of the present invention
  • FIG. 2 e is a schematic structural diagram of data storage in a data recovery method according to Embodiment 2 of the present invention.
  • FIG. 3a is a flowchart of a data offloading method according to Embodiment 3 of the present invention.
  • 3b is a schematic diagram of a symmetric elimination in a data offloading method according to Embodiment 3 of the present invention.
  • FIG. 4 is a structural block diagram of a data recovery device according to Embodiment 4 of the present invention.
  • FIG. 5 is a structural block diagram of a data recovery device according to Embodiment 5 of the present invention.
  • FIG. 6 is a structural block diagram of a data recovery device according to Embodiment 6 of the present invention.
  • FIG. 7 is a structural block diagram of a data recovery device according to Embodiment 7 of the present invention
  • FIG. 8 is a structural block diagram of a distributed storage system according to Embodiment 8 of the present invention. detailed description
  • FIG. 1A is a flowchart of a data recovery method according to Embodiment 1 of the present invention.
  • the data recovery method includes: Step 101: In case the distributed storage system loses three node data, according to the unmissed school The data of the node and the data storage node are restored, and the data of the target data storage node in the three node data is restored, and the target data storage node is determined according to the symmetry of the lost data.
  • Step 102 Downgrading and recovering remaining lost data according to the restored data of the target data storage node.
  • each data storage node may be divided into p strip units, where p ⁇ p ', p is a prime number That is, the prime number.
  • the data storage node disk number is 0 ' - 1, each disk is divided into p - 1 strips of the same size, the stripe number ranges from 0 - 2, and the stripe data of the first row is virtual zero padding. Does not exist on the storage node.
  • the data storage node can be viewed as a matrix D after partitioning, where D " can represent the i-th stripe unit data of the j-th data storage node, and ⁇ represents the i-th stripe unit of the horizontal check node.
  • the data, ⁇ represents the i-th stripe unit data of the diagonal check node, and represents the i-th stripe unit data of the inverse diagonal check node.
  • FIG. 1b to FIG. 1D are data recovery methods according to the first embodiment of the present invention.
  • the schematic diagram of the check node in the middle, the generation mode of the horizontal check node P (parity I) can be XORed according to the same type of pattern, see Figure lb; Diagonal check node Q with a slope of "1" (parity II)
  • the generation method may be that the data of the same type of graphic representation in the data storage node is XORed with the value of the adjustment factor (the adjuster) of the last row, and the adjustment factor is not saved, see Figure lc;
  • the inverse diagonal check node R (parity III) is generated in a similar manner to the diagonal check node. Only the position of the same type of graph in the data storage node is reversed. See Figure ld.
  • check nodes with other slopes can be used, for example: check nodes with a slope of "2", check nodes with a diagonal of "_2", and so on.
  • the three-node data of the distributed storage system may specifically include the following: Case 1: In the case that the lost three-node data includes data of three data storage nodes, the target data storage The node is the data storage node with the lost disk number in the middle.
  • the target data storage node that is restored first may be a data storage node (referred to as an intermediate node) with the lost disk number in the middle.
  • an intermediate node For example: You can calculate the difference between the disk number of the data storage node with the largest disk number lost (the largest node) and the intermediate node, and the disk number difference between the data storage node with the smallest disk number (the minimum node) and the intermediate node.
  • the minimum number of XORs and the step size, the data of the missing maximum node and the minimum node are converted into the exclusive OR of the two stripe unit data of the lost intermediate node, thereby obtaining the P-OR XOR sum, and then according to the virtual complement of the intermediate node Zero stripe unit data, gradually obtain data of all stripe units of the intermediate node, and further downgrade and recover the remaining two lost node data.
  • Case 2 In a case where the lost three node data includes data of a horizontal check node and two data storage nodes, the target data storage node is any one of the two data storage nodes that are lost.
  • the data of the lost data storage node may be restored, provided to the user, and then the data of the lost horizontal check node is restored.
  • the XOR of the adjustment factors of the diagonal check node and the inverse diagonal check node may be XORed by all the stripe unit data of the two check nodes.
  • the adjustment factor of the diagonal check node of the common stripe unit and the adjustment factor of the inverse diagonal check node may convert the stripe unit data of the two lost data storage nodes into the same lost data storage node.
  • the two band unit data are XORed.
  • the data recovery using the check data can ensure the effective utilization of the storage space of the distributed system to meet the performance requirements of the distributed storage system; determine the target data storage node that is first restored according to the symmetry of the lost data, and according to the school The data recovery and the data that is not lost recover the lost three node data, which can improve the data recovery performance in the case where the distributed storage system loses three nodes of data.
  • the data is distributed in different data storage nodes, the data is kept secret, and the user's data is more secure.
  • the algorithm In the case of losing the data of the three data storage nodes, first recovering the data storage node whose lost disk number is in the middle, the algorithm is simple and easy to encode; in the case of losing the data of the horizontal check node and the two data storage nodes, First restore a data storage section Point, not only the algorithm is simple, easy to code implementation, but also can restore the restored data storage node to the user, restore the data of the horizontal check node in parallel, reduce the waiting time of the user, and improve the user's physical examination.
  • step 101 is based on The data of the lost check node and the data storage node recovers the data of the target data storage node in the three node data, which may specifically include the following steps:
  • Step 201 Generate a diagonal adjustment factor and an inverse diagonal adjustment factor according to the verification data, where the verification data includes data of a horizontal check node, a diagonal check node, and an inverse diagonal check node.
  • a lost data storage node is set, where 0 ⁇ r ⁇ s ⁇ t ⁇ p' ⁇ ; 7, the main idea is to restore the intermediate node first by cross-combining.
  • the adjuster (adjuster) can be generated using equations (1.1) and (1.2).
  • the adjustment factor of the diagonal check node can be referred to as the diagonal adjustment factor, see formula (1.1); the adjustment factor of the inverse diagonal check node can be referred to as the inverse diagonal adjustment factor, see formula (1.2).
  • the diagonal adjustment factor is the inverse diagonal adjustment factor
  • P t is the first strip unit data of the horizontal check node
  • ⁇ is the Article data unit with corner check nodes
  • Q ⁇ i ⁇ P -2 is the number p is greater than or equal to a data storage node 'The prime number.
  • Step 202 Generate first level check data, first diagonal check data, and first inverse diagonal check data according to data of the data storage node that is not lost, the diagonal adjustment factor, and the level adjustment factor. .
  • new verification data can be generated using equations (L 3) to (1.5).
  • the first level check data is generated by using formula (1.3);
  • the first diagonal check data is generated by using formula (1.4);
  • the first inverse diagonal check data is generated by using formula (1.4);
  • Step 203 According to the diagonal adjustment factor, the inverse diagonal adjustment factor, the first horizontal parity data, the first diagonal parity data, and the first inverse diagonal parity data, The data of the data storage node whose lost disk number is in the middle is output.
  • FIG. 2b is a schematic diagram of a cross-over operation in the data offloading method according to Embodiment 2 of the present invention.
  • the cross-hatched line includes an odd-numbered stripe unit including a triangle and an even-numbered stripe unit.
  • the data of the stripe unit of the data storage node has symmetry, and the intersecting nodes including the square can be eliminated during the exclusive OR operation, for example: after /.
  • the XOR operation of the stripe unit data of all the data storage nodes on the two lines is equivalent to eliminating Z. . Therefore, the formula for a data storage node with the missing disk number in the middle of the missing data can be established by the crossover operation a.6):
  • the formula of the data storage node with the lost disc number in the middle may be eliminated, and then all The stripe unit data of the lost data storage node is converted into an exclusive OR of the two stripe unit data of the data storage node with the lost disc number in the middle, and the data of the data storage node with the lost disc number in the middle is obtained.
  • the specific ways to eliminate the processing can include:
  • the common cross operation may include: formulating the data storage node with the missing disk number in the middle by using the step size 6 to obtain the formula of the data storage node with the lost disk number in the middle (1.7) ):
  • FIG. 2c is a step-by-step variation in the data shunting method according to the second embodiment of the present invention.
  • the XOR is summed according to the step 2, and the cross line is passed through the even number of strip units / 2 , Z 2 and Z 2 are eliminated, and an exclusive OR sum of / 2 and Z 2 including only two variables can be obtained.
  • the XOR between the paired stripe unit data of the data storage node with the disk number "2" can be similarly obtained.
  • the formula of the circulatory equation group having only one variable sequentially solves other formulas of the circulatory equation group according to the solution result, and obtains each data of the data storage node whose lost disc number is in the middle.
  • FIG. 2e is a schematic structural diagram of data storage in a data recovery method according to Embodiment 2 of the present invention.
  • five disk storage node disk numbers are “( ⁇ 4” as an example, and three check nodes P and Q are generated.
  • R a total of 8 nodes, the size of each node is divided into 4 strips, the 5th strip (black solid circle of line number 4 in the figure) is a virtual zero-padded strip, according to the five data storage
  • the disk number of the horizontal check node generated by the node can be "5", the disk number of the diagonal check node can be "6", and the disk number of the reverse diagonal check node can be "7".
  • Horizontal check node P For the generation method of parity I), see Figure lb.
  • R parity III
  • the specific process of restoring the data of the three data storage nodes may include:
  • Step 201 is performed to calculate an adjustment factor of the diagonal check node Q and the inverse diagonal check node R. According to the formula (1.1) and the formula (1.2), the formula (1.1.0) and the formula (1.2.0) can be obtained:
  • Step 202 Calculate the check data of the horizontal check node P, the diagonal check node Q, and the inverse diagonal check node R, and obtain the formula of the first horizontal check data according to the formula (1.3) Group (L3.0); Substituting the formula (1.1.0) into the formula (L4) can obtain the formula group (1.4.0) of the first diagonal check data, and substitute the formula (1.2.0) into the formula (1.5). The formula set (1.5.0) of the first inverse diagonal check data is obtained.
  • D 02 then calculate D 12 in the second formula according to D Q2 , thereby calculating the data of the data storage node with the disk number "2" one by one, and then downgrading to the form of EVEN0DD and the recovery disk number is "0", "3" data storage node data.
  • the data recovery using the check data can ensure the effective utilization of the storage space of the distributed system to meet the performance requirements of the distributed storage system; determine the target data storage node that is first restored according to the symmetry of the lost data, and according to the school Data recovery and unrecovered data recovery of the lost three node data can improve the data recovery performance in the case where the distributed storage system loses three nodes of data; in the case of losing data of three data storage nodes, first Restore the data storage node whose lost disk number is in the middle, and the number of cyclic XORs can be obtained by simple mathematical formula. The number of XORs is small when recovering, which further saves the required cloud storage processing memory.
  • the algorithm is simple and easy to encode. achieve.
  • Embodiment 3 3a is a flowchart of a data offloading method according to a third embodiment of the present invention.
  • the same steps as those in FIG. 3a have the same meanings, and a detailed description of these components is omitted for the sake of brevity.
  • the difference from the above embodiment is: in the case of the second embodiment described above, in the case where the lost three node data includes the data of the horizontal check node and the two data storage nodes. And recovering the data of the target data storage node in the three node data according to the data of the check node and the data storage node that are not lost, and the method may include the following steps:
  • Step 301 Generate, according to data of the diagonal check node and the inverse diagonal check node, in case that the lost three node data includes data of a horizontal check node and two data storage nodes The exclusive OR of the diagonal adjustment factor and the inverse diagonal adjustment factor.
  • the first stripe unit data of the check node is the first stripe unit data of the inverse diagonal check node, 0 ⁇ i ⁇ p-2, which is the disc number of the lost horizontal check data, and is greater than Or a prime number equal to the number of data storage nodes.
  • Step 302 Generate second diagonal check data and second inverse diagonal check data according to data of the data storage node that is not lost.
  • the new check data may be generated by using the formula (2.2) and the formula (2.3), wherein the second diagonal check data is generated by using the formula (2.2); and the formula is generated by using the formula (2.3) Two inverse diagonal check data;
  • ⁇ ⁇ @( @ D ) ( 2. 3)
  • ⁇ is the second diagonal check data
  • Z is the first of the column data storage nodes
  • Step 303 Determine, according to the XOR sum of the diagonal adjustment factor and the inverse diagonal adjustment factor, the second diagonal check data, and the second inverse diagonal check data, use a symmetric elimination operation to find the lost location. Describe two data storage nodes Meaning one data.
  • Method 1 First recover the data lost in the data storage node in column S.
  • Method 2 First recover the data lost in the r column data storage node.
  • FIG. 3b is a schematic diagram of symmetric symmetry in the data offloading method according to the third embodiment of the present invention.
  • the stripe unit data is labeled as "4".
  • the row of the virtual row is a virtual zero padding.
  • the data storage node and the horizontal check node P of the disk number are determined to be:
  • Step 301 Calculate the XOR of the adjustment factors of the diagonal check node Q and the inverse diagonal check node R. According to the formula (2.1), the formula (2.1.0) can be obtained:
  • Step 302 is executed to calculate the verification data of the diagonal check node Q and the inverse diagonal check node R.
  • the formula group of the second diagonal check data (2.2.0) can be obtained; according to the formula ( 2.3)
  • the formula set (2.3.0) of the first inverse diagonal check data can be obtained.
  • R 0 D 0 , a ® D 22 @R 0
  • R 2 A, 0 ®D l @R 2 (2.3.0)
  • R 3 A, ,®D o @D 2 @R 3
  • ® D 3 performs step 303, see Fig. 3b, and the equation (2.4) is subjected to the elimination processing to obtain the formula (2.5), and the formula (2.5) can obtain the system of cyclic equations (2.5.0).
  • the formula (2.5) can obtain the system of cyclic equations (2.5.0).
  • XORing the points where the two lines intersect can eliminate D 31 and get the exclusive OR of D 13 and I ⁇ , see the second formula of the following cyclic equations (2.5.0). All formulas for the system of cyclic equations (2.5.0) can be obtained.
  • the D 43 strip unit data Since the D 43 strip unit data is zero, it can be calculated one by one! 3 , ⁇ 3 , ⁇ ) 2 , 3 , ⁇ ) 3 , 3 with unit data , recover the data of the data storage node with the disk number "3", and further restore the data of the data storage node with the disk number "1", Finally, the data of the level check node is restored.
  • the data of the data storage node with the disk number "1" can be restored first, and the data of the data storage node with the disk number "3" is restored, and finally the data of the horizontal check node is restored.
  • the data recovery using the check data can ensure the effective utilization of the storage space of the distributed system to meet the performance requirements of the distributed storage system; determine the target data storage node that is first restored according to the symmetry of the lost data, and according to the school Data recovery and unrecovered data recovery of the lost three node data can improve data recovery performance in the case where the distributed storage system loses three nodes of data; data in the lost level check node and two data storage nodes In the case of the first, a data storage node is first restored, which is not only simple in algorithm, but also easy to encode. The recovery performance is higher than that of the first recovery level check node, and the restored data storage node can be sent to the user first, and the horizontal check node is restored in parallel. Data, reducing user waiting time and improving user satisfaction.
  • Embodiment 4 Embodiment 4
  • the data recovery device may include:
  • the target recovery unit 41 is configured to recover data of the target data storage node in the three node data according to the data of the check node and the data storage node that are not lost, if the distributed storage system loses three node data, The target data storage node is determined according to the symmetry of the lost data;
  • the degradation recovery unit 43 is configured to downgrade and recover the remaining lost data according to the restored data of the target data storage node.
  • a plurality of data storage nodes and check nodes may be included in the distributed system or RAID, wherein each data storage node may be divided into a plurality of stripe units.
  • the number of the stripe units is generally greater than or equal to the number of data storage nodes.
  • the check node may include a horizontal check node, a diagonal check node, and an inverse diagonal check node, or may also include a check node with a slope of "2" and a diagonal of "-2". Check nodes, etc.
  • the data recovery using the check data can ensure the effective utilization of the storage space of the distributed system to meet the performance requirements of the distributed storage system; determine the target data storage node that is first restored according to the symmetry of the lost data, and according to the school The data recovery and the data that is not lost recover the lost three node data, which can improve the data recovery performance in the case where the distributed storage system loses three nodes of data.
  • FIG. 5 is a structural block diagram of a data recovery device according to Embodiment 5 of the present invention.
  • the same components of FIG. 5 and FIG. 4 have the same meanings, and the difference from the previous embodiment is:
  • the target data storage node is a data storage node whose lost disk number is in the middle; the target of the data recovery device
  • the recovery unit 41 can include:
  • the adjustment factor generating module 51 is configured to generate a diagonal adjustment factor and an inverse diagonal adjustment factor according to the verification data, where the verification data includes data of the horizontal check node, the diagonal check node, and the inverse diagonal check node ;
  • the first check data generating module 53 is configured to generate first level check data, first diagonal check data, and according to data of the data storage node that is not lost, the diagonal adjustment factor, and the level adjustment factor.
  • a cross operation module 55 configured to optimize according to the diagonal adjustment factor, the inverse diagonal adjustment factor, the first horizontal parity data, the first diagonal parity data, and the first inverse diagonal parity data Cross calculation
  • the lost disk number is in the middle of the data storage node data.
  • the adjustment factor generating module 51 may be specifically configured to:
  • the diagonal adjustment factor is the inverse diagonal adjustment factor
  • ⁇ is the first stripe unit data of the horizontal check node
  • ⁇ is the first strip of the diagonal check node
  • the unit data is the first stripe unit data of the inverse diagonal check node, 0 ⁇ i ⁇ p-2, which is a prime number greater than or equal to the number of data storage nodes.
  • the cross operation module 55 can be specifically used to:
  • the cross operation module 55 may specifically be used to:
  • the step offDis is used for k-th order XOR summation, and the data storage node formula in which the lost disk number is in the middle is obtained.
  • system of cyclic equations obtained according to the formula of the intermediate data storage node is used to represent an exclusive OR of two data of the intermediate data storage node, and each formula of the system of cyclic equations has at most two Determining the data of the data storage node with the lost disk number in the middle, including:
  • the data recovery using the check data can ensure the effective utilization of the storage space of the distributed system to meet the performance requirements of the distributed storage system; determine the target data storage node that is first restored according to the symmetry of the lost data, and according to the school Data recovery and unrecovered data recovery of the lost three node data can improve the data recovery performance in the case where the distributed storage system loses three nodes of data; in the case of losing data of three data storage nodes, first Restore the data storage node whose lost disk number is in the middle, and the number of cyclic XORs can be obtained by simple mathematical formula. The number of XORs is small when recovering, which further saves the required cloud storage processing memory.
  • the algorithm is simple and easy to encode. achieve.
  • FIG. 6 is a structural block diagram of a data recovery device according to Embodiment 6 of the present invention.
  • the same components of FIG. 6 and FIG. 4 have the same meanings, and the difference from the previous embodiment is:
  • the target recovery unit 41 of the data recovery device may include:
  • a factor exclusive OR sum module 57 configured to generate an exclusive OR of a diagonal adjustment factor and an inverse diagonal adjustment factor according to the data of the diagonal check node and the inverse diagonal check node;
  • a second check data generating module 58 configured to generate a second diagonal according to data of the data storage node that is not lost Check data and second inverse diagonal check data;
  • a symmetric elimination operation module 59 configured to use symmetric cancellation according to the exclusive OR sum of the diagonal adjustment factor and the inverse diagonal adjustment factor, the second diagonal verification data, and the second inverse diagonal verification data The calculation calculates the data of any one of the two data storage nodes that are lost.
  • the disk number of the lost horizontal parity data is a prime number greater than or equal to the number of data storage nodes.
  • ⁇ is the second diagonal check data
  • Z is the first stripe unit data of the column data storage node
  • r, s are lost data storage
  • the disk number of the node, 0 ⁇ j ⁇ p'-l, 0 ⁇ r ⁇ s ⁇ p' ⁇ p, ⁇ > p is the modulo operation.
  • the symmetric elimination operation module 59 can be specifically used to:
  • the stripe unit data of the two lost data storage nodes are converted into a data storage node by the elimination processing
  • the XOR sum of the two stripe unit data, the formula D u , r ®D ⁇ u+2 s — r>p , r Q ⁇ ' u+2s _ r>p ®R ®Q S ®R S '
  • the virtual zero-padded stripe unit data D p 0, the data lost by the r-th column data storage node is obtained.
  • the data recovery using the check data can ensure the effective utilization of the storage space of the distributed system.
  • the data recovery performance in the case where the system loses three nodes of data; in the case of losing the data of the horizontal check node and the two data storage nodes, first recovering a data storage node, which is not only simple in algorithm, easy to encode, and recovery performance ratio
  • the level of the check node is restored first, and the restored data storage node can be sent to the user first, and the data of the level check node is restored in parallel to reduce the waiting time of the user and improve the user satisfaction.
  • Figure 7 is a block diagram showing the structure of a data recovery device according to a seventh embodiment of the present invention.
  • the data recovery device may be a host server with computing power, a personal computer PC, or a portable computer or terminal that can be carried.
  • the specific embodiments of the present invention do not limit the specific implementation of the computing node.
  • the data recovery device includes a processor 71, a communications interface 72, a memory array 73, and a bus 74.
  • the processor 71, the communication interface 72, and the memory 73 complete communication with each other via the bus 74.
  • the communication interface 72 is for communicating with a network element, wherein the network element includes, for example, a virtual machine management center, shared storage, and the like.
  • the processor 71 is for executing a program.
  • Processor 71 may be a central processing unit CPU, or an Application Specific Integrated Circuit (ASIC), or one or more integrated circuits configured to implement embodiments of the present invention.
  • ASIC Application Specific Integrated Circuit
  • the memory 73 is used to store files.
  • the memory 73 may include a high speed RAM memory and may also include a non-volatile memory such as at least one disk memory.
  • Memory 73 can also be a memory array.
  • the memory 73 may also be partitioned, and the blocks may be combined into a virtual volume according to certain rules.
  • the above program may be program code including computer operating instructions. This program can be used to:
  • the data of the target data storage node in the three node data is restored according to the data of the non-lost check node and the data storage node, and the target data storage node is based on The symmetry of the lost data is determined;
  • the target data storage node is a data storage node whose lost disk number is in the middle;
  • Data of the check node and the data storage node that are not lost, and recover data of the target data storage node in the three node data including: Generating a diagonal adjustment factor and an inverse diagonal adjustment factor according to the verification data, where the verification data includes data of a horizontal check node, a diagonal check node, and an inverse diagonal check node;
  • the generating a diagonal adjustment factor and an inverse diagonal adjustment factor according to the verification data including:
  • the diagonal adjustment factor is generated using the formula ⁇ '; using the formula s _ ⁇ . i generating the inverse diagonal adjustment factor;
  • ft is the diagonal adjustment factor
  • inverse diagonal adjustment factor ⁇ is the first stripe unit data of the horizontal check node
  • ⁇ is the first strip of the diagonal check node
  • the band unit data is the first stripe unit data of the inverse diagonal check node, 0 ⁇ i ⁇ p-2, which is a prime number greater than or equal to the number of data storage nodes.
  • the generating, according to the data of the data storage node that is not lost, the diagonal adjustment factor, and the level adjustment factor, generating first level check data, first diagonal check data, and The first inverse diagonal check data includes: using the formula ⁇ ( ⁇ generating the first level check data;
  • the first diagonal check data is the first diagonal check data
  • the first reverse diagonal check data is a data storage node of the first column
  • the determining according to the diagonal adjustment factor, the inverse diagonal adjustment factor, the first horizontal verification data, the first diagonal verification data, and the first inverse diagonal verification data And obtaining, by using a crossover operation, data of the data storage node whose lost disk number is in the middle, including:
  • the stripe unit data of the storage node is converted into an exclusive OR of the two stripe unit data of the data storage node whose lost disc number is in the middle, and the data of the data storage node whose lost disc number is in the middle is obtained.
  • the step offDis is used for k-th order XOR summation, and the data storage node formula in which the lost disk number is in the middle is obtained.
  • system of cyclic equations obtained according to the formula of the intermediate data storage node is used to represent an exclusive OR of two data of the intermediate data storage node, and each formula of the system of cyclic equations has at most two Determining the data of the data storage node with the lost disk number in the middle, including:
  • the target data storage node is the two data stores that are lost. Node Any one of the data of the target data storage node in the three node data according to the data of the non-lost check node and the data storage node, including:
  • the generating an exclusive-OR sum of a diagonal adjustment factor and an inverse diagonal adjustment factor according to the data of the diagonal check node and the inverse diagonal check node including:
  • the formula ⁇ ( ⁇ 2 ⁇ )®( ⁇ 2 ), generates an exclusive OR of the diagonal adjustment factor and the inverse diagonal adjustment factor, wherein, for the diagonal adjustment factor, is the inverse diagonal adjustment factor, ⁇
  • the first stripe unit data of the diagonal check node is the first stripe unit data of the inverse diagonal check node, 0 ⁇ i ⁇ p-2, which is the missing horizontal check data.
  • the disk number and is a prime number greater than or equal to the number of data storage nodes.
  • the disk number is the number of data storage nodes, 0 ⁇ ⁇ ⁇ ⁇ '-1, 0 ⁇ r ⁇ s ⁇ p' ⁇ p, ⁇ > p is the modulo operation.
  • the symmetrical according to the XOR sum of the diagonal adjustment factor and the inverse diagonal adjustment factor, the second diagonal check data, and the second inverse diagonal check data calculates the data of the one data storage node, and includes:
  • the data recovery using the check data can ensure the effective utilization of the storage space of the distributed system to meet the performance requirements of the distributed storage system; determine the target data storage node that is first restored according to the symmetry of the lost data, and according to the school The data recovery and the data that is not lost recover the lost three node data, which can improve the data recovery performance in the case where the distributed storage system loses three nodes of data.
  • FIG. 8 is a structural block diagram of a distributed storage system according to Embodiment 8 of the present invention. As shown in FIG. 8, the distributed storage system includes: a plurality of data storage nodes 81, a plurality of check nodes 83, and a data recovery device 85;
  • the data recovery device 85 uses the data recovery device of any one of the embodiments of the present invention.
  • the data recovery using the check data can ensure the effective utilization of the storage space of the distributed system to meet the performance requirements of the distributed storage system; determine the target data storage node that is first restored according to the symmetry of the lost data, and according to the school.
  • the data recovery and the data that is not lost recover the lost three node data, which can improve the data recovery performance in the case where the distributed storage system loses three nodes of data.
  • the function is implemented in the form of computer software and sold or used as a stand-alone product, it may be considered to some extent that all or part of the technical solution of the present invention (for example, a part contributing to the prior art) is It is embodied in the form of computer software products.
  • the computer software product is typically stored in a computer readable storage medium and includes instructions for causing a computer device (which may be a personal computer, server, or network device, etc.) to perform all or part of the steps of the various embodiments of the present invention.
  • the aforementioned storage medium includes a USB flash drive and a mobile hard disk.
  • a medium that can store program code such as a disk, a Read-Only Memory (ROM), a Random Access Memory (RAM) disk, or an optical disk.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Databases & Information Systems (AREA)
  • Probability & Statistics with Applications (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Quality & Reliability (AREA)
  • Computing Systems (AREA)
  • Signal Processing For Digital Recording And Reproducing (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Error Detection And Correction (AREA)

Abstract

本发明涉及数据恢复方法、数据恢复设备和分布式存储系统，该方法包括：在分布式存储系统丢失三个节点数据的情况下，根据未丢失的校验节点和数据存储节点的数据，恢复所述三个节点数据中目标数据存储节点的数据，所述目标数据存储节点根据丢失数据的对称性确定；根据恢复后的所述目标数据存储节点的数据，降级恢复剩余的丢失数据。本发明实施例采用校验数据进行数据恢复可以保证分布式系统如云存储存储空间的有效利用率，以满足分布式存储系统的性能要求；根据丢失数据的对称性确定首先恢复的目标数据存储节点，并根据校验数据和未丢失的数据对丢失的三个节点数据进行恢复，可以提升分布式存储系统丢失三个节点数据的情况下的数据恢复性能。

Description

数据恢复方法、 数据恢复设备和分布式存储系统 本申请要求于 2013年 7月 26日提交中国专利局、 申请号为 201310320300. 3、发明 名称为 "数据恢复方法、 数据恢复设备和分布式存储系统" 的中国专利申请的优先权， 其全部内容通过弓 I用结合在本申请中。 技术领域 本发明涉及计算机技术领域， 尤其涉及一种数据恢复方法、 数据恢复设备和分布式 存储系统。 背景技术 随着云计算技术的普及， 云存储也越来越贴近人们的生活。 云存储的供应商也在逐 年增加， 目前业界的供应商数已达到了将近 200个。 数据可以被存放在远程的云存储系 统上， 因此可以极大的降低了对本地存储的需求。 但是云存储依然面临着诸多问题： 如何以最小的成本， 为用户数据提供最高的可靠性； 如何保证用户数据的安全性， 不被 窃取、 加密等。
为了保证用户数据的安全性， 可以将同一份数据复制多份副本（repl ication), 存 放在不同的存储节点上。 如果某一存储节点出错， 但只要还有一个存储节点存在， 用户 就可以获取这个数据。 例如： 做三个副本， 空间的浪费达到原始数据的 3倍。 对于云存 储供应商而言， 采用副本的存储空间浪费严重， 成本很高。
为了提升存储的空间利用率， 可以采用纠删码 （Erasure Code ) 替代副本， 纠删码 是一种被普遍采用的数据冗余纠错算法。其中，最著名的 Erasure Code是 Reed Solomon Code (里德所罗门码） 采用 GF矩阵和数据相乘， 可以得到了校验码。 但是， 对于计算 机 CPU ( Central Processing Unit , 中央处理器） 而言， 乘法的性能很低， 因此 Reed Solomon Code算法的性能较低。 此外， 目前的 Reed Solomon Code算法中数据的位宽最 大为 32位， 由于位宽越大性能越高， 对性能具有很大限制。
此夕卜， 早期 IBM提出的 EVEN0DD, 是针对 RAID ( redundant array of independent disks ,独立磁盘冗余阵列）系统的一种冗余度为 2 (具有两组校验数据）的算法。 cheng huang和 l ihao xu提出将其推广到冗余度为 3 (具有三组校验数据） 的 STAR算法 （添 加斜率为 -1的校验）。
在三个数据存储节点 （即三个数据磁盘） 丢失时， 采用 EVEN0DD与 STAR的恢复算 法复杂且编码实现难度大； 在两个数据存储节点和水平校验节点 （即两个数据磁盘、 水 平校验磁盘）丢失时， 需要先恢复水平校验节点的数据， 再恢复数据存储节点的原始数 据， 恢复性能较低， 而且算法不易于编码实现。 发明内容
有鉴于此，本发明要解决的技术问题是，现有分布式存储系统的数据恢复性能较低。 为了解决上述技术问题，根据本发明的一实施例，提供了一种数据恢复方法，包括： 在分布式存储系统丢失三个节点数据的情况下，根据未丢失的校验节点和数据存储 节点的数据， 恢复所述三个节点数据中目标数据存储节点的数据， 所述目标数据存储节 点根据丢失数据的对称性确定；
根据恢复后的所述目标数据存储节点的数据， 降级恢复剩余的丢失数据。
对于上述数据恢复方法， 在一种可能的实现方式中， 在丢失的所述三个节点数据包 括三个数据存储节点的数据的情况下，所述目标数据存储节点为丢失盘号处于中间的数 据存储节点； 所述根据未丢失的校验节点和数据存储节点的数据， 恢复所述三个节点数 据中目标数据存储节点的数据， 包括：
根据校验数据， 生成对角调节因子和逆对角调节因子， 所述校验数据包括水平校验 节点、 对角校验节点和逆对角校验节点的数据；
根据未丢失的数据存储节点的数据、 所述对角调节因子和所述水平调节因子， 生成 第一水平校验数据、 第一对角校验数据和第一逆对角校验数据；
根据所述对角调节因子、 逆对角调节因子、 所述第一水平校验数据、 第一对角校验 数据和第一逆对角校验数据，通过优化的十字交叉运算求出所述丢失盘号处于中间的数 据存储节点的数据。
对于上述数据恢复方法， 在一种可能的实现方式中， 所述根据校验数据， 生成对角 调节因子和逆对角调节因子， 包括：
0 =¾ · θβ·)
采用公式 ' 生成所述对角调节因子；
R = Θ (P. ® R )
采用公式 5 。、 ' '；生成所述逆对角调节因子；
其中， ft为所述对角调节因子， 为所述逆对角调节因子， ^为所述水平校验节 点的第 个条带单元数据， ρ,为所述对角校验节点的第 个条带单元数据， 为所述逆 对角校验节点的第 个条带单元数据， 0≤i≤p-2， p为大于或等于数据存储节点的个 数的素数。
对于上述数据恢复方法， 在一种可能的实现方式中， 所述根据未丢失的数据存储节 点的数据、 所述对角调节因子和所述水平调节因子， 生成第一水平校验数据、 第一对角 校验数据和第一逆对角校验数据， 包括： 采用公式 = ®( ), ,)生成所述第一水平校验数据； 采用公式 = a ® a ® ( ¾' D<t_]>p ) 生成所述第一对角校验数据； 采用公式 = ® ®( ¾1 Ζ)<,+ ί> ,) 生成所述第一逆对角校验数据； 其中， 为所述第一水平校验数据， 为所述第一对角校验数据， 为所述第一 逆对角校验数据， 为第 列数据存储节点的第 个条带单元的数据， r、 S、 t为丢失 的数据存储节点的盘号， 为数据存储节点的个数， 0≤J'≤P'-1 ， 0<r<s<t<p'<p , <>p为对 p进行取模运算。
对于上述数据恢复方法， 在一种可能的实现方式中， 所述根据所述对角调节因子、 逆对角调节因子、 所述第一水平校验数据、 第一对角校验数据和第一逆对角校验数据， 通过十字交叉运算求出所述丢失盘号处于中间的数据存储节点的数据， 包括：
通过十字交叉运算建立丢失数据的丢失盘号处于中间的数据存储节点的公式： k -Dds ® D © D ® D<d+a+b>p,s = P<d>p ® P ® R ® Q ； 其中， 0≤ί ≤ρ-1 ; s为所述丢失盘号处于中间的数据存储节点的盘号； a、 b为 丢失的三个数据存储节点之间的盘号差， a = S-r,b = t-s
根据丢失数据的数据存储节点的盘号差确定的移动的步长和循环异或求和次数，对 所述丢失盘号处于中间的数据存储节点的公式进行消元处理后，将所有丢失的数据存储 节点的条带单元数据转化为所述丢失盘号处于中间的数据存储节点的两个条带单元数 据的异或和， 求出所述丢失盘号处于中间的数据存储节点的数据。
对于上述数据恢复方法， 在一种可能的实现方式中， 所述对所述丢失盘号处于中间 的数据存储节点的公式进行消元处理后，将所有丢失的数据存储节点的条带单元数据转 化为所述丢失盘号处于中间的数据存储节点的两个条带单元数据的异或和， 包括： 对所述丢失盘号处于中间的数据存储节点的公式采用， 步长 offDis进行 k次异或求 和 ， 得 到 所 述 丢 失 盘 号 处 于 中 间 的 数 据 存 储 节 点 公 式 ® )<„+2minDis>P ,, , 若
Figure imgf000006_0001
k = m， 贝1 J min Dis - b, offDis - a , 否贝1 J min Dis - a, offDis - b , < + v x offDis >p =d， 0 < < p - \ ;
其中， 根据所述中间的数据存储节点的公式得到的循环方程组， 用于表示所述中间 的数据存储节点的两个数据的异或和， 所述循环方程组的每一个公式至多具有两个变 所述求出所述丢失盘号处于中间的数据存储节点的数据， 包括：
根据所述丢失盘号处于中间的数据存储节点的虚拟补零的条带单元数据 ^_1Λ = 0， 代入求解所述循环方程组中只具有一个变量的公式，根据求解结果依次求解所述循环方 程组的其他公式， 得到所述丢失盘号处于中间的数据存储节点的每个数据。
对于上述数据恢复方法， 在一种可能的实现方式中， 在丢失的所述三个节点数据包 括水平校验节点和两个数据存储节点的数据的情况下，所述目标数据存储节点为丢失的 所述两个数据存储节点的任意一个， 所述根据未丢失的校验节点和数据存储节点的数 据， 恢复所述三个节点数据中目标数据存储节点的数据， 包括：
根据所述对角校验节点和所述逆对角校验节点的数据， 生成对角调节因子和逆对角 调节因子的异或和；
根据未丢失的数据存储节点的数据， 生成第二对角校验数据和第二逆对角校验数 据；
根据所述对角调节因子和逆对角调节因子的异或和、所述第二对角校验数据和第二 逆对角校验数据，采用对称消元运算求出丢失的所述两个数据存储节点的任意一个的数 据。
对于上述数据恢复方法， 在一种可能的实现方式中， 所述根据所述对角校验节点和 所述逆对角校验节点的数据， 生成对角调节因子和逆对角调节因子的异或和， 包括： 采用公式 ρχ ® = (^2β.)®(^2 ）， 生成对角调节因子和逆对角调节因子的异或 和， 其中， 为所述对角调节因子， 为所述逆对角调节因子， ρ,为所述对角校验节 点的第 个条带单元数据， 为所述逆对角校验节点的第 个条带单元数据，
0 < i≤p-2 , p为丢失的水平校验数据的盘号， 且 p为大于或等于数据存储节点的个数 的素数。
对于上述数据恢复方法， 在一种可能的实现方式中， 所述根据未丢失的数据存储节 点的数据， 生成第二对角校验数据和第二逆对角校验数据， 包括： 采用公式 = Q Θ (θ' Ζ)<,—>^)生成所述第二对角校验数据； 采用公式 ^^,Φ^Φ1 ;) 生成所述第二逆对角校验数据； 其中， 为所述第二对角校验数据， 为所述第二逆对角校验数据， 为第 j'列 数据存储节点的第 个条带单元数据， r、 s为丢失的数据存储节点的盘号， 为数据 存储节点的个数， 0≤ ·≤ρ'-1， 0<r<s<p'<p, <>p为对 p进行取模运算。
对于上述数据恢复方法， 在一种可能的实现方式中， 所述根据所述对角调节因子和 逆对角调节因子的异或和、 所述第二对角校验数据和第二逆对角校验数据， 采用对称消 元运算求出所述一个数据存储节点的数据， 包括：
根据建立丢失数据公式 ， /^^^ ^^^^ ^^^ ， 经过 消元处理将丢失的两个数据存储节点的条带单元数据转化为一个数据存储节点的两个 条带单元数据的异或和， 得到公式 Du,s θζ)<Μ+2(ί— = G><u+S>p ® u+s—2r>p㊉ a㊉^， 根 据虚拟补零的条带单元数据 ^— 1Λ =0， 求出第 s列数据存储节点丢失的数据； 或
根据建立丢失数据公式/ ^ΘΖ)<Μ+2(ί— ^®ft® = M ， 经过 消元处理将丢失的两个数据存储节点的条带单元数据转化为一个数据存储节点的两个 条带单元数据的异或和， 得到公式 Du,r®D<u ,r = G><u+2s_r>p ®R ® ^， 根 据虚拟补零的条带单元数据 Ζ^ =0， 求出第 r列数据存储节点丢失的数据。
为了解决上述技术问题， 根据本发明的另一实施例， 提供了一种数据恢复设备， 包 括- 目标恢复单元， 用于在分布式存储系统丢失三个节点数据的情况下， 根据未丢失的 校验节点和数据存储节点的数据， 恢复所述三个节点数据中目标数据存储节点的数据， 所述目标数据存储节点根据丢失数据的对称性确定；
降级恢复单元， 用于根据恢复后的所述目标数据存储节点的数据， 降级恢复剩余的 丢失数据。
对于上述数据恢复设备， 在一种可能的实现方式中， 在丢失的所述三个节点数据包 括三个数据存储节点的数据的情况下，所述目标数据存储节点为丢失盘号处于中间的数 据存储节点； 所述目标恢复单元包括：
调节因子生成模块， 用于根据校验数据， 生成对角调节因子和逆对角调节因子， 所 述校验数据包括水平校验节点、 对角校验节点和逆对角校验节点的数据；
第一校验数据生成模块， 用于根据未丢失的数据存储节点的数据、 所述对角调节因 子和所述水平调节因子， 生成第一水平校验数据、 第一对角校验数据和第一逆对角校验 数据；
十字交叉运算模块， 用于根据所述对角调节因子、 逆对角调节因子、 所述第一水平 校验数据、 第一对角校验数据和第一逆对角校验数据， 通过优化的十字交叉运算求出所 述丢失盘号处于中间的数据存储节点的数据。
对于上述数据恢复设备， 在一种可能的实现方式中， 所述调节因子生成模块具体用 于： 采用公式 ^ ' 生成所述对角调节因子；
R
采用公式 s - (P. ®
« Θ R )
·、 ' ' 生成所述逆对角调节因子；
其中， 为所述对角调节因子， 为所述逆对角调节因子， 为所述水平校验节 点的第 个条带单元数据， β为所述对角校验节点的第 个条带单元数据， 为所述逆 对角校验节点的第 个条带单元数据， Q≤i≤p-2， p为大于或等于数据存储节点的个 数的素数。
对于上述数据恢复设备， 在一种可能的实现方式中， 所述第一校验数据生成模块具 体用于- 采用公式 = φ ( A , )生成所述第一水平校验数据；
=0 " 采用公式 = ¾ Φ β Θ ( ¾' D<t_j>p j ) 生成所述第一对角校验数据； 生成所述第一逆对角校验数据；
Figure imgf000008_0001
其中， 为所述第一水平校验数据， 为所述第一对角校验数据， 为所述第一 逆对角校验数据， 为第 列数据存储节点的第 个条带单元的数据， r、 S、 ί为丢失 的数据存储节点的盘号， 为数据存储节点的个数， 0≤j'≤p'-l ， 0<r<s<t<p'<p , <>p为对 p进行取模运算。
对于上述数据恢复设备， 在一种可能的实现方式中， 所述十字交叉运算模块具体用 于：
通过十字交叉运算建立丢失数据的丢失盘号处于中间的数据存储节点的公式- -Dd,s Φ D<d+a〉 Φ D<d+b>^^ Θ D<d+a+b〉 = P<d〉p ® P ® Q 其中， 0≤ί ≤ρ-1 ; s为所述丢失盘号处于中间的数据存储节点的盘号； 。、 6为 丢失的三个数据存储节点之间的盘号差， a = S-r,b = t-S;
根据丢失数据的数据存储节点的盘号差确定的移动的步长和循环异或求和次数，对 所述丢失盘号处于中间的数据存储节点的公式进行消元处理后，将所有丢失的数据存储 节点的条带单元数据转化为所述丢失盘号处于中间的数据存储节点的两个条带单元数 据的异或和， 求出所述丢失盘号处于中间的数据存储节点的数据。
对于上述数据恢复设备， 在一种可能的实现方式中， 所述十字交叉运算模块具体还 用于- 对所述丢失盘号处于中间的数据存储节点的公式采用， 步长 offDis进行 k次异或求 和 ， 得 到 所 述 丢 盘 号 处 于 中 间 的 数 据 存 储 节 点 公 式
® )<„+2minDis>P,, &k , 若
Figure imgf000009_0001
k = m， 贝1 J min Dis - b, offDis - a , 否贝1 J min Dis - a, offDis - b , < + vx offDis >p =d， 0<u< p-\;
其中， 根据所述中间的数据存储节点的公式得到的循环方程组， 用于表示所述中间 的数据存储节点的两个数据的异或和， 所述循环方程组的每一个公式至多具有两个变 所述求出所述丢失盘号处于中间的数据存储节点的数据， 包括：
根据所述丢失盘号处于中间的数据存储节点的虚拟补零的条带单元数据 ^_1Λ =0， 代入求解所述循环方程组中只具有一个变量的公式，根据求解结果依次求解所述循环方 程组的其他公式， 得到所述丢失盘号处于中间的数据存储节点的每个数据。
对于上述数据恢复设备， 在一种可能的实现方式中， 在丢失的所述三个节点数据包 括水平校验节点和两个数据存储节点的数据的情况下， 所述目标恢复单元包括：
因子异或和模块， 用于根据所述对角校验节点和所述逆对角校验节点的数据， 生成 对角调节因子和逆对角调节因子的异或和；
第二校验数据生成模块， 用于根据未丢失的数据存储节点的数据， 生成第二对角校 验数据和第二逆对角校验数据；
对称消元运算模块， 用于根据所述对角调节因子和逆对角调节因子的异或和、 所述 第二对角校验数据和第二逆对角校验数据，采用对称消元运算求出丢失的所述两个数据 存储节点的任意一个的数据。
对于上述数据恢复设备，在一种可能的实现方式中，所述因子异或和模块具体用于: 采用公式 ^ = (^2ρ,.)®(^2 ）， 生成对角调节因子和逆对角调节因子的异或 和， 其中， 为所述对角调节因子， 为所述逆对角调节因子， β为所述对角校验节 点的第 个条带单元数据， 为所述逆对角校验节点的第 个条带单元数据， Q≤i≤p-2， p为丢失的水平校验数据的盘号， 且 p为大于或等于数据存储节点的个数 的素数。
对于上述数据恢复设备， 在一种可能的实现方式中， 所述第二校验数据生成模块具 体用于- 采用公式 Q;= Q Θ (¾' /)<,_ >^)生成所述第二对角校验数据； 采用公式 ^^,Φ^Φ1 Ζ)<,+ ,> ;) 生成所述第二逆对角校验数据； 其中， 为所述第二对角校验数据， 为所述第二逆对角校验数据， 为第 j'列 数据存储节点的第 个条带单元数据， r、 s为丢失的数据存储节点的盘号， 0≤ ≤p'-1， 0≤r<s<p'≤p, <>p为对 p进行取模运算。
对于上述数据恢复设备， 在一种可能的实现方式中， 所述对称消元运算模块具体用 于：
根据建立丢失数据公式 ， /^^^ ^^^^ ^^^ ， 经过 消元处理将丢失的两个数据存储节点的条带单元数据转化为一个数据存储节点的两个 条带单元数据的异或和， 得到公式 Du,s θζ)<Μ+2(ί— = G><u+S>p ® ㊉ a㊉^， 根 据虚拟补零的条带单元数据 ^— 1Λ =0， 求出第 s列数据存储节点丢失的数据； 或 根据建立丢失数据公式 Du,r Θ D<u+2 s ,r θ ¾ Θ Ws = G ㊉ ， 经过消 元处理将丢失的两个数据存储节点的条带单元数据转化为一个数据存储节点的两个条 带单元数据的异或和， 得到公式 Du,r ® D<u ,r = G><u+2s_r>p ® R ® ® ， 根 据虚拟补零的条带单元数据 Ζ^ = 0， 求出第 r列数据存储节点丢失的数据。
为了解决上述技术问题， 根据本发明的另一实施例， 提供了一种分布式存储系统， 包括： 多个数据存储节点、 多个校验节点和数据恢复设备；
所述数据恢复设备采用本发明实施例中任意一种结构的数据恢复设备。
本发明实施例采用校验数据进行数据恢复可以保证分布式系统如云存储存储空间 的有效利用率， 以满足分布式存储系统的性能要求； 根据丢失数据的对称性确定首先恢 复的目标数据存储节点， 并根据校验数据和未丢失的数据对丢失的三个节点数据进行恢 复， 可以提升分布式存储系统丢失三个节点数据的情况下的数据恢复性能。
根据下面参考附图对示例性实施例的详细说明，本发明的其它特征及方面将变得清 楚。 附图说明 包含在说明书中并且构成说明书的一部分的附图与说明书一起示出了本发明的示 例性实施例、 特征和方面， 并且用于解释本发明的原理。
图 la为本发明实施例一的数据恢复方法的流程图；
图 11T图 Id为本发明实施例一的数据恢复方法中校验节点的示意图；
图 2a为本发明实施例二的数据分流方法的流程图；
图 2b为本发明实施例二的数据分流方法中的十字交叉运算的示意图；
图 2c为本发明实施例二的数据分流方法中的按步长进行循环异或求和的示意图； 图 2d为本发明实施例二的数据分流方法中的按优化步长进行循环异或求和的示意 图；
图 2e为本发明实施例二的数据恢复方法中数据存储的结构示意图；
图 3a为本发明实施例三的数据分流方法的流程图；
图 3b为本发明实施例三的数据分流方法中对称消元的示意图；
图 4为本发明实施例四的数据恢复设备的结构框图；
图 5为本发明实施例五的数据恢复设备的结构框图；
图 6为本发明实施例六的数据恢复设备的结构框图；
图 7为本发明的实施例七的数据恢复设备的结构框图； 图 8为本发明的实施例八的分布式存储系统的结构框图。 具体实施方式
以下将参考附图详细说明本发明的各种示例性实施例、 特征和方面。 附图中相同的 附图标记表示功能相同或相似的元件。 尽管在附图中示出了实施例的各种方面， 但是除 非特别指出， 不必按比例绘制附图。
在这里专用的词 "示例性"意为 "用作例子、 实施例或说明性" 。 这里作为 "示例 性"所说明的任何实施例不必解释为优于或好于其它实施例。
另外， 为了更好的说明本发明， 在下文的具体实施方式中给出了众多的具体细节。 本领域技术人员应当理解， 没有这些具体细节， 本发明同样可以实施。 在另外一些实例 中， 对于大家熟知的方法、手段、元件和电路未作详细描述， 以便于凸显本发明的主旨。
实施例一
图 la为本发明实施例一的数据恢复方法的流程图， 如图 la所示， 该数据恢复方法包 括- 步骤 101、 在分布式存储系统丢失三个节点数据的情况下， 根据未丢失的校验节点 和数据存储节点的数据， 恢复所述三个节点数据中目标数据存储节点的数据， 所述目标 数据存储节点根据丢失数据的对称性确定。
步骤 102、 根据恢复后的所述目标数据存储节点的数据， 降级恢复剩余的丢失数据。 优选地， 如果分布式系统或 RAID中具有的数据存储节点（数据磁盘）个数为 p '， 可 以将每个数据存储节点划分为 p个条带单元， 其中， p≥p '， p为素数即质数。 此外， 分布式系统或 RAID中可以具有 3个校验节点， 因此总节点个数为; 7 '+3个。 数据存储节点 盘号为 0 ' - 1，每个盘分为 p - 1个同等大小的条带，条带编号 的取值范围为 0 - 2， 第 行的条带数据为虚拟补零， 在存储节点上不存在。 从数学角度上， 数据存储节点 分块后可以看为一个矩阵 D，其中 D "可以表示第 j个数据存储节点第 i个条带单元数据， ^表示水平校验节点的第 i个条带单元数据， ρ,表示对角校验节点的第 i个条带单元数 据， 表示逆对角校验节点的第 i个条带单元数据。 图 lb〜图 Id为本发明实施例一的数据 恢复方法中校验节点的示意图， 水平校验节点 P (parity I ) 的生成方式可以按照同类 型的图案进行异或得到， 参见图 lb ; 斜率为 " 1 " 的对角校验节点 Q (parity I I ) 的生 成方式可以为数据存储节点中同类型的图形表示的数据异或后与最后一行的调节因子 ( adjuster) 的值异或而来， 调节因子 （adjuster) 不保存， 参见图 lc; 斜率为 的逆对角校验节点 R (parity I I I ) 的生成方式与对角校验节点类似， 仅同类型的图形 的在数据存储节点的位置为逆序， 可以参见图 ld。 此外， 也可以采用其他斜率的校验节 点， 例如： 斜率为 " 2 " 的校验节点、 对角为 "_2 " 的校验节点等。
本发明实施例中， 分布式存储系统丢失三个节点数据具体可以包括以下情况： 情况一、 在丢失的所述三个节点数据包括三个数据存储节点的数据的情况下， 所述 目标数据存储节点为丢失盘号处于中间的数据存储节点。
对于情况一， 在恢复丢失的三个数据存储节点的数据时， 先恢复的目标数据存储节 点可以是丢失盘号处于中间的数据存储节点 （简称中间节点）。 例如： 可以计算丢失盘 号为最大的数据存储节点 （简称最大节点）与中间节点的盘号差， 以及丢失盘号为最小 的数据存储节点 （简称最小节点） 与中间节点的盘号差， 确定最少的异或次数和步长， 将丢失最大节点和最小节点的数据转化为丢失的中间节点的两个条带单元数据异或和， 从而得到 P对异或和， 然后依据中间节点的虚拟补零的条带单元数据， 逐步求得中间节 点的所有条带单元的数据， 进一步可降级恢复剩余两丢失的节点数据。
情况二、在丢失的所述三个节点数据包括水平校验节点和两个数据存储节点的数据 的情况下， 所述目标数据存储节点为丢失的所述两个数据存储节点的任意一个。
对于情况二， 在恢复丢失的水平校验节点和两个数据存储节点的数据时， 可以先恢 复丢失的数据存储节点的数据， 提供给用户， 然后恢复丢失的水平校验节点的数据。 其 中，对角校验节点和逆对角校验节点的调节因子异或和可以由这两个校验节点的所有条 带单元数据异或而来。公共条带单元的对角校验节点的调节因子和逆对角校验节点的调 节因子异或可以将两个丢失的数据存储节点的条带单元数据，转化为同一个丢失的数据 存储节点的两条带单元数据异或和。 然后， 依据该这一个数据存储节点的虚拟补零的条 带单元数据， 可以逐步求得这一个数据存储节点的所有条带单元数据， 进一步可恢复另 一数据存储节点的数据和水平校验节点的数据。
本实施例采用校验数据进行数据恢复可以保证分布式系统存储空间的有效利用率， 以满足分布式存储系统的性能要求； 根据丢失数据的对称性确定首先恢复的目标数据存 储节点， 并根据校验数据和未丢失的数据对丢失的三个节点数据进行恢复， 可以提升分 布式存储系统丢失三个节点数据的情况下的数据恢复性能。 此外， 由于数据分布不同的 数据存储节点中， 有利于数据的保密， 用户的数据更安全。 在丢失三个数据存储节点的 数据的情况下，首先恢复丢失盘号处于中间的数据存储节点，算法简单，易于编码实现; 在丢失水平校验节点和两个数据存储节点的数据的情况下， 首先恢复一个数据存储节 点， 不仅算法简单， 易于编码实现， 还可以将恢复的数据存储节点先发给用户， 并行恢 复水平校验节点的数据， 减少用户的等待时间， 提高用户体检。
实施例二
图 2a为本发明实施例二的数据分流方法的流程图， 图 2a与图 la标号相同的步骤具有 相同的含义， 为简明起见， 省略对这些组件的详细说明。 如图 2a所示， 与上述实施例的 区别在于： 在上述实施例中所述的情况一， 在丢失的所述三个节点数据包括三个数据存 储节点的数据的情况下， 步骤 101根据未丢失的校验节点和数据存储节点的数据， 恢复 所述三个节点数据中目标数据存储节点的数据， 具体可以包括以下步骤：
步骤 201、 根据校验数据， 生成对角调节因子和逆对角调节因子， 所述校验数据包 括水平校验节点、 对角校验节点和逆对角校验节点的数据。
具体地， 设丢失 号数据存储节点， 其中 0≤r<s<t<p'≤ ;7， 其主要思想是通 过十字交叉组合先恢复中间节点。 可以采用公式 （1.1) 和公式 （1.2) 生成调节因子 (adjuster)。其中对角校验节点的调节因子可以简称为对角调节因子，参见公式（1.1)； 逆对角校验节点的调节因子可以简称为逆对角调节因子， 参见公式 （1.2)。
Q = ®(Ε θβ,·)
'·=。、 ， 1， ( 1.1)
R =P®(P. ®R )
s '·=。、 ， l， (1.2)
在公式（1.1)、 （1.2)中， 为所述对角调节因子， 为所述逆对角调节因子， Pt 为所述水平校验节点的第 个条带单元数据， β.为所述对角校验节点的第 个条带单元 数据， 为所述逆对角校验节点的第 个条带单元数据， Q≤i≤P-2， p为大于或等于 数据存储节点的个数 p'的素数。
步骤 202、 根据未丢失的数据存储节点的数据、 所述对角调节因子和所述水平调节 因子， 生成第一水平校验数据、 第一对角校验数据和第一逆对角校验数据。
具体地，可以采用公式（L 3)〜（1.5)生成新的校验数据。其中，采用公式（ 1.3) 生成第一水平校验数据； 采用公式 （ 1.4) 生成所述第一对角校验数据； 采用公式 ( 1.4) 生成所述第一逆对角校验数据；
P; = P; θ( Θ D; ,.) (1.3)
Figure imgf000014_0001
Rt' = ^ Φ Φ ( θ' D<i+ ,·> ,·) (1.5) 在公式（1.3)〜（1.5)， 为所述第一水平校验数据， 为所述第一对角校验数据， 为所述第一逆对角校验数据， Dtj为第 列数据存储节点的第 个条带单元的数据， r、 s、 t为丢失的数据存储节点的盘号， 为数据存储节点的个数， 0≤j≤p'-l， 0<r<s<t<p'<p, <>p为对 p进行取模运算。
步骤 203、 根据所述对角调节因子、 逆对角调节因子、 所述第一水平校验数据、 第 一对角校验数据和第一逆对角校验数据，通过优化的十字交叉运算求出所述丢失盘号处 于中间的数据存储节点的数据。
具体地， 图 2b为本发明实施例二的数据分流方法中的十字交叉运算的示意图， 如图 2b所示， 十字交叉线经过奇数次的条带单元中包括一个三角， 偶数次的条带单元中包括 一个方形 （两个三角组成）， 数据存储节点的条带单元数据具有对称性， 包括方形的相 交节点在进行异或运算的过程中可以消去， 例如： 经过/ 。的两条线上所有的数据存储 节点的条带单元数据的异或运算， 相当于消去了 Z 。。 因此可以通过十字交叉运算， 建 立丢失数据的丢失盘号处于中间的数据存储节点的公式 a.6)：
Ad=Dd s Φ D<d+a>p S®D<d+b>p S Φ D<d+a+b>p s = P<'d>p ® P<'d+a+b>p ® d—r>P ®Q<'d+t>P ( 1· 6) 在公式 （1.6) 中， 0≤ i≤P_i ; s为所述丢失盘号处于中间的数据存储节点的盘 号； a、 6为丢失的三个数据存储节点之间的盘号差， a = s-r,b = t-S。
然后，根据丢失数据的数据存储节点的盘号差确定的移动的步长和循环异或求和次 数， 可以对所述丢失盘号处于中间的数据存储节点的公式进行消元处理后， 将所有丢失 的数据存储节点的条带单元数据转化为所述丢失盘号处于中间的数据存储节点的两个 条带单元数据的异或和， 求出所述丢失盘号处于中间的数据存储节点的数据， 进行消元 处理的具体方式可以包括：
通常， 普通的用十字交叉运算可以包括： 对丢失盘号处于中间的数据存储节点的公 式采用步长 6进行 欠异或求和， 得到所述丢失盘号处于中间的数据存储节点的公式 (1.7):
Du,s® D<u〜 (1.7) 在公式（1.7) 中， 根据<^-^^6 =0确定 ， 图 2c为本发明实施例二的数据分流 方法中的按步长进行循环异或求和的示意图， 如图 2c所示， 以 6=2， =3为例， 可以对 盘号为 "2" 的数据存储节点进行消元处理， 沿着十字交叉的四条线， 按照步长 2进行 3 次异或求和后， 将十字交叉线经过偶数次的条带单元/ 2、 Z 2、 Z 2消去， 可以得到仅 包括两个变量的/ 2、 Z 2的异或和公式。 盘号为 "2" 的数据存储节点的成对的条带单 元数据之间的异或和公式可以类似得到。
优化的十字交叉运算具体可以包括：对所述丢失盘号处于中间的数据存储节点的τ公 式， 采用步长 offDis进行 欠异或求和， 若存在 ， im < min Dis - x offDis >p=0, 以 步长 offDis移动 欠（即进行 欠异或求和）， 可以得到所述丢失盘号处于中间的数据存 储节点的公式 (1.8)：
k-l
A。㊉ D <w+2min Dis> f =∑4 "<w+vxoffDis>n (1.8) 其中， 根据公式 α.9) 可以确定 ：
Figure imgf000016_0001
其中 ， 若 k = m， 贝 lj min Dis-ό, offDis -a， 否贝 lj min Dis - a, offDis - ό， <M + vxoffDis >p =d, 0<u<p-l, A 为上述公式（1.6) 中一个十字交叉的四条线所 过数据存储节点的数据的异或和，求解最优的 后， 由于先恢复中间节点的数据。 例如： 如果 a = 2,6 = l， 可得 = 2， 且以步长 offDis = 6 = 1移动异或， 图 2d为本发明实 施例二的数据分流方法中的按优化步长进行循环异或求和的示意图， 如图 2d所示， 按照 步长 1进行 2次异或求和后， 可以将 Z 2、 D22, Z 2消去， 可以得到仅包括两个变量的
Z 2、 Z 2的异或和公式。 盘号为 "2" 的数据存储节点的成对的条带单元数据之间的异 或和公式可以类似得到。
其中， 根据所述中间的数据存储节点的公式得到的循环方程组， 用于表示所述中间 的数据存储节点的两个数据的异或和， 所述循环方程组的每一个公式至多具有两个变 进一步地， 求出所述丢失盘号处于中间的数据存储节点的数据， 具体可以包括： 根 据所述丢失盘号处于中间的数据存储节点的虚拟补零的条带单元数据 =0， 代入求 解所述循环方程组中只具有一个变量的公式，根据求解结果依次求解所述循环方程组的 其他公式， 得到所述丢失盘号处于中间的数据存储节点的每个数据。 图 2e为本发明实施例二的数据恢复方法中数据存储的结构示意图， 如图 2e所示， 以 5个数据存储节点盘号为 "(Γ4" 为例， 生成 3个校验节点 P、 Q、 R, 共 8个节点， 将每个 节点等大小划分为 4个条带， 第 5条带（图中行号 4的黑色实心圆形） 为虚拟补零的条带， 根据这个五个数据存储节点生成的水平校验节点的盘号可以 "5"， 对角校验节点的盘号 可以为 "6"， 逆对角校验节点的盘号可以为 "7"。 水平校验节点 P (parity I) 的生成 方式可以参见图 lb， 对角校验节点 Q (parity II) 的生成方式可以参见图 lc， 逆对角校 验节点 R (parity III) 的生成方式可以参见图 ld。
对于情况一， 参见图 2d所示， 假设丢失节点 "0、 2、 3" ， 根据本实施例的数据恢 复方法， 恢复这三个数据存储节点的数据的具体过程可以包括：
执行步骤 201， 计算对角校验节点 Q、逆对角校验节点 R的调节因子， 根据公式（1.1) 和公式 （1.2) 可以得到公式 （1.1.0) 和公式 （1.2.0) ：
Qs= P0® P,® P2® P^Q^Q^Q^Q, (1.1.0) ?, - 0 ® ® 2 ® 3 ® i?0 ® ?! ® i?2 ® R3 (1.2.0) 执行步骤 202、计算水平校验节点 P、对角校验节点 Q、逆对角校验节点 R的校验数据， 根据公式 （1.3) 可以得到第一水平校验数据的公式组 （L3.0) ； 将公式 （1.1.0) 代 入公式 （L4) 可以得到第一对角校验数据的公式组 （1.4.0) ， 将公式 （1.2.0) 代入 公式 （1.5) 可以得到第一逆对角校验数据的公式组 （1.5.0) 。
(1. 3.0)
P^=D l®D 4®P}
尸4=0
Q0=Dl @Qs@Q0
(1 =
= ®z 4® ㊉
®Dl ®Rs®R2
-D24@Rs@R3
= D0,t '㊉ A,4㊉
执行步骤 203、 确定最小的异或求和次数 和步长 offDis。 由于丢失的节点号差为 α = 0— 2 = 2,6 = 3— 2 = 1 ， 代 入 公 式 ( 1.9 ) 可 以 得 到
<l-mx2>5=0,<2-nxl>5 = 0,m = 3,n = 2,k = min^n,n} = 2,因此， 异或求和次数 A = 2 步长为 offDis=b=l，参见图 2b所确定的恢复方式符合公式（1.8)，可以将公式组（1.3.0)、 (1.4.0) 、 (1.5.0) 代入公式 (1.8) ， 得到公式 (1.8.0) 。
k-l
Du ® <u+2x2>5 =∑ „+νχ1>5 Θ +2+1+νχ1>5 eR„_0+vxl>5®e„+3+vxl>5 (1.8.0) ν=0
由于 ο≤"≤ρ-ι， 公式 α.8.0)可以展开为循环方程组 α.8.1)， 包括的 ρ-ι = 4 对数据的异或和， 每个公式都是盘号为 "2" 的一对数据的异或和。
D02 Θ D42 = Ρ0 Θ尸3' Θ Θ ρ; Θ ' Θ ΡΑ Θ ?; Θ Q4'
Ζ 2Θ Ζ 2 = 'ΘΡ4'Θ Θρ ΘΡ2'ΘΡ。ΘΑ;Θρ。 ^ g ^
D22 Θ Dl2 = Ρ^® Ρ0® R2' @Q0® ® ® ^3®Q ， . .
D32 Θ D22 =Ρ;ΦΡ Φ ®Q[ ®P^@P^®R4' ®Q2' 由于 D42条带单元数据为零， 可以先计算循环方程组 （L8.1) 中第一个公式中的
D02， 再根据 DQ2计算第二个公式中的 D12， 从而逐个计算盘号为 "2"的数据存储节点 的数据， 然后， 可降级为 EVEN0DD等形式恢复盘号为 "0" 、 "3" 的数据存储节点的数 据。
本实施例采用校验数据进行数据恢复可以保证分布式系统存储空间的有效利用率， 以满足分布式存储系统的性能要求； 根据丢失数据的对称性确定首先恢复的目标数据存 储节点， 并根据校验数据和未丢失的数据对丢失的三个节点数据进行恢复， 可以提升分 布式存储系统丢失三个节点数据的情况下的数据恢复性能； 在丢失三个数据存储节点的 数据的情况下， 首先恢复丢失盘号处于中间的数据存储节点， 并且循环异或次数 k只用 简单的数学公式即可求得， 恢复时异或次数少， 进一步节省所需的云存储处理内存， 算 法简单， 易于编码实现。
实施例三 图 3a为本发明实施例三的数据分流方法的流程图， 图 3a与图 la标号相同的步骤具有 相同的含义， 为简明起见， 省略对这些组件的详细说明。 如图 3a所示， 与上述实施例的 区别在于： 在上述实施例所述的情况二时， 在丢失的所述三个节点数据包括水平校验节 点和两个数据存储节点的数据的情况下， 步骤 101中根据未丢失的校验节点和数据存储 节点的数据， 恢复所述三个节点数据中目标数据存储节点的数据， 具体可以包括以下步 骤：
步骤 301、 在丢失的所述三个节点数据包括水平校验节点和两个数据存储节点的数 据的情况下， 根据所述对角校验节点和所述逆对角校验节点的数据， 生成对角调节因子 和逆对角调节因子的异或和。
具体地， 设丢失 r， p号数据存储节点， 其中 0≤r<s< ≤ ， a = s-r , 可以采 用公式 （2. 1) 生成对角调节因子和逆对角调节因子的异或和；
QS @RS = (02 Q)0 (®2 Rt) (2. 1) 其中， ft为所述对角调节因子， 为所述逆对角调节因子， ρ,为所述对角校验节 点的第 个条带单元数据， 为所述逆对角校验节点的第 个条带单元数据， 0<i<p-2 , 为丢失的水平校验数据的盘号， 且 为大于或等于数据存储节点的个数 的素数。
步骤 302、 根据未丢失的数据存储节点的数据， 生成第二对角校验数据和第二逆对 角校验数据。
具体地， 可以采用公式 （2.2) 和公式 （2.3) 生成新的校验数据， 其中， 采用公 式 （2. 2) 生成第二对角校验数据； 采用公式 （2. 3) 生成所述第二逆对角校验数据；
Figure imgf000019_0001
^ =^@( @ D ) ( 2. 3) 其中， β:为所述第二对角校验数据， 为所述第二逆对角校验数据， Z 为第 列 数据存储节点的第 个条带单元数据， r、 s为丢失的数据存储节点的盘号， 为数据 存储节点的个数， 0≤ ·≤ -1， 0<r<s<p'<p, <>p为对 进行取模运算。
步骤 303、 根据所述对角调节因子和逆对角调节因子的异或和、 所述第二对角校验 数据和第二逆对角校验数据，采用对称消元运算求出丢失的所述两个数据存储节点的任 意一个的数据。
具体可以包括以下方式：
方式一、 先恢复第 S列数据存储节点丢失的数据。
可以根据建立丢失数据公式 （2.4):
Du s ®D<u+2(s_r)>p^®Qs ®RS = Q<'u+S>p ®R ( 2.4) 对公式 （2.4) 进行消元处理可以得到公式 （2.5):
Du,s ® D<u+2(s_r)>^s = Q<'u+S>p ®R ®QS®RS ( 2.5) 然后， 根据虚拟补零的条带单元数据 ^_ΐΛ =ο， 求出第 s列数据存储节点丢失的 数据。
方式二、 先恢复第 r列数据存储节点丢失的数据。
可以根据建立丢失数据公式 （2.6):
Du,r®D<u+2(s_r)>^r®Qs ®RS = Q<'u+2s_r>p ® R<'u—r>p ( 2.6) 对公式 （2.6) 进行消元处理可以得到公式 （2.7):
Du,r®D<u+2(s_r)>^r ^ Q<'u+2s_r>p ®R ®QS®RS ( 2.7) 然后， 根据虚拟补零的条带单元数据 Dp =0， 求出第 r列数据存储节点丢失的数 据。
其中， 先恢复 ^和/ "都可以； 图 3b为本发明实施例三的数据分流方法中对称消元的 示意图， 如图 3b所示， 左侧一列数字中， 标记为条带单元数据 "4" 的行是虚拟补零的 行。 对于情况二， 假设丢失盘号为 "1" 、 "3" 的数据存储节点和水平校验节点 P， 根 据本实施例的数据恢复方法， 具体可以包括：
执行步骤 301、 计算对角校验节点 Q、 逆对角校验节点 R的调节因子的异或和， 根据 公式 （2.1) 可以得到公式 （2.1.0) ：
Figure imgf000020_0001
执行步骤 302， 计算对角校验节点 Q、逆对角校验节点 R的校验数据， 根据公式（2.2) 可以得到第二对角校验数据的公式组 （2.2.0) ； 根据公式 （2.3) 可以得到第一逆对角 校验数据的公式组 （2.3.0) 。
Figure imgf000021_0001
R0 = D0, a®D22@R0
R[ = A,0
R2 =A, 0®Dl @R2 (2.3.0)
R3 =A, ,®Do @D2 @R3
®D3 执行步骤 303，参见图 3b，对公式（2.4)进行消元处理得到公式（2.5)， 公式（2.5) 可以得到循环方程组（2.5.0)。例如： 将两条线交叉的点进行异或运算， 可以消除 D31， 得到 D13、 I ^的异或和公式， 参见如下循环方程组 （2.5.0) 的第二个公式， 以此方式 可以得到循环方程组 （2.5.0) 的所有公式。
Figure imgf000021_0002
由于 D43条带单元数据为零， 可逐个计算！ 3,Ζ 3,Ζ)2,3,Ζ)3,3条带单元数据， 恢复盘 号为 "3"的数据存储节点的数据， 进一步恢复盘号为 "1"的数据存储节点的数据， 最 后恢复水平校验节点 Ρ的数据。
当然， 也可以根据公式 （2.7) ， 先恢复恢复盘号为 "1" 的数据存储节点的数据， 再恢复盘号为 "3" 的数据存储节点的数据， 最后恢复水平校验节点 Ρ的数据。
本实施例采用校验数据进行数据恢复可以保证分布式系统存储空间的有效利用率， 以满足分布式存储系统的性能要求； 根据丢失数据的对称性确定首先恢复的目标数据存 储节点， 并根据校验数据和未丢失的数据对丢失的三个节点数据进行恢复， 可以提升分 布式存储系统丢失三个节点数据的情况下的数据恢复性能； 在丢失水平校验节点和两个 数据存储节点的数据的情况下， 首先恢复一个数据存储节点， 不仅算法简单， 易于编码 实现， 恢复性能比先恢复水平校验节点高， 还可以将恢复的数据存储节点先发给用户， 并行恢复水平校验节点的数据， 减少用户的等待时间， 提高用户的满意度。 实施例四
图 4为本发明实施例四的数据恢复设备的结构框图， 如图 4所示， 该数据恢复设备可 以包括：
目标恢复单元 41， 用于在分布式存储系统丢失三个节点数据的情况下， 根据未丢失 的校验节点和数据存储节点的数据， 恢复所述三个节点数据中目标数据存储节点的数 据， 所述目标数据存储节点根据丢失数据的对称性确定；
降级恢复单元 43， 用于根据恢复后的所述目标数据存储节点的数据， 降级恢复剩余 的丢失数据。
具体地， 在分布式系统或 RAID中可以包括多个数据存储节点和校验节点， 其中， 每 个数据存储节点可以分为多个条带单元。条带单元的个数一般大于或等于数据存储节点 的个数， 具体可以参见本发明数据恢复方法实施例中的相关描述。 参见图 11T图 ld， 校 验节点可以包括水平校验节点、 对角校验节点和逆对角校验节点， 或者还可以包括斜率 为 "2" 的校验节点、 对角为 "-2" 的校验节点等。
本实施例采用校验数据进行数据恢复可以保证分布式系统存储空间的有效利用率， 以满足分布式存储系统的性能要求； 根据丢失数据的对称性确定首先恢复的目标数据存 储节点， 并根据校验数据和未丢失的数据对丢失的三个节点数据进行恢复， 可以提升分 布式存储系统丢失三个节点数据的情况下的数据恢复性能。
实施例五
图 5为本发明实施例五的数据恢复设备的结构框图， 图 5与图 4相同的组件具有相同 的含义， 与上一实施例的区别在于：
如图 5所示， 在丢失的所述三个节点数据包括三个数据存储节点的数据的情况下， 所述目标数据存储节点为丢失盘号处于中间的数据存储节点； 该数据恢复设备的目标恢 复单元 41可以包括：
调节因子生成模块 51， 用于根据校验数据， 生成对角调节因子和逆对角调节因子， 所述校验数据包括水平校验节点、 对角校验节点和逆对角校验节点的数据；
第一校验数据生成模块 53， 用于根据未丢失的数据存储节点的数据、 所述对角调节 因子和所述水平调节因子， 生成第一水平校验数据、 第一对角校验数据和第一逆对角校 验数据；
十字交叉运算模块 55， 用于根据所述对角调节因子、 逆对角调节因子、 所述第一水 平校验数据、 第一对角校验数据和第一逆对角校验数据， 通过优化的十字交叉运算求出 所述丢失盘号处于中间的数据存储节点的数据。
在一种可能的实现方式中， 所述调节因子生成模块 51具体可以用于：
Q = ®(P. ®Q. )
采用公式 ^ ' 生成所述对角调节因子； 采用公式 s ' ' 生成所述逆对角调节因子；
其中， 为所述对角调节因子， 为所述逆对角调节因子， ^为所述水平校验节 点的第 个条带单元数据， ρ,为所述对角校验节点的第 个条带单元数据， 为所述逆 对角校验节点的第 个条带单元数据， 0≤i≤p-2， 为大于或等于数据存储节点的个 数的素数。
在一种可能的实现方式中， 所述第一校验数据生成模块 53具体可以用于： 采用公式/ = Φ ( Θ Z), ;)生成所述第一水平校验数据；
=0 " 采用公式 β: = ft Φ β Θ ( V Di_j>p ) 生成所述第一对角校验数据； 采用公式 = Φ Φ( Θ1 D<i+i> 生成所述第一逆对角校验数据； 其中， 为所述第一水平校验数据， 为所述第一对角校验数据， 为所述第一 逆对角校验数据， 为第 列数据存储节点的第 个条带单元的数据， r、 S、 t为丢失 的数据存储节点的盘号， 为数据存储节点的个数， 0≤ ≤p'-l ， 0<r<s<t<p'<p , <>p为对 进行取模运算。
在一种可能的实现方式中， 所述十字交叉运算模块 55具体可以用于：
通过十字交叉运算建立丢失数据的丢失盘号处于中间的数据存储节点的公式： k —Dd,s Φ D<c a〉 Φ D<d+b>p^s Θ D<d+a+b>^^s = P<d〉p ® P ® Q 其中， 0≤ί ≤ -1 ; s为所述丢失盘号处于中间的数据存储节点的盘号； a、 b为 丢失的三个数据存储节点之间的盘号差， a = S-r,b = t-s
根据丢失数据的数据存储节点的盘号差确定的移动的步长和循环异或求和次数，对 所述丢失盘号处于中间的数据存储节点的公式进行消元处理后，将所有丢失的数据存储 节点的条带单元数据转化为所述丢失盘号处于中间的数据存储节点的两个条带单元数 据的异或和， 求出所述丢失盘号处于中间的数据存储节点的数据。 在一种可能的实现方式中， 所述十字交叉运算模块 55具体还可以用于：
对所述丢失盘号处于中间的数据存储节点的公式采用， 步长 offDis进行 k次异或求 和 ， 得 到 所 述 丢 失 盘 号 处 于 中 间 的 数 据 存 储 节 点 公 式
<b-mxa>p=0
㊉ D ∑4 ， 其中， 根据公式 < <3_MX6 >p= 0确定 ， 若 k = minim, n) k = m , 贝 lj min Dis - b, offDis - a , 否贝1 J min Dis - a, offDis - b , <u + vx offDis >p =d， 0<u< p-\;
其中， 根据所述中间的数据存储节点的公式得到的循环方程组， 用于表示所述中间 的数据存储节点的两个数据的异或和， 所述循环方程组的每一个公式至多具有两个变 所述求出所述丢失盘号处于中间的数据存储节点的数据， 包括：
根据所述丢失盘号处于中间的数据存储节点的虚拟补零的条带单元数据 ? =0， 代入求解所述循环方程组中只具有一个变量的公式，根据求解结果依次求解所述循环方 程组的其他公式， 得到所述丢失盘号处于中间的数据存储节点的每个数据。
本实施例采用校验数据进行数据恢复可以保证分布式系统存储空间的有效利用率， 以满足分布式存储系统的性能要求； 根据丢失数据的对称性确定首先恢复的目标数据存 储节点， 并根据校验数据和未丢失的数据对丢失的三个节点数据进行恢复， 可以提升分 布式存储系统丢失三个节点数据的情况下的数据恢复性能； 在丢失三个数据存储节点的 数据的情况下， 首先恢复丢失盘号处于中间的数据存储节点， 并且循环异或次数 k只用 简单的数学公式即可求得， 恢复时异或次数少， 进一步节省所需的云存储处理内存， 算 法简单， 易于编码实现。
实施例六
图 6为本发明实施例六的数据恢复设备的结构框图， 图 6与图 4相同的组件具有相同 的含义， 与上一实施例的区别在于：
如图 6所示， 在丢失的所述三个节点数据包括水平校验节点和两个数据存储节点的 数据的情况下， 该数据恢复设备的目标恢复单元 41可以包括：
因子异或和模块 57， 用于根据所述对角校验节点和所述逆对角校验节点的数据， 生 成对角调节因子和逆对角调节因子的异或和；
第二校验数据生成模块 58， 用于根据未丢失的数据存储节点的数据， 生成第二对角 校验数据和第二逆对角校验数据；
对称消元运算模块 59， 用于根据所述对角调节因子和逆对角调节因子的异或和、 所 述第二对角校验数据和第二逆对角校验数据，采用对称消元运算求出丢失的所述两个数 据存储节点的任意一个的数据。
在一种可能的实现方式中， 所述因子异或和模块 57具体可以用于： 采用公式 © =(^2β)®(^2 ）， 生成对角调节因子和逆对角调节因子的异或 和， 其中， 为所述对角调节因子， 为所述逆对角调节因子， ρ,为所述对角校验节 点的第 个条带单元数据， 为所述逆对角校验节点的第 个条带单元数据，
0<i<p-2 , 为丢失的水平校验数据的盘号， 且 为大于或等于数据存储节点的个数 的素数。
所述第二校验数据生成模块 58包括： 采用公式 β: = β Θ ( Θ1 D<t_j>p j)生成所述第二对角校验数据； 采用公式 Α^^,Φ^Φ1 ;) 生成所述第二逆对角校验数据；
j
其中， β:为所述第二对角校验数据， 为所述第二逆对角校验数据， Z 为第 列 数据存储节点的第 个条带单元数据， r、 s为丢失的数据存储节点的盘号， 0≤ j≤p'-l， 0<r<s<p'<p, <>p为对 进行取模运算。
在一种可能的实现方式中， 对称消元运算模块 59具体可以用于：
根据建立丢失数据公式
Figure imgf000025_0001
=ρ >ρ® _2 ， 经过 消元处理将丢失的两个数据存储节点的条带单元数据转化为一个数据存储节点的两个 条带单元数据的异或和， 得到公式 Du,s ®D<u+2{s_r)>^ = Q<'u+S>p ®R @¾ @ ^， 根 据虚拟补零的条带单元数据 ^_1Λ =0， 求出第 s列数据存储节点丢失的数据； 或
根据建立丢失数据公式 ζ @ΑΜ+2 θ ® =ρ:Μ+2^>ρ® >ρ ， 经过消 元处理将丢失的两个数据存储节点的条带单元数据转化为一个数据存储节点的两个条 带单元数据的异或和， 得到公式 Du,r®D<u+2 s—r>p,r = Q<'u+2s_r>p ®R ®QS®RS ' 根 据虚拟补零的条带单元数据 Dp =0， 求出第 r列数据存储节点丢失的数据。
本实施例采用校验数据进行数据恢复可以保证分布式系统存储空间的有效利用率， 以满足分布式存储系统的性能要求； 根据丢失数据的对称性确定首先恢复的目标数据存 储节点， 并根据校验数据和未丢失的数据对丢失的三个节点数据进行恢复， 可以提升分 布式存储系统丢失三个节点数据的情况下的数据恢复性能； 在丢失水平校验节点和两个 数据存储节点的数据的情况下， 首先恢复一个数据存储节点， 不仅算法简单， 易于编码 实现， 恢复性能比先恢复水平校验节点高， 还可以将恢复的数据存储节点先发给用户， 并行恢复水平校验节点的数据， 减少用户的等待时间， 提高用户的满意度。
实施例七
图 7为本发明的实施例七的数据恢复设备的结构框图。 所述的数据恢复设备可以是 具备计算能力的主机服务器、 个人计算机 PC、 或者可携带的便携式计算机或终端等。 本 发明具体实施例并不对计算节点的具体实现做限定。
所述数据恢复设备包括处理器（processor) 71、 通信接口 （Communications Interface) 72, 存储器（memory array) 73和总线 74。 其中， 处理器 71、 通信接口 72、 以 及存储器 73通过总线 74完成相互间的通信。
通信接口 72用于与网元通信， 其中网元包括例如虚拟机管理中心、 共享存储等。 处理器 71用于执行程序。 处理器 71可能是一个中央处理器 CPU， 或者是专用集成电 路 ASIC (Appl ication Specific Integrated Circuit ), 或者是被配置成实施本发明实 施例的一个或多个集成电路。
存储器 73用于存放文件。 存储器 73可能包含高速 RAM存储器， 也可能还包括非易失 性存储器（non-volati le memory) , 例如至少一个磁盘存储器。 存储器 73也可以是存储 器阵列。 存储器 73还可能被分块， 并且所述块可按一定的规则组合成虚拟卷。
在一种可能的实施方式中， 上述程序可为包括计算机操作指令的程序代码。 该程序 具体可用于：
在分布式存储系统丢失三个节点数据的情况下，根据未丢失的校验节点和数据存储 节点的数据， 恢复所述三个节点数据中目标数据存储节点的数据， 所述目标数据存储节 点根据丢失数据的对称性确定；
根据恢复后的所述目标数据存储节点的数据， 降级恢复剩余的丢失数据。
在一种可能的实现方式中，在丢失的所述三个节点数据包括三个数据存储节点的数 据的情况下， 所述目标数据存储节点为丢失盘号处于中间的数据存储节点； 所述根据未 丢失的校验节点和数据存储节点的数据， 恢复所述三个节点数据中目标数据存储节点的 数据， 包括： 根据校验数据， 生成对角调节因子和逆对角调节因子， 所述校验数据包括水平校验 节点、 对角校验节点和逆对角校验节点的数据；
根据未丢失的数据存储节点的数据、 所述对角调节因子和所述水平调节因子， 生成 第一水平校验数据、 第一对角校验数据和第一逆对角校验数据；
根据所述对角调节因子、 逆对角调节因子、 所述第一水平校验数据、 第一对角校验 数据和第一逆对角校验数据，通过优化的十字交叉运算求出所述丢失盘号处于中间的数 据存储节点的数据。
在一种可能的实现方式中， 所述根据校验数据， 生成对角调节因子和逆对角调节因 子， 包括：
Q = ®(P. ®Q. )
采用公式 ^ ' 生成所述对角调节因子； 采用公式 s _^。 i 生成所述逆对角调节因子；
其中， ft为所述对角调节因子， 为所述逆对角调节因子， ^为所述水平校验节 点的第 个条带单元数据， ρ,为所述对角校验节点的第 个条带单元数据， 为所述逆 对角校验节点的第 个条带单元数据， 0≤i≤p-2， 为大于或等于数据存储节点的个 数的素数。
在一种可能的实现方式中， 所述根据未丢失的数据存储节点的数据、 所述对角调节 因子和所述水平调节因子， 生成第一水平校验数据、 第一对角校验数据和第一逆对角校 验数据， 包括： 采用公式 Φ( Θ 生成所述第一水平校验数据；
=0 " 采用公式 β: =Qs®Qi®( V Di_j>p ) 生成所述第一对角校验数据； 采用公式 = Φ Φ( Θ1 D<i+i> 生成所述第一逆对角校验数据； 其中， 为所述第一水平校验数据， 为所述第一对角校验数据， 为所述第一 逆对角校验数据， 为第 列数据存储节点的第 个条带单元的数据， r、 S、 t为丢失 的数据存储节点的盘号， 为数据存储节点的个数， 0≤ j≤p'-l ， 0<r<s<t<p'<p , <>p为对 p进行取模运算。 在一种可能的实现方式中， 所述根据所述对角调节因子、 逆对角调节因子、 所述第 一水平校验数据、 第一对角校验数据和第一逆对角校验数据， 通过十字交叉运算求出所 述丢失盘号处于中间的数据存储节点的数据， 包括：
通过十字交叉运算建立丢失数据的丢失盘号处于中间的数据存储节点的公式： k —Dd,s Φ D<c a Φ D<d+b>p^s Θ D<d+a+b>^^s = P<d p ® P ® Q 其中， 0≤ί ≤ρ-1 ; s为所述丢失盘号处于中间的数据存储节点的盘号； a b为 丢失的三个数据存储节点之间的盘号差， a = S-r,b = t-s
根据丢失数据的数据存储节点的盘号差确定的移动的步长和循环异或求和次数，对 所述丢失盘号处于中间的数据存储节点的公式进行消元处理后，将所有丢失的数据存储 节点的条带单元数据转化为所述丢失盘号处于中间的数据存储节点的两个条带单元数 据的异或和， 求出所述丢失盘号处于中间的数据存储节点的数据。
在一种可能的实现方式中，所述对所述丢失盘号处于中间的数据存储节点的公式进 行消元处理后，将所有丢失的数据存储节点的条带单元数据转化为所述丢失盘号处于中 间的数据存储节点的两个条带单元数据的异或和， 包括：
对所述丢失盘号处于中间的数据存储节点的公式采用， 步长 offDis进行 k次异或求 和 ， 得 到 所 述 丢 失 盘 号 处 于 中 间 的 数 据 存 储 节 点 公 式
® )<„+2minDis>P,, 确定 ， 若
Figure imgf000028_0001
k = m , 贝 lj min Dis - b, offDis - a , 否贝1 J min Dis - a, offDis - b , <u + vx offDis >p =d， 0<u< p-\;
其中， 根据所述中间的数据存储节点的公式得到的循环方程组， 用于表示所述中间 的数据存储节点的两个数据的异或和， 所述循环方程组的每一个公式至多具有两个变 所述求出所述丢失盘号处于中间的数据存储节点的数据， 包括：
根据所述丢失盘号处于中间的数据存储节点的虚拟补零的条带单元数据 ^_1Λ =0， 代入求解所述循环方程组中只具有一个变量的公式，根据求解结果依次求解所述循环方 程组的其他公式， 得到所述丢失盘号处于中间的数据存储节点的每个数据。
在一种可能的实现方式中，在丢失的所述三个节点数据包括水平校验节点和两个数 据存储节点的数据的情况下，所述目标数据存储节点为丢失的所述两个数据存储节点的 任意一个， 所述根据未丢失的校验节点和数据存储节点的数据， 恢复所述三个节点数据 中目标数据存储节点的数据， 包括：
根据所述对角校验节点和所述逆对角校验节点的数据， 生成对角调节因子和逆对角 调节因子的异或和；
根据未丢失的数据存储节点的数据， 生成第二对角校验数据和第二逆对角校验数 据；
根据所述对角调节因子和逆对角调节因子的异或和、所述第二对角校验数据和第二 逆对角校验数据，采用对称消元运算求出丢失的所述两个数据存储节点的任意一个的数 据。
在一种可能的实现方式中，所述根据所述对角校验节点和所述逆对角校验节点的数 据， 生成对角调节因子和逆对角调节因子的异或和， 包括： 采用公式 © =(^2β)®(^2 ）， 生成对角调节因子和逆对角调节因子的异或 和， 其中， 为所述对角调节因子， 为所述逆对角调节因子， ρ,为所述对角校验节 点的第 个条带单元数据， 为所述逆对角校验节点的第 个条带单元数据， 0<i<p-2 , 为丢失的水平校验数据的盘号， 且 为大于或等于数据存储节点的个数 的素数。
在一种可能的实现方式中， 所述根据未丢失的数据存储节点的数据， 生成第二对角 校验数据和第二逆对角校验数据， 包括： 采用公式 β: = β Θ (Θ1 D<t_j>p j)生成所述第二对角校验数据； 采用公式 R; = Φ ( Θ1 D<i+ ,·> , ) 生成所述第二逆对角校验数据； 其中， β:为所述第二对角校验数据， 为所述第二逆对角校验数据， Z 为第 列 数据存储节点的第 个条带单元数据， r、 s为丢失的数据存储节点的盘号， 为数据 存储节点的个数， 0≤ ·≤ρ'-1， 0<r<s<p'<p, <>p为对 进行取模运算。
在一种可能的实现方式中， 所述根据所述对角调节因子和逆对角调节因子的异或 和、 所述第二对角校验数据和第二逆对角校验数据， 采用对称消元运算求出所述一个数 据存储节点的数据， 包括：
根据建立丢失数据公式 Α^@Ζ)<μ+2( >Ρ Θ ® =ρΜ ， 经过 消元处理将丢失的两个数据存储节点的条带单元数据转化为一个数据存储节点的两个 条带单元数据的异或和， 得到公式 Du,s ® D<u+2{s_r)>^ = Q<' u+S>p ® R @a @ ^， 根 据虚拟补零的条带单元数据 ^_1Λ = 0， 求出第 s列数据存储节点丢失的数据； 或
根据建立丢失数据公式 @ ® = M+2 p ® r>p ， 经过 消元处理将丢失的两个数据存储节点的条带单元数据转化为一个数据存储节点的两个 条带单元数据的异或和， 得到公式 Du,r ® D<u+2 s—r>p,r = Q<' u+2s_r>p ® R @ ¾ ® ^， 根 据虚拟补零的条带单元数据 Dp = 0， 求出第 r列数据存储节点丢失的数据。
本实施例采用校验数据进行数据恢复可以保证分布式系统存储空间的有效利用率， 以满足分布式存储系统的性能要求； 根据丢失数据的对称性确定首先恢复的目标数据存 储节点， 并根据校验数据和未丢失的数据对丢失的三个节点数据进行恢复， 可以提升分 布式存储系统丢失三个节点数据的情况下的数据恢复性能。
实施例八
图 8为本发明的实施例八的分布式存储系统的结构框图。 如图 8所示， 该分布式存储 系统包括： 多个数据存储节点 81、 多个校验节点 83和数据恢复设备 85 ;
其中， 所述数据恢复设备 85采用本发明实施例中任意一种结构的数据恢复设备。 本实施例采用校验数据进行数据恢复可以保证分布式系统存储空间的有效利用率， 以满足分布式存储系统的性能要求； 根据丢失数据的对称性确定首先恢复的目标数据存 储节点， 并根据校验数据和未丢失的数据对丢失的三个节点数据进行恢复， 可以提升分 布式存储系统丢失三个节点数据的情况下的数据恢复性能。
本领域普通技术人员可以意识到，本文所描述的实施例中的各示例性单元及算法步 骤， 能够以电子硬件、 或者计算机软件和电子硬件的结合来实现。 这些功能究竟以硬件 还是软件形式来实现， 取决于技术方案的特定应用和设计约束条件。 专业技术人员可以 针对特定的应用选择不同的方法来实现所描述的功能，但是这种实现不应认为超出本发 明的范围。
如果以计算机软件的形式来实现所述功能并作为独立的产品销售或使用时， 则在一 定程度上可认为本发明的技术方案的全部或部分（例如对现有技术做出贡献的部分）是 以计算机软件产品的形式体现的。该计算机软件产品通常存储在计算机可读取的存储介 质中， 包括若干指令用以使得计算机设备 （可以是个人计算机、 服务器、 或者网络设备 等） 执行本发明各实施例方法的全部或部分步骤。 而前述的存储介质包括 U盘、 移动硬 盘、只读存储器（ROM, Read-Only Memory)、随机存取存储器（RAM, Random Access Memory ) 磁碟或者光盘等各种可以存储程序代码的介质。
以上所述， 仅为本发明的具体实施方式， 但本发明的保护范围并不局限于此， 任何 熟悉本技术领域的技术人员在本发明揭露的技术范围内， 可轻易想到变化或替换， 都应 涵盖在本发明的保护范围之内。 因此， 本发明的保护范围应所述以权利要求的保护范围 为准。

Claims

权利要求
1、 一种数据恢复方法， 其特征在于， 包括：
在分布式存储系统丢失三个节点数据的情况下，根据未丢失的校验节点和数据存储 节点的数据， 恢复所述三个节点数据中目标数据存储节点的数据， 所述目标数据存储节 点根据丢失数据的对称性确定；
根据恢复后的所述目标数据存储节点的数据， 降级恢复剩余的丢失数据。
2、 根据权利要求 1所述的数据恢复方法， 其特征在于， 在丢失的所述三个节点数据 包括三个数据存储节点的数据的情况下，所述目标数据存储节点为丢失盘号处于中间的 数据存储节点； 所述根据未丢失的校验节点和数据存储节点的数据， 恢复所述三个节点 数据中目标数据存储节点的数据， 包括：
根据校验数据， 生成对角调节因子和逆对角调节因子， 所述校验数据包括水平校验 节点、 对角校验节点和逆对角校验节点的数据；
根据未丢失的数据存储节点的数据、 所述对角调节因子和所述水平调节因子， 生成 第一水平校验数据、 第一对角校验数据和第一逆对角校验数据；
根据所述对角调节因子、 逆对角调节因子、 所述第一水平校验数据、 第一对角校验 数据和第一逆对角校验数据，通过优化的十字交叉运算求出所述丢失盘号处于中间的数 据存储节点的数据。
3、 根据权利要求 2所述的数据恢复方法， 其特征在于， 所述根据校验数据， 生成对 角调节因子和逆对角调节因子， 包括：
Q = ® (P. ® Q. )
采用公式 ^ ' 生成所述对角调节因子； 采用公式 s ' ' 生成所述逆对角调节因子；
其中， ft为所述对角调节因子， 为所述逆对角调节因子， ^为所述水平校验节 点的第 个条带单元数据， ρ,为所述对角校验节点的第 个条带单元数据， 为所述逆 对角校验节点的第 个条带单元数据， 0≤i≤p-2， 为大于或等于数据存储节点的个 数的素数。
4、 根据权利要求 3所述的数据恢复方法， 其特征在于， 所述根据未丢失的数据存储 节点的数据、 所述对角调节因子和所述水平调节因子， 生成第一水平校验数据、 第一对 角校验数据和第一逆对角校验数据， 包括： 采用公式 Φ( Θ 生成所述第一水平校验数据；
=0 " 采用公式 β: = ft Φ β Θ ( V Di_j>p ) 生成所述第一对角校验数据； 采用公式 = Φ Φ( Θ1 D<i+i> 生成所述第一逆对角校验数据； 其中， 为所述第一水平校验数据， 为所述第一对角校验数据， 为所述第一 逆对角校验数据， 为第 列数据存储节点的第 个条带单元的数据， r、 S、 t为丢失 的数据存储节点的盘号， 为数据存储节点的个数， 0≤ j≤p'-l ， 0<r<s<t<p'<p , <>p为对 进行取模运算。
5、根据权利要求 4所述的数据恢复方法，其特征在于，所述根据所述对角调节因子、 逆对角调节因子、 所述第一水平校验数据、 第一对角校验数据和第一逆对角校验数据， 通过十字交叉运算求出所述丢失盘号处于中间的数据存储节点的数据， 包括：
通过十字交叉运算建立丢失数据的丢失盘号处于中间的数据存储节点的公式： k —Dd,s Φ D<c a〉 Φ D<d+b>p^s Θ D<d+a+b>^^s = P<d〉p ® P ® Q
其中， 0≤ί ≤ρ-1 ; s为所述丢失盘号处于中间的数据存储节点的盘号； a、 b为 丢失的三个数据存储节点之间的盘号差， a = S-r,b = t-s
根据丢失数据的数据存储节点的盘号差确定的移动的步长和循环异或求和次数，对 所述丢失盘号处于中间的数据存储节点的公式进行消元处理后，将所有丢失的数据存储 节点的条带单元数据转化为所述丢失盘号处于中间的数据存储节点的两个条带单元数 据的异或和， 求出所述丢失盘号处于中间的数据存储节点的数据。
6、 根据权利要求 5所述的数据恢复方法， 其特征在于， 所述对所述丢失盘号处于中 间的数据存储节点的公式进行消元处理后，将所有丢失的数据存储节点的条带单元数据 转化为所述丢失盘号处于中间的数据存储节点的两个条带单元数据的异或和， 包括： 对所述丢失盘号处于中间的数据存储节点的公式采用， 步长 offDis进行 k次异或求 和 ， 得 到 所 述 丢 失 盘 号 处 于 中 间 的 数 据 存 储 节 点 公 式
<b-mxa>p=0
®D<w+2minDi = <w+vx。 其中， 根据公式 <a-nxb>p= 0确定 ， 若 k = m im.n k二 m， 贝' J min Dis = b, offDis = a , 否贝' J min Dis = a, offDis -b？ < w + v x offDis >n =d , 0 < < p - \ ;
其中， 根据所述中间的数据存储节点的公式得到的循环方程组， 用于表示所述中间 的数据存储节点的两个数据的异或和， 所述循环方程组的每一个公式至多具有两个变 所述求出所述丢失盘号处于中间的数据存储节点的数据， 包括：
根据所述丢失盘号处于中间的数据存储节点的虚拟补零的条带单元数据 ^_1Λ = 0， 代入求解所述循环方程组中只具有一个变量的公式，根据求解结果依次求解所述循环方 程组的其他公式， 得到所述丢失盘号处于中间的数据存储节点的每个数据。
7、 根据权利要求 1所述的数据恢复方法， 其特征在于， 在丢失的所述三个节点数据 包括水平校验节点和两个数据存储节点的数据的情况下，所述目标数据存储节点为丢失 的所述两个数据存储节点的任意一个，所述根据未丢失的校验节点和数据存储节点的数 据， 恢复所述三个节点数据中目标数据存储节点的数据， 包括：
根据所述对角校验节点和所述逆对角校验节点的数据， 生成对角调节因子和逆对角 调节因子的异或和；
根据未丢失的数据存储节点的数据， 生成第二对角校验数据和第二逆对角校验数 据；
根据所述对角调节因子和逆对角调节因子的异或和、所述第二对角校验数据和第二 逆对角校验数据，采用对称消元运算求出丢失的所述两个数据存储节点的任意一个的数 据。
8、 根据权利要求 7所述的数据恢复方法， 其特征在于， 所述根据所述对角校验节点 和所述逆对角校验节点的数据， 生成对角调节因子和逆对角调节因子的异或和， 包括： 采用公式 © = (^2β) ® (^2 ）， 生成对角调节因子和逆对角调节因子的异或 和， 其中， 为所述对角调节因子， 为所述逆对角调节因子， ρ,为所述对角校验节 点的第 个条带单元数据， 为所述逆对角校验节点的第 个条带单元数据， 0 < i < p-2 , 为丢失的水平校验数据的盘号， 且 为大于或等于数据存储节点的个数 的素数。
9、 根据权利要求 8所述的数据恢复方法， 其特征在于， 所述根据未丢失的数据存储 节点的数据， 生成第二对角校验数据和第二逆对角校验数据， 包括： 采用公式 β: = β Θ ( Θ1 D<t_j>p j)生成所述第二对角校验数据； 采用公式 Α^^,Φ^Φ1 ;) 生成所述第二逆对角校验数据； 其中， β:为所述第二对角校验数据， 为所述第二逆对角校验数据， Z 为第 列 数据存储节点的第 个条带单元数据， r、 s为丢失的数据存储节点的盘号， 为数据 存储节点的个数， 0≤ ·≤ρ'-1， 0<r<s<p'<p, <>p为对 进行取模运算。
10、 根据权利要求 9所述的数据恢复方法， 其特征在于， 所述根据所述对角调节因 子和逆对角调节因子的异或和、 所述第二对角校验数据和第二逆对角校验数据， 采用对 称消元运算求出所述一个数据存储节点的数据， 包括：
根据建立丢失数据公式
Figure imgf000035_0001
=ρ >ρ® _2 ， 经过 消元处理将丢失的两个数据存储节点的条带单元数据转化为一个数据存储节点的两个 条带单元数据的异或和， 得到公式 Du,s ®D<u+2{s_r)>^ = Q<'u+S>p ®R @¾ @ ^， 根 据虚拟补零的条带单元数据 ^_1Λ =0， 求出第 s列数据存储节点丢失的数据； 或
根据建立丢失数据公式 @ ® = M+2 p® r>p ， 经过 消元处理将丢失的两个数据存储节点的条带单元数据转化为一个数据存储节点的两个 条带单元数据的异或和， 得到公式 Α^ΘΖ^^—^^^^—^θ^—^θβθ^, 根 据虚拟补零的条带单元数据 Dp =0， 求出第 r列数据存储节点丢失的数据。
11、 一种数据恢复设备， 其特征在于， 包括- 目标恢复单元， 用于在分布式存储系统丢失三个节点数据的情况下， 根据未丢失的 校验节点和数据存储节点的数据， 恢复所述三个节点数据中目标数据存储节点的数据， 所述目标数据存储节点根据丢失数据的对称性确定；
降级恢复单元， 用于根据恢复后的所述目标数据存储节点的数据， 降级恢复剩余的 丢失数据。
12、 根据权利要求 11所述的数据恢复设备， 其特征在于， 在丢失的所述三个节点数 据包括三个数据存储节点的数据的情况下，所述目标数据存储节点为丢失盘号处于中间 的数据存储节点； 所述目标恢复单元包括：
调节因子生成模块， 用于根据校验数据， 生成对角调节因子和逆对角调节因子， 所 述校验数据包括水平校验节点、 对角校验节点和逆对角校验节点的数据； 第一校验数据生成模块， 用于根据未丢失的数据存储节点的数据、 所述对角调节因 子和所述水平调节因子， 生成第一水平校验数据、 第一对角校验数据和第一逆对角校验 数据；
十字交叉运算模块， 用于根据所述对角调节因子、 逆对角调节因子、 所述第一水平 校验数据、 第一对角校验数据和第一逆对角校验数据， 通过优化的十字交叉运算求出所 述丢失盘号处于中间的数据存储节点的数据。
13、 根据权利要求 12所述的数据恢复设备， 其特征在于， 所述调节因子生成模块具 体用于-
Q = ®(P. ®Q. )
采用公式 ^ ' 生成所述对角调节因子； 采用公式 s ' ' 生成所述逆对角调节因子；
其中， ft为所述对角调节因子， 为所述逆对角调节因子， ^为所述水平校验节 点的第 个条带单元数据， ρ,为所述对角校验节点的第 个条带单元数据， 为所述逆 对角校验节点的第 个条带单元数据， 0≤i≤p-2， 为大于或等于数据存储节点的个 数的素数。
14、 根据权利要求 13所述的数据恢复设备， 其特征在于， 所述第一校验数据生成模 块具体用于- 采用公式 Φ( Θ 生成所述第一水平校验数据；
=0 " 采用公式 β: = ft Φ β Θ ( V Di_j>p ) 生成所述第一对角校验数据； 采用公式 = Φ Φ( Θ1 D<i+i> 生成所述第一逆对角校验数据； 其中， 为所述第一水平校验数据， 为所述第一对角校验数据， 为所述第一 逆对角校验数据， 为第 列数据存储节点的第 个条带单元的数据， r、 S、 t为丢失 的数据存储节点的盘号， 为数据存储节点的个数， 0≤j'≤ -l ， 0<r<s<t<p'<p , <>p为对 进行取模运算。
15、 根据权利要求 14所述的数据恢复设备， 其特征在于， 所述十字交叉运算模块具 体用于： 通过十字交叉运算建立丢失数据的丢失盘号处于中间的数据存储节点的公式： k —Dd,s Φ D<c a Φ D<d+b>p^s Θ D<d+a+b>^^s = P<d p ® P ® Q 其中， 0≤ί ≤ρ-1 ; s为所述丢失盘号处于中间的数据存储节点的盘号； a b为 丢失的三个数据存储节点之间的盘号差， a = S-r,b = t-s
根据丢失数据的数据存储节点的盘号差确定的移动的步长和循环异或求和次数，对 所述丢失盘号处于中间的数据存储节点的公式进行消元处理后，将所有丢失的数据存储 节点的条带单元数据转化为所述丢失盘号处于中间的数据存储节点的两个条带单元数 据的异或和， 求出所述丢失盘号处于中间的数据存储节点的数据。
16、 根据权利要求 15所述的数据恢复设备， 其特征在于， 所述十字交叉运算模块具 体还用于：
对所述丢失盘号处于中间的数据存储节点的公式采用， 步长 offDis进行 k次异或求 和 ， 得 到 所 述 丢 失 盘 号 处 于 中 间 的 数 据 存 储 节 点 公 式
® )<„+2minDis>P,, 确定 ， 若
Figure imgf000037_0001
k = m , 贝 lj min Dis - b, offDis - a , 否贝1 J min Dis - a, offDis - b , <u + vx offDis >p =d， 0<u< p-\;
其中， 根据所述中间的数据存储节点的公式得到的循环方程组， 用于表示所述中间 的数据存储节点的两个数据的异或和， 所述循环方程组的每一个公式至多具有两个变 所述求出所述丢失盘号处于中间的数据存储节点的数据， 包括：
根据所述丢失盘号处于中间的数据存储节点的虚拟补零的条带单元数据 ^_1Λ =0， 代入求解所述循环方程组中只具有一个变量的公式，根据求解结果依次求解所述循环方 程组的其他公式， 得到所述丢失盘号处于中间的数据存储节点的每个数据。
17、 根据权利要求 11所述的数据恢复设备， 其特征在于， 在丢失的所述三个节点数 据包括水平校验节点和两个数据存储节点的数据的情况下， 所述目标恢复单元包括： 因子异或和模块， 用于根据所述对角校验节点和所述逆对角校验节点的数据， 生成 对角调节因子和逆对角调节因子的异或和；
第二校验数据生成模块， 用于根据未丢失的数据存储节点的数据， 生成第二对角校 验数据和第二逆对角校验数据； 对称消元运算模块， 用于根据所述对角调节因子和逆对角调节因子的异或和、 所述 第二对角校验数据和第二逆对角校验数据，采用对称消元运算求出丢失的所述两个数据 存储节点的任意一个的数据。
18、 根据权利要求 17所述的数据恢复设备， 其特征在于， 所述因子异或和模块具体 用于- 采用公式 © =(^2β)®(^2 ）， 生成对角调节因子和逆对角调节因子的异或 和， 其中， 为所述对角调节因子， 为所述逆对角调节因子， ρ,为所述对角校验节 点的第 个条带单元数据， 为所述逆对角校验节点的第 个条带单元数据，
0<i<p-2 , 为丢失的水平校验数据的盘号， 且 为大于或等于数据存储节点的个数 的素数。
19、 根据权利要求 18所述的数据恢复设备， 其特征在于， 所述第二校验数据生成模 块具体用于- 采用公式 β: = β Θ (Θ1 D<t_j>p j)生成所述第二对角校验数据； 采用公式 Α^^,Φ^Φ1 ;) 生成所述第二逆对角校验数据；
j
其中， 为所述第二对角校验数据， 为所述第二逆对角校验数据， 为第 j'列 数据存储节点的第 个条带单元数据， r、 s为丢失的数据存储节点的盘号， 0≤ j≤p'-l， 0<r<s<p'<p, <>p为对 进行取模运算。
20、 根据权利要求 19所述的数据恢复设备， 其特征在于， 所述对称消元运算模块 具体用于- 根据建立丢失数据公式 ®ρ =ρ >ρ® _2 ， 经过 消元处理将丢失的两个数据存储节点的条带单元数据转化为一个数据存储节点的两个 条带单元数据的异或和， 得到公式 Du,s ®D<u+2{s_r)>^ = Q<'u+S>p ®R @a @ ^， 根 据虚拟补零的条带单元数据 ^_1Λ =0， 求出第 s列数据存储节点丢失的数据； 或
根据建立丢失数据公式 ζ @ΑΜ+2 θ ® =ρ:Μ+2^>ρ® >ρ ， 经过消 元处理将丢失的两个数据存储节点的条带单元数据转化为一个数据存储节点的两个条 带单元数据的异或和， 得到公式 Du,r®D<u+2 s ,r = Q<'u+2s_r>p ®R ®QS®RS ' 根 据虚拟补零的条带单元数据 = 0， 求出第 r列数据存储节点丢失的数据。
21、 一种分布式存储系统， 其特征在于， 包括： 多个数据存储节点、 多个校验节点 和数据恢复设备；
所述数据恢复设备采用权利要求 11-20中任一项所述的数据恢复设备。
PCT/CN2014/073383 2013-07-26 2014-03-13 数据恢复方法、数据恢复设备和分布式存储系统 Ceased WO2015010476A1 (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
EP14733496.5A EP2854033B1 (en) 2013-07-26 2014-03-13 Data recovery method, data recovery device, and distributed storage system
US14/331,485 US9529675B2 (en) 2013-07-26 2014-07-15 Data recovery method, data recovery device and distributed storage system

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN201310320300.3A CN103412799B (zh) 2013-07-26 2013-07-26 数据恢复方法、数据恢复设备和分布式存储系统
CN201310320300.3 2013-07-26

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US14/331,485 Continuation US9529675B2 (en) 2013-07-26 2014-07-15 Data recovery method, data recovery device and distributed storage system

Publications (1)

Publication Number Publication Date
WO2015010476A1 true WO2015010476A1 (zh) 2015-01-29

Family

ID=49605812

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2014/073383 Ceased WO2015010476A1 (zh) 2013-07-26 2014-03-13 数据恢复方法、数据恢复设备和分布式存储系统

Country Status (4)

Country Link
US (1) US9529675B2 (zh)
EP (1) EP2854033B1 (zh)
CN (1) CN103412799B (zh)
WO (1) WO2015010476A1 (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20190022509A1 (en) * 2016-03-17 2019-01-24 Golfzon Co., Ltd. Screen golf system, golf information service method and mobile terminal control method for golf information service realized in screen golf system, and computing-device-readable recording medium having program for performing the methods recorded therein

Families Citing this family (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103412799B (zh) * 2013-07-26 2016-08-24 华为技术有限公司 数据恢复方法、数据恢复设备和分布式存储系统
CN105045891B (zh) * 2015-07-31 2018-08-31 中国科学院计算技术研究所 提高顺序表性能方法、系统、架构、优化方法及存储装置
US10360119B2 (en) * 2015-10-06 2019-07-23 Netapp, Inc. Data recovery in a distributed storage system
CN106227617A (zh) * 2016-07-15 2016-12-14 乐视控股（北京）有限公司 自修复方法和基于纠删码算法的存储系统
CN107632994B (zh) * 2016-07-19 2021-05-25 普天信息技术有限公司 一种基于hdfs文件系统的可靠性增强方法和系统
CN106407366A (zh) * 2016-09-09 2017-02-15 浪潮软件股份有限公司 一种分布式系统数据提取方法
CN107870829B (zh) * 2016-09-24 2022-03-08 华为技术有限公司 一种分布式数据恢复方法、服务器、相关设备及系统
US10277253B2 (en) * 2016-12-21 2019-04-30 PhazrIO Inc. High performance data redundancy and fault tolerance
JP6807457B2 (ja) * 2017-06-15 2021-01-06 株式会社日立製作所 ストレージシステム及びストレージシステムの制御方法
US10379952B2 (en) * 2017-06-16 2019-08-13 Western Digital Technologies, Inc. Data recovery and regeneration using parity code
CN111949210B (zh) * 2017-06-28 2024-11-15 华为技术有限公司 分布式存储系统中元数据存储方法、系统及存储介质
CN113687793B (zh) * 2017-06-30 2024-03-15 伊姆西Ip控股有限责任公司 存储管理方法和系统
CN107423426B (zh) * 2017-08-02 2020-06-02 众安信息技术服务有限公司 一种区块链块数据的数据归档方法及电子设备
CN110120949B (zh) * 2019-05-10 2021-07-27 中国联合网络通信集团有限公司 一种数据存储方法和数据存储系统
CN111930552B (zh) * 2020-06-17 2024-07-30 深圳佰维存储科技股份有限公司 坏块数据的恢复方法、装置、存储介质及电子设备
CN113190377B (zh) * 2021-05-17 2022-03-11 北京中电兴发科技有限公司 一种基于分布式存储系统的可靠冗余方法及设备
CN119883717A (zh) * 2025-03-26 2025-04-25 山东云海国创云计算装备产业创新中心有限公司 基于双维奇偶校验码的数据处理方法、设备、产品及介质

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5412671A (en) * 1990-12-03 1995-05-02 Unisys Corporation Data protection and error correction, particularly for general register sets
CN1801105A (zh) * 2004-11-24 2006-07-12 国际商业机器公司 容许存储系统中的多个存储设备故障的系统和方法
CN101512492A (zh) * 2005-12-15 2009-08-19 网络装置公司 用于实现从存储阵列中的三重故障中高效恢复的三重奇偶校验技术
CN103412799A (zh) * 2013-07-26 2013-11-27 华为技术有限公司 数据恢复方法、数据恢复设备和分布式存储系统

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7613984B2 (en) * 2001-12-28 2009-11-03 Netapp, Inc. System and method for symmetric triple parity for failing storage devices
JP5993018B2 (ja) * 2011-11-02 2016-09-14 エンパイア テクノロジー ディベロップメント エルエルシー データ復元を容易にするためのトリプルパリティエンコーディング

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5412671A (en) * 1990-12-03 1995-05-02 Unisys Corporation Data protection and error correction, particularly for general register sets
CN1801105A (zh) * 2004-11-24 2006-07-12 国际商业机器公司 容许存储系统中的多个存储设备故障的系统和方法
CN101512492A (zh) * 2005-12-15 2009-08-19 网络装置公司 用于实现从存储阵列中的三重故障中高效恢复的三重奇偶校验技术
CN103412799A (zh) * 2013-07-26 2013-11-27 华为技术有限公司 数据恢复方法、数据恢复设备和分布式存储系统

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20190022509A1 (en) * 2016-03-17 2019-01-24 Golfzon Co., Ltd. Screen golf system, golf information service method and mobile terminal control method for golf information service realized in screen golf system, and computing-device-readable recording medium having program for performing the methods recorded therein

Also Published As

Publication number Publication date
EP2854033A4 (en) 2015-09-23
EP2854033A1 (en) 2015-04-01
CN103412799A (zh) 2013-11-27
US20150033070A1 (en) 2015-01-29
US9529675B2 (en) 2016-12-27
CN103412799B (zh) 2016-08-24
EP2854033B1 (en) 2018-12-26

Similar Documents

Publication Publication Date Title
WO2015010476A1 (zh) 数据恢复方法、数据恢复设备和分布式存储系统
US10146618B2 (en) Distributed data storage with reduced storage overhead using reduced-dependency erasure codes
CN105320899B (zh) 一种面向用户的云存储数据完整性保护方法
US9356626B2 (en) Data encoding for data storage system based on generalized concatenated codes
CN107086870B (zh) 修复多节点失效的mds阵列码编码以及解码方法
US20100218037A1 (en) Matrix-based Error Correction and Erasure Code Methods and Apparatus and Applications Thereof
US8392805B2 (en) Non-MDS erasure codes for storage systems
US9104603B2 (en) Method of exact repair of pairs of failed storage nodes in a distributed data storage system and corresponding device
CN101084486B (zh) 用于校验子生成以及数据恢复的方法和系统
RU2680350C2 (ru) Способ и система распределенного хранения восстанавливаемых данных с обеспечением целостности и конфиденциальности информации
CN110532126B (zh) 纠删码存储系统数据快速恢复方法、装置及存储介质
CN104156283B (zh) 数据恢复方法、装置及存储系统
Han et al. Update-efficient error-correcting product-matrix codes
WO2016058262A1 (zh) 一种基于二进制域里德所罗门码的数据编解码方法
CN109101360B (zh) 一种基于布隆过滤器和交叉编码的数据完整性保护方法
CN112130772A (zh) 一种基于稀疏随机纠删码技术的区块链安全存储方法
CN117271199A (zh) 码生成、编码及解码方法及其装置
Ivanichkina et al. Mathematical methods and models of improving data storage reliability including those based on finite field theory
WO2017041231A1 (zh) 一种精确修复的二进制再生码编解码
WO2017041232A1 (zh) 一种二进制循环码的编解码框架
Schindelhauer et al. Maximum distance separable codes based on circulant Cauchy matrices
Bhuvaneshwari et al. Review on LDPC codes for big data storage
WO2014012246A1 (zh) 用于分布式网络存储的自修复码的编码、重构和恢复方法
Huang et al. An improved decoding algorithm for generalized RDP codes
US9183076B2 (en) Using carry-less multiplication (CLMUL) to implement erasure code

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 2014733496

Country of ref document: EP

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 14733496

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE