Improved Parity-Declustered Layouts for Disk Arrays

Recently, parity-declustered layouts have been studied as a tool for reducing the time needed to reconstruct a failed disk in a disk array [6, 11]. Construction of such layouts for large disk arrays generally involves the use of a balanced incomplete block design (BIBD), a type of subset system over the set of disks. This research has been somewhat hampered by the dearth of effective, easily implemented constructions of BIBDs on large sets, and by inefficiencies in some parity-distribution methods that create layouts that are larger than necessary. We make progress on these problems in several ways. In particular, we ffl Demonstrate new BIBD constructions that generalize some previous constructions and yield simpler BIBDs that are optimally small in some cases. ffl Show how relaxing some of the balance constraints on data layouts leads to constructions of approximately-balanced layouts that greatly increase the number of feasible layouts for large arrays. ffl Give a new method for d..