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 anallkeys-*orvolatile-*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.
Connections
- Part of
- Caching
Recall
These cards are also in your review deck, scheduled with spaced repetition.