Research On MDS Array Codes In Fault-tolerant Storage Systems

As modern storage systems have grown in size and complexity, disk(node) failures have become a type of daily events(during their service time). In order to prevent data loss caused by various component failures, storage systems usually employ two data protection approaches: multi-way mirroring and erasure coding. Multi-way mirroring is quite easy to implement, but it normally leads to very low storage efficiency. In contrast, erasure coding can neatly control the storage efficiency, and hence is adopted by more and more storage systems. Maximum distance separable(MDS) array codes are erasure codes that are mainly designed for storage systems. These codes can provide a prescribed number of fault tolerance with a minimum amount of redundancy, and the encoding and decoding procedures use only simple XOR and cyclic shift operations, thus have gained increasing attention in recent years. This dissertation has lucubrated on certain double(triple)-erasure correcting MDS array codes, and obtained the following significant achievements:1. RAID-6 is poised to replace RAID-5 as the dominant form of RAID architectures due to its ability to protect against double disk failures. Many double-erasure correcting MDS array codes are specially designed for RAID-6,but all of them have their own limitations. In this dissertation, we study a representative class of such codes — Blaum-Roth codes, and analyze their advantages and limitations, then present optimized encoding and decoding algorithms for them. The improved Blaum-Roth(IBR) codes have the following attractive properties: a) encoding complexity reaches the lower bound, b) decoding complexity approaches the lower bound, and c) can provide scalability with almost no performance loss. Compared with other MDS array codes that specially designed for RAID-6,IBR codes are more suitable for building highly efficient and scalable RAID-6 systems.2. Double-erasure correcting MDS array codes are elegant in that their encoding, decoding and update complexities all achieve the lower bound. However, existing such codes have either extremely strict code length limit or encoding rules without explicit geometric structure, which makes them somewhat impractical. To this end, we present a new family of double-erasure correcting, lowest density MDS array codes, called S(ymmetry)-Code.S-Code can encode, decode and update optimally, and its code length can be p or p- 1 with p being a prime number greater than 2. Moreover, S-Code requires less I/O cost than most existing lowest density MDS array codes during single erasure recovery, and the I/O cost of single erasure recovery approaches the lower bound when the code length is small.3. Lowest density MDS array codes have gained much attention in recent years due to their optimality in both encoding and update. However, most of the existing lowest density MDS array codes are double-erasure correcting codes. Although there are few exceptions,all of them have extremely strict constraints on the code length, which makes them impractical. For instance, the existing triple-erasure correcting lowest density MDS array codes all require the code length to be p(or p- 1), where p is a prime number such that 3|(p- 1) and2 is primitive in GF(p). To this end, this dissertation propose a practical family of lowest density MDS array codes that are capable of correcting both triple erasures and a single error combined with one erasure, called XI-Code. The decoding complexity of XI-Code either reaches or approaches the lower bound, depending on the specific erasure pattern. Moreover, the code length of XI-Code can be either p or p+1 with p being a prime number greater than 2. To the best of our knowledge, XI-Code is the most practical family of triple-erasure correcting lowest density MDS array codes.4. The generalized RDP codes are identified as the most practical and efficient strong systematic MDS 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. This dissertation studies the generalized RDP codes, then presents an improved decoding algorithm for correcting triple column erasures. Compared with the existing decoding algorithms, the proposed algorithm has a much lower decoding complexity, which is at most 8 percent higher than the theoretical lower bound when the code length is neither 10 nor 11.