Methods for Placing Data and Parity to Tolerate Two Disk Failures in Disk Arrays Using Complete Bipartite Graphs

摘要

Redundant Arrays of Independent Disks (RAID) systems have come into widespread use because of their enhanced I/O bandwidths, large capacities, and low cost. However, the increasing demand for larger array capacities at low cost has led to the use of arrays with larger number of disks that increases the likelihood of the concurrent occurrence of two or more random disk failures. Hence the need for RAID systems to tolerate two or more random disk failures without compromising disk utilization. In this paper, we present algorithms based on (a) the perfect 1-factorization of the complete bipartite graph, K_(p,p), for placing data and parity in arrays with P and (P - 1) disks, where P is a prime number, and (b) the perfect 1-factorization of K_(2p-1, 2p-1) for placing data and parity in arrays with 2P - 2 disks to enable their recovery from two random disk failures. In both cases the fraction of space used for storing parity in the disk array is optimal.