raid6的数学算法

netkisser

raid6允许两块磁盘同时失效，将数据从其它盘恢复出来。使用的数学基础是李德-所罗门算法，伽罗瓦域。
这里有一篇文章介绍了raid6的数学算法
http://ftp.kernel.org/pub/linux/kernel/people/hpa/raid6.pdf
如果地址失效，到这里下载
http://download.csdn.net/source/2037497

1. 在raid6中，需要计算两个因子P，Q，是这样计算的

D就是指的数据盘。 这里的“加”指的是xor，而“乘”是伽罗瓦乘。
g指generator，raid6中一般选择2，它的幂次方都是已知的。

2. 如果丢失一个数据盘和P盘，那么就需要从Q和其它数据盘进行恢复了。
假设丢失的数据盘是Dx，我们先令Dx={00}，代入(2)式，求出Qx，再观察

这里，x，Q，Qx都是已知的数。在伽罗瓦域中，加和减是一样的，都是xor，于是

这里就能求出丢失的数据盘Dx的数据了。

3. 如果丢失了两块数据盘Dx和Dy，可以这样计算，设Dx={00}，Dy={00}，得到Pxy，Qxy，再观察

这里，x,y,Pxy,P,Q，Qxy都是已知的值，用g(x)除(7)式，得到


加法和减法相同，都是xor，得


代入等式（6），得到



如果g (y-x) +{01} 不等于 0，两边就可以同除于它了，这要求g (y-x)不等于{01},这个是成立的，因为y不等于x，故可以得到Dx的值



进而得到Dy的值



通常在实际应用中，会先计算g的幂次表和log表，以加快执行速度。


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/93140/showart_2165869.html