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

发布时间：2018-05-21 08:57

本文选题：分布式存储系统 + 多节点失效　；参考：《计算机研究与发展》2014年S2期

【摘要】：作为云计算重要基础的大规模分布式容错存储系统,采用纠删码作为数据冗余技术能比多副本技术以更低的存储开销获得相同的数据可靠性.然而,过高的修复成本使纠删码技术在实际中的应用受到限制.已有的改进工作虽然可以降低成本,但在多节点失效修复的成本过高.提出一种适用于多节点失效的高容错低修复成本纠删码——分组修复码(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%存储空间.
[Abstract]:Large scale distributed fault-tolerant storage system, which is an important foundation of cloud computing, can obtain the same data reliability with erasure code as data redundancy technology with lower storage cost than multi-replica technology. However, the high repair cost limits the application of erasure code in practice. Although the existing improvement work can reduce the cost, the cost of multi-node failure repair is too high. In this paper, a high fault-tolerant and low cost erasure code for multi-node failure is proposed. The block repair code group repairable codesGRC code can significantly reduce the amount of data to be transmitted by grouping the bar band and adding the block code block. Thus, the valuable network bandwidth and disk I / O resource / GRC code can be saved to reduce the repair cost and maintain a good fault-tolerant capability in the event of multi-node failure. According to the characteristics of GRC codes, a greedy strategy based decode algorithm based on greedy strategy based decode algorithm is proposed to optimize the repair process by ensuring the minimum repair cost of each failure block. The experimental results show that compared with RS code, GRC code will reduce the bandwidth of repair network and the disk I / O by 50%, increase the repair speed by 75% and increase the storage space by 21%. Compared with LRC code, GRC code will reduce the bandwidth of the repair network and the disk I / O by 35% and 45% respectively, increase the repair speed by 40% and 50%, and only need to increase the storage space by 13%. Compared with basic pyramid codebook BPC, GRC code will reduce the bandwidth of repair network and disk I / O by 15%, increase repair speed by 20% and increase storage space by only 6%.
【作者单位】：并行与分布处理国家重点实验室(国防科学技术大学计算机学院);
【基金】：国家自然科学基金项目(61379052);国家自然科学基金项目(61402509) 国家“八六三”高技术研究发展计划基金项目(2013AA01A213) 湖南省自然科学杰出青年基金项目(14JJ1026) 教育部高等学校博士学科点专项科研基金资助项目(20124307110015)
【分类号】：TP333;TP302.8

【参考文献】