论文部分内容阅读
分布式存储系统通过使用网络中多台机器上的存储设备,把数据分散存储在多个独立的节点上,从而实现对海量数据的存储。大规模存储系统中的节点因数目巨大而易频繁失效,为保证存储数据的可靠性,需要在系统中保存相当数量的冗余数据,以便在部分节点不可用时能够利用剩余的存活节点来重构原始文件;并且利用创建的冗余节点的数据使得失效节点得以修复。作为一种新的数据冗余技术,再生码因能有效地降低分布式系统中修复失效节点所消耗的带宽资源而成为研究的热点。目前,对单个失效节点进行修复的再生码方案已越来越完善,然而分布式存储系统中的修复通常是接连不断触发的,基于此本文主要研究失效节点的数目达到某一固定值时,多节点并行修复机制下的若干相关问题。首先,本文研究了多节点合作修复模型下满足最小存储点参数的编码形式。在Suh和Ramchandran利用通信系统中的干扰对齐技术构造的一类可精确修复单个失效节点的最小存储再生码的基础上,本文通过示例(n=7;k=3)码,说明了 Suh-Ramchandran码能够对多个失效的节点进行合作修复。同时,为了更清楚地表述一般参数(n=2k+s;k)下的多节点合作修复过程,基于Suh-Ramchandran码,本文重新描述并直接给出了此参数下的编码形式,并且证明了在该编码形式下,修复多个失效系统节点时仍可达到最优的修复带宽。其次,利用割型分析讨论了集中的多节点修复模型下的最小容量割,得到了更一般的最小容量割的数组表示形式,该形式包含了已知文献中的结果。根据新得到的最小容量割形式,利用线性规划的方法给出了存储-带宽理论界,过程更为简单且比已知文献中的边界关系更紧。另外,还给出了最小存储多节点再生码和最小带宽多节点再生码的参数表示。并与单节点修复模型和多节点合作修复模型做了比较,结果表明集中的多节点模型在修复多个失效节点时,需要的修复带宽最小。通过对一些特殊参数下存储和修复所需带宽资源的分析,给出了集中的多节点修复模型下满足最小存储多节点再生码和最小带宽多节点再生码参数的编码方案。最后,给出了一类连接少量特定的节点即可精确修复多个失效节点的再生码。已知Papailiopoulos等利用MDS码构造的简单再生码在可达到任意码率的同时,能够只使用系统中f个存活节点通过简单的异或运算来完成单个失效节点的精确修复。在此基础上,本文通过对简单再生码中校验数据的改造,得到了能够同时精确修复多个失效节点的新编码方式。这类改造的简单再生码的存储和修复带宽只与已设定的值f有关,并且随着f的增大,与节点存储的最小理论值接近。同时,在修复多个失效节点时,可直接获取剩余存活节点中存储的数据无需进行计算操作,修复运算简单且具有较好的局部修复性,所以可适用于分布式存储系统。