RAID: high-performance, reliable secondary storage

ABSTRACT

Disk arrays were proposed in the 1980s as a way to use parallelism between multiple disks to improve aggregate I/O performance. Today they appear in the product lines of most major computer manufacturers. This article gives a comprehensive overview of disk arrays and provides a framework in which to organize current and future work. First, the article introduces disk technology and reviews the driving forces that have popularized disk arrays: performance and reliability. It discusses the two architectural techniques used in disk arrays: striping across multiple disks to improve performance and redundancy to improve reliability. Next, the article describes seven disk array architectures, called RAID (Redundant Arrays of Inexpensive Disks) levels 0–6 and compares their performance, cost, and reliability. It goes on to discuss advanced research and implementation topics such as refining the basic RAID levels to improve performance and designing algorithms to maintain data consistency. Last, the article describes six disk array prototypes of products and discusses future opportunities for research, with an annotated bibliography disk array-related literature.

REFERENCES

• 1: AMDAHL, G.M. 1967. ValiditK, of the single processor approach to achievin'g large scale computing capabilities. In Proceedtngs of the AFIPS 1967 Sprzng Joint Computer Conference. Vol. 30. AFIPS, Washington, D.C., 483-485. Threepage paper that eloquently gives case for traditional computers by pointing out that performance improvement is limited by portion of the computation that is not improved.
• 2: BACCELLI, F. 1985. Two parallel queues created by arrivals with two demands. Tech Rep. 426, INRIA, Rocquencourt, France. Derives an exact solution for the two-server, M/G/1 fork-join queue.
• 3: BHIDE, A. AND DIAS, D. 1992. Raid architectures for OLTP. Tech. Rep. RC 17879 (#78489), IBM, Yorktown Heights, N.Y. Increases throughput for workloads emphasizing small, random write accesses in a redundant disk array by logging changes to parity for efficient application later. Parity changes are logged onto a separate disk which must be externally sorted before application to the disk array's parity.
• 4: Dina Bitton , Jim Gray, Disk Shadowing, Proceedings of the 14th International Conference on Very Large Data Bases, p.331-338, August 29-September 01, 1988
• 5: BURKU^RDT, W. AND MENON, J. 1993. Disk array storage system reliability. In the 23rd Annual International Symposium on Fault-Tolerant Computing. IEEE Computer Society, Washington, D.C., 432 441. Argnaes need for multiple error-correcting disk arrays; discusses how to use maximal-distance separable codes to protect against multiple errors in a space-efficient manner.
• 6: BUZEN, J. AND SHUM, W. C. 1986. I/O architecture in MVS/370 and MVS/XA. CMG Trans. 54 (Fall), 19-26. Overview of the MVS/370 and MVS/XA I/O architecture. Describes channel paths, storage directors, string controllers, rotational position sensing, static and dynamic reconnect.
• 7: Pei Cao , Swee Boon Lim , Shivakumar Venkataraman , John Wilkes, The TickerTAIP parallel RAID architecture, Proceedings of the 20th annual international symposium on Computer architecture, p.52-63, May 16-19, 1993, San Diego, California, United States
• 8: CHANDY, J. AND REDDY, A. L. N. 1993. Failure evaluation of disk array organizations. In Proceedmgs of the International Conference on Distrtbuted Computing Systems. IEEE Computer Society, Washington, D.C. Contrasts four previously described schemes for minimizing data reconstruction time in small (7 and 16 disks) redundant disk arrays: RAID 5 with a single spare disk, RAID 5 with a single spare whose space is distributed across all disks, a special case of Muntz and Lui's parity-clustering organization, and a method of dynamically converting a redundant data disk to a spare disk by merging two redundancy groups into one larger group. The second, distributed sparing, is generally preferred because of its performance and simplicity, but the Muntz scheme is better for minimal impact of user performance during recovery.
• 9: Peter M. Chen , Garth A. Gibson , Randy H. Katz , David A. Patterson, An evaluation of redundant arrays of disks using an Amdahl 5890, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.74-85, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 10: Peter M. Chen , David A. Patterson, Maximizing performance in a striped disk array, Proceedings of the 17th annual international symposium on Computer Architecture, p.322-331, May 28-31, 1990, Seattle, Washington, United States
• 11: C~tEN, S. AND TOWSLE~, D. 1991. A queuemg analysis of RAID architectures. Tech. Rep. COINS Tech. Rep. 91-71, Dept. of Computer and Information Science, Univ of Mas~ sachusetts, Amherst, Mass Analytically models RAID leveI-1 and RAID level-5 disk arrays to compare their performance on small and large requests. Bounds are used to model the quemng and fork-join synchronization in RAID level-1 disk arrays. Small write requests in RAID level-5 disk arrays are handled by ignoring the fork-join synchromzatlon overhead. Large requests are modcled by using a single queue for all the disks m the disk array.
• 12: CHEN, P. M AND LEE, E.K. 1993 Striping in a RAID level-5 disk array Tech. Rep. CSE-TR- 181-93, Univ. of' Michigan, Ann Arbor, Mtch. Discusses how to choose striping unit for RAID level-5 disk arrays. Quantifies effect of writes and varying number of dmks
• 13: Peter M. Chen , Edward K. Lee , Ann L. Drapeau , Ken Lutz , Ethan L. Miller , Srinivasan Seshan , Ken Shirriff , David A. Patterson , Randy H. Katz, Performance and design evaluation of the RAID-II storage server, Distributed and Parallel Databases, v.2 n.3, p.243-260, July 1994 [doi>10.1007/BF01266330]
• 14: Ann L. Chervenak , Randy H. Katz, Performance of a disk array protype, ACM SIGMETRICS Performance Evaluation Review, v.19 n.1, p.188-197, May 1991
• 15: George Copeland , William Alexander , Ellen Boughter , Tom Keller, Data placement in Bubba, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.99-108, June 01-03, 1988, Chicago, Illinois, United States
• 16: A. L. Drapeau , K. W. Shirriff , J. H. Hartman , E. L. Miller , S. Seshan , R. H. Katz , K. Lutz , D. A. Patterson , E. K. Lee , P. M. Chen , G. A. Gibson, RAID-II: a high-bandwidth network file server, Proceedings of the 21ST annual international symposium on Computer architecture, p.234-244, April 18-21, 1994, Chicago, Illinois, United States
• 17: EMLICH, L. W. AND POLICH, H.D. 1989 VAXmm- PLUS, a fault manager mlplementatmn Dig. Tech. J. 8, (Feb.) Describes Digatal Equipment Corporation's tool for predicting and awfiding disk failures
• 18: FLATTO, L. ~D HAHN, S. 1984. Two parallel queues created by arrivals with two demands I}. SIAM J. Comput. 44, 5 (Oct.), 1041-1053, Derives an exact solutmn for the two-server, M/M/l, fork-join queue.
• 19: FRmDMAN, M. B 1983. DASD access patterns. In the 14th International Conference on Managemeat ond Performance Evaluatmn of Computer Systems Computer Measurement Group, 51 61 Looks at how much disk accesses are skewed toward particular disks in several transaction-processing sites.
• 20: Garth Alan Gibson, Redundant disk arrays: reliable, parallel secondary storage, University of California at Berkeley, Berkeley, CA, 1992
• 21: GIBSON, G. A., PATTERSON, R. H., AND SATYA- NARAYANAN, M. 1992. D~sk reads with DRAM latency In the 3rd Workshop on Workstatwn Operating Systems. IEEE Computer Society, Washing-ton, D.C. Proposes that apphcatmns give hints about their future file accesses so that the buffer cache can prefetch needed data and provide low-latency file access. The hints could be exploited also to improve cache management and dmk scheduling
• 22: Jim Gray , Bob Horst , Mark Walker, Parity striping of disc arrays: low-cost reliable storage with acceptable throughput, Proceedings of the sixteenth international conference on Very large databases, p.148-161, September 1990, Brisbane, Australia
• 23: Marshall Hall, Jr., Combinatorial theory (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1998
• 24: HEII)ELBERGER, P AND TRIVEDI, K.S. 1982. Qeuelag network models for parallel processing with asynchronous tasks. IEEE Trans Comput C- 3 l, 11 (Nov.), 1099-1109. Derives approximate solutions for queuing systems with forks but no joins.
• 25: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 26: 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
• 27: HOLLAND, M. GmsoN, G., AND SIEWlOREK, D. 1993 Fast, on-line failure recovery in redundant disk arrays. In Proceedings of the 23rd International Symposium on Fault Tolerant Computing IEEE Computer Society, Washington, D,C. ompares and contrasts two data reconstruction algorithms for disk arrays: "parallel stripe-oriented reconstruction" and "disk-oriented reconstruction." Presents an implementation of the disk-oriented algorithm and analyzes reconstruction performance of these algorithms, concluding that the disk-oriented algorithm is superior. Investigates the sensitivity of the reconstruction process to the size of the reconstruction umt and the amount of memory available for reconstruction.
• 28: Hui-I Hsiao , David J. DeWitt, Chained Declustering: A New Availability Strategy for Multiprocessor Database Machines, Proceedings of the Sixth International Conference on Data Engineering, p.456-465, February 05-09, 1990
• 29: KATZ, R.H. 1992. High perfbrmance networkand channel-based storage. Proc. IEEE 80, 8 (Aug.), 1238 1261. Presents overview of network-based storage systems. Reviews hardware and software trends in storage systems.
• 30: R. Katz , P. Chen , A. Drapeau , E. Lee , K. Lutz , E. Miller , S. Seshan , D. Patterson, RAID-II: Design and implementation of a large scale disk array controller, Proceeding of the 1993 symposium on Research on integrated systems, p.23-37, February 1993, Seattle, Washington, United States
• 31: M Y Kim, Synchronized disk interleaving, IEEE Transactions on Computers, v.35 n.11, p.978-988, Nov. 1986 [doi>10.1109/TC.1986.1676699]
• 32: Michelle Y. Kim , Asser N. Tantawi, Asynchronous Disk Interleaving: Approximating Access Delays, IEEE Transactions on Computers, v.40 n.7, p.801-810, July 1991 [doi>10.1109/12.83618]
• 33: KORNER, K. 1990. Intelligent caching for remote file service. In Proceedings of the Internatmnal Conference on Distributed Computing Systems. IEEE Computer Society, Washington, D.C., 220 226. Uses traces to generate hints based on the program running and the directory and name of files accessed. The file server uses the hints to pick a caching algorithm: LRU, MRU, none. Simulation showed significant benefits from intelligent caching but not from readahead which delayed demand requests since it was not preemptable.
• 34: David Kotz , Carla Schlatter Ellis, Practical prefetching techniques for parallel file systems, Proceedings of the first international conference on Parallel and distributed information systems, p.182-189, December 1991, Miami, Florida, United States
• 35: Edward K Lee , Randy H. Katz, An Analytic Performance Model of Disk Arrays And Its Application, University of California at Berkeley, Berkeley, CA, 1991
• 36: 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
• 37: Edward K. Lee , Randy H. Katz, An analytic performance model of disk arrays, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.98-109, May 10-14, 1993, Santa Clara, California, United States
• 38: Miron Livny , Setrag Khoshafian , Haran Boral, Multi-disk management algorithms, Proceedings of the 1987 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.69-77, May 11-14, 1987, Banff, Alberta, Canada
• 39: LOVERSO, S. J., ISMAN, M., AND NANOPOULOS, A. 1993. A Parallel file system for the CM-5. In Proceedings of the USENIX Summer Con/krence. USENIX Assoclatmn, Berkeley, Calif. A description of the I/O hardware and the file system of the massively parallel processor from Thinking Machines. Their RAID-3 disk array has excellent performance for large file accesses.
• 40: Manish Malhotra , Kishor S. Trivedi, Reliability analysis of redundant arrays of inexpensive disks, Journal of Parallel and Distributed Computing, v.17 n.1-2, p.146-151, Jan./Feb. 1993 [doi>10.1006/jpdc.1993.1013]
• 41: Jai Menon , Jim Cortney, The architecture of a fault-tolerant cached RAID controller, Proceedings of the 20th annual international symposium on Computer architecture, p.76-87, May 16-19, 1993, San Diego, California, United States
• 42: MENON, J., MATTSON, D., AND NO, S. 1991. Distributed sparing for improved performance of disk arrays. Tech Rep. RJ 7943, IBM, Almaden Research Center. Explores the use of an on-line spare disk in a redundant disk array analytically It examines multiple configurations, but fundamentally it distributes the spare's space over the whole array so that every disk is N/(N + 2) data, 1/(N + 2) parity, and 1/(N + 2) spare. This gives an extra 1/(N + 2) performance, but, more significantly, it distributes the recovery-write load (the reconstructed data) over all disks to shorten recovery time. The benefits, not surprisingly, are largest for small arrays.
• 43: Jai Menon , James Roche , Jim Kasson, Floating parity and data disk arrays, Journal of Parallel and Distributed Computing, v.17 n.1-2, p.129-139, Jan./Feb. 1993 [doi>10.1006/jpdc.1993.1011]
• 44: MERCHANT, A. AND Yu, P. 1992. Design and modeling of clustered RAID. In Proceedings of the International Symposium on Fault Tolerant Computing. IEEE Computer Society, Washington, D.C., 140 149. Presents an implementation of parity declustering, which the authors call "clustered RAID," based on random permutations. Its advantage is that it ~s able to derive a data mapping for any size disk array with any size parity stripe, and the corresponding disadvantage is that the computational requirements of the mapping algorithm are high compared to the block-design-based approaches. Analyzes response time and reconstruction time using this technique via an analytic model, and finds substantial benefits m bath.
• 45: MONTGOMERY SECURITIES 1991. RAID: A technology prosed for explosive growth. Tech. Rep. DJIA: 2902, Montgomery Securities, San Franmsco, Calif. Industry projections of market growth for RAID systems from 1990 to 1995.
• 46: 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
• 47: R. Nelson , A. N. Tantawi, Approximate Analysis of Fork/Join Synchronization in Parallel Queues, IEEE Transactions on Computers, v.37 n.6, p.739-743, June 1988 [doi>10.1109/12.2213]
• 48: S. W. Ng, Crosshatch disk array for improved reliability and performance, Proceedings of the 21ST annual international symposium on Computer architecture, p.255-264, April 18-21, 1994, Chicago, Illinois, United States
• 49: NG, S AND MATTSON, D. 1991 Maintaining good performance in disk arrays during failure via uniform parity group distribution. In Proceed- ,~gs of t}le 1st Internatmnal Symposium on High Performance Distrzbuted Computing. 260 269 Uses balanced, incomplete block designs to distribute the extra load from a failed disk equally among other disks in the array.
• 50: Cyril U. Orji , Jon A. Solworth, Doubly distorted mirrors, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.307-316, May 25-28, 1993, Washington, D.C., United States
• 51: David A. Patterson , John L. Hennessy, Computer organization & design: the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 52: 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
• 53: R. Hugo Patterson , Garth A. Gibson , M. Satyanarayanan, A status report on research in transparent informed prefetching, ACM SIGOPS Operating Systems Review, v.27 n.2, p.21-34, April 1993 [doi>10.1145/155848.155855]
• 54: PETERSON, E. W. AND WELDON, E. J. 1972. Error-Correcting Codes. 2nd ed. MIT Press, Cambridge, Mass. A general textbook on the mathematics of error-correcting codes.
• 55: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.1-15, October 13-16, 1991, Pacific Grove, California, United States
• 56: Kenneth Salem , Hector Garcia-Molina, Disk Striping, Proceedings of the Second International Conference on Data Engineering, p.336-342, February 05-07, 1986
• 57: SCHEUERMANN, P., WEIKUM, G., AND ZABBACK, P. 1991. Automatic tuning of data placement and load balancing in disk arrays. Database Systems for Next-Generation Applications: Principles and Practme. Describes heuristics for allocating files to disks to minimize disk skew.
• 58: SCHULZE, M., GIBSON, G. KATZ, R., AND PATTERSON, D. 1989. How reliable is a RAID, In Procedures of the IEEE Computer Society International Conference (COMPCON). IEEE, New York. Gives a reliability calculation for the electronics as well as the disks for RAIDS.
• 59: SELTZER, M. I., CHEN, P. M., AND OUSTERHOUT, J. K. 1990. Disk scheduling revisited. In Proceedings of the Winter 1990 USENIX Technical Conference. USENIX Association, Berkeley, Calif. 313-324. Reexamines the problem of how to efficiently schedule a large number of disk accesses when accounting for both seek and rotational positioning delays.
• 60: Daniel Stodolsky , Garth Gibson , Mark Holland, Parity logging overcoming the small write problem in redundant disk arrays, Proceedings of the 20th annual international symposium on Computer architecture, p.64-75, May 16-19, 1993, San Diego, California, United States
• 61: TAIT, C. D. AND DUCHAMP, D. 1991. Detection and exploitation of file working sets. In Proceedings of the International Conference on Distributed Computing Systems. IEEE Computer Society, Washington, D.C., 2 9. Dynamically builds and maintains program and data access trees to predict future file accesses. The current pattern is matched with previous trees to prefetch data and manage the local cache in a distributed file system. Trace-driven simulation shows reduced cache miss rates over a simple LRU algorithm.
• 62: WEIKUM, G. AND ZABBACK, P. 1992. Tuning of striping units in disk-array-based file systems. In Proceedings of the 2nd Internatzonal Workshop on Research Issues on Data Engineering: Transaction and Query Processing. IEEE Computer Society, Washington, D.C., 80 87. Proposes file-specific striping units instead of a single, global one for all files.
• 63: WILMOT, R. B. 1989. File usage patterns from SMF data: Highly skewed usage. In the 20th Internatwnal Conference on Management and Performance Evaluation of Computer Systems. Computer Measurement Group, 668-677. Reports on how files are accessed on four large data centers and finds that a small number of files account for most of all disk I/O.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Mass storage (e.g., magnetic, optical, RAID)
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

General Terms:
Design, Performance, Reliability

Keywords:
RAID, disk array, parallel I/O, redundancy, storage, striping