TECHNICAL FIELD

The present disclosure relates to the field of distributed storage, and in particularly, to data recovery for minimum storage regenerating code via product matrix construction.

BACKGROUND

With the rapid development of emerging technologies such as the Internet, big data and cloud computing in recent years, the demand for massive data storage has also proliferated; accordingly, distributed data storage systems are becoming the main stream for massive data storage. Distributed storage systems outperform single-node storage systems in the respects of high reliability, high availability and high scalability. In a distributed storage system, it is common that one or more nodes fail. Under such condition, the service of the entire system can be kept uninterrupted through redundancy techniques such as replication or erasure coding. Erasure coding has larger space efficiency than simple replication, hence it is widely adopted in industry like the distributed storage systems from Microsoft, Azure and OceanStore. Specially, maximum distance separable (MDS) erasure codes are preferred since they can maximize the storage efficiency.

When node failure happens, the distributed storage system should recover the lost data in time to maintain redundancy and avoid longtime “degraded reading” which means reading a plurality of non-original data segments and then calculating required data in one way or another. This is usually accomplished through replacing or repairing the failed node(s) and recovering data on the new node(s) i.e. the substitute node(s). Since initially the substitute node knows nothing about the lost data, it has to get “helper data” from the other non-failed node(s) i.e. surviving node(s) which is called “assistant node(s)”. In a busy storage system, the network bandwidth cost by downloading the helper data for data recovery, referred to as “recovery bandwidth” is crucial to the performance of the overall system. Therefore, it is necessary to consider and discuss the minimization of the recovery bandwidth when designing and optimizing a distributed storage system. Benefiting from the idea of network coding, regenerating code can minimize the recovery bandwidth for node failure. And among them, minimum storage regenerating (MSR) code is a very useful class of regenerating code, since it can maximize the storage efficiency, meanwhile minimizing the recovery bandwidth.

MSR code constructed via product matrix (PM) is an important type of MSR codes with a simple and ingenious arrangement. Unfortunately, original PM MSR code only addresses the data recovery for a single node failure. However, practical distributed storage systems prevalent to suffer from multiple node failures that happen concurrently. One solution is to recover the failed nodes one by one like the way to handle the single node failure, which is straightforward but wasteful in bandwidth resource. Another way is to repair the failed nodes jointly to minimize the total required bandwidth. Another advantage of concurrent recovery over single recovery is that the repairing can be deferred until the number of failed nodes reaches a threshold or the degraded reading has lasted for certain time, hence the overall repairing cost can be further reduced.

Some current research works have considered this problem from various aspects, and a method that can concurrent recovery a general number of failed nodes through the concept of “virtual symbols” proposed, which has also proved the lower bound of the bandwidth of concurrent recovery. But the method evolves solving complex equations, which is huge and difficult to implement. Besides, a proxy-assisted MSR code with which the assistant node does not need to encode the helper data before transmission was studied and the existence of such codes for single- and double-node failures were proved. However, the solution of concurrent recovery for any number of failed nodes and general coding parameters is still not proposed.

Another category of concurrent recovery strategies for multiple data blocks adopts cooperation between nodes, wherein substitute nodes first download helper data from surviving nodes and then exchange the information they have with each other. Through careful design of coding structure, the recovery bandwidth can be reduced or even achieve a theoretical lower bound. Although cooperative recovery can minimize the recovery bandwidth in theory, it will meet difficulties in practice. Such two-phase data exchange i.e. “first-download-then-exchange” increases the completion time and requires more overhead, thereby requiring complex protocols to control, which leads to error prone.

From practical point of view, the policies of data recovery can be divided into two classes: centralized and distributed. With the centralized policy, an agent may collect helper data, then reconstruct the lost data and finally upload the recovered data to the actual substitute nodes. Conversely, with the distributed policy, substitute nodes collect and reconstruct data by themselves without the help of the agency. There are also mixtures of both policies, like cooperative recovery mentioned above, but the complexity of its implementation is high. Most previous works fall into the centralized category, and only consider the bandwidth of collection of helper data. But actually the uploading of reconstructed data to also substitute nodes consumes bandwidth, which fails to be considered in the previous works. The impact of network topology on recovery bandwidth and recovery strategies was investigated by some research, however, only some simple network topologies including tandem, star and grid networks have numerical results.

In addition, current data recovery strategies all use as many assistant nodes as possible when reconstructing data so as to reduce recovery bandwidth. It has been proved in theory that when all normal nodes except failed nodes, say, when all “surviving node” participate the data recovery as assistant nodes, the bandwidth is minimized. However in practical systems, more evolved assistant nodes will mean more delay and overhead, hence it is not always optimal to bother more assistant nodes in the case of comprehensive consideration of various aspects of performance.

SUMMARY

A method of data recovery for a distributed storage system with minimum storage regenerating code constructed via product matrix construction is proposed to solve a technical problem that is to provide a data recovery method for a distributed storage system which can be used for concurrent recovery of multiple failed nodes in the distributed storage system.

A method of data recovery for a distributed storage system is used for data recovery of a failed node in the distributed storage system, and the distributed storage system adopts a decoding method of the distributed storage system. Two methods of data recovery with MSR code constructed via PM (PM MSR) are provided herein, including centralized and distributed modes. In the centralized mode of data recovery, the number of the assistant nodes is chosen according to the number of the failed nodes to be recovered and the collection of the helper data sub-blocks, the computation of the repair matrix and the reconstruction of the missing data are implemented by a central agent. In the distributed mode of data recovery, the number of the assistant nodes is chosen according to the number of the failed nodes to be recovered, each new node reconstructs the data blocks stored on the failed node that it substitutes, and the collection of the helper data sub-blocks, the computation of the repair matrix and the reconstruction of the missing data are implemented by each corresponding new node.

The data recovery method comprises the following steps:

Step 1: selecting assistant nodes from surviving nodes, calculating helper data sub-blocks by using the assistant nodes, and sending the helper data sub-blocks to a regenerating node, that is a node for data regenerating, the number of the selected assistant nodes being related to the number of the failed nodes to be recovered;

Step 2: calculating a repair matrix based on the PM MSR code and the missing data information; and

Step 3: obtaining the missing data blocks by multiplying the repair matrix with the helper data sub-blocks to implement the reconstruction of data blocks.

In the actual operation process, to obtain the repair matrix, it is necessary to add node information that does not include the missing block to the loss list, or replace the node information in the original loss list with the node information that does not include the missing block. For example, in distributed mode, a new node can not only reconstruct the data blocks stored on the failed node that it substitutes, but also the data blocks required by other new nodes. In this respect, the new node can choose to send the extra reconstructed data blocks to other new nodes as needed, so as to prevent the new nodes from reconstructing the data blocks by themselves. This can further reduce the recovery bandwidth and computing overhead.

The beneficial effect of the present disclosure is that by providing a method of data recovery for a distributed storage system with MSR code constructed via PM, one or more data blocks can be reconstructed at the same time, which overcomes the difficulty that the lower limit of the minimum recovery bandwidth theory is difficult to achieve, and does not require data exchange between the new nodes, and the data can be repaired under any number of failed nodes and reasonable encoding parameters.

