GRC:一种适用于多节点失效的高容错低修复成本纠删码

• 全文链接
• 请求原文

作   者：

林轩;  王意洁;  裴晓强;  许方亮;  符永铨; 

作者机构：

并行与分布处理国家重点实验室(国防科学技术大学计算机学院); 

关键词：

纠删码;  数据修复;  多节点失效;  分组修复码;  分布式存储系统; 

期刊名称：

计算机研究与发展

基金项目：

长尾延迟优化的在线数据密集型计算运行环境支撑技术研究
海量不确定数据流的分布并行Skyline查询处理模型与算法研究

i s s n：

1000-1239

年卷期：

2014 年 S2 期

页   码：

172-181

摘   要：

作为云计算重要基础的大规模分布式容错存储系统,采用纠删码作为数据冗余技术能比多副本技术以更低的存储开销获得相同的数据可靠性.然而,过高的修复成本使纠删码技术在实际中的应用受到限制.已有的改进工作虽然可以降低成本,但在多节点失效修复的成本过高.提出一种适用于多节点失效的高容错低修复成本纠删码——分组修复码(group repairable codes,GRC).GRC码通过将条带分组并增加组编码块,显著减少了修复所要传输的数据量,从而节省了宝贵的网络带宽和磁盘I/O资源;GRC码通过多个组编码块在多节点失效时降低修复成本,且维持较好容错能力.根据GRC码的特征,提出基于贪心策略的解码算法(greedy strategy based decode algorithm,GSBD),GSBD通过保证每个失效块的修复成本最小以优化修复过程.实验结果显示,与RS码相比,GRC码将修复网络带宽和磁盘I/O分别降低50%~55%,修复速度提高75%~90%,仅需增加21%存储空间;与LRC码相比,GRC码将修复网络带宽和磁盘I/O分别降低35%~45%,修复速度提高40%~50%,仅需增加13%存储空间;与basic pyramid code(BPC)相比,GRC码将修复网络带宽和磁盘I/O降低15%~25%,修复速度提高20%~25%,仅需增加6%存储空间.