Skip to content
Redis Expiration & Eviction: 8 Strategies, Trade-offs & Source Code Analysis
Databases 44 min read

Redis Expiration & Eviction: 8 Strategies, Trade-offs & Source Code Analysis

This article analyzes Redis expiration deletion and memory eviction mechanisms, detailing eight eviction policies, their trade-offs, three production incidents, source code walkthroughs of lazy/active expiration and LFU/LRU approximations, and practical configuration guidelines for avoiding common pitfalls.

Architecture Pony
Architecture Pony
Architecture Pony

Introduction

Memory is Redis's most expensive resource, and the "life and death of keys" is governed by two independent mechanisms: expiration deletion (removes keys when TTL expires) and memory eviction (decides which keys to kill when memory is full). Many confuse these, leading to misdiagnosis — memory growth blamed on "expired keys not cleaned" when actually eviction policy is misconfigured; write failures blamed on "eviction broken" when maxmemory isn't set. These two lines differ in trigger conditions, target objects, and time scales; clarifying their boundaries wins half the battle.

Three Core Facts

Redis does not use precise timed deletion — per-key timers are too costly; it combines lazy + periodic deletion to amortize cost into daily requests.

LRU is approximate — not a textbook doubly-linked list, but "randomly sample 5 keys, pick the least recently used", trading precision for memory.

Replicas do not actively delete expired keys — deletion authority lies with the primary; replicas only "pretend it's expired on read".

These three are classic "simplicity over correctness" trade-offs and key differentiators in interviews between rote memorization and true understanding.

Three Incidents, Three Lessons

Incident 1: Short-TTL key flood, memory rises and won't fall. A verification-code service used SETEX 60s, peaking at 400k keys/sec. After 60s keys logically expired, but periodic deletion runs every 100ms, sampling max 20 keys per DB per round — hitting expired keys is luck; lazy deletion only handles keys that are read. Hundreds of thousands of dead keys lingered, memory plateaued at 70% of peak. SCAN returned logically expired keys, ops thought memory leak. Truth: expired keys not deleted, just "not yet scheduled for deletion".

Incident 2: Memory full, all writes error. A reporting instance had no maxmemory (default 0). Upstream added a dimension, writes doubled, memory hit host limit, Redis rejected writes with OOM command not allowed when used memory > 'maxmemory' — but maxmemory was 0, error condition false, very misleading. App treated as "Redis down", triggered full service degradation, though reads worked. Root cause: missing watermark is config issue; treating write failure as service outage is cognitive issue.

Incident 3: volatile-lru on instance with no TTL keys. Team copied "best practice": maxmemory 16gb + maxmemory-policy volatile-lru. Keys were session data, all without TTL. Memory hit 16GB, eviction started — volatile range only picks from keys with TTL, which was empty set, so eviction engine deleted nothing, behavior degraded to

