（计算机软件与理论专业论文）raid系统中纠删码研究.pdf

摘要 通过使用超大规模集成电路技术和并行架构，计算机的处理能力有了显著的 增强。随着处理能力的增强，系统对输入输出性能的要求也随之提高。磁盘是计 算机的主要存储设备，但是其存取速度的提高非常缓慢。1 9 8 8 年，美国加州大学 伯克利分校的d a p a t t e r s o n 等人提出了廉价冗余磁盘阵列技术，该技术通过并行 来提高系统对磁盘的访问速度，并通过冗余来提高系统的可靠性。 虽然如今单个磁盘的可靠性已经非常高，但是一个由数百甚至上千张磁盘组 成的阵列在一天或者一周之内至少有一张磁盘失效的概率依然非常大。在大规模 磁盘阵列中，如何在灾难性磁盘失效中保护数据已经成为磁盘阵列设计的一个关 键问题。随着磁盘阵列规模的增加，容错更多的磁盘失效变得越来越重要。将编 码技术应用在存储系统中，特别是磁盘阵列中，有助于提高系统的可靠性。 本文完成的主要工作包括以下几个方面： 1 综述了廉价冗余磁盘阵列技术的特点和实现方法。研究了传统阵列中的编 码方法，概述了适用于磁盘阵列的编码技术的最新进展。 2 给出了x 码极大最小距离可分性质的一个证明。在此证明的基础上，详细阐 述了x 码的译码算法。 3 给出了四种典型的纠删码：x 码，e v e n o d d 码，s t a r 码和r s 码的模拟仿 真，仿真结果表明了算法的可行性和正确性。分析这几种码的性能和优缺 点。 关键词：容错r a i d 系统纠删码可靠性 a b s t r a c t p r o c e s s i n gp o w e rh a s i n c r e a s e d d r a m a t i c a l l yt h r o u g hv e 巧l a r g es c a l e i n t e g r a t i o nt e c h n o l o g ya n dp a r a l l e la r c h i t e c t u r e si nc o m p u t e rs y s t e m a sp r o c e s s i n g p o w e ri n c r e a s e s ，s od o e st h ed e m a n df o ri n c r e a s e di n p u t o u t p u tp e r f o r m a n c e b u tt h e a c c e s ss p e e dt oh a r dd i s kw h i c hi st h em a j o rs t o r a g ed e v i c ei nc o m p u t e rs y s t e mh a s i n c r e a s e dv e r ys l o w l y t w od e c a d e sa g o ，t h ec o n c e p t i o no fr e d u n d a n ta r r a y so f i n e x p e n s i v ed i s k s ( r a i d ) w a si n t r o d u c e db yd a v i dp a t t e r s o ni nu n i v e r s i t yo f c a l i f o r n i aa tb e r k e l e y i nr a i ds y s t e m ，p a r a l l e li su s e dt or a i s ed a t a - a c c e s sr a t ea n d r e d u n d a n c yi sa d d e di nt oi m p r o v es y s t e m sr e l i a b i l i t y a l t h o u g ht o d a ys i n g l ed i s k sa r eh i g h l yr e l i a b l e ，w h e nad i s ka r r a yc o n s i s t so f h u n d r e d so fe v e no n et h o u s a n dd i s k s ，t h ep r o b a b i l i t yt h a ta tl e a s to n ed i s kw i l lf a i l w i t h i nad a yo raw e e ki sh i g h h o wt op r o t e c td a t aa g a i n s tc a t a s t r o p h i cd i s kf a i l u r eh a s b e c o m eac r u c i a li s s u ei nt h ed e s i g no fv e r yl a r g ed i s ka r r a y s w i t i lt h ei n c r e a s eo ft h e d i s ka r r a ys c a l e ，t o l e r a t i n gm o r ed i s kf a i l u r e sb e c o m e sm o r ea n dm o r ei m p o r t a n t i t w i l li n c r e a s et h er e l i a b i l i t yo fs t o r a g es y s t e mw h e nc o d i n gt e c h n i q u e sa r ea p p l i e di n s y s t e m ，e s p e c i a l l yi nt h er a i ds y s t e m n l em a i nc o n t e n t sa n dr e s u l t sa r ea sf o l l o w s 1 t h ef e a t u r e sa n dm a i ni m p l e m e n t a t i o nm e t h o d so fr a i da r es u m m a r i z e d t h ec o d i n gm e t h o d si nt r a d i t i o n a lr a i da r es t u d i e da n dt h en e w d e v e l o p m e n to fe r a s u r e - c o r r e c t i n gc o d e sw h i c hc a nb ea p p l i e di nr a i di s g e n e r a l i z e d 2 a n o t h e rp r o o fo ft h em a x i m u md i s t a n c es e p a r a b l ep r o p e r t yo fxc o d e si s p r e s e n t e d b a s e do nt h i sp r o o f , t h ed e c o d i n ga l g o r i t h mi sd e s c r i b e di nt h i s p 印e r 3 f o u rt y p i c a lc o d i n gs h e m a si nr a i d ，e v e n o d d ，xc o d e s ，s t a ra n dr s ， a r es i m u l a t e di ns o f t w a r e ；t h e i rf e a s i b i l i t ya n dc o r r e c t i o na r ed e m o n s t r a t e d i nt h es i m u l a t i o n t h e i rp e r f o r m a n c e sa r ea n a l y z e dr e s p e c t i v e l ya n dt h e i r a d v a n t a g e sa n dd i s a d v a n t a g e sa l ea l s od i s c u s s e d k e y w o r d s ：f a u i tt o e r a n c e r a i ds y s t e m e r a s u r e c o r r e c t i n gc o d e s r e i a b ii t y 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人警烨 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文和使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复印手段保存论文。( 保密的论文 在解密后遵循此规定) 本人签名： 导师签名： 日期妞z ：j ，! 么堡 日期刎了天疹 第一章绪论 第一章绪论 本章介绍了廉价冗余磁盘阵列概念提出的时代背景，说明了纠删码在磁盘阵 列中实现数据保护的重要意义。然后介绍了该技术的基本特点，说明了这些特点 的实现原理。回顾了纠删码的发展历史，描述了大规模存储中纠删码技术的研究 和发展现状。最后总结了作者的主要工作，给出了全文的安排。 1 1 廉价冗余磁盘阵列 1 1 1 廉价冗余磁盘阵列的提出 如今，人类已经从工业时代进入了信息时代。在信息存储领域，随着影像， 文字，图形及声音等多媒体数据资料越来越多的被存储在计算机系统中，信息资 源数量的飞速膨胀导致我们必须要考虑如何对海量的数据进行存储和传输【l 】。社 会信息化程度的深入和推广，使人们逐渐认识到信息的重要性，这就需要对大量 的信息进行快速的存储和管理。 长期以来，计算机系统中c p u 的运算速度和性能不断提高，而作为计算机系 统主要存储设备的磁盘存储器的存取速度增长却十分缓慢，因此出现了令人头痛 的“i o 瓶颈”问题。这是因为计算机的c p u 和内存等部件使用的是电子设备， 而磁盘i o 速度要受到盘片旋转和动臂机械性质的限制，增长缓慢，影响了计算 机的整体性能。 为了解决上述的两个问题，提高计算机的容错性，缩小c p u 和i o 系统之间 的速度差异，1 9 8 8 年，美国加州大学伯克利分校的p a t t e r s o n ，g i b s o n 和k a t z 在 a c ms i g m o d 大会上提出了“廉价磁盘冗余阵列”( r e d u n d a n ta r r a yo f i n e x p e m i v ed i s k s ，r a i d ) 的概念【2 】。其设计原理是：通过资源冗余来提高服务 质量，它将多个独立的磁盘组织成一个逻辑盘，以提供更大的存储容量；通过数 据分割、多通道并行读写来提高i o 速率；通过保存冗余的数据、校验信息及简 单的容错编码来提高存储的可靠性【3 】【4 j 【5 l 。r a i d 技术在提高系统i o 速度、数据 传输率、数据可靠性和数据存储容量方面取得了很好的效果。近些年来，由于大 部分磁盘驱动器都可谓是“廉价 的，r a i d 咨询委员会( r a i da d v i s o r yb o a r d ， r a b ) 决定使用“独立 ( i n d e p e n d e n t ) 来代替“廉价一词。但是这只是名称 的变化，实质内容并没有改变。r a i d 的出现解决了当时迫切的i o 瓶颈，也避 免了对单个高价大容量磁盘( s l e d - - - s i n g l el a r g ee x p e n s i v ed i s k ) 的研究和设计， 2r a i d 系统中纠删码研究 极大了的降低了海量存储的代价。 由于是对多个磁盘并行操作，所以与单一磁盘相比，r a i d 磁盘子系统的输 入输出性能得到了提高。服务器会把r a i d 阵列看作一个单一的存储单元，并对 几个磁盘同时存取，所以提高了输入输出速率。在当时s l e d 最大容量为2 5 0 0 m b ， 速率不超过1 0 0 m b s 的情况下，这一新技术显示了巨大的魅力。更为主要的是 r a i d 将数据分布在了不同的磁盘上，因此还可以保证一定的容错性【6 】。 早期的r a i d 系统使用最简单的奇偶校验技术来保障数据的可靠性【7 】【8 】【9 】，至 多只能容许一张磁盘失效。当系统规模较大时，同时发生多张磁盘失效的概率比 较高，存储系统的可靠性迅速降低。近些年来，许多研究者将纠删码技术作为分 布式存储系统中一种冗余机制来提高系统的可靠性，保证分布式存储系统数据的 高可用性和高容错性【1 0 1 1 1 1 1 1 1 2 】【1 3 】。其基本思想是：首先将要存储在系统中的文件分 割成k 块，然后采用纠删码技术对其编码得到疗个文件块，通过将这些文件碎片 分布到系统中的不同节点来实现冗余容错。当恢复数据时，只需从这些节点中获 得k ( 七七) 个可用的文件片，就可以重构得到原始文件。纠删码技术在没有过量 存储开销的基础上，通过合理的额外存储来提供系统的高可靠性和可用性。目前， 分布式存储系统纠删码技术研究已经成为热点问题【1 4 】【1 5 1 1 1 6 】【1 7 1 。 1 1 2 廉价冗余磁盘阵列的特点 存储工业界投入了大量的时间和财力来研究和开发r a i d 产品，它的一个显 著优势就是扩大了磁盘的容量。如果这是r a i d 的唯一优势，r a i d 就不会像今 天这样流行了。除了容量之外，r a i d 在可管理性、性能及可靠性方面都有其优 势。 1r a i d 容量的扩展性 r a i d 的基本概念之一是磁盘驱动器虚拟化，即虽然内部由多个驱动器组成， 但是在外部主机系统看来，r a i d 是一个单一的、快速可靠的大容量磁盘驱动器。 过去，建立支持大数据量的处理系统时，数据存储的扩展性是一个令人头疼的问 题。 比如对于w e b 服务器，为了支持日益增长的数据，存储系统必须提供足够 的存储容量。一旦一个存储子系统爆满，就需要安装新的磁盘驱动器。同时，任 何主机系统的i o 插槽数量总是有限的。因为每个新的磁盘驱动器都要占有一个 系统i o 插槽，最后存储系统将不得不扩展到多个服务器上。这不仅增加了成本， 也不可避免地造成管理上的困难。r a i d 的出现在一定程度上缓解了这方面的问 题，因为每个r a i d 可包含多个磁盘驱动器，但是只需要一个主机i o 插槽。 第一章绪论 需要指出的是，r a i d 的可用容量一般来说要小于成员容量的总和。这是因 为r a i d 管理算法需要一定的冗余开销，冗余开销与所采用的算法有关。在已知 r a i d 算法和成员磁盘容量的前提下，可以计算出存储子系统的可用容量。般 而言，r a i d 可用容量是成员磁盘容量总和的5 0 到9 0 。 2r a i d 的可管理性 由于r a i d 的设备虚拟化，可以将多个容量相对小的磁盘组成一个大容量的 虚拟驱动器。这样，用户就可以在这个虚拟驱动器上建立单一的文件系统来组织 和存储应用系统所需要的信息。与在每个成员磁盘上个建立一个文件系统并把数 据分配到各个文件系统中相比，这种方法可以节省很大的工作量。系统管理员只 需管理单个虚拟驱动器，而对各个实际成员驱动器的管理则由r a i d 本身来完成。 3r a i d 的高性能 通过分块访问，r a i d 可达到比单个磁盘驱动器更高的性能。磁盘分块操作 可以把主机i o 操作分散到各个成员磁盘驱动器中，因而在同一时间内可完成比 单个驱动器更多的i o 操作。分块访问有两种不同的方法，即并行访问和独立访 问。与这两种分块访问方法相对应，r a i d 阵列亦可分为并行访问分块阵列和独 立访问分块阵列。 ( 1 ) 并行访问分块阵列 并行访问分块阵列的工作原理是：对主机的每一个i o 请求，各成员磁盘驱 动器执行相同的、短时间的操作，包括转动磁盘臂以正确定位、把数据从缓冲区 写到盘片上或把盘片上的数据读到缓冲区中。采用这种方式，一般要求个成员磁 盘驱动器的电气特性( 如磁盘转动速度、读写速度等) 保持一致。这增加了设计 以及实现上的难度，因而此类阵列的成本相对比较昂贵。 通过充分利用缓冲区设计，并行访问分块阵列方式把主机的i o 请求分布到 多个驱动器中，从而降低了i o 时间( 就单个驱动器而言) ，提高了r a i d 性能。 对于以长时间的顺序访问为特征的应用，例如多媒体、图像处理、大型文件访问、 c a d 、数据库等，并行访问分块阵列能够较好的工作。但是，并行访问分块阵列 并没有有效地解决磁盘的寻道延迟问题。在随机的、大量i o 的事务处理环境下， 磁盘寻道延迟是影响其性能的主要因素。因此，在这种情况下，并行访问分块阵 列的效果并不好，需要应用独立访问方式。 ( 2 ) 独立访问分块阵列 采用独立访问方式的r a i d ，成员磁盘无需做同步操作，即它们各自可以在 同一时间执行独立的y o 操作。独立访问的优势是支持重叠i o 操作，从而缓解 了因单个驱动器的磁盘臂定位延迟而导致的i o 瓶颈问题，提高了整体性能。如 前所述，独立访问方式适用于大量随机i o 事务处理应用系统，例如e r p ，电子 4r a i d 系统中纠删码研究 商务、多用户服务器等。 4r a i d 的可靠性 r a i d 的另一个特性是其可靠性和可用性。直觉上是由多个磁盘驱动器组合 而成的r a i d 似乎还不如单个磁盘驱动器来得可靠。不过这种直觉是基于这样的 隐含假设：任何一成员磁盘驱动器的失败将导致整个r a i d 的失败。我们将会看 到，由于r a i d 的数据冗余技术，上面的假定是不真实的。 影响r a i d 可靠性和可用性的因素是多方面的。除数据冗余外，电源失败是 影响存储设备可用性的又一重要因素。预防电源失败的常用方法是采用冗余电源 和后备u p s ( u n i n t e r r u p t i b l ep o w e rs y s t e m ) 系统。此外，还需要一种方法，使 r a i d 出现故障的时候，能够在不影响正常操作的情况下进行修复，以维持系统 2 4 x 7 全天候可用性。r a i d 的这种能力称为热交换( h o ts w a p ) 能力，是r a i d 的设计时需要考虑的因素之一。 最直观、最原始的冗余技术就是所谓的镜像冗余，即把某一个磁盘驱动器上 的数据完全复制到另一个驱动器上。这样，当一个驱动器失效时，总是有备份驱 动器可以使用。但是这种冗余技术需要5 0 的额外容量开销。 为减少容量开销额，通常采用的方法是校验冗余。与镜像冗余不同，校验冗 余是把一个或多个磁盘驱动器上的数据校验值( 而不是数据本身) 备份到另一个 驱动器上。由于从容量方面看，校验可以比数据本身少很多，因此这种技术的冗 余开销要来得少。 失效磁盘 校验磁盘 图1 1 用x o r 算法产生校验数据图1 2 用x o r 算法恢复失效磁盘数据 图1 1 是采用异或( x o r ) 算法产生冗余校验的示意图。这是一个包含4 个磁 盘驱动器的阵列，其中一个磁盘驱动器作为校验磁盘使用。校验磁盘上存储的是 其它3 个数据磁盘相应位置数据的异或值。根据异或算法的特点，如果任何一个 磁盘失效，其数据可以由其它完好磁盘相应位置数据的异或值来恢复，如图1 2 所示。 需要说明的是，在实际实现时，校验数据并不一定要存储在同一磁盘上，而 是可以分布到各个成员磁盘中。不过校验数据的总容量仍然等于一个磁盘的容量。 所以，这种冗余校验的额外开销将与阵列中的磁盘个数成反比。图1 1 中的阵列 有4 个磁盘，其额外开销为2 5 。若磁盘个数增加为5 个，冗余额外开销将降低 第一章绪论 到2 0 。 从图1 1 可以看到，对每一个写操作，r a i d 控制器必须做一次异或运算。这 必然要求更多的内存和c p u 周期，当其它条件不变时，系统性能将受到影响。也 就是说，这种技术是以牺牲性能为代价来实现数据冗余保护的。 1 2 分布式存储系统中纠删码技术研究现状 在分布式存储系统中，早期使用的纠删码技术是最简单的+ 1 奇偶校验码， 容许单个磁盘失划1 8 】【1 9 1 1 2 0 】【2 1 1 1 2 2 1 。但是，随着磁盘阵列的增大，同时发生多个磁 盘失效的概率较高，存储系统的可靠性迅速降低，容许单个磁盘失效远远不能满 足系统的需要。在文【3 】中提出了一维奇偶校验分组的方法：数据磁盘设备划分为 m 组，每组能够纠正1 个磁盘的错误，多组可以纠正多个磁盘的故障；同时还提 出了二维奇偶校验码，能够纠正任意的两个磁盘失效。随后，在文献【9 】中建议采 用海明码，也能纠正任意两个磁盘失效。但是，这两种码都不是m d s 码，冗余 盘的数目是磁盘阵列系统中总盘数的对数，冗余信息量太大，代价昂贵，。般很 少使用。 阵y u - 幺q 删码由于在编码过程中只采用简单的二进制异或运算，在软硬件中很 容易被实现。在相同的编码效率下，阵列纠删码按照计算复杂度比r s 纠删码来 的更加有效，因此一直是分布式存储系统中纠删码技术研究的热点问题 2 3 1 2 4 】【2 5 】【2 6 】【2 7 】【2 8 2 9 1 1 3 0 】【3 1 1 3 2 1 。在磁盘阵列中，阵列纠删码的研究一直大多集中在纠 双错m d s 阵列纠删码上，例如e v e n o d d 码【2 6 】 2 8 】【3 2 1 、x 码【l o 】【3 3 】【3 4 】【3 5 1 、b 码【1 0 】【3 6 】、 b c p 码【3 7 1 、r d p 码【3 7 1 、s 码【3 9 1 等。但对纠多列错阵列纠删码的研究并不多，特别 是纠多列删除的m d s 阵列码研究，只有少数的几类纠多列错阵列码被提出。在 文 4 0 4 1 中，b l a u m 等人提出了一种纠多列错m d s 阵列码，后来又提出一种广 义e v e n o d d 码( t h eg e n e r a l i z e de v e n o d dc o d e s ) ，统称为b l a u m 码。t a u 和 w a n g 提出的h d d i 和h d d 2 码【4 2 1 ，能够同时允许3 个以上磁盘同时故障。差不 多直到2 0 0 4 年之后，纠多错( 大于等于3 ) 的阵列纠删码才有了新的进展。在2 0 0 4 年u s e n i xf a s t 会议上，j e i f h a r t l i n e 提出了一种具有最佳更新复杂性的r 5 x 0 阵y , j 坌q 删码1 3 0 1 。到了2 0 0 5 年，u s e n i xf a s t 会议上，同时出现了三篇有关纠多 列错的阵y , j 坌q 删码的文章：h o v e r 码【4 3 1 ，w e a v e r 码【4 4 1 ，s t a r 码【3 1 1 。r 5 x 0 ， h o v e r 码和w e a v e r 码都是i b ma l m a d e n 实验室r a i ds t o r a g es y s t e m 存储研究 小组提出来，能够同时容许多个磁盘故障，但是按照冗余量和恢复能力来说没有 达到最佳。h u a n g 和x u 在e v e n o d d 码的基础上，提出了一类能够纠正任意三 个磁盘错误的s t a r 码，该码的最小列距为4 。 除了阵p 0 - 幺q 删码，r s 类纠删码是另一类在分布式存储系统中应用的纠删码技 6r a i d 系统中纠删码研究 术。r s 类纠删码纠删码技术在分布式存储系统中早期的研究可以追溯到1 9 8 9 年， 在文 4 5 中，r a b i n 针对网络结点( 服务器) 的故障和网络带宽的问题，提出了基 于r a b i n 码的信息拆分算法。信息拆分算法实现的核心技术就是r s 类纠删码。 另外，采用r s 类纠删码技术产生冗余校验块，实现容许任意两个磁盘同时失效。 但直到近几年，n o n n e n m a c h e r ，b l o e m e r ，r i z z o 和p l a n k 等人专门研究了r s 类 纠删码【4 6 】【4 7 1 。在1 9 9 7 年r i z z o 和p l a n k 分别提出了两种简单的r s 类纠删码软件 实现方法，使得r s 类纠删码不再依赖于硬件实现，直接推动了r s 类纠删码在分 布式存储系统中的应用。 随着分布式存储系统和纠删码技术的进一步发展，低密度纠删码( l d p c ) 开始在分布式存储系统中得到应用，特别是以t o r n a d o 码【4 8 1 4 9 】为首的数字喷泉系 列码。在文献 5 0 】 5 1 】中首次提出了采用t o r n a d o 码实现分布式冗余机制，来保障 分布式存储系统i n t e r m e m o r y 的可靠性以及提高读取速度。随后t o m a d o 码在 o c e a n s t o r e 子系统t y p h o o n 文件系统中得到应用，采用t o r n a d o 码和r s 类纠删 码共同来实现分布式冗余容错机制。在这之后，文【5 2 5 3 】对l d p c 码在广域网分 布式存储系统应用进行了研究。文【5 4 】 5 5 】进一步分析了l d p c 码和r s 码的性能， 并说明在大规模存储系统中，l d p c 码比基于r s 码的纠删码( 范德蒙码，柯西 码等) 更有效。这类码不仅提供接近最优的损失保护，而且能以线性时间编码和 译码。但是l d p c 码是一类非确定性的码，译码过程具有概率性，不能保证译码 肯定成功。可能损失数目很小的信息块，被删除的信息就得不到完全的恢复。因 此这种编码适合于解决i n t e m e t 上的包传递问题，但并不完全适合分布式存储系 统，特别是对于1 0 0 数据恢复的存储系统。后来人们对l d p c 码进行了一定的 改进，能够一定程度上提高其译码成功率，但仍然不能保证1 0 0 的译码成功。 综上所述，在分布式存储系统中纠删码技术的研究主要有3 类纠删码： ( 1 ) 阵列纠删码；( 2 ) r s 类纠删码；( 3 ) l d p c 码。 1 3 本文主要内容及安排 r a i d 的提出解决了当时高端服务器需要的海量存储和快速存取需求，避免 了对单个高价大容量磁盘的研究。它的出现极大的降低了海量存储的成本，提高 了对磁盘的访问速度。传统的磁盘阵列只能容许一个磁盘故障，这在早期r a i d 系统比较小的时候可以满足系统的安全性要求。随着磁盘阵列规模的不断扩大和 应用的日益广泛，容许更多的磁盘故障对r a i d 系统显得越来越重要起来。为了 解决日益严峻的r a i d 容错问题，人们开始研究针对r a i d 系统的新的编码方案。 这些研究在近几年取得了长足的发展，为r a i d 更强容错的实现提供了技术保障。 本文研究了近几年来针对磁盘阵列的纠删码研究和发展情况，说明了容错对 第一章绪论 7 磁盘阵列的重要意义。在深入学习这些编码方案的基础上，提出了一种基于素数 有限域逆元的x 码极大最小距离可分性质的证明方法。该方法只使用了初等数论 的基础知识，简洁明了，可以从证明中直接演化出该编码的译码算法。详细描述 了i 峪码的软件实现方法，说明了它在容错中的重要意义。对文中涉及的 e v e n o d d 码、x 码、二维奇偶校验码、s t a r 码和r s 进行了程序仿真，并给 出了理论和程序的分析结果。 本文的内容主要分为五章，其具体安排为： 第一章介绍了磁盘阵列的概念和重要意义，说明了它的技术特点。回顾了纠 删码的发展历史和现状。 第二章介绍了纠删码的基本原理和r a i d 的分级制度，是文章后面章节的基 础。其中分析了r a i d 系统的可靠性模型，说明了使用容错编码的必要性和重要 意义。 第三章介绍了容许单盘和双盘故障的r a i d 编码技术。传统的r a i d 只能够 容许单个磁盘故障；使用的编码技术包括一维奇偶校验码和海明码，这两种编码 都只能够容错单个磁盘故障。针对传统r a i d 的容错能力不足问题，介绍了关于 双盘容错的编码技术的进展情况。这些编码主要包括二维奇偶校验码、e v e n o d d 和x 码。对其中的x 码的极大最小距离可分性质提出了一个自己的证明方法，在 此基础上，演示了具体的译码算法以及一条译码链译码算法的伪代码。最后给出 了该章涉及的编码方案的理论和仿真性能分析。 第四章在第三章的基础上，进一步讨论了容许多盘( 大于等于三张磁盘) 失 效的编码方案，这些编码出现的时间不长。很多的编码都有复杂的理论基础，特 别是s t a r 码和r s 码，前者建立在素数有限域的基础上，而后者建立在伽罗华 有限域的基础上。该章的最后给出了该章涉及的编码方案的理论分析和仿真结果。 最后总结了本文的所有工作，指出了磁盘存储技术应与网络分布式存储结合 起来，以抵抗区域性灾难事件，从而提供更安全的数据保护机制。 第二章纠删码原理和r a i d 概念 9 第二章纠删码原理和r a i d 概念 本章首先详细的说明了纠删码的原理和相关的基本概念，在此基础上，引出 了适合r a l l ) 系统的阵列纠删码概念。然后描述了r a i d 的分级规则，并详细说明 了它们各自的技术特征。最后分析了r a i d 系统的可靠性模型，说明了数据冗余对 系统的重要意义。 2 1 1 一般纠删码原理 2 1 纠删码原理 一般地，纠删码可以使用一个四元组( 挖，k ，b ，k ) 来表示。设其编码函数为e ， 译码函数为d ，对于消息m = ( m ，m ：，m i ) ，其中m ，为大小为bb i t s 的消息包， 编码后的消息e ( m ) = ( mr ，m ：，m ：) ，其中m ：( 1 k 疗) 大小仍然为6b i t s 。设 m 为e ( m ) 中任意尼( 七七) 个包组成的子消息，则d ( m ) = m ，即对e ( m ) 中任 意的k 个消息进行解包就可以得到源消息。( 疗，k ，b ，k ) 纠删码编码和译码的过程如 图2 1 所示。 编码数据接收数据 n k k 图2 1( 玎，k ，b ，k ) 纠删码编码和译码过程 在图2 1 中，其中出现“ 的地方是表示数据的丢失，也就是删除发生的位 置。这种模型和纠错码模型有本质区别：纠错码中，数据不是丢失，而是所有的 数据都可以被完全的接收到，但是接收方不能保证接收到的任何数据的正确性。 这样以来，接收方需要首先检查接受到的数据的正确性，如果是正确的，则不作 1 0r a i d 系统中纠删码研究 任何处理；如果错误，纠错码还要有能力发现这些错误发生的位置，并进而进行 纠正。纠删码的情况是，接受方根本就没有接受到一些数据，因此可以明确感知 这些删除发生的位置。译码器需要作的只是根据已知的信息恢复原始的数据信息。 另外，一个( 以，七) 线性纠删码常用的表示方法为：y = x g ，其中 x = x 0j c l ，x 七1 ) ，y = y 0 , y l ，一，y ) ，g 是一个k 疗的矩阵，g 称为( 甩，k ) 线 性纠删码的生成矩阵。若果g 的任意k 列组成的子矩阵g 均可逆，则称为( 甩，k ) 线 性纠删码。 2 1 2 阵列纠删码 目前，由于阵y d - 幺q 删码怕驯的编码和译码过程只需要简单的异或运算，并且与 相同码率的r s 类纠删码比较，编译码复杂度低。同时软硬件实现简单，因此有 多种阵列纠删码应用于分布式存储系统。 阵列纠删码也是一种线性纠删码，但是与常见的线性纠删码不同，它并不是 把信息位放在一个一维的向量中，而是放在二维阵列中。对于一个g ( q ) 上大小为 m x 刀的阵列码，可以看作是群g ( q ”) 上的一维线性码。若阵列码c 的码字总数为 ，则c 的维数可以定义为k = l o g n ，故c 能看作是一个g ( q ”) 上的一维 ( 聆，k ，d ) 线性码。码的最小距离d 也是在g ( q ”) 上定义，c 中除了零码字，非零列 列数的最小值称为二维阵列码c 的最小列重量，即码的最小列距离。若( 玎，k ，d ) 达 到了s i n g l e t o n 界，即d = 刀一k + 1 ，那么c 就是一个极大最小距离可分码( m d s 阵列码) ，具有最强的纠错能力【57 。 事实上，对于一个g ( g ) 上大小为m x r l 的阵列纠删码，它的一个码字可以看 作g ( q ) 上一个长度为m x n 的向量。这个向量包含 个分块，每一个分块包含m 个 元素，这个元素可以是1 比特或者多比特数据。根据这种对应关系，第f 块对应 阵列中的第f 列，向量每块中的m 个元素对应阵列中相应列的m 个元素。 2 2r a i d 的组织与分级 2 2 1r a i d 的分区及数据组织 1 分区和阵列 正如需要对p c 中的硬盘进行分区一样，r a i d 也需要对所管理的磁盘分区， 以便对数据进行处理。根据r a i d 咨询委员会的定义，分区指的是一组地址连续 的成员磁盘存储块。单个磁盘可以有一个或者多个分区，如果在一个磁盘定义了 第二章纠删码原理和r a i d 概念 多个分区，则它们的大小可以不同。多个不连续的分区可以通过虚拟磁盘到成员 磁盘的映射，成为同一虚拟磁盘的一部分。分区可被进一步组织成所谓的阵列， 阵列中的分区大小应相同。不规则的分区会产生存储校验问题，也会导致阵列地 址映射问题。如果阵列中的分区大小不同，控制器会选取最小分区的大小，较大 分区的多余部分将被忽略。 磁盘1磁盘2磁盘3 磁盘4 图2 2四张成员磁盘分区不例 图2 2 给出了一个由4 个磁盘组成的分区示例图，每个磁盘都定义了多个分 区。磁盘1 和磁盘3 定义了3 个分区( a ，b 和c ) ，磁盘2 和磁盘4 有4 个分 区( a ，b ，c 和d ) 。有多种方法可以将这些分区组合成阵列。比如说，将所有 这些磁盘中相应的a 、b 和c 分区组成阵列，即将分区1 a 一4 a 组成阵列a 、分区 1 b 4 b 组成阵列b 、分区1 c 4 c 组成阵列c 。另外，把分区2 d 和4 d 组成阵列d 。 2 分块和分条 根据r a b 的定义，分块是将一个分区分成一个或多个大小相等、地址相邻 的块，同一阵列中分块的大小相同。 正如分区可以组成阵列一样，分块组合成所谓的分条。r a b 对分条的定义如 下：分条是磁盘阵列中的两个或者更多分区上的一组位置相关的分块。所谓位置 相关是指，每个分区上的第一个分块属于第一分条，每个分区上的第二个分块属 于第二个分条，以此类推。 换言之，分条以某种方式组合多个分区上的分块。图2 3 显示了定义在同一 阵列上的4 个分区，在每个分区上有两个分块( 分块1 和分块2 ) ，4 个分块l 组成了一个分条，4 个分块2 也组成了一个分条。 阵列中的分条将被映射为虚拟驱动器中连续的块。当主机向虚拟驱动器写入 数据时，r a i d 控制器将请求地址转换为阵列中的分条。首先将第一个分区的对 应分块执行写操作，然后对第二个分区的对应分块执行写操作，接着对第三个分 区对应的分块执行写操作，以此类推。 1 2 r a i d 系统中纠删码研究 2 2 2r a i d 的分级 图2 3分块组成分条 分 条 l 在众多的r a i d 产品中，有6 种是加州大学伯克利分校的科学家们开发的。 所有r a i d 产品的一个共性在于它们都是由两个以上的硬盘虚拟地组合在一起形 成的大容量的单一存储设备。另外，在很多的r a i d 模式中都有较为完备的相互 校验恢复的措施，甚至是直接的相互镜像备份。从而大大提高了r a i d 系统的容 错性，保障了系统的稳定冗余性，这也是“r e d u n d a n t 一词的由来。 lr a i d 0 等级 r a i d 0 是无冗余无校验的磁盘阵列，又称为条带化( s t r i p i n g ) 的阵列，全称 是没有容错的条带磁盘阵列( s t r i p e dd i s ka r r a yw i t h o u tf a u l tt o l e r a n c e ) 。r a i d 0 的工作原理可以用图2 4 来表示。数据在存储时，由r a i d 控制器将其分割成大 小相同的数据条，并写入阵列中的各个磁盘。在读取数据时，也是同时从硬盘中 读取条带块，由于读写基本上都是基于并行的数据传输，所以这种阵列模式的读 写速度在所有r a i d 类型中最快，但是r a i d 0 没有提供数据的容错保护。 图2 4r a i d 0 结构示意图 2r a i d l 等级 r a i d l 是利用镜像技术来实现存储数据容错的阵列技术，它的关键点就是对 所存放数据的完全冗余。r a i d l 中的数据盘与镜像盘没有任何主从关系，它们是 第二章纠删码原理和r a i d 概念1 3 可以互为镜像或恢复的。这种方法虽然实现简单，但实现成本却要比r a i d 0 贵1 倍。它的工作原理如图2 5 所示。在这种阵列模式下，任何一块硬盘出现故障都 不会影响到整个阵列的正常工作，因为它还有一个镜像盘可以工作。甚至还能实 现在将近5 0 的硬盘失效的情况下，整个阵列系统不问断地工作。 图2 5r a i d l 结构示意图 3r a i d 2 级别 r a i d 2 又称为纠错海明码磁盘阵列。它是目前r a i d 阵列中最复杂的级别， 其主要原因就是它所采用的错误检测与修复技术一海明码( h a m m i n gc o d e ) 。海 明码是在原有数据中插入若干校验位来进行错误检查和纠正的编码技术。它根据 现有的数据编码各位的值，生成自己的校验码。然后再将校验码与原有的数据码 相合并，转换成新的数据编码。图2 6 是一个校验值个数为3 的r a i d 2 逻辑结构 图。 图2 6r a i d 2 结构示恿图 4r a i d 3 级别 r a i d 3 是在r a i d 2 的基础上发展而来的，关键是使用相对简单的异或校验 代替了复杂的海明校验，大大降低了阵列的实现成本。x o r 的原理就是，当两个 数据位比较时，相同为0 ，不同为1 。而且，在知道了x o r 值和两个数据位中的 任何一个，都可以反推出另一位的值，如图2 7 所示。 r a i d 系统中纠剧码研究 罔哮毒鲁 斟蚓重蔬、一 5r a i d 4 级别 r a i d 4 是独立的数据盘与共享的校验盘阵列技术，其全称为i n d e p e n d e n td a t a d i s k sw i t hs h a r e dp a r i t yd i s k 。r a i d 4 的关键之处是充分利用了数据块的优点，它 在分配存储空1 9 时是以数据块为单位进行的。r a i d 4 将数据块划分为足够包含一 个完整的文件，其主要目的是为了保证存储数据的局部完整性，不会受到因对完 整数据进行条带化并分散存储于其它硬盘上后带来多个硬盘出错对数据的影响。 6r a i d 5 级别 r a i d 5 是目前市场上最常见的r a i d 产品，它是种无独立校验盘的奇偶校 验硬盘阵列，它具有较高的存储性能、较强的数据安全性以及较低的实现成本等 特点。r a i d 5 同样也是采用x o r 校验来检查阵列中的存取错误。但不同的是它 没有独立的校验盘，而是把数据与其对应的奇偶校验信息分别存放到不同的硬盘 上。r a i d 5 的交叉丐技术主要是用来减少阵列写操作时的瓶颈问题。数据的写入 过程如图2 8 所示。 m # i# 2 l 。一 p 叫_ _ ! 生 p 譬 l ! 叫”“一 l ! 叫1 l ! 坠1 l 旦叫“”、“卜! ! | i 跬” _ i 船” ” ”j”_ i 。毒副刮胃一生! l 【耍 雪e 驾 l ! 坚二_ 4 ，竺型世! ：= _ 世! 型 圈2 8r a i d 5 的写入示意图 7r a i d 组合技术 目前常用的r a i d 并不是独立的一种级别，而是多种级别组合应用的例子。 第二章纠删码原理和r a i d 概念1 5 般是两种级别的组合，现有的大量文献资料中提到的组合方式有r a i d 0 1 、 r a i d l 0 、r a i d 3 0 、r a i d 5 0 、r a i d 5 3 等。但最具有现实意义的是r a i d 0 1 和 r a i d l 0 r a i d 阵列具有构建成本低、硬件功耗小、数据传输率高等优点。同时，r a i d 阵列还拥有容错和自动恢复失效硬盘的技术。所以，与同容量的硬盘相比，i 认i d 阵列的应用价值很高。目前，它已经广泛用于社会各个部门中，由它构成的存储 系统可以达到单个硬盘的几倍、几十倍甚至上百倍的效能。现在，r a i d 阵列正 在从高端的服务器向个人计算机用户转移。 2 3r a i d 系统的可靠性问题 2 3 1 系统的可靠性 一个容错系统的可靠性可以从多个方面来评价，作为数据的存储系统，其基 本功能是提供数据的存储和读取操作。因此，系统的有效度和数据的可用性是极 为重要的两个方面，两者反映了系统对设备故障和读写误码的容错能力。 1 系统的有效度 设系统的平均无故障时间为m t t f s ( m e a nt i m et