应用于海量存储中高度容错的新编码方案

　　 摘要：阐述了在网络存储系统中基于XOR的纠删编码的一种新方法，解决了传统RAID系统不能解决的高容错性问题，且比Reed?Solomon等算法有更好的时间效率。Ningxy编码方法对于解决高容错性问题有着最佳的效果，该编码更适用于动态增减磁盘数量的网络存储的数据修复；与此同时提出了新概念步长，步长对解决高度容错起到了关键性作用；通过线性变换、高斯消元，迅速地恢复丢失的磁盘数据。更值得一提的是从整体性能和效率上来说，该编码比其他的编码更具有灵活性。
　　关键词：独立冗余磁盘阵列/DRAID; 最大距离分离; 临界值
　　中图分类号：TP302.8文献标志码：A
　　文章编号：1001-3695(2007)12-0041-03
　　
　　随着当前信息数据的爆炸式增长，如何确切地保护和妥善管理用户的重要数据成为一个亟待解决的问题。目前拥有很多种方案来解决数据的安全性问题。例如当数据丢失后，仍可以让其恢复或再生。在解决这个问题中，需要提及一个概念RAID。它是由美国的D.A.Patterson在1988年提出的。RAID将离散的磁盘变成了RAID子系统。RAID具有较高的性能，这是因为不同磁盘上的数据可以同时读取，从而提高磁盘的带宽；所有磁盘可以并行地进行寻道工作，减少了寻道的时间，提高整体性能。在性能提高的同时，还可以保证一定程度的容错性。通过相应的冗余磁盘容错机制，可以保证在不丢失保存在失效磁盘上的数据的前提下允许磁盘的失效。Gibson等人对磁盘驱动器失效的规律进行了研究。他们广泛地收集实验数据并分析了磁盘失效模型，认为负指数分布很好地表述了磁盘驱动器的失效规律。这种研究可以提供一种思维方式，如因为自然灾害（地震、火灾）、战争等情况下，多个磁盘驱动器同时发生故障、系统瘫痪，也能对机密资料进行快速恢复或修复，给把数据视为生命的机构和单位提供保障。
　　大多数情况，在目前单点失效模式下，磁盘阵列系统主要依靠RAID 5容错来为用户数据提供可靠性。在比特错误提高很少的情况下，磁盘容量的持续增长把RAID 5和RAID 6系统可靠性削弱到了无法令人接受的境地。本文提出了在磁盘阵列和其他可靠的存储系统中基于XOR的纠删编码的一个新方法。这个新编码的一个关键优势是其并不是非MDS（在编码理论中，MDS代表最大距离分离）。
　　
　　1相关的概念术语
　　
　　a)单元（element）是一个基本的数据或者校验单元。
　　b)条带（stripe）是一个完整的数据和校验单元的集合。这些单元由于校验关系而有着依赖相关性。实际上它相当于一个码字，既有原始信息又有冗余信息，并且原始数据和冗余数据间必须有校验关系。
　　c)条块（strip）是所有连续的在同一磁盘和条带上的存储单元。它上面存放的是数据或者校验数据或者两者都有。值得说明的是，这些strip大小相同（包含同样数量的elements）。
　　d)阵列（array）是存在一个或者多个条带的数个磁盘的组合。磁盘阵列中的划分如图1所示。
　　e)堆栈（stack）是一个阵列中数个条带的集合，这些条带中的条块数目是相同的。
　　f)水平码（horizontal code）不同于数据，它单独地存储校验数据。
　　g)步长(step)是一个数据条块到另一个数据条块之间的跨度（本文引入的新概念）。步长示意图如图2所示。图中步长用?S?表示。
　　

