Flexible Usage of Redundancy in Disk Arrays

It is well known that dedicating one disk's worth of space in a disk array to parity check information can allow the array to tolerate a single failure. More recently, two possible ways of increasing that benefit through the use of additional redundant information have been demonstrated: the additional redundancy can be used to allow the array to tolerate more than one disk failure without the loss of information (multiple-fault tolerance ), or it can be used to speed up the reconstruction of a single failed disk and thus reduce the impact of on-line reconstruction on array performance (using a technique known as {parity declustering ). However, these two advantages could not be obtained simultaneously. In this paper we demonstrate for the first time how to divide the benefits of extra space for redundant information arbitrarily between increased fault tolerance and accelerated reconstruction of failed disks. In addition, we give general lower bounds on the space overhead required to protect information in a disk array by storing redundant information. These bounds widen the optimality of some known multiple-fault-tolerant data layouts. Received September 1997, and in final form October 1998.