Research On Regenerating Codes With Low Complexy For Distributed Storage Systems

In distributed storage systems,the data redundancy mechanism can be introduced to resist da-ta loss in the case of node failures.Regenerating codes is a new data redundancy technology that has emerged in recent years.As the high storage efficiency and optimal repair bandwidth,regenerating codes have attracted a lot of attention.There are two important classes of regen-erating codes,the minimum storage regenerating(MSR)codes which require the minimum storage overhead and the minimum bandwidth regenerating(MBR)codes which require the minimum repair bandwidth.In practical distributed storage systems,in addition to optimize the storage overhead and repair bandwidth,there are other metrics that also need to be further optiamized.In this paper,we mainly focus on the update complexity and the number of sys-tematic nodes of high-rate MSR codes,as well as the disk I/O overhead and the computational overhead during the node repair of MBR codes.Firstly,we study the(k?2,k)MSR codes with the encoding matrices being diagonal,which have the optimal update and can be used to modify existing distributed storage systems which based on classic erasure codes.By intensively analyzed the(k+2,k)Hadamard MSR code proposed by Cadambe et al and its new constructing method and the new node repair strategy proposed by Tang et al.,we present two new(k+2,k)MSR codes with the coding matrices being diagonal,under a given node capacity,the number of systematic nodes of the two new(k+2,k)MSR codes attains the theoretical upper bounds proposed by Tamo et al.Secondly,we study the number of systematic nodes and the update complexity of(k+r,k)high-rate MSR codes.So far,the known(k+r,k)high-rate MSR codes with the largest number of systematic nodes does not have the optimal update property,and the ones with the optimal update do not have the largest number of systematic nodes.By intensively studying the type ? coding matrices given by Li et al.,we present a new type of coding matrices,which can lower the update complexity of the corresponding MSR code under the same conditions.Based on the new type encoding matrices and type ? encoding matrices introduced by Li et al.,we present a new(k+r,k)MSR code.Under a given node capacity,the new code has the largest number of systematic nodes,while the update complexity is lower than the other MSR codes with the same number of systematic nodes,and is near optimal.Finally,we study MBR codes with the Repair-by-Transfer property,in which both of the repair bandwidth and disk I/O overhead are equal to the node capacity,while the computa-tional overhead is zero,therefore it can be easily implemented in pactical distributed storage systems.This construction is based on a concatenation of an outer MDS code with an inner FR(fractional repetition)code.However,the node repair of FR codes is table-based,which requires the systems to maintain a repair table.In order to reduce the storage cost of the repair table,we present the quasi-cyclic fractional repetition(QC-FR)code,whose incident matrix is composed of cyclic matrices,and therefore can greatly reduce the storage cost of the repair table.Furthermore,we establish the connection between QC-LDPC codes and QC-FR codes.Based on the mature research results of QC-LDPC codes,we construct quasi-cyclic fractional repetition codes.