Mastering Redis Expiration and Eviction: LRU vs LFU Explained

1. Introduction

Redis runs on servers with finite memory, so memory exhaustion can occur. When the Redis server runs out of memory, the behavior of subsequent commands depends on expiration settings and eviction policies.

2. Key Expiration Commands

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 timestamp (seconds). pexpireat key timestamp – set expiration at a specific Unix timestamp (milliseconds).

All of these ultimately invoke the internal pexpireat implementation. The SET command can also set an expiration atomically.

After setting an expiration, the remaining time can be queried with ttl key (seconds) or pttl key (milliseconds). Both return -1 if no expiration is set and -2 for an invalid expiration.

3. Expiration Deletion Strategies

Timed deletion : a timer is created for each key; when the timer fires, the key is removed. Memory‑friendly but CPU‑intensive.

Lazy deletion : keys are checked for expiration only when accessed; unaccessed expired keys waste memory.

Periodic scanning : Redis periodically scans keys with an expiration and deletes those that have expired. This is a compromise between the first two strategies, but may return already‑expired keys if the scan interval is too long.

Redis combines strategies 2 (lazy) and 3 (periodic) for practical use.

4. Internal Redis Database Structure

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

5. Memory‑Eviction Policies (maxmemory‑policy)

When maxmemory is reached and a write command (e.g., SET) is issued, Redis selects a key to evict based on the configured policy. The parameter can be set in the config file or dynamically with CONFIG SET maxmemory-policy <policy>.

The eight policies are:

noeviction

allkeys-lru

volatile-lru

allkeys-random

volatile-random

volatile-ttl

allkeys-lfu

volatile-lfu

Below is a diagram of the policies (image omitted for brevity).

6. LRU Algorithm in Redis

Redis does not use a classic LRU because it requires extra memory and can evict frequently used keys that have not been accessed recently. Instead, Redis samples a configurable number of keys (default maxmemory_samples 5) and applies LRU to the sample. maxmemory_samples 5 Redis also maintains a global lru_clock updated every 100 ms by serverCron. When deciding which key to evict, Redis computes the difference between lru_clock and each key’s stored lru value.

Because the lru field is only 24 bits, it wraps after about 194 days, requiring special handling for wrap‑around cases.

7. LFU Algorithm in Redis

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

Counter increment uses a probabilistic logarithmic algorithm controlled by lfu_log_factor (default 10). The increment steps are:

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

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

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

If R < P, increment the counter. lfu_log_factor 10 The counter decays over time based on lfu-decay-time (default 1 minute). The decay algorithm extracts the high 16 bits (last decrement time) and computes idle time, then reduces the counter by idle_time / lfu_decay_time.

lfu-decay-time 1

8. Summary

The article covered how Redis manages key expiration, the three deletion strategies, the eight configurable eviction policies for out‑of‑memory scenarios, and the internal LRU and LFU mechanisms that balance performance and accuracy.