An analytic behavior model for disk drives with readahead caches and request reordering

ABSTRACT

Modern disk drives read-ahead data and reorder incoming requests in a workload-dependent fashion. This improves their performance, but makes simple analytical models of them inadequate for performance prediction, capacity planning, workload balancing, and so on. To address this problem we have developed a new analytic model for disk drives that do readahead and request reordering. We did so by developing performance models of the disk drive components (queues, caches, and the disk mechanism) and a workload transformation technique for composing them. Our model includes the effects of workload-specific parameters such as request size and spatial locality. The result is capable of predicting the behavior of a variety of real-world devices to within 17% across a variety of workloads and disk drives.

REFERENCES

• 1: C. Adams, E. Gelenbe, and J. Vicard. An experimentally validated model of the paging drum. Acta Inforrnatica, 11:103 17, 1979.
• 2: Rakesh Barve , Elizabeth Shriver , Phillip B. Gibbons , Bruce K. Hillyer , Yossi Matias , Jeffrey Scott Vitter, Modeling and optimizing I/O throughput of multiple disks on a bus (summary), Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.264-265, June 22-26, 1998, Madison, Wisconsin, United States
• 3: A. L. Bastian. Cached DASD performance prediction and validation. Proc. 13th Intl Conf. on Mgmt. and Perf. Eval. of Comp. Sys. (CMG) (San Diego, CA), pages 174-7, M. Boksenbaum, G. W. Dodson, T. Moran, C. Smith, and H. P. Artis, editors, 14-17 Dec. 1982.
• 4: Anupam Bhide , Asit Dan , Daniel M. Dias, A Simple Analysis of the LRU Buffer Policy and Its Relationship to Buffer Warm-Up Transient, Proceedings of the Ninth International Conference on Data Engineering, p.125-133, April 19-23, 1993
• 5: G. Biagini. Evaluating I/O subsystem performance. Proc. Intl Conf. for the Meas. and Perf. Eval. of Comp. Sys. (CMG'86) (Las Vegas, NV), pages 299-306. Comp. Meas. Group, 1989.
• 6: Duane Buck , Mukesh Singhal, An analytic study of caching in computer systems, Journal of Parallel and Distributed Computing, v.32 n.2, p.205-214, Feb. 1, 1996 [doi>10.1006/jpdc.1996.0014]
• 7: Scott D. Carson , Sanjeev Setia, Analysis of the Periodic Update Write Policy for Disk Cache, IEEE Transactions on Software Engineering, v.18 n.1, p.44-54, January 1992 [doi>10.1109/32.120315]
• 8: Shenze Chen , Don Towsley, The design and evaluation of RAID 5 and parity striping disk array architectures, Journal of Parallel and Distributed Computing, v.17 n.1-2, p.58-74, Jan./Feb. 1993 [doi>10.1006/jpdc.1993.1005]
• 9: E. G. Coffman, Jr and M. Hofri. On tile expected perfbrmance of scanning disks. SIAM J. on Computing, 11(1):60- 70, Feb. 1982.
• 10: Gregory Robert Ganger , Yale N. Patt, System-oriented evaluation of i/o subsystem performance, 1995
• 11: R. Golding, E. Shriver, 2'. Sullivan, and J. Wilkes. Attributemanaged storage. Workshop on Modeling and Specification of I/O (San Antonio, TX), 26 Oct. 1995.
• 12: C. C. Gotlieb , G. H. MacEwen, Performance of Movable-Head Disk Storage Devices, Journal of the ACM (JACM), v.20 n.4, p.604-623, Oct. 1973 [doi>10.1145/321784.321789]
• 13: P. G. Hoel, S. C. Port, and C. J. Stone. Introduction to p#vbability theory. Houghton Mifflin Company, 1971.
• 14: Micha Hofri, Disk scheduling: FCFS vs.SSTF revisited, Communications of the ACM, v.23 n.11, p.645-653, Nov. 1980 [doi>10.1145/359024.359034]
• 15: A. Hospodor. Mechanical access time calculation. Advances in Information Storage Systems, 6:313-36, 1995.
• 16: D. M. Jacobson and J. Wilkes. Disk scheduling algorithms based on rotational position. Technical report HPL-CSP- 91--7. Itewlett-Packard Labs., Palo Alto, CA, 24 Feb. 1991, revised 1 Mar. 1991.
• 17: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 18: David Kotz , Song B Toh , Sriram Radhakrishnan, A Detailed Simulation Model of the HP 97560 Disk Drive, Dartmouth College, Hanover, NH, 1994
• 19: A. Kuratti, Performance analysis of the RAID 5 disk array, Proceedings of the International Computer Performance and Dependability Symposium on Computer Performance and Dependability Symposium, p.236, April 24-26, 1995
• 20: Stephen S. Lavenberg, Computer Performance Modeling Handbook, Academic Press, Inc., Orlando, FL, 1983
• 21: 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]
• 22: Spencer W. Ng, Improving Disk Performance Via Latency Reduction, IEEE Transactions on Computers, v.40 n.1, p.22-30, January 1991 [doi>10.1109/12.67317]
• 23: Walter C. Oney, Queueing Analysis of the Scan Policy for Moving-Head Disks, Journal of the ACM (JACM), v.22 n.3, p.397-412, July 1975 [doi>10.1145/321892.321902]
• 24: C. Ruemmler and J. Wilkes. UNIX disk access patterns. Proc. Winter 1993 USENIX (San Diego, CA), pages 405- 20, 25-29 Jan. 1993.
• 25: Chris Ruemmler , John Wilkes, An introduction to disk drive modeling, Computer, v.27 n.3, p.17-28, March 1994 [doi>10.1109/2.268881]
• 26: 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]
• 27: M. Seltzer, P. Chen, and J. Ousterhout. Disk scheduling revisited. Proc. Winter 1990 USENIX Conf. (Washington, DC), pages 313-23, 22----26 J#m. 1990.
• 28: Elizabeth Shriver, Performance modeling for realistic storage devices, New York University, New York, NY, 1997
• 29: Jon A. Solworth , Cyril U. Orji, Write-only disk caches, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.123-132, May 23-26, 1990, Atlantic City, New Jersey, United States
• 30: Toby J. Teorey , Tad B. Pinkerton, A comparative analysis of disk scheduling policies, Communications of the ACM, v.15 n.3, p.177-184, March 1972 [doi>10.1145/361268.361278]
• 31: F. Raab, editor. TPC benchmark C, Standard Specification Revision 3.0. Technical report. Transaction Processing Performance Council, 15 Feb. 1995.
• 32: Neil C. Wilhelm, An anomaly in disk scheduling: a comparison of FCFS and SSTF seek scheduling using an empirical model for disk accesses, Communications of the ACM, v.19 n.1, p.13-17, Jan. 1976 [doi>10.1145/359970.359977]
• 33: Neil C. Wilhelm, A General Model for the Performance of Disk Systems, Journal of the ACM (JACM), v.24 n.1, p.14-31, Jan. 1977 [doi>10.1145/321992.321994]
• 34: J. Wilkes. The Pantheon storage-system simulator. Technical Report HPL-SSP-95-14. Storage Systems Program, Hewlett-Packard Labs., Pato Alto, CA, 29 Dec. 1995.
• 35: Bruce L. Worthington, Aggressive centralized and distributed scheduling of disk requests, University of Michigan, Ann Arbor, MI, 1996
• 36: Bruce L. Worthington , Gregory R. Ganger , Yale N. Patt, Scheduling algorithms for modern disk drives, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.241-251, May 16-20, 1994, Nashville, Tennessee, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Performance