noeviction</sub>: all writes errored. Configured policy more dangerous than none, because team thought they had a safety net, didn't monitor memory curve.</p><h2>Technical Analysis: Two Lines, Three Diagrams</h2><h3>2.1 Expiration Deletion vs Memory Eviction: Six Differences</h3><pre>Expiration Deletion    Memory Eviction
Trigger                TTL reached          used_memory > maxmemory
Purpose                Data lifecycle       Memory watermark control
Target                 Only keys with TTL   Per policy scope
Timing                 On read + periodic   Before every write command
Primary/Replica        Primary deletes, replica syncs DEL   Each node independent
Extreme                Keys pile up         Write requests error</pre><p>Most overlooked row is "Primary/Replica": expiration deletion is "primary deletes, replicas sync DEL", cluster-wide consistent; memory eviction runs independently on each node — primary evicts per its watermark, replica per its watermark, possibly killing different keys. Hidden risk: if primary/replica watermarks diverge long-term (e.g., replica holds full-sync buffer), replica may evict first, ending up with fewer keys, replication looks "normal" but dataset already inconsistent.</p><h3>2.2 Expiration Deletion: Three Candidates and One Combination</h3><p>Textbook has three strategies; Redis chooses combination of latter two:</p><ol><li><strong>Timed deletion</strong> — per-key timer, delete on expiry. Most memory-efficient, but CPU-costly: every TTL key occupies a timer event; millions of TTL keys make event queue a bottleneck.</li><li><strong>Lazy deletion</strong> — ignore TTL, check on read, delete if expired. Most CPU-efficient, but memory-costly: unread keys occupy memory forever.</li><li><strong>Periodic deletion</strong> — background periodic random sampling, actively clean a batch. Compromise, but rhythm must be finely tuned, else either cleanup fails (Incident 1) or consumes too much CPU.</li></ol><p>Redis's combo: lazy deletion primary + periodic deletion secondary + lazyfree async. Lazy covers high-frequency "accessed keys" path; periodic covers "unaccessed keys"; 4.0 lazyfree moves actual large-object memory release to background thread, so deletion itself no longer blocks main thread. Three layers stacked, "delete key" impact on latency pressed to microseconds under normal load.</p><h3>2.3 Periodic Deletion Rhythm: Fast/Slow Two Modes</h3><p>Periodic deletion is not a simple timer but a <strong>self-adaptive sampling loop</strong> with two modes:</p><ul><li><strong>Slow cycle</strong> triggered by <code>serverCron

every 100ms, time-limited to 25% CPU (~10ms), the steady state. Fast cycle only activates when "previous slow cycle exited early but expired keys remain", runs every event loop, time-limited 1ms — fast mode exists to handle Incident 1's "short-TTL key flood", sacrificing some CPU to prevent expired key pileup. Each round has an adaptive exit condition : randomly sample 20 keys per DB; if all 20 expired, high expired-key density, continue sampling; if only a few expired, low density, move to next DB. This design makes cleanup intensity automatically follow expired-key density — high density spends more time, low density retreats quickly, the fundamental guarantee that "periodic deletion won't drag main thread".

2.4 Memory Eviction: Eight Policies and Three Scopes

maxmemory-policy has eight values, chaotic at first glance, but memorable via two dimensions: Scope dimension ( noeviction / volatile-* / allkeys-* ) × Algorithm dimension ( lru / lfu / random / ttl ):

noeviction           No eviction, write errors (default)
volatile-lru         Among TTL keys, pick least recently used
volatile-lfu         Among TTL keys, pick least frequently used
volatile-ttl         Among TTL keys, pick soonest to expire
volatile-random      Among TTL keys, random
allkeys-lru          Among all keys, pick least recently used
allkeys-lfu          Among all keys, pick least frequently used
allkeys-random       Among all keys, random

Two dimensions cross to give all eight, no rote memorization needed. Selection logic: pure cache (all keys regenerable) → allkeys-* ; mixed "regenerable cache + non-regenerable data" → volatile-* (sacrifice TTL keys to protect permanent keys); but volatile scope has implicit premise: TTL keys must exist and be substantial, else Incident 3. Cache scene default recommendation: allkeys-lru ; hot-read, few-write, access locality scenes consider allkeys-lfu .

2.5 What Memory Does maxmemory Govern

Critical detail: maxmemory only constrains "data-occupied memory", excluding replication buffers, AOF buffers, client output buffers . So a maxmemory set to 100% physical memory still OOMs — data hits limit, but replication streams, client buffers keep growing. Production rule of thumb: maxmemory ≤ 50%-70% physical memory , primary/secondary switch, fork (BGSAVE/COW), fragmentation, client concurrency all eat into that 30%-50% headroom. Cluster sharding needs another cut: each node's maxmemory calculated per "shard data + node fixed overhead", not simply total divided by node count.

2.6 How Expiry Time Is Stored

