Implementing Redis's Approximated LRU Algorithm: A Go Deep Dive

Introduction

Building upon the theoretical understanding of the approximated LRU algorithm, this article delves into its practical implementation. We will first dissect the Redis C source code to uncover its intricate details and design choices, then translate these concepts into a Go implementation, providing a comprehensive guide to building an efficient LRU cache.

Redis C Source Code Deep Dive

Redis’s approximated LRU algorithm is primarily implemented within the evict.c file. Analyzing this file reveals several key components and optimizations.

Eviction Pool Configuration: EVPOOL_SIZE_SECTOR_16

The first significant macro encountered is EVPOOL_SIZE_SECTOR_16, which defines the constant size of the eviction pool as 16. This pool temporarily holds a sample of keys. During eviction, Redis samples approximately 5 keys, adds them to this pool, and then evicts the best candidate from this pool – the one with the most idle time. The pool size of 16 ensures that there’s enough space to maintain a sorted list of potential eviction candidates.

The 24-Bit LRU Clock: getLRUClock

Redis uses a 24-bit clock to track the last access time of objects, optimizing memory usage. The getLRUClock function computes this clock as follows:

// Pseudocode inspired by Redis source
long long ms_time = get_unix_time_in_milliseconds();
long long epoch_seconds = ms_time / LRU_CLOCK_RESOLUTION; // LRU_CLOCK_RESOLUTION is 1000
unsigned int lru_clock = epoch_seconds & LRU_CLOCK_MAX; // LRU_CLOCK_MAX is (1 << 24) - 1

This calculation effectively takes the last 24 bits of the current Unix epoch seconds, providing a compact and efficient timestamp that wraps around every ~194 days (2^24 seconds).

Estimating Object Idle Time: estimateObjectIdleTime

The idle time of an object is crucial for LRU eviction. The estimateObjectIdleTime function calculates this based on the current 24-bit clock and the object’s lastAccessAt timestamp. It handles the clock wrap-around scenario:

// Pseudocode inspired by Redis source
unsigned int current_lru_clock = getLRUClock();
unsigned int object_lru = object->lru;

if (current_lru_clock >= object_lru) {
    // Normal case: current clock is ahead or equal
    return current_lru_clock - object_lru;
} else {
    // Clock wrapped around: current clock is smaller than last access
    return (LRU_CLOCK_MAX - object_lru) + current_lru_clock;
}

This logic ensures accurate idle time calculation even when the 24-bit clock cycles back to zero.

Eviction Pool Management Functions

Redis manages its eviction pool through dedicated functions:

• evictionPoolAlloc: This function allocates the eviction pool of size 16. It is invoked during the server’s initialization phase via initServer in server.c, ensuring the pool is ready from startup.
• evictionPoolPopulate: When the eviction pool is empty or lacks sufficient candidates, this function is called to populate it. It samples approximately 5 keys from the dictionary. The sampled keys are inserted into the pool if they are “better” (i.e., have a higher idle time, making them better candidates for eviction) than existing elements. The pool is maintained in ascending order of idle time, meaning the worst candidate (highest idle time) is at the end. For efficient insertion, Redis uses memmove to shift elements when a new candidate needs to be inserted in the middle of the sorted array.

Redis’s Dual Dictionary Structure: A Golden Nugget

One of the most insightful discoveries from the Redis source code is its use of two distinct dictionaries:

1. Key Dictionary: This is the primary dictionary storing all keys and their corresponding values.
2. Expires Dictionary: This specialized dictionary stores only keys that have an expiration time set. For these keys, it stores the key itself and its absolute expiration timestamp, but not the value. The actual value is still stored in the key dictionary.

This dual-dictionary approach significantly optimizes operations involving expired keys. By having a separate expires dictionary, Redis can quickly iterate over only the keys that might expire, making eviction, sampling, and other time-sensitive algorithms much more efficient. When sampling for eviction, Redis can prioritize sampling from the expires dictionary, as these keys are more likely to be evicted.

Performing Evictions: performEvictions

The performEvictions function is the core of the eviction process. Unlike a simple key count limit, Redis’s eviction is primarily driven by memory utilization. It aims to free memory until the total memory consumed falls below a configured maxmemory threshold.

The eviction loop continues as long as memory_freed is less than memory_to_free. Inside the loop:

1. It identifies the worst key (the one with the highest idle time) from the eviction pool, which is always at the end of the sorted pool.
2. It performs various checks and handles edge cases specific to Redis’s sophisticated database operations.
3. The key is deleted from both the key dictionary and the expires dictionary.
4. Relevant hooks and notifications, such as propagateExpire, are triggered to inform other system components about the eviction.

LFU and Zmalloc

• LFU (Least Frequently Used): Redis also supports LFU eviction. Interestingly, it reuses the same 24-bit field as LRU but stores frequency information instead of last access time.
• zmalloc: Redis implements its own memory allocation wrapper called zmalloc. This wrapper around the standard malloc function allows Redis to track the exact amount of memory it consumes, which is critical for its memory-driven eviction policies.

Go Implementation of Approximated LRU

Inspired by Redis’s design, we can implement a similar approximated LRU cache in Go.

