Algorithms / Redis
The LRU cache you were asked to implement — and how Redis really evicts keys
The interview answer is a hash map and a doubly linked list. The most deployed cache in the world refuses to pay for it. Here is what it does instead, and why that is the better engineering decision.
“Implement an LRU cache with O(1) get and put.” You know the answer: a hash map for lookup, a doubly linked list for recency, and you move a node to the front on every access. Now open the configuration of the most widely deployed cache in the world. Redis does not do that, and the reason it refuses is more interesting than the question.
Pick a sample size, evict a key, and watch an approximate algorithm converge on the exact answer — without ever computing it.
Open the 5-minute lesson →The version you were asked to build
The textbook structure is genuinely good. The hash map gets you to an entry in constant time. The linked list keeps an exact ordering from most to least recently used, and because you hold a pointer to the node, unlinking it and splicing it back at the front is also constant time. Evicting is just: take the tail.
Notice what you paid for that exactness. Every entry now carries two extra pointers, forever, whether or not it is ever evicted. And every read is secretly a write: a `get` mutates the list. On a single thread that is fine. Under concurrency, that mutation on the hot path is the thing you will end up putting a lock around.
get(key):
node = map[key] # O(1)
if node: move_to_front(node) # O(1), but this is a WRITE
return node.value
evict():
return remove(list.tail) # exactly the least recently usedWhy Redis refuses to pay for it
Redis's documentation is blunt about the trade. It says the reason Redis does not use a true LRU implementation is, in its words, because it “costs more memory”. For a cache holding tens of millions of keys, two pointers per entry is not a rounding error — it is the difference between fitting in RAM and not.
So Redis approximates. When it needs to free space it takes a small random sample of keys and evicts the one with the longest time since last access. Not the oldest key in the database — the oldest key it happened to look at. The number of keys it looks at is a setting, `maxmemory-samples`, which the documentation illustrates with a value of 5. Since Redis 3.0 it also keeps a pool of good eviction candidates between rounds, which pulls the result closer to true LRU without storing an order.
Primary reading: Key eviction · Redis: cache stampede prevention
# the shape of the real thing
evict():
sample = random_keys(maxmemory_samples) # default illustrated as 5
return oldest_by_idle_time(sample) # probably old. not provably oldest.What the approximation actually costs you
It costs you correctness in a specific, bounded way: Redis evicts a key that is probably among the oldest, rather than certainly the oldest. Open the lesson and change the sample size — with one sample you are evicting at random, and by ten you are nearly always taking a key from the genuinely cold end. The error shrinks as you look at more keys, and you pay for each one in CPU rather than in permanent per-entry memory.
That trade is only sensible because of how caches are actually used. Redis's own documentation notes that under a power-law access pattern the difference between true LRU and its approximation was “minimal or non-existent” in simulation. A handful of keys get most of the traffic, and those keys are not the ones a random sample keeps hitting. If your workload is genuinely uniform, LRU of any flavour was never going to help you much anyway.
Recency was only ever a guess
The deeper point hides in the policy list. Redis 4.0 added LFU, which evicts by how often a key is used rather than how recently, and tracks that frequency with a probabilistic counter costing a few bits per object. Redis 8.6 added LRM, which updates the timestamp only on writes, so a key that is read constantly but never modified becomes evictable. Three different models of “which key will I want next”, all approximate, all tunable.
None of them is the correct answer, because there isn't one. LRU is a prediction about the future dressed up as a data structure. Once you see it that way, maintaining a perfect ordering to serve a guess starts to look like precision in the wrong place.
The habit worth taking from this
When you reach for an exact data structure, ask what the exactness is buying and who pays for it. Here, exact ordering costs memory on every entry, on the hot path, forever — and buys you a marginally better guess. Sampling costs a little CPU only at the moment of eviction, and buys you a slightly worse guess. For a cache, that is not a close call.
This is also the difference between an answer that passes an interview and an answer that survives production. Both are correct. Only one of them was designed with a bill attached.
Turn the idea into a small project
Implement both: the hash map plus doubly linked list, and the sampling version. Generate a Zipfian workload so a few keys are genuinely hot. Then measure two things the interview never asks about — bytes of overhead per entry, and hit rate at a fixed memory budget rather than a fixed key count. The sampling cache gets to hold more keys in the same RAM, and that is where it wins.
What would you have to measure to know whether true LRU is worth two extra pointers on every entry in your cache?
Test your understanding →