（计算机系统结构专业论文）nlov存储系统的高可靠性研究.pdf

中文摘要 中文摘要 在信息化时代，对海量数据的存储解决方案成为一个非常紧迫的研究领域。 据专家预测，全球每年的数据存储量以8 0 的速度递增，对于一些典型的数据 应用领域，每隔大约9 0 天左右，数据量就会增加一倍，如何存储海量数据已经 成为一项重要的研究课题。基于网络的虚拟存储系统( n l o v ) 是南开大学并行与 分布式软件技术研究室顺应当前存储系统发展方向而开发的虚拟存储系统，本 文作者是核心开发成员之一，该系统采用基于广域网的架构，支持动态加入存 储节点，系统存储容量在理论上上可以无限扩展。对于存储容量庞大的存储系 统，保证其系统可靠性成为系统设计的最重要的目标之一。 主流的提高存储系统的可靠性的技术主要包括两种：利用副本技术提高存储 系统的可靠性和利用编码技术提高存储系统的可靠性。利用副本技术提高存储 系统可靠性的典型例子包括c o d a 、o c e a n s t o r e 、i n t e r m e z z o 和l u s t r e 等。利用编 码技术提高存储系统可靠性的典型例子包括r a i d 级别2 、r a i d 级别3 、r a i d 级别4 、r a i d 级别5 和r a i d 级别6 等。但由于n l o v 存储系统具有本身独特 的性质，以上这些技术都不太适合在n l o v 存储系统系统上采用。 本文充分分析n l o v 存储系统的特点提出了一种副本散布算法，利用这种 副本技术可以将数据副本按照存储节点的权重均匀的散布到各个存储节点，并 能使n l o v 存储系统在采用副本技术的情况下数据均匀散布和系统规模发生改 变时的数据迁移量接近最优。经过全面的实验表明在各种情况下该算法的散布 性能、稳定性能都很好。 关键词：存储系统；n l o v ；可靠性；副本技术；副本散布算法 a b s t r a c t n l es o l u t i o nf o rs t o r i n gm a s so fd a t ab e c o m e sap r e s s i n gr e s e a r c hf i e l da s i n f o r m a t i o n b a s e da g ec o m e s e x p e r t sp r e d i c tt h a tt h ey e a r l yd a t at ob es t o r e di s g r o w i n ga tas p e e do fe i g h t yp r e s e n t ，i ns o m et y p i c a lf i e l do fa p p l i c a t i o n ，t h ed a t aw i l l d o u b l ee v e r yn i n e t yd a y s ，a n dt h e nh o wt o s t o r es u c hm a s sd a t ab e c o m e sav e r y i m p o r t a n tr e s e a r c hf i e l d v i r t u a ls t o r a g es y s t e mb a s e do nt h ei n t e m e t n l o vi sa s t o r a g es y s t e mw h i c ha d a p t sat r e n do ft h ed e v e l o p i n gd i r e c t i o no fc u r r e n ts t o r a g e s y s t e m ，i ti sd e v e l o p e db yp a r a l l e la n dd i s t r i b u t e ds o f t w a r et e c h n o l o g yl a bo f n a n k a iu n i v e r s i t y , t h ea u t h o ro ft h i st h e s i si so n eo ft h ec o r ed e s i g n e r so ft h es y s t e m t i l i ss y s t e mu s e sw a n - b a s e ds t r u c t u r e i ts u p p o r t sd y n a m i c a l l ya d d i n ga n dd e l e t i n g s t o r a g en o d e ，a n dt h e o r e t i c a l l yi ts u p p o r t si n f i n i t ee x p a n s i o n a sas t o r a g es y s t e m w h i c hi sd e s i g n e dt os t o r em a s so fd a t ai sm e n t i o n e d ，h o wt og u a r a n t e ei t sr e l i a b i l i t y b e c o m e sav e r yi m p o r t a n tg o a l c u r r e n t l y , t h ep r e v a i l i n gt e c h n o l o g yf o rg u a r a n t e e i n gt h er e l i a b i l i t yo fs t o r a g e s y s t e mi n c l u d e st w ow a y s t h e ya r eu s i n gr e p l i c at e c h n o l o g yt oi m p r o v et h er e l i a b i l i t y o fs t o r a g es y s t e ma n du s i n ge n c o d i n gt e c h n o l o g yt oi m p r o v et h er e l i a b i l i t yo fs t o r a g e s y s t e m c o bo c e a n s t o r e ，i n t e r m e z z oa n d l u s t r ea r es o m eo ft h et y p i c a li n s t a n c e so f u s i n gr e p l i c at e c h n o l o g yt oi m p r o v 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 i l er a i d 2 ， r a i d 3 ，r a i d 4 ，r a i d 5a n dr a i d 6a r es o m eo ft h et y p i c a li n s t a n c e so fu s i n g e n c o d i n gt e c h n o l o g yt oi m p r o v et h er e l i a b i l i t yo fs t o r a g es y s t e m u n f o r t u n a t e l yn o n e o f t h e s et e c h n o l o 西e si sf i tf o rn l o v , j u s tb e c a u s et h i ss t o r a g es y s t e mh a si t sp a r t i c u l a r n a t u r e b a s eo nf u l l ya n a l y z i n gt h en l o vs t o r a g es y s t e m ，t h i st h e s i sc o m e su pw i t ha r e p l i c ad i s t r i b u t i o na l g o r i t h m t i l i sa l g o r i t h mi sa b l et oe q u a b l yd i s t r i b u t ed a t ar e p l i c a s t os t o r a g en o d e si na c c o r d a n c ew i t ht h ew e i g h t so ft h es t o r a g en o d e s t i l i sa l g o r i t h mi s a b l et oa p p r o x i m a t i v e l ye q u a b l yd i s t r i b u t ea l lt h ed a t at os t o r a g en o d e si nc a s eo f u s i n g r e p l i c at e c h n o l o g ya n da l s oi ti sa b l et og u a r a n t e et h a tt h ed a t aw h i c hn e e d st ob e m i g r a t e di sa p p r o x i m a t i v e l yl e a s t c o m p r e h e n s i v ee x p e r i m e n t a t i o n ss h o wt h a tt h e a b s t r a t c t p e r f o r m a n c eo fd a t ad i s t r i b u t i o no ft h i sa l g o r i t h mi se x c e l l e n ta n dt h i sa l g o r i t h mi sa v e r ys t a b l ea l g o r i t h m k e y w o r d s ：s t o r a g es y s t e m ；n l o v ；r e l i a b i l i t y , r e p l i c at e c h n o l o g y ；r e p l i c ad i s t r i b u t i o n a l g o r i t h m i i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 靴豢筹掰 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时 间j -年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 姊荔：一 孑年、，月f 日 目录 图目录 图2 1r a i d 级别2 数据布局8 图2 2r a i d 级别3 数据布局8 图2 3r a i d 级别4 数据布局9 图2 - 4r a i d 级别5 数据布局一1 0 图2 5r a i d 级别6 数据布局1 0 图3 1n l o v 系统架构1 2 图3 2d i m 算法1 4 图3 3 存储节点软件结构l5 图3 3 元数据服务器软件结构2 0 图3 4 客户端软件结构2 6 图4 1 增加存储节点的副本映射表更新过程3 4 图4 2 删除存储节点的副本映射表更新过程3 6 图4 3 类b 树构建过程3 9 图4 4 副本映射表查表过程4 0 图4 5 数据写过程4 1 图4 - 6 增加节点的数据迁移过程4 3 图4 7 删除节点的源数据迁移过程4 4 图4 8 删除节点的副本迁移过程4 5 图4 8 失效节点的数据访问方法4 6 图4 9 失效节点的副本恢复过程4 7 图4 1 0 失效后源数据的恢复过程4 8 图5 1 一次扩展到位数据顺序写在单节点内数据副本散布图5 2 图5 - 2 一次扩展到位数据随机写单节点内副本散布图5 4 图5 3 经历多次增加删除节点后数据顺序写单节点内数据副本散布图5 5 图5 _ 4 经历多次增加删除节点后数据随机写单节点内数据副本散布图5 7 v 1 目录 表目录 表3 1d e v i c e 数据结构1 6 表3 - 2s e r v e r m a n a g e r 数据结构1 7 表3 3s e r v e r 数据结构1 7 表3 _ 4m d s l i n k e r 数据结构1 8 表3 5r e g i o n 数据结构2 1 表3 - 6n o d e 数据结构2 2 表3 7o s dm 印数据结构2 2 表3 - 8l o g i c a l v o l u m e 数据结构2 3 表3 - 9l v 数据结构2 7 表3 1 0b i o 数据结构27pair 表3 1 1 数1 v u s e r 据结构。2 7 表3 1 2a g e n t 数据结构2 8 表4 1n o d et a b l eu s c i t 数据结构3 7 表4 2z o n eb o u n du 数据结构3 8 表5 一l 一次扩展到位顺序写副本散布性能5 2 表5 - 2 一次扩展到位随机写副本散布性能5 3 表5 3 经历多次节点增加、删除后顺序写副本散布性能5 5 表5 _ 4 经历多次节点增加、删除后随机写副本散布性能5 6 v i i 第一章绪论 第一章绪论 第一节存储系统高可靠性的背景 近年来，以计算机技术为核心的信息技术得到了飞速的发展。随着技术的 进步，一些新型的应用领域相继出现，包括电子商务，视频点播，网格计算等 等。可以说，信息技术已经渗透进了人类的日常生活，人类正步入信息化的时 代，网络通信技术的发展则加速了这种趋势。在信息化时代，对海量数据的存 储解决方案成为一个非常重要的研究领域。据专家预测，全球每年的数据存储 量以8 0 的速度递增，对于一些典型的数据应用领域，每隔大约9 0 天左右，数 据量就会增加一倍，如何存储海量数据已经成为一项重要的研究课题【l j 。南开大 学并行与分布式软件技术研究室在海量数据存储技术方面有全面深入的研究， 基于网络的虚拟存储系统( n l o v ：其中n 为n e t w o r k ，表示该系统是面向广域 网的；l 为l o 西c a l ，该系统是以逻辑卷管理器为基础的；o 为o b j e c t ，表示该 系统是面向对象的存储系统；v 为v i r t u a l ，该系统属于虚拟存储系统) 是顺应当 前存储系统发展方向而开发出来的虚拟存储系统，该系统采用基于广域网的架 构，支持动态加入存储节点，系统存储容量在理论上可以无限扩展。 与此同时，用户对系统的应用要求越来越高，联机商业模式需要系统提供 3 6 5 7 2 4 小时连续服务，停机就意味着业务的停顿和商业机会的丢失。因此 可靠性成为系统的一个非常重要的指标，特别是电子商务这样的系统要求实现。 据f c i a 估计，对于银行的自动取款机，停机1 小时，损失约为1 4 5 0 0 美元，而 对于一个证券经纪公司，l 小时的停机所带来的损失超过6 0 0 万美元，因此在系 统规模爆炸性增长的情况下保证存储系统的可靠性成为系统设计的最重要的目 标之一。 在工业界，可靠性通常用平均无故障时间( m e a nt i m et of a i l u r e ，m t t 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 ) 来度量。g i b s o n 等人 通过对1 3 5 0 个硬盘进行1 8 个月的试验，证实磁盘的寿命非常接近于指数分布【2 】， 因此可认为m r r f 描述了完整的磁盘可靠性函数，这对进行可靠性研究是非常 重要的。类似的，用平均数据丢失时间( m e a nt i m et od a t al o s s ，m t t d l ) 可以 完整描述产品的可靠性。因此，产品可靠性r ( t ) 可表示为产品平均寿命的函数： 第一章绪论 r c x p ( f ) = e 肘 若t 相对于平均寿命m 较小，上式可简化为r ( f ) 1 一t m ，另一种表述方式为： p r o b ( 时n t 前发生故障) = 1 一r ( f ) t m 因此，产品的故障率( f a i l u r er a t e ) 可用平均寿命的倒数1 m 来表示。 提高存储系统【3 1 的可靠性【4 1 可以通过两种方式来实现，分别是利用副本技术 【5 】实现存储系统的高可靠性和利用编码【6 】技术实现存储系统的高可靠性。副本技 术通过完全复制数据，形成数据的副本，并且将数据副本保存在不同的位置的 存储节点上。这样，当某个节点崩溃失效时，利用副本可以向请求者提供不间 断的数据服务，并且可以利用副本数据去恢复失效节点，确保数据有多重保障。 编码技术提高存储系统可靠性的方法是以数据条纹化为基础，将若干个数据条 纹确定为一个编码单位，之后对同一个单元的数据进行编码形成冗余数据，写 入的时候连同条纹数据以及它们编码形成的冗余数据一起写入存储设备，当一 个编码单元中的某编码单位的数据丢失时，可以通过编码运算的逆运算来得到 丢失的数据，由此实现提高存储系统的可靠性。 第二节本论文的工作以及结构 本文主要利用副本技术，针对南开大学并行与分布式软件技术实验室研究 开发的基于网络的虚拟存储系统( n l o v ) 的系统特点，为该系统设计系统高可靠 性策略一副本散布算法。本文主要完成以下工作： 充分分析了n l o v 存储系统的系统架构、以及实现源码，分析了数据可靠 性在存储系统中的重要性，从理论上分析了利用副本技术实现该系统可靠性的 合理性以及优点。 在确保n l o v 存储系统的系统架构特点的基础上本文实现了副本散布算法 以及相关的副本读、写、更新算法；n l o v 系统增加存储节点时的副本数据迁 移算法；n l o v 系统节点退出时的副本数据迁移算法。从而保证n l o v 的架构 特点，实现数据迁移最优。 在实现副本散布算法的基础上实现了系统节点失效时的数据访问算法；存 储节点失效后的数据恢复算法，从而保证了n l o v 存储系统的高可用性。 2 第一章绪论 本文各章节组织如下： 第二章主要介绍当前保证存储系统可靠性的两类主流实现技术。 第三章主要介绍存储系统n l o v 的系统架构、系统的三个组成部分及其相 互之间的关系。 第四章主要介绍针对n l o v 的系统结构情况、系统特点设计的目的在于实 现该系统可靠性的副本散布算法以及各种具体情况下的处理算法。 第五章主要是对第四章的设计与实现进行实验及结果分析。 第六章主要是对本文的一个总结以及提出一些对以后进一步工作的设想。 参考文献部分列出了本文所参考的文献，以便于对该问题相关知识的进一 步查阅。 3 第二章存储系统当前的主流高可用性策略 第二章存储系统当前的主流高可用性策略 当前针对存储系统的可靠性的主流技术分为两大类，它们分别是利用副本 技术来提高可靠性和利用编码技术提高可靠性。本章将对这两种主流技术的典 型例子做概况性的介绍。 第一节用副本技术提高存储系统可靠性 提高数据高可靠性通常的方案是完全复制数据，形成数据的副本，并且将 数据副本保存在不同的位置节点上。这样，当某个节点崩溃失效时，利用副本 可以向请求者提供不问断的数据服务，这就是副本技术。 副本技术可以很大程度上提高数据的可靠性。在广域网存储系统中，节点 失效是导致数据无法访问的直接原因。节点失效可分为暂时性失效与永久性失 效两种：暂时性失效是指由于网络拥塞或软件问题而导致的，节点暂时性的无 法访问，暂时性失效通常是可恢复的，且一般恢复后不会丢失任何数据；永久 性失效是指由于存储设备硬件问题而导致的节点无法访问，永久性失效通常是 不可恢复的，存储在节点上的数据也会丢失。通过使用副本管理技术，生成数 据的副本，并保存在其他的存储子节点，当节点发生暂时性失效，用户仍可以 访问其它节点上的数据副本，保证了用户访问数据的连续性，即提高了数据的 可用性，而且即使系统中一部分节点发生永久性失效，数据副本也可以保证数 据不会轻易丢失，从而提高了数据的可靠性。 2 1 1c o d a 采用的副本技术 c o d a 是卡内基一梅隆大学( c m u ) 1 9 9 0 开发的，c o d a 7 被设计为一个可扩 展的、安全的、高可用的分布式文件系统。 缓存和复制是c o d a 实现高可用性目标的基本方法。客户缓存之所以对c o d a 的操作至关重要是因为以下两个原因。首先，进行缓存是为了达到可扩展的目 的。其次，缓存提供了较高程度的容错性，这是因为客户变得较少依赖于服务 器的可用性。不管用户是为读操作还是为写操作而打开，整个文件的拷贝被传 4 第二章存储系统当前的主流高可用性策略 送给客户，然后缓存整个这份拷贝。c o d a 允许复制文件服务器。复制以卷为单 位。拥有一份卷拷贝的服务器的集合称为该卷的卷存储组( v o l u m es t o r a g eg r o u p ) ， 或简单称为v s g 。出现故障时那些可访问的服务器称为可访问存储组( a c c e s s i b l e v o l u m es t o r a g eg r o u p ) ( a v s g ) 。c o d a 的卷存储组可以提高客户访问的可用性，但 是卷存储组的创建只能由管理员手动去创建。 2 1 2o c e a n s t o r e 采用的副本技术 o c e a n s t o r e t 8 】是一个基于对等技术构建的大规模的存储服务系统，它主要设 计用来支持千万级用户和e 级( 1 0 8 ) 的数据存储规模。 在条件允许的情况下，o c e a n s t o r e 会自动将数据复制到距用户客户端较近的 节点或用户客户端本身上，这些数据副本被称作二级副本，以区别于保存在内 部环节点上的一级副本。二级副本的价值在于它将许多远程的数据请求变为了 本地请求，减少了用户客户端的访问延迟与带宽消耗，而且降低了系统节点的 负载。当用户访问数据时，将会在用户客户端自动生成数据的二级副本。二级 副本也可在距用户客户端较近的节点生成，用户在发出对数据访问请求的同时 为访问请求赋予一个较小的订l ，若经订l 跳后仍未发现数据副本，则在访问 请求到达的最后一个节点上生成二级副本。另一方面，当二级副本不再需要时， 系统可自动将其销毁。二级副本自动组织成以内部环节点为根的多播树。一级 副本使用多播树向二级副本发布认证、心跳( h e a n b e a t s ) 和更新信息，该多播树保 持了副本间的松散一致性。 在用户发出对数据的更新请求后，更新请求会首先在内部环进行确认，若 更新成功则产生一个新版本的数据对象，然后一级副本将借助多播树向二级副 本发送更新信息。每个二级副本接收到更新信息后，会将更新信息应用到副本 上。更新信息既可以是整个数据对象的内容，也可以只是数据对象中发生变化 的部分，这就可以允许副本节点自动调节所占用的带宽。对二级副本的更新还 可以使用懒惰更新的方法，即每次只向二级副本传输数据更新的版本，并将其 上的副本无效化，而不是传输数据的更新内容，只有在二级副本被用户访问的 情况下才对其进行真正更新，这种方法可以极大地减轻用户更新请求对网络带 宽的消耗，但会增加用户查询请求获取数据的访问延时。 5 第二章存储系统当前的主流高可用性策略 2 1 3i n t e r m e z z o 采用的副本技术 i n t e r m e z z o 9 】是由美特尔科技有限公司推出的，它受c o d a 文件系统的启发， 经过重新设计后而实现的高可用的分布式文件系统。 i n t e r m e z z o 也是基于客户服务器的分布式文件系统，它在多台服务器上存 有文件系统的副本，文件数据被存放在当前机器的磁盘文件系统中。在客户端， 这个文件系统在缓存中包含当前或最近使用的文件的副本，在服务器端，这个 文件系统在文件夹集合中包含所有文件的有效副本。所有的副本文件将通过 i n t e r s y n c 对其进行同步。i n t e r s y n c 会周期性的从服务器上取得最新的改变，并 将这些改变的数据同步到客户端的文件系统中。i n t e r m e z z o 文件系统会记录服务 器上对文件所有的改变，将它们记录在内核修改日志一k m l ( k e m e l m o d i f i c a t i o n l o g ) 中。然后由i n t e r s y n c 从服务器上通过h t t p 协议取得这些日志来同步本地文 件系统。由于i n t e r m e z z o 使用了副本机制，当i n t e r m e z z o 客户无法与服务器相 连，或当服务器无法接收合法客户的更新时，i n t e r m e z z o 自动转换成无连接操作， 各自修改本地的副本文件，并记录日志。这些情况是常有发生的，例如：当服 务器或网络的部件失效时。在无连接状态下，i n t e r m e z z o 允许访问己存储的文件 并通过日志记录更新。这样提供了高可用性的数据访问。当连接恢复时， i n t e r m e z z o 会同步化存储在客户和服务器端日志文件中的变化。首先，i n t e r m e z z o 将启动更新传递来转发已存储在服务器上的变化，但对再次连接的客户无效， 然后，i n t e r m e z z o 将在服务器上重整客户端的更新。当更新传递和重整完成，文 件夹集合也被同步化了。缓存( c a c h e ) 是一致的，因为同一进程可能被迁移到不同 的节点上运行。 2 1 4l u s t r e ! 加l 采用的副本技术 l u s t r e 文件系统是c l u s t e rf i l es y s t e m s 公司开发的一个高性能，高可用，可 扩展的，面向下一代存储的分布式文件系统。l u s t r e 主要由元数据服务器 m d s ( m e t a d a t as e r v e r ) ，分布式对象存储目标o s t ( d i s t r i b u t e do b j e c ts t o r a g e t a r g e t s ) ，基于对象的存储盘o b d ( o b j e c t e d b a s e dd i s k ) 和客户端c ( c l i e n t ) 组成。 m d s 用于管理文件的元数据，方便文件的定位和存储；o s t 负责文件的实际i o 操作，直接与存储设备打交道；而o b d 提供底层的物理存储设备。在该系统中， 一个文件对象存储在两个o s t 中，当其中的一个o s t 出现故障时，存储客户可 以自适应地重定向到第二个o s t 上。所以在该系统中，可以克服单点失败，大 6 第二章存储系统当前的主流高可用性策略 大提高了系统的可用性和可靠性。 第二节用编码技术提高存储系统可靠性 大型存储系统大多采用磁盘阵列技术来对磁盘进行组织，磁盘阵列技术的 基本思想有两个方面：利用数据条纹化提高性能以及利用编码技术产生冗余数 据来提高可靠性。利用编码技术产生冗余数据可以通过牺牲一些存储空间保存 校验数据，来实现对用户数据的保护，从而达到提高可靠性的目的。在磁盘阵 列中使用编码技术产生冗余数据这个方法带来两方面的问题。一方面是冗余数 据如何计算，虽然某些r a i d t 】【1 2 ( r e d u n d a n t a r r a y so f i n e x p e n s i v ed i s k s ) 结构使 用海明码( h a m m i n gc o d e s ) 或里德一所罗门编码( r e e d s o l o m o nc o d e s ) ，但出于效 率上的考虑，多数情况下还是使用较为简单的奇偶校验( p a d t y ) 。另一方面的问 题就是冗余数据如何分布。按照冗余数据的分布方法的不同，可将磁盘阵列粗 略地分为两类：使用少数磁盘专门存放校验数据；将校验数据均匀分布到所有 磁盘。后者与前者相比，避免了可能出现的热点问题和其他负载不均的问题， 显然性能更优。在这一节中将介绍几种典型的磁盘阵列编码方法。 2 2 1r a i d 级别2 ( 类似内存的纠错码) r a i d 2 采用内存系统中常用的纠错码海明码( h a m m i n ge l t 0 1 c o r r e c t i n g c o d e ) t 1 3 】进行数据保护。用户数据以位或字节为单位进行条纹化，用户数据划分 为若干相互重叠的子集( 一个数据属于多个子集) ，每个子集的用户数据计算校 验数据存放在一个校验磁盘上。由于校验磁盘的数目正比于磁盘总数的对数， 因此r a i d 2 的磁盘冗余度要小于r a i d l ，阵列规模越大这种优势越明显。当一 个磁盘发生故障时，几个校验组的数据会不一致，而丢失数据即为这几个校验 组共同包含的数据，用其中一个校验组的剩余数据即可恢复丢失数据。如果对 可靠性要求很高，r a i d 2 还可通过使用多故障纠错海明码扩展为可容许多磁盘 故障的r a i d 结构。t h i n k i n gm a c h i n e s 公司的d a t av a u l t 存储子系统【1 4 】采用了 r a i d 2 结构。图2 1 给出了r a i d 2 的数据布局方法，其中用小写字母表示条纹 单元大小为位或字节，一d 表示用户数据，h 表示海明码校验数据。 7 第二章存储系统当前的主流高可用性策略 条纹o 条纹1 条纹2 条纹3 条纹4 磁盘1 d l d 5 d 9 d 1 3 d 1 7 磁盘4 - 6 ”l 囝3 h 禾7 h 8 1 l ： h 1 2 1 5 ：h 1 6 _ 1 9 ， 图2 - 1r a i d 级别2 数据布局 2 2 2r a i d 级别3 ( 位交错奇偶校验) r a i d 2 没有考虑磁盘故障模型，因为磁盘有故障检测和修正机制，而且磁 盘与控制器之间用相当复杂完善的协议进行通信，因此磁盘故障可以很容易地 通过其内部状态信息或控制器和它之间的通信检测出来。通常把这种故障部件 可以自识别的系统称为“擦除通道”( e r a s u r ec h a n n e l ) ，而把不能自己定位故障的 系统称为“差错通道 ( e l t o rc h a n n e l ) 。用于差错通道系统的“n - 故障检测编码” ( n f a i l u r ed e t e c t i n gc o d e ) ，如果用在擦除通道系统中，其纠错能力就相当于“n 故障纠正编码”( n f a i l u r ec o r r e c t i n gc o d e ) 。这种编码也常被形象地称为“擦除纠 正编码 ( e r a s u r e c o r r e c t i n gc o d e ) ，即磁盘故障好像一列数据被擦除一样，编码 用来进行数据恢复。相对应的是“差错纠正编码”( e r r o r - c o r r e c t i n gc o d e ) ，故障 定位和恢复都由编码进行。因此，对于磁盘阵列这种“差错通道 系统，只需 使用奇偶校验编码方法即可，而无须使用更复杂、冗余度更高的海明码。 条纹0 条纹1 条纹2 条纹3 条纹4 磁盘o磁盘1磁盘2磁盘3 d 2 d 6 d 1 0 d 1 4 d 1 8 d 3 d 7 d 1 1 d 1 5 d 1 9 图2 - 2r m d 级别3 数据布局 2 2 3r a i d 级别4 ( 块交错奇偶校验) r a i d 4 与r a i d 3 基本相同，不同之处在于r a i d 4 采用粗粒度条纹化，条 纹单元较大( 3 2 k b 或更大1 5 1 ) 。由于条纹单元较大，多数较小请求只涉及到一 个磁盘，磁盘阵列可并行处理多个请求。因此r a i d 4 更适合于并发度高，而请 求相对较小的应用，如在线事务处理系统( o n - l i n et r a n s a c t i o np r o c e s s i n g ，o l t p ) 。 但对于相对较大的请求，r a i d 4 也可提供较高的数据传输率。因此，对那种大 8 第二章存储系统当前的主流高可用性策略 多数请求较小，而包含少量较大请求的应用，r a i d 4 的效率也是较高的。图2 3 是r a i d 4 的数据布局方式，大写字母表示粗粒度条纹化。 条纹o 条纹1 条纹2 条纹3 条纹4 磁盘0磁盘1磁盘2磁盘3 d o d 4 d 8 d 1 2 d 1 6 d 1 d 5 d 9 d 1 3 d 1 7 d 3 d 7 d 1 1 d 1 5 d 1 9 图2 - 3r a i d 级别4 数据布局 2 2 4r a l l ) 级别5 ( 块交错校验分布) r a i d 4 的数据布局方式存在着严重的校验磁盘瓶颈问题。因为使用专用校 验磁盘，对于每个小的写请求，在更新数据单元的同时也要更新相应的校验单 元，这样校验磁盘的负载就是数据磁盘的1 1 1 倍，校验磁盘成为磁盘阵列系统的 瓶颈。而r a i d 3 却不存在这个问题，这是因为r a i d 3 采用细粒度条纹化，每个 请求都由所有磁盘共同完成，每个请求相对校验单元大小而言都是“大请求”， 因此校验磁盘的负载与数据磁盘是一样的。通过将校验数据分布到所有磁盘， r a i d 5 解决了r a i d 4 的这一缺点。由于校验更新负载均匀分布，因此消除了系 统瓶颈。r a i d 5 另一个不易察觉的好处是，用户数据也分布到所有磁盘，所有 磁盘在读操作中均可利用，因此r a i d 5 的读性能也优于r a i d 4 。r a i d 5 有多种 不同的数据和校验布局方式【l 6 】【l7 1 ，图2 4 给出了左对称布局方式。从图中可见， 左对称布局可以看作以r a i d 0 布局为基础，将校验单元插入对角线，校验单元 之后的数据单元依次后移的结果。因此左对称布局保持了r a i d 0 用户数据条纹 化连续性的特点，对于连续数据请求，其负载总是均匀分布到所有磁盘。也就 是说，当顺序读取数据时，总是会依次访问所有磁盘，而不会出现有的磁盘没 有访问，而有的磁盘却已读取多个单元的情况。因此在多种不同的r a i d 5 布局 方式中，左对称布局的性能是最优的【l6 】【1 7 】。注意到，r a i d l 和r a i d 3 可以分别 看作条纹长度为2 和条纹单元大小为一个位或字节的r a i d 5 特例。 9 第二章存储系统当前的主流高可用性策略 条纹0 条纹l 条纹2 条纹3 条纹4 磁盘0磁盘1磁盘2磁盘3磁盘4 d o d 5 d l o d 1 5 p 1 6 - 1 9j d 1 d 6 d 1 1 p 1 2 1 5 d 1 6 d 2 d 7 p 8 - 1 1i d 1 2 d 1 7 d 3 p 4 - 7 j d 8 d 1 3 d 1 8 p 0 3。 d 4 d 9 d 1 4 d 1 9 图2 - 4r a i d 级别5 数据布局 2 2 5r a i d 级别6 ( p + q 冗余) 奇偶校验编码只能恢复单一自识别故障。但有很多因素，如阵列规模越来 越大、重构过程中遇到不可恢复位故障等等，要求磁盘阵列系统使用容错能力 更强的编码。r a i d 级别卜p + q 冗余就是一种可容许双故障的r a i d 结构。 r a i d 6 采用r e e d s o l o m o n 编码。r e e d s o l o m o n 编码使用范德蒙行列式作为系数 矩阵进行校验数据的计算和维护，在解码过程中使用高斯消去法解方程组来恢 复丢失数据，r e e d s o l o m o n 编码的所有计算都是有限域上的运算【1 8 】。校验数据 的计算如下所示： l1 l，2 1 n 1 2 ”一n “一1 盔 如 d ， c l c 2 r a i d 6 使用的是m = 2 的r e e d s o l o m o n 编码，如果要求更高的可靠性，使 用m = k 的r e e d s o l o m o n 编码，即可使阵列具有容许k 个故障的能力。r a i d 6 除了校验计算方法不同外，其他各方面与r a i d 5 均很相似，图2 5 给出了类似 左对称的r a i d 6 布局方式。r a i d 6 的优点是磁盘冗余度低，只比r a i d 5 增加 了一个磁盘就提供了双故障容错能力。但r e e d s o l o m o n 编码计算较为复杂，一 般需要特殊硬件辅助才能获得较好性能，不适于用软件实现。 条纹o 条纹1 条纹2 条纹3 条纹4 磁盘0磁盘1 磁盘2磁盘3 图2 - 5r a i d 级别6 数据布局 l o 磁盘5 ：q 0 - 3 ，l d 5 d 1 1 q 1 2 一1 5 d 1 7 第三章n l 0 v 系统分析 第三章n l o v 系统分析 n l o v 存储系统是南开大学并行与分布式软件技术实验室正在开发的大型 存储系统，本文作者是系统开发的核心成员之一。n l o v 中文全称为基于网络 的虚拟存储系统，其中n 为n e t w o r k ，表示该系统是面向广域网的；l 为l o 西c a l ， 系统是以逻辑卷管理器为基础的；0 为o b j e c t ，表示该系统是面向对象的存储系 统；v 为v i r t u a l ，该系统属于虚拟存储系统。该系统是顺应当前存储系统发展 方向而开发出来的虚拟存储系统，该系统采用基于广域网的架构，支持动态加 入、删除存储节点，系统存储容量在理论上上可以无限扩展。该系统采用基于 动态区间映射的数据布局算法【1 9 】来对系统数据进行布局，通过使用t i g d 2 0 】算法 实现数据在系统各个存储节点上的均衡散布，这样可以保证数据均衡的散布在 各个存储节点上，在提供数据服务的时候各个节点的负载与节点的服务能力成 正比，在进行数据迁移的时候保证数据迁移最优。 第一节整体结构 3 1 1n l o v 的系统架构 n l o v 采用s a n t 2 1 】t 2 2 ) ( s t o r a g ea r e an e t w o r k ) 文件服务器架构，系统分为三 个相对独立的组成部分：客户端( c l i e n t ) 、元数据服务器( m e t a d a t as e r v e r ) 、存储节 点( s t o r a g es e r v e r ) 。n l o v 存储系统的系统架构如图3 1 所示，图中c l i e n t l 、c l i e n t 2 属于客户端，m d s 是元数据服务器，s s l 、s s 2 属于存储节点。系统各部分都有 明确的分7 - - 元数据服务器是系统的管理者，负责管理整个系统的全局信息； 存储节点是系统的仓库，负责存储系统的具体数据；客户端是系统的窗口，负 责作为服务器为应用程序提供服务，在系统内部它们又是一个个客户端，因为 它们的数据都由元数据服务器和存储节点来提供。 第