Linux中RAID 6如何实现Q校验算法(linux,开发技术)

RAID即独立磁盘冗余阵列，简称为「磁盘阵列」，其实就是用多个独立的磁盘组成在一起形成一个大的磁盘系统，从而实现比单块磁盘更好的存储性能和更高的可靠性。

RAID 6概述

RAID 6是指带有两种分布存储的奇偶校验码（既P和Q）的独立硬盘结构。与RAID 5相比，RAID 6增加了第二个独立校验码（Q）信息块，两个独立的奇偶校验系统使用不同的算法，数据的可靠性非常高，即使两块硬盘同时失效也不会影响数据的使用，主要是用于要求数据绝对安全的场合。如下图： 上图中Q为RAID 6的第二个校验信息块，采用的是非常复杂的“伽罗华域”算法，稍后会讲到。

RAID 6的P校验概述

其实RAID 6的P校验和RAID 5的校验是一样的，都是采用的“异或”运算。异或运算符的原则就是相同为0，不同为1的。在RAID 5的环境中只能掉一块硬盘，但是RAID 6在RAID 5的基础上添加了Q校验，因此RAID 6支持同时掉两块盘。异或运算如下：

P=A+B+C=AxorBxorCA=P-B-C=PxorBxorC

注意：上述的加减法都是异或运算。

RAID 6的Q校验概述

说到Q校验就有点复杂了，它采用上面所提到的“伽罗华域”算法。“伽罗华域”实际上就是“0-255”的一个有限域GF(2^8)，在GF(2^8)内不管是是加、减、乘、除都不会超过这个范围。并且，加减法可逆，乘除法可逆，而且计算的值在GF(2^8)内是唯一的。注意：此处提到的加、减、乘、除法不是日常使用的加减乘除，而是“伽罗华域”内的运算。在GF(2^8)中，如果2的n次方大于某个值（本原多项式）就会对该值（本原多项式）取余，结果又会返回到GF(2^8)中。因此，保证了2^0到2^255的结果值在GF(2^8)内是唯一的。 在GF(2^8)中一共有16个本原多项式，分别如下：

1x8+x7+x6+x5+x4+x2+1111110101=0x1F52x8+x7+x6+x5+x2+x+1111100111=0x1E73x8+x7+x6+x3+x2+x+1111001111=0x1CF4x8+x7+x6+x+1111000011=0x1C35x8+x7+x5+x3+1110101001=0x1A96x8+x7+x3+x2+1110001101=0x18D7x8+x7+x2+x+1110000111=0x1878x8+x6+x5+x4+1101110001=0x1719x8+x6+x5+x3+1101101001=0x16910x8+x6+x5+x2+1101100101=0x16511x8+x6+x5+x+1101100011=0x16312x8+x6+x4+x3+x2+x+1101011111=0x15F13x8+x6+x3+x2+1101001101=0x14D14x8+x5+x3+x2+1100101101=0x12D15x8+x5+x3+x+1100101011=0x12B16x8+x4+x3+x2+1100011101=0x11D

RAID 6常用的本原多项式为0X11D，既上列中最后一个。Linux 环境中的RAID 6也是如此。 好了回到Q校验上，Q校验和P校验结合正好组成了一个二元一次方程，K1、K2、K3为GF(2^8)中多项式的数值。

P=A+B+CQ=A*K1+B*K2+C*K3

伽罗华域的乘除法运算

伽罗华域中的加减法也是异或运算，所以就不做详细解释了，重点解释一下乘除法。通过上面的Q校验知道Q校验的生成需要伽罗华域中的乘法运算，计算乘法运算是一件非常复杂的事情，最好的解决办法就是将GF(2^8)中所有多项式的值生成表格，通过查表得知乘法运算的值。

1、生成正表GFILOG

通过下表的方法生成正表GFILOG，注意：此表的本原多项式为0X11D。 如下：是正表GFILOG

2、生成反表GFLOG

有了正向变换表，要得到逆向表就很简单了，把正向中的表变换值做为索引，在把正向表中的索引作为值就OK了。如下表：

3、计算乘除法运算（查表法）

乘法：A*K1=GFILOG[(GFLOG[A]+GFLOG[K1])mod255];除法：A/K1=GFILOG[(GFLOG[A]-GFLOG[K1]+255)mod255];

现在知道了伽罗华域的乘除法，那么我们计算Q校验就方便了许多。

根据Q校验生成丢失的数据

当RAID 6中坏掉两块磁盘，那该如何生成丢失的数据呢？用RAID 6的一个条带举例说明。 1、如果某个条带中丢失的两块数据是P和Q，那么正好，数据没有丢失，正常提取即可。 2、如果某个条带中丢失的两块数据是P和A，那么可以根据Q校验计算出A的数据。

P=A*K1+B*K2+C*K3A*K1=P+B*K2+C*K3A=（P+B*K2+C*K3）/K1//注：K1可以同过查表获取

3、如果某个条带中丢失的两块数据是Q和A，那么可以根据校验P计算出A的数据。

P=A+B+CA=P+B+C

4、如果某个条带中丢失的两块数据是A和B，那么可以根据校验P和Q计算出A和B的数据。

P=A+B+CQ=A*K1+B*K2+C*K3A=P+B+CQ=(P+B+C)*K1+B*K2+C*K3Q=P*K1+B*K1+C*K1+B*K2+C*K3Q=P*K1+C*K1+C*K3+B*K1+B*K2Q+P*K1+C*K1+C*K3=(K1+K2)*BB=(Q+P*K1+C*K1+C*K3)/(K1+K2)

计算出B的值以后，再根据P校验和计算出A的值就容易很多了。

A=P+B+C

Linux环境下的RAID 6

根据前的内容已经知道RAID 6的大致原理了。因为伽罗华域的本原多项式有16种，因此RAID 6的种类有很多，再加上K值的不固定。因此计算某个RAID 6的Q校验值会变的很复杂。不过Linux环境下的RAID 6的K值经过测试，其值根据够成RAID 6阵列的磁盘数，从本原多项式0X11D的开始取（RAID 6总磁盘数 -2）个多项式的值作为K的值。