Reed-Solomen_RAID.doc

1、1毕业设计 （论 文）题 目：“Reed-Solomen”算法在 RAID 系统中的应用 系 别： 计算机科学与工程系 专 业： 计算机科学与技术 学生姓名： 张伟强 班级/学号 0213519 指导老师/督导老师： 张京生 起止时间：2006 年 2 月 20 日 至 2006 年 6 月 2 日北京信息科技大学2摘 要未来的世界是信息的世界，当二十世纪人类开启了信息时代的大门，世界信息化的脚步就越走越快，爆炸式的信息增长趋势已注定人类的二十一世纪及未来将和无处不在的信息形影不离：无论是人们的个人生活、工作、学习，还是工业生产、金融、国防，人类的所有社会活动将全面的进入信息化时代。这样，毫无

2、疑问的是，在这个即将到来的信息社会，其核心的资源必然是存储在数以亿计各式终端中的各类数据。然而，正是因为社会的每一个单元都开始变得和数据息息相关，数据本身的安全就一跃成为人们首要也是必须关心的问题。对比个人用户珍藏资料数据遭到破坏的莫大遗憾，银行金融系统，企业集团，政府机构，军队国防，航空航天等等社会单元的数据资料一旦遭到破坏，将会造成巨大的经济损失，甚至更为严重。金融经济的瞬间瘫痪，战场上的兵不血刃等等都将成为可能，而造成这一切的核心，就是数据存储的安全与否。然而，病毒破坏，火灾，地震，恐怖袭击，人为误操作，逻辑系统的缺陷，尤其是存储介质本身会出现故障的绝对性却决定了无论多么优良的存储介质也

3、无法绝对安全的现实。面对这样的现实情况，本文试图换个角度突破这个安全瓶颈，通过对纠错编码理论及有限域数学理论的一步步深入研究，尝试将基于有限域数学的 Galois 域 Reed-Solomon算法应用到 RAID(Redundant Array of Independent Disk 独立冗余磁盘阵列 ) 磁盘阵列当中，并尝试实现小型的 RAID6 级别的实验程序，从而为实现更加安全的存储技术提供了思路。关键词：里德-索罗门算法 、 纠错编码 、RAID6 、 磁盘阵列 、 有限域 、 伽罗华域 3AbstractThe world in the future will be a world

4、built upon full of various information. When people began an age called information age in the 20th century, it would never stop and develop faster and faster. As the information increase exponentially nowadays , were sure this world will be always together with the information everywhere in the 21s

5、t century and the future: whether personal life , work , study ,or industry production , finance system , national defense , etc , all social activities of people will be informationed all-around. In this case, there is no doubt in the information society; the key resource is the data which are stor

6、ed in billions of devices and terminals.However, just because every society unit is concerned with data, the security of data self has become the most serious problem that people have to be in the face of. Compared with the regret of personal commemorable datas damage, the bank and finance system, c

7、orporation group, the government, the army and national defense, the spaceflight, once the stored data of these units of society is destroyed, it will cause enormous economy damnify and even worse. Economy and finance systems sudden paralysis, wining victory without battle will be the truth, and the

8、 key reason of that is whether the data is secure or not. The data is secure? No, damage of computer virus, fire, earthquake, terrorism attack, man-made wrong operation, bugs of logic system, especially the inevitability of physical damage, all these have said that whether the storage device is good

9、 or not, the data will not be secure absolutely.In the face of above cases, this paper attempts to break through the bottleneck of data security with another way. Through study of Error Correction Code and Finite Field theoretics, this paper tries to apply the Reed-Solomom arithmetic based on Finite

10、 Field Galois Field to Redundant Array of Independent Disk, and tries to realize a simple RAID6 level programme, thereby could offer an idea for securer storage device. Keywords: Reed-Solomon theoretics 、Error Correction Code 、RAID6 、 Redundant Array of Independent Disk 、 Finite Field 、 Galois Field

