胡金平，李贵洋，江小玉，周 悦，韩鸿宇

(四川师范大学 计算机科学学院，成都 610101)

1 前 言

海量数据的增加导致存储系统应具有低价格和可扩展的优良特性.相比传统的集中式存储[1]，分布式存储系统[2]利用廉价的商用PC机和成熟的网络技术，形成了成本低廉且易扩展的存储系统.为保证数据的可靠性，分布式存储系统常利用多副本[3]和纠删码[4，5]这两种容错技术.前者较成熟且最简单，但空间利用率低；后者以其高容错能力，高空间利用率等优点得到学术界和工业界的关注，并广泛应用到Hadoop[6]、GFS[7]、Azure[8]等各大分布式存储系统中.

Reed-Solomon Codes[9，10]是具有MDS[11]性质的纠删码，能够达到理论上的最高容错能力和最低的存储代价，但存在修复成本高昂的问题.为了降低修复带宽，目前常用的有两种降低修复带宽的方式.一是Rashmi等人[12]提出了Piggybacking设计架构，其中将易于工程实现的双条带MDS码命名为Hitchhiker[13]码，并给出了三种Hitchhiker码的构造方案，适用于各种(k,r)参数配置.二是Gopalan 等人[14-16]分别提出了局部修复性编码(Locally Repairable Codes)，简称LRC.它通过添加局部校验来减少磁盘I/O，从而降低修复成本.目前RS码、LRC和Hitchhiker码都广泛应用于各大分布式存储系统中.例如：RS(6,3),RS(8,4),RS(10,4)分别应用到了Google文件系统[17]、Baidu Atlas云平台[18]和Facebook存储系统[19]中，在Hadoop分布式文件系统提供多种参数的RS(k,r)码[20]供用户选择；LRC应用在Azure和Hadoop中[21，22]，两者的编码方式有稍许差异；(10,4)-Hitchhiker已部署在Hadoop文件系统中.

目前Hitchhiker码只针对系统单元的修复进行了优化，而对校验单元未做处理.LRC虽能显著的降低单节点失效的修复带宽，但由于增……