Detail often probed: expires dictionary value stores "absolute timestamp" (milliseconds), not "remaining seconds" . SETEX 60 converted to now+60000 at execution. Benefit: key expiry time independent of "where read from" — primary/secondary replication propagates TTL as absolute timestamp, primary/secondary switch, client reads from any DB, expiry moment consistent; cost: clock dependency — server clock large step-back causes batch of keys "delayed expiry" or "premature expiry", why ops standards forbid NTP large jumps on Redis machines. Another detail: precision: EXPIRE second-granularity, PEXPIRE millisecond-granularity, underlying storage/comparison unified in milliseconds. Second commands multiply by 1000 internally, so "60s expiry" actual expiry at 60.000s, zero error; real uncertainty from deletion timing — expiry is only "logical death moment", physical deletion may lag hundreds of ms to seconds (when periodic deletion reaches it). TTL command returns "remaining seconds", rounded down, so seeing TTL=1 actual remaining could be 1.9s; business using second semantics must be aware.

Core Flow: From SETEX to Eviction

3.1 Life of a TTL Key

String all expiration-related actions on a key's lifecycle — shortest path to understanding. A SETEX code:1001 60 "x7k2" complete journey:

T+0  Primary executes SETEX
T+0  Key written to dict (keyspace dictionary)
T+0  Expiry time written to expires dictionary
     key -> now+60000 (milliseconds)
T+0  Command written to replication stream and AOF
T+10 GET code:1001
     expireIfNeeded: not expired, return value
T+70 GET code:1001 (past logical expiry)
     expireIfNeeded: expired
     Primary: real delete, propagate DEL, return nil
     Replica: only return nil, wait for primary DEL
T+70~ Periodic deletion cycle samples
     If key never read, deleted when sampling reaches it

expires is a dictionary parallel to dict : key points to same key object, value is millisecond timestamp. Expiry check = one dict lookup + one comparison, negligible cost. Note SETEX is atomic SET + EXPIRE , while plain SET on existing TTL key clears TTL — #1 source of "keys mysteriously immortal" (detailed in 5.6).

3.2 One Eviction Execution Scene

After memory full, eviction action occurs before every write command actually executes ( freeMemoryIfNeeded check), full steps: calculate current watermark → if not over, proceed → if over, start picking keys per policy: each round randomly sample 5 ( maxmemory-samples ), estimate each's "idle time", pick the most deserving to delete , then recalc watermark, not enough → another round, until enough space freed or no candidate keys deletable (then error). This loop runs on main thread, each deleted key goes through "sample 5 pick 1", so eviction storm latency cost real — during peak sales memory hugging maxmemory, P99 jitter often caused by eviction loop .

3.3 Primary/Replica Different Treatment of Expiry

Primary is sole deleter. It deletes expired keys via lazy + periodic, propagates each deletion as DEL to replicas and AOF. Replicas only delete upon receiving DEL — even if they discover key "logically expired" they don't act — guarantees primary/replica dataset consistency (deletion order identical to primary). But when read requests hit replica, Redis does a logical expiry check on read path: if key expired, return nil directly, though key body still in memory. This is why "replica TTL may show negative but GET returns nil" — key physically alive, logically dead.

Core Source Code: Five Key Logic Sections

4.1 expireIfNeeded: Lazy Deletion Entry

/* db.c simplified */
int expireIfNeeded(client *c, robj *key) {
    if (!keyIsExpired(c,key)) return 0;

    if (server.masterhost == NULL) {
        /* Primary: real delete */
        server.stat_expiredkeys++;
        propagateExpire(c,key,
            server.lazyfree_lazy_expire);
        notifyKeyspaceEvent(
            NOTIFY_EXPIRED,"expired",key,...);
        if (server.lazyfree_lazy_expire)
            dbAsyncDelete(c->db,key); /* background */
        else
            dbSyncDelete(c->db,key);
    }
    /* Replica: don't delete, return 1 so caller treats key as non-existent */
    return 1;
}

