首页 | 邮件资讯 | 技术教程 | 解决方案 | 产品评测 | 邮件人才 | 邮件博客 | 邮件系统论坛 | 软件下载 | 邮件周刊 | 热点专题 | 工具
网络技术 | 操作系统 | 邮件系统 | 客户端 | 电子邮箱 | 反垃圾邮件 | 邮件安全 | 邮件营销 | 移动电邮 | 邮件软件下载 | 电子书下载

网络技术

邮件原理 | 硬件设备 | CISCO | 网络协议 | 网络管理 | 传输介质 | 线路接入 | 路由接口 | 邮件存储 | 华为3Com |
首页 > 网络技术 > 邮件存储 > RAID6及“准RAID6”算法介绍 > 正文

RAID6及“准RAID6”算法介绍

出处:ChinaUnix 作者:pekics 时间:2007-1-9 19:18:00
 既然是讲原理,那些“为什么需要RAID6”、“RAID6的优势”等内容就都省去了。直接进入枯燥无趣的理论。

  一、RAID5和XOR运算

  为了照顾初学者,还是先把相关基本概念介绍一下,老手可以跳过这部分直接看下面。(别低头!是看本帖下面,想些什么呐~)

  XOR运算是数理逻辑的基本运算之一,在课本上的符号是一个圆圈里面一个加号。实在懒得用插入符号功能,大家就凑合着看吧。

  两个数字之间的XOR运算定义是:

  1 XOR 1 = 0

  1 XOR 0 = 1

  0 XOR 1 = 1

  0 XOR 0 = 0

  多个数字XOR的时候,有两个特点:

  A)结果与运算顺序无关。也就是 (a XOR b) XOR c = a XOR (b XOR c)。

  B)各个参与运算的数字与结果循环对称。如果 a XOR b XOR c = d,那么a = b XOR c XOR d;b = a XOR c XOR d;c = a XOR b XOR d。

  磁盘阵列中的RAID5之所以能够容错,就是利用了XOR运算的这些特点。上面例子中的a、b、c、d就可以看作是四颗磁盘上的数据,其中三个是应用数据,剩下一个是校验。碰到故障的时候,甭管哪个找不到了,都可以用剩下的三个数字XOR一下算出来。

  在实际应用中,阵列控制器一般要先把磁盘分成很多条带(英文叫Stripe,注意不是Stripper),然后再对每组条带做XOR。

  P1 = 数据a XOR 数据b XOR 数据c

  P2 = 数据d XOR 数据e XOR 数据f

  P3 = 数据g XOR 数据h XOR 数据i

  P4 = 数据j XOR 数据k XOR 数据l

  扫盲部分就讲这么多,再不懂就google吧,满山遍野都是RAID5算法的介绍。

  

