Row-Diagonal Parity for Double Disk Failure Correction

This paper introduces Row-Diagonal Parity (RDP), a new algorithm for protecting against double disk failures. 

Row-Diagonal Parity (RDP) is a new algorithm for protecting against double disk failures. It stores all data unencoded, and uses only exclusive-or operations to compute parity. RDP is provably optimal in computational complexity, both during construction and reconstruction. Like other algorithms, it is optimal in the amount of redundant information stored and accessed. RDP works within a single stripe of blocks of sizes normally used by file systems, databases and disk arrays. It can be utilized in a fixed (RAID-4) or rotated (RAID-5) parity placement style. It is possible to extend the algorithm to encompass multiple RAID-4 or RAID-5 disk arrays in a single RDP disk array. It is possible to add disks to an existing RDP array without recalculating parity or moving data. Implementation results show that RDP performance can be made nearly equal to single parity RAID-4 and RAID-5 performance. Best Paper Award.

In Proceedings of the USENIX Conference on File and Storage Technologies 2004 (FAST ’04)

Resources

A copy of the paper is attached to this posting. rdp-fast04.pdf