Primary/replica fork point is this single if . Primary runs full "delete + propagate + notify" chain; replica does nothing, just returns "key expired" fact to caller. propagateExpire stuffing DEL into replication stream is key: deletion must appear in replication stream, else replicas forever accumulate extra dead keys. lazyfree_lazy_expire switch decides sync vs async delete — large value scenes recommend enabling, offload memory release to background thread.

4.2 activeExpireCycle: Adaptive Sampling Skeleton

/* expire.c simplified */
/* Slow cycle: every 100ms, limit 25% CPU */
iteration++;
if ((iteration & 0xf) == 0)
    /* every 16 rounds */
    timelimit = 16ms;
else
    timelimit = 1ms; /* other rounds */
start = ustime();

do {
    num = 20; /* sample 20 keys per DB */
    expired = activeExpireCycleTryExpire(
        db, num, now);
    total_expired += expired;

    /* expired count < sample count: low density, switch DB */
    if (expired < num)
        goto next_db;
    /* timeout check */
    if (ustime()-start > timelimit*1000)
        break;
} while (1);

Most chew-worthy: "using sample hit-rate as density estimator". It maintains no "expired key counter", instead uses "how many expired in one sample" to estimate whole DB expired-key density — statistically "sample proportion estimates population proportion", 20 samples sufficient at this precision. Every 16 rounds relax time limit (16ms) to prevent single slow cycle eating too much main thread time; other rounds 1ms quick in/out. If you've seen "expired key cleanup CPU spikes", answer lies in this timelimit tuning.

4.3 evictionPool: 16-Slot Eviction Pool

/* evict.c simplified */
/* Pool size 16, ordered by idle ascending, heap top smallest */
for (k = 0; k < count; k++) {
    /* count = maxmemory-samples, default 5 */
    idle = estimateObjectIdleTime(o);
    if (pool not full || idle > pool[0].idle) {
        /* new key idle larger, evict heap top */
        evictionPoolInsert(idle, key);
    }
}
/* During eviction, take pool tail (largest idle) */

This pool design is "accumulate info across multiple sampling rounds". Each round samples 5 keys, those with idle larger than pool's minimum squeeze in; eviction time doesn't pick from "this round's 5", but from "historically accumulated 16 candidates" the oldest. Means candidate quality improves with sampling rounds — after many rounds, pool's 16 keys likely cover globally least-used batch, precision loss from sampling 5 largely recovered by pool's accumulation effect . Another "small memory for high precision": pool itself only 16 entries.

4.4 Eviction Trigger Point: Before Write Command

Eviction check occurs in processCommand , before command actually executes: first judge if command may increase memory (read commands skip), then calculate watermark, if over enter freeMemoryIfNeeded loop . Implication: read requests never trigger eviction — they don't grow memory. Also: a large SET may run dozens of eviction loops before executing , stretching that command's latency, monitoring shows "this command especially slow but server idle". Another reason to leave 30% maxmemory headroom: let write commands almost never trigger eviction loop.

4.5 LFU: 8-bit Logarithmic Counter with Decay

/* 24bit lru field reused */
/* high 16bit: minute-level clock (for decay) */
/* low 8bit: logarithmic counter 0-255 */
uint8_t counter = LD_C(lru);
if (counter > LFU_INIT_VAL) {
    /* higher = harder to grow: logarithmic growth */
    r = rand() % 255;
    baseval = counter - LFU_INIT_VAL;
    if (r > baseval*lfu_log_factor
        + 255) {
        return;
        /* probabilistic fail, no increment */
    }
}
counter++; /* if pass, +1, cap 255 */

/* Decay: every lfu-decay-time minutes -1 */
elapsed = now/60000 - LD_T(lru);
counter -= elapsed / lfu_decay_time;

