On-Line Data Reconstruction in Redundant Disk Arrays (CMU-CS-94-164)

There exists a wide variety of applications in which data availability must be continuous, that is, where the system is never taken off-line and any interruption in the accessibility of stored data causes significant disruption in the service provided by the application. Examples include on-line transaction processing systems such as airline reservation systems, and automated teller networks in banking systems. In addition, there exist many applications for which a high degree of data availability is important, but continuous operation is not required. An example is a research and development environment, where access to a centrally-stored CAD system is often necessary to make progress on a design project. These applications and many others mandate both high performance and high availability from their storage subsystems. Parity-based redundant disk arrays are very attractive storage alternatives for these systems because they offer both low cost per megabyte and high data reliability. Unfortunately such systems exhibit poor availability characteristics; their performance is severely degraded in the presence of a disk failure. This dissertation addresses the design of parity-based redundant disk arrays that offer dramatically higher levels of performance in the presence of failure than systems comprising the current state of the art. We consider two primary aspects of the failure-recovery problem: the organization of the data and redundancy in the array, and the algorithm used to recover the lost data. We apply results from combinatorial theory to generate data and parity organizations that minimize performance degradation during failure recovery by evenly distributing all failure-induced workload over a larger-than-minimal collection of disks. We develop a reconstruction algorithm that is able to absorb for failure-recovery essentially all of the array's bandwidth that is not absorbed by the application process(es). Additionally, we develop a design for a redundant disk array targeted at extremely high availability through extremely fast failure recovery. This development also demonstrates the generality of the presented techniques.