Algorithms / Redis

Evict a key the way Redis does.

~5 minutesKnow what a hash map isFree to explore

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.

session:8f2aidle 2ssampled
cart:1049idle 390s 
user:221idle 11s 
feed:homeidle 1s 
price:SKU-77idle 240s 
session:3c91idle 95ssampled
user:884idle 610sevicted
search:shoesidle 48s 
cart:2290idle 175ssampled
token:refreshidle 7ssampled
51% exact

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

Why does Redis sample a few random keys instead of keeping an exact recency order?

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

  1. True LRU costs memory on every entry, forever — two pointers you cannot amortise away.
  2. Redis samples a few keys at random and evicts the oldest it saw; more samples, closer to exact.
  3. An approximation with a tunable error is a legitimate answer, not a shortcut.

Primary source: https://redis.io/docs/latest/develop/reference/eviction/

03 / Connect the dots

See the engineering behind the idea.

Read the full explainer →
Next lesson →

Built from Redis: Key eviction (read 31 October 2026). Original MockStruct teaching model; no affiliation. Report a correction.