35
北亞工程師詳解數據恢複中RAID6結構
【什麼是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：
```javascript
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，即完成所有數據的補缺。
本文出自 “張宇(數據恢複)” 博客，請務必保留此出處https://zhangyu.blog.51cto.com/197148/1134820
最後更新：2017-04-10 11:29:53