二、RAID6和Reed-Solomon编码

  本来想写成“李德-所罗门编码”,但那样就不方便大家一边看帖子一边google了。

  Reed-Solomon编码是通讯领域中经常碰到的一个算法,已经有15年以上的历史了。(靠!讲存储嘛,跟通讯有个鸟关系?)

  其实很多校验算法都是通讯领域最先研究出来,然后才应用到其他领域的。前面说到的XOR算法对一组数据只能产生一个校验,搞通讯的工程师们觉得不够可靠,于是就研究出很多能对一组数据产生多个校验的算法。Reed-Solomon编码是其中应用最广泛的一个,咱们以前经常用的ADSL、xDSL、高速Modem都有采用。后来手机、卫星电视、数字电视、CD唱片、DVD、条码系统、还有……(有完没完!说存储呢!)连高级点儿的服务器内存也用这个算法做校验和纠错。(总算跟存储沾上点儿边~)

  现在存储的工程师也觉得RAID5中只能容忍一颗磁盘离线不够理想,需要一种容忍多颗磁盘离线的技术,自然就会想到Reed-Solomon编码啦。把这种算法应用到存储中,就可以让N颗磁盘的空间装应用数据,M颗磁盘的空间装校验码(对一组N个数据生成M个校验,但实际上校验码是分散在所有磁盘上的),这样只要离线的磁盘不大于M颗,数据就不会丢失。

  Reed-Solomon编码理论中有一个公式:

  N + M + 1 = 2的b次方(在电脑里写公式真是麻烦!)

  其中b是校验字的位数。(校验字是生成校验过程需要用的一个东东,不是最后的校验码。)举例来说,如果用8位的字节做校验字,那么M + N = 255,而RAID6是特指M = 2,这样N = 253。

  就是说,用8位字节做校验字的话,理论上一个RAID6的磁盘组可以容下253颗磁盘。

  当然啦,实际应用中,太多的磁盘一起做运算会严重影响性能,所以阵列控制器和芯片的设计者都会把磁盘组的容量限制在16颗左右。

  (做了这么多无聊算术题,还是没提RAID6到底是啥!)

  喂!喂!别走啊,很快就讲到RAID6的实现啦。

  卖了这么多关子,实在是因为RAID6这个概念所指的意义太混乱。从功能上讲,能实现两颗磁盘掉线容错的,都叫RAID6。(至少我认识的销售们都这么认为。)但是实行这一功能的方式却有很多很多。(沉默3分钟)

  真的很多!哎哟!别打啊~

  Intel的P+Q RAID6,NetApp的RAID-DP,HP的RAID5-DP,还要很多实验室中的原型机都能实行这个功能。但是由于机制不同,各种所谓的RAID6,其性能表现、磁盘负载分布、错误恢复方式都完全不同。

  你让我从哪说起好哩?

 三、基于P+Q的RAID6

  在Intel的80333IOP芯片中,有一个新的引擎叫P+Q单元,是专门用来处理RAID6加速的。详情请查阅Intel官方网站,下课……(鸡蛋、西红柿、拖鞋。咦!这是谁的臭袜子?)

  好啦~当偶真不知道啊!

  Intel的P+Q RAID6是这样写磁盘的:

  

  这里每个条带中的P,跟RAID5里面的P意义完全一样,就是同一条带中除Q以外其它数据的XOR运算结果。

  而Q呢,就是理解这个技术的关键所在了。

  咳~咳~听好了。

  Q是同一条带中各数据的Galois Field进行XOR运算的结果。

  “找到条带中每个数据的GF,然后这些GF再XOR一下,就得到Q。”

  (大哥,你到底懂不懂啊!GF是Galois Field的缩写,是法国著名数学家伽罗瓦发明的一种数学变换。)

  哦,想起来了。伽罗瓦嘛,发明群论的那个。生于法国大革命前,二十出头就英年早逝,还是为了个姑娘跟人决斗被打死的。最著名的成果就是给3次以上方程判了死刑。是我人生第二偶像啊……

  这个GF变换呢,就是这个淘气的伽同学当年为了逃避老师点名,而发明的一种教室换座位方法。按照这种方法,每个人都不会坐在自己的座位上,而且每个人都肯定会有座位。而且任意个同学的座位号进行XOR运算之后,仍然跑不出这个教室里的座位号。

  (这个伽同学好像很无聊噢!没办法,人家聪明嘛!)

  扯太远啦!回到正题。

  在Intel 80333IOP中存着两个表格,分别对应GF正向变换和反向变换。任何一个8位二进制数,都可以直接在表格中查到对应的GF变换结果。(我还是想把这个结果说成是源数据的女朋友~)

  这两个表格分别在Intel 80333IOP研发手册的第445页和446页,不过我估计大部分人会懒得去看。也是,看了又能怎么样呢?反正Intel已经把那玩意固化到芯片里了。

  如果一颗磁盘掉线,根本不需要Q用P直接就搞定了,跟RAID5一样。

  如果两颗磁盘掉线,又分做两种情况:

  A)坏的地方有Q。这种情况跟RAID5坏一颗磁盘一样,用XOR就恢复了。

  B)坏的地方没有Q。用GF变换加XOR一起搞定。按照Intel的官方说法,是用“恢复矩阵”进行恢复。

  结合上面表格的例子,如果磁盘5和磁盘6掉线。那条带1和条带2就属于情况A;而条带3、4、5和6属于情况B。

  其实P+Q只是一种算法,Intel IOP里面的硬件加速引擎并不是必须的。有一些产品就采用了PowerPC等不含P+Q引擎的CPU,一样不耽误P+Q RAID6功能。

  GF转换表在软件里完成就是了。

