【什麼是RAID】
RAID的概念描述在網際網路上比比皆是，用最簡單的原理描述，就是在定義存儲方式時允許在一部分資料缺失的情況下不影響全部資料，類似于通訊領域的糾錯碼。不同的備援模式形成了不同的RAID類别。
【單一備援模型】
我們需要先描述僅具備一個磁盤備援的RAID模型(思想同RAID3,RAID4,RAID5)。
假設現在有3頁空白的紙，用來記錄一些數字，為了更清晰地記錄，我們先将每頁白紙劃出相同大小的一些表格。再假設有一個可能：這3頁紙，特定情況下會有其中某一頁丢失。為了在上述設定情況保證這些數字能完整安全的記錄下來，我們要設計一些互相牽連的備援關系。
如我們要記錄的數字序列是:3、14、28、4、98、88 。我們可以依次在第1頁和第2頁寫要記錄的數字，在第3頁寫上他們的和。如下圖所示：
<a href="http://zhangyu.blog.51cto.com/attachment/201302/17/197148_1361117941pPBz.png"></a>
根據上圖，可以很容易的分析出，不管這3頁中的哪一頁丢失，都可以通過另兩頁計算另一頁的資料來。很顯然，即使是超過3頁的情況，按上述方式設計記錄模式，也可以支援任意一頁記錄的丢失。
但這個模型卻不會在實際中應用，原因來自于上圖的第三行資料：98+88 = 186 ，從這行的運算來看，為了記錄整個一行資料的和，校驗頁所用的空間要大于等于任何一個資料頁。其實，校驗和的總容量要等于所有資料頁的總容量，換個角度說，如果記錄的是10頁資料，那麼可能要用另外10頁的空間來記錄校驗，這是完全沒有意義的方案(與其這樣，還不如所有資料抄兩份，即RAID1的模型)
是以，一些工程師開始用别的算法代替加法，以減少校驗和的總容量，但算法的實作效果需要與加法完全相同，同時運算要足夠簡單。最好的方案就是異或。
異或是基于位的運算，首先其運算性能非常好，無需更多的專門運算器。同時異或算法完全滿足正運算與逆運算的完全映射(即，正運算的結果唯一，同時這個正運算的逆運算結果也唯一。這個在數學上叫什麼？恕筆者數學底子差，暫時這樣稱呼),滿足交換律和結合律。而且最重要的是，異或不會升位。
用異或算法改寫後的存儲記錄如下：
<a href="http://zhangyu.blog.51cto.com/attachment/201302/17/197148_1361117941TNOp.png"></a>
可以很清晰得看到，第三行的校驗和，不再是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個滿足條件的本原多項式，分别如下：
<b>1 </b>x8+x7+x6+x5+x4+x2+1 1 1111 0101 = 0x1F5
<b>2 </b>x8+x7+x6+x5+x2+x+1 1 1110 0111 = 0x1E7
<b>3 </b>x8+x7+x6+x3+x2+x+1 1 1100 1111 = 0x1CF
<b>4 </b>x8+x7+x6+x+1 1 1100 0011 = 0x1C3
<b>5 </b>x8+x7+x5+x3+1 1 1010 1001 = 0x1A9
<b>6 </b>x8+x7+x3+x2+1 1 1000 1101 = 0x18D
<b>7 </b>x8+x7+x2+x+1 1 1000 0111 = 0x187
<b>8 </b>x8+x6+x5+x4+1 1 0111 0001 = 0x171
<b>9 </b>x8+x6+x5+x3+1 1 0110 1001 = 0x169
<b>10 </b>x8+x6+x5+x2+1 1 0110 0101 = 0x165
<b>11 </b>x8+x6+x5+x+1 1 0110 0011 = 0x163
<b>12 </b>x8+x6+x4+x3+x2+x+1 1 0101 1111 = 0x15F
<b>13 </b>x8+x6+x3+x2+1 1 0100 1101 = 0x14D
<b>14 </b>x8+x5+x3+x2+1 1 0010 1101 = 0x12D
<b>15 </b>x8+x5+x3+x+1 1 0010 1011 = 0x12B
<b>16 </b>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為資料)：
<a href="http://zhangyu.blog.51cto.com/attachment/201302/17/197148_1361117942WbEf.png"></a>
之是以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，等等，如下表所示：
<a href="http://zhangyu.blog.51cto.com/attachment/201302/17/197148_1361117959sqEs.png"></a>
傳回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：
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，即完成所有資料的補缺。
本文轉自 張宇 51CTO部落格，原文連結：http://blog.51cto.com/zhangyu/1134820，如需轉載請自行聯系原作者
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)