The idea: two ways a key disappears
Redis keeps every key in memory, so it needs ways to forget. A key expires when its time to live (TTL) runs out: SET k v EX 60, EXPIRE k 60. A key is evicted when memory is full: used_memory is above maxmemory when the next command arrives. Expiry is a promise you made about one key; eviction is Redis choosing a victim by its maxmemory-policy.
The page has one master with 12 keys, sized in KB, and a replica. The numbers are scaled down so they fit: maxmemory 1000kb (real servers use gigabytes), 4 keys per active-expire sample (20 in Redis), and an 8-entry eviction pool (16 in Redis). maxmemory-samples 5, hz 10, lfu-log-factor 10 and lfu-decay-time 1 are the real defaults. Every random choice uses a seeded generator, so each demo plays the same way every time.
The expires dict
Each database has two hash tables: the main dict (key → value) and the expires dict (key → deadline, an absolute Unix time in milliseconds). A key without a TTL is only in the main dict. TTL k is just the deadline minus now. Nothing happens at the deadline itself: there is no timer per key. The key stays in memory, already "dead", until one of two things finds it.
Lazy expiry: the read finds it
Every command that looks a key up goes through lookupKey, which first calls expireIfNeeded. If now is past the deadline, the key is deleted there and then, and the command behaves as if it never existed: GET returns (nil). The deletion is written to the AOF and sent to the replicas as a DEL (Demo: lazy expiry on GET). Lazy expiry costs nothing for keys nobody touches, but on its own it would let unread expired keys fill memory.
Active expiry: serverCron samples
serverCron runs hz times a second (10 by default) and calls activeExpireCycle. One call works in loops:
- take 20 random keys of the expires dict (
ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP; 4 on the page); - delete the ones whose deadline has passed;
- if more than 25% of the sample was expired, go back to step 1, as long as the call's time budget lasts (25% of the CPU: 25 ms of each 100 ms).
The rule is statistical: a sample that is mostly expired means many more expired keys are probably waiting, so it keeps going; a sample with few expired keys means memory is mostly clean, so it stops. A key that is never read still goes within a few calls (Demo: never read, removed by serverCron: the first call's sample misses rate:1, the second finds it; 1 of 4 is exactly 25%, not more, so the call stops), and a burst of expired keys makes one call loop several times (Demo: more than 25% expired, cycle repeats). The page runs one call per click of serverCron and pauses it otherwise, so you can see lazy expiry.
The 25% rule is the one the Redis docs describe. Since Redis 6 the source walks the expires table with a cursor instead of random sampling, and repeats while more than 10% is stale (ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE, tunable with active-expire-effort). The idea is the same.
Replicas wait for DEL
A replica never deletes an expired key on its own. It waits for the master's DEL, so master and replica stay identical and a key cannot vanish on one side only. Since Redis 3.2 a read on the replica already answers (nil) for a key past its deadline, but the key keeps its memory until the DEL arrives. On the page the replica's chips turn red at the deadline and disappear when the DEL box lands.
maxmemory and the policies
With maxmemory set, processCommand calls performEvictions before every command, reads included. If used_memory is above the limit, it deletes keys one by one until it is under. Only when that fails does the command's type matter: a deny-oom command, one that may use memory (SET, LPUSH, …), is refused with OOM; reads and deletes still run. The check is before the command, so a write can push memory over the limit again; the next command, even a GET, pays for it (Demo: lazy expiry on GET first evicts hot:cfg, then deletes sess:a).
| maxmemory-policy | Candidates | Victim |
|---|---|---|
noeviction (default) | none | the write fails: -OOM command not allowed when used memory > 'maxmemory'. |
allkeys-lru | all keys | least recently used (sampled) |
volatile-lru | keys with a TTL | least recently used (sampled) |
allkeys-lfu | all keys | least frequently used (sampled) |
volatile-ttl | keys with a TTL | nearest deadline (sampled) |
allkeys-random | all keys | one random key |
With noeviction a full Redis refuses writes but still serves reads: performEvictions fails on the GET too, but a read is not refused (Demo: noeviction returns OOM). The volatile-* policies never touch keys without a TTL; if there are none, they fail like noeviction. volatile-ttl sacrifices the keys that would expire soonest anyway (Demo: volatile-ttl evicts the nearest deadline). There is also volatile-random and volatile-lfu.
Approximated LRU and the eviction pool
True LRU needs a list of all keys in access order, updated on every read: two pointers per key and a list change per access. Redis instead stores a 24-bit LRU clock in every object (seconds, wrapping after about 194 days) and estimates the idle time as now minus that clock. To evict, evictionPoolPopulate samples maxmemory-samples keys (5) and inserts them into the eviction pool, 16 entries sorted by idle time. The best candidate, at the right end, is evicted if it still exists. The pool survives between evictions, so good candidates found earlier are remembered.
The result is close to LRU, not equal. If the oldest key is not in the sample, a younger one goes (Demo: allkeys-lru sampling vs true LRU: true LRU would evict user:3, idle 500 s, but the sample missed it and hot:cfg, idle 300 s, was evicted). With 10 samples Redis is very close to true LRU; with 5 it is good enough and cheaper.
LFU: a counter that grows slowly and decays
LRU only knows when a key was last used. A key read a thousand times an hour ago looks worse than a key read once a minute ago. LFU (Redis 4) reuses the same 24 bits: 16 bits for the last decrement time in minutes and an 8-bit counter. The counter is logarithmic: each access increments it only with probability p = 1 / ((counter − 5) · lfu-log-factor + 1), so it climbs fast at first and slowly later, and 255 is reached only after about a million hits with lfu-log-factor 10. A new key starts at 5 (LFU_INIT_VAL) so it isn't evicted at once. The counter decays by one for every lfu-decay-time minutes (1) since its last decrement, so old popularity fades.
| Counter | p of an increment (lfu-log-factor 10) |
|---|---|
| ≤ 5 | 1 |
| 6 | 1/11 ≈ 0.091 |
| 15 | 1/101 ≈ 0.010 |
| 30 | 1/251 ≈ 0.004 |
In Demo: allkeys-lfu keeps the hot key, hot:cfg was idle 300 s, the most idle key in the sample, so LRU would evict it. Its stored counter is 30; five minutes without a decrement bring it to 25, still far above the cold keys (3 to 5), so LFU evicts cart:7 (counter 3) and keeps hot:cfg. The eviction runs before the demo's GET user:2, because memory is over the limit; the read itself then shows both rules on one access: the counter first decays from 5 to 4 (one minute), then the increment, with p = 1 below 5, takes it back to 5. On the page each key shows both its idle time and its counter so you can compare; real Redis keeps only one of them in the object, depending on the policy.
See also the Redis event loop (the thread that runs serverCron and every command), the Redis dict (the hash table behind the main and expires dicts), Redis replication, RDB and AOF persistence, Redis encodings, sorted sets, streams, transactions, Redis Cluster, cache eviction policies (LRU, LFU, CLOCK, OPT on one trace) and an exact LRU cache built from a hash map and a linked list.
What the page leaves out
The fast expire cycle that runs in beforeSleep; the cursor walk and the 10% threshold of Redis 6+ (the page samples at random with the documented 25% rule); several databases; keys deleted with UNLINK-style lazy freeing (lazyfree-lazy-eviction, lazyfree-lazy-expire); memory that does not count toward eviction (replica output buffers, AOF buffers); maxmemory-eviction-tenacity; the fact that dictGetSomeKeys is not perfectly random and the pool can hold duplicates; volatile-random and volatile-lfu (they work like their allkeys cousins on the expires dict); writable replicas; and Redis 7.4 hash-field expiry.