How Redis Implements LFU Eviction Using Morris Counter

Redis, known for its high performance and versatile data structures, supports various eviction strategies to manage memory efficiently. Beyond the commonly understood Least Recently Used (LRU) strategy, Redis also implements Least Frequently Used (LFU). LFU aims to evict keys that have been accessed the fewest times. This document delves into how Redis achieves this, particularly focusing on its space-efficient approach using an approximate counting algorithm known as the Morris Counter.

The Challenge of LFU: Tracking Frequency

Implementing LFU requires tracking the access frequency of each key. A naive approach would involve storing a simple integer counter for every key and incrementing it on each access. However, this poses significant challenges for a memory-optimized system like Redis:

1. Space Overhead: Storing a full-fledged counter (e.g., 64-bit integer) for potentially millions of keys would consume substantial memory, defeating the purpose of an in-memory data store.
2. Stale Popularity: A key accessed heavily early on but rarely later might retain a high count, preventing its eviction even if it’s no longer actively used. This necessitates a decay mechanism.

Redis addresses these challenges with a highly frugal and intelligent implementation.

Redis’s Approximate LFU Strategy

Redis’s LFU implementation is built upon two core principles:

1. Approximate Counting: Instead of exact frequency counts, Redis uses an approximate counter that is highly space-efficient.
2. Time-Based Decay: The frequency count is decayed over time, ensuring that older, less recent accesses contribute less to a key’s overall “frequency score.”

Remarkably, Redis reuses the existing 24-bit lru field within its redisObject structure to implement LFU. These 24 bits are split into two parts:

• 16 bits: Used to store the Last Decrement Time (LDT).
• 8 bits: Used to store a Logarithmic Counter, which is an implementation of the Morris Counter.

Last Decrement Time (LDT): 16 Bits for Temporal Decay

The 16 bits dedicated to LDT store the Unix time in minutes, specifically the least significant 16 bits of the current Unix timestamp divided by 60. This allows Redis to track when a key’s counter was last decayed.

The purpose of LDT is to implement a decay mechanism:

• Preventing Stale Popularity: If a key was accessed frequently in the past but not recently, its count should gradually decrease to make it a candidate for eviction.
• On-Access Decay: Instead of running a background thread to periodically decay all counters (which would be resource-intensive), Redis performs decay on access. When a key is accessed, Redis calculates the time elapsed since its LDT and adjusts its counter accordingly.
• Exponential Decay: When the logarithmic counter V is reduced by 1, the effective actual count N (where V = log(1+N)) is roughly halved. This provides an exponential decay effect, making keys rapidly lose “popularity” if not accessed.

Logarithmic Counter: 8 Bits for Approximate Frequency (Morris Counter)

The 8 bits are used to store a logarithmic counter, which can represent values from 0 to 255. This is where the Morris Counter algorithm comes into play.

Why a Logarithmic Counter?

A logarithmic counter is crucial for LFU because:

• Higher Precision for Smaller Values: For keys accessed infrequently (e.g., 1, 2, 5 times), even small differences in frequency are significant. A logarithmic scale provides higher precision in this lower range.
• Lower Precision for Larger Values: For keys accessed very frequently (e.g., 10,000, 10,100, 11,000 times), the difference between 10,000 and 10,100 is less significant in relative terms. A logarithmic scale naturally tapers off precision for larger values, saving space without losing much practical information.

The relationship between the stored value V (8 bits) and the actual count N is approximately V = log_base(1 + N). Redis uses a base-2 logarithm, specifically V = log2(N+1) / log2(LFU_LOG_INCR_FACTOR). The LFU_LOG_INCR_FACTOR is a configurable value (defaulting to 10 in Redis 7.0+), which effectively scales the logarithm.

The Morris Counter Mechanism: Probabilistic Increment

Since we only have 8 bits for V (0-255), we cannot simply increment V on every access, especially if N can grow very large. The Morris Counter solves this by probabilistically incrementing V.

The core idea is to increment V to V+1 with a probability P that decreases as V (and thus N) increases. This ensures that V increments more frequently for small N and less frequently for large N.

The probability P is calculated based on the “cost” or inaccuracy incurred by incrementing V. If N(V) is the estimated actual count for a stored value V, and N(V+1) for V+1, then the difference N(V+1) - N(V) represents the jump in estimated count.

• If this difference is small (for small V), the probability of incrementing V should be high.
• If this difference is large (for large V), the probability of incrementing V should be low.

Redis’s implementation uses a probability P derived from 1 / (N(V+1) - N(V)). More precisely, it uses a formula that involves LFU_LOG_INCR_FACTOR. When a key is accessed:

