Geiger: monitoring the buffer cache in a virtual machine environment

ABSTRACT

Virtualization is increasingly being used to address server management and administration issues like flexible resource allocation, service isolation and workload migration. In a virtualized environment, the virtual machine monitor (VMM) is the primary resource manager and is an attractive target for implementing system features like scheduling, caching, and monitoring. However, the lackof runtime information within the VMM about guest operating systems, sometimes called the semantic gap, is a significant obstacle to efficiently implementing some kinds of services.In this paper we explore techniques that can be used by a VMM to passively infer useful information about a guest operating system's unified buffer cache and virtual memory system. We have created a prototype implementation of these techniques inside the Xen VMM called Geiger and show that it can accurately infer when pages are inserted into and evicted from a system's buffer cache. We explore several nuances involved in passively implementing eviction detection that have not previously been addressed, such as the importance of tracking disk block liveness, the effect of file system journaling, and the importance of accounting for the unified caches found in modern operating systems.Using case studies we show that the information provided by Geiger enables a VMM to implement useful VMM-level services. We implement a novel working set size estimator which allows the VMM to make more informed memory allocation decisions. We also show that a VMM can be used to drastically improve the hit rate in remote storage caches by using eviction-based cache placement without modifying the application or operating system storage interface. Both case studies hint at a future where inference techniques enable a broad new class of VMM-level functionality.

REFERENCES