Logarithmic growth solves LFU classic problem: old hotkeys hog counter. Higher counter, lower probability of next increment — 1M visits and 2M visits both hit 255 in 8-bit, but logarithmic slope ensures "new keys have chance to climb". Decay solves another problem: "yesterday's hotkey, nobody visits today" — every lfu-decay-time minutes counter auto -1, long-unvisited keys naturally drop. Two parameter tuning: lfu-log-factor larger → steeper curve (higher counter discrimination); lfu-decay-time larger → slower decay (longer historical heat retention).

Advanced Topics: Six Accounts to Calculate Upfront

5.1 Why LRU Is "Approximate"

Textbook LRU needs doubly-linked list, every access moves node to head — requires two extra pointers per key (~16 bytes) and one list write per access , 10M keys = 160MB extra memory plus pointer shuffling per access. Redis answer: stuff a 24-bit "last access clock" (second precision) into each object header , eviction time randomly sample 5, compare clocks. Cost: "may pick not the absolute oldest key"; gain: zero extra memory, zero access-path overhead . Measured experience: sampling 5 hit-rate vs true LRU gap within 10%, sampling 10 nearly identical — but usually don't tune, 5 is enough.

5.2 LRU vs LFU Dividing Line

LRU only sees "how long since last access", LFU sees "access frequency + recent access time" . Dividing scenario: "occasional full scans" — a full-table scan (reporting, migration script) refreshes all LRU clocks, true hotkeys become "recently not accessed" and get mis-killed — classic "cache pollution". LFU immune: scan adds only +1 per key, hotkeys' hundreds of thousands of counts still crush. One-sentence criterion: if your instance has periodic full-table scan tasks, or access pattern has bursty long-tail, choose LFU; if access locality stable, LRU sufficient.

5.3 Expired Key Pileup Investigation & Remediation

Fixed three-step investigation:

Watch INFO stats expired_keys growth curve — should correlate with TTL key write rate; curve flat while memory rises = pileup.

Calculate expired key density — random sample keys check TTL, estimate cluster-wide "logically expired but not deleted" proportion; >5% needs action.

Three remediation axes — stagger TTL concentration (avoid all expiring same second), enable lazyfree-lazy-expire yes for async deletion, when necessary use SCAN + UNLINK manual cleanup ( UNLINK async delete, safer than DEL).

Periodic deletion sampling is random, pileup cannot be cured by "increase sample count", only mitigated by lowering expired-key density or async deletion.

5.4 SET Overwrite Loses TTL: #1 "Immortal Key" Source

Redis semantics: SET is "whole key replacement" — overwriting existing key clears TTL, key becomes immortal. Almost every team steps on this : session key originally 30min expiry, one day code refactor changed to "SET then SETEX", middle SET wiped TTL; or use INCR accumulate counter, thought TTL still there. Investigation: periodically spot-check suspicious keys' TTL return values — -1 means immortal (no TTL set), -2 means key non-existent, positive = remaining seconds. Large-scale -1 = "immortal key" incident, combine with memory curve quickly locate offending code. Correct TTL-preserving posture: modify value use SETEX (atomic reset with TTL), append use EXPIRE explicit renewal, never write "bare SET" overwriting TTL key.

5.5 Production Default Config Selection

Baseline per scene (copy-paste ready): Pure cache instance → maxmemory 70% + allkeys-lru (or allkeys-lfu ) + maxmemory-samples 5 ; Mixed instance → volatile-lru + ensure TTL key proportion > 50%; Has periodic scan tasks → allkeys-lfu + lfu-log-factor 10 ; Large value scenes uniformly enable lazyfree-lazy-eviction / lazyfree-lazy-expire / lazyfree-lazy-user-del three switches. All scenes share three bottom lines: maxmemory must be explicitly set (cannot leave 0), must configure monitoring alerts (used_memory/maxmemory ratio), write failures must distinguish "eviction failed" from "service fault" .

5.6 Six High-Frequency Pitfalls

SETEX vs SET+EXPIRE not same — non-atomic version may be interrupted mid-way, leaving immortal keys.

