【什么是RAID】
RAID的概念描述在互聯(lián)網(wǎng)上比比皆是，用最簡(jiǎn)單的原理描述，就是在定義存儲(chǔ)方式時(shí)允許在一部分?jǐn)?shù)據(jù)缺失的情況下不影響全部數(shù)據(jù)，類似于通訊領(lǐng)域的糾錯(cuò)碼。不同的冗余模式形成了不同的RAID類別。
【單一冗余模型】
我們需要先描述僅具備一個(gè)磁盤(pán)冗余的RAID模型(思想同RAID3,RAID4,RAID5)。
假設(shè)現(xiàn)在有3頁(yè)空白的紙，用來(lái)記錄一些數(shù)字，為了更清晰地記錄，我們先將每頁(yè)白紙劃出相同大小的一些表格。再假設(shè)有一個(gè)可能：這3頁(yè)紙，特定情況下會(huì)有其中某一頁(yè)丟失。為了在上述設(shè)定情況保證這些數(shù)字能完整安全的記錄下來(lái)，我們要設(shè)計(jì)一些互相牽連的冗余關(guān)系。
如我們要記錄的數(shù)字序列是:3、14、28、4、98、88 。我們可以依次在第1頁(yè)和第2頁(yè)寫(xiě)要記錄的數(shù)字，在第3頁(yè)寫(xiě)上他們的和。如下圖所示：
根據(jù)上圖，可以很容易的分析出，不管這3頁(yè)中的哪一頁(yè)丟失，都可以通過(guò)另兩頁(yè)計(jì)算另一頁(yè)的數(shù)據(jù)來(lái)。很顯然，即使是超過(guò)3頁(yè)的情況，按上述方式設(shè)計(jì)記錄模式，也可以支持任意一頁(yè)記錄的丟失。
但這個(gè)模型卻不會(huì)在實(shí)際中應(yīng)用，原因來(lái)自于上圖的第三行數(shù)據(jù)：98+88 = 186 ，從這行的運(yùn)算來(lái)看，為了記錄整個(gè)一行數(shù)據(jù)的和，校驗(yàn)頁(yè)所用的空間要大于等于任何一個(gè)數(shù)據(jù)頁(yè)。其實(shí)，校驗(yàn)和的總?cè)萘恳扔谒袛?shù)據(jù)頁(yè)的總?cè)萘?，換個(gè)角度說(shuō)，如果記錄的是10頁(yè)數(shù)據(jù)，那么可能要用另外10頁(yè)的空間來(lái)記錄校驗(yàn)，這是完全沒(méi)有意義的方案(與其這樣，還不如所有數(shù)據(jù)抄兩份，即RAID1的模型)
所以，一些工程師開(kāi)始用別的算法代替加法，以減少校驗(yàn)和的總?cè)萘?，但算法的?shí)現(xiàn)效果需要與加法完全相同，同時(shí)運(yùn)算要足夠簡(jiǎn)單。最好的方案就是異或。
異或是基于位的運(yùn)算，首先其運(yùn)算性能非常好，無(wú)需更多的專門(mén)運(yùn)算器。同時(shí)異或算法完全滿足正運(yùn)算與逆運(yùn)算的完全映射(即，正運(yùn)算的結(jié)果唯一，同時(shí)這個(gè)正運(yùn)算的逆運(yùn)算結(jié)果也唯一。這個(gè)在數(shù)學(xué)上叫什么？恕筆者數(shù)學(xué)底子差，暫時(shí)這樣稱呼),滿足交換律和結(jié)合律。而且最重要的是，異或不會(huì)升位。
用異或算法改寫(xiě)后的存儲(chǔ)記錄如下：
可以很清晰得看到，第三行的校驗(yàn)和，不再是3個(gè)數(shù)字，而且不論多少個(gè)數(shù)據(jù)成員，用異或得到的校驗(yàn)和容量不會(huì)累加。
為了更好的概括，我們用"+"表示這個(gè)正向的校驗(yàn)運(yùn)算，用“-”表示其逆運(yùn)算。在我們最初的描述中，就表示數(shù)字的加減法，之后"+"表示異或，“-”也是異或(異或的逆運(yùn)算也是異或，所以運(yùn)算器簡(jiǎn)單，速度快)
假設(shè)有n個(gè)存儲(chǔ)成員，把每個(gè)存儲(chǔ)成員劃分成若干個(gè)存儲(chǔ)單元，其中n-1(數(shù)學(xué)減法，下面的Dn-1同理)個(gè)成員盤(pán)為數(shù)據(jù)，1個(gè)成員盤(pán)為校驗(yàn)。每個(gè)水平條帶上的校驗(yàn)關(guān)系如下：
D1 + D2 + D3 + ... +Dn-1 = P1
Dx = P1 - D1 - D2 - D3 - ... -Dn-1(D序列中排除Dx)
也就是：Dx = P1 + D1 + D2 + D3 +... +Dn-1(D序列中排除Dx)
【多次冗余模型】
上述單一冗余僅支持一個(gè)存儲(chǔ)成員的缺失，在實(shí)際中有可能需要更高的冗余性，則需要更進(jìn)一步對(duì)算法進(jìn)行改進(jìn)。
如果需要設(shè)計(jì)一種存儲(chǔ)模型，實(shí)現(xiàn)在缺失2個(gè)成員的情況下，存儲(chǔ)整體依然可以運(yùn)算完整，最好的數(shù)學(xué)模型恐怕就是二元一次方程了，形如下面方程組：
aX+bY=c
dX+eY=f。 其中a/d != b/e
上述方程式用到乘法與除法，同時(shí)，乘法與除法完全可逆，且滿足交換律、結(jié)合律與分配率。
還是在加法中遇到的困難，普通的數(shù)學(xué)乘法會(huì)導(dǎo)致校驗(yàn)容量的累加，所以不可取。有沒(méi)有一種乘除法符合我們的要求呢？有！---基于伽羅華域的乘除法。
數(shù)學(xué)概念是很抽象的，僅以GF(2^8)為例，我們?cè)O(shè)計(jì)一個(gè)有限循環(huán)域，域上僅有0-255這幾個(gè)數(shù)字，這些數(shù)字之間再設(shè)計(jì)一個(gè)完整的加減乘除運(yùn)算，其結(jié)果依然在這些數(shù)字中，而且運(yùn)算結(jié)果唯一，無(wú)二義性。
我們來(lái)設(shè)計(jì)一種算法，對(duì)于2，如果2的n次方大于某個(gè)值(本原多項(xiàng)式),則讓其對(duì)這個(gè)值(本原多項(xiàng)式)取余，確保又折回到0-255這個(gè)范圍內(nèi)，如果從2^0,2^1,2^2,,,直到2^255，按這個(gè)規(guī)律做運(yùn)算，得到的值均處于0-255范圍內(nèi)，且均不相等，這樣就形成了一個(gè)一對(duì)一的映射關(guān)系，同時(shí)滿足2的這些次冪與結(jié)果之間就乘法/除法的運(yùn)算規(guī)律(具體理論需參考群、環(huán)、域、有限域等數(shù)學(xué)理論)。
在GF(2^8)上，有16個(gè)滿足條件的本原多項(xiàng)式，分別如下：
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的本原多項(xiàng)式，意思是2的n次方如果大于0x11D，就對(duì)于做xor的取余運(yùn)算，確保結(jié)果小于0x256，這樣就可以算出2^0到2^255之間的所有數(shù)值。
GF(2^8)上的加減法同樣是異或算法(xor)。
GF(2^8)上的乘法即多項(xiàng)式乘法，但依然要對(duì)本原多項(xiàng)式取xor余，在算法設(shè)計(jì)上，有多種計(jì)算方式，但在GF(2^8)上，最快的推薦方法是查表法，只需事先計(jì)算好所有的0~255 分別乘以 0~255的值，生成65536個(gè)值的表格，計(jì)算時(shí)直接查表即可。也有使用對(duì)數(shù)查表法，使乘法轉(zhuǎn)變?yōu)榧臃ㄟM(jìn)行運(yùn)算的，需要查表和加法結(jié)合使用。
GF(2^8)上的除法可轉(zhuǎn)換為對(duì)其逆元的乘法，即a 除以 d，假設(shè)d對(duì)應(yīng)于(x的m次冪)，那找出對(duì)應(yīng)(x的255-m次冪)的值d',a除以d，即等于a乘以d'。
【RAID6】
在，加減乘除都確定后，2元一次方程組就可以求解了。所以，一個(gè)以此原理生成的RAID的結(jié)構(gòu)設(shè)計(jì)大致如下圖(以5塊盤(pán)為例，P為第一重校驗(yàn)，Q為第二重校驗(yàn)，xn為數(shù)據(jù))：
之所以P和Q螺旋式循環(huán)分布，是為了使所有磁盤(pán)負(fù)載均衡，如果不好理解，可以把P和Q單獨(dú)放在一列中，算法的意義是相同的。
再重復(fù)一下，下面提及的+、-、*、/運(yùn)算都是指基于GF(2^8)上的加、減、乘、除
P值等于同一行(條帶)上的所有單元相加的和?；蛘呖梢岳斫鉃?與每個(gè)單元相乘后的累加和，如第一個(gè)條帶的P：
P= x1+x2+x3 也就是P=1*x1 + 1*x2 + 1*x3
在GF(2^8)上，每個(gè)多項(xiàng)式對(duì)應(yīng)一個(gè)0~255的值，即d0對(duì)應(yīng)多項(xiàng)式X的0次冪，d1對(duì)應(yīng)多項(xiàng)式X的2次冪等，按多項(xiàng)式展開(kāi)，X為2進(jìn)制，故d0 = 1,d1 =2，d2=4 ,d3=8，等等，如下表所示：
返回RAID結(jié)構(gòu)圖中，Q值等于每個(gè)數(shù)值單元格乘以他們的相應(yīng)的dn再累加的結(jié)果，其中dn可約定，只需保證同一條帶的運(yùn)算中不重復(fù)出現(xiàn)dn即可，如第一行的Q可以為：
Q = d1* x1 + d2*x2 +d3*x3
這樣，對(duì)于每一行(條帶)，就可以保證任意2個(gè)單元丟失，都可以計(jì)算出來(lái)(為了明了，以下計(jì)算直接將減法改為加法)：
以第一行為例:
a) 如果P,Q均丟失，數(shù)據(jù)區(qū)不影響，x1,x2,x3均可正常讀寫(xiě)
b)如果xn丟失，根據(jù)P或Q都可計(jì)算出來(lái)(實(shí)際中，因P 的計(jì)算更快速，通常會(huì)使用P校驗(yàn)計(jì)算出丟失的 xn)
c)如果P,xn丟失，P值不做處理，假設(shè)丟失的是x2,根據(jù)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) 如果兩個(gè)x丟失，則可根據(jù)二元一次方式的標(biāo)準(zhǔn)解法進(jìn)行求解，假設(shè)丟失的是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
再根據(jù)P= x1 + x2 + x3求得x1，即完成所有數(shù)據(jù)的補(bǔ)缺。
