1、基于纠错码的容错技术的研究EVENODD 码的设计与实现摘 要由于网络技术的迅猛发展，存储系统的规模变得越来越庞大。因此它对系统的可靠性提出了严峻的挑战。而采用 EVENODD 编码算法的布局策略可以同时容许两个数据块同时出错，可以很好的保证系统的稳定性。它已经被广泛应用在 RAID（Redundant Arrays of Independent Disks）等技术中。本论文从EVENODD 编码原理出发，详细介绍了 EVENODD 的编码和译码过程，以及从理论上对该译码的算法进行了分析证明，同时使用 java 编译技术实现了该编码过程的仿真。在本论文中还对该仿真软件的设计思路、开发过程、以及
2、主要功能模块的实现都进行了详细的介绍。EVENODD 码仿真软件的实现是理论运用于实际的又一典范。通过对其编码和译码核心算法的调用，可以实现图片、二进制文件等格式的备份和恢复。关键词： EVENODD 编码 ；容错技术 ；系统稳定性； java 编译技术Research of Fault Tolerance Technology based on Error Correcting CodeThe Design and Implementation of EVENODD CodesAbstractWith the fast development of network technique, th
3、e scale of storage system becomes bigger and bigger. So, it is an austere challenge to the system. But the data placement strategy of EVENODD which has the ability to simultaneously correct two error data blocks can ensure the stability of the system. It has been extensively used in the RAID( Redund
4、ant Arrays of Independent Disks) technology. In the thesis encoding and decoding algorithms of EVENODD codes are introduced. Moreover decoding algorithms are analyzed and proven. At the same time, the software of EVENODD emulator is developed by java technology .The idea of design, the process of de
5、velopment and the design of main function blocks are proposed. It is an apotheosis which uses theory in the real world. Pictures and binary files can be backed up and recovered by EVENODD codes.Key words: EVENODD; Fault-tolerant; Stability of system; Java technology目 录论文总页数： 31 页1 引言 .11.1 选题背景及意义 .
6、11.2 相近课题研究 .11.2.1 2D 奇偶校验编码方案 .11.2.2 纠双错 RS 码 .21.3 本课题要达到的设计目标 .22 EVENODD 码 .22.1 预先定义 .22.2 编码原理 .32.3 EVENODD 码译码算法 .42.4 译码原理证明 .63 软件设计与目标 .83.1 设计目标及内容 .83.2 软件总体功能结构 .83.2.1 功能结构图 .83.2.2 功能说明 .83.3 设计实现的策略及主要算法描述 .93.3.1 VENODD 编码算法 .93.3.2 EVENODD 译码算法 .113.4 算法接口实现 .223.4.1 编码功能接口设计 .2
7、23.4.2 编码功能接口流程图 .223.4.3 译码功能接口设计 .223.4.4 译码功能接口设计流程图 .224 软件操作说明 .254.1 打开 .254.2 编码 .264.3 数据破坏 .274.4 译码 .274.5 其余功能 .28结 论 .28参考文献 .28致 谢 .30声 明 .31第 1 页 共 31 页1 引言1.1 选题背景及意义随着企业信息系统的普及和整个社会电子商务的发展，现代企业的运作越来越依赖于信息技术。越来越多的关键数据被存储在计算机系统中，这些数据的丢失和损坏将对企业造成难以估量的损失。同时企业对于数据可用性的要求也大为提高，因为即使是短时间的系统停机
8、也将造成业务停顿和经济损失。一旦 IT 系统和数据遭到灾难性打击，企业将面临破产的威胁，因此数据资料的完好保存是企业在灾难后能够继续生存的保证。容错技术是保证系统稳定性的重要手段。容错是指一个系统在发生故障时仍能正确完成指定任务的能力。在硬件失效或软件错误的情况下，仍能够继续完成指定任务的系统称为容错系统。容错技术是指系统对故障的容忍技术，也就是指处于工作状态的系统中一个或多个关键部分发生故障或差错时，能自动检测与诊断，并能采取相应措施保证系统维持其规定功能或保持其功能在可接受的范围内的技术。所有的容错手段都必须依赖于“保护性冗余” ，即依赖于系统中冗余的部件和算法。所谓“冗余”指的是如果系统
9、是无缺陷的，那么这些部件和算法是不需要的。然而，EVENODD 码理论的提出为容错技术的发展做出了重要的贡献。它以一种简单的方式越来越受到人们的青睐，并在各种系统中广泛使用，尤其是磁盘阵列布局方案中。其核心运算就是依据一定的规则将数据简单相异或。因此对 EVENODD 编码的研究及其实现具有很强的现实意义。1.2 相近课题研究容错技术在存储系统中有着广泛的应用。目前，已有的适用于存储系统的容错技术主要有三种：2D 奇偶校验编码方案（二维奇偶校验） ，RS（Reed-Solomon）码以及 EVENODD 码。1.2.1 2D 奇偶校验编码方案2D 奇偶编码的码字结构为 nn 的二维阵列，总共有
10、 N2 个信息位，其中校验信息位为 2N 个，即水平校验和垂直校验，对矩阵的行和列分别进行校验计算。例如，假定信息位 X 是两个不同的组 C1 和 C2 两个组的成员，在 C1 组超过 k 个信息位出错，但是 C2 中少于 k 个信息位出错，那么 X 可以通过 C2 来恢复。每个码字不是一个组的成员，而是多个组的成员，进行容错计算。图 1 显示的是一个二维编码的策略和二维奇偶校验码。单个的奇偶校验能够容忍单个码字出错，二维校验可以容忍任意的两个码字出错，而且如果增加一个 full parity sever，可以容忍达到三个码字出错。二维第 2 页 共 31 页编码策略是通过增加冗余，增加服务器
11、的容错能力。冗余数据的增加，必定会导致编码和译码计算量的增加，及数据信息位和校验信息位之间的比之变化。1.2.2 纠双错 RS 码Reed Solomon(RS)是一类有很强纠错能力的多进制 BCH 码，也是一类典型的几何码。它首先是由里德（Reed）和索洛蒙（Solomon ）应用 MS 多相式于1960 年构造出来的。它不仅可以纠正突发错误, 还可以纠正随机错误, 特别适用于纠正信号的突发错误。Reed Solomon code 适合传送信息符号，而不是比特。RS 虽然在六十年代就提出来了，但是实际得到应用差不多在八十年代。在 1994 年，在 RAID-6 层，也称为（P+Q redun
12、dancy）：数据以块为单位分割，然后采用编码技术为纠双错 RS. 设每列信息位分别为1212(,),(,),mmbb ，其两列校验信息位 ，两个校验列的编码(,)pq方程为：1.3 本课题要达到的设计目标本论文采用 EVENODD 码实现存储系统的容错仿真。利用随意的 5 张图片模拟存储系统中存储的数据，然后利用 EVENODD 编码技术，生成 2 个校验数据存于另外存储设备中（即两张校验图片） 。随机破坏其中的一张或者两张数据，利用 EVENODD 的译码算法将这 2 张图片的数据恢复出来。整个仿真过程将在一个界面友好的应用软件中实现。2 EVENODD 码2.1 预先定义为了方便本文后面
13、的叙述，先定义本文一些符号记法：m = j 表示 j n(mod m) （ 0 j m+1 ） 。例如：5 = 2，5 = 3。row parity full parity paritycolumn parity图 1 二维奇偶校验编码1(1)(),2,;kkmiiiipqb第 3 页 共 31 页另外我们还对本原理做一些必要的假设：1) 设存在 m+2 列数据块，其中前 m 个数据块依次存有信息，校验信息将存储在最后两列数据块。这样将在所有的数据块中形成冗余以避免在重复写操作时形成瓶颈。2) 设 m 列数据块中每一个数据块只有 m-1 行。对于任意容量的数据块，可以预先分割成 m-1 行的块
14、分别进行处理。为简单起见，在本文中假设每一个标识位大小为 1bit（不过在一些应用程序当中，一个标识位可能大到 512 字节） 。3) EVENODD 码中，m 必须是素数，否则 EVENODD 码不是 MDS 码。因此若 m 不是素数，可使用如下方法将它构成素数：若存储任意数量的数据块而非必要的素数，通过增加不带任何信息的数据块达到 m 列的数据块，其中 m 为素数，那些多余的数据块所有信息位都为 0。4) 为了译码描述方便，EVENODD 码增加一行信息位，数据全为 0。例如：am-1,j = 0（0 j m+1 ，根据这个假设，数组大小现在是 m(m+2)） 。2.2 编码原理EVENO
15、DD 码的码字放在一个(m-1)*(m+2)的阵列中，m 是素数，其中信息放在(m 1) m 的阵列中，最后两列为奇偶校验信息符。两列奇偶校验位是分别通过同一行的信息位或者给定斜率对角线的信息位异或而构成的。EVENODD code 的编码，设 aij 表示位为第 i 行第 j 列上的信息符，则奇偶校验符按下列规则进行构造：从几何上看，S 是由第 m 列开始沿斜率为 1 的信息位的异或构成的。第一列的各奇偶校验位正好是这一行 m 个信息位的异或运算，第二列的各奇偶校验位是各自沿斜率为 1 的信息位的异或，再和 S 异或共同构成的。例 1 下面以 m5 为例显示一个（7，5）EVENODD 的编
16、码，如表 1表 1 EVENODD 编码a1 a2 a3 a4 a5 a1+a2+a3+a4+a5 S+a1+b5+c4+d3b1 b2 b3 b4 b5 b1+b2+b3+b4+b5 S+a2+b1+c3+d4c1 c2 c3 c4 c5 c1+c2+c3+c4+c5 S+a3+b2+c1+d51,0,1, 2302,miittiittmttaSSij公 式 （ ） ， 公 式 （ ）， 公 式 （ ） 并 且 = modn第 4 页 共 31 页d1 d2 d3 d4 d5 d1+d2+d3+d4+d5 S+a4+b3+c2+d1其中 S=a5+b4+c3+d2（1） 从 EVENODD
17、编码的结构可以看出， 2 个奇偶校验列是独立得到的，当 m 是素数时，满足 Singleton bound,是一类 MDS，如 m 不是素数时，不能保证 EVENODD 具有 MDS 的性质，例如下面的这种情况（6，4）的情况，表2，码字之间的最小距离是 2，若 1，3 列丢失，不能恢复原信息符。表 2 （6，4）数组（2） 在两列冗余校验中，其中有一列的冗余校验和参数 S 进行以后，参数 S（m-1,1 ） ,(m-3,2),(0,m-1)可能是奇或偶，也是由于这个原因，M.Blaum称这类阵列码为 EVENODD code。如果参数 S 忽略，则不能保证 EVENODD code 的 MD
18、S 性质。例如下面的（7，5）情况表 3，码字之间的最小距离就是2，若第 2，6 列出错，是不能恢复的。表 3 （7，5）数组b b b b b b bb b b b b b bb b b b b b bb a b b b a b2.3 EVENODD 码译码算法在这一节将介绍 EVENODD 码纠双列删错的译码方法。这两译码算法没有有限域的计算操作，只需要简单异或操作，软硬件实现简单。下面简单介绍一下 EVENODD 的译码算法，EVENODD code 译码算法（Two Erasure Decoding Algorithm ）假定数据块 i 和 j 损坏，0im,0)， (m,1)，(i,m-1)上的数值相异或得到。这是一条唯一不与第 i 列相交的对角线（此时第 i 列无效） 。因此所有的对角线都有相同的公共因子 S。经过分析公式（ 2）得到 的过程，我们可以推出能够,kia找到恢复第 i 列数值的公式（5） ，一旦第 i 列的值被恢复，这个算法就可以利用公式（1）得到第 m 列的值。（3） i m ， j = m+1，这种情形和编码的过程相似，在这里不再赘述。
