为基于XOR的RAID-6码设计的并行编解码算法

A Parallel Coding Algorithm for XOR-Based RAID-6 Codes

RAID-6被广泛应用于存储系统中对数据进行保护.其中基于XOR的RAID-6码具有计算复杂度低的优点,因而受到广泛的关注和应用.但是,这类编码的潜在并行能力还没有被充分地挖掘和发挥.分析了基于XOR的RAID-6码的编解码过程,把校验方程的计算分解为预计算和递归求解2个阶段,其中预计算阶段可以被并行执行.此外,还观察到多种RAID-6码具有z-turn性质——只要失效情况在该RAID-6码的容错能力范围内,就至少有1个校验方程只包含1个不可用的数据块.基于此,设计了一个并行的编解码算法EOPC(equation-oriented parallel coding),用以实现具有z-turn性质的基于XOR的RAID-6码的编解码过程.在RDP码和P-Code上的编解码实验表明,使用EOPC实现的编解码过程与传统串行实现方法相比,在编解码吞吐率上有超过50%的性能提升.

Inheriting from RAID-6codes to protect data against two simultaneous disk failures,XORbased RAID-6codes have low computational complexity due to only using exclusive-or operations to encode and decode,and they are extensively studied and employed in practice.But the potential parallelism of these codes have not yet been sufficiently explored.In this paper,we observe that for XOR-based RAID-6coding procedures,calculations of parity check equations can be decomposed into pre-calculating and recursive resolution phases.Moreover,these pre-calculating phases of equations can execute in parallel to obtain intermediate blocks that are further used to recursively resolve all missing blocks in a specific sequence.Based on this observation,we present a parallel coding algorithm,called EOPC,for XOR-based RAID-6codes with the z-turn property,where there exists at least one parity check equation having only one unavailable block under their fault tolerance.We further build EOPC based on two representative XOR-based RAID-6codes—RDP code and P-Code,to evaluate the effectiveness of EOPC.Experiment results show that EOPC approach outperforms the corresponding serialized approach by more than 50%in encoding/decoding throughput.