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

从一个给定的汉密尔顿拉丁方，我们可以用与EVENODD码类似的方法构造编码，只不过各单元对于第二校验盘的校验关系不再依单元所在对角线位置决定，而是根据拉丁方相应位置的符号决定。根据图5，得到表7所示的PDHLatin码。

3.5 X码

上面介绍的几种编码方法虽然都达到了冗余的最优，但在更新复杂度方面均稍高于最优值，那么是否可以达到两者同时最优呢？文献[9]提出的X码是一种这样的双容错编码。

X码的想法也很简单，仍然是在阵列中采用主对角线和辅对角线两种校验，但是通过巧妙地将校验单元分布到各个磁盘中(而不是像其他方法中，校验单元被分离出来，独立存放于校验盘)，使得系统同时达到了两方面指标同时最优。

为了满足双容错的要求，X码也要求阵列中包含的列数(或说码长)为素数。码长为素数p的X码中，每一列包含p-2个用户数据单元，2个冗余校验单元。

3.6 B码

是否还存在与X码相同特性的其他编码方案呢？显然将两个X码阵列重叠，系统仍然保持最优冗余与最优更新复杂度。

这样得到的新编码，在磁盘数目不变的情况下，每块盘需要关联的单元数目加倍。而在实际中，为了简化实现，我们实际上需要每块盘关联的单元数目尽量少。对于n块磁盘，在保持最优冗余与最优更新复杂度的条件下，每块盘最少需要多少个单元来关联校验呢？文献[10]提出的B码在双容错的情况下很好地解决了这一问题。

通过将编码构造等同于图论中的完全图完美-因子分解问题。并根据图论已有的结论，给出一种各方面性能均达到最优的编码。依据一个完全图的一种完美1因子分解方案，我们可以构造如表8所示的双容错编码——B码。

这种编码，每块磁盘包含至多1个校验单元，并且只有一块磁盘不包含校验单元。它将n个符号的所有2元组分划为多列，并且满足双容错要求，因而在保持了最优冗余度与更新复杂度的前提下，码长达到最长。因而这种编码也被称做最长最低密度阵列码。

3.7 T码

对于3容错的最长最低密度阵列码的构造较之双容错要复杂很多。文献[11]最先给出了一种这样的构造，并利用计算机辅助证明了某些参数下，3、4容错最长最低密度阵列码的MDS性。在文献[12]中独立构造了同样的编码并利用组合结构近乎可分的不完全区组设计(NRB)给出了这种编码的组合解释，同时也给出了简明的代数证明。

T码从形式上与B码相同，每块磁盘包含至多1个校验单元，并且只有一块磁盘不包含校验单元。文献[12]证明了对于任意容错的最长最低密度阵列码均满足这种性质。

对于普遍参数的T码，或任意容错的最长最低密度阵列码的构造，仍是困难问题。

3.8 Weaver码

前面的编码都将优化冗余率最优设为第一目标，同时兼顾编码/更新复杂度。但在一些系统中，如果冗余率的适当损失可换来更好的性能或更易于部署，则也是可选择的。文献[13]从优先考虑系统编码/更新复杂度的角度，提出了易于构造的Weaver码。

由B码、T码的构造也可以看出，在保持更新复杂度最优的前提下，校验单元分布在各磁盘中的编码比较容易构造。为了简化问题，文献[13]选择具有循环对称性的阵列进行研究。也就是说要求编码满足：(1)所有数据单元参与的校验组数为常数；(2)所有校验组包含的单元数目为常数；(3)如果磁盘i上的数据单元j参与磁盘k上的校验单元p所代表的校验组，则必有对于任何0≤x

为了更容易地得到k容错编码，文献[13]放宽了冗余的要求，只研究每块磁盘中，冗余校验单元不少于用户数据单元的情况。这样，Weaver码的最好冗余率只有50%。

4 结束语

阵列码尽管有着很多性能优势，但在目前的存储系统中，还是RS码及层叠RAID(如RAID1+0等)使用得比较多。笔者认为其原因主要为以下几个方面：

首先是实现上的简单性因素：RS码已经是工业界流行的技术，无论软硬件都有成熟的实现方案，而层叠RAID原理十分简单，所以这两种编码实施最简单易行。与之相对，阵列码多种多样、原理复杂，实施需要一定的投入。目前海量存储系统正处于发展阶段，什么是"最好的"编码尚不能形成定论，因而就目前阶段来讲，最简单的就是最好的。

