董春，施亮

0 引言

近年來網(wǎng)絡(luò)技術(shù)與半導(dǎo)體技術(shù)的飛速發(fā)展，對存儲(chǔ)設(shè)備的性能提出了越來越高的要求。1988年加州大學(xué)伯克利分校的Patterson.Gibson和Katz，提出了廉價(jià)磁盤冗余陣列技術(shù)（Raid），很好地解決這一問題。RAID磁盤陣列雖然種類眾多，但一個(gè)突出的局限性就是，無法容忍兩塊硬盤同時(shí)故障的情況發(fā)生，RAID6正是為了解決這個(gè)問題而誕生的。

樂觀的估計(jì)RAID6技術(shù)，將可靠性提高了1000倍以上。不過RAID6在計(jì)算校驗(yàn)數(shù)據(jù)時(shí)，需要消耗大量的CPU時(shí)間，為了提高RAID6的性能，設(shè)計(jì)了專門的硬件加速器來完成該操作，這也是本文的主要內(nèi)容。

RAID6松散的定義為當(dāng)多達(dá)兩個(gè)磁盤同時(shí)失效時(shí)，仍能保持?jǐn)?shù)據(jù)不丟失的磁盤陣列。只要能滿足以上要求的磁盤陣列都可以稱為RAID6，因此RAID6發(fā)展出多種形式。本文的 RAID6指基于 P+Q編碼的 RAID6，此種實(shí)現(xiàn)基于Reed-Solomon編碼理論。

1 RAID6編碼理論

Reed-Solomon編碼是歐文.里德(Irving Reed)和格斯.所羅門(Gus Solomon)于1960年發(fā)布的一種糾錯(cuò)編碼。他使用伽羅瓦域(GF)運(yùn)算法則，能提供在RAID6中Q校驗(yàn)數(shù)據(jù)的計(jì)算，并提供錯(cuò)誤恢復(fù)功能。

它是最大距離可分碼的一種類型，表示為 RS(n,k)，其中n表示每個(gè)碼字(codeword)符號的總數(shù)，k表示每個(gè)碼字中數(shù)據(jù)符號的總數(shù)，其中2t = n - k為每個(gè)碼字中校驗(yàn)符號總數(shù)，對于RAID6來說2t＝2，所以它能修復(fù)兩個(gè)磁盤損壞；假如符號(symbol)的長度為s，那么碼字的長度n=2^s – 1。

當(dāng)采用byte長度(8bit)為符號長度時(shí)，其最大碼字長度為n = 2^8–1=255，所以可以支持255個(gè)磁盤，其中253個(gè)為數(shù)據(jù)盤，剩下2個(gè)為校驗(yàn)盤。

里德－所羅門編碼算法基于伽羅瓦域運(yùn)算。伽羅瓦域的特點(diǎn)是域內(nèi)任意兩個(gè)元素運(yùn)算的結(jié)果仍然是該域內(nèi)的元素，伽羅瓦域加法和減法通過異或運(yùn)算來實(shí)現(xiàn)。伽羅瓦域乘法和除法運(yùn)算通過查找表來實(shí)現(xiàn)。

取符號長度為 s=8，生成多項(xiàng)式g(x)=x^8+x^4+x^3+x^2+1，可生成伽羅瓦域GF(2^8)，根據(jù)該生成多項(xiàng)式可得到伽羅瓦域的對數(shù)表和反對數(shù)表[5]。

伽羅瓦域域內(nèi)的乘法運(yùn)算通過以下方式實(shí)現(xiàn)：

圖1 伽羅瓦域乘法運(yùn)算示意圖

其中g(shù)flog與gfilog是查表運(yùn)算，這兩個(gè)表格在FPGA的Bolck RAM中，運(yùn)算時(shí)，當(dāng)Bolck RAM地址線有輸入時(shí)，在下個(gè)周期便可以輸出對應(yīng)地址的結(jié)果，乘法器實(shí)現(xiàn)方便。

伽羅瓦域運(yùn)算符號表示：⊕ GF域加法；? GF域乘法；÷ GF域除法；＋ 整數(shù)域加法。

2 RAID6校驗(yàn)算法

為了得到容許兩個(gè)磁盤損壞的數(shù)據(jù)恢復(fù)能力，我們需要計(jì)算P和Q兩個(gè)校驗(yàn)數(shù)據(jù)。

假設(shè)：m = RAID中所含的數(shù)據(jù)磁盤數(shù)目

n = RAID中磁盤的某個(gè)條帶

RAID6的操作可以劃分為以下八種不同的操作：

1.一個(gè)數(shù)據(jù)盤損壞

