RAID6结构原理详解51CTO博客 - 娱乐之横扫全球

RAID6结构原理详解51CTO博客

2019-01-03 17:03:52 | 作者: 问凝 | 标签: 运算,数据,能够 | 浏览: 2183

【什么是RAID】

    RAID的概念描绘在互联网上举目皆是,用最简略的原理描绘,便是在界说存储办法时答应在一部分数据缺失的状况下不影响悉数数据,类似于通讯范畴的纠错码。不同的冗余形式形成了不同的RAID类别。       

【单一冗余模型】

    咱们需求先描绘仅具有一个磁盘冗余的RAID模型(思想同RAID3,RAID4,RAID5)。

    假定现在有3页空白的纸,用来记载一些数字,为了更明晰地记载,咱们先将每页白纸划出相同巨细的一些表格。再假定有一个或许:这3页纸,特定状况下会有其间某一页丢掉。为了在上述设定状况确保这些数字能完好安全的记载下来,咱们要规划一些相互牵连的冗余联系。

    如咱们要记载的数字序列是:3、14、28、4、98、88  。咱们能够顺次在第1页和第2页写要记载的数字,在第3页写上他们的和。如下图所示:

    依据上图,能够很简略的分分出,不管这3页中的哪一页丢掉,都能够经过另两页核算另一页的数据来。很显然,即使是超越3页的状况,按上述办法规划记载形式,也能够支撑恣意一页记载的丢掉。

    但这个模型却不会在实践中运用,原因来自于上图的第三行数据:98+88 = 186 ,从这行的运算来看,为了记载整个一行数据的和,校验页所用的空间要大于等于任何一个数据页。其实,校验和的总容量要等于一切数据页的总容量,换个视点说,假如记载的是10页数据,那么或许要用其他10页的空间来记载校验,这是彻底没有含义的计划(与其这样,还不如一切数据抄两份,即RAID1的模型)

    所以,一些工程师开端用其他算法替代加法,以削减校验和的总容量,但算法的完结作用需求与加法彻底相同,一起运算要满意简略。最好的计划便是异或。

    异或是依据位的运算,首要其运算功能非常好,无需更多的专门运算器。一起异或算法彻底满意正运算与逆运算的彻底映射(即,正运算的成果仅有,一起这个正运算的逆运算成果也仅有。这个在数学上叫什么?恕笔者数学根柢差,暂时这样称号),满意交换律和结合律。并且最重要的是,异或不会升位。

    用异或算法改写后的存储记载如下:

    能够很明晰得看到,第三行的校验和,不再是3个数字,并且不管多少个数据成员,用异或得到的校验和容量不会累加。

    为了更好的归纳,咱们用"+"表明这个正向的校验运算,用“-”表明其逆运算。在咱们开始的描绘中,就表明数字的加减法,之后"+"表明异或,“-”也是异或(异或的逆运算也是异或,所以运算器简略,速度快)

    假定有n个存储成员,把每个存储成员划分红若干个存储单元,其间n-1(数学减法,下面的Dn-1同理)个成员盘为数据,1个成员盘为校验。每个水平条带上的校验联系如下:

   D1 + D2 + D3 + ... +Dn-1 = P1

   Dx = P1 - D1 - D2 - D3 - ... -Dn-1(D序列中扫除Dx)

也便是:Dx = P1 + D1 + D2 + D3 +... +Dn-1(D序列中扫除Dx)

 

【屡次冗余模型】

        上述单一冗余仅支撑一个存储成员的缺失,在实践中有或许需求更高的冗余性,则需求更进一步对算法进行改善。

        假如需求规划一种存储模型,完结在缺失2个成员的状况下,存储全体仍然能够运算完好,最好的数学模型恐怕便是二元一次方程了,形如下面方程组:

    aX+bY=c

    dX+eY=f。 其间a/d  != b/e

    上述方程式用到乘法与除法,一起,乘法与除法彻底可逆,且满意交换律、结合律与分配率。

    仍是在加法中遇到的困难,一般的数学乘法会导致校验容量的累加,所以不可取。有没有一种乘除法契合咱们的要求呢?有!---依据伽罗华域的乘除法。

    数学概念是很笼统的,仅以GF(2^8)为例,咱们规划一个有限循环域,域上仅有0-255这几个数字,这些数字之间再规划一个完好的加减乘除运算,其成果仍然在这些数字中,并且运算成果仅有,无二义性。

    咱们来规划一种算法,关于2,假如2的n次方大于某个值(来源多项式),则让其对这个值(来源多项式)取余,确保又折回到0-255这个范围内,假如从2^0,2^1,2^2,,,直到2^255,按这个规则做运算,得到的值均处于0-255范围内,且均不持平,这样就形成了一个一对一的映射联系,一起满意2的这些次幂与成果之间就乘法/除法的运算规则(详细理论需参阅群、环、域、有限域等数学理论)。

    在GF(2^8)上,有16个满意条件的来源多项式,别离如下:

1     x8+x7+x6+x5+x4+x2+1          1 1111 0101 = 0x1F5  

