The TickerTAIP parallel RAID architecture

ABSTRACT

Traditional disk arrays have a centralized architecture, with a single controller through which all requests flow. Such a controller is a single point of failure, and its performance limits the maximum number of disks to which the array can scale. We describe TickerTAIP, a parallel architecture for disk arrays that distributes the controller functions across several loosely coupled processors. The result is better scalability, fault tolerance, and flexibility.This article presents the TickerTAIP architecture and an evaluation of its behavior. We demonstrate the feasibility by a working example, describe a family of distributed algorithms for calculating RAID parity, discuss techniques for establishing request atomicity, sequencing, and recovery, and evaluate the performance of the TickerTAIP design in both absolute terms and by comparison to a centralized RAID implementation. We also analyze the effects of including disk-level request-scheduling algorithms inside the array. We conclude that the Ticker TAIP architectural approach is feasible, useful, and effective.

REFERENCES

• 1: AT & T. 1989. In Umx System VAT& T C+ + language system release 2.0 selected readings. Select Code 307-144. AT & T, Indianapolis, In.
• 2: BARTLETT, J., BARTLETT, W., CARR, R., GARCIA, D., GRAY, J., HORST, R., JARDINE, R., LENOSKI, n., AND McGUIRE, D. 1990. Fault tolerance in Tandem computer systems Tech. Rep. 90.5, Tandem Computers, Cupertino, Calif.
• 3: BORAL, H. 1988. Parallelism and data management. Tech. Rep. ACA-ST-156-88, Microelectronics and Computer Technology Corporation, Austin, Tex.
• 4: 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
• 5: CLARK, B. E., LAWLOR, F. D., SCHMIDT-STUMPF, W. E., STEWART, T. J., AND TIMMS, G. D. JR. 1988. Parity spreading to enhance storage access. U.S. Patent 4,761,785; filed 12 June 1986; granted 2 August 1988.
• 6: 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
• 7: David J. DeWitt , Robert H. Gerber , Goetz Graefe , Michael L. Heytens , Krishna B. Kumar , M. Muralikrishna, GAMMA - A High Performance Dataflow Database Machine, Proceedings of the 12th International Conference on Very Large Data Bases, p.228-237, August 25-28, 1986
• 8: D. J. DeWitt , S. Ghanderaizadeh , D. Schneider, A performance analysis of the gamma database machine, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.350-360, June 01-03, 1988, Chicago, Illinois, United States
• 9: S. W. Dietrich , M. Brown , E. Cortes-Rello , S. Wunderlin, A practitioner's introduction to database performance benchmarks and measurements, The Computer Journal, v.35 n.4, p.322-331, Aug. 1992 [doi>10.1093/comjnl/35.4.322]
• 10: 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
• 11: DUNPHY, R. H. JR., WALSH, R., AND BOWERS, J.H. 1990. Disk drive memory. U.S. patent 4, 914, 656; filed 28 June 1988, granted 3 April 1990.
• 12: ENGLISH, R. M. AND STEPANOV, A A. 1992. Loge: A self-organizing storage device. In Proceedtngs of USENIX Winter'92 Technical Conference. USENIX Assoc., Berkeley Calif., 237 251.
• 13: 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
• 14: GRAY, J. 1988. A comparison of the Byzantine agreement problem and the transaction commit problem. Tech. Rep 88.6 Tandem Computers, Cupertino, Calif.
• 15: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 16: 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
• 17: HEWLETT-PACKARD. 1991. HP 97556, 97558, and 97560 5.25-inch SCSI Disk Drzves: Technical Munual. Part No. 5960 0115. Hewlett-Packard Company, Boise, Idaho
• 18: HEWLETT-PACKARD 1988b. HP 7936 and HP 7937 Dzsc Drives Operating- and Installation Manual. Part. No 07937-90902. Hewlett-Packard Company, Boise, Idaho.
• 19: 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
• 20: JACOBSEN, D. M. AND WILKES, J. 1991. Disk scheduling algorithms based on rotational position. Tech. Rep. HPL-CSP-91-7, Hewlett-Packard Laboratories, Pale Alto, Calif.
• 21: Butler W. Lampson, Atomic Transactions, Distributed Systems - Architecture and Implementation, An Advanced Course, p.246-265, January 1981
• 22: LAWLOR, F.D. 1981. Efficient mass storage parity recovery mechanism. In IBM Tech. D~sclos. Bull 24, 2 (July), 986 987.
• 23: Edward K Lee, Software and Performance Issues in the Implementation of a RAID, University of California at Berkeley, Berkeley, CA, 1990
• 24: Marshall K. McKusick , William N. Joy , Samuel J. Leffler , Robert S. Fabry, A fast file system for UNIX, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.181-197, Aug. 1984 [doi>10.1145/989.990]
• 25: 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
• 26: MENON, J AND KASSON, J. 1992. Methods for improved update performance of disk arrays, In Proceedings of 25th Internatmnal Conference on System Sciences. Vol. 1. IEEE, New York, 74 83.
• 27: MmLEB, E L. AND KATZ, R H 1991. Analyzing the I/O behavior of supercomputer applications In Digest of Papers, 11th IEEE Symposzum on Mass Storage Systems. IEEE, New York, 51 59
• 28: 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
• 29: Philip M. Neches, Hardware support for advanced data management systems, Computer, v.17 n.11, p.29-40, Nov. 1984 [doi>10.1109/MC.1984.1658998]
• 30: Ot,STERII()UT, J K 1990. Why aren't operating systems getting faster as fast as hardware? In Proceedings of USENIX Summer'90 Techmcol Conference. USENIX Assoc., Berkeley, Calif., 247 256
• 31: PAn,k, A AND BALASUBRAMANIAN, K. 1986 Providing fault tolerance in parallel secondary storage systems. Tech. Rep. CS-TR-057-86, Dept. of Computer Scmnce, Princeton Univ, Princeton, N J
• 32: PATrEI~ON, {) A., CHEN, m.. GIBSON, G. AND KATZ, R. H. 1989. Introduction to redundant arrays of inexpensive disks (RAID). In Sprzng COMPCON'89. IEEE, New York, 112 117
• 33: 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
• 34: Krzysztof Pawlikowski, Steady-state simulation of queueing processes: survey of problems and solutions, ACM Computing Surveys (CSUR), v.22 n.2, p.123-170, June 1990 [doi>10.1145/78919.78921]
• 35: PCI 1994 In PCI Spemf~catzon. Intel Corporatmn, Hillsboro, Or.
• 36: CORPORATE Perihelion Software Ltd., The Helios parallel operating system (revised ed.), Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1991
• 37: RUEMMLE~4, C. AND WILKES, J. 1993. UNIX disk access patterns. In Proceedings of W~nter 1993 USENL~ USENIX Assoc., Berkeley, CaliL, 405 420
• 38: Martin E. Schulze, Considerations in the Design of a RAID Prototype, University of California at Berkeley, Berkeley, CA, 1988
• 39: SCHULZE, M., GIBSON, G, KATZ, R., AND PATTERSON, D. 1989 How reliable is a RAID? In Spring COMPCON'89. IEEE, New York, 118-123.
• 40: SCSI. 1991. Secretariat, Computer and Business Equipment Manufacturers Association. Draft proposed American National Standard for information systems--Small Computer System Interface-2 (SCSI-2), Draft ANSI standard X3T9.2/86-109, 2 February 1991 (revision 10d).
• 41: SELTZER, M., CHEN, P., AXD OUSTERHOUT, J. 1990. Disk scheduhng revisited. In Proceedings of Winter 1990 USENIX Conference. USENIX Assoc., Berkeley, Calif., 313-323.
• 42: Kang G. Shin, HARTS: A Distributed Real-Time Architecture, Computer, v.24 n.5, p.25-35, May 1991 [doi>10.1109/2.76284]
• 43: Daniel P. Siewiorek , Robert S. Swarz, Reliable computer systems (2nd ed.): design and evaluation, Digital Press, Newton, MA, 1992
• 44: SLOAN, R.D. 1992. A practical implementation of the database machine--Teradata DBC/1012. In Proceedings of 25th International Con/~rence on System Sciences. Vol. 1. IEEE, New York, 320-327.
• 45: STONEBRAKER, M. 1989. Distributed RAID--a new multiple copy algorithm. Tech. Rep. UCB/ERL M89/56, Electronics Research Lab., Univ. of California, Berkeley, Calif.
• 46: WILKES, J. 1992. DataMesh research project~ phase 1. In USENIX Workshop on File Systems. USENIX Assoc., Berkeley, Calif., 63-69.
• 47: J. Wilkes, The DataMesh research project, Proceedings of the world transputer user group (WOTUG) conference on Transputing '91, p.547-553, May 1991, Sunnyvale, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.2 Input/Output Devices
          Subjects: Channels and controllers

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Secondary storage
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
RAID disk array, decentralized parity calculation, disk scheduling, distributed controller, fault tolerance, parallel controller, performance simulation