11、4目 录摘要 (中文) I(英文) II第一章 绪论1.1 信息时代数据存储安全的极端重要性1.2 当今数据存储及数据安全的现状1.3 本课题的研究内容及实现目标1.4 本课题在领域内研究的现状第二章 RAID(Redundant Array of Independent Disk) 独立冗余磁盘阵列理论基础与 RAID6 模型的建立2.1 什么是独立冗余磁盘阵列2.2 已成功研发的各级别(level)RAID 系统原理、性能比较与原因分析2.3 继承与发展，RAID6 独立冗余磁盘阵列的设想与模型建立第三章 Reed-Solomon 算法理论探究3.1 群、环、域的基本概念和性质3.2 有限

12、域的定义及有限域的性质3.3 二元域的运算3.4 基于 Galois 域 GF( )的 Reed-Solomon 算法3.5 实现基于 Galois 域 GF( )的 Reed-Solomon 算法在 RAID6 磁盘阵列中的应用P 校验、Q 校验的生成方法第四章 基于 Reed-Solomon 算法的 RAID6 级别磁盘阵列的模拟实现创建RAID6 部分4.1 RAID6 模型框架的程序实现4.2 实现 P 校验4.3 Galois 域 GF( )的程序实现4.4 实现 Q 校验4.5 待存储文件字节数不为偶数情况的处理4.6 RAID6 级别磁盘阵列的模拟实现及验证第五章 基于 Reed

13、-Solomon 算法的 RAID6 级别磁盘阵列的模拟实现实现对数据的恢复部分5.1 RAID6 当两块磁盘失效时进行数据恢复的算法5.2 恢复算法的程序实现5.3 以随机两块模拟磁盘失效进行恢复演示第六章 总结与展望致谢5第一章 绪 论1.1 信息时代数据存储安全的极端重要性未来的世界将是一个用 0 和 1 来进行描述的世界，随着二十世纪末人类开启了信息时代的大门，世界信息化的脚步就越走越快，爆炸式的信息增长趋势已注定人类的二十一世纪及未来将会和无处不在的信息形影不离：无论是人们的个人生活、工作、学习，还是工业生产、金融、国防，人类所有的社会活动将全面进入被信息化的时代。显而易见，对于这样

14、的一个信息社会来说，其核心的社会资源无疑将是存储在数以亿计各式终端中的各类数据。根据 IDC(国际数据资讯 )的调查显示，截止到 2003 年，全球计算机数据存储量已达2000000TB，并且能够保持以每年 80%的速度在增长，而预计到了 2008 年，仅中国就将达到 139415TB（IDC 数据）的外部磁盘存储容量，可以预见，在不远的将来，一个真正数字化的信息社会将在人类的面前实现。然而，正是因为社会的每一个单元都开始变得和数据息息相关，数据存储本身的安全就已然成为人们首要也是必须关心的核心问题。珍藏的数码照片，个人的影像资料，各种私人文档、统计表格，甚至是个人的科研成果等等，这些对于个人

15、用户来说极为重要的存储数据一旦遭到破坏，将会是莫大的遗憾和惋惜；而对比以上这些个人数据，银行金融系统，大型企业集团，国家政府机构，军队国防系统，航空航天等等，这些社会单元的数据资料一旦遭到破坏，将会造成巨大的经济损失，甚至会更为严重。在不远的将来，可以想象一个国家甚至世界范围内的金融经济在一瞬间瘫痪，可以想象在战场上兵不血刃就可以摧毁敌方的防御能力，可以想象一个大型的企业集团因为核心资料被破坏而无法运作，而在人类探索太空的道路上，资料数据的存储安全更是极为重要。结论是很明显的，在未来这个被全面信息化的世界里，绝大部分的社会单元，社会活动都是以存储在介质上的数据资料作为核心的，其安全的极端重要性

16、，正是人们必须迫不及待关心的重大问题。1.2 当今数据存储及数据安全的现状1.2.1 数据存储概况数据的存储是指根据不同的应用环境通过采取合理有效的方式将数据保存到某些介质上并能保证有效的访问，当今对数据的存储可以从四个方面进行分类：一是按照使用的方式，可以分为移动存储设备和非移动存储设备；二是按照存储的介质进行分类，可以分为光介质存储、电介质存储和磁介质存储；三是按照传输速度的快慢或访问频度进行分类，可以分为在线存储、近线存储和离线存储；还有一种就是按照存储设备与服务器的连接方式分类，目前可以有存储设备与服务器直接相连的 DAS(Direct Attached Storage,直连方式存储)