2纠错码原理
　　
　　按照误码控制的不同功能可分为检错码、纠错码和纠删码等。检错码仅具备识别错码功能而无纠正错码功能；纠错码不仅具备识别错码功能，同时具备纠正错码功能；纠删码则不仅具备识别错码和纠正错码的功能，而且当错码超过纠正范围时可把无法纠错的信息删除。
　　按照误码产生的原因不同，可分为纠正随机错误的码与纠正突发性错误的码。前者主要用于产生独立的局部误码；后者主要用于产生大面积连续误码的情况，如磁带数码记录中磁粉脱落而发生的信息丢失。按照信息码元与附加的监督码元之间的检验关系可分为线性码与非线性码。如果两者呈线性关系，即满足一组线性方程式，称为线性码；否则，两者关系不能用线性方程式来描述，称为非线性码。
　　
　　6进一步工作
　　
　　本文阐述了容错度为?t?且根据决定空间效率的参数?r/v?来进行磁盘整列的设计、分析时间复杂度的情况。这种编码算法对于在RAID或者DRAID结构中的磁盘损坏有很好的恢复效果。就存储效率和性能来说，也比其他很多编码有更强的优势，如比Weaver、Reed?Solomon等算法空间复杂性与时间复杂性都好。同时也引进了一个新的概念，即步长。这个概念的引入对解决高容错性磁盘阵列问题或者更大的网络存储数据修复问题起着非常重要的作用。进一步工作是如何用解决高容错度的思路去得出?v、r、t和n?的关系，求出最佳的公式表达。主要的工作就是探讨存储效率更高、容错更大，使得空间效率和时间效率在某一应用中能达到最佳状态，对这个DRAID或者RAID系统的影响，并提出一些新的观点，以求解决在高容错情况下高容错度问题。
　　致谢：笔者向对本文的工作给予支持和建议的同行，特别是兰州理工大学电通院的董建设、徐维涛以及江南大学的刘英戈表示感谢。
　　
　　参考文献：
　　[1]PLANK J S. A tutorial on Reed?Solomon coding for fault?tolerance in RAID?like systems [J].Software Practice & Experience, 1997, 27(9):995-1012.
　　[2]HAFNER J L. HoVer erasure codes for disk arrays[C]//Proc of International Conference on Dependable Systems and Networks. Washington DC:IEEE Computer Society, 2006:217-226.
　　[3]XU Li?hao, BRUCK J. X?code: MDS array codes with optimal encoding [J].IEEE Trans on Information Theory,1999,45(1):272-276.
　　[4]BLAUM M, BRADY J, BRUCK J,?et al?. EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures [J].IEEE Trans on Computers, 1995,44(2):192-202.
　　[5]PERUMAL S, KRITZINGER P. Object?oriented design of the groupware layer for the ecosystem information system [D]. Montana:University of Montana, 1995.
　　[6]ZAITSEV G V, ZINOVEV V A, SEMAKOV N V. Minimum? check? density codes for correcting bytes of errors [J].Problems in Information Transmission, 1983,19(3):29-37.
　　[7]周敬礼,余胜生.网络存储原理与技术[M].北京：清华大学出版社,2005:33-55.
　　[8]江藤良纯,金子敏信.纠错码及其应用[M].北京：科学出版社，2003:45-93.
　　[9]HAFNER J L. Weaver erasure codes for disk arrays[R].San Jose:IBM Research, 2005.
　　[10]XIN Qin,MILLEAR E L,SCHWARZ T,?et al?. Reliability ?mecha??nisms for very large storage systems[C]//Proc of the 20th IEEE/11th NASA Goddard Conference on Mass Storage Systems and Technologies. Washington DC:IEEE Computer Society,2003:146-156.
　　[11]HAFNER J L. Matrix methods for lost data reconstruction in erasure codes[C]//Proc of the 4th USENIX Conference on File and Storage Technologies.San Francisco:[s.n.],2005:183-196.
　　[12]PLANK J S. T1:erasure codes for storage applications[C]//Proc of the 4th USENIX Conference on File and Storage Technologies.San Francisco:[s.n.],2005:1-74.