自适应可分解部分重复码的扩展构造

Extended Construction of Adaptive-and-resolvable Fractional Repetition Codes

部分重复(Fractional Repetition,FR)码能够实现精确无编码修复,修复复杂度低且修复带宽成本小。在动态分布式存储系统中,要求FR码的节点存储开销和数据块重复度会随机动态变化。为了使FR码更灵活地适应动态分布式存储系统,该文提出利用超图实现自适应可分解FR码的扩展构造方法。具体地,建立超图中边和顶点与FR码中节点和数据块的对应关系,通过增加或删除超图中对应边和顶点,实现超图的扩展构造,进而得到存储系统规模和存储文件规模变化时自适应可分解FR码的扩展构造。基于这种方法,能够扩展构造出给定参数范围内所有自适应可分解FR码,列举了存储节点数20以内的所有参数。自适应可分解FR码与常见的简单再生码(Simple Regenerating Codes,SRC)和RS(Reed-Solomon)码相比,在修复局部性和修复带宽开销方面具有一定优势。

Fractional repetition(FR)codes can achieve exact uncoded repair for failed nodes,with lower repair computational complexity and repair bandwidth overhead.In dynamic distributed storage system,node storage overhead and coded packets repetition degree of FR codes will change randomly and dynamically.In order to make FR codes more flexible to adapt to dynamic distributed storage system,we propose the extended construction method of adaptive-and-resolvable FR codes by hypergraph.Specifically,the corresponding relationship between edges and vertices in hypergraph and nodes and data blocks in FR codes is established.By adding or deleting corresponding edges and vertices in hypergraph,the extended construction of hypergraph and adaptive-and-resolvable FR code are realized when file size and scale of distributed storage system change.Based on the scheme,all adaptive-and-resolvable FR codes within given parameter ranges can be constructed by extension,and all the parameter within 20 storage nodes are listed.Compared with Simple Regenerating Codes(SRC)and Reed-Solomon(RS)codes,the adaptive-and-resolvable FR codes have some advantages in repair locality and repair bandwidth overhead.