Redis's Approximated LRU Algorithm: Deep Dive into Memory-Efficient Eviction

Understanding Cache Eviction and LRU

For a cache to be truly efficient, it must hold keys that are most likely to be accessed again. The Least Recently Used (LRU) algorithm is a widely adopted strategy for this purpose. The core idea behind LRU is that a key that has not been accessed recently is less likely to be accessed in the future, making it a prime candidate for eviction when memory limits are reached. While LRU is a standard algorithm, Redis implements an approximated version, making crucial design decisions to prioritize memory efficiency and performance at scale.

The Pitfalls of Naive LRU Implementations

Before diving into Redis’s approach, let’s consider how a naive LRU might be implemented and why these methods fall short for an in-memory database like Redis.

Naive Approach 1: Storing Timestamps and Sorting

A straightforward way to implement LRU would be to store a last_accessed_at timestamp for each key. Every time a key is accessed, this timestamp would be updated. When eviction is needed, all keys would be sorted by their last_accessed_at values, and the one with the oldest timestamp would be evicted.

Problems:

• Slowness at Scale: Sorting all keys at eviction time is an O(N log N) operation, which is prohibitively slow for a high-performance system like Redis, especially with millions of keys.

Naive Approach 2: Doubly Linked List

A classic solution for true LRU is to maintain a doubly linked list. When a key is accessed, its corresponding node is moved to the head of the list. The head always contains the most recently used keys, and the tail contains the least recently used keys. Eviction then simply involves removing nodes from the tail.

Problems:

• Extra Memory Overhead: Each node in a doubly linked list requires additional pointers (to the next and previous nodes) beyond the actual key data. For an in-memory database where every byte counts, this extra memory for pointers is catastrophic, reducing the space available for actual data.
• CPU Overhead for Pointer Manipulation: Moving a node to the head involves updating multiple pointers, which is a CPU-intensive operation. At Redis’s speed, frequent pointer manipulations can significantly tax the CPU and reduce throughput.
• Random Memory Access: Linked lists often involve random memory access patterns, which are less cache-friendly compared to contiguous memory blocks. This can lead to CPU cache misses and slower performance.
• Timestamp Storage: Even with a linked list, storing the last_accessed_at timestamp for each object typically requires 32 bits (4 bytes). For millions of objects, this adds substantial memory overhead.

Redis’s Approximated LRU Algorithm: Key Design Decisions

Redis addresses the challenges of naive LRU by making several clever design decisions, prioritizing memory efficiency and practical performance over theoretical exactness.

1. The 24-bit LRU Clock: Saving Memory

Instead of a full 32-bit timestamp, Redis dedicates only 24 bits to store the lru information within each redisObject structure. This lru field stores a trimmed-down version of the last_accessed_at time.

Why 24 bits?

• Memory Savings: Saving 8 bits (1 byte) per object is significant. For a dataset of 1 million keys, this translates to 1 MB of saved memory, which can be used to store more actual data.
• CPU Cache Alignment: The redisObject structure is designed to be a multiple of 4 bytes (e.g., 32 bits for type, encoding, and lru; 32 bits for reference count; 32 bits for pointer). This alignment makes it highly efficient for CPU cache lines to read and write, improving overall performance.

How it works:

Redis obtains the current time (e.g., in seconds) as a 32-bit integer. To fit it into 24 bits, it performs a bitwise AND operation with 0x00FFFFFF. This masks out the most significant 8 bits, effectively taking only the least significant 24 bits of the current time.

lru_clock_value = (current_unix_time_in_seconds & 0x00FFFFFF)

This creates a