17、 ，和存储设备需连接到 TCP/IP 网络中的 NAS(Network Attached Storage 网络连接存储) 方式。6而在这几种不同角度的分类中，我们可以看出，最基本的存储要素还是采用何种存储介质进行存储，就当前的发展而言，磁存储仍然是世界主流的存储介质，那么，目前数据存储的安全性如何呢？1.2.2 数据存储的安全性现状虽然计算机存储的安全技术在不断的快速发展，但是，显然还跟不上世界信息化过程中数据爆炸式增长、数据重要性日益升高对数据存储安全的需要，就目前而言，以下几个方面的影响仍然是数据存储安全保障的大敌：I计算机病毒的破坏：充斥在计算机世界的各种病毒程序随时随地都会对数据、重要

18、数据产生重大的威胁，它们要么使数据表现失效，不能够被正常访问，要么干脆就毁掉数据，使数据不能够再生，以 1999 年在全球爆发的 CIH 病毒为例，仅一波攻击就导致全球超过六千万台计算机数据遭到破坏，造成超过 10 亿美元的直接或间接经济损失。II逻辑系统的设计缺陷：数据在存储过程中是必须需要软件来对数据进行组织和管理的，例如，文件系统就是用来管理存储在磁盘上的数据的管理系统，然而，这些软件产品却很难做到十全十美，万无一失，在实际的应用中，由于设计上的难于发现的 bug 或一些莫名奇妙的原因，导致数据失效的情况不足为奇。III. 人为误操作： 人们在对计算机数据进行管理和操作时，偶尔会出现人为

19、的失误，这种失误有时将会导致严重的数据被破坏的后果，例如，对数据进行误删除，误格式化，对存储设备进行误插拔等等，这些不可百分百避免的人为事故都是数据安全的大敌。IV. 恐怖袭击人为的恶意破坏，要求数据的存储系统能够提供尽可能多的对于数据的保护及尽可能强的灾难恢复功能。V. 地震，火灾等同样，大自然不可抗力的破坏，也对数据存储的安全构成重大威胁，也同样要求存储系统能够提供尽可能多的对于数据的保护及尽可能强的灾难恢复功能。VI. 物理介质损坏的必然性物理介质存在出现故障的可能的必然性，是威胁数据存储安全的又一重要原因，不管有多么优秀的设计技术，多么优秀的质量，作为一种机械设备，单个的磁盘存储器都必

20、然会有发生故障的可能，而恰恰是这种不可预见的对于数据的破坏，形成了当今数据存储安全的一个瓶颈。因此，就目前而言，数据存储的安全现状并不容乐观，人们仍需找出一种能够尽可能保证数据安全的方法，这也正是本文努力的方向。1.3 本课题的研究内容及实现目标7正是针对目前数据存储的现状，本文试图换一个角度，采用多个磁盘存储设备协同配合，对数据进行冗余存储的方法，即磁盘阵列技术，尝试突破数据存储安全的瓶颈，从而为实现更加安全的数据存储技术提供一种思路。其中，本课题的具体研究内容包括以下几个方面：RAID6 磁盘阵列模型的构想及功能实现原理有限域代数及二元域运算的研究基于 Galois 域 GF（ ）的 Re

21、ed-Solomon 算法基于 Galois 域 GF（ ）的 Reed-Solomon 算法的程序实现及在 RAID6 阵列中的应用P 校验、Q 校验的程序实现基于 Galois 域 GF（ ）Reed-Solomon 算法的 RAID6 磁盘阵列的模拟实现基于 Galois 域 GF（ ）Reed-Solomon 算法的 RAID6 磁盘阵列数据恢复功能的模拟实现最终，本课题将模拟一个基于 Reed-Solomon 算法的 RAID6 级别的磁盘阵列( 以 4 块磁盘驱动器为例)，并成功完成在两块磁盘驱动器( 模拟)失效的情况下，对存储于其中的数据进行百分之百的恢复。1.4 本课题在领域内

