Array codes have been widely employed in storage systems, such as Redundant Arrays of Inexpensive Disks (RAID). The row-diagonal parity (RDP) codes and EVENODD codes are two popular double-parity array codes. As the capacity of hard disks increases, better fault tolerance by using array codes with three or more parity disks is needed. Although many extensions of RDP codes and EVENODD codes have been proposed, the high decoding complexity is the main drawback of them. In this paper, we present a new construction for all families of EVENODD codes and RDP codes, and propose a unified form of them. Under this unified form, RDP codes can be treated as shortened codes of EVENODD codes. Moreover, an efficient decoding algorithm based on an LU factorization of Vandermonde matrix is proposed when the number of continuous surviving parity columns is no less than the number of erased information columns. The new decoding algorithm is faster than the existing algorithms when more than three information columns fail. The proposed efficient decoding algorithm is also applicable to other Vandermonde array codes. Thus the proposed MDS array code is practically very meaningful for storage systems that need higher reliability.
There are many follow-up studies on EVENODD codes @cite_4 and RDP codes @cite_19 along different directions, such as the extensions of fault tolerance @cite_21 @cite_1 @cite_16 , the improvement of repair problem @cite_24 @cite_17 @cite_8 @cite_6 and efficient decoding methods @cite_18 @cite_20 @cite_5 @cite_9 of their extensions.
@cite_18 @cite_4 @cite_8 @cite_9 @cite_21 @cite_1 @cite_6 @cite_24 @cite_19 @cite_5 @cite_16 @cite_20 @cite_17
2963877468 2008200179 2794738250 2147343704
Array codes are used widely in data storage systems such as redundant array of independent disks. The row-diagonal parity (RDP) codes and EVENODD codes are two popular double-parity array codes. The increasing capacity of hard disks demands better fault tolerance by using array codes with three or more parity disks. Although many extensions of RDP and EVENODD codes have been proposed, their main drawback is high decoding complexity. In this paper, we propose a unified form of RDP and EVENODD codes under which RDP codes can be treated as shortened EVENODD codes. Moreover, an efficient decoding algorithm based on an LU factorization of a Vandermonde matrix is proposed. The LU decoding method is applicable to all the erasure patterns of RDP and EVENODD codes with three parity columns. It is also applicable to the erasure decoding of RDP and EVENODD codes with more than three parity columns when the number of continuous surviving parity columns is no less than the number of erased information columns and the first parity column has not failed. The proposed efficient decoding algorithm is also applicable to other Vandermonde array codes, with less decoding complexity than that of the existing method. The current parallel storage systems use thousands of inexpensive disks to meet the storage requirement of applications. Data redundancy and or coding are used to enhance data availability, for instance, Row-diagonal parity (RDP) and EVENODD codes, which are widely used in RAID-6 storage systems, provide data availability with up to two disk failures. To reduce the probability of data unavailability, whenever a single disk fails, disk recovery will be carried out. We find that the conventional recovery schemes of RDP and EVENODD codes for a single failed disk only use one parity disk. However, there are two parity disks in the system, and both can be used for single disk failure recovery. In this article, we propose a hybrid recovery approach that uses both parities for single disk failure recovery, and we design efficient recovery schemes for RDP code (RDOR-RDP) and EVENODD code (RDOR-EVENODD). Our recovery scheme has the following attractive properties: (1) “read optimality” in the sense that our scheme issues the smallest number of disk reads to recover a single failed disk and it reduces approximately 1 4 of disk reads compared with conventional schemes; (2) “load balancing property” in that all surviving disks will be subjected to the same (or almost the same) amount of additional workload in rebuilding the failed disk. We carry out performance evaluation to quantify the merits of RDOR-RDP and RDOR-EVENODD on some widely used disks with DiskSim. The offline experimental results show that RDOR-RDP and RDOR-EVENODD outperform the conventional recovery schemes of RDP and EVENODD codes in terms of total recovery time and recovery workload on individual surviving disk. However, the improvements are less than the theoretical value (approximately 25p), as RDOR-RDP and RDOR-EVENODD change the disk access pattern from purely sequential to a more random one compared with their conventional schemes. EVENODD codes are binary array codes for correcting double disk failures in RAID-6 with asymptotically optimal encoding and decoding complexities. However, the update complexity of EVENODD is sub-optimal. We propose a new construction of binary maximum distance separable array codes, namely EVENODD+, such that the encoding, decoding, and update complexities of EVENODD+ are less than those of EVENODD in general. Moreover, EVENODD+ achieves asymptotically optimal update complexity. 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. >