Study On The Construction Of Fractional Repetition Codes In Distributed Storage Systems

With the rapid development of Internet technology,information data is growing explosively.Owing to outstanding advantages of high throughput,high availability and high scalability in massive storage capacity,large-scale distributed storage systems have been widely deployed.However,node failures are inevitable in distributed storage systems.In order to ensure the reliability and availability of data storage,replication and erasure codes strategy are usually adopted.However,the storage overhead of replication mechanism is too high,and meanwhile the repair bandwidth overhead of erasure codes strategy is too large.Subsequently,Dimakis et al.proposed regenerating codes,which ensure lower storage overhead and repair bandwidth overhead.Locally repairable codes can ensure lower disk I/O overhead during repairing failed nodes.But regenerating codes and locally repairable codes have higher computational complexity and repairable time overhead during repairing.Fractional repetition(FR)codes can achieve better performances in repair bandwidth overhead,repair locality and computational complexity since exact uncoded repair for multiple node failures.Thus,the FR codes have been widely studied for distributed storage systems,characterized by the exact uncoded repair for multiple node failures.How to reduce repair bandwidth overhead,repair locality and computational complexity has been an urgent problem to be solved during repairing failed nodes.Considering the problems above,the construction of FR codes are studied in this paper,including the following contents:(1)A new coding scheme,termed as locally repairable codes based on FR codes,is proposed in this paper.Specifically,the proposed coding scheme divides nodes into multiple local groups.Then based on proposed construction algorithm of FR codes,the FR codes with repetition degree ?(28)2 are adopted in each local group.Locally repairable codes based on FR codes can achieve exact uncoded repair for single failed node in each local group,and rapid repair for multiple failed nodes in distributed storage systems.This coding scheme can improve reliability of distributed storage systems and repair efficiency of failed nodes.Furthermore,locally repairable codes based on FR codes have remarkable advantages in repair bandwidth overhead and repair locality.(2)Since traditional FR codes cannot be flexibly applied to dynamic distributed storage systems,a new construction scheme of adaptive-and-resolvable FR codes based on hypergraph coloring is proposed.Specifically,linear uniform regular hypergraph is constructed based on heuristic algorithm of hypergraph coloring proposed in this paper.Then edges and vertices in hypergraph correspond to nodes and coded packets of FR codes respectively to construct adaptive-and-resolvable FR codes.According to hypergraph coloring,adaptive-and-resolvable FR codes can achieve rapid repair for failed nodes.Further,adaptive-and-resolvable FR codes can be generalized to heterogeneous distributed storage systems.Adaptive-and-resolvable FR codes have lower computational complexity and shorter time overhead during repairing failed nodes,with remarkable advantages in repair locality and repair bandwidth overhead.