Algorithms / Redis
Evict a key the way Redis does.
BY THE END, YOU CANExplain why sampling a few keys beats maintaining a perfect recency order.
01 / Try the idea
Redis needs to free one key. It does not scan all ten — it looks at a few at random and evicts the coldest one it saw. Change how many it looks at.
of evictions at this sample size pick the genuinely coldest key, over 400 rounds.
It sampled 5 keys and the coldest key happened to be among them, so this eviction matches true LRU exactly. Run it again — nothing guarantees the next one will.
A fixed, seeded model of the sampling Redis documents — not a running Redis server. Redis 3.0 and later also keep a pool of candidates between rounds, which does better than this.
02 / Check your understanding
Read the idea in plain text
Ten keys are cached. The coldest has been idle for 610 seconds; the hottest for 1 second. Sampling one key at random evicts whatever it happened to look at, so it is barely better than random. Sampling five usually catches something from the cold end. Sampling all ten always evicts the 610-second key — and that is exactly the full scan Redis is avoiding, because reading every key on every eviction is what costs the memory and CPU in the first place.
This is a small teaching model. Use it to reason about a design, then check the details against your own system.
Evict a key the way Redis does.
MockStruct / Quick Learn · 31 October 2026
https://mockstruct.com/learn/lru-eviction-sampling
Your one-minute recap
- True LRU costs memory on every entry, forever — two pointers you cannot amortise away.
- Redis samples a few keys at random and evicts the oldest it saw; more samples, closer to exact.
- An approximation with a tunable error is a legitimate answer, not a shortcut.
Primary source: https://redis.io/docs/latest/develop/reference/eviction/
Built from Redis: Key eviction (read 31 October 2026). Original MockStruct teaching model; no affiliation. Report a correction.