Parity declustering for continuous operation in redundant disk arrays

We describe and evaluate a strategy for declustering the parity encoding in a redundant disk array. This declustered parity organization balances cost against data rehability and performance during failure recovery in highly-available parity-based arrays for use in continuous-operation systems. It improves on standard parity organizations by reducing the additional load on surviving disks during the reconstruction of a failed disk's contents. This yields higher user throughput during recovery, and/or shorter recovery time. We first demonstrate a software implementation of declustered parity based on balanced incomplete and complete block designs. This implementation is then evaluated using a disk array simulator under a highly concurrent workload comprised of small user accesses. We show that declustered parity penalizes user response time while a disk is being repaired (before and during its recovery) less than comparable non-declustered (RAID 5) organizations without any penalty to user response time in the fault-free state. We then show that previously proposed modifications to a simple, single-sweep reconstruction algorithm further decrease user response times during recovery, but, contrary to previous suggestions, this may be achieved at the cost of slower recovery in many declustered parity arrays. This result arises from the simple model of disk access performance used in previous work, which did not consider throughput variations due to positioning delays.