IMPROVED PARITY-DECLUSTERED LAYOUTS FOR DISK ARRAYS

Recently, parity-declustered layouts have been studied as a tool for r educing the time needed to reconstruct a failed disk in a disk array. 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 hampere d by the dearth of effective, easily implemented constructions of BIBD s on large sets and by inefficiencies in some parity-distribution meth ods that create layouts that are larger than necessary. We make progre ss on these problems in several ways. In particular, we demonstrate ne w BIBD constructions that generalize some previous constructions and y ield simpler BIBDs that are optimally small in some cases, show how re laxing some of the balance constraints on data layouts leads to constr uctions of approximately-balanced layouts that greatly increase the nu mber of feasible layouts for large arrays, and give a new method for d istributing parity that produces smaller data layouts, resulting in ti ght bounds on the size of data layouts derived from BIBDs. Our results use a variety of algebraic, combinatorial, and graph theoretic techni ques, and together greatly increase the number of parity-declustered d ata layouts that are appropriate for use in large disk arrays. (C) 199 6 Academic Press, Inc.