Cache eviction: why LRU fails under bursts
This is the most common follow-up to any caching answer: "You said you'd use a cache with LRU. What happens when a link goes viral, or a crawler sweeps your long tail?" The answer is cache pollution, and knowing the mechanism precisely — and its fix — is one of the highest-value pieces of depth you can carry into an interview.
1. How LRU actually works
A standard LRU cache is a hash map plus a doubly-linked list:
HEAD (most recently used) TAIL (evicted next)
┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐
│ K7 │◄─►│ K3 │◄─►│ K9 │◄─►│ K1 │◄─►│ K4 │◄─►│ K8 │◄─►│ K2 │
└────┘ └────┘ └────┘ └────┘ └────┘ └────┘ └────┘
- Hit: move the node to the head. O(1).
- Miss: fetch from the origin, insert at the head. O(1).
- Full: evict the tail. O(1).
LRU encodes exactly one assumption: recency implies importance. If something was read just now, it will probably be read again soon. For steady-state traffic with temporal locality that assumption is excellent, which is why LRU is everywhere.
2. The failure: cache pollution
Two access patterns coexist in almost every real system:
- A steady-state hot set — keys read continuously, day after day. A shortener's marketing links, a feed service's popular posts, a config blob read on every request.
- A burst of one-hit-wonders — a crawler sweeping 100,000 cold URLs, a backfill job, a scanner, or a flood of genuinely new items during an event.
Here is the failure, step by step:
Step 1 — the burst arrives.
100,000 distinct cold keys are requested within a few seconds.
Step 2 — LRU admits every one of them at the HEAD.
A miss is treated as "most recently used" by definition. There is no
distinction between "read once, ever" and "read ten thousand times a day."
Step 3 — the hot set drifts toward the TAIL.
Keys read continuously for a month, but not in the last 400 milliseconds,
are now behind 100,000 keys that will never be read again.
Step 4 — the hot set is evicted.
Memory is full, so eviction takes from the tail: the valuable keys.
Step 5 — the cascade.
A second later, normal traffic returns for the hot keys. Every request is
now a miss. The origin database receives the full unfiltered load at once,
latency climbs, the cache churns, and hit rate does not recover for minutes.
The damage is not the burst itself — the burst was going to miss anyway. The damage is that the burst destroyed the value of the cache for everything else. This is why the term is pollution: the cache is full of data with no future value.
The formal property LRU lacks is scan resistance: the ability to survive a sequential sweep of items that will not be re-referenced.
3. The fix: admission control
The insight is that eviction is the wrong place to solve this. By the time you are choosing a victim, the bad key is already in. The fix is to ask a different question before insertion:
"Is this candidate more likely to be accessed again than the victim I would have to evict to make room for it?"
If the candidate has been seen once and the victim has been seen fifty times, do not admit the candidate at all. This is TinyLFU, and the practical version used in production caches is W-TinyLFU.
Counting frequencies without storing keys
Answering "how often have I seen this key recently?" naively requires a counter per key — which is as large as the cache you are trying to protect. Instead, use a Count-Min Sketch: a fixed-size 2D array of small counters, indexed by several hash functions.
class FrequencySketch:
"""4-bit counters. For a 1M-entry cache, ~4 MB of sketch protects
hundreds of MB of cache. The estimate never undercounts."""
def __init__(self, width=1 << 20, depth=4):
self.table = [[0] * width for _ in range(depth)]
self.width, self.depth = width, depth
self.size, self.reset_at = 0, width * 10 # sample size before halving
def increment(self, key):
for i in range(self.depth):
j = hash_i(key, i) % self.width
if self.table[i][j] < 15: # saturate at 4 bits
self.table[i][j] += 1
self.size += 1
if self.size >= self.reset_at:
self._age() # the sliding-window mechanism
def estimate(self, key) -> int:
# Minimum across rows: every cell may have collided upward.
return min(self.table[i][hash_i(key, i) % self.width] for i in range(self.depth))
def _age(self):
# Halve every counter. Frequency becomes RECENT frequency rather than
# all-time frequency, so yesterday's hot key eventually loses its claim.
for row in self.table:
for j in range(len(row)):
row[j] >>= 1
self.size //= 2
Two properties make this work at negligible cost. 4-bit counters are enough — you only need to compare relative frequencies, not measure them, and the sketch is tiny. Periodic halving is what makes it a sliding window: without it, a key that was popular last month would block a key that is popular now, and the cache would ossify.
The admission decision
boolean admit(K candidate, K victim) {
int candidateFreq = sketch.estimate(candidate);
int victimFreq = sketch.estimate(victim);
if (candidateFreq > victimFreq) return true;
// Anti-adversarial: an attacker who knows the scheme could craft keys that
// always lose. A small random admission chance keeps that attack ineffective,
// and costs almost nothing in hit rate.
return candidateFreq >= 3 && random.nextInt(100) < 1;
}
Now the burst plays out completely differently:
Crawler requests cold key X. sketch.estimate(X) = 1
Eviction victim is hot key H. sketch.estimate(H) = 47
1 > 47 is false -> X is NOT admitted. H stays. The hot set survives intact.
Why the "W" in W-TinyLFU
Pure TinyLFU has one flaw: a genuinely new hot key — a post that just went viral, a link that just launched — starts with frequency 1 and can never get admitted, because every resident key beats it. The cache becomes unable to learn.
W-TinyLFU fixes this with a small window cache in front:
┌──────────────────────────────────┐
new ───►│ Window LRU (≈1% of capacity) │ everything enters here
└───────────────┬──────────────────┘
│ evicted from window
▼
┌─────────────┐
│ TinyLFU │ admission decision vs the main victim
│ admission │
└──────┬──────┘
admit │ reject
▼ └──► discarded
┌──────────────────────────────────┐
│ Main SLRU (≈99% of capacity) │
│ probation 20% | protected 80%│
└──────────────────────────────────┘
Every key gets a brief chance in the window. A key accessed twice in quick succession builds frequency there and then wins admission to the main cache. A one-hit-wonder passes through the window and is discarded without ever displacing anything valuable.
4. The simpler alternatives
You do not always need W-TinyLFU. Two simpler structures get most of the benefit and are worth knowing by name.
Segmented LRU (SLRU) / 2Q
Split the cache into two lists:
Probationary (A1) ──promoted on 2nd access──► Protected (A2)
new keys enter here only twice-accessed keys
evicted from here first evicted only when A2 is full
A burst of single-request keys churns entirely within the probationary segment and never touches the protected segment. This is scan resistance with no sketch, no hashing, and about twenty lines of code — and it is why allkeys-lru in Redis is actually an approximated LRU with sampling, while allkeys-lfu maintains a counter with decay, which is Redis's answer to the same problem.
The near-cache guard
Often the best answer is architectural rather than algorithmic: put a small in-process cache (Caffeine, Ristretto) in front of the distributed cache. The viral key is served entirely from the application server's own RAM, so the burst never reaches Redis at all, and the distributed cache's eviction policy stops being the thing standing between you and an outage. See distributed cache §4.4.
5. How to choose
| Policy | Scan-resistant | Memory overhead | Complexity | Use when |
|---|---|---|---|---|
| LRU | No | Minimal | Trivial | Uniform-ish traffic, no scans, no bursts |
| LFU (pure) | Yes | Counter per key | Low | Very stable popularity; suffers from ossification |
| SLRU / 2Q | Yes | Minimal | Low | You want scan resistance with no sketch |
| W-TinyLFU | Yes | ~4 bits/entry sketch | Library | The default for a general-purpose cache |
| ARC | Yes | Two ghost lists | Medium | Adaptive workloads; patent history complicated adoption |
| S3-FIFO | Yes | Minimal | Low | Modern, simple, competitive with W-TinyLFU |
On real Zipfian workloads, W-TinyLFU typically buys 5–15 percentage points of hit rate over LRU. At a 95% baseline, moving to 98% cuts origin load by 60% — which is the number worth quoting, because hit rate improvements compound into origin-capacity savings non-linearly.
6. What to say in an interview
"I'd use a cache with admission control, not just eviction — Caffeine or Ristretto, which implement W-TinyLFU. Plain LRU isn't scan-resistant: a crawler sweeping cold keys, or a burst of new items, enters at the head and evicts the steady-state hot set, so a moment later the valuable traffic all misses at once and hits the database in a thundering herd. W-TinyLFU keeps a Count-Min Sketch of recent frequencies — about 4 bits per entry — and refuses to admit a candidate that is less frequent than the key it would evict. The sketch is halved periodically so it tracks recent frequency rather than all-time, and a small window cache in front lets genuinely new hot keys break in. If I wanted something simpler, segmented LRU gets most of the scan resistance for twenty lines of code."
Follow-ups you should be ready for:
- "What if the attacker knows your admission policy?" → the small random admission probability, plus the fact that the sketch is keyed by a hash they cannot control precisely.
- "How do you size the sketch?" → roughly 10× the cache's entry count in counters, at 4 bits each; it is small relative to the values being cached.
- "Does this help with a single hot key?" → No. Admission control fixes pollution; a single key hotter than one node's capacity is a different problem, solved by a near-cache or key replication.