Cache eviction

A cache keeps a few items close at hand: pages in RAM instead of on disk, database rows in memory, images in a browser, videos on a CDN server near you. When it is full and a new item arrives, something has to go. The eviction policy decides what. A good choice means the next request is a hit (served from the cache); a bad one means a miss (a trip to the slow storage behind it).

This page feeds one sequence of requests, the trace, to five caches of the same size at once, one request per step. Each cache uses a different policy. Green squares are hits, red squares are misses, and the bars at the bottom race the hit counts. Pick a workload, a capacity and a length, then press Run. Or type your own trace.

The five policies

  • LRU, least recently used: evict the key that has gone longest without a request (the largest "idle" number). The bet: what was used recently will be used again soon. It needs a hash map plus a list that is updated on every hit; see the LRU cache page.
  • LFU, least frequently used: evict the key with the fewest requests since it entered the cache (the smallest "×" count). Ties go to the least recently used. The bet: popular stays popular.
  • FIFO, first in first out: evict the key that has been in the cache longest (the largest "age"), however often it is used. Almost free to implement, and the baseline to beat.
  • CLOCK, second chance: each slot has a reference bit, set when its key is used. A hand sweeps the slots. A slot with the bit set gets it cleared and is passed over (its second chance); the first slot with the bit clear is evicted. It approximates LRU with one bit per slot and no list to update on hits, which is why operating systems use it for page replacement.
  • OPT, Bélády's optimal policy: evict the key whose next request is furthest in the future, or that is never requested again. No real cache can know the future. OPT is the ceiling: the best hit rate any policy could reach on this trace, so it shows how much room each real policy leaves.
Trace A C C B B A D, then E misses at t8 with the cache full of A, B, C, D; the future requests A, C, D are known only to OPT. Grid of policies by keys: LRU evicts C (idle 5, the longest), LFU evicts D (used once), FIFO evicts A (entered first, age 7), OPT evicts B (not requested soon)
On the same full cache, LRU, LFU, FIFO and OPT each pick a different victim, because each looks at a different number.
Two clock faces with four slots. Before: A bit 1, B bit 1, C bit 0, D bit 1, hand at A, and E arrives. The hand clears A's and B's bits and skips them, then evicts C, whose bit is 0. After: A bit 0, B bit 0, E with bit 1 in C's slot, hand moved on to D
CLOCK clears the bit of each recently used key it passes and evicts the first key whose bit is already clear.

Why OPT is optimal

Suppose some policy evicts key x where OPT would evict y, whose next request comes later than x's. Swap the two decisions: keep x, evict y. Up to x's next request nothing changes. At that request the swapped version hits where the original missed, and anything the original gains later on y it could only gain by paying that miss first. Repeating the argument turns any policy into OPT without ever losing a hit. The page's tests check this on thousands of traces: OPT never has fewer hits than any other row.

The workloads, and what each one shows

  • Hot keys: 75% of requests go to 3 keys. LFU wins: the hot keys build up high counts and stay. FIFO loses: it evicts a hot key on schedule and pays a miss to bring it straight back.
  • Random: every key equally likely. The four real policies tie at about capacity / 12; there is no pattern to exploit. Only OPT does better.
  • Looping scan: the same capacity + 1 keys in a loop. LRU, LFU, FIFO and CLOCK all get 0%: each one evicts exactly the key that is needed next, every time. OPT keeps most of the loop. Databases meet this with repeated table scans, and many detect them and bypass the cache.
  • Scan pollution: bursts of hot keys, each followed by a scan of cold keys read once. The scans flush the hot keys out of LRU, FIFO and CLOCK. LFU sees the scanned keys were used only once and keeps the hot keys, finishing close to OPT.
  • Shifting popularity: one set of keys is hot for the first half, another for the second. Now LFU loses: the old favourites' high counts keep them in the cache long after they stop being requested. LRU forgets them as soon as they go quiet.

No policy wins everywhere. LRU adapts but is fooled by scans and loops. LFU resists scans but cannot forget. Every workload that makes one look good can be flipped to make it look bad.

This page's own averages over 300 traces each, capacity 4, 60 requests:

                         LRU    LFU    FIFO   CLOCK   OPT
Hot keys                 62%    70%    58%    59%     74%
Random                   31%    32%    31%    31%     53%
Looping scan              0%     0%     0%     0%     70%
Scan pollution           31%    51%    31%    31%     53%
Shifting popularity      73%    51%    69%    70%     78%

What real systems do

  • Operating systems (Linux, the BSDs) use CLOCK-like schemes with an active and an inactive list, so a page must be used twice before it counts as hot. That resists scans.
  • Redis offers allkeys-lru and allkeys-lfu, both approximate. It samples a few keys and evicts the worst of the sample instead of keeping a full order, and its LFU counters decay over time so old favourites can be forgotten.
  • CPU caches use pseudo-LRU: a few bits per set that roughly track recency, cheap enough to update in hardware on every access.
  • Combined policies try to get the best of both. ARC (in ZFS) balances a recency list and a frequency list. W-TinyLFU (in Java's Caffeine library) admits a new key only if it looks more popular than the one it would replace.

Common mistakes

  • Judging a policy on one workload. Every policy here wins one preset and loses another.
  • LFU without aging. Counts that never decay make a cache that cannot adapt; see Shifting popularity.
  • Forgetting what LRU costs. True LRU reorders a list on every hit, which is expensive under heavy concurrency. That is why real systems approximate it (CLOCK, sampling).
  • Assuming a bigger cache always helps FIFO. Bélády's anomaly: for FIFO, some traces get more misses with more slots. LRU and OPT never do.