基于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.