High performance fault-tolerant disk arrays
Eric J. Schwabe, Ian M. Sutherland · 1996
Processor speeds have been increasing at a significantly higher rate than disk speeds over the last decade. For applications that manipulate large data sets, I/O is thus becoming the performance bottleneck. The gap between processor and disk speeds can be narrowed by using an array of many disks operating in parallel, but using a large disk array reduces the mean time to data loss due to some disk crashing unrecoverably. Redundant Arrays of Independent Disks (RAID) can tolerate a certain level of disk failure, but have various drawbacks in the areas of performance, flexibility, and degree of fault tolerance. This dissertation provides a collection of techniques for achieving fault tolerance at low cost in arrays of disks. We particularly focus on disk arrays that must function continuously while managing redundancy and recovering from faults. Some of our work extends existing techniques for reducing the cost of fault tolerance to situations where they have not formerly been applicable, or reduces the cost of applying existing techniques. Other work gives new techniques that offer a higher degree of fault tolerance than was previously available at low cost, or provide new capabilities for fault-tolerant arrays. We have developed new classes of parity-declustered layouts for disk arrays that extend the technique of parity-declustering to a broader class of disk arrays. We have developed new algorithms for distributing redundant information in a disk array that distribute redundancy evenly over the disks in the array without increasing the size of the layout. We have developed a new coding scheme for disk arrays that tolerates multiple faults with near-optimal redundancy overhead and smaller performance penalty than has previously been possible. Finally, we have developed a type of parity-declustered layout that can be extended with new disks, and developed efficient algorithms for extending such layouts while the array continues to function.