How Redis Manages Memory Exhaustion: Expiration, Eviction, LRU & LFU

Preface

Because a server’s memory is finite, Redis can run out of memory. When that happens, Redis must decide how to handle further commands.

Key Expiration

Redis provides four commands to set a key’s time‑to‑live:

expire key ttl – set expiration in seconds

pexpire key ttl – set expiration in milliseconds

expireat key timestamp – set expiration at a specific Unix time (seconds)

pexpireat key timestamp – set expiration at a specific Unix time (milliseconds)

All of these ultimately call pexpireat internally. The SET command can also set an expiration atomically.

After a key has an expiration, its remaining time can be queried with TTL (seconds) or PTTL (milliseconds). If no expiration is set the commands return –1; if the expiration is invalid they return –2.

Expiration Strategies

When an expired key is removed, Redis can use three strategies:

Timed deletion – a timer is created for each key; when the timer fires the key is deleted. This is memory‑friendly but consumes CPU for each timer.

Lazy deletion – keys are only checked for expiration when accessed; if expired they are removed at that moment.

Periodic scanning – the server periodically scans keys with an expiration and deletes the expired ones. This is a compromise between the first two strategies.

Redis combines strategies 2 (lazy) and 3 (periodic scanning). The periodic scan only examines keys that have an expiration, because such keys are stored separately.

typedef struct redisDb {
    dict *dict;          // all key‑value pairs
    dict *expires;       // keys with an expiration
    dict *blocking_keys; // keys blocked by commands like BLPOP
    dict *watched_keys;  // WATCHed keys
    int id;              // database ID
    // ... other fields omitted
} redisDb;

Eight Eviction Policies

If all keys are persistent and memory becomes full, Redis uses one of eight eviction policies, configured via maxmemory-policy. The total memory limit is set with maxmemory (e.g., config set maxmemory 1GB). Without this setting, Redis can use up to 3 GB on 32‑bit systems and is unlimited on 64‑bit systems.

LRU Algorithm

LRU (Least Recently Used) removes the key that has not been accessed for the longest time. Redis does not use a classic LRU because it requires extra memory and can evict frequently used keys that happen to be idle.

Redis‑Improved LRU

Redis samples a small number of keys (default maxmemory_samples 5) and applies LRU only to that sample, reducing memory overhead and improving performance.

How Redis Tracks Hot Data

Each redisObject contains an lru field that records the last access time. A global lru_clock is updated every 100 ms by serverCron, allowing Redis to compute idle time as lru_clock - object.lru without calling the system clock for each object.

typedef struct redisObject {
    unsigned type:4;      // object type
    unsigned encoding:4;   // encoding
    unsigned lru:LRU_BITS;// last access time (24 bits)
    int refcount;        // reference count
    void *ptr;           // pointer to actual data
} robj;

Because the lru field is only 24 bits, it wraps after about 194 days. When lru_clock is less than the stored lru, Redis computes idle time as lru_clock_max - lru + lru_clock. This edge case is rare and does not significantly affect eviction accuracy.

LFU Algorithm

LFU (Least Frequently Used) records both the last decrement time (high 16 bits) and a usage counter (low 8 bits) inside the same lru field.

Counter Increment

The 8‑bit counter (max 255) is increased probabilistically:

Generate a random number R in (0,1).

Compute baseval = max(counter‑initial, 0) (initial default 5).

Calculate probability P = 1 / (baseval * lfu_log_factor + 1).

If R < P, increment the counter.

The log factor ( lfu_log_factor) defaults to 10 and can be tuned; higher values make the counter grow more slowly.

lfu_log_factor 10

Counter Decay

When a key is not accessed, its counter decays. The decay speed is controlled by lfu-decay-time (default 1 minute). The algorithm:

Convert the current timestamp to minutes and keep the low 16 bits ( now).

Extract the high 16 bits from the object’s lru ( ldt).

Compute idle minutes: if now >= ldt then idle = now - ldt, else idle = 65535 - ldt + now.

Calculate num_periods = idle / lfu_decay_time.

Decrease the counter by num_periods.

This simple formula effectively reduces the counter proportionally to how long the key has been idle.

Summary

The article explains how Redis handles key expiration, the three expiration‑deletion strategies, the eight memory‑eviction policies, and the internal LRU and LFU mechanisms—including sampling, global clocks, and counter decay—that together allow Redis to manage hot data efficiently under memory pressure.