网络存储系统容错编码技术进展

3 阵列编码

上述几种编码各有优缺点，那么是否存在对于多指标同时最优的k容错编码方法呢？自文献[5]提出EVENODD码起，一大类只使用异或运算的阵列编码被提出并被人们广泛研究。

多维阵列或FULL码等二进制线性码每块磁盘只取一个逻辑单元进行校验运算。而阵列码则在每块磁盘上取多个逻辑单元，一起交叉进行校验运算。校验计算同2进制线性码一样，只使用二进制异或运算，但冗余度却可以与RS码相同。

3.1 EVENODD码

EVENODD码的想法很简单，每块磁盘中取若干单元，排成方阵，然后将这些单元分成不同的校验组，另外添加两块磁盘用于存储校验单元。所有校验组均使用简单的二进制奇偶校验。

水平校验与对角校验如表1所示。表1中D代表用户数据单元，P代表冗余校验单元。可以看出，Disk1—Disk5存储用户数据单元；Disk6、7存储冗余校验单元。Disk6的各单元为用户数据各行的水平校验和，而Disk7的各单元为用户数据的辅对角线校验和。

设存储用户数据盘的数目为p(如上例中p=5)，则系统包含p+2块磁盘，前p+1块磁盘中的最后一个单元为虚拟0元，故每盘实际包含p-1个单元，最后一块磁盘包含p个单元。可以证明，当p为素数时系统是双容错的。

简单计算可知此时的系统的冗余度为(2p-1)/((p+2)(p-1)+1)。由于最后的校验盘多出一个单元，所以冗余度稍稍大于最优的2/(p+2)。为了达到最优值，文献[5]中使用如下技巧：将多出的单元(即辅对角交验和)叠加到该盘其他单元上，构造MDS的EVENODD码如表2所示。

表2也可表示为如表3所示。

也就是说当第一辅对角校验和为1时，其他各对角校验为奇校验；当第一辅对角校验和为0时，其他各对角校验为偶校验。这就是它被命名为EVENODD码的原因。

3.2 RDP码

从表2可以看出，为了得到冗余最优，EVENODD码的辅对角线上的单元的更新复杂度很高。每次更新这些单元的数据时都要同时更新其他p个校验单元。对于双容错编码来说，最优值为2。文献[6]中构造的RDP编码将这些单元的更新复杂度均衡到每个单元，从而有效地消除了写操作中更新性能的不均衡。一个包含水平校验的对角线校验如表4所示。

与EVENODD不同处在于，做对角校验时也包含了水平校验单元的一列(因此，数据单元也比EVENODD少了一列)。

同样的，RDP的最后一个校验盘多出一个单元，使得整个系统不为MDS码。但RDP码的优势在于，简单地将多出的单元删去，系统仍然为双容错的。即得到如表5所示阵列。

从表5可以看出，所有数据单元的更新负载为2或3，分布比EVENODD码要均匀，不会产生由编码方式带来的额外"瓶颈"，但系统的平均更新复杂度是相同的。

3.3 Liberation码

从前面几种编码可以看出，所使用的方法都是水平校验加其他一种校验共同构成双容错。不同之处就在于"另一种校验"的不同选择。如将另一校验盘上的校验元看作一个"0"、"1"向量，每块数据盘上的单元对这些校验元的影响可用一个"0"、"1"矩阵来表示。如表5中的第1列的4个数据单元对Disk7中的各校验元的影响可表示为如图4所示矩阵。

在这种表示下，前面所说的更新复杂度就对应着矩阵中1的个数。于是构造一个双容错阵列码的问题就转变为：寻找若干个这样的矩阵，使得其中1的个数尽量少，并且任意2个之和为满秩。

在p为素数时，文献[7]中构造的Liberation码使得p×p阶矩阵1的数目不超过p+1，其构造的p个矩阵可简单地描述为：各对角线加一个额外单元。第k个矩阵的额外的1单元的位置可描述为(k(p-1)/2 Mod p,1+k(p=1)/2 Mod p)。得到的编码如表6所示。

3.4 PDHLatin码

前面这些编码为MDS码的充要条件均为：码长与素数相关(RDP为p+1，其他为p+2)。它们的双容错解码方法均为根据一个已知单元，然后通过校验关系与失效单元形成的链式关系依次恢复所有单元。这使人们理解到其容错能力的本质是任意两列都可以形成这样的关联结构。文献[8]中利用拉丁方构造了PDHLatin码，使得码长不再必须关联一个素数。

所谓拉丁方是指n×n的方阵中填入n个不同符号，使得每行每列的符号都不重复。显然拉丁方的每两列构成一个n元置换。所谓汉密尔顿拉丁方是指拉丁方的任何两列构成的置换为单环的。图5为一个9阶汉密尔顿拉丁方。

作者：林胜 刘晓光 王刚 来源：中兴通讯技术——2010年 第5期