RENAME preserves TTL but changes key name — new key has TTL, old key disappears, TTL checks easily confuse objects.

EXPIRE relative time translated to absolute timestamp during replication — so primary/secondary switch won't cause TTL drift, but if business assumes "relative business time" be careful.

SCAN returns expired keys — SCAN guarantees "keys existing throughout traversal returned at least once", doesn't filter expiry; business must TTL-filter results.

TTL returns -1 and -2 completely different — former immortal, latter non-existent; monitoring must separate.

PERSIST makes key immortal — this command in cluster as dangerous as SET, code review must focus.

5.7 Eviction Storm Monitoring & Alerting

Eviction not "configure and forget", it's runtime behavior, must enter monitoring:

First metric: evicted_keys growth rate — INFO stats counter starts continuously rising, instance entered "steady-state eviction", memory curve inevitably hugging maxmemory, earliest capacity alert signal.

Second metric: used_memory / maxmemory ratio — >90% must expand or clean, don't wait for 100%.

Third metric: write command P99 correlation with evicted_keys curve — both rise together = eviction storm dragging latency; fix: reduce write volume, pre-expand, or temporarily lower samples to stop bleeding.

Alert threshold design experience: evicted_keys per-minute increment >0 → warning, >1000 → critical. Eviction is "slow capacity problem" turning into "acute latency problem" inflection point, not instantaneous failure but continuous deterioration, so monitoring value lies in "early" — handle at first eviction record, cost lowest; handle at eviction storm, already losing cache data, falling back to origin. Put "whether evicted_keys growing" into cache instance daily report — lowest cost, highest yield ops discipline.

Learning Path

Level 1 (Reproduce): Spin up maxmemory 100mb instance, stuff 200mb keys observe allkeys-lru eviction; then use volatile-lru but write no TTL keys, reproduce "degrades to noeviction".

Level 2 (Measure): Load 500k 60s TTL keys, per-second record used_memory and expired_keys, plot "pileup-cleanup" curve; change maxmemory-samples from 5 to 10 compare eviction precision.

Level 3 (Rescue): Reproduce SET overwrite loses TTL, write TTL spot-check patrol script; artificially create "cache pollution" (full-table SCAN then observe allkeys-lru killing hotkeys), compare allkeys-lfu behavior.

Level 4 (Modify): Read expire.c activeExpireCycle and evict.c evictionPool, manually trace the "sample-density estimate-exit" closed loop.

Interview Questions (with Answers)

20 Q&A covering: difference between expiration and eviction, why no timed deletion, how periodic deletion avoids blocking, fast/slow cycle differences, why SCAN sees expired keys, how replicas handle expiry, why approximate LRU, maxmemory-samples meaning and cost, LRU vs LFU selection, LFU solving old hotkey hogging, default eviction policy rationale, volatile-lru on no-TTL instance behavior, when eviction triggers (reads don't), maxmemory coverage and 100% physical memory viability, SET on TTL key effect and prevention, TTL -1 vs -2 difference, lazyfree/UNLINK vs DEL, expired key pileup investigation/remediation, cache pollution and LFU prevention, production config defaults.

Summary

All mechanisms in this article boil down to one sentence: Redis uses "estimation" instead of "precision", turning key life/death management into a zero-steady-state-cost statistical system — expiration deletion uses sample hit-rate to estimate expiry density, LRU uses object-header clock plus random sampling to estimate idle time, LFU uses 8-bit logarithmic counter to estimate access frequency, eviction pool uses 16 slots to accumulate global optimal candidates. Every "estimation" trades massive memory/CPU savings, while precision loss recovered by engineering means (pool accumulation, adaptive exit, decay). Understanding this statistical thinking means understanding Redis memory management's soul: it's not about doing things exactly right, it's about doing them cheap and good enough.

Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

Memory ManagementRedisconfigurationcachingtroubleshootingLRUsource codeLFUevictionexpiration
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.