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

基于纠错码的容错技术的研究-EVENODD码的设计与实现
摘  要
由于网络技术的迅猛发展，存储系统的规模变得越来越庞大。因此它对系统的可靠性提出了严峻的挑战。而采用EVENODD编码算法的布局策略可以同时容许两个数据块同时出错，可以很好的保证系统的稳定性。它已经被广泛应用在RAID（Redundant  Arrays of Independent Disks）等技术中。本论文从EVENODD编码原理出发，详细介绍了EVENODD的编码和译码过程，以及从理论上对该译码的算法进行了分析证明，同时使用java编译技术实现了该编码过程的仿真。在本论文中还对该仿真软件的设计思路、开发过程、以及主要功能模块的实现都进行了详细的介绍。EVENODD码仿真软件的实现是理论运用于实际的又一典范。通过对其编码和译码核心算法的调用，可以实现图片、二进制文件等格式的备份和恢复。

关键词： EVENODD编码 ；容错技术 ；系统稳定性； java编译技术
 
Research of Fault Tolerance Technology based on Error Correcting Code
——The Design and Implementation of EVENODD Codes
Abstract
With the fast development of network technique, the 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( Redundant 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 development 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    引言    1
1.1    选题背景及意义    1
1.2    相近课题研究    1
1.2.1    2D奇偶校验编码方案    1
1.2.2    纠双错RS码    2
1.3    本课题要达到的设计目标    2
2    EVENODD码    2
2.1    预先定义    2
2.2    编码原理    3
2.3    EVENODD码译码算法    4
2.4    译码原理证明    6
3    软件设计与目标    8
3.1    设计目标及内容    8
3.2    软件总体功能结构    8
3.2.1    功能结构图    8
3.2.2    功能说明    8
3.3    设计实现的策略及主要算法描述    9
3.3.1    VENODD编码算法    9
3.3.2    EVENODD 译码算法    11
3.4    算法接口实现    22
3.4.1    编码功能接口设计    22
3.4.2    编码功能接口流程图    22
3.4.3    译码功能接口设计    22
3.4.4    译码功能接口设计流程图    22
4    软件操作说明    25
4.1    打开    25
4.2    编码    26
4.3    数据破坏    27
4.4    译码    27
4.5    其余功能    28
结    论    28
参考文献    28
致    谢    30
声    明    31
 
1    引言
1.1    选题背景及意义
随着企业信息系统的普及和整个社会电子商务的发展，现代企业的运作越来越依赖于信息技术。越来越多的关键数据被存储在计算机系统中，这些数据的丢失和损坏将对企业造成难以估量的损失。同时企业对于数据可用性的要求也大为提高，因为即使是短时间的系统停机也将造成业务停顿和经济损失。一旦IT系统和数据遭到灾难性打击，企业将面临破产的威胁，因此数据资料的完好保存是企业在灾难后能够继续生存的保证。
容错技术是保证系统稳定性的重要手段。容错是指一个系统在发生故障时仍能正确完成指定任务的能力。在硬件失效或软件错误的情况下，仍能够继续完成指定任务的系统称为容错系统。容错技术是指系统对故障的容忍技术，也就是指处于工作状态的系统中一个或多个关键部分发生故障或差错时，能自动检测与诊断，并能采取相应措施保证系统维持其规定功能或保持其功能在可接受的范围内的技术。所有的容错手段都必须依赖于“保护性冗余”，即依赖于系统中冗余的部件和算法。所谓“冗余”指的是如果系统是无缺陷的，那么这些部件和算法是不需要的。然而，EVENODD码理论的提出为容错技术的发展做出了重要的贡献。它以一种简单的方式越来越受到人们的青睐，并在各种系统中广泛使用，尤其是磁盘阵列布局方案中。其核心运算就是依据一定的规则将数据简单相异或。因此对EVENODD编码的研究及其实现具有很强的现实意义。
1.2    相近课题研究
容错技术在存储系统中有着广泛的应用。目前，已有的适用于存储系统的容错技术主要有三种：2D奇偶校验编码方案（二维奇偶校验），RS（Reed-Solomon）码以及EVENODD码。
1.2.1    2D奇偶校验编码方案
2D奇偶编码的码字结构为n×n的二维阵列，总共有N2个信息位，其中校验信息位为2N个，即水平校验和垂直校验，对矩阵的行和列分别进行校验计算。例如，假定信息位X是两个不同的组C1和C2两个组的成员，在C1组超过k个信息位出错，但是C2中少于k个信息位出错，那么X可以通过C2来恢复。每个码字不是一个组的成员，而是多个组的成员，进行容错计算。图1显示的是一个二维编码的策略和二维奇偶校验码。
单个的奇偶校验能够容忍单个码字出错，二维校验可以容忍任意的两个码字出错，而且如果增加一个full parity sever，可以容忍达到三个码字出错。二维编码策略是通过增加冗余，增加服务器的容错能力。冗余数据的增加，必定会导致编码和译码计算量的增加，及数据信息位和校验信息位之间的比之变化。

1.2.2    纠双错RS码
Reed Solomon(RS)是一类有很强纠错能力的多进制BCH码，也是一类典型的几何码。它首先是由里德（Reed）和索洛蒙（Solomon）应用MS多相式于1960年构造出来的。它不仅可以纠正突发错误, 还可以纠正随机错误, 特别适用于纠正信号的突发错误。Reed Solomon code 适合传送信息符号，而不是比特。RS虽然在六十年代就提出来了，但是实际得到应用差不多在八十年代。
在1994年，在RAID-6层，也称为（P+Q redundancy）：数据以块为单位分割，然后采用编码技术为纠双错RS. 设每列信息位分别为 ，其两列校验信息位 ，两个校验列的编码方程为：
1.3    本课题要达到的设计目标
本论文采用EVENODD码实现存储系统的容错仿真。利用随意的5张图片模拟存储系统中存储的数据，然后利用EVENODD编码技术，生成2个校验数据存于另外存储设备中（即两张校验图片）。随机破坏其中的一张或者两张数据，利用EVENODD的译码算法将这2张图片的数据恢复出来。整个仿真过程将在一个界面友好的应用软件中实现。
2    EVENODD码
2.1    预先定义
为了方便本文后面的叙述，先定义本文一些符号记法：<n>m = j 表示 j ≡ n(mod m) （0 ≤ j ≤ m+1）。例如：<7>5 = 2，<-2>5 = 3。
另外我们还对本原理做一些必要的假设：
1)    设存在m+2列数据块，其中前m个数据块依次存有信息，校验信息将存储在最后两列数据块。这样将在所有的数据块中形成冗余以避免在重复写操作时形成瓶颈。
2)    设m列数据块中每一个数据块只有m-1行。对于任意容量的数据块，可以预先分割成m-1行的块分别进行处理。为简单起见，在本文中假设每一个标识位大小为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)）。