（计算机软件与理论专业论文）双容错raid数据布局方法的研究.pdf

摘要 双容错r a i d 数据布局方法的研究 摘要 自从d a v i dp a t t e r s o n 等人在1 9 8 8 年提出r a i d ( r e d u n d a n ta r r a y s o f i n e x p e n s i v ed i s k s ，廉价冗余磁盘阵列) 概念以来，r a i d 技术不断发展，并被广 泛应用于当前的大型存储系统。随着信息量的爆炸性增长和新的多媒体应用的出 现，磁盘阵列的规模不断增大，对可靠性和可用性的需求也进一步提高，传统的 容单个磁盘故障的磁盘阵列已逐渐显示出不足，未来的大型存储系统应具备容多 个并发磁盘故障的能力，因此，十多年来，关于双容错磁盘阵列的研究从未间断 过。 本文首先简要介绍了传统的单容错磁盘阵列的原理和特点，并对现有的多种 双容错磁盘阵列构造方法进行了较详细的介绍与分析，根据其特点将双容错磁盘 阵列构造方法划分为三类：利用多擦除纠错码实现双容错；采用简单奇偶校验， 对校验条纹矩阵编码实现双容错；采用简单奇偶校验，构造校验条纹数据布局实 现双容错。 然后，在分析现有技术的基础上，本文提出一种新的、基于完全图的双容错 磁盘阵列构造方法，称为o r d p ( 最优冗余) 双容错数据布局方法。o r d p 方法 属于第三类双容错构造方法，具有冗余存储容量最优、校验计算简单、编解码方 式简单、适用性广等特点，是一种灵活的双容错数据布局方法。本文提出并证明 了o r d p 方法的相关基础理论，总结了双容错约束条件，设计并实现了构造算 法，获得了部分参数条件下的o r d p 双容错数据布局。 最后，通过理论分析和实验测试，本文从多个方面对o r d p 方法和其他双容 错方法进行了比较，分析及测试结果表明，o r d p 方法的整体性能优于其它双容 错方法。 o r d p 方法思路新颖、性能优越，是一种实用的双容错磁盘阵列构造方法， 但是算法实现方面还存在不足，实验评估也还有待完善，本文分析了存在的问题 并探讨了解决方案。 关键字： r a i d 磁盘阵列；双磁盘故障；最优冗余数据布局；完全图 t h er e s e a r c ho fd a t a p l a c e m e n ts c h e m e f o r t o l e r a t i n g d o u b l ed i s kf a i l u r e si n r a i da r c h i t e c t u r e s a b s t r a c t s i n c et h ec o n c e p to fr a i dw a sf i r s td e f i n e di n19 8 8b yd a v i dp a t t e r s o ne t a 1 。 t h et e c h n o l o g yo fr a i dp r o g r e s s e dc o n t i n u a l l y , i th a sb e e nw i d e l ya p p l i e di ng r e a t s t o r a g es u b s y s t e m sa l r e a d y t o d a y , t h ea m o u n to fi n f o r m a t i o ni sh u g e ra n dh u g e r , s e v e r a ln e wa p p l i c a t i o n s ，s u c ha sm u l t i m e d i aa p p l i c a t i o n s ，a r ec o m ef o r t h ，d i s ka r r a y i s b i g g e rt h a nb e f o r e ，a n d h a sb e e np l a c i n gs t r o n g e rd e m a n d so nr e l i a b i l i t ya n d a v a i l a b i l i 讹n a d i t i o n a ld i s k a r t a y s w h i c h t o l e r a t i n g a s i n g l e d i s kf a i l u r ea r e i n s l l f f i c i e n t 、t h e g r e a ts t o r a g es u b s y s t e m s i nf u t u r es h o u l dt o l e r a t e m u l t i p l e s i r e u l t a n e o n sd i s kf a i l u r e s t h e r e b y , t h er e s e a r c h e si nr a i da r c h i t e c t u r e sf o rt o l e r a t i n g d o u b l ed i s kf a i l u r e sa r ea l w a y so n g o i n gf o rad e c a d e f i r s t l y , t h i st h e s i sb r i e f l yr e v i e w st h et h e o r ya n dc h a r a c t e r i s t i co f t r a d i t i o n a ld i s k a r r a y st o l e r a t i n gas i n g l ed i s kf a i l u r e ，t h e ni n t r o d u c e sa n da n a l y s e se x i s t i n gs c h e m e s f o rt o l e r a t i n gd o u b l ed i s kf a i l u r e si nr a i da r c h i t e c t u r e sr a t h e rd e t a i l e d d i s t i n g u i s h i n g t h e mi n t ot h r e ec l a s s e s ：c o d i n gw i t ht h em u l t i p l ee m s u r ec o r r e c t i n gc o d e ；u s i n g p a r i t y c o d ea n d e n c o d i n g a sm a t r i x ；u s i n gp a r i t yc o d ea n dc o n s t r u c t i n gd a t ap l a c e m e n t s e c o n d l y , t h i st h e s i sp r e s e n t san e wm e t h o dt oc o n s t r u c td i s ka r r a y sb a s e do n c o m p l e t eg r a p h ，w h i c h i sc a l l e d o r d p ( o p t i m a lr e d u n d a n c yd a t ap l a c e m e n t ) s c h e m ef o rt o l e r a t i n gd o u b l ed i s kf a i l u r e si nr a i da r c h i t e c t u r e s 0 r d pi saf l e x i b l e m e t h o d ，b e l o n g e dt ot h et h i r dc l a s s ，w h o s er e d u n d a n c yi so p f i m a l ，p a d t yc o m p u t i n gi s s i m p l e ，e n c o d e ，d e c o d ea l g o r i t h m sa r ea l s os i m p l e ，a n di t i s a p p l i c a b l et oa l l c a s e s s o m eb a s i ct h e o r e m so fo r d pa r ep r e s e n t e da n dp r o v e d ，t h er e s t r i c t i o n so fd a t a p l a c e m e n tf o rt o l e r a t i n gd o u b l ed i s kf a i l u r e si nd i s ka r r a y sa r ec o n c l u d e d ，t h e nw eg o t s e v e r a l0 r d pd a t a p l a c e m e n tu s i n go u rc o n s t r u c t i o na l g o r i t h m l a s t l y , w ec o m p a r e0 r d ps c h e m ew i t ho t h e rm e t h o d st o l e r a t i n gd o u b l ed i s k f a i l u r e s ，t h er e s u l t so ft h et h e o r e t i ca n a l y s i sa n dt h ee x p e r i m e n tt e s t ss h o wt h a tt h e p e r f o r m a n c eo f 0 r d p i sb e t t e rt h a no t h e r s o r d pi san o v e l e x c e l l e n ta n da p p l i e dm e t h o dt oc o n s t r u c td a t ap l a c e m e n tf o r t o l e r a t i n gd o u b l ed i s kf a i l u r e si nr a i da r c h i t e c t u r e s b u tt h ec o n s t r u c t i o na l g o r i t h mi s s t i l l i n s u f f i c i e n t ，t h et e s t sa r en o tp e r f e c t ，t o o i nt h i st h e s i s ，w ed i s c u s sa b o u tt h e s h o r t c o m i n g sa n d t h es o l u t i o n s k e y w o r d s r a i d ；d i s ka r r a y s ；d o u b l ed i s k f a i l u r e s ；o r d p ；c o m p l e t eg r a p h i i 翌查堡! 型! 垫塑查星查鲨塑! ! 塑 1 1r a i d 技术起源 第一章绪论 计算机技术的基本工作原理是存储程序控制原理，计算机系统结构是以存储 器为中心的结构。存储器是计算机的记忆设备，输入到计算机中的程序、数据以 及计算机的运算结果都必须存放在存储器中，计算机运行时，由c p u 从存储器中 取出程序指令和待处理的数据，处理完后，再将结果送回存储器中。因此，存储 器是计算机系统最重要的组成部分。 计算机的存储器分为两大类：1 内部存储器，简称内存或主存；2 外部存 储器，简称外存。内存一般都是半导体存储器，按照工作方式可分为随机读写存 储器( r a m ) 和只读存储器( r o m ) ；外存多以磁性材料或光学材料制造，可分为 磁介质存储器和光介质存储器。内存的速度快，通过系统总线直接同c p u 打交道， 但是作为主存的动态存储器( d r a m ) 不能永久保存信息，一旦停电，所存储的信 息立即消失；而只读存储器虽然断电后能保存信息，又只能读出不能写入。外部 存储器有硬盘、软盘、光盘、磁带等等，外存为计算机提供了大容量、永久性的 存储功能。其中，硬盘是最重要的外部存储设备，与其它固定存储设备相比具有 廉价、容量大、速度快、使用方便等特点。因此，硬盘是计算机系统的数据存储 中心，应用程序和数据绝大多数都存储在硬盘上，是计算机用户数据存储不可或 缺的设备。 早在2 0 世纪8 0 年代，由于当时磁存储技术的限制，单磁盘设备容量小，而 硬件厂商所生产的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 s ，昂贵的大容量单磁 盘) 价格高昂。同时，c p u 和内存的性能飞速增长，i o 性能却因为磁盘设备的 机械局限性增长得十分缓慢，成为整个计算机系统的瓶颈。为了克服磁盘设备自 身的不足，d a v i dp a t t e r s o n 等人在1 9 8 8 年加利福尼亚州伯克利大学的一次会 议上首次提出了r a i d ( r e d u n d a n ta r r a y so fi n e x p e n s i v ed i s k s ，廉价冗余磁 盘阵列) 概念，避开了无法解决的技术局限性，提出用组合多个小的廉价磁盘的 方法获得大容量的虚拟存储系统，同时利用数据信息存储条纹化的技术，将用户 数据分布到多个磁盘上，通过并行读写操作获得高的i o 性能。 经过更细致的分析，科学家们发现，多个磁盘组合成的磁盘阵列系统，可靠 性比单个磁盘低，因此又提出了用额外磁盘存储冗余信息以提高可靠性的思路， 当个磁盘发生故障时，利用冗余信息重新生成丢失信息，保护了数据的完整性 与可用性。 苎二里堕丝 1 2 磁盘技术简介 磁盘设备是目前最主要的数据存储物理介质，它通常由一块或多块涂有磁介 质的盘片、若干个带有磁读写头的机械臂构成，数据存放在盘片上，所有盘片 都围绕一个同心轴旋转，通过固定在可移动读写头上的传感器进行读写，数据传 输可以在多个盘片上并行进行。磁盘设备通常利用c h s ( 柱面数、磁头数和扇区 数) 来进行描述，在盘片的表面是由, j , f o 大的多个同心圆，其中最小的读写单位 是圆上的一段弧，称为扇区，为5 1 2 字节。每个圆称为一个磁道，盘片组的纵向 扇区集合则称为柱面。 当前市面上的主流磁盘设备根据数据接口技术的不同，可分为i d e 、s c s i 、 f c 几类，目前又出现了串行a t a 接口的高速磁盘，为未来发展高频率、大容量 和高带宽的磁盘指明了方向。本文所提到的磁盘如无特殊说明均是指i d e 接口磁 盘。 影响磁盘性能的指标主要有主轴转速、单碟容量、平均寻道时间、平均旋转 延迟、平均访问时间、道一道间寻道时间、数据传输率、平均无故障时间等。其 含义如下： 1 主轴转速：以每分钟硬盘盘片的旋转圈数来表示，单位为r p m ，转速越高， 硬盘性能相对越好，因为较高的转速能缩短硬盘的平均等待时间并提高硬盘 的内部传输速度。 2 单碟容量：硬盘由一个或几个盘片组成，单碟容量是指包括正反两面在内 的每个盘片的总容量。单碟容量的提高意味磁介质密度的提高，目前最大单 碟容量已达6 0 g 。 3 平均寻道时间( a v e r a g es e e kt i m e ) ，指硬盘磁头移动到数据所在磁道时 所用的时间，单位为毫秒( m s ) ，与磁介质密度和磁头机械臂技术有关。 4 平均旋转延迟( a v e r a g el a t e n c yt i m e ) ，指磁头移动到数据所在的磁道后， 等待指定数据扇区转动到磁头下方的时间，单位为毫秒( m s ) 。与硬盘主轴转 速相关。一般来说，5 4 0 0 r p m 硬盘的平均旋转延迟时间为5 6 m s ，而7 2 0 0 r p m 硬盘的平均旋转延迟对阈为4 2 m s 。 5 平均访问时间( a v e r a g ea c c e s st i m e ) ，指磁头从起始位置到达目标磁道 位置，并且从目标磁道上找到指定的数据扇区所需的时间，即：平均访问时 间3 平均寻道时间十平均旋转延迟，单位为毫秒( m s ) 。平均访问时间体现了硬 盘读写速度。 6 数据传输率( d a t at r a n s f e rr a t e ) ，可分为外部传输率( e x t e r n a l t r a n s f e rr a t e ) 和内部传输率( i n t e r n a l t r a n s f e rr a t e ) 。外部传输率是指 计算机通过i d e 接口从硬盘的缓存中将数据读出交给相应的控制器的速度， 翌查堡坠! 里垫塑塑旦变鎏! ! ! ! 塑 内部传输率是指硬盘将数据从盘片上读出交给硬盘上的缓冲存储器的速度， 前者要比后者快得多，两者之间利用缓冲存储器作为桥梁以缓解速度f 内差距。 外部数据传输率也称为突发数据传输率( b u r s t d a t at r a n s f e rr a t e ) ，内部 数据传输率也称硬盘的持续传输率( s u s t a i n e d t r a n s f e rr a t e ) ，一般取决于 硬盘的转速和盘片线性密度。内部数据传输率的高低是评价硬盘整体性能的 决定性因素，有效提高硬盘的内部传输率才能对磁盘系统的性能有最直接、 最明显的提升。 7 m t b f ( m e a nt i m eb e t w e e nf a i l u r e s ，平均故障时间间隔) ，指硬盘从丌始 运行到出现故障的时间间隔，单位为小时。一般硬盘的m t b f 都在3 0 ，0 0 0 或 5 0 0 0 0 小时之间。 如同发生在微处理器领域的变化一样，在过去的若干年中，硬盘的技术也发 生了翻天覆地的变化，这些变化相应地表现在硬盘的容量、速度和价格上。 1 9 5 6 年i b m 工程小组研制出世界上第一台磁盘存储系统i b m3 5 0r a m a c ( r a n d o ma c c e s sm e t h o do fa c c o u n ti n ga n dc o n t r 0 1 ) ，磁盘容量仪有5 m b ， 而现在的主流硬盘动辄i o o g b 左右。目前容量最大的硬盘是原昆腾旗下的s n a p a p p l i a n c e 公司发布的s n a p s e r v e r4 4 0 0 硬盘，容量高达7 2 0 g b 。i b m3 5 0r a m a c 使用了5 0 个直径为2 4 英寸的磁盘盘片，盘片上每平方英寸的数据密度只有 2 0 0 0 b i t ，而现在的主流磁盘大小只有3 5 英寸，最小的甚至仅有一英寸。而且 由于磁介质存储技术在存储密度方面的突破，最高单碟容量可达8 0 g b ，最高数 据密度居然高达每平方英寸1 6 9 g b i t 。同时，磁介质存储技术的提高使磁盘生产 成本降低，价格也越来越便宜。i b m3 5 0r a m a c 的数据传输能力只有1 1 k b s ， 而现在主流硬盘的最大数据传输率约为1 0 0 m b s 。目前最快的磁盘是希捷发布的 c h e e t a hx 1 5 系列硬盘，其转速高达1 5 ，0 0 0 r p m ，内部数据传输率达4 8 m b s ，外 部数据传输率为1 6 0 l l b 2 0 0 m b s 。 硬盘在容量方面虽然取得了长足的进步，但是单从速度衡量，当今主流存储 设备的发展并不能让人满意，主流硬盘外部数据传输率的提升每年在1 0 m b s 以 内，远远低于容量的提升幅度。串行a t a 接口技术虽然突破了当前i d e 接口技术 在寻址能力和传输带宽方面的技术极限，具有未来硬盘所必需的高频率、大容量 和高带宽的特点，但是存储介质和磁头技术才是束缚硬盘发展的关键所在，却并 没有突破性的进展。 1 3 处理器和存储系统的性能差距 近四十年来，摩尔定律一直主导着半导体技术的发展，芯片上的晶体管数量 每1 8 个月就翻一番，也就是说计算机的性能每1 8 个月就能翻一番。因此c p u 的 釜二皇堕丝一 速度越来越快，内存的容量越来越大，进而也要求二级存储系统具有更大的容量， 更好的性能。 纵观硬盘发展现状，容量的发展令人满意，但是z o 性能发展缓慢。a m d a h 7 定律曾经预言，如果二级存储系统的性能得不到相应的提高，微处理器的巨大发 展对整个计算机系统的性能只能带来边缘性的改善。目前，最快的处理器速度已 经达到3 0 h z ，内存的数掘传输率高达若干o b s ，数据存取时间为纳秒级，而磁 盘存储系统的内部数据传输率却仅有数十、至多上百m b s ，外部数据传输率多 为1 0 0 m b s ，最大也只有2 0 0 m b s ，数据存取时间为毫秒级，i o 性能的增长远 远落后于c p u 和内存性能的增长。 出现这种现象的原因在于集成电路技术的快速发展使c p u 的速度有显著提 高，而磁盘设备受限于机械部件技术瓶颈，性能的改进要缓慢得多。例如减少磁 盘访问时问，需要改进驱动读写头移动的机械臂，而机械臂性能的改善每年仅有 不到1 0 ；提高磁盘传输速率，除了要提高磁介质密度还需要加快磁盘的转速， 改进感应磁头的读写性能，虽然磁存储介质密度有了非常大的提高，但是整体性 能的提高仍然远远低于微处理器发展速度。因此c p u 和内存的性能与i o 性能的 差距越来越大，i o 性能成为影响整个系统性能的瓶颈，而且这种情况还在不断 恶化。 利用r a i d 技术，将多个磁盘设备组合成一整个大容量逻辑卷，通过并, 7 亍t j l 制提高整体i o 性能，从某种程度上填补了处理器与i o 之间的性能鸿沟。 1 4r a i d 技术特点 r a i d 概念最先是由d a v i dp a t t e r s o n 等人在论文“ac a s ef o rr e d u n d a n t a r r a y so fi n e x p e n s i v ed i s k s ( r a i d ) ”中提出的，其核心思想是用多个廉价小 磁盘和条纹化的数据存储来取代将所有数据存储于单个磁盘的传统方法，通过多 个磁盘的并行读写提高存储系统的整体i o 性能。 然而，由于文件数据是均匀散布在各个磁盘上，如果磁盘阵列中有一个磁盘 发生故障，就会发生数据丢失现象。形象地来说就好像文件中每隔一定长度，内 容就缺少一部分，从而导致整个文件千疮百孔。因此，一个磁盘故障，将使得 r a i d 存储阵列系统中所有磁盘的数据均不可用。但是，由多个磁盘构成的阵列 可靠性本来就低于单个磁盘，如果将n 个平均无故障时间为m t b f 的独立磁盘组 合在起，其总的平均无故障时间将减少为m t b f n 。当n 值增大时，磁盘阵列 的可靠性下降得非常之快。因此，用额外的磁盘存储冗余信息以防止数据丢失成 为r a i d 技术的又一重要思想。如果一个磁盘发生故障，就利用磁盘阵列中冗余 磁盘及其他磁盘中含有的相关信息重新生成丢失数据。丢失数据的重构操作可以 翌查堡! 型里鏊塑鱼星查生塑型塞 在后台完成，对终端用户来说是透明的，即使终端用户要求访问尚未恢复的数据， 也依然口j 以通过临时重构要求访问的数据来实现。由于所有信息都可用，磁盘故 障将不会对终端用户产生影响，这样就保证了数据的持续可用性。 多个廉价磁盘的组合提供了大容量虚拟设备，条纹化数据存储提高了i o 性 能，冗余磁盘的信息保证了数据可靠性和可用性，r a i d 技术以其高可用、高可 靠的特点倍受瞩目。在经过了十多年不断的研究与发展之后，r a i d 技术同趋成 熟，如今各大硬盘厂商的生产线上都已经有了应用r a i d 技术的大型存储系统。 1 5 更高可靠性的要求 当前的社会是信息的时代，信息无所不在，因特网、数据仓库、e m a i l 、以 及不断涌现的各种新的应用，如音频、视频等多媒体应用，导致信息爆炸性地增 长。现在，一般人认为5 0 0 g b 的存储量已经相当大了，但到了2 0 0 5 年，这样的 存储量将是一般家庭为电影、音乐，照片和其他娱乐需求准备的最小值，硬盘将 不仅是p c 的一个重要部件，并且将成为一种家用电器的名称，成为人们生活密 切相关的一部分。同时，企业的发展也推动信息量的迅速增长，早在1 9 8 7 年 g o l d s t e i e 就依据从中大型商业组织收集的资料，预言1 9 9 5 年平均的企业级数 据存储量将达到t b 级。事实也证实了这一点，当前主流硬件厂商提供的商业大 容量存储器都是若干t b 的海量存储器。而根据i d c 的预计，2 0 0 3 年全球服务器 端存储市场的规模将达到2 0 0 万t b 。信息是企业生存和发展的关键，美国德克 萨斯州大学的调查显示：”只有6 的公司可以在数据丢失后生存下来，4 3 的 公司会彻底关门，5 1 的公司会在两年之内消失。”因此，信息已成为关乎一个 企业生死存亡的最重要资产，越来越多的企业意识到存储信息的重要性，开始借 助于高可靠性的存储系统来完善保存其数据。 存储系统的可靠性可以用平均数据丢失时间m t t d l 来衡量。p a t t e r s o n 等人 总结出通用的r a i d5 磁盘阵列的m t t d l 公式如下： 仍d e ：丝! ： n ( g 】) m t t r 其中m t t f ( m e a n t i m e t o f a i l u r e ) 表示单个磁盘的平均故障时间，m t t r ( m e a n t i m e t o r e p a i r ) 表示单个磁盘的平均修复时间，n 为磁盘阵列中的磁盘 数目，g 为校验组大小。 十年前，w a l tb u r k h a r d 等人曾在一篇论文中做过一个有趣的估算，他们按 照g o l d s t e i n 的预测推算出到2 0 0 0 年，一般的商业组织可能会有多达i o t b 的数 据信息。同时也对磁盘的发展进行了预测，认为到2 0 0 0 年主流磁盘容量将达到 2 0 0 n b ，因此个普通的企业级存储系统将包括5 0 ，0 0 0 块磁盘。如果使用容单个 第一章绪论 磁盘错的( i o + p ) r a i d5 ( 1 0 个数据盘+ 1 个冗余校验盘) 技术，假定单盘m t b f 为 5 0 0 ，0 0 0 小时，修复率为每小时1 1 ，那么整个磁盘系统的平均数据丢失时问 ( m t t d l ) 将变得和单个成员磁盘的平均无故障时问差不多。如果有1 0 0 0 个这样 的存储系统，那么几乎每5 0 0 小时，约2 1 天，就有其中的一个会丢失数据。因 此，随着磁盘阵列的大型化，对当时来讲性能十分优秀的r a i d5 技术将不再能 满足需求，将会要求提供更高可靠性的磁盘阵列技术。 从今天来看，这一估算稍微高估了普通企业级数据存储量，远远低估了磁盘 技术在容量上的发展。事实上，到2 0 0 0 年4 0 g b 的硬盘已相当普遍，而当时i b m 公司的d e s k s t a r7 5 g x p 更是已经拥有高达7 5 g b 的容量，目前主流硬盘的容量已 经高达1 0 0 2 0 0 g b 。另一方面，当前的商用存储系统，一般只提供几t b 的容量， 一些高端产品才具备扩充到1 0 几t b 容量的能力。商用存储系统的磁盘数目绝对 不可能达到数千个之多，因此r a i d5 技术仍然在存储系统的舞台上发挥着巨大 的作用，尤其是在同时要求高性能和低冗余的领域中，仍然是一种最佳的折衷方 案。但是b u r k h a r d 等人对未来社会将要求更高可靠性存储系统的看法却是十分 准确的。应该看到，随着新的数据类型如音频、视频数据的出现，随着多媒体实 时应用技术的发展，对存储系统的容量、可靠性确确实实提出了更高的要求，这 是不同于普通应用的、对存储性能有特殊要求的新型应用领域。同时，考虑到磁 盘的物理特性，一般构成磁盘阵列的磁盘均是同时购进的，其使用寿命差不多， 很容易同时发生多个磁盘故障，如果在一个故障磁盘尚未修复完成的时间间隔 内，就出现新的磁盘故障，将导致数据磁盘的丢失。此外，不可预知的系统崩溃、 无故障磁盘的潜在位错误都有可能导致故障磁盘的修复工作不能顺利完成，从而 提高数据丢失的可能性。 因此，传统的可容单个磁盘错的r a i d 技术已经越来越显现出其不足，将来 的发展趋势必然要求存储系统具有更高的可靠性，能够容许两个或者多个并发的 磁盘故障。近十年来，不少科学家在这一领域进行了研究，双容错的磁盘阵列技 术不仅成为了重要发展方向，并且已经逐渐登上高端存储系统的应用舞台。 6 双容错r a i d 数据布局方法的研究 第二章现有磁盘阵列技术简介 传统r a i d 体系结构的三个主要构建要素为； 1 数据条纹化数据信息被分为若干个等大小的块，同时每个磁盘的存储空间也 被划分为相同等大小的块，数据信息交叉地分别存储到r a i d 阵列中的多个磁 龠上，每个块称为一个条纹单元，r a i d 阵列中所有磁盘上相互关联的块构成 一个完整条纹。数据的逻辑存储对应着所有磁盘设备的物理存储，因此能够 创建大的逻辑卷，并进而能够通过多个磁盘的并行操作，提高i 0 性能。 2 镜像数据信息同时存储于两块磁盘，即数据有两份一模一样的完整备份。 3 奇偶校验数据信息写入多个磁盘，并使用一至多块磁盘存储校验信息。如果 个磁盘发生故障，校验信息可与未发生故障磁盘上的数据信息相结合，重 新生成丢失信息。 在磁盘阵列体系结构中，交叉数据的粒度，即条纹单元大小，以及冗余信息 的计算方法和其在磁盘阵列中的散布方式，是划分r a i d 存储系统的两个主要特 征。 交叉数据的粒度可分为细粒度和粗粒度。细粒度方式下，条纹单元的尺寸很 小，任何i 0 请求都将访问阵列中的所有磁盘，虽然可以获得很高的数据传输率， 但是同一时刻只能为一个i o 请求服务。而采用粗粒度方式的磁盘阵列，条纹单 元较大，小的i o 请求只需访问一小部分磁盘，大的i o 请求才访问所有磁盘， 因此既能为多个小请求提供并行服务，同时也能为大请求提供高的传输速率。 磁盘阵列中的冗余校验信息一般采用简单的奇偶校验计算得到，也有少数使 用海明码或者r e e d s o l o m o n 编码。冗余校验信息在磁盘阵列中的散布方式主要 可分为两大类，一类是集中存储于一个或若干个校验磁盘，另一类是均匀散布于 所有磁盘。冗余校验信息的均匀散布可避免校验磁盘在小数据写i o 操作时的瓶 颈问题，以及其他一些负载均衡问题。 在实际应用中，数据条纹大小和冗余方案应综合考虑可靠性、性能和价格三 个因素来决定。 2 1 单容错磁盘阵列技术 2 ，1 1 单容错r a i d 体系结构简介 传统的单容错r a l d 体系结构可分为6 类，其主要特征如下： 第一二章现有碰盘阵列技术简介 。r a l d0 条纹化 描述：条纹化的磁盘阵列，不具备容错能力，不是真正意义上的r a i d 。 实现：r a i d0 至少需要用2 块磁盘实现。 特征和优势：r a i d0 实现了一种条纹化的磁盘阵列，数据分块存放在不同 的磁盘设备中，每一数据块称为一个条纹单元，可将多个磁盘创建为一个大 的逻辑卷。在r a i d0 中，由于i o 负载分布到多个通道和设备上，i o 性能 得到很大提高。如果数据的条纹化存取由多个控制器来实现，并且每个控制 器只管理一个硬盘，可获得最好盼陛能。r a i d0 不需要校验计算，易于设计 和实现。 缺点：由于没有容错能力，r a i d0 并不是真正意义上的冗余磁盘阵列，只要 有一个磁盘发生故障，阵列中所有数据都会丢失。因此绝不能用于对数据可 靠性要求较高的任务环境中。( 有一些实际应用采用将控制信息存储于r a i d 1 或5 文件系统，而多媒体数据存储于r a i do 磁盘阵列，并用磁带或光箍进 行备份，在利用r a i d0 高i 。0 性能的同时，相应地提高可靠性。) 应用领域：视频制作和编辑、图像编辑、前期排版，以及任何要求高带宽的 应用领域。 r aj d1 镜像 描述：将相同的数据信息同时存储在两块磁盘上，互为备份。为了获得最佳 性能，磁盘控制器应能在成对的镜像磁盘上进行独立的读操作，以及并发的 两个写操作。 实现：r a i d1 至少需要2 块磁盘设备实现。 特点优势：每对镜像磁盘可支持一个写操作或两个读操作，与单磁盘相比 读传输率是其两倍，写传输率与其相同。1 0 0 的数据冗余意味着在磁盘故障 时不需要进行重构，只需用备份磁盘代替故障磁盘，不会引起故障期间的性 能降级。r a i d1 能承受多个并发的磁盘故障，但如果一个镜像磁盘对中的两 个磁盘同时发生故障，则会造成数据丢失。镜像对中的磁盘均包含所有信息， 因此不需要特殊的r a i d 硬件软件的支持。 缺点：磁盘冗余量是所有r a i d 级别中最高的( 1 0 0 ) 。 应用领域：账目统计、计算报告、财政分析，以及任何要求极高数据可用性 的领域 r a i d 2 位交叉海明码9 0 0 校验 8 翌查丝坠堡墼塑塑旦查鲨塑塑塞一 描述：r a i d2 使用位交叉技术，利用内存阵列所采用的海明码e c c ( e r r o r c o r r e c t i o nc o d e ，错误修正码) 计算校验信息。校验数据存放于多个校验 盘，校验盘数目与总的磁盘数的对数成比例。 缺点：冗余率高。数据读写性能很差，数据读涉及所有磁盘，不支持并行的 多个i 0 请求；数据写需要写所有数据盘和多个校验盘。 应用领域：无。 r a l d3 位或字节交叉，奇偶校验 描述：r a i d3 使用位或字节交叉技术，采用奇偶校验。校验信息存储于单独 的校验磁盘中，写数据时更新校验信息，读数据时检验校验信息，任意t o 操作需由所有磁盘参与完成。 实现：至少需要三块磁盘来实现。 特点优势：可用存储空间为阵列磁盘数减1 ，读写性能好，具备数据保护能 力，可容许一个磁盘故障，并能重构丢失数据，比r a i d4 ，5 易于实现。 缺点：数据读需要读所有数据磁盘，数据写需要涉及所有数据盘和校验盘， 同一时间只能响应一个i o 请求，因此不能同时处理多个并发i 0 操作。小 数据i 0 操作的性能羞，在降级状态下性能会受影响，只适用于单用户环境。 应用领域：适用于对带宽要求较高，但不要求高i o 率的应用领域，特别适 用于大数据传输的单用户、单任务环境。 - r a i d4 块交叉奇偶校验 描述：数据信息以任意大小分块存储在不同磁盘上，条纹化方式类似于r a i d 0 。采用奇偶校验，校验信息存储于单独的校验磁盘。如果数据磁盘发生故 障，可利用校验信息在空闲磁盘上重构数据信息；如果校验磁盘故障，则在 空闲磁盘上重新计算校验信息。 特点优势：可用空间为阵列磁盘数减l ，容许单磁盘故障，故障情况下，可 从剩余磁盘重新生成丢失数据。小数据读时，可支持并行的i 0 操作。 缺点：校验磁盘周定，小数据写时，需要频繁访问校验磁盘以更新校验单元， 校验磁盘将成为整个系统性能的瓶颈。 应用领域：可用于单块磁盘性能大大高于阵列中其他磁盘性能的环境中( 高 性能磁盘作为校验盘) 。有软件实现，但几乎没有应用。 r a i d5 块交叉的校验散布 描述：采用块交叉技术，奇偶校验计算。与r a i d4 类似，唯一的区别是校 验信息均匀散布于所有磁盘上，通常使用左对称校验散布。 第二章现有磁盘阵列技术简介 实现：r a i d5 需要至少3 块磁盘实现。 特征优势：可用空间为阵列磁盘数减1 ，容许单磁盘故障，可重构丢失数据。 具有最好的数据读和大数据写性能，特别适用于以读操作为主的应用环境。 缺点：小数据写时，由于要进行读一修改一写操作以更新校验单元，性能比单 磁盘差。 应用领域：对数据可用性要求高的领域，有不同大小i o 传输的多任务环境， 要求好的读性能、中等写性能的领域。如文件和应用程序服务器、数据库服 务器、w w w ， e - m a il 和n e w 服务器，以及i n t r a n e t 服务器。r a i d5 是最通 用的r a i d 级别。 传统的6 级单容错r a i d 体系结构在性能、可靠性及价格上的比较总结如下 级别组织方式数据传输率i o 请求速率数据可靠性价格 块条纹化，无冗很高很高著一一低下低 r aj d0余单个磁盘设 备 镜像，无条纹化数据读传输i 0 读的速率很高，可容许高( 必须 率比单个磁为单个磁盘的特定条件f使用双倍 r a l d1盘高，但不2 倍，i 0 写速的多个磁盘的磁赢) 能均衡负载率比单个磁盘故障 稍差 按位条纹化，如果纠错码约为单个磁盘很高，可容许高( 需要 e c c 校验的计算由硬的2 倍特定条件下多个磁 r a d2件完成。数的多个磁盘盘) ，但 据传输率高故障比镜像方 式略好 按位或字节条是所列各级利用并行磁盘好，可容许单多一个校 r a i d3 纹化，奇偶校验r a i d 中最高访问，比单个个磁盘故障验磁盘 的磁盘速率高 与r a i d3 类似，数据读传输i o 读速率比好可容许单多一个校 但按块条纹化率比单个磁单个磁盘高，个磁盘故障验磁盘 r a f d4盘高，数据i 0 写速率比 写传输率则单个磁盘低得 低得多多 与r a i d4 类似，数据读传输i 0 读速率比 好，可容许单多一个校 校验条纹均匀率比单个磁 单个磁盘高，个磁盘故障验磁盘 r a l d5散布于所有磁 盘高，写传i 0 写速率比 盘输率比单个 单个磁盘低 磁盘低 表2 1 各级别单容错r a i d 比较 2 0 0 2 年的一份统计资料表明，目前广泛使用的r a i d 级别除了r a i do ( 条纹 化) 、r a i di ( 镜像) 、r a i d3 ( 字节条纹化并有特定校验盘) 、r a i d5 ( 条纹 1 0 双容错r a i d 数据布局方法的研究 化并散布校验信息) 之外，还有r a i d1 0 ( 镜像条纹化) 和r a i d ( 0 + 1 ) ( 条纹化 镜像) 。 r a i d1 0 和r a i d ( 0 + 1 ) 是硬件厂商结合r a i d0 、l 所提出的，是传统r a i d 体系结构的扩展。 r a i d1 0 镜像条纹化 描述：由多个r a i d1 镜像磁盘对构成，并在这些镜像设备上进行条纹化的 数据存储，创建最终的大容量虚拟设备。 优点：具有非常高的可靠性，可以承受多个磁盘同时发生故障的情况，但前 提是同一镜像对中的两个磁盘至少有一个正常工作。能够在保证可靠性的基 础上实现最高性能的i o 操作，能够将多个磁盘组合为一个大的虚拟设备。 缺点：由于总是写双份数据，写性能次于单个磁盘写。冗余量大，每个镜像 对需要一个额外磁盘，实际数据存储容量只有总容量的一半。 应用领域：对数据可用性要求非常高的领域、对整体性能要求很高的领域。 r a i d0 + 1 条纹化镜像 描述：创建顺序与r a i d1 0 恰好相反，磁盘设备首先进行条纹化，然后为这 些设备建立镜像磁盘。通常用两个或两个以上的磁盘进行条纹化数据存储， 创建为个大的虚拟设备，然后再用同等数目的、也采用条纹化存储技术的 磁盘设备创建其镜像。 优点：具有高i o 性能，能够创建大的逻辑卷。 缺点：可靠性不如r a i dl 和r a i d1 0 。如果一个盘发生故障，即降级为r a i d o 结构。而由多个盘构成的r a i d 0 结构，发生磁盘故障的可能性会增大。需 要两倍的存储设备，可利用的数据存储容量只有实际物理磁盘容量的一半。 2 1 2 单容错r a i d 校验编码方法 在单容错r a i d 结构中，主要使用了两种计算冗余校验信息的方法：r a i d2 的海明码e c c 校验和r a i d3 、4 、5 的奇偶校验。 利用海明码计算校验信息需要多个校验磁盘。例如数据磁盘数为4 的阵列系 统，需要3 个校验盘，数据磁盘数为8 的阵列系统需4 个校验盘。校验计算 复杂，除非用硬件实现，否则写性能将低下得令人无法接受，此外，冗余磁盘数 目与阵列中数据磁盘数的对数成比例，因此在小的磁盘阵列中，冗余率很高，随 着阵列数据磁盘数的增多，才会得到一定改善。兼顾好的性能和低的冗余率，奇 第二章现有磁盘阵列技术简介 偶校验计算以其简单的特性和有效的纠错能力广泛地应用于r a i d 存储系统之 中。 下面先引入有关校验计算的几个定义： 条纹单元：采用条纹化技术存储数据，磁盘空间被划分为若干等大小的小块， 每一个称为一个条纹单元。 数据单元：存储用户数据的条纹单元。 校验单元：存储校验数据的条纹单元。 校验组：若干个数据单元以及由这些数据单元通过校验计算得到的一个或若 干个校验单元所组成的集合，称为校验组。传统r a i d 结构中，r a i d3 、4 、5 的 校验组包含多个数据单元和一个校验单元，r a i d2 的校验组包含多个数据单元 和多个校验单元。校验组是基于校验计算角度提出的概念。 校验条纹：能够实现某种容错能力的若干个数据单元和一个或多个校验单元 的集合。在传统r a i d 容单磁盘错的结构中，校验条纹与校验组是一致的；丽在 可容多个并发错的磁盘阵列中，校验条纹根据编码方式的不同，有可能包含多个 校验组。校验条纹是基于容错角度提出的概念。 技验组o23 5 1 0 6 1 6 7 1 2 8 1 3 1 8 4 9 1 4 1 9 校验单元、数据单元 图2 1 校验计算相关定义示意图 以r a i d3 为例，它所采用的奇偶校验就是从磁盘阵列中的每个数据盘的相 应位置各取一个数据单元进行异或计算，所得结果作为校验数据，存放到校验磁 盘的一个校验单元中，这些单元共同构成一个校验组。r a i d4 和r a i d5 与之类 似。采用奇偶校验的r a i d 结构校验计算简单，不会占用c p u 太多的资源，同时 根据