ABC Tools

Cache Replacement Policies, Explained

After reading this you can predict which key a cache will evict, compute a hit rate by hand, and explain why adding memory sometimes makes FIFO worse and why a simple loop drives LRU to zero.

What a replacement policy decides

A cache holds a fixed number of keys. When you request a key that is already there, that is a hit. When you request a key that is not there, that is a miss, and the cache must load it. If the cache is full, it must throw something out first. The rule that picks the victim is the replacement policy.

Every policy sees the same input: a sequence of key requests and a slot count. They differ only in which key they evict. That single choice separates a 90% hit rate from a 10% hit rate on the same workload, so it is worth understanding precisely.

Here is the hook. Take the sequence 1 2 3 4 1 2 5 1 2 3 4 5 under FIFO. With 3 slots it misses 9 times. With 4 slots, the same policy on the same sequence misses 10 times. More memory produced more misses. That is Bélády's anomaly, and the simulator reproduces it from a preset.

The policies, from simple to clever

FIFO
Evict the key that was loaded earliest, regardless of how often it has been used since. Cheap: one queue. Vulnerable to the anomaly above.
LRU
Evict the least recently used key. On every hit, mark the key as most recent. Good for workloads with temporal locality. Never suffers Bélády's anomaly.
LFU
Evict the least frequently used key, counting references. Good when some keys are genuinely popular, bad when yesterday's popular key never comes back.
MRU
Evict the most recently used key. Sounds backwards, but it wins on looping scans, as you will see.
CLOCK
An approximation of LRU using one reference bit per slot and a rotating hand. This is what real operating systems use for page replacement.
ARC
Adaptive Replacement Cache. Balances recency and frequency automatically by keeping ghost lists of recently evicted keys, and shifts its budget toward whichever list is producing hits.
OPT
Bélády's optimal algorithm. Evict the key whose next use is farthest in the future. It requires seeing the future, so it is not implementable. It exists as an upper bound.

The one number: hit rate

Everything reduces to one ratio. Over a sequence of N requests that produce h hits:

\text{hit rate} = \frac{h}{N} = \frac{N - m}{N}

Here m is the number of misses, and h + m = N always. If a 12-request sequence produces 3 hits, the hit rate is 3/12 = 0.25, or 25%, and the miss rate is 75%. The running hit rate the simulator animates is the same formula computed after each request, so early spikes and dips smooth out as N grows.

The first request for any key is always a miss, no matter the policy: the cache starts empty. These are called compulsory misses. A sequence of 12 requests over 5 distinct keys has at least 5 compulsory misses, so no policy can exceed a hit rate of 7/12 ≈ 0.583 on that sequence.

A worked example on the demo sequence

FIFO with 3 slots on 1 2 3 4 1 2 5 1 2 3 4 5

Load the demo defaults and trace FIFO with 3 slots. The oldest-loaded key is always the leftmost below. A star marks a hit.

  1. Request 1: miss. Cache [1].
  2. Request 2: miss. Cache [1 2].
  3. Request 3: miss. Cache [1 2 3].
  4. Request 4: miss, full, evict 1 (oldest). Cache [2 3 4].
  5. Request 1: miss, evict 2. Cache [3 4 1].
  6. Request 2: miss, evict 3. Cache [4 1 2].
  7. Request 5: miss, evict 4. Cache [1 2 5].
  8. Request 1: hit. Cache [1 2 5].
  9. Request 2: hit. Cache [1 2 5].
  10. Request 3: miss, evict 1 (oldest still). Cache [2 5 3].
  11. Request 4: miss, evict 2. Cache [5 3 4].
  12. Request 5: hit. Cache [5 3 4].

Count: 3 hits (steps 8, 9, 12), 9 misses. Hit rate 3/12 = 0.25. Now rerun with 4 slots. You will find 2 hits and 10 misses, hit rate 2/12 ≈ 0.167. The larger cache did worse, exactly as the footnote claims.

FIFO misses rise from 9 to 10 when slots go from 3 to 4. LRU and OPT both improve. Fewer misses is better.

Why LRU dies on a loop, and MRU saves it

Consider a workload that scans keys in a loop: 1 2 3 4 1 2 3 4 1 2 3 4, with an LRU cache of 3 slots. There are 4 distinct keys and only 3 slots, so one key is always missing. LRU evicts the least recently used key, which on a strict loop is always the exact key you are about to request next.

Trace the steady state. After loading 1 2 3, request 4: LRU evicts 1 (least recent). Next request is 1: miss, evict 2. Next is 2: miss, evict 3. Every request after the warm-up misses. The hit rate approaches 0%.

MRU evicts the most recently used key instead. After loading 1 2 3 and missing on 4, MRU evicts 3 (the one just used), keeping 1 and 2. The next requests for 1 and 2 both hit. On this loop MRU holds a hit rate near (N-4)/N, which climbs toward 75% as the loop lengthens. The lesson: locality assumptions are assumptions. A scan has anti-locality, and the "obviously good" policy is the worst one.

