A brief discussion on the source code analysis of LFU algorithm in Redis

Redis's LFU (Least Frequently Used, least frequently used) elimination algorithm is mainly used formaxmemory-policySet toallkeys-lfuorvolatile-lfuWhen, use the key with the minimum frequency of use to eliminate it. Its core implementation involves access frequency counting and time attenuation mechanisms, and the source code is mainly concentrated insrc/andsrc/in the file.

1. LFU count storage

Redis uses 8-bitLRUFields are used to store access frequency counts, stored inrobjStructurallruIn the field:

struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; // for LRU/LFU calculations    int refcount;
    void *ptr;
};

inlruThe 8-bit space of the variable is split:

• First 6-bit(counter): used to store access count, maximum value of 63.
• The last 2-bit(clock): used for time attenuation calculation.

2. Calculation of access count

The LFU count is incremented every time the key is accessed, but the increment method is not simple.+1, instead use the logarithmic growth method to avoid the monopoly of certain keys due to high visits:

unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long counter = LFUGetCounter(o);
    if (counter == 0) return 0;
    if (rand() % (counter + 1) == 0) counter--;
    LFUSetCounter(o, counter);
    return counter;
}

When counting growth:

int LFUIncrAndReturn(robj *o) {
    unsigned long counter = LFUGetCounter(o);
    if (counter < 63) {
        if (rand() % (counter + 1) == 0) counter++;
    }
    LFUSetCounter(o, counter);
    return counter;
}

This means:

• The counting grows faster at initially (1 → 2 → 3…)
• The higher the count, the lower the probability of growth (comply with the logarithmic curve)
• This prevents some high access keys from long-term survival.

3. Attenuation of LFU access frequency

Since some data may be accessed frequently in the short term, but will no longer be accessed for a long time, Redis adopts a time decay mechanism:

Decrement the access count every 1 minute.

Use 2-bit to record the last visit timelfu_clock, trigger attenuation every 60s:

#define LFU_INIT_VAL 5 // Initial access countunsigned long LFUDecrAndReturn(robj *o) {
    unsigned long counter = LFUGetCounter(o);
    if (counter == 0) return 0;
    if (rand() % (counter + 1) == 0) counter--;
    LFUSetCounter(o, counter);
    return counter;
}

This method will reduce the count according to a certain probability, ensuring that the keys visited recently will not be easily eliminated, while keys that have not been accessed for a long time will be gradually eliminated.

4. Elimination strategy

whenmaxmemoryWhen it exceeds, Redis needs to eliminate some data, and LFU mainly executes:

Iterate through the data and find the key with the smallest access count.

Adoptvolatile-lfuorallkeys-lfuPerform data deletion:

evictionPoolPopulate(dict *sample_dict) {
    // Randomly sample N keys from the dictionary    for (i = 0; i < EVPOOL_SIZE; i++) {
        lfu = LFUGetCounter(entry);
        if (lfu < min_lfu) {
            min_lfu = lfu;
            min_entry = entry;
        }
    }
    // The least number of elimination visits    dictDelete(sample_dict, min_entry);
}

Use approximate random sampling instead of traversing all keys to improve efficiency.

5. Key Summary

• Storage method: UseThe 8-bit space of the variable stores access count and time information.
• Access count growth: Use logarithmic growth strategy to prevent a single key from consuming memory due to excessive visits.
• Time decay: Attenuates the access frequency count every minute to ensure that long-term unreached keys are eliminated.
• Elimination strategy: Sample multiple keys and find the key with the least access count to delete.

Redis's LFU mechanism is more suitable for hot data access scenarios than LRU, avoiding some short-term popular keys occupying a large amount of cache, and also allowing real high-frequency access to data to survive longer.

This is the end of this article about the analysis of the source code of the LFU algorithm in Redis. For more related content of Redis LFU algorithm, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!