• 1: Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Information and control in gray-box systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 2: Lakshmi N. Bairavasundaram , Muthian Sivathanu , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, X-RAY: A Non-Invasive Exclusive Caching Mechanism for RAIDs, Proceedings of the 31st annual international symposium on Computer architecture, p.176, June 19-23, 2004, München, Germany
• 3: S. Ballmer. Keynote address. Microsoft Management Summit, April 2005.
• 4: S. Best. JFS Overview. www.ibm.com/developerworks/library/ljfs. html, 2000.
• 5: T. C. Bressoud , F. B. Schneider, Hypervisor-based fault tolerance, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.1-11, December 03-06, 1995, Copper Mountain, Colorado, United States
• 6: Edouard Bugnion , Scott Devine , Mendel Rosenblum, Disco: running commodity operating systems on scalable multiprocessors, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.143-156, October 05-08, 1997, Saint Malo, France
• 7: Peter M. Chen , Brian D. Noble, When Virtual Is Better Than Real, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.133, May 20-22, 2001
• 8: Zhifeng Chen , Yan Zhang , Yuanyuan Zhou , Heidi Scott , Berni Schiefer, Empirical evaluation of multi-level buffer cache collaboration for storage systems, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 9: Z. Chen, Y. Zhou, and K. Li. Eviction-based Placement for Storage Caches. In Proceedings of the USENIX Annual Technical Conference (USENIX '03), pages 269--282, San Antonio, Texas, June 2003.
• 10: C. Clark, K. Fraser, S. Hand, J.G. Hansen, E. Jul, C. Limpach, I. Pratt, and A. Warfield. Live Migration of Virtual Machines. In Proceedings of the 2nd Symposium on Networked Systems Design and Implementation (NSDI '05), Boston, Massachusetts, May 2005.
• 11: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 12: P.J. Denning. Working Sets: Past and Present. IEEE Transactions on Software Engineering, SE-6(1):64--84, January 1980.
• 13: Paul Barham , Boris Dragovic , Keir Fraser , Steven Hand , Tim Harris , Alex Ho , Rolf Neugebauer , Ian Pratt , Andrew Warfield, Xen and the art of virtualization, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 14: Renato J. Figueiredo , Peter A. Dinda , José A. B. Fortes, A Case For Grid Computing On Virtual Machines, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.550, May 19-22, 2003
• 15: K. Fraser, S. Hand, R. Neugebauer, I. Pratt, A. Warfield, and M. Williamson. Safe Hardware Access with the Xen Virtual Machine Monitor. In OASIS ASPLOS 2004 workshop, 2004.
• 16: Tal Garfinkel , Ben Pfaff , Jim Chow , Mendel Rosenblum , Dan Boneh, Terra: a virtual machine-based platform for trusted computing, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 17: R. Goldberg. Survey of Virtual Machine Research. IEEE Computer, 7(6):34--45, 1974.
• 18: P. Gum. System/370 Extended Architecture: Facilities for Virtual Machines. IBM Journal of Research and Development, 27(6):530--544, November 1983.
• 19: ImageMagick Studio LLC. ImageMagick image processing software. http://www.imagemagick.org.
• 20: Intel Corporation. Intel Virtualization Technology Specification. ftp://download.intel.com/technology/computing/vptech/C97063.pdf,2005.
• 21: Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
• 22: S.T. Jones, A.C. Arpaci-Dusseau, and R.H. Arpaci-Dusseau. Antfarm: Tracking Processes in a Virtual Machine Environment. In Proceedings of the USENIX Annual Technical Conference (USENIX '06), Boston, Massachusetts, June 2006.
• 23: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 24: S.T. King and P.M. Chen. Backtracking Intrusions. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP '01), Banff, Canada, October 2001.
• 25: D. Muntz and P. Honeyman. Multi-Level Caching in Distributed File Systems - or - Your Cache Ain't Nuthin' But Trash. Proceedings of the USENIX Winter Conference, pages 305--313, January 1992.
• 26: Open Source Development Labs. OSDL Database Test Suite. http://www.osdl.org/lab activities/kernel testing/osdl database test suite.
• 27: R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 28: H. Reiser. ReiserFS. www.namesys.com, 2004.
• 29: Constantine P. Sapuntzakis , Ramesh Chandra , Ben Pfaff , Jim Chow , Monica S. Lam , Mendel Rosenblum, Optimizing the migration of virtual computers, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060324]
• 30: M. Sivathanu, L.N. Bairavasundaram, A.C. Arpaci-Dusseau, and R.H. Arpaci-Dusseau. Life or Death at Block Level. In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI '04), pages 379--394, San Francisco, California, December 2004.
• 31: Muthian Sivathanu , Vijayan Prabhakaran , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Awarded Best Student Paper! -- Improving Storage System Availability with D-GRAID, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 32: Storage Performance Council. SPC web search engine storage traces. http://traces.cs.umass.edu/storage.
• 33: Jeremy Sugerman , Ganesh Venkitachalam , Beng-Hong Lim, Virtualizing I/O Devices on VMware Workstation's Hosted Virtual Machine Monitor, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.1-14, June 25-30, 2001
• 34: A. Sweeney, D. Doucette, W. Hu, C. Anderson, M. Nishimoto, and G. Peck. Scalability in the XFS File System. In Proceedings of the USENIX Annual Technical Conference (USENIX '96), San Diego, California, January 1996.
• 35: A. Tridgell. Dbench filesystem benchmark. http://samba.org/ftp/tridge/dbench.
• 36: Theodore Y. Ts'o , Stephen Tweedie, Planned Extensions to the Linux Ext2/Ext3 Filesystem, Proceedings of the FREENIX Track: 2002 USENIX Annual Technical Conference, p.235-243, June 10-15, 2002
• 37: S.C. Tweedie. EXT3, Journaling File System. olstrans.sourceforge.net/release/OLS2000-ext3/OLS2000-ext3.html, July 2000.
• 38: Carl A. Waldspurger, Memory resource management in VMware ESX server, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060307]
• 39: Andrew Whitaker , Marianne Shaw , Steven D. Gribble, Scale and performance in the Denali isolation kernel, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060308]
• 40: Theodore M. Wong , John Wilkes, My Cache or Yours? Making Storage More Exclusive, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.161-175, June 10-15, 2002
• 41: Ming Zhao , Jian Zhang , Renato Figueiredo, Distributed File System Support for Virtual Machines in Grid Computing, Proceedings of the 13th IEEE International Symposium on High Performance Distributed Computing (HPDC'04), p.202-211, June 04-06, 2004 [doi>10.1109/HPDC.2004.10]
• 42: Yuanyuan Zhou , James Philbin , Kai Li, The Multi-Queue Replacement Algorithm for Second Level Buffer Caches, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.91-104, June 25-30, 2001

INDEX TERMS

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

General Terms:
Design, Measurement, Performance

Keywords:
inference, virtual machine