Object and Store Modifications (object.go)

To support LRU and expiration, the Object structure and the Store (our main key-value dictionary) require modifications:

• Object Structure: Instead of an expire field, we introduce lastAccessAt of type uint32 to store the 24-bit LRU clock value. Go does not natively support bit fields, so uint32 is used, though a more complex bit-packing approach could achieve 24-bit storage.

type Object struct { Value interface{} lastAccessAt uint32 // 24-bit clock resolution } ```

• Store Structure: We introduce a separate expires map, similar to Redis’s dual-dictionary approach. This map stores object pointers (or keys) and their absolute expiration times in milliseconds.

type Store struct { data map[string]*Object expires map[string]uint64 // Key -> Absolute Expiration Time in Milliseconds // … other fields } ```

• Helper Functions:

  • setExpiry(obj *Object, durationMs uint64): This function adds or updates an entry in the expires map for a given object and duration.
  • hasExpired(obj *Object) bool: Checks if an object has expired by comparing its expiration time in the expires map with the current Unix milliseconds.

• Put and Get Operations: Both Put (update) and Get (access) operations must update the lastAccessAt field of the accessed object to the current 24-bit clock. The Get operation also incorporates the hasExpired check, triggering a deletion if the key is expired.

• Delete Operation: Deletion must now remove the key from both the main store map and the expires map.

Clock and Idle Time Calculation (eviction.go)

The core eviction logic resides in eviction.go:

• getCurrentClock() uint32: This function returns the current 24-bit LRU clock, calculated as the least significant 24 bits of the current Unix epoch seconds.

func getCurrentClock() uint32 { // Unix() returns seconds since epoch return uint32(time.Now().Unix()) & ((1 << 24) - 1) } ```

• getIdleTime(currentClock, lastAccessAt uint32) uint32: This function implements the same idle time calculation logic as Redis C, handling clock wrap-around.

func getIdleTime(currentClock, lastAccessAt uint32) uint32 { if currentClock >= lastAccessAt { return currentClock - lastAccessAt } else { // Clock wrapped around return ((1 << 24) - 1 - lastAccessAt) + currentClock } } ```

Eviction Pool Implementation (eviction.go)

The evictionPool in Go is a struct containing an array of poolItems and a keySet for quick lookups.

type PoolItem struct {
    Key        string
    LastAccessAt uint32
}

type EvictionPool struct {
    PoolItems []PoolItem
    KeySet    map[string]struct{}
    // ... custom sort interface methods
}

• populateEvictionPool(store *Store): This function samples keys from the main store (or expires map for better efficiency, if implemented) and adds them to the EvictionPool.

  • It samples 5 keys.
  • Before adding, it checks if the key already exists in the keySet to avoid duplicates.
  • If the pool has space (less than 16 elements), the new PoolItem is appended.
  • If the pool is full, the new item is only added if its idle time is worse (higher) than the current worst item in the pool. In this case, the best item (lowest idle time) is removed from the pool to make space.
  • Performance Note: For simplicity, this implementation repeatedly sorts the entire PoolItems array by idle time after every insertion. A more optimized approach would use an insertion sort or a min-heap/priority queue to maintain sorted order more efficiently.

• pop() *PoolItem: This function removes and returns the best candidate for eviction (the item with the lowest idle time, which is at index 0 after sorting) from the EvictionPool.

The Eviction Loop: allKeysLRU

The main eviction function, allKeysLRU, is triggered when the cache hits its maxKeys limit (in this simplified Go implementation, unlike Redis’s memory-based limit).

func (s *Store) allKeysLRU() {
    // 1. Populate the eviction pool with sampled keys
    s.evictionPool.populateEvictionPool(s) // Pass the store to sample from

    // 2. Determine how many keys to evict (simplified: based on maxKeys)
    keysToEvict := len(s.data) - s.maxKeys

    // 3. Loop and evict until target memory/key count is met
    for i := 0; i < keysToEvict; i++ {
        item := s.evictionPool.pop()
        if item == nil {
            break // Pool is empty
        }
        s.Delete(item.Key) // Delete from both store and expires
    }
}

This function first populates the eviction pool, then iteratively pops the best eviction candidates from the pool and Deletes them from the main store until the maxKeys limit is respected.

Demonstration and Key Takeaways

When this approximated LRU implementation is run, we observe that the number of keys in the cache consistently stays at or below the configured maxKeys limit (e.g., 100 keys). As soon as the limit is breached, eviction is triggered, removing the keys with the highest idle time and bringing the cache size back within bounds.

Implementing the approximated LRU algorithm offers a fascinating insight into efficient cache management. While our Go implementation simplifies some aspects (like using maxKeys instead of maxmemory and naive sorting), it effectively demonstrates the core principles of sampling, idle time tracking, and pool-based eviction, mirroring Redis’s robust approach.

What’s Next?

In the next video, we will explore Redis’s sophisticated memory management techniques, specifically how zmalloc enables Redis to accurately track and cap its memory utilization, a crucial aspect of its maxmemory eviction policy.

Source Code

The source code for this implementation can be found at github.com/arpitbbhayani/implementation. You can navigate through the commits to find the relevant changes for this LRU implementation.