CN109426590A - Method for the method for back end storing data and for restoring data - Google Patents
Method for the method for back end storing data and for restoring data Download PDFInfo
- Publication number
- CN109426590A CN109426590A CN201710777448.8A CN201710777448A CN109426590A CN 109426590 A CN109426590 A CN 109426590A CN 201710777448 A CN201710777448 A CN 201710777448A CN 109426590 A CN109426590 A CN 109426590A
- Authority
- CN
- China
- Prior art keywords
- data
- node
- redundant
- nodes
- blocks
- 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.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR 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/14—Error detection or correction of the data by redundancy in operation
- G06F11/1402—Saving, restoring, recovering or retrying
- G06F11/1446—Point-in-time backing up or restoration of persistent data
- G06F11/1458—Management of the backup or restore process
- G06F11/1469—Backup restoration techniques
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR 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/14—Error detection or correction of the data by redundancy in operation
- G06F11/1402—Saving, restoring, recovering or retrying
- G06F11/1415—Saving, restoring, recovering or retrying at system level
- G06F11/1435—Saving, restoring, recovering or retrying at system level using file system or storage system metadata
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Quality & Reliability (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Library & Information Science (AREA)
- Storage Device Security (AREA)
Abstract
This application discloses a kind of methods for back end storing data, comprising: the data for belonging to same back end is divided into the identical data block of K size, and to be set as size identical for the data block of different data node；K data block of each back end is encoded using the first correcting and eleting codes encryption algorithm, generates the first redundant data block；The data block of different data node is selected, and selects data block in each back end, is encoded using the second correcting and eleting codes encryption algorithm, the second redundant data block is generated；Wherein, K is the integer not less than two.The application can improve the overall usability of data in the case where ensuring local tolerance and cross-node tolerance, reduce carrying cost.The application also provides a kind of for restoring the method for data.
Description
Technical Field
The present application relates to a method for storing data, in particular to a method for a data node to store data, and also relates to a method for recovering data. The application also relates to a storage device for multi-node storage of data, and also relates to a storage device for recovery of data; the application also relates to an electronic device for multi-node data storage; the application also relates to an electronic device for recovering data.
Background
Most of cloud computing platforms adopt distributed systems, and in order to improve the disaster tolerance capability of the whole system, data can be backed up and stored in machine rooms in a plurality of different regions. When any computer room is not available, data of the whole cloud platform is still available. The general storage mode is a mode of mirror image backup.
Taking a system distributed in 3 rooms as an example, it may be set that each room can hold one copy of data. One problem with this is that data recovery is required across the network bandwidth of the computer room whenever there is data corruption, and generally, the bandwidth across the computer room is a scarce resource, and in order to alleviate this pressure, multiple copies of data can be placed in each computer room, but this consumes more storage resources. For example, 2 copies of data are placed per room in the case of 3 rooms, and 6 copies of data are placed in total, i.e., the total storage cost (overhead) is 6 times that of the data to be stored.
Therefore, the existing data storage mode of mirror image backup consumes a large amount of storage resources in order to save bandwidth when data is accessed across a computer room when the data is damaged.
Disclosure of Invention
The present application provides a method for data node to store data, so as to solve the above problems of the existing data storage method. The present application further provides a method for restoring data, a storage device for multi-node stored data, a storage device for restoring data, an electronic device for multi-node stored data, and an electronic device for restoring data.
The application provides a method for data node storage data, which is used for data storage of more than two data nodes and comprises the following steps:
dividing data belonging to the same data node into K data blocks with the same size, and setting the data blocks of different data nodes to be the same size;
encoding the K data blocks of each data node by adopting a first erasure code encoding algorithm to generate a first redundant data block;
selecting data blocks of different data nodes, selecting the data blocks at each data node, and coding by adopting a second erasure code coding algorithm to generate a second redundant data block;
wherein K is an integer not less than two.
Optionally, the encoding the K data blocks of each data node by using a first erasure coding algorithm, and generating a first redundant data block includes:
and according to the preset local fault tolerance of each data node, sequentially coding the data blocks stored in each data node by adopting a first erasure code algorithm to generate a first redundant data block.
Optionally, in the step of generating the first redundant data block, the local fault tolerance set by different data nodes is the same by sequentially encoding the data blocks stored in each data node by using a first erasure code algorithm according to the preset local fault tolerance of each data node.
Optionally, the encoding the K data blocks of each data node by using a first erasure coding algorithm, and generating a first redundant data block further includes:
and storing the first redundant data block in a data node where the data block generating the first redundant data block is located.
Optionally, in the step of encoding the K data blocks of each data node by using a first erasure coding algorithm to generate a first redundant data block, the K data blocks belonging to different data nodes are encoded by using different first erasure coding algorithms.
Optionally, the selecting data blocks of different data nodes, selecting a data block at each data node, and encoding by using a second erasure code encoding algorithm to generate a second redundant data block includes:
forming a cross-node global erasure code coding group by using data blocks of different data nodes;
and coding the cross-node global erasure code coding group by adopting a second erasure code algorithm according to the preset fault tolerance of each cross-node global erasure code coding group to obtain a second redundant data block of the cross-node global erasure code coding group.
Optionally, the selecting data blocks of different data nodes, selecting a data block at each data node, and encoding by using a second erasure code encoding algorithm to generate a second redundant data block, further includes:
and respectively storing the second redundant data blocks of the cross-node global erasure code coding group in different redundant data nodes.
Optionally, the cross-node global erasure coding group adopts different second erasure coding algorithms.
Optionally, the first erasure coding algorithm and the second erasure coding algorithm are different.
Optionally, the method further includes:
and carrying out third erasure code coding on a second redundant data block obtained by carrying out second erasure code coding on the data blocks of different data nodes.
Optionally, the performing erasure coding on the second redundant data block obtained by performing second erasure coding on the data blocks of different data nodes includes:
dividing second redundant data blocks obtained by performing second erasure code coding on data blocks of different data nodes into different redundant data node coding groups;
and according to the preset global local fault tolerance of each redundant data node, performing third erasure code coding on a second redundant data block of the same redundant remainder data node coding group to obtain a global first redundant data block.
Optionally, the method further includes storing the global first redundant data block in a redundant data node that generates the global first redundant data block.
Optionally, the method is used for a distributed storage system across computer rooms.
Optionally, the data node includes a storage resource of any one of the following areas or locations: racks, cabinets, rooms, or other storage resources that define a spatial region.
In addition, the present application also provides a method for recovering data, comprising:
acquiring information of damaged data blocks in the data node;
judging whether the number of the damaged data blocks is greater than a preset local fault tolerance or not;
if so, recovering the damaged data block of the data node by using the undamaged data blocks of other data nodes or redundant data nodes across nodes; wherein,
the other data nodes are data nodes except the data node participating in erasure code coding of the data block of the data node;
the redundant data node is used for storing a second redundant data block after data block erasure code coding of the node and other data nodes;
the uncorrupted data blocks and corrupted data blocks comprise pre-encoded data blocks or encoded second redundant data blocks participating in a cross-node global erasure code encoding group.
Optionally, after the step of recovering the damaged data block across nodes by using the good data blocks of other data nodes or the redundant data node, the method further includes:
returning to the step of judging whether the number of the damaged data blocks is greater than the preset local fault tolerance or not;
if not, the damaged data block is recovered by using the intact data block of the local erasure code coding group.
Optionally, before the recovering the damaged data block across nodes by using the good data blocks of the other data nodes or the redundant data node, the method further includes:
and recovering the corresponding data block or the second redundant data block by using the erasure code coding group of the data node or the redundant data node.
Optionally, the method is used for a distributed storage system crossing a computer room.
In addition, the application also provides a system for storing data by multiple nodes, which comprises more than two original data storage nodes and at least one global redundant data node;
each original data storage node is used for storing K data blocks with the same size and a first redundant data block generated by encoding the K data blocks of the data node through a first erasure code encoding algorithm;
the global redundant data node is used for storing data blocks selected from different original data nodes, selecting the data block at each original data node, and generating a second redundant data block by adopting a second erasure code coding algorithm for coding;
wherein K is an integer not less than two.
Optionally, the system further includes a global local redundant data node, configured to store global local redundant data obtained by performing third erasure coding on a second redundant data block obtained by performing second erasure coding on data blocks of different data nodes.
In addition, the present application also provides an electronic device for multi-node data storage, which includes a storage device and a processor, wherein the storage device stores instructions, and the instructions are loaded and executed by the processor to perform the following operations:
dividing data belonging to the same data node into K data blocks with the same size, and setting the data blocks of different data nodes to be the same size;
encoding the K data blocks of each data node by adopting a first erasure code encoding algorithm to generate a first redundant data block;
selecting data blocks of different data nodes, selecting the data blocks at each data node, and coding by adopting a second erasure code coding algorithm to generate a second redundant data block;
wherein K is an integer greater than two.
In addition, the present application also provides an electronic device for recovering data, which includes a storage device and a processor, wherein the storage device stores instructions, and the instructions are loaded and executed by the processor to perform the following operations:
acquiring information of damaged data blocks in the data nodes;
judging whether the number of the damaged data blocks is greater than a preset local fault tolerance or not;
if so, recovering the damaged data block by using other data nodes or redundant data nodes and the damaged data block to belong to the intact data block or the second redundant data block of the same cross-node global erasure code coding group.
In addition, the present application also provides a method for data node storage, which is used for data storage of more than two data nodes, and comprises the following steps:
for each data node, acquiring K data blocks with the same size of the node, and setting the data blocks of different data nodes to be the same size;
encoding the K data blocks of each data node by adopting a first erasure code encoding algorithm to generate a first redundant data block;
selecting data blocks of different data nodes, selecting the data blocks at each data node, and coding by adopting a second erasure code coding algorithm to generate a second redundant data block;
wherein K is an integer not less than two.
Compared with the prior art, the method for storing data by the data node has the following advantages: the method can improve the overall availability of data and reduce the storage cost under the condition of ensuring the local fault tolerance and the cross-node fault tolerance.
Compared with the prior art, the method for recovering the data has the following advantages: the data can be recovered under the condition that the data damage exceeds the local fault tolerance, but the cross-node fault tolerance requirement is met and the cross-node bandwidth is not remarkably increased, so that the effects of reducing the storage cost and improving the overall availability of the data are achieved.
Drawings
FIG. 1 is a flow diagram illustrating an embodiment of a method for a data node to store data;
FIG. 2 is a data storage diagram of an embodiment of a method for a data node to store data herein;
FIG. 3 is a data storage schematic diagram of an embodiment of a method for a data node to store data of the present application;
FIG. 4 is a schematic flow chart diagram of an embodiment of a method for recovering data of the present application.
Detailed Description
In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present application. This application is capable of implementation in many different ways than those herein set forth and of similar import by those skilled in the art without departing from the spirit of this application and is therefore not limited to the specific implementations disclosed below.
An embodiment of the present application provides a method for a data node to store data, a flowchart of which is shown in fig. 1, and includes the following steps:
step S101, dividing data belonging to the same data node into K data blocks with the same size, and setting the data blocks of different data nodes to be the same size.
The data node in the present application refers to different storage resources for storing data that should be divided according to areas or locations, and may be, for example, a storage resource of any one of the following locations or areas: racks, cabinets, rooms, or other storage resources that define spatial zones, etc. Specifically, the storage devices of different computer rooms may be regarded as different storage nodes (or data nodes), all the storage resources of the same administrative area or geographic location may be regarded as one data node, and the storage resources of different administrative areas or locations may be regarded as different data nodes.
For convenience of description, in this embodiment, data of the same data node is divided into K data blocks with the same size, and the data blocks of different data nodes are adjusted to be the same size. Wherein K is an integer greater than or equal to two.
For the data or data blocks stored in each (same) data node, the data or data blocks can be divided or packed into different data blocks according to a preset size, and for the data blocks which are still smaller than the preset size after being divided or packed, a method of filling with a preset filling value can be adopted to achieve the same effect as the size of other data blocks.
Meanwhile, the number of data blocks of different data nodes can be adjusted to be the same, and similarly, the effect that the number of the data blocks of different data nodes is the same can be achieved by adopting a data block filling mode under different conditions.
Adjusting the number of data blocks of different data nodes to be the same facilitates planning and maintenance of the entire storage system.
Step S102, encoding the K data blocks of each data node by adopting a first erasure code encoding algorithm to generate a first redundant data block.
Erasure Coding (EC) is a method of data protection by dividing data into segments, generating redundant data through a certain algorithm, expanding, encoding and storing redundant data blocks in different locations, such as disks, storage nodes or other geographical locations. Commonly used erasure code algorithms include RS (Reed-Solomon) codes, pattern array codes, longitudinal array codes, LDPC codes, or the like, and RS codes include dammond RS codes (Vandermonde RS codes), Cauchy RS codes (Cauchy RS codes), and the like.
For data blocks stored in the same data node, in order to ensure that the data blocks have certain local (node) data recovery capability, erasure code coding needs to be performed on the data blocks, that is, all the data blocks of the node are used as an erasure code coding group, and after the data blocks of the coding group are subjected to erasure code coding, when the number of damaged data blocks of the local (node) is smaller than a predesigned allowable range, the damaged data blocks can be recovered by using other good data blocks.
Specifically, in this embodiment, according to a preset local fault tolerance of each data node, a first erasure code algorithm is adopted to sequentially encode the data blocks stored in each data node to obtain first redundant data blocks, and the first redundant data blocks are respectively stored in the corresponding data nodes. Specifically, for each data node, according to the degree of tolerance required for data recovery (referred to as local tolerance in this embodiment, since redundant data after encoding the data block of the data node is stored in a node where the data blocks to be encoded are the same, the corresponding degree of tolerance is referred to as local tolerance, the corresponding redundant data block is referred to as a first redundant data block, which is also referred to as a local redundant data block, so as to distinguish a subsequent second redundant data block, which is also referred to as a global redundant data block), K data blocks of the data node are encoded, and a first redundant data block is generated. In the embodiment, the selected fault tolerance of all the data nodes is the same, so that the generated redundant data blocks are the same in number; the first erasure code algorithm selected by all the data nodes is also the same so as to simplify the difficulty and the calculation amount of subsequent data recovery. Of course, different data nodes may select different first erasure coding algorithms, which is not limited in this application.
In this embodiment, for each data node, the first redundant data block is stored in the data node where the data block that generates the first redundant data block is located.
In the present embodiment and the following embodiments, the qualifiers "first" and "second" in the first erasure correction code algorithm and the second erasure correction code algorithm are merely for distinguishing the erasure correction code encoding objects from each other, and do not represent the numbers nor have any other substantial meaning. For example, "first" is for encoding blocks of data within the same data node, "second" is for encoding blocks of data that exaggerate the selection of data nodes, and so on.
In this embodiment, the fault tolerance is the maximum amount of a damaged data block on the premise that the damaged data block is recovered by using other intact data blocks in the same erasure code coding group when the data block is damaged.
In the following description, a case where r (in this embodiment, r is an integer greater than or equal to 2) data nodes each having K (in this embodiment, K is not distinguished from K, and K is also an integer greater than or equal to 2) data blocks is taken as an example. For convenience of illustration, as shown in FIG. 2, the data chunks of data node 1 are named D1-1, D1-2 through D1-k, respectively; the data chunks for data node 2 are named D2-1, D2-2 through D2-k, … … through Dr-1, Dr-2 through Dr-k, respectively.
In this embodiment, the local fault tolerance of each data node is set to m, and corresponding setting may be performed in practical application as needed.
In the step, for k data blocks D1-1 and D1-2 stored in a data node 1, until D1-k, first erasure code coding is performed for m according to local fault tolerance to obtain m first redundant data blocks LP1-1 to LP1-m, and the first redundant data blocks LP1-1 to LP1-m and the data blocks D1-1 to D1-k are stored in the data node 1 together.
Similar operations are also performed for data blocks stored by other data nodes:
for the data blocks D2-1 and D2-2 stored in the data node 2, until k data blocks of D2-k are subjected to erasure code encoding for m according to the local fault tolerance to obtain m first redundant data blocks LP2-1 to LP2-m, and the first redundant data blocks LP2-1 to LP2-m and the data blocks D2-1 to D2-k are stored in the data node 2 together.
……
Until k data blocks Dr-1, Dr-2 stored in the data node r and up to Dr-k are subjected to erasure code encoding according to the local fault tolerance m to obtain m first redundant data blocks LPr-1 to LPr-m, and the first redundant data blocks LPr-1 to LPr-m and the data blocks Dr-1 to Dr-k are stored in the data node r together.
Therefore, when a certain data node has data blocks damaged and the number of the damaged data blocks (including data and redundancy speed) is less than or equal to m, the damaged data blocks can be recovered by using other k intact data blocks of the node, so that the local redundancy function of each data node is achieved.
And step S103, selecting data blocks of different data nodes, selecting a data block at each data node, and coding by adopting a second erasure code coding algorithm to generate a second redundant data block.
After the data blocks of the data nodes are subjected to local redundancy operation, the data blocks are subjected to redundancy processing among the data nodes.
Firstly, data blocks of different data nodes are utilized to form a cross-node global erasure code coding group. In this embodiment, a data block of each data node is used to form a cross-node global erasure coding group.
With continued reference to FIG. 2, a cross-node global erasure code coding group G1 is formed by the data block D1-1 of data node 1, the data blocks D2-1, … … of data node 2, and the data block Dr-1 of data node r; forming a cross-node global erasure code coding group G2 by using the data block D1-2 of the data node 1, the data block D2-2 of the data node 2 and the data block Dr-2 of the data node r; and so on until a cross-node global erasure code coding group Gk is formed by the data block D1-k of the data node 1, the data block D2-k of the data node 2 and the data block Dr-k of the data node r. So far, all data blocks of all r data nodes form a cross-node global erasure code encoding group.
And then, according to the preset fault tolerance of each cross-node global erasure code coding group, coding each cross-node global erasure code coding group by adopting a second erasure code algorithm to obtain a second redundant data block of the cross-node global erasure code coding group. In this embodiment, a redundant data block obtained by performing erasure coding on a data block selected across different data nodes is referred to as a second redundant data block, so as to distinguish the redundant data blocks generated by performing erasure coding on the data block of the same data node. In this embodiment, the error tolerance for different global erasure code encoding groups is set to be the same, and in other embodiments, it may also be set to be different. In addition, the second erasure coding algorithms adopted for different global erasure coding groups are the same, so that different second erasure coding algorithms can be selected by the assignee. In addition, the second erasure coding algorithm may or may not be the same as the first erasure coding algorithm. In this embodiment, the first erasure correction code algorithm and the second erasure correction code algorithm are the same.
For example, the fault tolerance of the cross-node global erasure code coding group is n (in practical application, the fault tolerance corresponding to each cross-node global erasure code coding group may be set as required), and erasure code coding is performed on the cross-node global erasure code coding group G1 to obtain second redundant data blocks GP1-1 to GPn-1; carrying out erasure code coding on the cross-node global erasure code coding group G2 to obtain second redundant data blocks GP1-2 to GPn-2; … … until the cross-node global erasure code coding group Gk is subjected to erasure code coding to obtain second redundant data blocks GP1-k to GPn-k.
And after the second redundant data blocks are obtained, the second redundant data blocks of the cross-node global erasure code coding group are respectively stored in different redundant data nodes. In the present embodiment, as shown in FIG. 3, the second redundant data blocks GP1-1 to GP1-k are stored in the redundant data node 1, and the second redundant data blocks GP2-1 to GP2-k are stored in the redundant data node 2; until a second redundant data block GPn-1 to GPn-k is stored at redundant data node n.
Therefore, the data block processing of all the data nodes can be recovered in the node and also can be recovered among different nodes, and the overall availability of the data is improved. And compared with the existing mirror image data storage mode, the storage cost is reduced.
Taking 3 computer rooms as an example, two of the computer rooms are data storage nodes, the other computer room is a redundant data node, the local fault tolerance of each computer room is 1, and under the condition that the number of data blocks is 5, the storage cost of data is as follows:
((5+1)*(2+1))/(5*2)＝1.8
the storage cost of the existing mirror image storage mode is 6, and it can be seen that the storage cost of the method for storing data by the data node provided by the application is only 30% of that of the existing mirror image storage mode.
In this embodiment, a data block of each data node is used to form a cross-node global erasure code encoding group, and second redundant data blocks of the cross-node global erasure code encoding group are respectively stored in different redundant data nodes.
In addition, according to the actual situation, such as the data bandwidth between nodes, a plurality of data blocks (e.g., 2 data blocks for each data node) can be selected from each data node to form a cross-node global erasure code encoding group. In addition, the second redundant data blocks of the cross-node global erasure code coding group can be stored in the same or multiple redundant data nodes. In any case, any variation of selecting data blocks of different data nodes for erasure coding is included in the scope of the idea of the present application, and those skilled in the art can make corresponding variations according to the teaching of the embodiments of the present application.
On the basis of the above operation, erasure coding can be performed again on the second redundant data block. Therefore, the storage cost is further reduced, meanwhile, the bandwidth between the nodes is saved, and the overall availability of data is improved.
Specifically, the second redundant data block obtained by performing erasure coding on the data blocks stored in different data nodes may be first divided into different redundant data node coding groups. For example, in the aforementioned example of r data nodes and n redundant data nodes, the second redundant data block of the same redundant data node is used as a redundant data node encoding group.
And carrying out erasure code coding on the second redundant data block of the same redundant remainder data node coding group, namely carrying out third erasure code coding on the second redundant data block of the same redundant data node according to the preset local fault tolerance corresponding to each redundant data node.
For example, with continued reference to FIG. 3, where the predetermined local fault tolerance of each redundant data node is m,
the second redundant data blocks GP1-1, GP1-2 through GP1-k of redundant data node 1 are encoded. Obtaining a global first redundant data block of a second redundant data block: GPLP1-1 to GPLP 1-m.
The second redundant data blocks GP2-1, GP2-2 through GP2-k of redundant data node 2 are encoded. Obtaining a global first redundant data block of a second redundant data block: GPLP2-1 to GPLP 2-m.
Until the second redundant data block GPn-1, GPn-2 through GPn-k of the redundant data node n is encoded. Obtaining a global first redundant data block of a second redundant data block: GPLPn-1 to GPLPn-m.
And after the global first redundant data block of the second redundant data block is obtained, storing the global first redundant data block of the same redundant data node coding group in the corresponding redundant data node. Storing GPLP1-1 through GPLP1-m to redundant data node 1; GPLPs 2-1 through GPLP2-m are stored to redundant data node 2 until GPLPn-1 through GPLPn-m are stored to redundant data node n.
The third erasure code coding and the local fault tolerance adopted for different redundant data node coding groups can be the same or different. The third erasure coding algorithm may be the same as or different from the first erasure coding algorithm and the second erasure coding algorithm; in this embodiment, the same third erasure code algorithm and local fault tolerance are used. And the third erasure code algorithm is the same as the first erasure code algorithm and the second erasure code algorithm.
The method of the embodiment can improve the overall availability of data and reduce the storage cost under the condition of ensuring the local fault tolerance and the cross-node fault tolerance.
The method provided by the embodiment can be applied to any multi-node data storage scene, such as a distributed storage system across a computer room. The memory space can be saved significantly while satisfying the redundancy requirements and without increasing the bandwidth of the machine room.
An embodiment of the present application further provides a method for recovering data, and an embodiment of the method is shown in fig. 4, and includes the following steps:
step S201, obtaining information of the damaged data block in the data node.
When data is damaged quickly, the storage system checks the relevant information of the damaged data, such as which node it belongs to, which data block, how many data blocks are damaged, and the like. This step acquires the above information for subsequent processing. The data blocks include a data block or a redundant data block and a second redundant data block.
In this embodiment, a case where the data blocks D1-1 to D1-m +1 of the data node 1 in the storage system shown in FIG. 3 are broken will be described as an example.
In the storage system, the data blocks of each data node are in the same erasure code coding group, and the data blocks of different data nodes in each column are in the same cross-node global erasure code coding group. D1-1 to Dr-k are data blocks, and LP1-1 to LPr-m are first redundant data blocks of an erasure code coding group consisting of data blocks of the same data node; GP1-1 to GPn-k are second redundant data blocks of cross-node global erasure code coding groups G1 to Gk composed of data blocks of different data nodes; GPLPs 1-1 to GPLPn-m are global first redundant data blocks of an erasure code coding group consisting of second redundant data blocks of the same redundant data node, m is less than or equal to k.
For example, for the above case, the information acquired in this step includes: data blocks D1-1 through D1-m +1 are corrupted within data node 1.
Step S202, judging whether the number of the damaged data blocks is larger than the preset local fault tolerance.
This step determines whether the number of data blocks damaged in the node is greater than the local fault tolerance for the case where local recovery can be performed.
For the data storage case shown in fig. 3, the preset local fault tolerance of each data node is m, and the number of damaged data blocks of data node 1 is m + 1. And comparing the m with the m. It is known that it is larger than m.
Step S203, recovering the damaged data block of the data node in a cross-node manner according to the undamaged data blocks of other data nodes or redundant data nodes; the other data nodes are data nodes except the data node participating in erasure code coding of the data block of the data node; the redundant data node is used for storing a second redundant data block after data block erasure code coding of the node and other data nodes; the uncorrupted data blocks and corrupted data blocks comprise pre-encoded data blocks or encoded second redundant data blocks participating in a cross-node global erasure code encoding group.
In this embodiment, the number of damaged data blocks of the data node 1 is greater than the local fault tolerance m, and this step is executed.
The corrupted data blocks D1-1 through D1-m +1 of data node 1 belong to cross-node global erasure code encoding groups G1 through Gm +1, respectively, across nodes.
D1-1 to D1-m +1 may be recovered by using the cross-node global erasure code encoding groups G1 to Gm +1, or a corresponding data block may be recovered by using any cross-node global erasure code encoding group of the cross-node global erasure code encoding groups G1 to Gm +1, or a data block may be recovered by using any cross-node global erasure code encoding group of the cross-node global erasure code encoding groups G1 to Gm + 1.
For example, in the embodiment, the intact data blocks of the data blocks D2-m +1 to Dr-m +1 of the data nodes 1 to r in the cross-node global erasure coding group G1-m +1 and the intact second redundant data blocks of the second redundant data blocks GP1-m +1 to GPn-m +1 of the redundant data nodes 1 to n are utilized to recover the data block D1-m + 1.
For the case that the number of damaged data blocks in the cross-node global erasure coding group of the cross-node is not enough to satisfy the requirement of recovering the damaged data blocks, for example, when the number of intact data blocks and second redundant data blocks in G1-m +1 is less than m, the corresponding data blocks or second redundant data blocks can be recovered by using the erasure coding group of any data node or redundant data node.
For example, in the case that the second redundant data block GP1-m +1 of redundant data node 1 is corrupted, the second redundant data block GP1-m +1 may be recovered using the intact second redundant data block and the global first redundant data block in the erasure code coding group (GP1-1 through GP1-m, GP1-m +2 through GP1-k, GPLP1-1 through GPLP1-m) of redundant data node 1.
By using the erasure code coding groups of the data nodes or the redundant data nodes, the global availability of the data can be further improved after the corresponding data blocks or the second redundant data blocks are recovered.
After recovering the corresponding data block or the second redundant data block by using the erasure code coding group of any data node or redundant data node, if the number of the undamaged data blocks in the cross-node global erasure code coding group of the cross-node meets the condition of recovering the damaged data block, the damaged data block is recovered by continuously using the intact data block or the second redundant data block of the cross-node global erasure code coding group of other data nodes or redundant data nodes and the damaged data block.
When the damaged data block in the node is recovered, the data can be further recovered by using the intact data block in the node.
Specifically, it may be determined again whether the number of damaged data blocks is greater than the preset local fault tolerance.
If the number of damaged data blocks is less than or equal to the local fault tolerance of the node after the damaged data blocks are recovered by using other data nodes and the damaged data blocks belonging to the same erasure code coding group and crossing nodes, the damaged data blocks are recovered by using the damaged data blocks of the erasure code coding group of the node.
And the bandwidth between the nodes can be saved by recovering the residual damaged data blocks by using the intact data blocks of the local erasure code coding group.
In this embodiment, after the data block D1-m +1 is recovered in the previous step, the number m of damaged data blocks is equal to the local fault tolerance of the data node, which is that other damaged data blocks D1-1 to D1-m can be recovered by using other intact data blocks in the erasure code encoding group of the node.
The method of the embodiment can recover the data under the condition that the data damage exceeds the local fault tolerance, but meets the cross-node fault tolerance requirement and does not remarkably increase the cross-node bandwidth, thereby achieving the effects of reducing the storage cost and improving the overall availability of the data.
The method of the present embodiment is preferably used for a distributed storage system across a computer room. The data can be recovered under the condition that the data damage exceeds the fault tolerance of the local machine room, but the requirement of the fault tolerance of the cross machine room is met and the bandwidth of the cross machine room is not remarkably increased, so that the effects of reducing the storage cost and improving the overall availability of the data are achieved.
In addition, the application also provides a system for storing data by multiple nodes, which comprises more than two original data storage nodes and at least one global redundant data node;
each original data storage node is used for storing K data blocks with the same size and a first redundant data block generated by encoding the K data blocks of the data node through a first erasure code encoding algorithm;
the global redundant data node is used for storing data blocks selected from different original data nodes, selecting the data block at each original data node, and generating a second redundant data block by adopting a second erasure code coding algorithm for coding;
wherein K is an integer not less than two.
The present application further provides a storage device for multi-node storage of data, the device storing instructions capable of being loaded by a processor and performing the following operations:
dividing data belonging to the same data node into K data blocks with the same size, and setting the data blocks of different data nodes to be the same size;
encoding the K data blocks of each data node by adopting a first erasure code encoding algorithm to generate a first redundant data block;
selecting data blocks of different data nodes, selecting the data blocks at each data node, and coding by adopting a second erasure code coding algorithm to generate a second redundant data block;
wherein K is an integer not less than two.
The present application further provides an electronic device for multi-node data storage, the electronic device comprising a storage device and a processor, the storage device storing instructions that, when loaded and executed by the processor, perform the following:
dividing data belonging to the same data node into K data blocks with the same size, and setting the data blocks of different data nodes to be the same size;
encoding the K data blocks of each data node by adopting a first erasure code encoding algorithm to generate a first redundant data block;
selecting data blocks of different data nodes, selecting the data blocks at each data node, and coding by adopting a second erasure code coding algorithm to generate a second redundant data block;
wherein K is an integer not less than two.
The present application further provides an electronic device for recovering data, the electronic device comprising a storage device and a processor, the storage device storing instructions that, when loaded and executed by the processor, perform the following:
acquiring information of damaged data blocks in the data nodes;
judging whether the number of the damaged data blocks is greater than a preset local fault tolerance or not;
if so, recovering the damaged data block by using other data nodes or redundant data nodes and the damaged data block to belong to the intact data block or the second redundant data block of the same cross-node global erasure code coding group.
In addition, the present application also provides a method for data node storage, which is used for data storage of more than two data nodes, and comprises the following steps:
for each data node, acquiring K data blocks with the same size of the node, and setting the data blocks of different data nodes to be the same size;
encoding the K data blocks of each data node by adopting a first erasure code encoding algorithm to generate a first redundant data block;
selecting data blocks of different data nodes, selecting the data blocks at each data node, and coding by adopting a second erasure code coding algorithm to generate a second redundant data block;
wherein K is an integer not less than two.
Although the present application has been described with reference to the preferred embodiments, it is not intended to limit the present application, and those skilled in the art can make variations and modifications without departing from the spirit and scope of the present application, therefore, the scope of the present application should be determined by the claims that follow.
In a typical configuration, a computing device includes one or more processors (CPUs), input/output interfaces, network interfaces, and memory.
The memory may include forms of volatile memory in a computer readable medium, Random Access Memory (RAM) and/or non-volatile memory, such as Read Only Memory (ROM) or flash memory (flash RAM). Memory is an example of a computer-readable medium.
1. Computer-readable media, including both non-transitory and non-transitory, removable and non-removable media, may implement information storage by any method or technology. The information may be computer readable instructions, data structures, modules of a program, or other data. Examples of computer storage media include, but are not limited to, phase change memory (PRAM), Static Random Access Memory (SRAM), Dynamic Random Access Memory (DRAM), other types of Random Access Memory (RAM), Read Only Memory (ROM), Electrically Erasable Programmable Read Only Memory (EEPROM), flash memory or other memory technology, compact disc read only memory (CD-ROM), Digital Versatile Discs (DVD) or other optical storage, magnetic cassettes, magnetic tape magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that can be used to store information that can be accessed by a computing device. As defined herein, computer readable media does not include non-transitory computer readable media (transient media), such as modulated data signals and carrier waves.
2. As will be appreciated by one skilled in the art, embodiments of the present application may be provided as a method, system, or computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein.
Claims (23)
1. A method for data node storage of data for data storage of two or more data nodes, comprising:
dividing data belonging to the same data node into K data blocks with the same size, and setting the data blocks of different data nodes to be the same size;
encoding the K data blocks of each data node by adopting a first erasure code encoding algorithm to generate a first redundant data block;
selecting data blocks of different data nodes, selecting the data blocks at each data node, and coding by adopting a second erasure code coding algorithm to generate a second redundant data block;
wherein K is an integer not less than two.
2. The method of claim 1, wherein the encoding the K data blocks of each data node using a first erasure coding algorithm to generate a first redundant data block comprises:
and according to the preset local fault tolerance of each data node, sequentially coding the data blocks stored in each data node by adopting a first erasure code algorithm to generate a first redundant data block.
3. The method as claimed in claim 2, wherein the step of sequentially encoding the stored data blocks of each data node by using a first erasure coding algorithm according to the preset local tolerance of each data node to generate the first redundant data block includes that the local tolerances set by different data nodes are the same.
4. The method as claimed in claim 1 or 2, wherein the encoding of the K data blocks of each data node by using the first erasure coding algorithm, and the generating of the first redundant data block further comprises:
and storing the first redundant data block in a data node where the data block generating the first redundant data block is located.
5. A method for a data node to store data according to claim 1 or 2, characterized by: and in the step of encoding the K data blocks of each data node by adopting a first erasure code encoding algorithm to generate a first redundant data block, encoding the K data blocks belonging to different data nodes by adopting different first erasure code algorithms.
6. The method of claim 1, wherein selecting data blocks of different data nodes, selecting a data block at each data node, encoding using a second erasure coding algorithm, and generating a second redundant data block comprises:
forming a cross-node global erasure code coding group by using data blocks of different data nodes;
and coding the cross-node global erasure code coding group by adopting a second erasure code algorithm according to the preset fault tolerance of each cross-node global erasure code coding group to obtain a second redundant data block of the cross-node global erasure code coding group.
7. The method of claim 6, wherein the selecting data blocks of different data nodes and selecting data blocks at each data node, encoding using a second erasure coding algorithm to generate a second redundant data block, further comprises:
and respectively storing the second redundant data blocks of the cross-node global erasure code coding group in different redundant data nodes.
8. The method of claim 6, wherein the second erasure coding algorithm employed by the cross-node global erasure coding group is different.
9. The method for a data node to store data according to claim 6 or 7, wherein the first and second erasure coding algorithms are different.
10. The method for a data node to store data as recited in claim 1, further comprising:
and carrying out third erasure code coding on a second redundant data block obtained by carrying out second erasure code coding on the data blocks of different data nodes.
11. The method of claim 10, wherein the erasure coding a second redundant data block obtained by second erasure coding a data block of a different data node comprises:
dividing second redundant data blocks obtained by performing second erasure code coding on data blocks of different data nodes into different redundant data node coding groups;
and according to the preset global local fault tolerance of each redundant data node, performing third erasure code coding on a second redundant data block of the same redundant remainder data node coding group to obtain a global first redundant data block.
12. The method of claim 10, further comprising storing a global first redundant data block in a redundant data node that generated the global first redundant data block.
13. The method for data node storage of data of claim 1, wherein the method is used in a distributed storage system across a computer room.
14. A method for a data node to store data according to any of claims 1 to 13, characterized in that the data node comprises storage resources of any of the following areas or locations: racks, cabinets, rooms, or other storage resources that define a spatial region.
15. A method for recovering data, comprising:
acquiring information of damaged data blocks in the data node;
judging whether the number of the damaged data blocks is greater than a preset local fault tolerance or not;
if so, recovering the damaged data block of the data node by using the undamaged data blocks of other data nodes or redundant data nodes across nodes; wherein,
the other data nodes are data nodes except the data node participating in erasure code coding of the data block of the data node;
the redundant data node is used for storing a second redundant data block after data block erasure code coding of the node and other data nodes;
the uncorrupted data blocks and corrupted data blocks comprise pre-encoded data blocks or encoded second redundant data blocks participating in a cross-node global erasure code encoding group.
16. The method for recovering data according to claim 15, wherein after the step of recovering the corrupted data blocks of the data node across nodes by using the uncorrupted data blocks of other data nodes or redundant data nodes, the method further comprises:
returning to the step of judging whether the number of the damaged data blocks is greater than the preset local fault tolerance or not;
if not, the damaged data block is recovered by using the intact data block of the local erasure code coding group.
17. The method for recovering data according to claim 15, wherein before the recovering the corrupted data blocks of the data node across the nodes using the uncorrupted data blocks of other data nodes or redundant data nodes, further comprising:
and recovering the corresponding data block or the second redundant data block by using the erasure code coding group of the data node or the redundant data node.
18. The method for recovering data of claim 15, used for a distributed storage system across a computer room.
19. A system for storing data by data nodes is characterized by comprising more than two original data storage nodes and at least one global redundant data node;
each original data storage node is used for storing K data blocks with the same size and a first redundant data block generated by encoding the K data blocks of the data node through a first erasure code encoding algorithm;
the global redundant data node is used for storing data blocks selected from different original data nodes, selecting the data block at each original data node, and generating a second redundant data block by adopting a second erasure code coding algorithm for coding;
wherein K is an integer not less than two.
20. The system according to claim 20, further comprising a global local redundant data node, configured to store global local redundant data obtained by performing a third erasure coding on a second redundant data block obtained by performing a second erasure coding on data blocks of different data nodes.
21. An electronic device for a data node to store data, comprising a storage device and a processor, the storage device storing instructions that, when loaded and executed by the processor, perform the following:
dividing data belonging to the same data node into K data blocks with the same size, and setting the data blocks of different data nodes to be the same size;
encoding the K data blocks of each data node by adopting a first erasure code encoding algorithm to generate a first redundant data block;
selecting data blocks of different data nodes, selecting the data blocks at each data node, and coding by adopting a second erasure code coding algorithm to generate a second redundant data block;
wherein K is an integer greater than two.
22. An electronic device for recovering data, comprising a storage device and a processor, the storage device storing instructions that, when loaded and executed by the processor, perform the following:
acquiring information of damaged data blocks in the data nodes;
judging whether the number of the damaged data blocks is greater than a preset local fault tolerance or not;
if so, recovering the damaged data block by using other data nodes or redundant data nodes and the damaged data block to belong to the intact data block or the second redundant data block of the same cross-node global erasure code coding group.
23. A method for data node storage of data for data storage of two or more data nodes, comprising:
for each data node, acquiring K data blocks with the same size of the node, and setting the data blocks of different data nodes to be the same size;
encoding the K data blocks of each data node by adopting a first erasure code encoding algorithm to generate a first redundant data block;
selecting data blocks of different data nodes, selecting the data blocks at each data node, and coding by adopting a second erasure code coding algorithm to generate a second redundant data block;
wherein K is an integer not less than two.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710777448.8A CN109426590A (en) | 2017-09-01 | 2017-09-01 | Method for the method for back end storing data and for restoring data |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710777448.8A CN109426590A (en) | 2017-09-01 | 2017-09-01 | Method for the method for back end storing data and for restoring data |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN109426590A true CN109426590A (en) | 2019-03-05 |
Family
ID=65505666
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201710777448.8A Pending CN109426590A (en) | 2017-09-01 | 2017-09-01 | Method for the method for back end storing data and for restoring data |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN109426590A (en) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112732164A (en) * | 2019-10-28 | 2021-04-30 | 北京白山耘科技有限公司 | Cross-node data group management method, device and medium |
| CN113536356A (en) * | 2021-07-30 | 2021-10-22 | 海宁奕斯伟集成电路设计有限公司 | Data verification method and distributed storage system |
| WO2023000686A1 (en) * | 2021-07-22 | 2023-01-26 | 华为技术有限公司 | Method and apparatus for data storage in storage system |
Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102546755A (en) * | 2011-12-12 | 2012-07-04 | 华中科技大学 | Data storage method of cloud storage system |
| CN102843212A (en) * | 2012-08-03 | 2012-12-26 | 中兴通讯股份有限公司 | Coding and decoding method and device |
| US20140380125A1 (en) * | 2013-06-25 | 2014-12-25 | Microsoft Corporation | Erasure coding across multiple zones |
| WO2016116377A1 (en) * | 2015-01-20 | 2016-07-28 | International Business Machines Corporation | Multiple erasure codes for distributed storage |
| US20160380650A1 (en) * | 2015-06-26 | 2016-12-29 | Microsoft Technology Licensing, Llc | Flexible erasure coding with enhanced local protection group structures |
| CN106776111A (en) * | 2017-01-06 | 2017-05-31 | 东北大学 | A kind of recovered cloud storage system based on LRC correcting and eleting codes |
| CN106776112A (en) * | 2017-02-09 | 2017-05-31 | 长安大学 | It is a kind of that coding method is repaired based on Pyramid yards of locality |
-
2017
- 2017-09-01 CN CN201710777448.8A patent/CN109426590A/en active Pending
Patent Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102546755A (en) * | 2011-12-12 | 2012-07-04 | 华中科技大学 | Data storage method of cloud storage system |
| CN102843212A (en) * | 2012-08-03 | 2012-12-26 | 中兴通讯股份有限公司 | Coding and decoding method and device |
| US20140380125A1 (en) * | 2013-06-25 | 2014-12-25 | Microsoft Corporation | Erasure coding across multiple zones |
| WO2016116377A1 (en) * | 2015-01-20 | 2016-07-28 | International Business Machines Corporation | Multiple erasure codes for distributed storage |
| US20160380650A1 (en) * | 2015-06-26 | 2016-12-29 | Microsoft Technology Licensing, Llc | Flexible erasure coding with enhanced local protection group structures |
| CN106776111A (en) * | 2017-01-06 | 2017-05-31 | 东北大学 | A kind of recovered cloud storage system based on LRC correcting and eleting codes |
| CN106776112A (en) * | 2017-02-09 | 2017-05-31 | 长安大学 | It is a kind of that coding method is repaired based on Pyramid yards of locality |
Non-Patent Citations (2)
| Title |
|---|
| JIE HAO等: "On the single-parity locally repairable codes with availability", 《2016 IEEE/CIC INTERNATIONAL CONFERENCE ON COMMUNICATIONS IN CHINA (ICCC)》 * |
| 周松: "面向数据密集型超级计算的基于纠删码的容错存储技术研究", 《中国优秀博硕士学位论文全文数据库(硕士) 信息科技辑》 * |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112732164A (en) * | 2019-10-28 | 2021-04-30 | 北京白山耘科技有限公司 | Cross-node data group management method, device and medium |
| WO2023000686A1 (en) * | 2021-07-22 | 2023-01-26 | 华为技术有限公司 | Method and apparatus for data storage in storage system |
| CN113536356A (en) * | 2021-07-30 | 2021-10-22 | 海宁奕斯伟集成电路设计有限公司 | Data verification method and distributed storage system |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US10289488B1 (en) | System and method for recovery of unrecoverable data with erasure coding and geo XOR | |
| US10503611B1 (en) | Data protection management for distributed storage | |
| US9983959B2 (en) | Erasure coding of data within a group of storage units based on connection characteristics | |
| US9251154B2 (en) | Priority based reliability mechanism for archived data | |
| US7739579B2 (en) | Storage system, control method, and program for enhancing reliability by storing data redundantly encoded | |
| CN103699494B (en) | A kind of date storage method, data storage device and distributed memory system | |
| US20160006461A1 (en) | Method and device for implementation data redundancy | |
| WO2020035088A3 (en) | Prioritizing shared blockchain data storage | |
| US11210169B2 (en) | Data storage method, apparatus, and system | |
| CN114153651B (en) | A data encoding method, device, equipment and medium | |
| WO2018000788A1 (en) | Data-storage method and apparatus, and data-recovery method and apparatus | |
| US11748197B2 (en) | Data storage methods and systems | |
| CN111782152A (en) | Data storage method, data recovery method, device, server and storage medium | |
| CN109426590A (en) | Method for the method for back end storing data and for restoring data | |
| WO2015195104A1 (en) | Distributed storage data recovery | |
| CN115098295A (en) | Data local recovery method, equipment and storage medium | |
| CN115113819A (en) | A data storage method, single-node server and device | |
| US12131051B2 (en) | Migrating data between different medium layers of a storage system | |
| CN109117292B (en) | Cluster storage method and device and cluster storage system | |
| Ivanichkina et al. | Mathematical methods and models of improving data storage reliability including those based on finite field theory | |
| CN118409717B (en) | Data distribution method, system, computer program product, equipment and medium | |
| WO2019076912A1 (en) | Systematic and xor-based coding technique for distributed storage systems | |
| CN107885615B (en) | Distributed storage data recovery method and system | |
| CN111984443B (en) | Encoding method, decoding method and corresponding device in distributed system environment | |
| CN114048061A (en) | Check block generation method and device |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination |