Fractional Repetition Code Constructs That Can Efficiently Repair Failed Nodes

With the rapid development of digital information echnology,the era of data technology has quietly arrived.How to store massive Data safely and reliably has become a research hotspot.The traditional storage method mainly use centralized storage,but its equipment is expensive and the storage capacity is limited and it has been unable to adapt to large-scale data storage.Distributed storage has gradually become the mainstream of data storage method because of its advantages such as low equipment price,large storage capacity and easy expansion.However,its storage nodes are prone to failure,resulting in data loss,so the reliable storage of data in the distributed storage system has become the focus.The main fault-tolerant methods in distributed storage system are replication and erasure codes strategies.The replication strategy is simple and reliable,but its storage overhead is large.The erasure code strategy can effectively reduce the storage overhead,but its repair bandwidth overhead and computational complexity are large.Regenerative code pioneered the idea of network coding into distributed storage.Regenerative codes need to connect more surviving nodes to repair failed nodes,which leads to high repair locality.Fractional Repetition(FR)codes have been widely used in distributed storage systems because of their precise uncoded repair of failure nodes,low repair bandwidth overhead and low repair locality.This paper focuses on the research of partial duplicate codes in distributed storage system,and the main research contents are as follows:(1)A construction algorithm based on Hadamard Grouping Fractional Repetition(HGFR)code is proposed,which can reduce the bandwidth overhead when repairing the fault nodes.It can tolerate multi-node faults and realize the local repair of the fault nodes,thus effectively reducing the algorithm complexity.Specifically,based on the 8th order Hadamard matrix,the FR code is constructed by grouping,the rows of the matrix represent the storage nodes and the columns represent the stored data blocks.Theoretical analysis shows that compared with Reed-Solomon codes and simple Regenerating codes,the designed HGFR codes have lower repair bandwidth and repair locality.At the same time,there is no need to encode and decode to repair the failure node,and its computational complexity is low.(2)Considering that most of the existing Fractional Repetition code construction algorithms have fixed parameters,storage capacity and repetition cannot be changed,and it cannot flexibly adapt to the storage requirements.A construction algorithm of Fractional Repetition based on shadow(FRS)code in combinatorial mathematics is proposed.The FRS codes can be constructed with appropriate storage capacity and repeatability,and the heterogeneous Fractional Repetition codes can be constructed by simple transformation of the correlation matrix.Compared with the existing Fractional Repetition codes,the fault tolerance of FRS codes is significantly improved,the repair locality is reduced,and the storage reliability of the system is improved.Compared with RS code and SRC code,the designed FRS code has lower repair bandwidth overhead and computational complexity,which reduces the repair time,and it is more suitable for the needs of distributed storage system.(3)Two algorithms for constructing heterogeneous Fractional Repetition codes based on graphs are proposed.The heterogeneous FR codes are constructed based on the K-regular complete graph,and the repetition and storage capacity are selected through the selection of the K-regular complete graph.The homogeneous FR codes can be transformed into heterogeneous FR codes through the simple transformation of the correlation matrix.Furthermore,considering that the scale of distributed storage system will continue to increase and the distributed storage system will be upgraded and extended,a scalable heterogeneous FR code based on Fano graph is proposed.Without changing the existing data storage structure,storage nodes can be increased by directly flipping the graph and translating the graph,which significantly enhances the system's scalability and is suitable for further expansion of distributed storage system.Compared with RS codes,the repair locality and repair bandwidth overhead of the two heterogeneous FR codes are further reduced,and the scalability is stronger.