On a loop of K distinct keys through a cache of S slots, LRU and FIFO approach a 0% hit rate whenever S < K, because they always evict the next-needed key. MRU keeps S-1 of the keys resident and reaches a hit rate near (S-1)/K. When S ≥ K every policy reaches 100% after warm-up.

Reading the comparison chart

The comparison mode runs every policy on one sequence and plots each running hit rate. Read it in three passes. First, find the OPT line: it is the ceiling nothing can beat. If your chosen policy tracks OPT within a few percent, you are done tuning. Second, look at the gap. On the demo sequence OPT achieves 5 hits out of 12 (hit rate 0.417) with 3 slots, while FIFO gets 3 (0.25). That gap of 2 hits is the ceiling on how much a better policy could win here.

Third, watch the shape over time, not just the final value. A policy that starts low and climbs is warming up through compulsory misses. A policy that climbs then collapses has hit a phase change in the workload, such as a loop starting. The final number hides both stories.

Hits on the 12-request demo sequence, 3 slots
PolicyHitsMissesHit rate
FIFO390.25
LRU2100.1667
OPT570.4167

Common mistakes

Do not treat OPT as a policy you can ship. It reads the future access sequence to pick victims. Use it only as a measuring stick: if OPT gets 0.42 and LRU gets 0.40 on your trace, no clever policy will recover more than 2 percentage points, so stop optimizing the policy and attack the workload instead.

Two more traps. First, comparing hit rates across different sequences is meaningless: a 40% hit rate on a scan can be far better than 90% on a trace with heavy repetition. Fix the sequence, then compare. Second, assuming bigger caches always help. Bélády's anomaly proves the opposite for FIFO. LRU is stack-based: the set of keys held with S slots is always a subset of the set held with S+1 slots, so its miss count can never rise when you add memory. FIFO, MRU and Random lack this property.

A third subtlety with LFU: raw frequency counts never decay, so a key that was requested 1000 times last hour but never again still outranks a fresh popular key with a count of 5. Real LFU implementations add aging for this reason. The simulator's plain LFU shows the un-aged behavior, which makes the failure visible.

Related tools

If you want to see the data structures that make these policies fast (the doubly linked list plus hash map behind LRU, or the heap behind LFU), open the Data Structure Visualizer. Caching sits next to two other probabilistic ideas worth exploring: the Bloom Filter Playground for membership tests that trade accuracy for space, and the Consistent Hashing Ring for spreading keys across cache servers so adding a node moves only 1/N of them. To see why cache misses matter at scale, the Tail Latency and Autoscaling Simulator shows how a small miss-rate rise pushes p99 latency past a cliff.

Frequently asked questions

What hit rate should I expect in production?

It depends entirely on locality. Web caches with a Zipfian request pattern often hit 80% to 95%. A cold batch scan hits near the compulsory-miss floor. There is no universal target: measure your own trace against OPT to find the achievable ceiling.

Is LRU always better than FIFO?

Not always, but LRU never suffers Bélády's anomaly and usually matches or beats FIFO on workloads with temporal locality. FIFO's advantage is cost: it needs one pointer, no per-access bookkeeping. CLOCK gives you most of LRU's quality at close to FIFO's cost.

Why do operating systems use CLOCK instead of LRU?

True LRU requires updating a data structure on every memory access, which is far too expensive for page replacement. CLOCK approximates it with a single reference bit per page and a sweeping hand that clears bits and evicts the first page whose bit is already 0. It is cheap and close to LRU in practice.

What makes ARC adaptive?

ARC keeps two lists, one for keys seen once (recency) and one for keys seen more than once (frequency), plus ghost lists of recently evicted keys. When a ghost hit lands in the recency ghost list, ARC grows the recency budget; when it lands in the frequency ghost list, it grows the frequency budget. The split shifts automatically toward whatever the current workload rewards.

Can any policy beat OPT?

No. Bélády proved OPT is optimal for a known access sequence: no algorithm can produce fewer misses. Any real policy that appears to beat it has a bug or is being measured on a different sequence.

Try it yourself in the tool

Related tools

Bloom Filter Playground

Add items, watch bits light up, measure the false positive rate.

Consistent Hashing Ring

See why adding a server moves 1/N of the keys, not all of them.

Data Structure Visualizer

Watch BST, AVL, red-black trees, heaps, hash tables, tries and union-find work, step by step.

Digital Logic Gate Simulator

Build circuits from gates and flip-flops, wire them up, and watch the signals flow live.

Git Branching Sandbox

Type git commands and watch the commit DAG, branches and HEAD move — with levels, remotes, undo, and merge-vs-rebase contrast.

IEEE-754 Floating Point Explorer

Flip the bits of a float and see why 0.1 + 0.2 ≠ 0.3.