1. A random number R is generated.
2. If R is less than P, V is incremented. Otherwise, V remains unchanged.

This probabilistic increment results in a “step-like” increase when plotting V against actual accesses, where V stays constant for a period before jumping to the next value.

Redis Source Code Insights

The transcript highlights several key functions in Redis’s evict.c and db.c files that demonstrate the LFU implementation:

1. lfuGetTimeInMinutes()

This function retrieves the current Unix time in minutes and masks it to 16 bits (65535). This value is stored as the Last Decrement Time (LDT) in the lru field.

// Pseudocode based on description
uint16_t lfuGetTimeInMinutes() {
    return (server.unixtime / 60) & 0xFFFF; // 0xFFFF is 65535
}

2. lfuTimeElapsed()

Similar to LRU, this function calculates the elapsed time in minutes between the current time and the stored LDT, handling potential rollovers of the 16-bit timestamp.

// Pseudocode based on description
long lfuTimeElapsed(uint16_t ldt) {
    uint16_t now = lfuGetTimeInMinutes();
    if (now >= ldt) {
        return now - ldt;
    } else {
        // Handle 16-bit rollover
        return (0xFFFF - ldt) + now;
    }
}

3. LFU_LOG_INCR_FACTOR and Probabilistic Increment

The core Morris Counter logic is encapsulated around LFU_LOG_INCR_FACTOR. The LFU_LOG_INCR macro (or similar function) in the source code shows the random number generation and comparison to decide whether to increment the 8-bit counter.

// Simplified pseudocode for probabilistic increment
// 'count' is the current 8-bit logarithmic counter
// 'LFU_LOG_INCR_FACTOR' is a configuration value (e.g., 10)
int lfuLogIncr(int count) {
    if (count == 255) return 255; // Max value
    double r = (double)rand() / RAND_MAX; // Random number between 0 and 1
    double p = 1.0 / (count * LFU_LOG_INCR_FACTOR + 1); // Simplified probability
    if (r < p) {
        count++;
    }
    return count;
}

The actual Redis implementation uses a more precise formula for p based on LFU_LOG_INCR_FACTOR and the current counter value to achieve the desired logarithmic distribution.

4. lfuDecrAndReturn()

This function is responsible for calculating the decayed counter value. It takes the current 24-bit lru value, extracts the LDT (16 bits) and the logarithmic counter (8 bits), calculates the elapsed periods (minutes) based on server.lfu_decay_time (default 1 minute), and subtracts these periods from the counter. Crucially, this function returns the new counter value; it does not persist it. The persistence happens in updateLFU.

// Pseudocode for decay calculation
int lfuDecrAndReturn(uint64_t lru_value) {
    uint16_t ldt = (lru_value >> 8) & 0xFFFF; // Extract 16-bit LDT
    uint8_t counter = lru_value & 0xFF;       // Extract 8-bit counter

    long elapsed_minutes = lfuTimeElapsed(ldt);
    long periods = elapsed_minutes / server.lfu_decay_time; // server.lfu_decay_time is typically 1

    if (periods > counter) {
        return 0; // Counter cannot go below zero
    } else {
        return counter - periods;
    }
}

5. updateLFU()

This is the central function invoked every time a key is accessed when LFU eviction is enabled.

1. It calls lfuDecrAndReturn() to get the decayed counter value.
2. It then calls the probabilistic increment logic (lfuLogIncr or similar) to increment the counter based on the current access.
3. Finally, it reconstructs the 24-bit lru field by combining the new LDT (current time in minutes) and the updated 8-bit logarithmic counter, storing this back into the redisObject.

// Pseudocode for updateLFU on key access
void updateLFU(redisObject *o) {
    // 1. Get decayed counter
    int current_counter = lfuDecrAndReturn(o->lru);

    // 2. Probabilistically increment
    int new_counter = lfuLogIncr(current_counter);

    // 3. Reconstruct and store new lru field
    uint16_t new_ldt = lfuGetTimeInMinutes();
    o->lru = ((uint64_t)new_ldt << 8) | new_counter;
}

Redis also saturates the counter at a certain effective frequency (e.g., 1 million accesses), meaning that beyond this point, further increments won’t significantly change its eviction priority. This prevents extremely old, high-frequency keys from perpetually staying in memory.

Conclusion

Redis’s LFU implementation is a testament to ingenious engineering for space efficiency. By repurposing 24 bits, combining a time-based decay mechanism with a probabilistic Morris Counter, it provides an effective approximate LFU strategy. This approach minimizes memory overhead while still providing a robust eviction policy, demonstrating the power of approximate algorithms in distributed systems.