Outperforming LRU with an adaptive replacement cache algorithm
The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Abstract
The self-tuning, low-overhead, scan-resistant adaptive replacement cache algorithm outperforms the least-recently-used algorithm by dynamically responding to changing access patterns and continually balancing between workload recency and frequency features. Caching, a fundamental metaphor in modern computing, finds wide application in storage systems, databases, Web servers, middleware, processors, file systems, disk drives, redundant array of independent disks controllers, operating systems, and other applications such as data compression and list updating. In a two-level memory hierarchy, a cache performs faster than auxiliary storage, but it is more expensive. Cost concerns thus usually limit cache size to a fraction of the auxiliary memory's size.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Amortized efficiency of list update and paging rules
Sleator, D. D., & Tarjan, R. E. (1985) · Communications of the ACM · doi:10.1145/2786.2793 · Cited by 2,123
A study of replacement algorithms for a virtual-storage computer
Belady, L. A. (1966) · IBM Systems Journal · doi:10.1147/sj.52.0078 · Cited by 1,659
Evaluation techniques for storage hierarchies
Mattson, R. L., Gecsei, J., Slutz, D. R., & Traiger, I. L. (1970) · IBM Systems Journal · doi:10.1147/sj.92.0078 · Cited by 1,302
ARC: a self-tuning, low overhead replacement cache
Megiddo, N., & Modha, D. S. (2003) · File and Storage Technologies · Cited by 1,120
Self-citation2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm
Johnson, T. J., & Shasha, D. E. (1994) · Very Large Data Bases · Cited by 811
Coffman, E. G., & Denning, P. J. (1973) · Medical Entomology and Zoology · Cited by 795
Lee, D., Choi, J., Kim, J.-H., Noh, S. H., Min, S. L., Cho, Y., & Kim, C. S. (2001) · IEEE Transactions on Computers · doi:10.1109/tc.2001.970573 · Cited by 590
Jiang, S., & Zhang, X. (2002) · Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems · doi:10.1145/511334.511340 · Cited by 489
The Multi-Queue Replacement Algorithm for Second Level Buffer Caches
Zhou, Y., Philbin, J. F., & Li, K. (2001) · USENIX Annual Technical Conference · Cited by 408
Denning, P. J. (1980) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1980.230464 · Cited by 396
Data cache management using frequency-based replacement
Robinson, J. T., & Devarakonda, M. V. (1990) · Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems - SIGMETRICS '90 · doi:10.1145/98457.98523 · Cited by 394
Principles of Optimal Page Replacement
Aho, A. V., Denning, P. J., & Ullman, J. D. (1971) · Journal of the ACM · doi:10.1145/321623.321632 · Cited by 289
Jiang, S., & Zhang, X. (2002) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/511399.511340 · Cited by 192
An optimality proof of the LRU- K page replacement algorithm
O'Neil, E. J., O׳Neil, P. E., & Weikum, G. (1999) · Journal of the ACM · doi:10.1145/300515.300518 · Cited by 120
The automatic improvement of locality in storage systems
Hsu, W. W., Smith, A. J., & Young, H. C. (2005) · ACM Transactions on Computer Systems · doi:10.1145/1113574.1113577 · Cited by 102
WSCLOCK—a simple and effective algorithm for virtual memory management
Carr, R. W., & Hennessy, J. L. (1981) · ACM SIGOPS Operating Systems Review · doi:10.1145/1067627.806596 · Cited by 100
WSCLOCK---a simple and effective algorithm for virtual memory management
Carr, R. W., & Hennessy, J. L. (1981) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/800216.806596 · Cited by 84
Data cache management using frequency-based replacement
Robinson, J. T., & Devarakonda, M. V. (1990) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/98460.98523 · Cited by 78
Research works printed but not linked: 1
- Corbato, 1969, A Paging Experiment with the Multics System, 217
Cited by
OS v : optimizing the operating system for virtual machines
Kivity, A., Laor, D., Costa, G., Enberg, P., Har’El, N., Martí, D., & Zolotarov, V. (2014) · USENIX Annual Technical Conference · Cited by 250
System-level implications of disaggregated memory
Lim, K., Turner, Y. F., Santos, J. R., AuYoung, A., Chang, J., Ranganathan, P., & Wenisch, T. F. (2012) · IEEE International Symposium on High-Performance Computer Architecture (HPCA) · doi:10.1109/hpca.2012.6168955 · Cited by 239
Performance of compressed inverted list caching in search engines
Zhang, J., Long, X., & Suel, T. (2008) · Proceedings of the 17th international conference on World Wide Web · doi:10.1145/1367497.1367550 · Cited by 230
SSD bufferpool extensions for database systems
Canim, M., Mihaila, G. A., Bhattacharjee, B., Ross, K. A., & Lang, C. A. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1921017 · Cited by 165
Three-level caching for efficient query processing in large Web search engines
Long, X., & Suel, T. (2005) · International World Wide Web Conference (WWW) · doi:10.1145/1060745.1060785 · Cited by 162
Metadata
- Authors
- Megiddo, N., & Modha, D. S.
- Affiliations
- IBM Research - Almaden (US)
- Venue
- Computer
- Published
- 2004-04
- Volume
- 37
- Issue
- 4
- Pages
- 58-65
- ISSN
- 0018-9162 (ISSN-L)
- OpenAlex
- W2003549201
- Cited by
- 243
- References
- 18
- Citations by year
- 2026: 6 · 2025: 5 · 2024: 6 · 2023: 9 · 2022: 9 · 2021: 13 · 2020: 11 · 2019: 9 · 2018: 16 · 2017: 19 · 2016: 17 · 2015: 12 · 2014: 18 · 2013: 11 · 2012: 17
- FWCI
- 14.18
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Computer (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Computer Networks and Communications › Caching and Content Delivery
- Physical Sciences › Computer Science › Computer Networks and Communications › Advanced Data Storage Technologies
- Keywords
- LRU cache, cache replacement policy, auto-tuning
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.