基于纠错码的容错技术的研究——X码的设计与实现

基于纠错码的容错技术的研究——X码的设计与实现
摘  要
随着计算机网络技术的迅猛发展，办公自动化和企业信息化的不断普及，人们对数据存储的需求越来越高,容错技术是提高计算机系统可靠性的有效手段。目前，X码已经作为计算机网络中提高系统可靠性的一种容错编码技术,被广泛应用在存储系统中。本文主要分析了基于纠错码的容错技术，并从X码的编码算法和译码算法的关键技术出发，采用X码对文件信息进行编码，增加两列校验文件信息，预先知道出错文件位置情况下，通过X码译码算法能恢复任意两列文件信息，实现一个文件容错仿真模型，进一步证明了基于X码容错技术的可靠。
关键词： X码；编码算法；译码算法；容错技术；可靠性
 
 
Research of Fault Tolerance Technology based on Error Correcting Code
——The Design and Implementation of X Codes
Abstract
With the rapid expansion of the Internet and the increasingly wide of information
technology, the demand for data storage becomes higher and higher. Fault-tolerant technology is an effective method to improve the reliability of computer systems. X codes are already a reliable fault-tolerant technology in the computer network and is widely used in storage systems. This dissertation systematically investigates fault tolerance technology based on error correcting code in storage system. And the file information is encoding by X codes, two columns of parity file information are added.
Two columns of files’ losses can be recovered up to by decoding algorithm of X codes if error positions are known in advance. A File fault tolerance model is implemented by analyzing encoding and decoding algorithm of X codes. The reliability of X codes is further proven by experimentations.
Key words: X code; encoding algorithm; decoding algorithm; Fault-tolerant technology; Reliability
 
目录
                                         论文总页数：20页
1    引言    1
1.1    课题背景    1
1.2    容错技术的概念    1
1.3    容错技术的发展历史    1
1.4    基于纠错码的容错技术的研究方法    2
2    X码的设计与实现的理论知识    2
2.1    X码的编码模式    2
2.2    X码的译码算法    4
2.2.1 纠正2列信息块    4
2.2.2 纠正2列信息块的算法    5
3    基于X码的文件恢复模块分析与设计    7
3.1    基于X码的文件恢复的模块功能图    7
3.2 文件随机产生模块功能    9
3.3 文件分割产生模块功能    10
3.4 编码模块功能    10
3.5 译码模块功能    12
4    测试和测试结论    13
4.1    测试    13
4.2 测试结论：    17
结    论    17
参考文献    18
致    谢    19
声    明    20
 
1    引言
1.1     课题背景
信息存储是人类社会永恒的需求，从古时文字印刷到电子磁盘、光盘，人类信息的存储技术突飞猛进。IDC估计全球网络存储市场将从1999年2亿美元增加到如今25亿美元。国内对网络存储的需求量正在迅速增长中，从目前的市场销售金额（60亿）和每年的市场销售增长（20％左右）可以看出中国存储市场显示出其巨大的市场潜力。随着网络飞速地发展，应用在人们生活中的存储设备的数目不断增多，产生了大量的数据。为满足日益复杂的各种信息存储需求，因此希望这些设备可以独立于数据进行重启、更换，或者设备遭受损坏，而不至于影响到数据的正常使用。今后这些设备的数据主要是放在网络上，用户可以随时随地存储和访问自己的数据，并进行共享和交流。于是开发一种信息容量大的存储模式，实现真正的“网络存储”，同时提高人们查询读取的速度，这已成为互联网信息存储领域的前沿方向。为了满足用户对高可靠性、易于访问的海量存储系统的需求，人们把纠错码冗余技术应用到分布式存储系统中，用于提高存储系统的可靠性。
1.2     容错技术的概念
容错（Fault-tolerance）：容忍故障，考虑故障一旦发生时能够自动检测出来并使系统能够自动恢复正常运行。
当出现某些指定的硬件故障或软件错误时，系统仍能执行规定的一组程序，或者说程序不会因系统中的故障而中止或被修改，并且执行结果也不包含系统中故障所引起的差错。
    即使采用了排错技术，一个计算机系统还是迟早会发生故障的。因此在设计计算机系统时应考虑一旦发生故障能自动检测出故障并使系统自动恢复正常运行。这样设计出来的计算机系统在发生故障后仍能正确运行。
    容错技术是从系统结构方面来提高计算机系统的可靠性。
    容错技术与排错技术并不是相互对立的，它们可以相互补充，构成高可信的计算机系统。
