Cache Eviction Policies

Every modern computer carries a private lie: the memory your program thinks it has is much slower than the memory it actually uses. Between the CPU and the sprawling depths of RAM sits a cache — a small, blazingly fast pool of data that your processor checks first. If the data is there (cache hit), you're done in nanoseconds. If it isn't (cache miss), you wait a hundred times longer while the system fetches it from slower storage.

Caches are useful precisely because programs are not random. They tend to touch the same data again and again — a phenomenon called locality of reference. A cache that holds the "right" data sees mostly hits; one that holds the wrong data constantly misses and might as well not exist.

The catch is that caches are small. The moment you try to bring in one more item and the cache is full, something has to leave. The rule that decides what gets evicted is the eviction policy — and it is one of the most consequential small decisions in all of systems design.

The four classic policies are LRU (Least Recently Used), LFU (Least Frequently Used), CLOCK (an efficient approximation of LRU), and ARC (Adaptive Replacement Cache). Each bets on a different model of the future: that what you used last is what you'll use next, or that what you've used most often will keep being popular, or that you need both kinds of prediction at once.

Below you can watch four eviction policies race through the same stream of page requests. The cache holds 4 slots. Each column shows what the policy keeps in cache at every step — green means a hit, red means a miss.

<div id="controls">
  <label>{{preset_label}} </label>
  <button class="preset" data-seq="1,2,3,4,1,2,5,1,2,3,4,5">{{preset_recency}}</button>
  <button class="preset" data-seq="1,2,1,3,1,2,1,4,1,2,1,3">{{preset_frequency}}</button>
  <button class="preset" data-seq="1,2,3,4,5,1,2,6,1,3,2,1">{{preset_mixed}}</button>
</div>
<div id="custom-row">
  <label for="seq">{{custom_seq_label}}</label>
  <input id="seq" type="text" value="1,2,3,4,1,2,5,1,2,3,4,5" />
  <button id="run">{{run_btn}}</button>
</div>
<div id="legend">
  <span class="hit-badge">{{legend_hit}}</span>
  <span class="miss-badge">{{legend_miss}}</span>
</div>
<div id="table-wrap">
  <table id="results">
    <thead>
      <tr>
        <th>{{th_step}}</th>
        <th>{{th_page}}</th>
        <th>LRU</th>
        <th>LFU</th>
        <th>CLOCK</th>
        <th>ARC</th>
      </tr>
    </thead>
    <tbody></tbody>
  </table>
</div>
<div id="summary"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
#controls { display: flex; gap: .4rem; align-items: center; flex-wrap: wrap; margin-bottom: .5rem; }
#controls label { font-weight: 600; }
.preset { padding: .3rem .65rem; font: 600 13px system-ui; background: #e8eef3; border: 1px solid #b0bec8;
          border-radius: 6px; cursor: pointer; }
.preset:hover { background: #d0dce6; }
#custom-row { display: flex; gap: .4rem; align-items: center; flex-wrap: wrap; margin-bottom: .5rem; }
#custom-row label { font-weight: 600; }
#seq { flex: 1; min-width: 180px; padding: .3rem .5rem; border: 1px solid #b0bec8; border-radius: 6px; font-size: 13px; }
#run { padding: .3rem .75rem; font: 600 13px system-ui; background: #1d3557; color: #fff;
       border: none; border-radius: 6px; cursor: pointer; }
