文档介绍：基于分布式存储系统的Reed―Solomon算法优化
摘要：随着存储规模的增大和信息节点的增多，基于分布式存储系统的磁盘发生故障的概率越来越高。为了增强系统的可靠性，我们通过RS算法引入冗余数据。随后该研究针对
基于分布式存储系统的Reed―Solomon算法优化
摘要：随着存储规模的增大和信息节点的增多，基于分布式存储系统的磁盘发生故障的概率越来越高。为了增强系统的可靠性，我们通过RS算法引入冗余数据。随后该研究针对传统RS码的生成矩阵做出了一些改进，使得生成矩阵1的数目减少，优化了编码解码的速度。
关键词：分布式存储系统纠删码RS码冗余数
据
中图分类号：TP393文献标识码：A文章编号：
1672-3791（2014）08（c）-0020-02
1CauchyRS编码矩阵优化
原来的Cauchy矩阵被认为是无差异的，算法复杂度一样。该研究给出了一种构建Cauchy编码矩阵的算法。我们把编译结果和原来的CRS码[1]和其他一些阵列奇偶校验码做以比较。
假设o表示每一个编码矩阵中“1”的平均数目。那么在计算每一个冗余包所需要进行的异或运算次数为。举例来说，对于图1的编码矩阵来说，“1”的总
数目为47个。剩余编码矩阵一共有
6行，，
。
考虑另外一种构造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测试结果
随后我们把通过上一章得到的编码矩阵和其他类
型的编码算法进行比较：CauchyRS（Original），CauchyRS（GC），CauchyRS（BC）和Star-Code[2]。
所有CRS类型的码中，CRS（GC）的表现最好，尽管它的编码复杂度也会随着n的增大而降低，和其他两个类型