Cache Replacement Policies

Cache Replacement Policies

A cache is a small, fast store that sits in front of a big, slow one (disk, a database, a remote service). It only earns its keep when the item you ask for is already inside it — a hit. When it isn't — a miss — you pay the full slow-path cost. The catch is that a cache is deliberately too small to hold everything: RAM costs money, and the working set is usually far larger than what you can afford to keep hot. So the moment the cache is full and a new item arrives, you must throw something out. The rule that decides which existing entry to evict is the cache replacement (or eviction) policy.

The whole game is prediction under uncertainty: you want to evict the entry you are least likely to need again soon, because every wrong eviction turns a future fast hit into a slow miss. No online policy can see the future, so each real policy is a cheap, computable proxy for "what will be reused." Understanding those proxies — and where each one is fooled — is the core skill an interviewer is testing.

How it works, precisely

Every policy answers one question when the cache is full: given the set of resident keys, which one leaves? The classic families:

• Belady / OPT — the theoretical optimum: evict the item whose next use is furthest in the future. Unimplementable online (needs a crystal ball), but it's the yardstick every real policy is measured against.
• LRU (Least Recently Used) — evict the entry untouched for the longest time. Bets on temporal locality: recently used things tend to be used again. Implemented as a hash map (key → node) plus a doubly linked list; every access unlinks the node and moves it to the head in O(1), evicting from the tail.
• LFU (Least Frequently Used) — evict the entry with the smallest access count. Bets on popularity: hot items stay hot. Needs a frequency counter per key and a way to find the min (buckets or a min-heap).
• FIFO — evict the oldest inserted entry, ignoring usage. A queue; trivially cheap but blind to reuse.
• Random — evict a uniformly random entry. No metadata, lock-free-friendly, surprisingly hard to beat under adversarial patterns.
• TTL — evict on an absolute expiry, orthogonal to the above and usually layered with them.

Modern production caches blend these. LRU-K tracks the last K references to resist one-hit pollution. ARC (Adaptive Replacement Cache) keeps two LRU lists — one for recency, one for frequency — plus ghost lists of recently evicted keys, and shifts capacity between them based on which ghosts get hit. W-TinyLFU (used by Caffeine) fronts a small LRU "window" with an admission filter: a compact frequency sketch decides whether a newcomer is even worth displacing the current eviction victim.

ARC's "shifts capacity" deserves a concrete step, because the follow-up is always how much, decided by what? ARC splits the cache into T1 (recent — seen once) and T2 (frequent — seen at least twice), each shadowed by a ghost list (B1, B2) that remembers keys recently evicted from it, and keeps a target size p for T1. The adaptation rule: a hit in ghost B1 grows p (a recently-evicted one-timer came back — recency is being punished, give it more room); a hit in ghost B2 shrinks p (frequency is being punished). Trace it with cache size 4 and p = 2: T1 = {W, X}, T2 = {Y, Z}, ghost B1 = {A}. Access A → ghost hit in B1 → p increases to 3, and A is fetched and inserted into T2 (it has now been seen twice). The insertion forces an eviction, and the rule is: evict the LRU of T1 when |T1| > p, else the LRU of T2. Here |T1| = 2 ≤ p = 3, so the victim is T2's LRU end (Y) — which is precisely how the freed capacity shifts toward recency. Had T1 instead been over target (say T1 = {V, W, X} with p back at 2, so |T1| = 3 > p), the victim would have been T1's LRU end. ARC is a feedback controller: the ghost lists measure which kind of eviction you are regretting, and p moves toward whichever list is generating regret. (Mechanism per Megiddo & Modha, "ARC: A Self-Tuning, Low Overhead Replacement Cache", USENIX FAST 2003.)

A worked scenario

Say you run a product-catalog API at 50,000 QPS. A cache hit costs ~0.2 ms (in-memory), a miss costs ~8 ms (Postgres + row assembly). Traffic is Zipfian: the top 20% of SKUs drive ~80% of reads. Your cache holds 100,000 of 2,000,000 SKUs — 5% of the catalog.

