论文部分内容阅读
当前，信息技术产业已从以计算设备为核心的计算时代进入到以存储设备为核心的存储时代，数据海量化成为了一种趋势。分布式存储以网络技术为基础，利用小型服务器甚至PC机来搭建存储池，从而以其廉价性和高扩展性等特点而适用于对数据的海量存储。但是由于分布式存储节点可用性并不高，因此如何保证高数据可靠性就成为亟待解决的问题。在存储系统中，保证数据可靠性主要依赖于数据容错技术，而数据容错的关键性问题是如何进行有效的数据修复，即存活节点尽可能少地消耗系统资源来修复失效节点的问题。本文就分布式存储容错中的修复机制进行了研究，主要研究成果如下：
(1) 分布式存储容错中修复问题的建模
在现阶段，较少工作采用网络流图这个数据工具来对分布式存储容错中修复过程进行建模，而且少数几个相关工作的模型都是针对分布式存储容错中较特殊的修复情形，缺乏普适性。因此，本文利用网络流图工具，提出了一个能够适用绝大多数容错修复情况下的数学模型。同时，本文引入了虚拟信源节点的思想，简化了流图分析。另外，本文还针对分布式存储修复机制的特点，专门在网络流图中引入了三段节点，精确刻画了分布式存储节点在修复过程中的特性。最后，本文利用该数学模型，证明了分布式存储容错中修复过程并不需要有存活节点之间的数据传输过程，从而为后面的修复机制的设计提供了一定的理论基础。
(2) 一种基于弹性的节点修复机制
在分布式存储容错修复问题上，已有的修复机制限制所有的待修复节点必须连接同样多的d个存活节点来完成修复，但在较为不稳定的网络环境中，待修复节点并不能保证总是能连接到d个存活节点。因此，本文提出了一种基于弹性的节点修复机制MFR，该机制能够让一个待修复节点Yj任意连接dj个节点来完成修复过程，不同的新节点Yi和Yj所对应的di和dj无需相等。这样可以使得新节点的修复过程更加灵活，从而适应不同的网络状况。同时，本文还针对MFR机制，利用网络流图模型计算出完成修复所消耗的修复带宽下界。最后本文为MFR设计了相应的随机线性编码算法，并保证该算法正确性的前提下，达到已知的修复带宽下界，因此该下界是紧致的，并且该算法是基于MFR机制的最优算法。
(3) 一种基于相互协作的多节修复机制
现有的一些较好的修复机制都是针对于单节点修复问题的，没有专门针对多节点同时修复的问题进行研究，然而多节点的同时修复问题在实际分布式存储系统中非常常见。本文针对多节点同时修复的问题，提出了一种基于相互协作的多节点修复机制MCR，该机制能够让一个待修复节点不再是独立地进行修复过程，而是所有待修复节点一起相互协助完成修复过程。本文还针对MCR机制，利用网络流图模型计算出完成修复所消耗的修复带宽下界，经过数值分析可以得知，MCR所耗费的修复带宽下界比起现有最好的修复算法减少10％，同时存储量亦减少20％。然后本文为MFR设计了相应的传输算法，并引入强MDS性质来构造出随机线性编码算法。最后本文证明了该算法正确性，且达到已知的修复带宽下界，因此该下界是紧致下界，并且该算法是基于MCR机制的最优算法。
(4) 非对称的多节点修复问题
已提出的MCR方案假设所有的恢复链路带宽消耗都是同样的，即对称修复。这个对称假设可能过强，因为非对称的情况不仅在实际情况中经常出现，而且更关键的是，多节点存储容错修复问题的最优解可能出现在非对称状况下。本文研究了非对称的多节点修复问题，通过考察该状况下的网络流图，并利用最大流-最小截定理，给出非对称的多节点修复时修复总带宽的下界。在发现该下界等于基于MCR的修复带宽下界后，我们得出结论：多节点同时修复的问题通过对称修复，总能够达到修复带宽消耗的最小值。这意味着，我们所设计的基于MCR的对称修复的编码算法和传输算法总是最优算法。