论文部分内容阅读
当前,信息技术产业已从以计算设备为核心的计算时代进入到以存储设备为核心的存储时代,数据海量化成为了一种趋势。分布式存储以网络技术为基础,主要利用小型服务器甚至PC机来搭建存储池,从而以其廉价性和高扩展性等特点而适用于对数据的海量存储。但是由于分布式存储节点的可用性不高,因此如何保证数据可靠性就成为亟待解决的问题。在存储系统中,保证数据可靠性主要依赖于数据容错技术,而数据容错的关键性问题是如何进行有效的数据修复,使得修复失效节点所消耗系统资源尽可能少。本文研究了基于网络编码的分布式存储容错中的修复机制,主要研究内容与贡献如下：(1)分布式存储容错中修复问题的建模本文将分布式存储数据修复问题抽象为基于网络流图的数据传输模型,以便于利用网络流相关理论来分析修复带宽下界。该模型中引入了虚拟信源节点的思想,将分布式存储容错中连续的多次修复转变为多个独立的单次修复,从而很大程度上简化了问题的分析。利用该数学模型,本文证明了修复过程中存活节点之间并不需要数据传输,为实际修复机制的设计提供了一定的理论基础。(2)一种基于弹性的节点修复机制现有修复机制通常要求所有待修复节点必须连接相同数目的存活节点来完成修复。本文提出了一种基于弹性的节点修复机制(Multi-loss Flexible Recovery,MFR),使得每个待修复节点可以连接不同数目的存活节点来完成修复。针对MFR修复机制,本文分析了修复带宽的下界,设计了基于随机线性编码的修复算法,该算法达到了修复带宽下界。因此,该算法是基于MFR的带宽最优修复算法。经过数值分析知,在数据冗余度较低的情形,MFR所耗费的修复带宽比起现有最好的修复算法减少20%以上。(3)一种基于相互协作的多节点修复机制本文针对多节点同时修复的问题,提出了一种基于相互协作的节点修复机制(Mutually Cooperative Recovery, MCR)。针对MCR修复机制,分析了修复带宽的下界,并引入强(n,k)-性质构造了基于随机线性编码的修复算法,证明了该算法正确性且达到修复带宽下界,因此,该算法是基于MCR的带宽最优修复算法。经过数值分析知,MCR所耗费的修复带宽比起现有最好的修复算法减少10%,同时存储量亦减少20%。(4)非对称修复问题现有的修复模型均基于对称修复机制,即每条修复链路带宽消耗均相同。本文分析了基于非对称修复机制的修复带宽下界,并发现该下界大于等于已提出的MCR带宽最优算法的带宽消耗。因此在非对称修复问题中,该算法仍然是带宽最优修复算法。