How Redis Implements LRU Eviction: Deep Dive with Python Example

Introduction

Redis is widely used as an in‑memory cache, and its memory‑eviction policy directly affects cache efficiency. In most deployments the Least Recently Used (LRU) algorithm is chosen. This article walks through the LRU concept, provides a simple Python implementation, and then examines how Redis implements LRU internally.

What Is LRU?

LRU discards the items that have not been accessed for the longest time. Implementations typically keep an "age" counter for each cached entry and update these counters on every access, which can be expensive but ensures that the truly least‑used items are evicted.

Simple Python LRU Cache

The following code demonstrates a basic LRU cache using a doubly‑linked list for ordering and a hash map for O(1) look‑ups.

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.pre = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head = None
        self.end = None

    def get(self, key):
        if key in self.map:
            node = self.map[key]
            self.remove(node)
            self.setHead(node)
            return node.value
        return -1

    def set(self, key, value):
        if key in self.map:
            node = self.map[key]
            node.value = value
            self.remove(node)
            self.setHead(node)
        else:
            node = Node(key, value)
            if len(self.map) >= self.capacity:
                self.map.pop(self.end.key)
                self.remove(self.end)
            self.setHead(node)
            self.map[key] = node

    def remove(self, node):
        if node.pre:
            node.pre.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.pre = node.pre
        else:
            self.end = node.pre

    def setHead(self, node):
        node.next = self.head
        node.pre = None
        if self.head:
            self.head.pre = node
        self.head = node
        if not self.end:
            self.end = self.head

Running a short test shows how keys move to the head of the list on get and set operations.

Redis Internal LRU Mechanism

Redis stores a global LRU clock in the struct redisServer:

struct redisServer {
    ...
    unsigned lruclock:LRU_BITS; /* Clock for LRU eviction */
    ...
};

The clock is updated every 100ms (configurable via hz, default 10). The function getLRUClock() returns the current clock value reduced to LRU_BITS bits:

#define LRU_CLOCK_RESOLUTION 1000
#define LRU_BITS 24
#define LRU_CLOCK_MAX ((1<<LRU_BITS)-1)
unsigned int getLRUClock(void) {
    return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}

Each redisObject holds its own lru field, which is compared against the global clock to decide whether the object is a candidate for eviction.

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

When a key is accessed, the lookupKey function updates the object's lru field unless a child process is performing a save operation.

Maxmemory Policies

Redis offers several eviction policies controlled by the maxmemory-policy setting. The LRU‑related options are:

volatile‑lru : approximate LRU among keys with an expiration.

allkeys‑lru : approximate LRU among all keys.

Other policies ( volatile‑lfu, allkeys‑lfu, volatile‑random, allkeys‑random, volatile‑ttl, noeviction) are mentioned for completeness but are not covered in detail here.

Active Eviction (serverCron)

Redis periodically runs serverCron, which invokes databasesCron to expire keys. The active eviction algorithm samples up to 20 keys with an expiration in each of up to 16 databases, removes expired keys, and respects a time budget (default 25 ms). The process repeats while enough keys are actually evicted.

Passive Eviction (freeMemoryIfNeeded)

Before executing a write command, Redis calls freeMemoryIfNeeded. It calculates the current memory usage, subtracts buffers used by slaves, AOF, and other overhead, then attempts to free memory according to the configured policy. If the policy is noeviction, an OOM error is returned.

The eviction steps are:

Obtain mem_reported (memory used by the server).

If mem_reported < server.maxmemory, continue; otherwise adjust for slaves, AOF buffers, etc.

If memory is still over the limit and the policy is LRU, sample maxmemory_samples keys (default 5) and evict the one with the highest idle time.

Repeat until memory usage falls below the limit or no more keys can be evicted.

Key Takeaways

Redis relies on an approximated LRU algorithm; excessive expired keys can cause active eviction cycles to take up to 250 ms, potentially leading to request timeouts.

When memory pressure is high, passive eviction is triggered, which may also cause latency spikes.

Adjusting the hz parameter changes the frequency of active eviction checks and can mitigate timeout issues caused by large numbers of expired keys.