其次，受到目前大部分应用的存储需求影响：尽管将多个单个部件合成一个统一的虚拟部件会有好处，但也会有相应的问题。如对10 000块磁盘是合成1个系统好呢？还是组成10每个包含1 000块磁盘的小系统好呢？这要根据需求来判断。一般来说小一些的系统会更容易管理和维护。目前只有极少的应用需要对超过1 000块盘容量的数据并行的处理，因而将系统分为多个较小系统是有益的。

第三，硬盘的造价较低且发展迅速：这使得人们可以比较"奢侈"地使用存储空间，因而大型存储系统的建造目前还处于"粗旷经营"阶段。相对于易实施性、易维护性、易扩展性，当前阶段冗余率还并不是主要决定因素。

但是，随着单磁盘容量的日趋饱和，系统对性能、容错、节能等需求的不断变化，海量存储系统构造相应的也会不断发展。明天的存储系统将会需要具备什么特性的编码形式，还需我们不断探索。

5 参考文献

[1] HARTLINE J R, RAO K K. Notes on Reliability Models for Non-MDS Erasure Codes [R]. Research Report. RJ10391(A0610-035). San Jose, CA,USA: IBM. 2006.

[2] 王新梅, 肖国镇. 纠错码——原理与方法 [Ｍ]. 西安：西安电子科技大学出版社, 2001.

[3] 林胜. 存储系统容错及阵列编码 [D]. 天津：南开大学, 2010.

[4] HELLERSTEIN L, GIBSON G A, KARP R M, et al. Coding Techniques for Handling Failures in Large Disk Arrays [J]. Algorithmic, 1994,12(3/4):182-208.

[5] BLAUM M, BRADY J, BRUCK J, et al. EVENODD: An Optimal Scheme for Tolerating Double Disk Failures in RAID Architectures [J]. ACM SIGARCH Computer Architecture News, 1994,22(1):245-254.

[6] CORBETT P, ENGLISH B, GOEL A. Row-diagonal Parity for Double Disk Failure Correction [C]//Proceedings of the 3rd USENIX Conference on File and Storage Technologies(FAST’04), Mar 31-Apr 2, 2004, San Francisco, CA,USA. Berkeley, CA, USA: USENIX Association, 2004: 14p.

[7] PLANK J S. The RAID-6 Liberation Codes [C]//Proceedings of the 6th USENIX Conference on File and Storage Technologies(FAST’08), Feb 26-29, 2008, San Jose, CA, USA. Berkeley, CA, USA: USENIX Association, 2008:97-110.

[8] WANG Gang, LIN Sheng, LIU Xiaoguang, et al. Combinatorial Constructions of Multi-erasure-correcting Codes with Independent Parity Symbols for Storage Systems [C]//Proceedings of the 13th IEEE Pacific Rim International Symposium on Dependable Computing(PRDC’07), Dec 17-19, 2007, Melbourne, Australia. Piscataway, NJ, USA: IEEE, 2007:61-68.

[9] XU Lihao, BRUCK J. X-code: MDS Array Codes with Optimal Encoding [J]. IEEE Transactions on Information Theory, 1999,45(1):272-276.

[10] XU Lihao, BOHOSSIAN V, BRUCK J, et al. Low Density MDS Codes and Factors of Complete Graphs [J]. IEEE Transactions on Information Theory, 1999,45(6): 1817-1826.

[11] LOUIDOR E, ROTH R M. Lowest-density MDS Codes over Extension Alphabets [C]//Proceedings of the IEEE International Symposium on Information Theory (ISIT’03), Jun 29-Jul 4,2003, Yokohama, Japan. Piscataway, NJ, USA: IEEE, 2003:58.

[12] LIN Sheng, WANG Gang, STONES D S, et al. T-code: 3-erasure Longest Lowest-density MDS Codes [J]. IEEE Journal on Selected Areas in Communications, 2010, 28(2):289-296.

[13] HAFNER J L. WEAVER Codes: Highly Fault Tolerant Erasure Codes for Storage Systems [C]//Proceedings of the 4th USENIX Conference on File and Storage Technologies(FAST’05), Dec 13-16,2005, San Francisco, CA,USA. Berkeley, CA, USA: USENIX Association, 2005.

林胜，南开大学计算机专业博士毕业，天津理工大学副教授，研究方向为存储编码、组合算法。

刘晓光，南开大学计算机专业博士毕业，南开大学信息技术科学学院副教授，研究方向为高性能计算、海量信息存储技术。

王刚，南开大学计算机专业博士毕业，南开大学信息技术科学学院教授，研究方向为海量信息存储技术、并行计算。

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