Scene 05

Eviction is sampled, not exact

When maxmemory is exceeded Redis picks maxmemory-samples random keys and evicts the worst — so 'LRU' is approximate and tunable, not a doubly-linked list.

Previously

Persistence keeps data across crashes. But while the process is RUNNING and used_memory rises past maxmemory, someone has to go — and Redis doesn't actually keep a perfect LRU list.

Scene 05

Eviction is sampled, not exact

Watch
Try it
Predict
Capture

What to watch for

Hot keys (top row) get touched repeatedly while a stream of cold writes pushes used memory past maxmemory. When that happens Redis picks maxmemory-samples random keys, highlights them, and evicts the worst one — most hot keys survive, but not all.

Implementation

Highlighted lines are the ones running in the diagram right now.

freeMemoryIfNeeded

called before every write; evicts until under maxmemory

1def freeMemoryIfNeeded():
2    if policy == 'noeviction':
3        return OK  # caller checks separately
4    while used_memory() > maxmemory:
5        victim = pickVictim()
6        if victim is None:
7            return Error('cannot free memory')
8        evict(victim)        # del + propagate to AOF/replicas
9        used_memory_subtract(sizeof(victim))
10    return OK

pickVictim (sampled LRU/LFU)

N random keys, evict the worst — not a global scan

1def pickVictim():
2    pool = candidate_pool  # carries near-misses across passes
3    samples = random_sample(keyspace, maxmemory_samples)
4    for k in samples:
5        pool.insert(k, score=lru_or_lfu(k))
6    # worst = highest idle time (LRU) or lowest counter (LFU)
7    return pool.pop_worst()

noeviction.handleWrite

the rejection path when memory is full

1def handleWrite(cmd, value):
2    if used_memory() + sizeof(value) > maxmemory:
3        return Error(
4            'OOM command not allowed when used '
5            'memory > maxmemory'
6        )
7    # reads (GET, EXISTS, ...) keep serving normally
8    apply(cmd, value)
9    return OK

Sources

Where this sits in Build Redis

Scene 05 of 10, in the Memory act — Persistence, eviction, TTL — what makes RAM disappear.. maxmemory + sampled LRU/LFU — Redis only inspects N keys per pass; tunable via `maxmemory-samples`.

Up next. TTL & cleanup — eviction fires under memory pressure. The OTHER cleanup path is the clock: TTLs expire whether you're full or not.

All 10 scenes in Build Redis · Every curriculum

Designs that use this

Built with Arqly

Every scene in Build Redis builds on the one before it.All 10 Build Redis scenes