1.3    容错技术的发展历史
近年来制造业、能源、交通、教育等行业对IA服务器的需求量迅猛增长，他们不仅期望服务器能够提供7X24小时的不间断连续运行，同时还希望减少维护工作量，以控制TCO(总拥有成本)等等。从2003年起，以超过20%的市场占有率名列日本服务器市场第一位的NEC服务器进入中国市场，使国内用户真正开始接触到IA架构、Windows 2000平台的容错服务器。事实上，容错技术从问世到现在，已经拥有了20年的历史。
用“大器晚成”形容容错技术20年来不断完善、发展的历史，实不为过。早在20世纪80年代，第一代容错技术就开始进入商用领域。美国Stratus（容错公司）采用了Motorola M68000处理器，在Stratus独特的硬件级容错技术及VOS专有操作系统环境下，为满足金融业、证券业、电信业，交通业及博彩业的需求提供了可靠的保证。Stratus领先的硬件级容错体系结构确保了99.999%的连续可用性，在当时遥遥领先于其他技术。但由于此服务器采用专有处理器与操作系统的封闭式架构，所以给它的广泛推广与大规模应用造成了阻碍，而其相对较高的成本和复杂的维护工作量也使得其局限于少数应用。
21世纪以来，全球信息技术革命如火如荼，制造业、中小企业、能源、交通等领域对服务器特别是中低端IA服务器需求激增，而过去仅仅可以应用在RISC平台、HP-UX环境下的容错产品面临着新的挑战。另一方面，企业越来越依赖信息系统来完成关键业务的应用，对服务器系统的可用性、高安全性提出更高的要求，同时他们不可能配备更多的专业人员来进行专职维护，这是双机热备、集群服务器难以解决的问题，所以容错技术就成为解决这些问题的主流。
现如今，容错服务器对很多用户来说，早已不再陌生。建立在冗余技术基础之上的容错服务器，在解决单点故障、缩短故障恢复时间、降低人为错误、减少部件和软件版本不兼容等方面相对于集群服务器都显示出了其强大的优势，并逐渐成为服务器市场的新亮点。
1.4    基于纠错码的容错技术的研究方法
阵列纠错码的编码过程只需要异或运算，软硬件实现非常容易，在相同编码效率的下，阵列码按照计算复杂度比RS纠删码来得更加有效，因此一直是容错技术中研究的一个热点问题。基于纠错码的容错技术是在数据的传输、存储、处理过程中，根据信息位和校验位之间的相关性进行检查，判定信息是否丢失，并进行纠正。常用的检错码编码技术有奇偶校验码、循环码、海明码等。而本论文设计实现的X码是奇偶校验码，通过在矩阵上信息位的基础上增加校验位，并能以正确的值校正删除值，使信息恢复到原来正确状态。目前，纠错码技术已经作为计算机网络中提高可靠性的一种容错技术。
2    X码的设计与实现的理论知识
2.1    X码的编码模式
X码是一种具有几何特性的Vertical code，一般记为(n, n-2,3)X码。在结构上，(n, n-2,3)X码每个码字是一个n*n的阵列，前n-2行存放信息位，即信息位放在一个(n-2)*n阵列中，后2行存放奇偶校验位，分别是沿着斜率+1或-1的对角线的信息位的异或运算重新构造出2行校验行，每一列有信息位也有奇偶校验位。X码的编码模式如下所示。
设 为第i行第j列上的位,则奇偶校验位按下列规则进行构造：
                     
这里i=0,1, …,n-1,并且 ， 2个奇偶校验行上各奇偶校验位的值是各自沿着斜率为-1或+1的对角线的n-2个信息位的校验和(异或运算)得到。
从X码的结构看出2个奇偶校验行是独立地被得到的。每个信息位只影响每一奇偶校验行中的一个奇偶校验位，所有的奇偶校验位只依赖信息位；但不互相依赖，所以更新一个信息位只需更新2个奇偶校验位即可，这样X码有最佳的编码<或更新>特性。另外每一列有2个奇偶校验位并且每一奇偶校验位是n-2个信息位的校验和，这样在每一列计算奇偶校验位需要2*(n-3)次异或运算。X码的这个平衡计算特性在需要均匀分布计算的应用中是非常有用的。
为了方便了解X码的编码过程，下面以n=7为例显示一个（7，5） X码的编码：
                            表1 7*7的矩阵
C00    C01    C02    C03    C04    C05    C06
C10    C11    C12    C13    C14    C15    C16
C20    C21    C22    C23    C24    C25    C26
C30    C31    C32    C33    C34    C35    C36
C40    C41    C42    C43    C44    C45    C46
C50    C51    C52    C53    C54    C55    C56
C60    C61    C62    C63    C64    C65    C66
其中2个奇偶校验行可根据公式（1）进行计算求得，如下：