双解码技巧

双重编解码算法对比 概述

双重编解码算法是实现数据保护的关键技术。磁盘阵列中常用的算法是RAID6，属于Reed-solomon算法。RAID6算法计算复杂度高，往往需要硬件加速单元的支持。随着闪存技术的发展，新的编解码技术层出不穷，因此有必要了解常见阵列技术的双重编解码算法。一般来说，常见的双重编解码算法有三种:

1.二维(2D)奇偶校验方法

2.奇偶码校验方法

3.里德-所罗门码验证方法

下面将详细解释这三种算法的原理，然后比较这三种算法的性能和计算复杂度。

二维奇偶校验算法

二维奇偶校验方法将数据磁盘组织成mXn矩阵，然后分别在水平和垂直方向进行奇偶校验编码。如果有mXn个数据磁盘，则用于存储校验信息的磁盘数为m+n，二维奇偶校验采用简单的异或运算，易于实现。二维奇偶校验算法的原理如下图所示:

这种方式的磁盘冗余率为:

(m+n)/(mXn+m+n)

空之间的利用率为:

(mXn)/(mXn+m+n)

可以看出，这种算法的计算复杂度很低，但是需要的冗余磁盘数量很大。例如，对于12(3X4)个磁盘的阵列，该算法需要7个冗余磁盘，而传统的RAID6算法只需要2个冗余磁盘。

EVEN-ODD编解码算法

这种编码方式利用水平冗余和对角冗余来设计校验码，如下图所示:

水平检查

对角线检查

对于m个数据磁盘，这种编码方式需要两个冗余磁盘，编码方式采用常见的异或计算方式。冗余磁盘是一种常见的RAID5级别检查算法；另一个冗余磁盘是对角线编码算法。XDP在EMCXtremIO全闪存阵列中采用了这种算法(请参考文章“分析XtremIO的XDP技术”)。

在传统的磁盘阵列中，这种算法的应用受到限制。每次数据更新都会转换成“读-修改-写”的复杂耗时的 *** 作，小写性能会变得很低。但是在全闪存阵列中，情况就变得很不一样了，小写数据的问题不存在了，但是这个算法反而有了用武之地。

Reed-Solomon编码算法

里德-所罗门编码算法是现在RAID6采用的算法。其基本原理如下图所示:

该算法的编码过程描述如下(具体算法请参考RAID6算法分析):

p编码是通过异或运算得到的，类似于RAID5。

通过加权系数相乘相加得到q码，可以和P码形成两个方程，允许两个磁盘同时失效。

采用条带化数据存储模式。

需要两个冗余磁盘，属于最优编码的范畴。

三种编解码算法性能对比

从理论分析可以看出，这三种编解码算法具有不同的IO性能。其中，2D编码最简单，奇偶编码次之，RS编码最复杂。当系统中存在故障磁盘时，三种算法具有不同的数据恢复计算复杂度。下图显示了一个磁盘损坏和两个磁盘损坏时三种算法的计算复杂度。红线是RS算法，绿线是EO算法，白线是2D算法。(需要注意的是，横轴不是时间，是盘数；纵轴是计算复杂度)

单个磁盘损坏时数据恢复的计算复杂度(X轴:磁盘数量，Y轴:复杂度)

两个磁盘损坏时数据恢复的计算复杂度(X轴:磁盘数量，Y轴:复杂度)

从上图可以看出，三种双误码中，2D译码最简单，奇偶次之，RS译码最复杂。

磁盘存储阵列中三种编解码算法的比较结果如下表所示:

综上所述，在磁盘阵列应用领域，我们可以得出以下结论:

2D编码方法简单易行，但构造的磁盘阵列性价比低(不是最优冗余编码)。

RS编解码比EVENT-ODD更复杂，通常需要硬件电路实现。而RS码具有良好的小写性能，因此适用于软硬件优化(指令加速)的阵列。

奇偶编码和翻译过程比RS码简单，只有异或运算，但小写性能差。因此，奇偶校验适用于实时性强的连续数据存储。

随着闪存存储的发展，存储介质的特性发生了实质性的变化，因此最优编解码算法也会发生变化。不适用于磁盘阵列的EO算法，却能在闪存存储中大放异彩。