Declustered disk array architectures with optimal and near-optimal parallelism

ABSTRACT

This paper investigates the placement of data and parity on redundant disk arrays. Declustered organizations have been traditionally used to achieve fast reconstruction of a failed disk's contents. In previous work, Holland and Gibson identified six desirable properties for ideal layouts; however, no declustered layout satisfying all properties has been published in the literature. We present a complete, constructive characterization of the collection of ideal declustered layouts possessing all six properties. Given that ideal layouts exist only for a limited set of configurations, we also present two novel layout families. PRIME and RELPR can tolerate multiple failures in a wide variety of configurations with slight deviations from the ideal. Our simulation studies show that the new layouts provide excellent parallel access performance and reduced incremental loads during degraded operation, when compared with previously published layouts. For large accesses and under high loads, response times for the new layouts are typically smaller than those of previously published declustered layouts by a factor of 2.5.

REFERENCES

• 1: Guillermo A. Alvarez , Walter A. Burkhard , Flaviu Cristian, Tolerating multiple failures in RAID architectures with optimal storage and uniform declustering, Proceedings of the 24th annual international symposium on Computer architecture, p.62-72, June 01-04, 1997, Denver, Colorado, United States
• 2: G. Alvarez, W. Burkhard, L. Stockmeyer, and E Cristian. Declustered disk array architectures with optimal and near-optimal parallelism. CS98-576, UCSD, 1998. http : //www- cse. ucsd. edu /groups /gemini /papers. html.
• 3: M. Blaum , J. Brady , J. Bruck , J. Menon, EVENODD: an optimal scheme for tolerating double disk failures in RAID architectures, Proceedings of the 21ST annual international symposium on Computer architecture, p.245-254, April 18-21, 1994, Chicago, Illinois, United States
• 4: W. Burkhard and J. Menon. Disk array storage system reliability. In Proc. of the International Symposium on Fault-tolerant Computing, pages 432-41, 1993.
• 5: Peter M. Chen , Edward K. Lee, Striping in a RAID level 5 disk array, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.136-145, May 15-19, 1995, Ottawa, Ontario, Canada
• 6: William V. Courtright Ii , Garth Gibson , Mark Holland , Jim Zelenka, A Structured Approach to Redundant Disk Array Implementation, Proceedings of the 2nd International Computer Performance and Dependability Symposium (IPDS '96), p.11, September 04-06, 1996
• 7: 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
• 8: Garth A. Gibson , David F. Nagle , Khalil Amiri , Fay W. Chang , Eugene M. Feinberg , Howard Gobioff , Chen Lee , Berend Ozceri , Erik Riedel , David Rochberg , Jim Zelenka, File server scaling with network-attached secure disks, Proceedings of the 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.272-284, June 15-18, 1997, Seattle, Washington, United States
• 9: M. Hall. Combinatorial Theory. Wiley, New York, 1986.
• 10: H. Hanani. Balanced Incomplete Block Designs and Related Designs. Discrete Mathematics, 1975.
• 11: 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
• 12: Mark Calvin Holland, On-line data reconstruction in redundant disk arrays, Carnegie Mellon University, Pittsburgh, PA, 1994
• 13: Edward K. Lee , Randy H. Katz, Performance consequences of parity placement in disk arrays, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.190-199, April 08-11, 1991, Santa Clara, California, United States
• 14: 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
• 15: 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
• 16: Eric J. Schwabe , Ian M. Sutherland, Improved parity-declustered layouts for disk arrays, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.76-84, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181045]
• 17: Andrew Tomkins , R. Hugo Patterson , Garth Gibson, Informed multi-process prefetching and caching, Proceedings of the 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.100-114, June 15-18, 1997, Seattle, Washington, United States
• 18: Xuefeng Wu , Jie Li , Hisao Kameda, Reliability Analysis of Disk Array Organizations by Considering Uncorrectable Bit Errors, Proceedings of the 16th Symposium on Reliable Distributed Systems (SRDS '97), p.2, October 22-24, 1997

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Mass storage (e.g., magnetic, optical, RAID)

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Performance