A status report on research in transparent informed prefetching

ABSTRACT

This paper focuses on extending the power of caching and prefetching to reduce file read latencies by exploiting application level hints about future I/O accesses. We argue that systems that disclose high-level knowledge can transfer optimization information across module boundaries in a manner consistent with sound software engineering principles. Such Transparent Informed Prefetching (TIP) systems provide a technique for converting the high throughput of new technologies such as disk arrays and log-structured file systems into low latency for applications. Our preliminary experiments show that even without a high-throughput I/O subsystem TIP yields reduced execution time of up to 30% for applications obtaining data from a remote file server and up to 13% for applications obtaining data from a single local disk. These experiments indicate that greater performance benefits will be available when TIP is integrated with low level resource management policies and highly parallel I/O subsystems such as disk arrays.

REFERENCES

• 1: [Amdah167] Amdahl, G.M., "Validity of the single processor approach to achieving large scale computing capabilities," Proc. AFIPS 1967 Spring Joint Computer Conference, V. 30, Atlantic City, New Jersey, April 1967, pp. 483- 485.
• 2: Mary G. Baker , John H. Hartman , Michael D. Kupfer , Ken W. Shirriff , John K. Ousterhout, Measurements of a distributed file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.198-212, October 13-16, 1991, Pacific Grove, California, United States
• 3: [Cate92] Cate, V., "Alex--A Global Filesystem," Proceedings of the Usenix File Systems Workshop, Ann Arbor, MI, May 1992, pp. 1-11.
• 4: [Chou85] Chou, H.T., DeWitt, D.J., "An Evaluation of Buffer Management Strategies for Relational Database Systems," Proc. of the 11th Int. Conf. on Very Large Data Bases, Stockholm, 1985, pp. 127-141.
• 5: D. W. Cornell , Ph.S. Yu, Integration of buffer management and query optimization in relational database environment, Proceedings of the 15th international conference on Very large data bases, p.247-255, July 1989, Amsterdam, The Netherlands
• 6: R. J. Feiertag , E. I. Organick, The Multics Input/Output system, Proceedings of the third ACM symposium on Operating systems principles, p.35-41, October 18-20, 1971, Palo Alto, California, United States [doi>10.1145/800212.806497]
• 7: Garth Alan Gibson, Redundant disk arrays: reliable, parallel secondary storage, University of California at Berkeley, Berkeley, CA, 1992
• 8: Andrew S. Grimshaw , Edmond C. Loyot, Jr., ELFS: Object-Oriented Extensible File Systems, University of Virginia, Charlottesville, VA, 1991
• 9: M Y Kim, Synchronized Disk Interleaving, IEEE Transactions on Computers, v.35 n.11, p.978-988, November 1986 [doi>10.1109/TC.1986.1676699]
• 10: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• 11: [Korner90] Korner, K., "Intelligent Caching for Remote File Service, Proc. of the Tenth Int. Conf. on Distributed Computing Systems, 1990, pp. 220-226.
• 12: 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
• 13: 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
• 14: 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]
• 15: Ethan L. Miller, Input/Output Behavior of Supercomputing Application, University of California at Berkeley, Berkeley, CA, 1992
• 16: [Mummert92] Mummert, L., Satyanarayanan, M., "Efficient and Portable File Reference Tracing in a Distributed Workstation Environment," Carnegie Mellon University, manuscript in preparation.
• 17: Michael N. Nelson , Brent B. Welch , John K. Ousterhout, Caching in the Sprite network file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.134-154, Feb. 1988 [doi>10.1145/35037.42183]
• 18: Raymond Ng , Christos Faloutsos , Timos Sellis, Flexible buffer allocation based on marginal gains, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.387-396, May 29-31, 1991, Denver, Colorado, United States
• 19: John K. Ousterhout , Hervé Da Costa , David Harrison , John A. Kunze , Mike Kupfer , James G. Thompson, A trace-driven analysis of the UNIX 4.2 BSD file system, Proceedings of the tenth ACM symposium on Operating systems principles, p.15-24, December 1985, Orcas Island, Washington, United States
• 20: John Ousterhout , Fred Douglis, Beating the I/O bottleneck: a case for log-structured file systems, ACM SIGOPS Operating Systems Review, v.23 n.1, p.11-28, Jan. 1989 [doi>10.1145/65762.65765]
• 21: [Palmer91] Palmer, M.L., Zdonik, S.B., "FIDO: A Cache that Learns to Fetch," Brown University Technical Report CS-90-15, 1991.
• 22: 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
• 23: A. L. Reddy , P. Banerjee, An Evaluation of Multiple-Disk I/O Systems, IEEE Transactions on Computers, v.38 n.12, p.1680-1690, December 1989 [doi>10.1109/12.40846]
• 24: 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
• 25: Giovanni Maria Sacco , Mario Schkolnick, A Mechanism for Managing the Buffer Pool in a Relational Database System Using the Hot Set Model, Proceedings of the 8th International Conference on Very Large Data Bases, p.257-262, September 08-10, 1982
• 26: Kenneth Salem , Hector Garcia-Molina, Disk Striping, Proceedings of the Second International Conference on Data Engineering, p.336-342, February 05-07, 1986
• 27: M. Satyanarayanan , John H. Howard , David A. Nichols , Robert N. Sidebotham , Alfred Z. Spector , Michael J. West, The ITC distributed file system: principles and design, Proceedings of the tenth ACM symposium on Operating systems principles, p.35-50, December 1985, Orcas Island, Washington, United States
• 28: Mahadev Satyanarayanan , James J. Kistler , Puneet Kumar , Maria E. Okasaki , Ellen H. Siegel , David C. Steere, Coda: A Highly Available File System for a Distributed Workstation Environment, IEEE Transactions on Computers, v.39 n.4, p.447-459, April 1990 [doi>10.1109/12.54838]
• 29: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 30: [Seltzer90] Seltzer, M.I., Chen, P.M., Ousterhout, J.K., "Disk Scheduling Revisited," Proc. of the Winter 1990 USENIX Technical Conf., Washington DC, January 1990.
• 31: Alan J. Smith, Disk cache—miss ratio analysis and design considerations, ACM Transactions on Computer Systems (TOCS), v.3 n.3, p.161-203, Aug. 1985 [doi>10.1145/3959.3961]
• 32: [Spector89] Spector, A.Z., Kazar, M.L., "Wide Area File Service and The AFS Experimental System," Unix Review, V. 7 (3), March, 1989.
• 33: Michael Stonebraker, Operating system support for database management, Communications of the ACM, v.24 n.7, p.412-418, July 1981 [doi>10.1145/358699.358703]
• 34: [Tait91] Tait, C.D., Duchamp, D., "Detection and Exploitation of File Working Sets," Proc. of the 11th Int. Conf. on Distributed Computing Systems, Arlington, TX, May, 1991, pp. 2-9.
• 35: [Trivedi79] Trivedi, K.S., "An Analysis of Prepaging", Computing, V. 22 (3), 1979, pp. 191-210.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
      D.4.4 Communications Management
          Subjects: Input/output

General Terms:
Design, Experimentation, Management, Performance