四、Dual-XOR

  除了P+Q RAID6,还要好多种办法可以实现对两颗磁盘掉线的容错。

  Intel提到一种Dual-XOR算法,这种方法就是取横向和斜向两个方向进行XOR运算,这样每个应用数据都在两个校验中留下痕迹,当两颗磁盘掉线时,就可以恢复数据。

  但是Dual-XOR的恢复工作异常复杂艰苦,并不实用。很多技术人员研究这种算法的意义,完全是把它当作未经优化的原型思想。

  

  如图,Pa是横向的校验,跟RAID5完全一样:

  Pa1 = 数据a XOR 数据b

  Pa2 = 数据c XOR 数据d

  …………

  Pa6 = 数据k XOR 数据l

  Pb是斜向校验,定义为:

  Pb4 = 数据a XOR Pa2 XOR数据f

  Pb5 = 数据c XOR 数据e XOR Pa4

  Pb6 = Pa3 XOR数据h XOR 数据j

  可以看出Dual-XOR的校验生成过程比P+Q要简单(没有GF,生活就是简单!),但是根据“麻烦守恒定律”,正向工作简单的事情,一般反向工作都会复杂。

  备份和恢复一般也遵循这个规律。

  (别跟我提CDP,那东西是遵循的是广义麻烦守恒定律。每个I/O都打个时间标签,还都当宝贝存着不扔,这能是个不麻烦的事吗?Sorry,又扯远了。)

  当两颗磁盘掉线的时候,Dual-XOR的算法只能支持逐个数据块的恢复,而且不同条带之间还要共同参与计算。

  比如图中的磁盘1和2掉线,恢复数据e的时候,就要至少动用到数据f、Pb3、Pa4和Pb5。而数据c和Pa3的恢复还要依赖数据e的恢复。

  总之恢复起来是件贼头痛的事情!

 五、NetApp RAID-DP

  虽然Intel的Dual-XOR理论意义大于实际意义,但其改良的版本RAID-DP却已经被NetApp产品化。NetApp之所以喜欢这个类似Dual-XOR的RAID-DP算法,原因也很简单。

  NetApp原本用的就是RAID4,而不是RAID5,其算法的中心思想就是每次I/O只跟两颗磁盘打交道就OK,自然就不会在乎RAID-DP中很多动作都只跟两、三颗磁盘打交道。

  (这个思想也许在很多RAID5的Fans看来有点奇怪,难道不是磁头越多性能就越好吗?但是人家NetApp这么多年的经验都集中在WAFL文件系统上,而WAFL文件系统又是专门针对这种思想优化的。所以NetApp对这个略有异类的思想不仅没有放弃,而且还越研究越起劲。)

  这个递归式数据恢复机制简直像在玩RPG游戏,但是对WAFL文件系统来说,却的确是最合适的选择之一。

  

   六、五花八门的“准RAID6”

  除了RAID-DP,还有X-Code编码、ZZS编码、Park编码……都可以看做是“准RAID6”。

  X-Code编码

  下面这个图是X-Code编码的解释。

  

  P3x = 数据33 XOR 数据35 XOR 数据32

  Px4 = 数据44 XOR 数据24 XOR 数据54

  其他的校验是啥意思,不需要一一列出来了吧~

  X-Code从理论上看,的确是个负载均衡、计算简单(只有XOR,没有类似GF一样的变换)、磁盘对称度很高的算法。但是实际应用还是有问题。

  上图的例子是5颗磁盘的X-Code编码方式,例子中的5个条带是一个整体,一起处理。如果写入的数据不多,没有写满前3个条带,就需要在写入的同时,把未更新的数据读出来,凑齐3x5个数据,再一起计算校验码。

  如果是6颗磁盘,那就要6个条带作为一个整体。

  7颗磁盘一个RAID组,就需要7个条带一个整体。

  8颗磁盘一个RAID组,就需要8个条带一个整体。

  9颗磁盘一个RAID组,就需要9个条带一个整体。

  10颗磁盘一个RAID组,就需要10个条带一个整体……

  (打住!在这发帖子又没稿费,不用拼命凑字!)

  总之这个算法的“重复单元”有点大。在实际应用中,这么大的“重复单元”使X-Code的应用面临两个问题:计算量大和空间浪费。(可能还有其他问题,比如名字太难听,总让人联想到黄色的东东。)

  ZZS编码

  ZZS也叫俄罗斯编码,bingo!猜对了,真聪明。这就是三个俄罗斯人在1983年提出的一种编码方式,ZZS就是三个人名字首字母缩写,跟S.H.E.演唱组的命名规则一样。

  与X-Code相比,ZZS的“重复单元”就小很多——7颗磁盘的时候,3个条带是一个整体。

  人家ZZS论文里给出的是数学公式:n颗磁盘的时候,(n-1)/2个条带是一个整体。

  从这个公式你应该能发现ZZS编码的一个要求……(我知道,只支持单数颗磁盘。)

  嘿嘿!你错了!实际上,ZZS算法只支持磁盘的个数为素数:……5、7、11、13、17……

  不过人家ZZS组合(暂时就这么称呼吧)也指出,ZZS算法支持其中一颗磁盘上面全写0。这样就可以在应用中支持4、6、10、12、16……(素数-1)颗盘了。

  什么?还没明白?在计算的时候,内存里虚拟一个全0的影子盘不就行啦!

  

  Park编码

  Park是名IBM的员工,在Yorktown上班。他的业余爱好是……(Sorry,又差点跑题)

  相比俄国人训练有素的数学功底,美国人既没有兴趣,也没有耐心再从算法上去优化“双重校验”的技术。但是美国人讲求实际的思想还是挺值得称道。

  这不,人家Park就说了,“研究了这么多算法,最终目的不就是坏两颗盘数据仍可恢复吗。到头来算法搞得那么复杂,还不如我的看家本领——穷举法——更实在。”

  Park同志是这样说的,也是这样做的(凝重的音乐声响起~)

  他编了一个程序,让计算机帮他搜索给定磁盘数量的校验分布模式。

  结果你猜怎么着,人家还真有收获。从3颗磁盘到38颗磁盘,除了8颗磁盘和9颗磁盘的情况,其他情况Park都找到了满足要求的校验分布模式。

  什么?你问满足的是什么要求?两颗磁盘掉线数据可恢复啊。汗!

  后来,一个名叫徐力浩(音)的中国人补上了8颗盘和9颗盘的校验分布表。(咱们中国人到底还是比米国人聪明那么一点点,哈~)

  现在Park编码已经对从3颗到38磁盘的所有情况,都能给出双重校验分布方法。但是各种分布方法之间根本没有联系,所以只能在给定磁盘数量的时候,去查Park编码表。Park编码的样子都是以3个条带为一个“重复单元”,其中1个条带专门用来存校验,另外2个存数据。

  

