未命名

RAID6磁盘阵列

 

第一部分预热知识
 
 XOR算法是RAID运算里最基础的概念,也是RAID5的容错原理,在RAID6里也将频繁涉及到。
XOR最基本的bit运算法则为:1⊕1 = 0, 0⊕0=0, 1⊕0=1.因此,会衍生出如下的byte运算法则,对于byte数据M来说:M⊕M=0, M⊕0=M。
    如果P为数据块X,Y,Z计算的XOR 值,也就说P = X⊕Y⊕Z时;当X数据块故障时,可以通过P,Y,Z来得到它,也就是X = P⊕Y⊕Z = (X⊕Y⊕Z) ⊕Y⊕Z=X⊕(Y⊕Y) ⊕(Z⊕Z)。
这就是基于XOR运算的RAID5能够允许一个存储设备故障的根本原因。其中RAID6中的两个校验块,其中一块就采用了XOR算法即P位。而另一个校验位采用的是伽罗瓦域运算和里德-所罗门编码算法来计算另一块位Q位。这是恢复RAID6的关键算法,此算法原理非常复杂,下面就请兆柏高级工程师给你讲解吧。
伽罗瓦域运算包括+,-,*,÷,其中,+-就是采用XOR(异或算法),*主要通过转换成相应的多项式乘积,例如:{53} • {CA} = {01}
原理如下:
(x6 + x4 + x + 1)(x7 + x6 + x3 + x) =x13 + x12 + x9 + x7 + x11 + x10 + x7 + x5
+ x8 + x7 + x4 + x2 + x7 + x6 + x3 + x =x13 + x12 + x9 + x11 + x10 + x5 + x8 + x
4 + x2 + x6 + x3 + x =x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x4 + x3 + x2
+ x
上面已经详细介绍了伽罗瓦域运算加法就是相应的xor因此,四个x7 相加就是0,再把所得的结果与多项式
x8 + x4 + x3 + x + 1求mod运算。如下:x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 +
x4 + x3 + x2 + x modulo x8 + x4 + x3 + x + 1 = (11111101111110 mod 100011011) = 1
此算法比较难理解吧,RAID6的核心算法技术就是伽罗瓦域的运算,下面就用程序为你实现吧。算法实现如下:
 
 
 
/* GF(2^8)有限域中的两数相加 */
uint8_t gadd(uint8_t a, uint8_t b) {
        return a ^ b;
}
 
/* GF(2^8)有限域中的两数相减*/
uint8_t gsub(uint8_t a, uint8_t b) {
        return a ^ b;
}
 
/* GF(2^8)有限域中的两数相乘
 * 相乘结果与多项式 x^8 + x^4 + x^3 + x + 1求mod */
uint8_t gmul(uint8_t a, uint8_t b) {
        uint8_t p = 0;
        uint8_t counter;
        uint8_t hi_bit_set;
        for(counter = 0; counter < 8; counter++) {
               if(b & 1) 
                       p ^= a;
               hi_bit_set = (a & 0x80);
               a <<= 1;
               if(hi_bit_set) 
                       a ^= 0x1b; /* x^8 + x^4 + x^3 + x + 1 */
               b >>= 1;
        }
        return p;
}
此算法就是校验位RAID6校验位Q算法原理。
 
第二部分 RAID6实现方法
 
 RAID6磁盘阵列数据和校验存储结构图如下:
 
 
RAID6写入需要计算双重校验,第一重校验和RAID5一样,采用XOR校验,从上面的讲解可知,异或运算法则比较简单,为此一些厂商设计了专门的硬件来完成;在Intel的IOP33x处理器上就有专门的硬件模块,XOR应用加速器 (Application Accelerator with XOR),它专门处理异或运算,将CPU解放出来,从而提高整个系统的性能。同时写多个数据块时,P = D0⊕D1⊕D2⊕D3,只需告诉XOR应用加速器D0, D1, D2, D3在内存的位置,它就可以自动的完成XOR计算得到P。
    对于第二重校验,需要采用基于伽罗瓦域(Galois Field)计算操作的Reed- Solomon编码,也就是说在计算Q时,会引入一个系数Ki,如图-1所示:Q = (K0⊙D0)⊕(K1⊙D1)⊕(K2⊙D2)⊕(K3⊙D3)
同样,由于RAID6采用了更为复杂的算法,因此可以设计专门的硬件来完成RAID6计算,Intel的IOP333上就有RAID6应用加速器 (Application Accelerator for RAID6);它和XOR应用加速器一样,只需要知道数据D0,D1,D2,D3在内存中的位置,它就可以自动完成RAID6的计算。
 
第三部分 RAID6数据恢复原理
 第一种情况 P、Q故障

    当两个校验数据出现故障时,此时是最简单的情况,只需要将现有的数据按照P、Q计算方法,重新得到新数据,就可以恢复故障了。
第二种情况 P与数据盘故障

     如某数据,暂时记为D2与P发生故障,那么可以通过如下计算来恢复它:
     计算一个中间变量Q’:Q’= (K0⊙D0)⊕(K1⊙D1)⊕(K3⊙D3),

     D2可以通过如下公式得到(K2-1是K2在GF(8)表中的逆值):


    K2-1⊙(Q⊕Q’)=K2-1⊙{[(K0⊙D0)⊕(K1⊙D1)⊕(K2⊙D2)⊕(K3⊙D3)]⊕

    [(K0⊙D0)⊕(K1⊙D1)⊕(K3⊙D3)]}

    = K2-1⊙(K2⊙
D2)

    = D2
     由于D2成功恢复,所以P的恢复,只需要按照其计算方法就可以得到了
第三种情况 Q与数据盘故障

   
某数据,暂记为D1与Q发生故障,那么可以通过如下计算来恢复它:

    D1 = P⊕D0⊕D2⊕D3,  (因为P=D0⊕D1⊕D2⊕D3)

    因为D1成功恢复,所以Q的恢复,只需要按照其计算方法就可以得到了
第四种情况 两个数据盘故障

   
如果D1与D2发生故障,那么可以通过如下计算来恢复它:
    由D1= P⊕D0⊕D2⊕D3

    Q = (K0⊙D0)⊕(K1⊙D1)⊕(K2⊙D2)⊕(K3⊙
D3)

    = (K0⊙D0)⊕(K1⊙[P⊕D0⊕D2⊕D3])⊕(K2⊙D2)⊕(K3⊙
D3)

    = (K1⊙P)⊕[(K0⊕K1)⊙D0]⊕[(K1⊕K2)⊙D2]⊕[(K1⊕K3)⊙D3],
    因此,可以得到D2相关,并且不包含D1的表达式:

    (K1⊕K2)⊙D2= Q⊕(K1⊙P)⊕[(K0⊕K1)⊙D0] ⊕[(K1⊕K3)⊙
D3]

    D2={Q⊕(K1⊙P)⊕[(K0⊕K1)⊙D0] ⊕[(K1⊕K3)⊙D3]}/(K1⊕K2)
因为D2成功恢复,所以对于D1的恢复,就是相当简单计算了。
 
总结
 RAID6数据恢复算法比较复杂,RAID6发生故障时,恢复起来也是比较困难的,目前国内只有少数的几个大的数据恢复公司才有能力恢复RAID6,这些技术一般是比较保密的,兆柏工程师打破这种技术垄断,让RAID6算法和恢复方法公布于众。

 

相关文章