Modelled on src/evict.c, Redis 7.2.14, with the LRU/LFU field handling from src/object.c and src/db.c and the defaults from src/config.c.
Every maxmemory-policy except noeviction and the two random ones picks its
victim from a sample, not from the whole keyspace. This page runs the real selection path — the same
sampling, the same 16-entry pool, the same probabilistic LFU counter — so you can watch it evict a key
it should not have, which is what approximation actually costs.
Empty. Run a command to fill it.
Sorted ascending by score, best candidate on the right (src/evict.c:44–47). Each entry holds the score from when it was sampled. Nothing recomputes it.
Scanning every key to find the true oldest is O(N), and Redis will not pay that on the command path.
Each eviction instead samples maxmemory-samples keys (src/evict.c:150), scores them, and
merges them into a 16-entry pool kept sorted by score (src/evict.c:188–215). The pool is then walked
from its best end and the first key that still exists is evicted (src/evict.c:605–627) —
existence is the only thing rechecked. A key whose entry is gone from the keyspace is what the source calls
a ghost; it is dropped and the walk continues.
The score in the pool is a snapshot. It is never recomputed, so a key read a moment after it was sampled can still be evicted on the strength of an idle time that is no longer true. Press GET on a key sitting in the pool and then force an eviction to see it happen.
Every command runs performEvictions() first (src/server.c:3989), reads included.
Rank is computed against every eligible key, scored fresh. Rank 1 means the sample happened to contain the key true LRU/LFU/TTL would have chosen.
LRU moderobj.lru holds LRU_CLOCK(), a wall-clock second count masked to 24 bits. LRU_CLOCK_RESOLUTION is 1000 ms (src/server.h:895), so idle time is only ever accurate to a second. 2^24 seconds is about 194 days, after which the clock wraps; estimateObjectIdleTime (src/evict.c:92–99) compensates for exactly one wrap and scores anything idle longer than that wrongly. · LFU modeThe same 24 bits split: high 16 are the last-decrement time in minutes, low 8 are the frequency counter (src/evict.c:320–321, src/server.h:903–905). The counter is not a hit count — see the notes below.
One field, two meanings. Switching policy mid-run reinterprets what is already stored rather than rewriting it, which this page reproduces.
A new key starts at LFU_INIT_VAL = 5 (src/object.c:53–63, src/server.h:3411).
Each access increments it only with probability 1 / ((counter - 5) * lfu-log-factor + 1)
(src/evict.c:299–307), so the climb from 5 to 6 is certain and the climb from 200 to 201 almost never
happens. It saturates at 255 (src/evict.c:300). Reading it subtracts one unit per elapsed
lfu-decay-time period (src/evict.c:319–326) without writing the result back, so a key
that stops being read sinks on its own. The pool stores 255 - counter so that
low frequency sorts as a high eviction score (src/evict.c:181).
The block comment at src/evict.c:274–277 says the counter is halved on decay. The code at src/evict.c:322–324 subtracts one unit per elapsed period. This page follows the code.
It is in the same pool branch as LRU and LFU (src/evict.c:582–583) and scores sampled keys
ULLONG_MAX - expire-time (src/evict.c:184), so the nearest expiry wins — among the
sampled keys only. A key expiring in one second routinely survives while one expiring in an hour is
evicted, because the first was never in the sample. Set the policy to volatile-ttl, drop
maxmemory-samples to 1 and the accuracy readout collapses.
performEvictions() returns EVICT_FAIL under noeviction
(src/evict.c:556–558) and when nothing eligible is left to evict (src/evict.c:717–719). The caller
turns that into -OOM command not allowed when used memory > 'maxmemory'.
(src/server.c:1870–1871) but only for commands flagged CMD_DENYOOM
(src/server.c:4001, 4015–4016). GET is not one of them, so reads keep working against a
full instance — and still trigger the eviction attempt on the way in.
Memory is counted in keys, not bytes, so one key is always exactly the amount a single overflowing write
needs to free; the real loop compares mem_freed against a computed mem_tofree
(src/evict.c:573). There is one database here, so the per-database round-robin at src/evict.c:594–600
and src/evict.c:640–650 collapses to a single pass. Sampling is modelled as uniform random draws,
distinct within one call; the real dictGetSomeKeys walks the hash table instead, so its
spread is its own. Nothing dedupes the pool either way (src/evict.c:191–215), so a key sampled on two
separate rounds holds two slots with two different scores — you will see that happen.
Expiry removes a key the moment its TTL passes rather than through the active expire cycle.
Each command advances the simulated clock 250 ms so you do not have to wait in real time, which means
four consecutive commands land in the same LRU second and are genuinely indistinguishable to
allkeys-lru — that tie is not an artefact, it is what
LRU_CLOCK_RESOLUTION costs you.
Because eviction runs before a command rather than after, the keyspace sits one key over the limit
until the next command arrives (src/server.c:3988) — that lag is real, not a rendering delay.