Redis Expiration and Eviction Strategies: Memory Management, LRU and LFU Algorithms

Introduction

Because a server's memory is finite, Redis may run out of memory; when this happens, the behavior of subsequent commands depends on the expiration and eviction mechanisms described below.

Memory Expiration

Redis provides four commands to set a key's time‑to‑live (TTL):

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 commands ultimately invoke the internal pexpireat implementation. Commands such as set can also set an expiration atomically.

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

Expiration Strategies

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

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

Lazy deletion : keys are only removed when accessed; if a key is expired at access time it is deleted, otherwise its value is returned. This can waste memory.

Periodic scanning : the server periodically scans keys with expirations and deletes those that have expired. This balances CPU and memory usage but may return an expired key before it is removed.

Redis combines strategy 2 (lazy) and strategy 3 (periodic) for its default behavior.

Eight Eviction Policies

If all keys are non‑expiring and memory becomes full, Redis applies one of eight maxmemory-policy options. The maximum memory limit is configured with the maxmemory directive (e.g., maxmemory 1GB ) or the CONFIG SET maxmemory command. On 32‑bit systems the default ceiling is 3 GB; on 64‑bit systems there is no hard limit.

LRU Algorithm

LRU (Least Recently Used) evicts keys that have not been accessed for the longest time. Redis does not store a full timestamp for each key; instead it keeps a 24‑bit lru field that records the last access time in a coarse clock.

Redis Improved LRU Algorithm

To avoid the overhead of a traditional LRU list, Redis samples a small number of keys (default maxmemory_samples 5 ) and evicts the one with the oldest lru value among the sample. The larger the sample size, the closer the result approximates true LRU.

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;

Redis also maintains a global lru_clock that is updated every 100 ms by serverCron . The difference between lru_clock and a key's lru determines its idle time, avoiding a system call for each key access.

LFU Algorithm

LFU (Least Frequently Used) tracks how often a key is accessed. Redis stores an 8‑bit counter (max 255) and an 8‑bit last‑decrement‑time (ldt) inside the same 16‑bit lru field.

Frequency Increment

When a key is accessed, Redis probabilistically increments the counter using a logarithmic factor ( lfu_log_factor , default 10). The increment occurs with probability 1/(baseval * lfu_log_factor + 1) , where baseval is the difference between the current counter and a base value (default 5).

lfu_log_factor 10

A larger lfu_log_factor slows counter growth; for example, a factor of 100 requires about 10 million accesses to reach the 255 limit.

Frequency Decrement

To prevent counters from saturating, Redis periodically decays them based on the elapsed idle time. The decay interval is controlled by lfu-decay-time (default 1 minute). The idle time (in minutes) divided by lfu-decay-time determines how many points to subtract from the counter.

lfu-decay-time 1

The algorithm extracts the current minute‑level timestamp, compares it with the stored ldt , computes the number of decay periods, and reduces the counter accordingly.

Summary

The article covered how Redis manages key expiration, the three expiration handling strategies, the eight memory‑eviction policies configurable via maxmemory-policy , and the internal LRU and LFU algorithms that drive those policies, including their sampling, clock, and probabilistic counter mechanisms.