FAST '03 Abstract
ARC: A Self-Tuning, Low Overhead Replacement Cache
Nimrod Megiddo and Dharmendra S. Modha, IBM Almaden Research Center
We consider the problem of cache management
in a demand paging scenario with uniform page sizes. We
propose a new cache management policy, namely, Adaptive
Replacement Cache (ARC), that has several advantages.
In response to evolving and changing access patterns, ARC
dynamically, adaptively, and continually balances between the
recency and frequency components in an online and self-tuning
fashion. The policy ARC uses a learning rule to
adaptively and continually revise its assumptions about the
The policy ARC is empirically universal, that is, it empirically
performs as well as a certain fixed replacement policyeven when the latter uses the best workload-specific tuning
parameter that was selected in an offline fashion. Consequently,
ARC works uniformly well across varied workloads
and cache sizes without any need for workload specific a
priori knowledge or tuning. Various policies such as LRU-2,
2Q, LRFU, and LIRS require user-defined parameters, and,
unfortunately, no single choice works uniformly well across
different workloads and cache sizes.
The policy ARC is simple-to-implement and, like LRU,
has constant complexity per request. In comparison, policies
LRU-2 and LRFU both require logarithmic time complexity
in the cache size.
The policy ARC is scan-resistant: it allows one-time se-quential
requests to pass through without polluting the cache.
23 real-life traces drawn from numerous domains, ARC
leads to substantial performance gains over LRU for a wide
range of cache sizes. For example, for a SPC1 like synthetic
benchmark, at 4GB cache, LRU delivers a hit ratio of
9.19% while ARC achieves a hit ratio of 20%.
- View the full text of this paper in PDF.
Until May 2004, you will need your USENIX membership identification in order to access the full papers. The Proceedings are published as a collective work, © 2003 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.