A Graph Theoretic Algorithm For Placing Data And Parity To Tolerate Two Disk Failures In Disk Array Systems

In recent years commercial Redundant Arrays of Inexpensive Disks (RAID) systems have become increasingly popular because of their enhanced I/O bandwidths, large capacities and low cost. However, the continued demand for larger capacities at low cost, has led to the use of larger arrays with increased probability of random disk failures. Hence the need for RAID systems to tolerate two or more random disk failures without sacrificing performance or storage space. In this paper, we devise a novel graph-theoretic method for placing data and parity in an array of N disks (N ≥ 3) to enable its recovery from any two random disk failures. We first provide an algorithm for the case when the number of disks N= P - 1, where P is a prime number, and then generalize the solution for any arbitrary N. We also determine the fraction of space used for storing parity in an array of W disks employing our algorithm, and show that this fraction has the optimal value of 2/N for all N = P - 1. For illustration, this fraction and the percentage of its difference from the optimal ratio are graphed for values of N between 5 and 255. Finally, we describe a method for determining the data-blocks from where the reconstruction of two failed disks can be started in such an array. © 2005 IEEE