22、研究的现状作为一项刚刚开始进入实际应用的新技术，RAID6模型的设计，算法的实现及产品的开发还未形成统一的规范和标准，正如美国企业管理协会(Enterprise Management Associates)资深分析师Mike Karp所说：RAID6磁盘阵列提供了重要的资料保障升级，让存储数组以合理的成本获得更完善的保护。对于那些读取频繁的应用系统，如任选视讯与其它固定内容应用等，RAID 6将是最理想的选择，也将是最获得市场青睐的磁盘阵列技术。因而，作为行业先驱者的各大厂商均按照RAID6所构想的基本目标要求纷纷推出了自己的RAID产品并形成自己的RAID6规范和标准，2005年末，Prom

23、ise公司及Intel存储事业部等就推出了自己的RAID6双重校验码硬盘存储架构产品。因此，本文也将按照 RAID6 所构想的基本目标要求，通过对有限域代数、基于Galois 域的 Reed-Solomon 算法的研究，将该算法应用于 RAID6 磁盘阵列及 RAID6 数据恢复的算法研究，最终完成基于 Galois 域 GF（ ）Reed-Solomon 算法、拥有创建和数据恢复功能的 RAID6 磁盘阵列(以 4 块磁盘驱动器为例)的模拟实现。8第二章 RAID(Redundant Array of Independent Disk)独立冗余磁盘阵列理论基础与 RAID6 模型的建立2.1

24、 什么是独立冗余磁盘阵列正如前所述，单个磁盘存储介质的安全性是难以保障的，最根本的原因在于其作为一种机械设备，必然会有物理上的损坏，从而造成不可预期的数据破坏。正是在这种情况下，采用多个磁盘驱动器协同工作，利用数据的冗余存储而避免数据被彻底破坏的方法应运而生，这种方法就是 RAID(Redundant Array of Independent Disk)独立冗余磁盘阵列。RAID 技术最早是由加州大学伯克利分校于 1987 年提出的，但它最初的目的却并不是为了专门应用于数据的安全领域，而是为了组合小的廉价的磁盘来代替大的昂贵的磁盘，因为当这种方法提出时，几个小容量磁盘驱动器的价格总和要比同等容

25、量的一个大容量磁盘驱动器的价格便宜得多，因此，RAID 一词最初的含义为 Redundant Array of Inexpensive Disks，即廉价磁盘冗余阵列。到了后来，当不存在以上所说的价格问题的时候，我们发现采用这种磁盘驱动器阵列的方法，把数据进行冗余后再进行存储，可以大大的提高数据存储的安全性，这时，RAID 才正式更名为 Redundant Array of Independent Disk，也就是独立冗余磁盘阵列。独立冗余磁盘阵列实际上是指一种由多块磁盘驱动器按照一定的要求构成的冗余阵列，在操作系统中，这多块磁盘驱动器将作为一个独立的大型存储设备而出现。RAID 按照不同的需

26、求和设计要求分为不同的级别(level)，需要说明的是，各个级别的差异是根据用户对于其需求的不同而设定的，之间没有性能上的比较，也不存在高级别是低级别的性能升级的情况。当有数据需要存储时，待存储数据首先需要按照不同级别的 RAID 系统的规定进行相关的处理，主要是加上冗余位信息，然后再和冗余位信息一起作为新的数据存入磁盘阵列当中。RAID，作为一种由多个存储设备组成的、能够协同工作的存储设备，可以充分发挥出其多个存储设备的优势：它既可以提升存储的速度，更可以增大容量 , 利用冗余信息位的作用，它很好地提供了对于数据的容错与数据灾难的恢复功能，不会因为单个存储设备的损坏而造成对数据的破坏，有的级