當(dāng)?shù)趚（0≤x≤m-1）個(gè)數(shù)據(jù)盤損壞，可以用剩余有效數(shù)據(jù)和校驗(yàn)數(shù)據(jù)P來恢復(fù)損壞的數(shù)據(jù)，類似RAID5的數(shù)據(jù)恢復(fù)算法，公式如下：

2.寫操作更新數(shù)據(jù)

當(dāng)更新第x個(gè)數(shù)據(jù)盤的數(shù)據(jù)時(shí)，校驗(yàn)數(shù)據(jù)P、Q需重新計(jì)算。首先將舊數(shù)據(jù)和舊校驗(yàn)讀出，和新數(shù)據(jù)一起計(jì)算得到新校驗(yàn)，然后將新數(shù)據(jù)和新校驗(yàn)寫入對應(yīng)的磁盤中，公式如下：

3.重建校驗(yàn)數(shù)據(jù)P

當(dāng)校驗(yàn)數(shù)據(jù)P損壞時(shí)，利用數(shù)據(jù)盤上的數(shù)據(jù)即可將其重建，公式如下：

4.重建校驗(yàn)數(shù)據(jù)Q

當(dāng)校驗(yàn)數(shù)據(jù)Q損壞時(shí)，利用數(shù)據(jù)盤上的數(shù)據(jù)即可將其重建，計(jì)算Q時(shí)，每個(gè)數(shù)據(jù)盤都要都要GF乘以一個(gè)對應(yīng)的常數(shù)然后相加，此常數(shù)可以通過查反對數(shù)表得到，公式如下：

5.重建校驗(yàn)數(shù)據(jù)P、Q

當(dāng)校驗(yàn)數(shù)據(jù)P、Q損壞時(shí)，所需要的運(yùn)算是前面兩種運(yùn)算的結(jié)合，公式如下：

6.Q與一個(gè)數(shù)據(jù)Dx損壞

當(dāng)Q與一個(gè)數(shù)據(jù)Dx損壞時(shí)，可以先由P和完好的數(shù)據(jù)計(jì)算出損壞的數(shù)據(jù)Dx，然后即可計(jì)算得到校驗(yàn)數(shù)據(jù)Q，公式如下[1]：

7.P與一個(gè)數(shù)據(jù)Dx損壞

當(dāng)P與一個(gè)數(shù)據(jù)Dx損壞時(shí)，應(yīng)先由剩余的完好數(shù)據(jù)計(jì)算出一中間值P’、Q’，由Q’和Q計(jì)算出損壞的數(shù)據(jù)Dx；然后由P’和Dx便可計(jì)算出損壞的校驗(yàn)數(shù)據(jù)P，公式如下[1]：

8.兩個(gè)數(shù)據(jù)Dx、Dy損壞

當(dāng)兩個(gè)數(shù)據(jù)Dx、Dy損壞時(shí)，解聯(lián)立方程組得損壞數(shù)據(jù)的計(jì)算公式如下[1]：

3 RAID6硬件實(shí)現(xiàn)

以上8種RAID6操作可通過下圖硬件結(jié)構(gòu)實(shí)現(xiàn)，由于篇幅有限，我們僅以第七種操作來說明其實(shí)現(xiàn)流程，其余情況類似。

下圖中模塊 XOR_BRAM、MUX_BRAM_A、MUX_BRAM_B、MUX_BRAM_C、MUX_BRAM_D 用FPGA的Block RAM實(shí)現(xiàn)，用作計(jì)算校驗(yàn)數(shù)據(jù)或數(shù)據(jù)恢復(fù)過程中暫存中間結(jié)果，模塊GF_MULT_A、GF_MULT_B、GF_MULT_C、GF_MULT_D為用Block RAM做查找表實(shí)現(xiàn)的伽羅瓦域乘法器單元，模塊PRAMA_A、PRAMA_B用于在第八種情況下計(jì)算系數(shù)A、B，為數(shù)眾多的多路選擇器用于在不同狀態(tài)下選擇不同的數(shù)據(jù)通路。

圖2 RAID6數(shù)據(jù)計(jì)算單元（8bit）

當(dāng)校驗(yàn)數(shù)據(jù)P與一個(gè)數(shù)據(jù)Dx丟失時(shí)RAID6的數(shù)據(jù)恢復(fù)流程如下，(a)、(b)表示兩種操作在本步中同時(shí)并行進(jìn)行：

1）(a)取第一個(gè)數(shù)據(jù)，寫入XOR_BRAM中。

(b)取第一個(gè)數(shù)據(jù)，寫入MUX_BRAM_A，數(shù)據(jù)經(jīng)GF_MULT_A后再次寫入

MUX_BRAM_A。

2)(a)取第二個(gè)數(shù)據(jù)，將其與XOR_BRAM的輸出異或的結(jié)果寫入XOR_BRAM。

