Research On Erasure-coding Technologies For Disk Arrays

Data reliability has become the primary concern of most business and governmentorganizations. Unexpected data loss or corruption can sometime be seen as a catastrophicincident to these organizations. However, as today's storage systems grow in size andcomplexity, they are increasingly confronted with various disk errors, such as disk fail-ures, latent sector errors, and undetected disk errors. These disk errors can make storagesystems very unreliable. To solve this problem, disks employed by storage systems areoften organized into fault-tolerant disk arrays using redundancy technologies. Among theexisting redundancy technologies, multi-way mirroring technologies can be easily imple-mented, but require multi-fold additional storage overheads, resulting in very low storageefciency; in contrast, erasure-coding technologies can provide very high storage ef-ciency, and thus, have become very popular in both the academic and industry research.Then, this dissertation carries out a research study on several theoretical and methodolog-ical issues of erasure-coding technologies. The main contributions of this dissertation arelisted as follows:1. This dissertation carries out a study on one kind of lowest-density MDS codeswith2fault tolerance, called C-Codes, which both have the property of cyclicsymmetry and achieve the maximum length that lowest-density MDS codes canhave. This dissertation reveals the underlying connections between C-Codes (orquasi-C-Codes) and starters in group theory. Based on the obtained results, this dis-sertation gives the constructions of several families of C-Codes (or quasi-C-Codes).As a result, this dissertation solves, in a large part, the recent problem that how toconstruct C-Codes (or quasi-C-Codes) for RAID6of arbitrary size.2. This dissertation proposes a new kind of erasure codes with high fault tolerance,called GRID codes, which can be easily implemented in disk arrays, can providehigh performance, and can provide high storage efciency. As a result, this disser-tation efectively solves the problem that each of the existing erasure codes withhigh fault tolerance has some limitations on implementation complexity, perfor-mance, or storage efciency. Consequently, the designers of large-scale disk arrayscan make a better tradeof among implementation complexity, fault tolerance, per-formance, and storage efciency. 3. This dissertation proposes a new data reconstruction method that can detect andcorrect silent data corruptions in erasure-coded disk arrays using the error detectionability of MDS horizontal codes. Compared with the traditional metadata methodsof detecting silent data corruptions, this new method not only avoids storing someadditional metadata information, but also can detect more types of silent data cor-ruptions. Meanwhile, this new method extends the range of errors that currenterasure-coding technologies can tolerate.4. This dissertation proposes a new Disk Architecture with Composite Operation(DACO) specially to improve small-write performance in erasure-coded disk ar-rays. As a result, this dissertation efectively solves the problem that the existingmethods of improving small-write performance do not have the property of robust-ness because they cannot avoid the read-modify-write mode of updating paritiesin small-write operations. In contrast to the existing methods, DACO can providemore performance improvement in the case of an erasure code with higher faulttolerance.