相关文章 热门文章
  • 了解RAID 6
  • RAID数据恢复常见故障处理手册
  • RAID扫盲
  • Raid教程:全程图解手把手教你做RAID
  • Windows server 2003创建软RAID完全手册
  • 如何使用Server RAID support CD 配置阵列
  • RAID5和RAID10,哪种RAID更适合你(下)
  • RAID5和RAID10,哪种RAID更适合你(上)
  • 存储入门系列——软RAID
  • 存储入门三步曲3——图文详解RAID5
  • 存储入门三步曲2——稳定之王RAID1
  • 存储入门三步曲1——容量之王RAID0
  • 磁盘阵列配置全程解(图)
  • 硬盘接口技术详解
  • 高档企业磁盘阵列选购指南
  • VERITAS NetBackup的安装
  • 网络存储之RAID卡全解析
  • RAID技术简述
  • 硬盘及磁盘阵列常用技术术语
  • SCSI大实话
  • SATA硬盘使用攻略
  • 硬盘“0”磁道损坏的排解
  • 细谈磁盘阵列的各种选购要素
  • 浅析硬盘“空间”与“文件大小”秘密
  • 自由广告区
     
    最新软件下载
  • SharePoint Server 2010 部署文档
  • Exchange 2010 RTM升级至SP1 教程
  • Exchange 2010 OWA下RBAC实现的组功能...
  • Lync Server 2010 Standard Edition 标..
  • Lync Server 2010 Enterprise Edition...
  • Forefront Endpoint Protection 2010 ...
  • Lync Server 2010 Edge 服务器部署文档
  • 《Exchange 2003专家指南》
  • Mastering Hyper-V Deployment
  • Windows Server 2008 R2 Hyper-V
  • Microsoft Lync Server 2010 Unleashed
  • Windows Server 2008 R2 Unleashed
  • 今日邮件技术文章
  • 腾讯,在创新中演绎互联网“进化论”
  • 华科人 张小龙 (中国第二代程序员 QQ...
  • 微软推出新功能 提高Hotmail密码安全性
  • 快压技巧分享:秒传邮件超大附件
  • 不容忽视的邮件营销数据分析过程中的算..
  • 国内手机邮箱的现状与未来发展——访尚..
  • 易观数据:2011Q2中国手机邮箱市场收入..
  • 穿越时空的爱恋 QQ邮箱音视频及贺卡邮件
  • Hotmail新功能:“我的朋友可能被黑了”
  • 入侵邻居网络发骚扰邮件 美国男子被重..
  • 网易邮箱莫子睿:《非你莫属》招聘多过..
  • 中国电信推广189邮箱绿色账单
  • 最新专题
  • 鸟哥的Linux私房菜之Mail服务器
  • Exchange Server 2010技术专题
  • Windows 7 技术专题
  • Sendmail 邮件系统配置
  • 组建Exchange 2003邮件系统
  • Windows Server 2008 专题
  • ORF 反垃圾邮件系统
  • Exchange Server 2007 专题
  • ISA Server 2006 教程专题
  • Windows Vista 技术专题
  • “黑莓”(BlackBerry)专题
  • Apache James 专题
  • 分类导航
    邮件新闻资讯:
    IT业界 | 邮件服务器 | 邮件趣闻 | 移动电邮
    电子邮箱 | 反垃圾邮件|邮件客户端|网络安全
    行业数据 | 邮件人物 | 网站公告 | 行业法规
    网络技术:
    邮件原理 | 网络协议 | 网络管理 | 传输介质
    线路接入 | 路由接口 | 邮件存储 | 华为3Com
    CISCO技术 | 网络与服务器硬件
    操作系统:
    Windows 9X | Linux&Uinx | Windows NT
    Windows Vista | FreeBSD | 其它操作系统
    邮件服务器:
    程序与开发 | Exchange | Qmail | Postfix
    Sendmail | MDaemon | Domino | Foxmail
    KerioMail | JavaMail | Winwebmail |James
    Merak&VisNetic | CMailServer | WinMail
    金笛邮件系统 | 其它 |
    反垃圾邮件:
    综述| 客户端反垃圾邮件|服务器端反垃圾邮件
    邮件客户端软件:
    Outlook | Foxmail | DreamMail| KooMail
    The bat | 雷鸟 | Eudora |Becky! |Pegasus
    IncrediMail |其它
    电子邮箱: 个人邮箱 | 企业邮箱 |Gmail
    移动电子邮件:服务器 | 客户端 | 技术前沿
    邮件网络安全:
    软件漏洞 | 安全知识 | 病毒公告 |防火墙
    攻防技术 | 病毒查杀| ISA | 数字签名
    邮件营销:
    Email营销 | 网络营销 | 营销技巧 |营销案例
    邮件人才:招聘 | 职场 | 培训 | 指南 | 职场
    解决方案:
    邮件系统|反垃圾邮件 |安全 |移动电邮 |招标
    产品评测:
    邮件系统 |反垃圾邮件 |邮箱 |安全 |客户端
    广告联系 | 合作联系 | 关于我们 | 联系我们 | 繁體中文
    版权所有:邮件技术资讯网©2003-2010 www.5dmail.net, All Rights Reserved
    www.5Dmail.net Web Team   粤ICP备05009143号