A Repair Framework For MDS Codes In Distributed Storage System

Distributed storage systems usually use replication to guarantee the reliability of data storage.Replication is simple,but introduces too much redundancy,only by increasing the number of copies to improve the reliability of data storage.In recent years,replication has been substituted for erasure codes to reduce storage overhead[1].Reed-Solomon(RS)codes are widely used in production environments because of high storage efficiency.In large-scale distributed systems,storage node failure is very frequent[2][3].The traffic generated in the network during node repair is called the repair bandwidth.In Facebook,8% data are stored using erasure codes.The repair bandwidth costs about 20% of the total network traffic[4].How to reduce repair bandwidth is referred to as repair problem by Dimakis et al[5].The traditional repair framework usually downloads the data of k surviving nodes to the new node,and then the new node reconstructs the data of the failed node[6].This framework leads to a lot of bandwidth overhead,and even leads to network congestion.In large-scale distributed storage systems where storage nodes frequently fail,the large amount of traffic caused by data maintenance leads to network congestion.Network coding and interference alignment are the theoretical basis for optimizing repair bandwidth.Based on network coding,Dimakis et al.turned the distributed storage system into a directed graph,and then through the maximum flow minimum cut theory in the network information flow,gave the lower bound of the minimum repair bandwidth[6].Shah et al.demonstrated interference alignment is a necessity for the construction of minimum storage codes[7].The relative generalized Hamming weight theory was proposed in the study of wiretap channel of type II[8].The repair problem model is very similar to the wiretap channel model of type II.Therefore,the relative generalized Hamming weight theory helps optimize repair bandwidth.Based on the relative generalized Hamming weight and network coding,this paper focuses on how to optimize the repair bandwidth,and research content includes:1)Scalar code model and vector code model are summarized.Compared with the scalar code model,the vector code model can simplify the encoding and decoding process to the XOR operation and improve the computing performance,and the vector code model isthe basis for optimizing the bandwidth performance of the MDS code.Therefore,this paper analyzes how to transform the scalar code model into the vector code model based on the operations of the elements on the finite field.2)Network coding and interference alignment are the theoretical basis for optimizing repair bandwidth.This paper analyzes how network coding and interference alignment optimize repair bandwidth,and why local interference alignment is not optimal by an example.3)Based on the idea of relative generalized Hamming weight,the lower bound of minimum repair bandwidth of single systematic node is deduced by using probability theory and mutual information,and the conclusion is generalized to the problem of repairing a parity check node failure.