Multi-level RAID for very large disk arrays

ABSTRACT

Very Large Disk Arrays - VLDAs have been developed to cope with the rapid increase in the volume of data generated requiring ultrareliable storage. Bricks or Storage Nodes - SNs holding a dozen or more disks are cost effective VLDA building blocks, since they cost less than traditional disk arrays. We utilize the Multilevel RAID - MRAID paradigm for protecting both SNs and their disks. Each SN is a k-disk-failure-tolerant kDFT array, while replication or l-node failure tolerance - lNFTs paradigm is applied at the SN level. For example, RAID1(M)/5(N) denotes a RAID1 at the higher level with a degree of replication M and each virtual disk is an SN configured as a RAID5 with N physical disks. We provide the data layout for RAID5/5 and RAID6/5 MRAIDs and give examples of updating data and recovering lost data. The former requires storage transactions to ensure the atomicity of storage updates. We discuss some weaknesses in reliability modeling in RAID5 and give examples of an asymptotic expansion method to compare the reliability of several MRAID organizations. We outline the reliability analysis of Markov chain models of VLDAs and briefly report on conclusions from simulation results. In Conclusions we outline areas for further research.

REFERENCES

• 1: Khalil Amiri , Garth A. Gibson , Richard Golding, Highly Concurrent Shared Storage, Proceedings of the The 20th International Conference on Distributed Computing Systems ( ICDCS 2000), p.298, April 10-13, 2000
• 2: Sung Hoon Baek , Bong Wan Kim , Eui Joung Joung , Chong Won Park, Reliability and performance of hierarchical RAID with multiple controllers, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.246-254, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384036]
• 3: Mario Blaum , Jim Brady , Jehoshua Bruck , Jai Menon, EVENODD: An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures, IEEE Transactions on Computers, v.44 n.2, p.192-202, February 1995 [doi>10.1109/12.364531 ]
• 4: M. Blaum, J. Brady, J. Bruck, J. Menon, and A. Vardy. "The EVENODD code and its generalizations", in High Performance Mass Storage and Parallel I/O: Technologies and Applications, H. Jin. T. Cortes, and R. Buyya (editors), Wiley 2002, pp. 187--205.
• 5: J. Chandy and A. L. N. Reddy. "Failure evaluation of disk array organizations", Proc. 13th Int'l Conf. on Distributed Computing Systems - ICDCS, Pittsburgh, PA, May 1993, pp. 319--326.
• 6: Peter M. Chen , Edward K. Lee , Garth A. Gibson , Randy H. Katz , David A. Patterson, RAID: high-performance, reliable secondary storage, ACM Computing Surveys (CSUR), v.26 n.2, p.145-185, June 1994 [doi>10.1145/176979.176981]
• 7: Peter Corbett , Bob English , Atul Goel , Tomislav Grcanac , Steven Kleiman , James Leong , Sunitha Sankar, Awarded Best Paper! -- Row-Diagonal Parity for Double Disk Failure Correction, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 8: P. A. Franaszek , J. R. Haritsa , J. T. Robinson , A. Thomasian, Distributed Concurrency Control Based on Limited Wait-Depth, IEEE Transactions on Parallel and Distributed Systems, v.4 n.11, p.1246-1264, November 1993 [doi>10.1109/71.250103 ]
• 9: J. Gray. "Storage bricks - Keynote speech", First USENIX Conf. on File and Storage Technologies - FAST'02, Monterey, CA, January 2002.
• 10: J. Gray. "Greetings from a filesystem user", Fourth USENIX_Conf. on File and Storage Technologies - FAST'02, San Francisco, CA, December 2005 (keynote speech).
• 11: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 12: Christopher R. Lumb , Richard Golding, D-SPTF: decentralized request distribution in brick-based storage systems, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 13: Arif Merchant , Philip S. Yu, Analytic Modeling of Clustered RAID with Mapping Based on Nearly Random Permutation, IEEE Transactions on Computers, v.45 n.3, p.367-373, March 1996 [doi>10.1109/12.485575 ]
• 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: Chan-Ik Park, Efficient Placement of Parity and Data to Tolerate Two Disk Failures in Disk Array Systems, IEEE Transactions on Parallel and Distributed Systems, v.6 n.11, p.1177-1184, November 1995 [doi>10.1109/71.476189 ]
• 16: 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
• 17: Erhard Rahm, Empirical performance evaluation of concurrency and coherency control protocols for database sharing systems, ACM Transactions on Database Systems (TODS), v.18 n.2, p.333-377, June 1993 [doi>10.1145/151634.151639]
• 18: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill, Inc., New York, NY, 1999
• 19: K. K. Rao, J. L. Hafner, and R. A. Golding. "Reliability for networked storage nodes", IBM Research Report RJ10358, Almaden Research Center, San Jose, CA, September 2005.
• 20: Daniel J. Rosenkrantz , Richard E. Stearns , Philip M. Lewis, II, System level concurrency control for distributed database systems, ACM Transactions on Database Systems (TODS), v.3 n.2, p.178-198, June 1978 [doi>10.1145/320251.320260]
• 21: Bernhard Seeger, An analysis of schedules for performing multi-page requests, Information Systems, v.21 n.5, p.387-407, July 1996 [doi>10.1016/0306-4379(96)84498-X ]
• 22: Alexander Thomasian , Jai Menon, RAID5 Performance with Distributed Sparing, IEEE Transactions on Parallel and Distributed Systems, v.8 n.6, p.640-657, June 1997 [doi>10.1109/71.595583 ]
• 23: Alexander Thomasian , Chunqi Han , Gang Fu , Chang Liu, A Performance Evaluation Tool for RAID Disk Arrays, Proceedings of the The Quantitative Evaluation of Systems, First International Conference on (QEST'04), p.8-17, September 27-30, 2004 [doi>10.1109/QEST.2004.2]
• 24: Alexander Thomasian, Reconstruct versus read-modify writes in RAID, Information Processing Letters, v.93 n.4, p.163-168, 28 February 2005 [doi>10.1016/j.ipl.2004.10.009]
• 25: A. Thomasian. "Access costs in clustered RAID disk arrays", The Computer Journal 48(11): 702--713 (November 2005).
• 26: A. Thomasian and J. Xu. "Reliability and performance of mirrored disk organizations", revised and resubmitted November 2005.
• 27: A. Thomasian. "Shortcut method for reliability comparisons in RAID", The Journal of Systems and Software, revised and resubmitted Fall 2005.
• 28: Donald F. Towsley , Shenze Chen , Shou-Pin Yu, Performance Analysis of a Fault Tolerant Mirrored Disk System, Proceedings of the 14th IFIP WG 7.3 International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.239-253, September 12-14, 1990
• 29: Qin Xin , Ethan L. Miller , Thomas Schwarz , Darrell D. E. Long , Scott A. Brandt , Witold Litwin, Reliability Mechanisms for Very Large Storage Systems, Proceedings of the 20 th IEEE/11 th NASA Goddard Conference on Mass Storage Systems and Technologies (MSS'03), p.146, April 07-10, 2003

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:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  E. Data
  E.5 FILES
      Subjects: Organization/structure

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.1 Project and People Management
          Subjects: Systems analysis and design

General Terms:
Design, Management, Performance, Reliability