信息存储系统教育部重点实验室 English Version

柳青博士的论文在期刊TOS发表

点击次数:发布时间:2017-10-24 16:47作者:

在导师冯丹教授的指导下,柳青博士与实验室施展老师、胡燏翀老师等人合作的论文《High-Performance General Functional Regenerating Codes with Near-Optimal Repair Bandwidth》发表在ACM Transaction On Storage (TOS) 期刊。ACM TOS 期刊是中国计算机学会推荐的A 类期刊,收录计算机存储领域的相关文章。

在存储系统中,纠删码技术以一种更加节省存储空间的方法保证了数据可靠性,因此被广泛地应用于CD/DVD、磁盘阵列和分布式系统等存储系统中。但同时,其在编码、解码时的巨大计算开销和数据重建时的高昂数据修复开销等弊端也制约了它的应用。近年来,如何提高编码速度和如何减少数据重建时的修复开销成为纠删码领域研究的重点和热点。

下图以Reed-Solomon(RS)码为例,指出了纠删码的修复开销。(5,3)-RS码在修复一个丢失数据块时需要其他三个数据块参与重建,从而引起三倍的磁盘I/O和网络流量。

论文《High-Performance General Functional Regenerating Codes with Near-Optimal Repair Bandwidth 》提出了GFR 码来解决修复开销大的问题。GFR码是一类基于随机线性编码的再生码,再生码是一类能够达到理论最小修复开销的编码方法。通过合理地选择参数并借助于一种启发式算法,GFR不仅在最小存储开销(存储开销和RS 码相同)的情况下达到了近似理论最优的修复开销,并能够通过增加其存储开销换取减少更多的修复开销。

论文还提出了一种经过调度的移位乘法SSM能够加速GFR码在编码、修复时的计算速度。

下图指出了GFR码具有近似理论最优的修复开销。

下图给出了基于SSM算法的GFR码修复速度,与传统的查表法(TABLE)、移位乘法(SHIFT)相比较。

   

Top