Start here: the victim-selection problem#
TL;DRthe 30-second version
- A full cache has to evict one entry to admit a new one. The eviction policy picks the victim. It is a bet about which entry you're least likely to need again soon.
- LRU (Least Recently Used) bets on recency: evict whatever has gone untouched longest. It is a hash map plus a doubly-linked list, and every operation is O(1).
- LFU (Least Frequently Used) bets on frequency: evict whatever has been used the fewest times. The O(1) form keeps one list per use-count plus a minFreq pointer, so it never scans for the minimum.
- Neither wins everywhere. A one-time scan floods LRU with cold data. Plain LFU clings to last week's hot keys unless the counts age.
- Real systems mostly run cheaper approximations or hybrids: CLOCK, segmented LRU (Memcached), ARC (ZFS), and W-TinyLFU (Caffeine). Redis exposes the choice as a config knob.
A cache trades memory for speed. You keep hot data close so you don't re-fetch it from something slower, like a disk, a database, or a network call. But memory is finite. Once the cache is full, every insert needs a victim. The rule that picks the victim is the eviction policy. A bad rule evicts data you're about to ask for again, and that miss is the whole cost.
There is a provably best answer, and you can't use it. Bélády's algorithm evicts the entry whose next use is furthest in the future. It gives the fewest misses of any policy. The catch is that it needs to know the future. So every real policy guesses the future from the past. The two simplest guesses are 'what I used recently, I'll use again' (that's LRU) and 'what I use often, I'll keep using' (that's LFU).
These guesses work because real access streams have structure. A key touched now tends to be touched again soon. And a small fraction of keys take most of the traffic. A cache only beats random eviction because the workload has that structure.
LRU: evict whoever you haven't touched in the longest time#
LRU keeps two structures. A hash map from key to node gives you O(1) lookup. A doubly-linked list, kept in recency order, gives you O(1) reordering. The most recently used entry sits at the head. The least recently used sits at the tail. The tail is always the next victim.
- GET key: look it up in the map. Miss → done. Hit → unlink its node, relink it at the head, and return the value.
- PUT key=value, key exists: update the node's value, then move it to the head exactly like a GET hit.
- PUT key=value, new key, below capacity: create a node, link it at the head, add it to the map.
- PUT key=value, new key, at capacity: unlink the tail node, remove it from the map, then insert the new node at the head and in the map.
PredictCapacity is 3 and the cache holds [A, B, C] with C the most-recently-used. You GET A, then PUT D. Under LRU, which key gets evicted?
Hint: LRU evicts whichever key has gone untouched the longest.
B. The GET A just made A recently used, so the least-recently-used entry is now B. It gets pushed out to make room for D.
LFU: evict whoever's been touched the fewest times#
LFU asks a different question: how many times has this key been used? A key hit 100 times an hour ago beats a key hit once a second ago. That is the opposite of what LRU would decide. The naive way to find the least-used key is to scan every entry for the minimum count, which is O(n). The O(1) version avoids the scan with three maps: key to value, key to frequency, and frequency to a list of the keys at that count. One extra pointer, minFreq, always names the lowest count that has any keys in it.
front = newest at that frequency, back = oldest · minFreq names the lowest occupied bucket
- GET key (hit) or PUT on an existing key: read its frequency f, remove it from bucket[f], push it to the front of bucket[f+1], and record f+1.
- If bucket[f] is now empty and f was minFreq, bump minFreq to f+1.
- PUT a new key below capacity: insert it at the front of bucket[1], and reset minFreq to 1. A fresh key is always the new floor.
- PUT a new key at capacity: evict the back entry of bucket[minFreq], remove it from all maps, then insert the new key as above.
The two policies store the same data and differ only in the question they ask. So the same access stream can send them after different victims. Capacity is 4, the cache is full with A, B, C, D, and a new key X arrives. Recent accesses, oldest to newest: A A A A B C D.
| Policy | Question it asks | Victim on this stream |
|---|---|---|
| LRU | touched longest ago? | A — B, C, and D were all touched more recently |
| LFU | used fewest times? | counts A:4, B:1, C:1, D:1 → evict B (the B/C/D tie broken toward the least-recently-touched) |
Cost: time, and the memory tax of pointers#
Both policies hit the goal. Every operation is O(1) on average. The 'on average' comes from the hash map, which occasionally rehashes. The list and bucket moves touch a fixed number of pointers, so they are O(1) every time. The per-request cost does not grow as the cache fills.
| LRU | LFU (O(1) form) | |
|---|---|---|
| GET (hit) | O(1): map lookup + move node to head | O(1): lookup + move node to next freq bucket |
| PUT (new) | O(1): insert at head, maybe drop tail | O(1): insert in bucket[1], maybe evict from bucket[minFreq] |
| Eviction | O(1): the tail is always the victim | O(1): back of bucket[minFreq] is always the victim |
| Per-entry metadata | 2 pointers (prev/next) + map entry | 2 pointers + frequency counter + bucket membership + map entry |
The cost people forget is memory. A list node carries two pointers, 16 bytes on a 64-bit machine, on top of the key, the value, and the map entry. For a cache of 8-byte integers keyed by 8-byte integers, the bookkeeping outweighs the data. LFU adds a frequency counter and a bucket membership per entry. That overhead is why production systems often use approximate policies. One reference bit per entry, or a few sampled keys, buys most of LRU's hit rate for a fraction of the memory. Chasing pointers through a linked list is also unfriendly to the CPU's own cache, which is one more reason array-backed CLOCK shows up in high-performance systems.
The recency bet vs the frequency bet
Each policy is right exactly when its assumption holds. LRU assumes the thing you touched most recently is the thing you'll touch next. That holds for a user's current session, or the pages of a file you're scrolling. LFU assumes a small set of items is durably hot and the rest is noise. That holds for the top trending videos, a handful of celebrity profiles, or hot product pages.
The sharpest practical difference is scan resistance. A scan reads a large set of items exactly once. LRU has no defence: every scanned item looks maximally recent, so the scan marches your real working set out the tail. LFU resists scans naturally, because a scanned item only ever reaches frequency 1 and is evicted before it can displace a hot key. This one property is why almost every serious policy (2Q, ARC, segmented LRU, W-TinyLFU) blends in a frequency or second-chance signal.
Policies side by side
| Policy | Recency | Frequency | Scan-resistant | Per-entry overhead |
|---|---|---|---|---|
| FIFO | No (insertion order only) | No | No | Minimal (queue link) |
| Random | No | No | Partially (by luck) | None |
| LRU | Yes (primary) | No | No | 2 pointers + map |
| LFU | Tie-break only | Yes (primary) | Yes | Pointers + counter + buckets |
| CLOCK | Approximate | No | No | 1 reference bit |
| ARC | Yes (adaptive) | Yes (adaptive) | Yes | 2 lists + 2 ghost lists |
| W-TinyLFU | Window only | Yes (aged sketch) | Yes | Sketch (shared, tiny) |
Read the table top to bottom. The top rows are cheap and blind. CLOCK approximates LRU with one reference bit per entry and a sweeping hand that gives each entry a second chance. ARC keeps one LRU list for keys seen once and one for keys seen twice, and uses ghost lists of recently evicted keys to shift capacity toward whichever list is missing more. W-TinyLFU estimates frequency with a tiny shared sketch, halves the counters periodically so old popularity fades, and only admits a new key if it is more frequent than the entry it would evict. For an interview, placing LRU and LFU on this spectrum, and naming what the smarter policies add, is worth more than a flawless re-derivation of either.
Where these policies actually run
- Redis exposes the policy as the maxmemory-policy config: noeviction, allkeys-lru, allkeys-lfu, allkeys-random, and the volatile-* variants that only evict keys with a TTL. Its LRU and LFU are both approximate. It samples a handful of keys (default 5) and evicts the best of the sample rather than keeping a true global order. Its LFU uses an 8-bit Morris counter plus a configurable decay period so counts age.
- Memcached was a straightforward LRU. Since 1.5 it runs a segmented LRU with HOT, WARM, and COLD sub-lists, so a one-time scan only pollutes the first segment.
- Caffeine (Java) is the reference W-TinyLFU implementation and the default cache across much of the JVM ecosystem, including Spring. It beats LRU, LFU, and ARC on real traces while staying highly concurrent.
- The Linux page cache keeps two LRU lists, active and inactive, which is an approximation of segmented LRU. Older kernels used CLOCK.
- CPU caches can't afford true LRU in hardware, so they use pseudo-LRU (a tiny tree of bits) or random replacement within a set.
Database buffer pools (PostgreSQL's clock-sweep, InnoDB's midpoint-insertion LRU), CDN edge caches, browser caches, and DNS resolver caches are all the same shape: a fixed-size map plus a victim rule.
How each one fails in production
- LRU cache pollution from a bulk scan. A backup job, an analytics query, or a crawler reads every row once. Each read looks 'most recent', so LRU keeps all of it and evicts the real working set. When the scan ends, the hit rate craters until the hot keys are re-warmed. This is the most common LRU outage.
- LFU stale-hot keys. A product that went viral last month keeps a huge count and refuses to leave. New hot keys can't build enough count to displace it. The fix is frequency decay. The bug is shipping textbook LFU without it.
- LFU new-key starvation. A brand-new key enters at frequency 1, the lowest possible, so it is first in line for eviction. In a busy cache it can be evicted before it ever gets a second hit. W-TinyLFU's admission window exists to give newcomers a probation period.
- Cold start. Right after a restart the cache is empty, so every request misses and hits the backing store at once. Neither policy helps here. This is about cache warming and request coalescing, not eviction.
In an interview
Lead with the O(1) constraint. It is what forces the data structures. For LRU: hash map plus doubly-linked list. For LFU: a value map, a frequency map, and a frequency-to-keys structure where each bucket is an LRU list, plus a minFreq pointer. If you can explain why minFreq only ever goes up by one or resets to one, you've shown you understand why the whole thing is O(1).
Justify the choice with the workload. LRU for general-purpose caching where recent access predicts future access, like most HTTP or database caches. LFU when some keys are durably hotter regardless of when they were last touched. Then name the failure modes unprompted: LRU's scan pollution, LFU's stale keys without aging. If it goes deeper, drop one real anchor: Redis samples, Memcached segments, ZFS uses ARC, Caffeine uses W-TinyLFU.
Why a doubly-linked list instead of an array?
Moving a just-touched item to the front has to be cheap. In an array that's an O(n) shift. In a doubly-linked list you repoint a couple of neighbour pointers, which is O(1) no matter how big the list is. It must be doubly linked so you can splice a node out without walking the list to find its predecessor.
Isn't LFU always better than LRU, since it counts real usage?
No. Textbook LFU clings to keys that were popular long ago, because raw counts never decrease without aging, and it starves new keys that enter at frequency 1. LRU adapts instantly but a one-time scan can wipe its working set. That's why production systems use hybrids like ARC and W-TinyLFU.
How does LFU break a tie between two keys with the same count?
By recency. Each frequency bucket is itself an LRU list, so among keys with the same count the one untouched longest is evicted first.
A nightly backup reads every row once through an LRU cache. What happens?
Every row looks most recently used, so the scan evicts the hot working set out the tail. The hit rate collapses during the scan and stays low until the hot keys are re-warmed. Scan-resistant policies fix it: LFU, 2Q, segmented LRU, ARC, W-TinyLFU. A once-read row never builds enough frequency to displace hot data.
References & further reading
- Megiddo & Modha — ARC: A Self-Tuning, Low Overhead Replacement Cache (USENIX FAST 2003) — the adaptive recency/frequency cache used in ZFS
- Einziger, Friedman & Manes — TinyLFU: A Highly Efficient Cache Admission Policy — the frequency-sketch admission filter behind W-TinyLFU / Caffeine
- Redis — Key eviction (maxmemory-policy, approximate LRU/LFU, Morris counter) — how a real system samples instead of maintaining true order
- Caffeine Wiki — Efficiency (W-TinyLFU vs LRU/LFU/ARC on real traces) — hit-rate comparisons that motivate adaptive policies