基于FPGA的RAID6硬件加速器的實現

董春，施亮

0 引言

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

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

RAID6松散的定義為當多達兩個磁盤同時失效時，仍能保持數據不丟失的磁盤陣列。只要能滿足以上要求的磁盤陣列都可以稱為RAID6，因此RAID6發展出多種形式。本文的 RAID6指基于 P+Q編碼的 RAID6，此種實現基于Reed-Solomon編碼理論。

1 RAID6編碼理論

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

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

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

里德－所羅門編碼算法基于伽羅瓦域運算。伽羅瓦域的特點是域內任意兩個元素運算的結果仍然是該域內的元素，伽羅瓦域加法和減法通過異或運算來實現。伽羅瓦域乘法和除法運算通過查找表來實現。

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

伽羅瓦域域內的乘法運算通過以下方式實現：

圖1 伽羅瓦域乘法運算示意圖

其中gflog與gfilog是查表運算，這兩個表格在FPGA的Bolck RAM中，運算時，當Bolck RAM地址線有輸入時，在下個周期便可以輸出對應地址的結果，乘法器實現方便。

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

2 RAID6校驗算法

為了得到容許兩個磁盤損壞的數據恢復能力，我們需要計算P和Q兩個校驗數據。

假設：m = RAID中所含的數據磁盤數目

n = RAID中磁盤的某個條帶

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

1.一個數據盤損壞

當第x（0≤x≤m-1）個數據盤損壞，可以用剩余有效數據和校驗數據P來恢復損壞的數據，類似RAID5的數據恢復算法，公式如下：

2.寫操作更新數據

當更新第x個數據盤的數據時，校驗數據P、Q需重新計算。首先將舊數據和舊校驗讀出，和新數據一起計算得到新校驗，然后將新數據和新校驗寫入對應的磁盤中，公式如下：

3.重建校驗數據P

當校驗數據P損壞時，利用數據盤上的數據即可將其重建，公式如下：

4.重建校驗數據Q

當校驗數據Q損壞時，利用數據盤上的數據即可將其重建，計算Q時，每個數據盤都要都要GF乘以一個對應的常數然后相加，此常數可以通過查反對數表得到，公式如下：

5.重建校驗數據P、Q

當校驗數據P、Q損壞時，所需要的運算是前面兩種運算的結合，公式如下：

6.Q與一個數據Dx損壞

當Q與一個數據Dx損壞時，可以先由P和完好的數據計算出損壞的數據Dx，然后即可計算得到校驗數據Q，公式如下[1]：

7.P與一個數據Dx損壞

當P與一個數據Dx損壞時，應先由剩余的完好數據計算出一中間值P’、Q’，由Q’和Q計算出損壞的數據Dx；然后由P’和Dx便可計算出損壞的校驗數據P，公式如下[1]：

8.兩個數據Dx、Dy損壞

當兩個數據Dx、Dy損壞時，解聯立方程組得損壞數據的計算公式如下[1]：

3 RAID6硬件實現

以上8種RAID6操作可通過下圖硬件結構實現，由于篇幅有限，我們僅以第七種操作來說明其實現流程，其余情況類似。

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

圖2 RAID6數據計算單元（8bit）

當校驗數據P與一個數據Dx丟失時RAID6的數據恢復流程如下，(a)、(b)表示兩種操作在本步中同時并行進行：

1）(a)取第一個數據，寫入XOR_BRAM中。

(b)取第一個數據，寫入MUX_BRAM_A，數據經GF_MULT_A后再次寫入

MUX_BRAM_A。

2)(a)取第二個數據，將其與XOR_BRAM的輸出異或的結果寫入XOR_BRAM。

(b)取第二個數據，寫入 MUX_BRAM_C，數據經GF_MULT_B后與 MUX_BRAM_A輸出異或的結果寫入MUX_BRAM_B。

3)(a)取第三個數據，將其與XOR_BRAM的輸出異或的結果寫入XOR_BRAM。

(b)取第三個數據，寫入 MUX_BRAM_C，數據經GF_MULT_B后與 MUX_BRAM_B輸出異或的結果寫入MUX_BRAM_B。

4)重復步驟三，當m-1個完好數據取完后，兩個中間結果P’和Q’分別保存XOR_BRAM和MUX_BRAM_B中。

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

6)(a)MUX_BRAM_D的輸出Dx與XOR_BRAM的輸出P’異或的結果為校驗數據P，將其寫入XOR_BRAM。

(b)將恢復的數據Dx從MUX_BRAM_D輸出。

7)(a)將恢復的校驗數據P從XOR_BRAM輸出。

至此RAID的兩個丟失數據均得以恢復。

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

圖3 RAID6系統框圖

修改Linux RAID的設備驅動程序，用對加速器的調用代替軟件的函數調用，用軟件填充加速器的狀態/控制寄存器來通知加速器將要進行的工作。

與純軟件實現相比，軟硬件協同實現的RAID6系統CPU占用率降低了約40%-50%，處理速度提高了約3倍，這是因為加速器分擔了CPU的計算任務，CPU可以去做其他的工作，CPU與加速器的工作可并行進行。

4 結束語

近年來隨著Internet以及其他網絡的飛速發展，計算機CPU處理能力的快速增長，對信息存儲設備的容量和容錯性能提出了空前的要求，而磁盤陣列作為一種高速、廉價、可靠、大容量的存儲技術得到了快速發展和廣泛應用。充分利用通用處理器和可編程邏輯器件各自的特點，用軟硬件結合的方法實現RAID6系統，成本低，開發周期短，效果好。

[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.