Cache eviction policies

Why it matters

Memory is finite and the key space is not. Every cache eventually fills, and the rule it uses to make room decides its hit ratio from then on. A good eviction policy keeps the hot set resident through traffic spikes and background scans. A bad one throws away the hottest keys exactly when a batch job walks through the table.

The idea

An eviction policy is a guess about the future based on the past: which keys are least likely to be asked for next? Each classic policy encodes one assumption.

Least Recently Used (LRU). Evict the key that has gone longest without being accessed. Assumes recent access predicts future access. Implemented with a doubly linked list plus a hash map; every hit moves the key to the front in O(1).

Least Frequently Used (LFU). Evict the key with the fewest accesses. Assumes popularity is stable. Protects long-lived favourites that LRU would drop after a quiet minute, but a key that was hot last week can squat in the cache forever unless counts decay.

First In, First Out (FIFO). Evict the oldest inserted key regardless of use. Trivial and surprisingly competitive on some workloads, but it will evict a hot key simply because it is old.

Random. Evict any key. Cheap, no metadata, and not as bad as it sounds on skewed traffic; Redis's default eviction samples a few keys and picks the best candidate among them, which approximates LRU at a fraction of the bookkeeping.

Time To Live (TTL). Not strictly an eviction policy but usually combined with one: each key expires after a fixed lifetime. TTL bounds staleness; the eviction policy bounds memory.

The failure that matters: scans

LRU's weakness is the scan. A report job reads every row once, each read is a miss that inserts into the cache, and a million one-time keys push the real hot set out of the tail. The next user request misses on everything.

Modern caches fix this with admission and segmentation. W-TinyLFU, used by Caffeine, keeps a small recency window for new keys and only admits a key into the main region if a compact frequency sketch says it is more popular than the key it would evict. A single scan never earns admission. ARC and SLRU split the cache into recently-seen-once and seen-twice segments for the same reason.

	LRU	LFU	W-TinyLFU
Signal	Recency	Frequency	Frequency, with a recency window for new keys
Metadata per key	List pointers	Counter (decayed)	Shared 4-bit sketch, near zero per key
Scan resistance	Poor	Good	Excellent
Adapts to shifting hot set	Fast	Slow unless counts decay	Fast, via the window
Where you meet it	Most hand-written caches, Memcached	Some CDNs, custom caches	Caffeine, Ristretto, modern libraries

Trade-offs

More accurate policies cost more metadata and CPU per access, which matters at millions of operations per second. LRU's O(1) list update is cheap; a frequency sketch is cheaper still per key but harder to reason about. FIFO and random need almost nothing and are fine when the hot set is small and stable.

Eviction interacts with TTL. A long TTL and a small cache means eviction, not expiry, removes most keys, so the policy decides freshness too. A short TTL means most keys expire before eviction gets a vote.

In an interview

Name LRU as the default, then say the one sentence that shows depth: "LRU is fine until a scan evicts the hot set, so for a shared cache I would want scan-resistant admission like TinyLFU, or I would keep bulk reads out of the cache with write-around." Mention that Redis uses approximated LRU by sampling, and that you would set maxmemory with a policy rather than letting the process grow until it is killed.