Redis Expiration & Eviction

The expires Dict

A separate hashtable per database mapping key → absolute deadline.

Each Redis database has two top-level dicts: the main keyspace dict (db->dict) mapping key → robj, and the expires dict (db->expires) mapping key → 64-bit absolute timestamp in milliseconds. EXPIRE key 60 stores now_ms + 60000 in expires; PERSIST key removes the entry; deleting the key from the main dict also removes it from expires.

The two-dict design has a quirk: a key without a TTL has no entry in expires, so iterating the expires dict is equivalent to iterating only keys with TTL. This is what makes the active expiration sample efficient — it samples from this restricted set, not from the entire keyspace. If only 10% of your keys have TTLs, active expiration only walks 10%.

Lazy Expiration

Check on every access. Free for unaccessed keys.

Every command that touches a key calls expireIfNeeded() first:

int expireIfNeeded(redisDb *db, robj *key) {
  long long when = getExpire(db, key);
  if (when < 0) return 0;          // no TTL set
  if (now_ms() < when) return 0;   // not yet expired
  // expired — delete it lazily
  if (server.lazyfree_lazy_expire)
    dbAsyncDelete(db, key);
  else
    dbSyncDelete(db, key);
  notifyKeyspaceEvent("expired", key);
  return 1;
}

A return of 1 tells the calling command to act as if the key didn't exist. The keyspace notification (__keyspace@0__:foo expired) gets published to subscribers, useful for cache-invalidation patterns where downstream systems need to know when a TTL fires.

The cost of lazy expiration is exactly: one hashtable lookup per command. The cost it doesn't pay: no work for keys nobody asks about. The downside: if you SET a key with TTL and never read it, it sits in memory forever from lazy alone — that's why active expiration exists.

Active Expiration (the Sampling Algorithm)

Probabilistic; runs in the cron callback up to its CPU budget.

serverCron fires every 1000/hz ms (default hz=10, so every 100 ms). One of its jobs is the active expiration cycle, implemented in activeExpireCycle():

while (cycle_time_used < 25% of tick) {
  for each db in dbs {
    repeat {
      sample 20 random keys from db->expires
      delete those that are expired
      stats: expired_in_batch / 20

      if (expired_in_batch > 5)         // >25% threshold
        repeat the loop on this db
      else
        move on to next db
    } until budget exhausted
  }
}

The "if more than 25% of the sample expired, do another sample" is the probabilistic cleverness: when the database has lots of expired keys, the loop spins fast and clears them quickly; when most keys are fresh, the first sample shows few expired and the loop moves on. The CPU budget cap (25% of the tick) prevents starvation of normal command processing.

Tuning hz: higher values (up to 500) make the cron run more frequently, so active expiration is more responsive but uses more CPU. The default of 10 is fine for most workloads. hz=100 may help if you have a large fraction of short-TTL keys (e.g. sub-second tokens) and need tighter eviction lag. dynamic-hz yes (default) lets Redis raise hz adaptively when many clients are connected.

The expected staleness bound: even in worst case, no more than ~1/4 of the expires dict should be stale, because the loop repeats while >25% are expired. This isn't a hard guarantee — for a few cron ticks under burst load it can drift higher — but in steady state it's tight.

Eviction When maxmemory Is Reached

Different mechanism, different policies, different goal.

Eviction is the action taken when a write would push memory over maxmemory and Redis must drop something to fit. The policy is set by maxmemory-policy:

noeviction          ← reject writes with OOM error (default)
allkeys-lru         ← approximate LRU across all keys
volatile-lru        ← approximate LRU among keys with TTL
allkeys-lfu         ← approximate LFU across all keys
volatile-lfu        ← approximate LFU among keys with TTL
allkeys-random      ← random across all keys
volatile-random     ← random among keys with TTL
volatile-ttl        ← key with soonest deadline among TTL keys

For caching workloads, allkeys-lru is the typical choice — drop the least-recently-used regardless of TTL. For workloads where some keys are designated cache (TTL set) and others designated state (no TTL), volatile-lru protects the state. noeviction is the right choice when Redis is the source of truth and dropping data is unacceptable.

Approximate LRU and LFU

Why Redis doesn't maintain a global LRU list.

A textbook LRU cache requires a doubly-linked list of all keys ordered by access time, with O(1) move-to-head on access. For a hashtable with millions of keys, this list adds 16 bytes of pointer overhead per key — significant memory cost. Redis instead stores a 24-bit "LRU clock" per object (in the robj header), updated on every access, and uses a sampling-based eviction:

when memory needs freeing {
  maxmemory_samples = 5  // configurable
  pool = empty priority queue of (key, lru_clock)

  for i in 0..maxmemory_samples {
    k = random key
    insert (k, k.lru_clock) into pool
  }
  evict the key in pool with the smallest lru_clock (oldest)
}

With samples=5, each eviction picks "old enough" but not perfectly oldest. The Redis docs include charts showing that with samples=10, the result is nearly indistinguishable from true LRU at much lower memory cost. Typical production: leave at default unless eviction quality matters more than CPU.

LFU is similar but stores a 24-bit field split into a 16-bit "last decremented" timestamp and an 8-bit logarithmic counter. Each access increments the counter probabilistically (with diminishing probability as the counter grows, so it caps around 255 even for very-hot keys). Periodically the counter decays based on the timestamp gap. The eviction sample picks the key with the lowest counter — i.e., least frequently used recently. LFU shines when scans shouldn't displace genuinely hot data; default LRU policies fail this case.

Tradeoffs Across Policies

FAQ