Eviction is sampled, not exact

Scene 05 · Eviction is sampled, not exact

maxmemory + sampled LRU/LFU — Redis only inspects N keys per pass; tunable via `maxmemory-samples`.

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

Diagram

A grid of keys, each cell showing its size, idle-time, and access-count badges. On the right, the maxmemory bar fills as new writes land. When it crosses the line, the sampler highlights N random cells (you control N), scores them by the active policy (LRU / LFU), and the worst one fades out — eviction is approximate by design, never a perfect global pick.

Sources

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

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

PreviousPersistence — fork, CoW, and the 1-second window NextTTL and cleanup — lazy, active, and the freer thread