Redis's allkeys-lru eviction policy is documented as an *approximated* LRU. When Redis needs to free memory, how does it actually pick a victim key, and what does the maxmemory-samples setting control?
answer
- no global LRU list, 24 bits in the object header
- random sample, evict the idlest of the sample
- default maxmemory-samples 5, 10 near-exact
- volatile-* samples only the expires dict
- eviction runs in the command path, not a timer
basics
~20 sRedis keeps no global LRU list. When memory exceeds maxmemory it picks maxmemory-samples random keys (default 5), reads the last-access timestamp stored in each key's object header, and evicts the idlest. More samples means better accuracy and more CPU.
solid answer
~50 sExact LRU needs a doubly-linked list over every key plus a relink on every access: extra pointers per object and cache-hostile pointer chasing. Redis instead stores a 24-bit clock field in each object header, refreshed on every lookup, and *samples*. When a command would push memory above `maxmemory`, Redis runs an eviction loop before executing it. Each round takes `maxmemory-samples` random keys from the candidate dictionary - the whole keyspace for `allkeys-*`, only keys carrying a TTL for `volatile-*` - estimates each one's idle time and evicts the best candidate, looping until memory is back under the limit. If nothing can be freed, write commands get an OOM error. Since Redis 3.0 the samples feed a 16-entry candidate pool that survives across rounds, so quality is far better than "best of 5 random". Default 5 is close to true LRU; 10 is very close at more CPU; 3 is cheaper and sloppier.
code
text · 9 linesredis-cli CONFIG SET maxmemory 4gb
redis-cli CONFIG SET maxmemory-policy allkeys-lru
redis-cli CONFIG SET maxmemory-samples 10
# how idle is one key, without touching its recency
redis-cli OBJECT IDLETIME session:8123
# how much eviction is actually happening
redis-cli INFO stats | grep evicted_keysgo deeper
Know that Redis approximates LRU by sampling a few random keys and evicting the idlest, and that maxmemory plus a policy must both be set for eviction to happen at all.
Explain the 24-bit header field, the sample-then-evict loop, the default of 5, and the difference between allkeys-* and volatile-* candidate sets.
Tie sampling cost to latency on the single command thread, mention lazyfree-lazy-eviction, and describe how to observe eviction pressure through evicted_keys and latency tooling.
Frame it as a deliberate memory-and-CPU tradeoff: bounded per-key metadata and probabilistic quality in exchange for no allocation and no hot-path relinking, and say when that approximation is unacceptable for the workload.
## Why exact LRU was rejected Exact LRU means you can always name the one key accessed longest ago. The textbook implementation is a hash map plus a doubly-linked list: each read unlinks the touched node and moves it to the head, eviction pops the tail. Over tens of millions of small keys that is two extra pointers per entry plus pointer chasing on every single read - memory Redis would rather spend on data, and cache misses on the hot path of a store whose whole selling point is microsecond latency. Redis chose an approximation that costs no extra allocation at all: 24 bits inside the `redisObject` header that every value already carries. Under an LRU policy those bits hold a coarse timestamp of the last access, updated in `lookupKey` whenever a command touches the key. ## The eviction loop Eviction is not a background timer. It runs on the main thread in the command path: before executing a command, Redis checks whether used memory exceeds `maxmemory`, and if so tries to free enough to get back under. The loop is: 1. Choose the candidate dictionary. `allkeys-lru`/`allkeys-lfu`/`allkeys-random` sample the main keyspace; `volatile-*` sample only the expires dictionary, i.e. keys that have a TTL set. With `volatile-*` and no key carrying a TTL, there is nothing to evict and writes fail with OOM. 2. Take `maxmemory-samples` keys at random from that dictionary. 3. Score each: under LRU the score is estimated idle time; under LFU it is the inverse of the frequency counter. 4. Evict the best candidate (asynchronously freeing the value if `lazyfree-lazy-eviction yes`), and repeat until under the limit or until progress stops. Because the candidates are random rather than globally ordered, Redis can evict a key that is not the true least-recently-used one - it evicts one of the idlest keys it happened to see. That is the whole meaning of "approximated". ## What maxmemory-samples buys `maxmemory-samples` is the sample size per round, not the number of keys evicted. Raising it makes each decision closer to true LRU because a larger sample is more likely to contain a genuinely idle key; lowering it makes each eviction cheaper. The published accuracy comparisons show 10 samples nearly indistinguishable from exact LRU, the default 5 very good, and 3 visibly worse. The cost is CPU on the single command-execution thread, paid on every eviction round; on an instance evicting thousands of keys per second a large sample size shows up directly as latency. ## Consequences worth naming in an interview - Eviction is synchronous work in the command path, so an instance permanently at `maxmemory` pays eviction CPU on ordinary traffic. - Approximation is fine for a cache and wrong for anything needing guarantees: never assume a specific key survives because it was touched recently. - Reads count as accesses. A full scan of the keyspace with `GET`s refreshes recency on cold keys and can poison LRU quality (one of the reasons LFU exists). - `OBJECT IDLETIME` reads the field without touching it, so you can inspect a key without changing its eviction odds.
- How close to true LRU is the default sample size of five?Very close for practical caches. The sampling is combined with a persistent candidate pool, so the keys evicted are drawn from the idlest tail of the keyspace rather than uniformly at random. Raising the sample size to 10 tightens it further at roughly double the per-eviction CPU; dropping to 3 measurably increases the chance of evicting a recently used key.
- Under volatile-lru, which keys are candidates, and what happens when none exist?Only keys that currently have a TTL, because the sampling runs over the expires dictionary rather than the main dictionary. If no key has a TTL, Redis has nothing it is allowed to evict, so once maxmemory is reached write commands fail with an OOM error while reads keep working. That is a classic production surprise when someone sets volatile-lru but forgets to set TTLs.
Picking the oldest item by pulling five boxes at random off the shelf and discarding the dustiest of the five, instead of maintaining a strict arrival order for the whole warehouse.
saying these in an interview costs you the question
- Claiming Redis maintains a real LRU linked list or exact access ordering
- Reading maxmemory-samples as the number of keys evicted per cycle rather than the sample size
- Believing eviction happens in a background thread on a timer instead of in the command path
- Assuming volatile-lru can evict keys without a TTL
- Treating a higher sample value as free accuracy with no latency cost