Study On Structure-Optimizing Techniques For Fault-Tolerating Stroage Systems

The fault-tolerating technique, due to its major advantage of providing high data reliability, is becoming more and more important in modern storage systems. However, the fault-tolerating storage systems are still facing many challeges today. On the one hand, most of the erasure-correcting codes used by the fault-tolerating storage systems have performance defects, and also have code-length restrictions. On the other hand, the data redundancy inside the fault-tolerating storage systems incurs addtional overhead upon each write operation, and adversely impacts the write performance. To solve these critical issues, efforts must be paid to the studies on the methods to construct high performance erasure codes, methods to extend the lengths of the erasure codes, and methods to alleviate the write overhead and improve the write performance of the fault-tolerating storage systems.The most important performance metrics for an erasure code include the space efficiency, update complexity, and computational complexity. It is proved that, for a double-erasure-correcting code, each of the three metrics has a theoritically optimal bound. A new double-erasure-correcting code, named P-Code, is proposed. P-Code has attained the optimal bounds for all the three performance metrics. The encoding of P-Code is described in an intuitive label-based approach, making it very easy to be understood and implemented. Moreover, the structure of P-Code is so flexible that, exchanges of block labels inside each column, or between two columns, will not affect the erasure-correcting ability of P-Code.The Row-Diagonal Parity (RDP) code is a representative state-of-the-art double-erasure-correcting code. RDP has attained the optimal space efficiency and computational complexity, but failed to attain the optimal update complexity. A row-parity placement strategy for RDP is proposed. The strategy helps RDP to attain the optimal update complexity. The code-length restrictions of erasure codes incur restrictions to the disk/node numbers in the fault-tolerating storage systems. The lengths of horizontal codes can be easily extended by removing some data columns directly. However, the lengths of vertical codes can not be extended in this way, since each column inside the structures of vertical codes includes not only data blocks but also parity blocks. Tow length extending algorithms for vertical codes are proposed. Both of the algorithms can extend a vertical code to an arbitrary length, while keeping its erasure-correcting ability. Additinally, the vertical shortening algorithm for vertical codes is proposed. The algorithm can improve the computational performance and failure recovery speed of vertical codes, at the expense of their space-efficiency decreasion.In order to solve the write performance problem of the double-failure-tolerating RAID6 architecture, a log-based optimization scheme, called RAID6L, is proposed. RAID6L integrates a log disk into the traditional RAID6 architecture, and alleviates its write penalty by simplifying the processing steps to service a write request. On the other hand, RAID6L also guarantees that the accelerated RAID6 systems can still recover from double disk failures. Compared with the traditional RAID6 architecture, RAID6L significantly improves the write performance of the RAID6 systems, at the expense of minimal reliability losses.The Parity Logging scheme was originally proposed to boost the write performance of the XOR-based RAID5 systems. A method to generalize the Parity Logging scheme is proposed, making it applicable to any form of RAID systems. Detailed comparisons and extensive experiments are conducted between RAID6L and the generalized Parity Logging. The results show that, compared with the generalized Parity Logging, RAID6L is more advantageous to the performance promotion of the RAID6 systems.