One question that recently made me rethink cache eviction was:
If Redis uses LRU, why doesn't it maintain a heap (or a perfectly sorted list) of keys?
The answer comes down to optimizing the common case.
The Problem
Imagine a Redis instance with 10 million keys.
If Redis maintained a perfect LRU structure, every cache hit would need to update it:
GET user:123
↓
Update LRU ordering
↓
Return value
Even though the lookup is O(1), updating a heap would be O(log n), and maintaining a doubly-linked LRU list would still require modifying shared metadata on every single read.
For a cache serving millions of requests per second, that's expensive.
Redis's Approach: Approximate LRU
Instead of maintaining an exact ordering, Redis uses random sampling.
When memory is full and a write arrives:
- Randomly sample a small number of keys (default: 5).
- Find the least recently used among them.
- Evict that key.
At first glance, this seems inaccurate.
What if all 5 sampled keys are hot?
It's possible—but statistically very unlikely for most real-world workloads.
The Clever Optimization: Eviction Pool
Redis goes one step further.
Instead of discarding the remaining sampled keys after each eviction, it keeps the best eviction candidates in a small eviction pool (16 entries internally).
Example:
Iteration 1
------------
Sample: A B C D E
Pool:
A B C D E
Evict A
Remaining Pool:
B C D E
Need more memory?
Iteration 2
------------
Sample:
F G H I J
Merge:
B C D E F G H I J
Keep only the best candidates
Evict the worst one
The pool gradually accumulates better eviction candidates while still sampling only a handful of random keys each iteration.
Why This Works
Redis optimizes for the common case:
- Millions of GETs
- Relatively few evictions
Instead of paying a maintenance cost on every read, Redis does a small amount of work only when memory is exhausted.
This is a classic systems engineering trade-off:
Accept a near-perfect approximation during rare events to keep the hot path extremely fast.
That's one of the reasons Redis continues to scale so well while delivering cache hit rates that are remarkably close to a true LRU implementation.