面向多节点失效的纠删码及数据修复技术研究

作     者：林轩 

作者单位：国防科学技术大学 

学位级别：硕士

导师姓名：王意洁

授予年度：2014年

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：分布式存储系统 纠删码 延迟修复 多节点修复 

摘      要：在分布式存储系统中,基于纠删码的容错机制相比于基于副本的容错机制能够极大地节省数据存储开销。然而,纠删码修复所产生的大量数据传输影响了系统性能,阻碍了纠删码在实际分布式存储系统中的广泛应用。纠删码的修复方式分为立即修复和延迟修复两种,延迟修复相比于立即修复能够节省系统资源,因此成为目前主流的修复方式。然而,延迟修复将导致多节点失效更为常见。现有的纠删码和修复策略主要针对于单节点失效修复,在多节点失效修复时数据传输量大、速度慢。为降低多节点数据传输量、加快修复速度,对面向多节点失效的纠删码以及数据修复技术进行了深入研究。取得的主要研究进展如下:首先,针对已有纠删码在多节点修复时存在数据传输量大的问题,本文提出了一种面向多节点失效的分组修复码GRC。GRC码利用分组思想将整个条带分成若干组并在组内计算出多个局部编码块,来减少多节点修复时的数据传输量。在计算局部编码块时,通过控制生成矩阵,使得各组中序号相同的局部编码块能够合成全局编码块,合成的全局编码块和已有全局编码块共同维持纠删码容错度。根据GRC码的编码特征,本文提出针对GRC码的基于多阶段选择策略的解码算法GMCD以减少解码过程的数据传输量,优化系统性能。实验结果表明,与已有的典型纠删码RS码相比,GRC码将修复时数据传输量降低50%以上;与分组结构型纠删码BPC码相比,GRC码将修复时数据传输量降低15%-25%。其次,针对已有修复技术在多节点修复时速度慢的问题,本文提出了一种分组数据互换修复技术GDER。不同于传统集中式同时修复技术中将所有块发送到一个新生节点上进行解码,GDER将修复所用到的块平均分成两组,并各自发送到两个新生节点。两个新生节点分别计算得出中间数据,然后交换部分中间数据,使得新生节点本身计算得到的中间数据和从另一个新生节点接收得到的中间数据合成失效块。由于修复过程中两个节点并行地接收数据和进行解码计算,因此GDER的修复速度相比于传统集中式同时修复技术有近一倍的提高。此外,本文提出了一种以最小数据传输代价为目标的节点选择算法MDTNS以优化多节点修复性能。实验结果表明,与传统集中式同时修复技术相比,GDER在保持修复数据传输量较低的情况下,修复速度提高70%以上。最后,基于上述研究成果,设计并实现了一个基于分组修复码的分布容错存储原型系统Group CR。Group CR基于开源的分布式容错存储系统HDFS-RAID设计实现,含有丰富的纠删码编码算法,包括已有的GRC码、BPC码、RS码和XOR码,也能较容易地扩展支持其他的编码算法。此外,Group CR支持分组数据互换修复技术GDER,也能较容易地扩展支持其他的修复技术。大量真实环境下的实验表明,在采用星型修复技术时,分组修复码相比于RS码在修复过程中传输的数据量减少50%-60%,相比于BPC码在修复过程中传输的数据量减少15%-25%;在采用RS码和GRC码时,分组数据互换修复技术GDER比传统集中式同时修复技术在修复速度上均提高70%-80%,进一步验证了理论分析和模拟实验的结果。