Study On Optimal Coding In Distributed Storage Systems

With the rapid development of information technology and the popularity of Internet,massive data have also emerged.How to manage and store massive data reliably has become a key point that needs to be solved.In current practical production,distributed storage technology is the most effective method for massive data storage.However,the scales of data storage systems are often very large,and node failures caused by equipment and disk failures are also very common.For this reason,it becomes a research focus to repair the faulty nodes efficiently and reliably in the storage systems.At present,the most common method is to adopt data redundancy strategy in distributed storage systems,including replication strategy and erasure coding strategy.Although both of these methods can ensure the reliability and availability of distributed storage systems,the two methods also have their own shortcomings.Concretely,the replication strategy requires a large amount of replicated data,inducing too large storage overhead.Erasure coding strategy can improve the performance of the system's storage overhead,but the cost of repair bandwidth is much higher.Based on Locally Repairable Codes(LRCs)and Fractional Repetition Code(FRC),two optimized coding schemes are proposed in this paper that can better adapt to distributed storage.The specific research contents are as follows:(1)At present,the research on LRCs in distributed storage systems indicates that,it is relatively easy to construct BLRCs with the optimal minimum distance,but under the minimum distance upper boundary condition,it is also difficult to construct the BLRCs with the optimal code rate.To this end,two construction methods for single-check BLRCs with the optimal minimum distance and optimal code rate with a unified generator matrix structure,are proposed in this paper.The linear codes obtained by the construction are BLRCs with locality and availability of information symbols,and each locally repair group has a parity symbol.Specifically,using block design in combinatorics,BLRCs with the optimal minimum distance can be constructed.In particular,when availability t =2 or locality r =2,the minimum distance and code rate can both satisfy the optimal boundary conditions and are the optimal BLRCs.Moreover compared with other existing optimal BLRCs,the BLRCs constructed in this paper perform better in terms of code length and code rate.Furthermore,using the method of identity matrix transformation,BLRCs with optimal minimum distance and optimal code rate for availability t =2 are also constructed.Compared with the existing BLRCs based on graph structure,this construction has the same characteristics of optimal minimum distance and optimal code rate,At the same time,this method has lower algorithm complexity than other methods.(2)The existing construction algorithms of FRC are complex,and the most of construction algorithms of FRC can only be applied to isomorphic distributed storage systems with the same capacity of each storage node.For this reason,two decomposable FRC construction algorithms are proposed in this paper.The constructed FRC parameters can be selected flexibly,which can meet the heterogeneity of the storage capacity of system nodes.The algorithm complexity is low,and the fault nodes can be repaired quickly and accurately according to the parallel class repair method.Specifically,the square network is used to construct FRC with repetition degree? =2.This method can construct homogeneous and heterogeneous FRC,and it is proved theoretically that the FRC based on the square network is generally good FRC.Moreover the FRC is with the optimal distance.Secondly,a cube network is used to construct FRC with repetition degree ? =3.Similarly,this method can construct FRC with homogeneous and heterogeneous node storage capacity respectively.Compared with the Reed-Solomon(RS)codes and the simple regeneration codes,the FRC based on the network construction has lower repair locality in the repair of the failure nodes without any finite domain calculation,and the repair computational complexity is lower and the repair efficiency is high.In addition,compared with the existing FRC construction algorithm,this construction method is flexibler in parameter selection and simpler in construction.