27、别的 RAID 系统还能够保证在若干存储个体出现故障时整个系统仍可以继续正常工作。2.2 已成功研发的各级别(level)RAID 系统原理、性能比较与原因分析RAID 技术从发明到现在，得到了迅速的发展，目前，已成功研发出的各级别磁盘阵列系统在各个领域得到了使用，其中，我们就最主要的 RAID 系统的工作原理、性能比较和原因分析如下：RAID 0 ：9RAID 0，我们又称之为 Stripe 或 Striping，即条带型存储，它代表了所有 RAID 级别当中最高的存储性能。RAID 0 提高存储性能的原理在于把连续的数据分散地存储到了多个磁盘驱动器上，这样，当系统有数据请求时，就可以由多个

28、磁盘并行的同时执行，每个磁盘驱动器执行属于它自己的那部分数据请求。这种数据上的并行操作可以充分利用总线的带宽，从而可以显著提高磁盘整体的存取性能。 图 2.1RAID0 的具体原理模型如图 2.1 所示：当操作系统向三个磁盘组成的逻辑硬盘（ RAID 0 磁盘组，在操作系统中表现为一个存储器）发出 I/O 数据请求时，该请求被转化为了 3项操作，其中的每一项操作都对应于一块单一的物理硬盘。我们从图中可以清楚的看到，通过建立 RAID 0 磁盘阵列，原先顺序的数据请求被分散到所有的三块磁盘驱动器中同时并行执行。从理论上讲，三块磁盘驱动器的并行操作可以使同一时间内磁盘读写速度提升3 倍( 当然，由

29、于总线带宽等多种因素的影响，实际的提升速率肯定会低于理论值) ，与单一的串行传输相比较，当大量的数据进行并行传输时速度的提升效果是十分显著的。但是，RAID 0 有一个明显的缺点，即它并没有提供数据的冗余处理，因此谈不上对数据拥有安全性能上的保护，一旦数据遭到破坏，则损坏的数据将无法得到恢复。综合来看，RAID 0 磁盘阵列所具有的特点，使其特别适用于对存储性能尤其是存储速度要求比较高，但对数据安全不太在乎的领域，如图形工作站等。当然，对于个人用户，RAID 0 也是提高硬盘存储性能的绝佳选择。RAID 1： RAID 1，我们又称之为 Mirror 或 Mirroring，即镜像磁盘阵列，

30、RAID1 的宗旨是最大限度的保证用户数据的安全性和可恢复性。 RAID 1 的操作方式是把用户写入磁盘驱动器的数据百分之百地自动复制到另外一个磁盘驱动器上。如图 2.2 所示：10图 2.2当操作系统读取数据时，系统先从 Disk 0 上开始读取数据，如果读取数据成功，则系统不再去管备份磁盘驱动器上的数据；而如果读取数据失败，则系统自动转向读取备份磁盘驱动器上的数据，从而不会造成用户工作任务的中断。当然，这也需要及时地更换损坏的磁盘驱动器并利用备份数据重新建立 Mirror，避免备份磁盘驱动器同时发生损坏时，造成不可挽回的数据损失。在 RAID1 中，由于对存储的数据进行了百分之百的备份，因

31、此， RAID 1 提供比较高的数据安全保障。但与此同时，同样由于数据的百分之百备份，备份数据占据了总存储空间的一半，因而，RAID1 的磁盘空间利用率低，存储成本较高。总的来看，RAID1 虽不能提高存储性能，但由于其具有较高的数据安全性，使其尤其适用于存放重要数据，如服务器和数据库存储等领域。 RAID 0+1：正如这种 RAID 的名字一样 RAID 0+1 是 RAID 0 和 RAID 1 的组合形式，也称为RAID 10。 我们可以以四个磁盘组成的 RAID 0+1 为例来分析它的原理，其数据存储方式如图 2.3所示。RAID 0+1 是兼顾存储性能和数据安全性的方案。它在提供与 RAID 1 一样的数据安全保障的同时，也提供了与 RAID 0 近似的存储性能。 但由于 RAID 0+1 同样通过数据的 100%备份的方式来提供数据安全的保障，因此RAID 0+1 的磁盘空间利用率与 RAID 1 是相同的，它的存储成本也比较高。 RAID 0+1 的特点使其特别适用于既要求有大量数据需要存取，同时又对数据安全性要求特别严格的领域，如银行、金融、商业超市、仓储库房、各种档案管理等。