Cache Replacement — How Each Policy Actually Works
The real question: how do you evict in O(1)?
“This policy evicts the X item” is the what. The useful part is how each one is built, because a cache needs lookup, recency/frequency update, and eviction to all be fast. Below, every policy — not just LRU — with its actual data structure.
See all three on the same trace
Before the details, build intuition: the debugger below runs one access trace through LRU, LFU, and FIFO side by side. Switch the workload and predict, on each full-cache miss, which key gets evicted — then watch the hit rates diverge. There is no universally best policy; each wins on a different access pattern.
LRU — Least Recently Used (the diagram above)
Structure: a hash map key → node for O(1) lookup + a doubly-linked list ordered by
recency (head = newest, tail = oldest). Doubly-linked so any node can be unlinked and moved to the head in O(1).
- GET(k): map finds the node → unlink it → move to head → return value.
- PUT(k,v): insert at head; if full, remove the tail node and delete its map key.
cap=3: put A,B,C → [C,B,A] get A → [A,C,B] put D → evict tail B → [D,A,C]
LFU — Least Frequently Used
Evicts the item with the fewest accesses. The naive “scan for the minimum count” is O(n); the O(1) design uses frequency buckets:
- hash map
key → (value, freq); - a second map
freq → doubly-linked list of keys at that frequency; - a
minFreqcounter.
On access: move the key from its freq=f bucket to the f+1 bucket (it got used
once more); if the f bucket emptied and was minFreq, bump minFreq.
On evict: remove the tail of the minFreq bucket. All O(1).
access counts: A:1 B:3 C:1 → minFreq=1, bucket[1]={A,C}
evict → drop the oldest in bucket[1] (e.g. A). B (freq 3) is safe.
Use when popularity is stable (a few keys are always hot) and recency misleads.
FIFO — First In, First Out
Evicts the oldest inserted, ignoring usage entirely. Structure: a plain queue — enqueue on insert, dequeue the front on eviction. Cheap, but a frequently-used old item gets evicted just for being old.
Random
Evicts a random entry. Structure: an array of entries + a random index. Zero bookkeeping, O(1), and — surprisingly — competitive at large scale where access is fairly uniform.
MRU — Most Recently Used
The opposite of LRU: evicts the head (the just-used item). Same hash-map + linked-list structure as LRU, but you drop from the head. Use when a recently-seen item is least likely to recur — e.g. a one-pass scan over a file, where you won’t revisit what you just read.
Side by side
| Policy | Evicts | Built from | Cost | Best when |
|---|---|---|---|---|
| LRU | Oldest-used (tail) | Hash map + doubly-linked list | O(1) | Default — recency predicts reuse |
| LFU | Fewest-used | Map + freq buckets + minFreq | O(1), more memory | Stable hot set |
| FIFO | Oldest-inserted | Queue | O(1), cheapest | Simple; usage doesn't matter |
| Random | A random entry | Array + RNG | O(1), no state | Uniform access, huge scale |
| MRU | Most-recently used (head) | Hash map + linked list | O(1) | One-pass scans |
Refresh-ahead — beat the expiry latency spike
Normally a TTL expires and the next request eats the slow refill (a spike; a stampede on a hot key). Refresh-ahead renews popular entries in the background before they expire, so reads stay warm — applied only to predictably hot keys (or you waste refreshes).
Takeaways
- LRU = map + doubly-linked list (O(1) lookup/reorder/evict-tail) — the default.
- LFU = frequency buckets + minFreq; FIFO = queue; Random = array; MRU = LRU but evict the head.
- Pick by access pattern; pair with the memory & cache-sizing playbook (size for the hot 20%).
Re-authored from-scratch; diagram hand-authored (SVG) for this guide.
🤖 Don't fully get this? Learn it with Claude
Stuck on Cache Replacement — How Each Policy Actually Works? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Build the mental picture, not memorization.
I just read a lesson on **Cache Replacement — How Each Policy Actually Works** (System Design) and want to truly understand it. Explain Cache Replacement — How Each Policy Actually Works from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Socratic — adapts to where you're stuck.
Teach me **Cache Replacement — How Each Policy Actually Works** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Active recall exposes what you missed.
Quiz me on **Cache Replacement — How Each Policy Actually Works** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Intuition + hook + flashcards for long-term memory.
Help me remember **Cache Replacement — How Each Policy Actually Works** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.