Parity logging disk arrays

ABSTRACT

Parity-encoded redundant disk arrays provide highly reliable, cost-effective secondary storage with high performance for reads and large writes. Their performance on small writes, however, is much worse than mirrored disks—the traditional, highly reliable, but expensive organization for secondary storage. Unfortunately, small writes are a substantial portion of the I/O workload of many important, demanding applications such as on-line transaction processing. This paper presents parity logging, a novel solution to the small-write problem for redundant disk arrays. Parity logging applies journalling techniques to reduce substantially the cost of small writes. We provide detailed models of parity logging and competing schemes—mirroring, floating storage, and RAID level 5—and verify these models by simulation. Parity logging provides performance competitive with mirroring, but with capacity overhead close to the minimum offered by RAID level 5. Finally, parity logging can exploit data caching more effectively than all three alternative approaches.

REFERENCES

• 1: BHIDE, A, AND DIAS, D. 1992. RAID architectures for OLTP. Computer Science Research Report RC 17879, IBM Corp., Almaden, Cahf
• 2: Pei Cao , Swee Boon Lim , Shivakumar Venkataraman , John Wilkes, The TickerTAIP parallel RAID architecture, ACM SIGARCH Computer Architecture News, v.21 n.2, p.52-63, May 1993
• 3: 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
• 4: DISK/TREND, INc. 1994.1994 DISK/TREND Report. Disk Drive Arrays. DISK/TREND, Inc., Mountain View, Calif.
• 5: FEIGEL, C. 1994. Flash memory heads toward mainstream. Microprocess. Rep. 8, 7, 19-25.
• 6: Robert Geist , Stephen Daniel, A continuum of disk scheduling algorithms, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.77-92, Feb. 1987 [doi>10.1145/7351.8929]
• 7: Garth A. Gibson, Redundant disk arrays: reliable, parallel secondary storage, MIT Press, Cambridge, MA, 1992
• 8: Garth A. Gibson , David A. Patterson, Designing disk arrays for high data reliability, Journal of Parallel and Distributed Computing, v.17 n.1-2, p.4-27, Jan./Feb. 1993 [doi>10.1006/jpdc.1993.1002]
• 9: Mark Holland , Garth A. Gibson, Parity declustering for continuous operation in redundant disk arrays, ACM SIGPLAN Notices, v.27 n.9, p.23-35, Sept. 1992
• 10: IBM CORP. 1989. IBM 0661 Dtsk Drive Product Descr~ptwn, Model 370, First Edition, Low End Storage Products, 504/114-2. IBM Corp., Armonk, New York.
• 11: MENON, J. 1993. Performance of RAID5 disk arrays with read and write caching. Computer Science Res. Rep. RJ9485(83363). IBM Corp., Alamaden, Calif.
• 12: MENON, J., AND KASSON, J. 1992. Methods for improved update performance of disk arrays. In Proceedtngs of the Hawalt International Conference on System Sctences. IEEE Computer Society Press, Los Alamitos, Calif., vol. 1, 74-83.
• 13: Cyril U. Orji , Jon A. Solworth, Doubly distorted mirrors, ACM SIGMOD Record, v.22 n.2, p.307-316, June 1, 1993
• 14: John K. Ousterhout , Andrew R. Cherenson , Frederick Douglis , Michael N. Nelson , Brent B. Welch, The Sprite Network Operating System, Computer, v.21 n.2, p.23-36, February 1988 [doi>10.1109/2.16]
• 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: Christos A. Polyzois , Anupam Bhide , Daniel M. Dias, Disk Mirroring with Alternating Deferred Updates, Proceedings of the 19th International Conference on Very Large Data Bases, p.604-617, August 24-27, 1993
• 17: K. K. Ramakrishnan , Prabuddha Biswas , Ramakrishna Karedla, Analysis of file I/O traces in commercial computing environments, ACM SIGMETRICS Performance Evaluation Review, v.20 n.1, p.78-90, June 1992
• 18: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, ACM SIGOPS Operating Systems Review, v.25 n.5, p.1-15, Oct. 1991
• 19: Kenneth Salem , Hector Garcia-Molina, Disk Striping, Proceedings of the Second International Conference on Data Engineering, p.336-342, February 05-07, 1986
• 20: SC~ULZE, M. E., GmSON, G. A., KATZ, R. H., AND PATTERSON, D.A. 1989. How reliable is s RAID? In Proceedings of the 1989 IEEE Computer Society Internatwnal Conference. IEEE Computer Society Press, Los Alamitos, Calif., 118 123.
• 21: SEbTZ~R, M., CHEN, P., AND OUSTERHOUT, J. 1990. Disk scheduling revisited In Proceedings of the Winter 1990 USENIX Conference. USENIX Assoc., Berkeley, Calif., 313-324.
• 22: Jon A. Solworth , Cyril U. Orji, Write-only disk caches, ACM SIGMOD Record, v.19 n.2, p.123-132, Jun. 1990
• 23: Jon A. Solworth , Cyril U. Orji, Distorted mirrors, Proceedings of the first international conference on Parallel and distributed information systems, p.10-17, December 1991, Miami, Florida, United States
• 24: Daniel Stodolsky , Garth Gibson , Mark Holland, Parity logging overcoming the small write problem in redundant disk arrays, ACM SIGARCH Computer Architecture News, v.21 n.2, p.64-75, May 1993
• 25: STODOLSKY, D., HOLLAND M., COURTRICHT, W., AND GIBSON, G. 1994. Parity logging disk arrays. Computer Science Research CMU-CS-94-170, Carnegie Mellon Univ., Pittsburgh, Penn.
• 26: TPC 1989. The TPC-A Benchmark: A Standard Specifzcation. Transaction Processing Performance Council.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.5 Reliability, Testing, and Fault-Tolerance**
          Subjects: Redundant design**

General Terms:
Design, Performance, Reliability

Keywords:
RAID, disk arrays