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 2962858508 2337263547 2535559676 1639538057 2338020779 2507181206 2155418912 2158646168 2951303562
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. > The repair problem for an (n, k) error-correcting code calls for recovery of an unavailable coordinate of the codeword by downloading as little information as possible from a subset of the remaining coordinates. Using the terminology motivated by coding in distributed storage, we attempt to repair a failed node by accessing information stored on d helper nodes, where k &#x227C; d &#x227C; n &#x2013; 1, and using as little repair bandwidth as possible to recover the lost information.By the so-called cut-set bound (, 2010), the repair bandwidth of an (n,k = n &#x2013; r) MDS code using d helper nodes is at least dl (d + 1 &#x2013; k), where l is the size of the node. A number of constructions of MDS array codes have been shown to meet this bound with equality. In a related but separate line of work, Guruswami and Wootters (2016) studied repair of Reed-Solomon (RS) codes, showing that it is possible to perform repair using a smaller bandwidth than under the trivial approach. At the same time, their work as well as follow-up papers stopped short of constructing RS codes (or any scalar MDS codes) that meet the cut-set bound with equality, which has been an open problem in coding theory.In this work we present a solution to this problem, constructing RS codes of length n over the field of size (ql, l = exp((1 + o(1)n log n) that meet the cut-set bound. We also prove an almost matching lower bound on l, showing that super-exponential scaling is both necessary and sufficient for achieving the cut-set bound using linear repair schemes. More precisely, we prove that for scalar MDS codes (including the RS codes) to meet this bound, the sub-packetization l must satisfy l &#x227D; exp((1 + o(1))k log k). The generalized RDP codes are identified as the most practical and efficient triple-erasure correcting MDS (maximum-distance separable) codes, since they can encode optimally and support arbitrary code length. However, none of the existing decoding algorithms for these codes is adequate in that their decoding complexity leaves a relatively large room for improvement. In this letter, we present an improved decoding algorithm for the generalized RDP codes. Compared with the existing decoding algorithms, the proposed algorithm has a much lower decoding complexity, which is very close to the theoretical lower bound. Data placement scheme based on the generalized EVENODD array code was one of the most important choices for data storage systems to tolerate failures. The efficiency of the erasure code was directly related to the number of XOR operations during the encoding and decoding. We provided an improved decoding algorithm of the generalized EVENODD array code for correcting various triple node failures. It showed that the decoding complexity of the new algorithm was much lower than those of the existing comparable algorithm, thus it made the generalized EVENODD array code more efficiency in storage systems. In this work, we present a new upper bound on the minimum distance d of linear locally repairable codes (LRCs) with information locality and availability. The bound takes into account the code length n, dimension k, locality r, availability t, and field size q. We use tensor product codes to construct several families of LRCs with information locality, and then we extend the construction to design LRCs with information locality and availability. Some of these codes are shown to be optimal with respect to their minimum distance, achieving the new bound. Finally, we study the all-symbol locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and 4-cycle free regular low-density parity-check (LDPC) codes. We also investigate their optimality using the new bound. Binary maximum distance separable (MDS) array codes are widely used in storage systems. EVENODD code and row-diagonal parity (RDP) code are two well-known binary MDS array codes with two parity columns. The Blaum–Bruck–Vardy (BBV) code is an extension of the double-erasure-correcting EVENODD code. It is known that the BBV code is always MDS for three parity columns, and sufficient conditions for up to eight parity columns to be MDS are also known. However, the MDS condition for more than eight parity columns is an open problem since then. In this letter, we study the MDS condition of BBV code and give a sufficient MDS condition of the BBV code with more than eight parity columns. Given any r and n, we present an explicit construction of high-rate maximum distance separable (MDS) array codes that can optimally repair any d failed nodes from any h helper nodes for all h, 1 ≤ h ≤ r and d, k ≤ d ≤ n − h simultaneously. These codes can be constructed over any base field F as long as |F| ≥ sn; where s = lcm(1, 2, …, r). The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Our results present a significant improvement over earlier results which can only construct explicit codes for the case of at most 3 parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In the second part of the paper we give an explicit construction of Reed-Solomon codes with asymptotically optimal repair bandwidth. Linear erasure codes with local repairability are desirable for distributed data storage systems. An [n,k,d] linear code having all-symbol (r,δ)-locality, denoted as (r,δ)_a, is considered optimal if it has the actual highest minimum distance of any code of the given parameters n,k,r and δ. A minimum distance bound is given in . The existing results on the existence and the construction of optimal (r, δ)_a linear codes are limited to only two small regions within this special case, namely, i) m=0 and ii) m≥ (v+δ-1)>(δ-1) and δ=2, where m=n mod(r+δ-1) and v=k mod r. This paper investigates the properties and existence conditions for optimal (r,δ)_a linear codes with general r and δ. First, a structure theorem is derived for general optimal (r,δ)_a codes which helps illuminate some of their structure properties. Next, the entire problem space with arbitrary n, k, r and δ is divided into eight different cases (regions) with regard to the specific relations of these parameters. For two cases, it is rigorously proved that no (r,δ)_a linear code can achieve the minimum distance bound in . For four other cases the optimal (r,δ)_a codes are shown to exist over a field of size q≥( n k-1 ), deterministic constructions are proposed. Our new constructive algorithms not only cover more cases, but for the same cases where previous algorithms exist, the new constructions require a smaller field, which translates to potentially lower computational complexity. Our findings substantially enriches the knowledge on optimal (r,δ)_a linear codes, leaving only two cases in which the construction of optimal codes are not yet known. In distributed storage systems that use coding, the issue of minimizing the communication required to rebuild a storage node after a failure arises. We consider the problem of repairing an erased node in a distributed storage system that uses an EVENODD code. EVENODD codes are maximum distance separable (MDS) array codes that are used to protect against erasures, and only require XOR operations for encoding and decoding. We show that when there are two redundancy nodes, to rebuild one erased systematic node, only 3 4 of the information needs to be transmitted. Interestingly, in many cases, the required disk I O is also minimized. In distributed storage systems that use coding, the issue of minimizing the communication required to rebuild a storage node after a failure arises. We consider the problem of repairing an erased node in a distributed storage system that uses an EVENODD code. EVENODD codes are maximum distance separable (MDS) array codes that are used to protect against erasures, and only require XOR operations for encoding and decoding. We show that when there are two redundancy nodes, to rebuild one erased systematic node, only 3 4 of the information needs to be transmitted. Interestingly, in many cases, the required disk I O is also minimized.