Do the arithmetic on hit rate. At an 85% hit rate, average latency ≈ 0.85×0.2 + 0.15×8 = 1.37 ms, and the DB sees 50,000×0.15 = 7,500 QPS. Nudge the hit rate to 92% with a better policy and it's 0.92×0.2 + 0.08×8 = 0.82 ms with only 4,000 QPS hitting the DB — a 40% latency drop and nearly half the backend load, from the same memory budget. That delta is exactly what a good replacement policy buys you.

Here LRU does well because popular SKUs are re-touched constantly. But watch what a nightly analytics scan that reads all 2M SKUs once does to LRU: it streams cold keys through the cache, evicting your hot 100k in favor of items used exactly once. Hit rate collapses to near 5% until traffic re-warms it. LFU or W-TinyLFU shrug this off — the scanned keys never accumulate enough frequency to be admitted, so the hot set survives.

Trade-offs: when to use, when not

LRU — the sane default. Use it when access shows temporal locality (session data, recently viewed items, hot rows). It's cheap, O(1), and easy to reason about. Don't use plain LRU when large sequential scans pollute it, or when a truly popular-but-not-recent item keeps getting bumped by bursty newcomers.

LFU — use when popularity is stable over long windows (a CDN edge serving evergreen assets, dictionary/embedding lookups). Don't use naive LFU when popularity shifts: old hits give stale items an unearned high count, freezing them in ("cache ossification"). Mitigate with aged/decaying counters or windowed LFU.

FIFO — use only when metadata cost must be near zero and access is roughly uniform, or as a building block (e.g. FIFO-based S3-FIFO now rivals LRU with less overhead). Don't use it as a general reuse predictor — it ignores hits entirely.

Random — use in massively concurrent caches where LRU's per-access list mutation is a lock-contention bottleneck; eviction needs no global order. Don't use when you need predictable, explainable behavior.

ARC / W-TinyLFU — use when you want near-optimal hit rates that self-tune between recency and frequency and resist scan pollution — this is what Caffeine, RocksDB, and many databases actually ship. Don't reach for them when a plain LRU already saturates your hit rate; the extra sketches and ghost lists add memory and complexity you won't recoup. (Note: ARC's patent history pushed some projects toward LIRS/TinyLFU instead.)

Pitfalls an interviewer probes

• "Why does LRU fail on a scan?" — Be ready to name sequential-flooding / cache pollution and explain the fix (admission control, LRU-K, segmented LRU, or frequency-aware policies). This is the single most common follow-up.
• Hit rate is not the only metric. A policy with a slightly lower hit rate but O(1) lock-free eviction can win under high concurrency because it removes tail-latency spikes. Interviewers love candidates who trade hit rate against contention.
• LRU's hidden write cost. Every read mutates the list, so a read-heavy cache still takes a write lock. Mention striped locks, sampling (Redis' maxmemory-policy allkeys-lru approximates LRU by sampling N keys, not tracking exact order), or CLOCK (an approximate-LRU using a reference bit and a rotating hand).
• Confusing eviction with expiration. TTL bounds staleness; replacement bounds size. They coexist — an entry can be evicted before its TTL, or expire while there's free space.
• Belady's anomaly. For FIFO, adding cache capacity can paradoxically lower the hit rate. Stack algorithms like LRU are immune. A great signal you understand the theory.
• Thundering herd on miss. When a hot key is evicted, many concurrent requests miss and stampede the backend at once — orthogonal to the policy, but solved with request coalescing / single-flight locks. Interviewers slip this in to see if you connect eviction to backend load.

Key takeaways

• A replacement policy is a cheap, computable proxy for future reuse; Belady/OPT is the unbeatable-but-unimplementable yardstick every real policy chases.
• LRU is the right default (temporal locality, O(1)); LFU wins on stable popularity; FIFO/Random trade hit rate for near-zero overhead and low contention; ARC/W-TinyLFU self-tune and resist scan pollution.
• Small hit-rate gains compound hugely: moving 85%→92% can halve backend QPS and cut average latency ~40% on the same memory budget.
• Know the traps: scan pollution, LFU ossification, LRU's read-path write lock (mitigated by sampling/CLOCK), Belady's anomaly, and the thundering herd that eviction can trigger downstream.