Cache Eviction Lab

royhp.com

A cache holds only a few of the keys an application keeps asking for. When a wanted key is already resident it's a hit; otherwise it's a miss and — if the cache is full — something must be evicted to make room. Which victim you pick is the eviction policy, and the right choice depends on how skewed the access pattern is. Generate a stream, step or play it through, and compare every policy against Belady's clairvoyant optimal baseline.

Cache size4 slots Stream length120 accesses Key space8 keys Access skew0.80

Stream pattern Detailed policy

Speed 1×

Incoming key

ready

Press Step or Play to feed the access stream into the cache.

LRU cache · 4 slots badge = accesses since last use

Access stream tap a cell to jump · hit miss

Hit rate (so far)

0.0%

0 / 0 served

Miss rate

0.0%

0 misses

Evictions

evictions

Accesses

of 120

Policy showdown — hit rate over the full stream optimal ceiling

Every policy runs the same generated stream at the current cache size. The dashed marker is Belady's optimal — the best any policy could do with perfect knowledge of the future. The closer a bar gets to it, the better that heuristic suits this workload.

Try this: with a skewed (Zipf) stream a small cache already wins — a handful of hot keys carry most accesses, and LRU / LFU keep them resident. Now drag Access skew down to uniform: every key is equally likely, reuse distance explodes, and even Optimal struggles — caching simply can't help. Switch the pattern to Sequential scan with a key space larger than the cache and watch LRU and FIFO collapse to 0% hits (each key is evicted exactly one step before it's needed again) while Random salvages a few. The Hot set + scans pattern is the classic case where scan traffic flushes an LRU cache but LFU protects the hot working set. Raise the cache size past the working-set size and every policy converges on Optimal.