2     x8+x7+x6+x5+x2+x+1            1 1110 0111 = 0x1E7

3     x8+x7+x6+x3+x2+x+1            1 1100 1111 = 0x1CF

4     x8+x7+x6+x+1                         1 1100 0011 = 0x1C3

5     x8+x7+x5+x3+1                       1 1010 1001 = 0x1A9

6     x8+x7+x3+x2+1                       1 1000 1101 = 0x18D

7     x8+x7+x2+x+1                         1 1000 0111 = 0x187

8     x8+x6+x5+x4+1                       1 0111 0001 = 0x171

9     x8+x6+x5+x3+1                       1 0110 1001 = 0x169

10   x8+x6+x5+x2+1                       1 0110 0101 = 0x165

11   x8+x6+x5+x+1                         1 0110 0011 = 0x163

12   x8+x6+x4+x3+x2+x+1            1 0101 1111 = 0x15F

13   x8+x6+x3+x2+1                       1 0100 1101 = 0x14D

14   x8+x5+x3+x2+1                       1 0010 1101 = 0x12D

15   x8+x5+x3+x+1                        1 0010 1011 = 0x12B

16   x8+x4+x3+x2+1                      1 0001 1101 = 0x11D

     常用0x11D做为raid6的来源多项式,意思是2的n次方假如大于0x11D,就关于做xor的取余运算,确保成果小于0x256,这样就能够算出2^0到2^255之间的一切数值。

    GF(2^8)上的加减法同样是异或算法(xor)。

    GF(2^8)上的乘法即多项式乘法,但仍然要对来源多项式取xor余,在算法规划上,有多种核算办法,但在GF(2^8)上,最快的引荐办法是查表法,只需事前核算好一切的0~255 别离乘以 0~255的值,生成65536个值的表格,核算时直接查表即可。也有运用对数查表法,使乘法转变为加法进行运算的,需求查表和加法结合运用。

    GF(2^8)上的除法可转换为对其逆元的乘法,即a 除以 d,假定d对应于(x的m次幂),那找出对应(x的255-m次幂)的值d,a除以d,即等于a乘以d。

【RAID6】

    在,加减乘除都确认后,2元一次方程组就能够求解了。所以,一个以此原理生成的RAID的结构规划大致如下图(以5块盘为例,P为榜首重校验,Q为第二重校验,xn为数据):

     之所以P和Q螺旋式循环散布,是为了使一切磁盘负载均衡,假如欠好了解,能够把P和Q独自放在一列中,算法的含义是相同的。

   再重复一下,下面提及的+、-、*、/运算都是指依据GF(2^8)上的加、减、乘、除

   P值等于同一行(条带)上的一切单元相加的和。或许能够了解为1与每个单元相乘后的累加和,如榜首个条带的P:

    P= x1+x2+x3  也便是P=1*x1 + 1*x2 + 1*x3

   在GF(2^8)上,每个多项式对应一个0~255的值,即d0对应多项式X的0次幂,d1对应多项式X的2次幂等,按多项式打开,X为2进制,故d0 = 1,d1 =2,d2=4 ,d3=8,等等,如下表所示:

    回来RAID结构图中,Q值等于每个数值单元格乘以他们的相应的dn再累加的成果,其间dn可约好,只需确保同一条带的运算中不重复呈现dn即可,如榜首行的Q能够为:

Q = d1* x1 + d2*x2 +d3*x3

这样,关于每一行(条带),就能够确保恣意2个单元丢掉,都能够核算出来(为了明晰,以下核算直接将减法改为加法):

以榜首行为例:

a) 假如P,Q均丢掉,数据区不影响,x1,x2,x3均可正常读写

b)假如xn丢掉,依据P或Q都可核算出来(实践中,因P 的核算更快速,通常会运用P校验核算出丢掉的 xn)

c)假如P,xn丢掉,P值不做处理,假定丢掉的是x2,依据Q值的界说

      Q = d1* x1 + d2*x2 +d3*x3

=> d2*x2 = Q + d1*x1 + d3*x3

=> x2 = (Q + d1*x1 + d3*x3) * x253 ;//注:x253为x2的逆元,能够查表得到

d) 假如两个x丢掉,则可依据二元一次办法的规范解法进行求解,假定丢掉的是x1,x3:

      P = x1+x2+x3

      Q =  d1* x1 + d2*x2 +d3*x3

=> x1 = P + x2 + x3

=> Q = d1 * (P + x2 + x3) +d2*x2 +d3*x3

=> Q = d1*P + d1*x2 + d1* x3 + d2*x2 + d3*x3

=> Q = d1*P + d1*x2 + d2*x2 + d1*x3 + d3*x3

=> Q + d1*P + d1*x2 + d2*x2 = (d1+d3) * x3

=> x3 = ( Q + d1*P + d1*x2 + d2*x2) / (d1+d3)

查表法得到(d1 + d3)的逆元dn后,可知

x3 = ( Q + d1*P + d1*x2 + d2*x2) * dn  

再依据P= x1 + x2 + x3求得x1,即完结一切数据的补缺。

版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表娱乐之横扫全球立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章