Title :
EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures
Author :
Blaum, Mario ; Brady, Jim ; Bruck, Jehoshua ; Menon, Jai
Author_Institution :
IBM Almaden Res. Center, San Jose, CA, USA
fDate :
2/1/1995 12:00:00 AM
Abstract :
We present a novel method, that we call EVENODD, for tolerating up to two disk failures in RAID architectures. EVENODD employs the addition of only two redundant disks and consists of simple exclusive-OR computations. This redundant storage is optimal, in the sense that two failed disks cannot be retrieved with less than two redundant disks. A major advantage of EVENODD is that it only requires parity hardware, which is typically present in standard RAID-5 controllers. Hence, EVENODD can be implemented on standard RAID-5 controllers without any hardware changes. The most commonly used scheme that employes optimal redundant storage (i.e., two extra disks) is based on Reed-Solomon (RS) error-correcting codes. This scheme requires computation over finite fields and results in a more complex implementation. For example, we show that the complexity of implementing EVENODD in a disk array with 15 disks is about 50% of the one required when using the RS scheme. The new scheme is not limited to RAID architectures: it can be used in any system requiring large symbols and relatively short codes, for instance, in multitrack magnetic recording. To this end, we also present a decoding algorithm for one column (track) in error
Keywords :
Reed-Solomon codes; computational complexity; error correction codes; magnetic disc storage; EVENODD; RAID architectures; Reed-Solomon error-correcting codes; complexity; decoding algorithm; double disk failures toleration; exclusive-OR computations; multitrack magnetic recording; optimal redundant storage; parity hardware; redundant disks; Acceleration; Computer architecture; Decoding; Error correction codes; Galois fields; Hardware; Magnetic recording; Maintenance; Reed-Solomon codes; Writing;
Journal_Title :
Computers, IEEE Transactions on