#run:hover { background: #2e4f7a; }
#legend { display: flex; gap: .5rem; margin-bottom: .4rem; }
.hit-badge, .miss-badge { padding: .15rem .5rem; border-radius: 4px; font: 600 12px system-ui; }
.hit-badge { background: #d4edda; color: #155724; }
.miss-badge { background: #f8d7da; color: #721c24; }
#table-wrap { overflow-x: auto; }
table { border-collapse: collapse; width: 100%; }
th { background: #e8eef3; padding: .35rem .5rem; text-align: center; font-weight: 700;
     border: 1px solid #cdd9e3; white-space: nowrap; }
td { padding: .3rem .45rem; border: 1px solid #cdd9e3; text-align: center; white-space: nowrap; }
tr:nth-child(even) td { background: #f5f8fa; }
.cell-hit { background: #d4edda !important; color: #155724; font-weight: 700; }
.cell-miss { background: #f8d7da !important; color: #721c24; font-weight: 700; }
.cache-state { font-size: 11px; color: #555; display: block; }
#summary { margin-top: .6rem; display: flex; gap: 1rem; flex-wrap: wrap; }
.policy-score { padding: .35rem .7rem; border-radius: 6px; border: 1px solid #cdd9e3;
                font: 600 13px system-ui; background: #f5f8fa; }
.best { background: #d4edda; border-color: #28a745; color: #155724; }

// Code not found

Try the presets: Recency-heavy workloads (repeatedly revisiting recent items) favour LRU; frequency-heavy ones (a small hot set requested many times) favour LFU; mixed workloads reveal why ARC adapts — it dynamically shifts weight between a recency list and a frequency list. CLOCK sits close to LRU but uses far less memory.

Each policy makes a different bet on the future — and pays a different implementation price.

LRU — Least Recently Used (introduced in the 1960s)

Evicts whichever item was accessed furthest in the past. The intuition: if you haven't used something recently, you probably don't need it soon. A textbook implementation uses a doubly-linked list + hash map so every access and eviction is $O(1)$. LRU provably beats random and FIFO on workloads with strong temporal locality.

LFU — Least Frequently Used

Evicts the item with the lowest access count. Good for recognisably hot data, but it suffers from cache pollution — a file scanned once to build an index floods the frequency table and pushes genuinely popular items out. A clean $O(1)$ LFU was only published in 2010 by Shah, Mitra & Matani using frequency buckets (a doubly-linked list of frequency nodes, each holding a set of items at that count).

CLOCK (Second-Chance)

Approximates LRU with a circular buffer and a single reference bit per slot. On access, set the bit to 1. When eviction is needed, the "hand" sweeps the circle: if a bit is 1, clear it and advance; if it is 0, evict. The result is nearly as good as LRU with $O(1)$ time and far less bookkeeping — which is why most operating system page-replacement algorithms use CLOCK variants rather than true LRU.

ARC — Adaptive Replacement Cache (Megiddo & Modha, USENIX FAST 2003)

Keeps four internal lists: T1 (recently seen once), T2 (seen at least twice), B1 (recently evicted from T1), B2 (recently evicted from T2). When a miss falls on B1 the policy grows the recency side; on B2 it grows the frequency side. ARC is self-tuning — it finds the balance that fits the current workload without any manual parameter. It is covered by US Patent 6,996,676, which is why Linux uses a variant called CAR instead.

No policy wins on every workload. The optimal offline algorithm (Bélády's, 1966) always evicts the item you will need furthest in the future — but that requires knowing the future, so it serves only as a benchmark.

The same eviction problem appears everywhere storage is tiered by speed:

• CPU L1/L2/L3 caches: hardware implements a CLOCK-like policy in silicon. A poorly-predicted eviction here costs ~100 CPU cycles per miss — microseconds that add up to seconds at scale.
• Operating system page replacement: Linux uses a variant of CLOCK (with active and inactive lists) to decide which pages of RAM to swap to disk. Getting this wrong under memory pressure turns a fast server into a thrashing one.
• Web servers and CDNs: Nginx's proxy cache and Varnish both offer LRU-based eviction; Cloudflare uses custom policies tuned to web traffic patterns. A 10% improvement in hit rate on a CDN edge node can halve origin-server load.
• Database buffer pools: PostgreSQL's shared buffer uses a CLOCK-sweep algorithm; InnoDB (MySQL) uses a modified LRU. The buffer pool is often the single biggest performance lever in a database.
• DNS resolvers: every resolver is a TTL-bounded LRU. Evict a popular domain early and you add a full recursive lookup (up to 200 ms) to every user's next DNS query.
• Key-value stores: Redis supports LRU, LFU and random eviction (configurable with maxmemory-policy). Choosing the right policy for a session store versus a leaderboard cache is a real engineering decision.

Understanding eviction policies connects directly to related problems: recommendation systems (what content to keep in a user's feed), load balancing (which server to route a request to), and any system where a bounded fast layer must shadow an unbounded slow one.

Every cache is a bet on the future. LRU bets on recency, LFU bets on frequency, CLOCK bets you can approximate LRU cheaply enough to be worth it, and ARC bets it can learn on the fly which bet is winning.

None of them is optimal — Bélády's algorithm is optimal, and it requires a time machine. What the four classic policies give you is a toolkit: match the policy to the workload, measure hit rates, and adjust. That discipline — bounded fast storage, principled eviction, continuous measurement — underlies virtually every layer of the modern computing stack.

The next time a web page loads in 30 milliseconds instead of 3 seconds, there is a quiet algorithm somewhere deciding what to forget. Getting that decision right is one of the most impactful pieces of engineering you can do with a few dozen lines of code.