基于分布式存储系统的Reed—Solomon算法优化

陈浩

摘 要：随着存储规模的增大和信息节点的增多，基于分布式存储系统的磁盘发生故障的概率越来越高。为了增强系统的可靠性，我们通过RS算法引入冗余数据。随后该研究针对传统RS码的生成矩阵做出了一些改进，使得生成矩阵1的数目减少，优化了编码解码的速度。

关键词：分布式存储系统 纠删码 RS码 冗余数据

中图分类号：TP393 文献标识码：A 文章编号：1672-3791（2014）08（c）-0020-02

1 Cauchy RS编码矩阵优化

原来的Cauchy矩阵被认为是无差异的，算法复杂度一样。该研究给出了一种构建Cauchy编码矩阵的算法。我们把编译结果和原来的CRS码[1]和其他一些阵列奇偶校验码做以比较。

假设o表示每一个编码矩阵中“1”的平均数目。那么在计算每一个冗余包所需要进行的异或运算次数为。举例来说，对于图1的编码矩阵来说，“1”的总数目为47个。剩余编码矩阵一共有6行，o为7.83，则需要进行的异或运算次数平均为6.83次。

考虑另外一种构造Cauchy矩阵的方法：集合X取域中的前m个元素，Y取后n个元素。在我们给出的例子中，这个编码矩阵有54个“1”。这种随机产生矩阵比原来的编码矩阵的复杂度要高17%。

考虑三个参数n，m和w，把域中个元素分到集合X和Y中的方法总数为。我们列举了所有可能组合的情况，纵坐标表示的是编码算法复杂度，如图1所示：

首先，我们可以观察到当n的值越小影响就越大，这是因为n和m的选择受制于不等式，而n越小，在域上可供m选择的值越多，所以产生的差距也就越大；当n的值增大，矩阵选择所造成的差异逐渐减小。然后当n值增大时，CRS算法性能逐渐下降，这是因为当Cauchy矩阵的维度不断增大时，编码矩阵从域中所包含的元素越多。对于域中的每一个元素，它所包含的“1”的数目的变化范围在和之间。维度较小的矩阵可以尽可能多的包含“1”的数目为的元素，维度较大的矩阵则必须包含“1”的数目为的元素，所以它的计算复杂度较高。

2 测试结果

随后我们把通过上一章得到的编码矩阵和其他类型的编码算法进行比较：Cauchy RS（Original），Cauchy RS（GC），Cauchy RS（BC）和Star-Code[2]。

所有CRS类型的码中，CRS（GC）的表现最好，尽管它的编码复杂度也会随着n的增大而降低，和其他两个类型的CRS表现趋向一致。并且每次当为整数时，CRS（Original）和CRS（BC）的编码复杂度都会发生跳跃性变化，而CRS（GC）一直是平滑增长。

3 结语

该研究通过改善Cauchy矩阵的生成方式提高了编码效率。在用C语言实现CRS算法时只用了横向校验，这样每次在进行解码时都需要占据过多的带宽去下载所需要的数据块或者冗余块，如果我们考虑使用对角线校验，那么就可以进行混合修复，这样可以节约带宽。

参考文献

[1] Plank JS. A Tutorial on Reed-Solomon Coding for Fault-tolerance in Raid-like Systems [J]. Software ？Practice & Experience，1997，27（9）：995-1012.

[2] Blomer J， Kalfane M， Karpinski M， et al. An XOR-based Erasure-resilient Coding Scheme [J]. California， UC Berkeley， International Computer Science Institute Technical Reporttr-95-048，1995：1-19.