(b)取第二個(gè)數(shù)據(jù)，寫入 MUX_BRAM_C，數(shù)據(jù)經(jīng)GF_MULT_B后與 MUX_BRAM_A輸出異或的結(jié)果寫入MUX_BRAM_B。

3)(a)取第三個(gè)數(shù)據(jù)，將其與XOR_BRAM的輸出異或的結(jié)果寫入XOR_BRAM。

(b)取第三個(gè)數(shù)據(jù)，寫入 MUX_BRAM_C，數(shù)據(jù)經(jīng)GF_MULT_B后與 MUX_BRAM_B輸出異或的結(jié)果寫入MUX_BRAM_B。

4)重復(fù)步驟三，當(dāng)m-1個(gè)完好數(shù)據(jù)取完后，兩個(gè)中間結(jié)果P’和Q’分別保存XOR_BRAM和MUX_BRAM_B中。

5)(b)取輸入數(shù)據(jù)Q，其與MUX_BRAM_B的輸出Q’異或后的值經(jīng)GF_MULT_D 后得到丟失數(shù)據(jù) Dx，將其寫入MUX_BRAM_D。

6)(a)MUX_BRAM_D的輸出Dx與XOR_BRAM的輸出P’異或的結(jié)果為校驗(yàn)數(shù)據(jù)P，將其寫入XOR_BRAM。

(b)將恢復(fù)的數(shù)據(jù)Dx從MUX_BRAM_D輸出。

7)(a)將恢復(fù)的校驗(yàn)數(shù)據(jù)P從XOR_BRAM輸出。

至此RAID的兩個(gè)丟失數(shù)據(jù)均得以恢復(fù)。

以上模塊只能處理一個(gè)字節(jié)的數(shù)據(jù)，四次例化本模塊可同時(shí)處理4個(gè)字節(jié)的數(shù)據(jù)。本硬件結(jié)構(gòu)在RAID6狀態(tài)機(jī)的控制之下動(dòng)作，通過控制各個(gè)多路選擇器來選擇不同的數(shù)據(jù)通路以實(shí)現(xiàn)不同的數(shù)據(jù)操作，RAID6狀態(tài)機(jī)的跳轉(zhuǎn)由狀態(tài)/控制寄存器控制，狀態(tài)/控制寄存器的初值由軟件設(shè)定。在FPGA內(nèi)例化一個(gè) PCI接口邏輯，將此硬件加速器以 PCI設(shè)備的形式掛在PCI總線上，通過DMA形式控制主機(jī)與加速器的數(shù)據(jù)傳輸。系統(tǒng)示意圖如下：

圖3 RAID6系統(tǒng)框圖

修改Linux RAID的設(shè)備驅(qū)動(dòng)程序，用對加速器的調(diào)用代替軟件的函數(shù)調(diào)用，用軟件填充加速器的狀態(tài)/控制寄存器來通知加速器將要進(jìn)行的工作。

與純軟件實(shí)現(xiàn)相比，軟硬件協(xié)同實(shí)現(xiàn)的RAID6系統(tǒng)CPU占用率降低了約40%-50%，處理速度提高了約3倍，這是因?yàn)榧铀倨鞣謸?dān)了CPU的計(jì)算任務(wù)，CPU可以去做其他的工作，CPU與加速器的工作可并行進(jìn)行。

4 結(jié)束語

近年來隨著Internet以及其他網(wǎng)絡(luò)的飛速發(fā)展，計(jì)算機(jī)CPU處理能力的快速增長，對信息存儲(chǔ)設(shè)備的容量和容錯(cuò)性能提出了空前的要求，而磁盤陣列作為一種高速、廉價(jià)、可靠、大容量的存儲(chǔ)技術(shù)得到了快速發(fā)展和廣泛應(yīng)用。充分利用通用處理器和可編程邏輯器件各自的特點(diǎn)，用軟硬件結(jié)合的方法實(shí)現(xiàn)RAID6系統(tǒng)，成本低，開發(fā)周期短，效果好。

[1]Peter Anvin H.“The Mathematics of RAID6”,Last updated 2 July 2008.

[2]Michael Gilroy，James Irvine，“RAID 6 Hardware Acceleration”,Field Programmable Logic and Applications,2006.FPL '06.International Conference on 28-30 Aug.2006.

[3]James S.Plank，“A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems”,Technical Report CS-96-332,Department of Computer Science University of Tennessee.

[4]Matt DiPaolo,“Hardware Accelerator for RAID6 Parity Generation / Data Recovery Controller with ECC and MIG DDR2 Controller”,May 2 .2007,Xilinx Corporation.

[5]Intel 80333 IO Processor Developer’s Manual,March.2005,Intel Corporation.