Coordinated Multilevel Buffer Cache Management with Consistent Access Locality Quantification
|
This paper proposes a protocol for effective coordinated buffer cache management in a multilevel cache hierarchy typical of a client/server system. Currently, such cache hierarchies are managed suboptimally—decisions about block placement and replacement are made locally at each level of the hierarchy without coordination between levels. Though straightforward, this approach has several weaknesses: 1) Blocks may be redundantly cached, reducing the effective total cache size, 2) weakened locality at lower-level caches makes recency-based replacement algorithms such as LRU less effective, and 3) high-level caches cannot effectively identify blocks with strong locality and may place them in low-level caches. The fundamental reason for these weaknesses is that the locality information embedded in the streams of access requests from clients is not consistently analyzed and exploited, resulting in globally nonsystematic, and therefore suboptimal, placement and replacement of cached blocks across the hierarchy. To address this problem, we propose a coordinated multilevel cache management protocol based on consistent access-locality quantification. In this protocol, locality is dynamically quantified at the client level to direct servers to place or replace blocks appropriately at each level of the cache hierarchy. The result is that the block layout in the entirely hierarchy dynamically matches the locality of block accesses. Our simulation experiments on both synthetic and real-life traces show that the protocol effectively ameliorates these caching problems. As anecdotal evidence, our protocol achieves a reduction of block accesses of 11 percent to 71 percent, with an average of 35 percent, over uniLRU, a unified multilevel cache scheme.
[1] 95 L.N. Bairavasundaram, M. Sivathanu, A.C. Arpaci-Dusseau, and R.H. Arpaci-Dusseau, “X-RAY: A Non-Invasive Exclusive Caching Mechanism for RAIDs,” Proc. 31st Ann. Int'l Symp. Computer Architecture, June 2004.
[2] I. Ari, A. Amer, R. Gramacy, E.L. Miller, S.A. Brandt, and D.D.E. Long, “ACME: Adaptive Caching Using Multiple Experts,” Proc. 2002 Workshop Distributed Data and Structures, Mar. 2002.
[3] L.A. Belady, “A Study of Replacement Algorithms for a Virtual-Storage Computer,” IBM Systems J., vol. 5, no. 2, pp. 78-101, 1966.
[4] M.G. Baker, J.H. Hartman, M.D. Kupfer, K.W. Shirriff, and J.K. Ousterhout, “Measurements of a Distributed File System,” Proc. 13th ACM Symp. Operating Systems Principles, pp. 198-212, 1991.
[5] J.-L. Baer and W.-H. Wang, “On the Inclusion Properties for Multi-Level Cache Hierarchies,” Proc. 15th Ann. Int'l Symp. Computer Architecture, pp. 73-80, 1988.
[6] Trace Distribution Center, Performance Evaluation Laboratory, Brigham Young Univ., http:/tds.cs.byu.edu/, 2001.
[7] E.G. Coffman and P.J. Denning, Operating Systems Theory. Prentice-Hall, 1973.
[8] P. Cao, E.W. Felten, and K. Li, “Application-Controlled File Caching Policies,” Proc. USENIX Summer 1994 Technical Conf., pp.171-182, 1994.
[9] J. Choi, S. Noh, S. Min, and Y. Cho, “Towards Application/File-Level Characterization of Block References: A Case for Fine-Grained Buffer Management,” Proc. 2000 ACM SIGMETRICS Conf. Measuring and Modeling of Computer Systems, June 2000.
[10] J. Choi, S. Noh, S. Min, and Y. Cho, “An Implementation Study of a Detection-Based Adaptive Block Replacement Scheme,” Proc. 1999 Ann. USENIX Technical Conf., pp. 239-252, 1999.
[11] Z. Chen, Y. Zhou, and K. Li, “Eviction-Based Placement for Storage Caches,” Proc. 2003 Ann. USENIX Technical Conf., June 2003.
[12] Z. Chen, Y. Zhang, Y. Zhou, H. Scott, and B. Schiefer, “Empirical Evaluation of Multi-Level Buffer Cache Collaboration for Storage System,” Proc. ACM Int'l Conf. Measurement and Modeling of Computing Systems (SIGMETRICS '05), June 2005.
[13] P.J. Denning, “The Working Set Model for Program Behavior,” Comm. ACM, vol. 11, no. 5, May 1968.
[14] M.D. Dahlin, R.Y. Wang, T.E. Anderson, and D.A. Patterson, “Cooperative Caching: Using Remote Client Memory to Improve File System Performance,” Proc. First Symp. Operating Systems Design and Implementation, pp. 267-280, Nov. 1994.
[15] W. Effelsberg and T. Haerder, “Principles of Database Buffer Management,” ACM Trans. Database Systems, pp. 560-595, Dec. 1984.
[16] S. Jiang, K. Davis, F. Petrini, X. Ding, and X. Zhang, “A Locality-Aware Cooperative Cache Management Protocol to Improve Network File System Performance,” Proc. 26th Int'l Conf. Distributed Computing Systems, July 2006.
[17] T. Johnson and D. Shasha, “2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm,” Proc. 20th Int'l Conf. Very Large Data Bases, pp. 439-450, 1994.
[18] S. Jiang and X. Zhang, “LIRS: An Efficient Low Inter-Reference Recency Set Replacement Policy to Improve Buffer Cache Performance,” Proc. 2002 ACM SIGMETRICS Conf. Measuring and Modeling of Computer Systems, June 2002.
[19] J. Kim, J. Choi, J. Kim, S. Noh, S. Min, Y. Cho, and C. Kim, “A Low-Overhead, High-Performance Unified Buffer Management Scheme that Exploits Sequential and Looping References,” Proc. Fourth Symp. Operating Systems Design and Implementation, Oct. 2000.
[20] D. Lee, J. Choi, J. Kim, S. Noh, S. Min, Y. Cho, and C. Kim, “On the Existence of a Spectrum of Policies that Subsumes the Least Recently Used (LRU) and Least Frequently Used (LFU) Policies,” Proc. 1999 ACM SIGMETRICS Conf. Measuring and Modeling of Computer Systems, May 1999.
[21] D. Lee, S. Noh, S. Min, and Y. Cho, “Efficient Caching Algorithms for Two-Level Disk Cache Hierarchies,” Proc. Eighth Ann. Symp. Combinatorial Pattern Matching, 1997.
[22] D. Muntz and P. Honeyman, “Multi-Level Caching in Distributed File System—or—Your Caching Ain't Nuthin' but Trash,” Proc. USENIX Winter Technical Conf., 1992.
[23] N. Megiddo and D. Modha, “ARC: A Self-Tuning, Low Overhead Replacement Cache,” Proc. Second USENIX Symp. File and Storage Technologies (FAST '03), Mar. 2003.
[24] P. Sarkar and J. Hartman, “Efficient Cooperative Caching Using Hints,” Proc. Second Symp. Operating Systems Design and Implementation, 1996.
[25] Y. Smaragdakis, S. Kaplan, and P. Wilson, “EELRU: Simple and Effective Adaptive Page Replacement,” Proc. 1999 ACM SIGMETRICS Conf. Measuring and Modeling of Computer Systems, pp.122-133, May 1999.
[26] M. Uysal, A. Acharya, and J. Salts, “Requirements of I/O Systems for Parallel Machines: An Application-Driven Study,” Technical Report CS-TR-3802, Dept. of Computer Science, Univ. of Maryland, College Park, May 1997.
[27] G. Voelker, E. Anderson, T. Kimbrel, M. Feeley, J. Chase, A. Karlin, and H. Levy, “Implementing Cooperative Prefetching and Caching in a Globally Managed Memory System,” Proc. 1998 ACM SIGMETRICS Conf. Measuring and Modeling of Computer Systems, June 1998.
[28] D.L. Willick, D.L. Eager, and R.B. Bunt, “Disk Cache Replacement Policies for Network Fileservers,” Proc. 13th Int'l Conf. Distributed Computing Systems, pp. 2-11, 1993.
[29] J. Wilkes, “The Pantheon Storage-System Simulator,” Technical Report, HPL-SSP-95-14 rev. 1, HP Lab, May 1996.
[30] C. Williamson, “On Filter Effects in Web Caching Hierarchies,” ACM Trans. Internet Technology, vol. 2, no. 1, pp. 47-77, Feb. 2002.
[31] T.M. Wong and J. Wilkes, “My Cache or Yours? Making Storage More Exclusive,” Proc. 2002 Ann. USENIX Technical Conf., June 2002.
[32] Y. Zhu and Y. Hu, “Can Large Disk Built-In Caches Really Improve System Performance?” Proc. 2002 ACM SIGMETRICS Conf. Measuring and Modeling of Computer Systems, June 2002.
[33] Y. Zhou, “Memory Management for Networked Servers,” PhD dissertation, Computer Science Dept., Princeton Univ., Nov. 2000.
[34] Y. Zhou, J.F. Philbin, and K. Li, “The Multi-Queue Replacement Algorithm for Second Level Buffer Caches,” Proc. 2001 Ann. USENIX Technical Conf., pp. 91-104, June 2001.
Index Terms:
Replacement algorithm, locality, multilevel caching, networked file system.
Citation:
Song Jiang, Kei Davis, Xiaodong Zhang, "Coordinated Multilevel Buffer Cache Management with Consistent Access Locality Quantification," IEEE Transactions on Computers, vol. 56, no. 1, pp. 95-108, Jan. 2007, doi:10.1109/TC.2007.7
PURCHASE ARTICLE: $19
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb