论文部分内容阅读
随着互联网技术的快速发展,信息数据呈爆炸性增长,大规模分布式存储系统以其高吞吐量、高可用性、高可扩展性等突出优势成为海量数据的有效存储手段。分布式存储系统中节点故障不可避免,通常采用复制和纠删码策略来提高数据存储的可靠性和有效性。然而,复制策略存储代价过高,纠删码修复带宽开销过大。Dimakis等人提出了再生码,保证系统具有较低存储开销的同时修复带宽开销较低。局部性修复编码保证故障节点修复具有较低的磁盘I/O开销。但再生码和局部性修复编码在节点故障修复过程中计算复杂度较高,修复时间较长。部分重复(Fractional Repetition,FR)码因对故障节点提供精确无编码修复而得到广泛研究,其修复带宽开销和修复局部性较低,并能有效降低修复故障节点的计算复杂度。如何降低分布式存储系统中故障节点修复过程的带宽开销和修复局部性,降低修复过程中计算复杂度和修复时间,是目前亟需解决的主要问题。考虑到多节点故障的快速修复,本文针对FR码的构造进行研究,主要研究内容如下:(1)提出一种基于FR码的局部性修复编码方案。具体地,采用重复度?(28)2的FR码构造算法构造FR码编码结构,基于该编码结构划分局部修复组。基于FR码的局部性修复编码能够实现局部修复组内单节点故障的精确无编码修复以及分布式存储系统中多节点故障的快速修复。该编码方案提高了系统可靠性和故障节点修复效率。基于FR码的局部性修复编码在保证节点存储开销前提下,有效降低了修复局部性和修复带宽开销。(2)提出一种自适应可分解FR码的构造方案。针对传统FR码不能灵活适用于动态分布式存储系统的问题,提出了一种基于超图染色的自适应可分解FR码构造方案。具体地,基于超图染色的启发式构造算法构造线性一致正则超图,将超图中链路和顶点分别对应FR码中节点和编码块,进一步得到自适应可分解FR码。通过超图染色实现了故障节点的精确快速修复,并将自适应可分解FR码推广到异构分布式存储系统中。自适应可分解FR码修复故障节点过程中计算复杂度低,修复时间短,同时具有较低的修复局部性和修复带宽开销。