论文部分内容阅读
分布式存储系统通常使用副本技术来实现数据的可靠性。副本实现简单,但系统冗余度太高,只能通过增加拷贝数量来提高数据存储的可靠性。近些年,纠删码被用来替代副本技术以减少存储开销[1]。Reed-Solomon(RS)码具有非常高的存储效率,所以被广泛应用于生产环境。在大规模的分布式系统中,存储节点发生故障是很频繁的[2][3]。在故障节点修复过程中网络产生的通信量被称为修复带宽。在Facebook,8%的数据采取了纠删码存储方案,在修复故障节点过程中产生的修复带宽约占网络总流量的20%[4]。Dimakis等人将如何减少故障节点的修复带宽称为修复问题[5]。传统修复方案通常将k个存活节点的数据下载到新节点,然后新节点再修复出故障节点的数据[6]。这个过程会导致很大的带宽开销,甚至导致网络阻塞的发生。在存储节点发生故障频繁的大规模分布式存储系统中,数据维护带来的大通信量,导致节点故障难以容忍。网络编码和干扰对齐是优化修复带宽的理论基础。在网络编码的基础上,Dimakis等人将分布式存储系统抽象为一个有向图,然后通过网络信息流中的最大流最小割理论,给出了纠删码的最小修复带宽下界,并提出了再生码的概念[6]。Shah等人证明了干扰对齐技术在最小存储再生码的编码方案构造中的必要性[7]。相对广义汉明重量理论,源于对第二类窃听信道的研究[8]。第二类窃听信道模型和纠删码的修复模型非常相似。该理论对优化修复带宽具有很好的指导价值,应用在分布式存储系统中,可以研究在对r份数据进行恢复时,最少需要的d_r份编码消息,从而降低数据恢复时的带宽资源,提高系统性能。本文在网络编码的基础上,使用相对广义汉明重量来优化修复带宽,研究内容包括:1)概述了纠删码的标量模型和矢量模型。相比于标量模型,矢量模型可以将编解码过程简化为XOR运算,提高计算性能,同时矢量模型是优化MDS码修复带宽性能的基础。本文基于有限域上元素的性质,分析了如何将标量纠删码转化为矢量纠删码。2)分析了网络编码及干扰对齐优化故障节点修复带宽的工作原理,通过举例说明了局部干扰对齐怎样有效地优化修复带宽性能,但得到的结果却不是最优的,并分析了局部干扰对齐的不足之处。3)通过借鉴相对广义汉明重量的推导过程及思想,利用概率论和互信息量对单节点最小修复带宽进行了推导,给出了单系统节点修复带宽的下界限,并将该结论推广到了故障校验节点的修复问题。