Improved parity-declustered layouts for disk arrays

ABSTRACT

Recently, parity-declustered layouts have been studied as a tool for reducing the time needed to reconstruct a failed disk in a disk array [5, 9]. 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 general results and constructions for 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 •Demonstrate a new BIBD construction that generalizes some previous constructions and yields a simpler BIBD that is optimally small in some cases. •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. •Give a new method for distributing parity that produces smaller data layouts, resulting in tight bounds on the size of the data layouts derived from BIBDs. Our results use a variety of algebraic, combinatorial, and graph-theoretic techniques, and together greatly increase the number of parity-declustered data layouts that are appropriate for use in large disk arrays.

REFERENCES

• 1: R. C. Bose. "On the construction of balanced incomplete block designs." Ann. of Eugenics, Vol. 9, pp. 353-399, 1939.
• 2: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 3: G. A. Gibson , L. Hellerstein , R. M. Karp , D. A. Patterson, Failure correction techniques for large disk arrays, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.123-132, April 03-06, 1989, Boston, Massachusetts, United States
• 4: H. Hanani. "Balanced Incomplete Block Designs and Related Designs." Discrete Mathematics, Vol. 11, pp. 255- 369, 1975.
• 5: Mark Holland , Garth A. Gibson, Parity declustering for continuous operation in redundant disk arrays, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.23-35, October 12-15, 1992, Boston, Massachusetts, United States
• 6: M. Holland and G. A. Gibson. Personal communication, 1993.
• 7: Mark Holland , Garth A. Gibson , Daniel P. Siewiorek, Architectures and algorithms for on-line failure recovery in redundant disk arrays, Distributed and Parallel Databases, v.2 n.3, p.295-335, July 1994 [doi>10.1007/BF01266332]
• 8: N. Jacobson. Basic Algebra I. W.H. Freeman and Company, San Francisco, CA, 1974.
• 9: Richard R. Muntz , John C. S. Lui, Performance analysis of disk arrays under failure, Proceedings of the sixteenth international conference on Very large databases, p.162-173, September 1990, Brisbane, Australia
• 10: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

General Terms:
Design, Theory, Verification