Notesfoundations🌱 seedling

Cache Eviction Policy

Also: Eviction Policy · LRU · LFU · TinyLFU · S3-FIFO · Cache Replacement Policy

When a cache is full, its eviction policy decides what to throw out, betting on which keys won't be needed soon. Modern policies add admission control, so a key must prove it's reused before it can displace established ones.

Why it exists

Memory is finite and the future is unknown. A better guess means a higher hit ratio from the same memory.

How it works

  • LRU: evict the least recently used. Good for recency, but one scan of one-off keys flushes the hot set.
  • LFU: evict the least frequently used. Scan-resistant, but needs aging so old popularity fades.
  • FIFO / CLOCK-style: evict the oldest inserted. Hits just set a bit, so there are no list moves and little locking.
  • Admission and probation: segmented LRU (Memcached's hot/warm/cold), W-TinyLFU (a count-min sketch admits a newcomer only if it's more popular than the victim), S3-FIFO (a small probation FIFO, a main FIFO and a ghost queue), SIEVE (one FIFO, a visited bit and a moving hand).
  • Sampling: Redis approximates LRU/LFU by sampling a few keys (5 by default) and evicting the best candidate.

Trade-offs

Policy Gains Costs
LRU simple, strong for recency scan-vulnerable; a list update on every hit
LFU / TinyLFU scan-resistant, high hit ratio sketch and aging complexity
FIFO-based (S3-FIFO, SIEVE) lock-friendly, fast, often fewer misses less intuitive; newer

In practice

  • Twitter's production traces: FIFO matched or beat LRU on many clusters, and TTL expiry often bounded the working set more than eviction did.
  • Redis defaults to noeviction (writes fail when memory is full); caches should set an allkeys-* or volatile-* policy.

Pitfalls

  • Leaving a cache unbounded, or a store at noeviction, and treating out-of-memory errors as a cache.
  • Judging policies on synthetic workloads: real traces have TTLs, write bursts and scans.

Recall

These cards are also in your review deck, scheduled with spaced repetition.