What is the LFU Cache Algorithm?

What is LFU?

LFU stands for "Least Frequently Used".

An LFU Cache is a common cache management algorithm. Its core idea is that when the cache is full, it evicts the least frequently used data. This simple mechanism helps keep the cache as relevant as possible, thereby improving the cache hit rate.

Use Cases for LFU

A classic use case for LFU is in HTTP caching proxies. These proxies sit between the network service and the user, as shown in the diagram below:

(Image source: Oracle)

The role of a caching proxy is to cache popular static files within the limited storage space of the cache server, thereby speeding up the response time of the network service and optimizing network utilization. The implementation cost should be as low as possible to ensure the proxy can still function correctly under high load.

LRU is also a good choice, but in certain specific scenarios — such as accessing a series of different data in a round-robin order — the cache can be constantly churned, which might cause LRU to fail.

Interface Design

CPP

class LFUCache {
Public:
    // Construct a cache with capacity size
    LFUCache(int capacity) {}
    // Retrieve the value by its key, return -1 if not found
    int get(int key) {}
    // Put the key-value pair into the cache
    // Delete the least frequently used data if the cache is full
    // If multiple data have the same frequency, delete the least recently used one
    void put(int key, int val) {}
}

Data Structure Design

The implementation of an LFU cache relies on two hash tables to achieve O(1) time complexity for both get and put operations.

The first hash table stores the key-value pairs.
The second hash table stores the access frequency for each key.

The access frequency of each key is used to determine the order of the least frequently used data.

The least frequently used data refers to the data with the smallest access frequency. If multiple data items share the same frequency, the least frequently used data is the one that has been accessed least recently.

C++ Example Code

CPP

#include <list>
#include <random>
#include <iostream>
#include <unordered_map>

using namespace std;

struct Node
{
    int key;
    int value;
    int frequency;
    Node(int k, int v, int f) : key(k), value(v), frequency(f) {}
};

class LFUCache
{
private:
    int minFreq;                                        // minimum frequency of the cache
    int capacity;                                       // maximum capacity of the cache
    unordered_map<int, list<Node>::iterator> key_table; // key to iterator mapping table
    unordered_map<int, list<Node>> freq_table;          // frequency to list mapping table

public:
    int HIT = 0;
    int MISS = 0;

    LFUCache(int capacity){
        this->capacity = capacity;
        minFreq = 0;
        key_table.clear();
        freq_table.clear();
    }

    int get(const int &key)
    {
        // if the capacity is 0, return -1
        if (capacity == 0)
        {
            return -1;
        }
        // find the iterator of the node
        auto it = key_table.find(key);
        // if the node is not found, return -1
        if (it == key_table.end())
        {
            MISS++;
            return -1;
        }
        list<Node>::iterator node = it->second;
        int value = node->value;
        int freq = node->frequency;
        freq_table[freq].erase(node);
        // if the list is empty, remove it from the map, and update the minimum frequency
        if (freq_table[minFreq].size() == 0)
        {
            freq_table.erase(freq);
            // if the minimum frequency is equal to current frequency, increase the min frequency
            if (minFreq == freq)
                minFreq++;
        }
        // insert the node to the freq + 1 position
        freq_table[freq + 1].push_front(Node(key, value, freq + 1));
        // update the iterator in the map
        key_table[key] = freq_table[freq + 1].begin();
        HIT++;
        return value;
    }

    void put(int key, int value)
    {
        // if the capacity is 0, return
        if (capacity == 0)
            return;
        // find the iterator of the node
        auto it = key_table.find(key);
        if (it == key_table.end())
        {
            // if the key is not in the cache, will insert it
            // check the capacity first
            if (key_table.size() == capacity)
            {
                // if the cache is full, remove the least frequently used node
                // get the last node by the minimum frequency
                auto minNode = freq_table[minFreq].back();
                key_table.erase(minNode.key);
                // insert the new node now
                freq_table[minFreq].pop_back();
                if (freq_table[minFreq].size() == 0)
                {
                    // if the list is empty, remove it from the map
                    freq_table.erase(minFreq);
                }
            }
            // update the iterator in the map
            minFreq = 1;
            freq_table[minFreq].push_front(Node(key, value, minFreq));
            key_table[key] = freq_table[minFreq].begin();
        }
        else
        {
            // if the key is in the cache, update the frequency
            list<Node>::iterator node = it->second;
            int freq = node->frequency;
            freq_table[freq].erase(node);
            if (freq_table[freq].size() == 0)
            {
                // remove old frequency
                freq_table.erase(freq);
                // if the min frequency = current frequency, update the min frequency
                if (minFreq == freq)
                    minFreq++;
            }
            // insert the node to the freq + 1 position
            freq_table[freq + 1].push_front(Node(key, value, freq + 1));
            // update the iterator in the map
            key_table[key] = freq_table[freq + 1].begin();
        }
    }

    void clear()
    {
        key_table.clear();
        freq_table.clear();
        minFreq = 0;
        HIT = 0;
        MISS = 0;
    }
};

void testCase(){
    // from leetcode example
    LFUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // returns 1
    cache.put(3, 3);              // evicts key 2
    cout << cache.get(2) << endl; // returns -1 (not found)
    cout << cache.get(3) << endl; // returns 3.
    cache.put(4, 4);              // evicts key 1.
    cout << cache.get(1) << endl; // returns -1 (not found)
    cout << cache.get(3) << endl; // returns 3
    cout << cache.get(4) << endl; // returns 4
}

int main()
{
    // testCase();

    const int CAPACITY = 200;
    const int NUM = 1000;

    LFUCache cache(CAPACITY);

    // sequential access
    cout << "Sequential Access" << endl;
    cache.clear();
    for (int i = 0; i < NUM; ++i)
    {
        if (cache.get(i) == -1)
        {
            cache.put(i, i);
        }
    }
    cout << "HIT: " << cache.HIT << "\t\tMISS: " << cache.MISS
         << "\t\tHit Rate: " << (double)cache.HIT / (cache.HIT + cache.MISS) << endl;

    // random access with uniform distribution
    cout << "Random Access with Uniform Distribution" << endl;
    cache.clear();
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, NUM);
    for (int i = 0; i < NUM; ++i)
    {
        int key = dis(gen);
        if (cache.get(key) == -1)
        {
            cache.put(key, key);
        }
    }
    
    cout << "HIT: " << cache.HIT << "\t\tMISS: " << cache.MISS
         << "\t\tHit Rate: " << (double)cache.HIT / (cache.HIT + cache.MISS) << endl;


    // random access with normal distribution
    cout << "Random Access with Normal Distribution" << endl;
    cache.clear();
    int mu = NUM / 2;
    int sigma = NUM / 6;
    normal_distribution<> ndis(mu, sigma);
    for (int i = 0; i < NUM*10; ++i)
    {
        int key = ndis(gen);
        if (cache.get(key) == -1)
        {
            cache.put(key, key);
        }
    }

    cout << "HIT: " << cache.HIT << "\t\tMISS: " << cache.MISS
         << "\t\tHit Rate: " << (double)cache.HIT / (cache.HIT + cache.MISS) << endl;

    return 0;
}

Potential Problems with LFU

Hot data is hard to evict: Some data might be accessed very frequently only for a short period. During that time, it accumulates a high frequency count, so it can remain in the cache for a long time even after its popularity fades.
New data is more easily evicted: If only the data with the lowest frequency is evicted, newly added data is more likely to be removed. This is because new data starts with a default frequency of 1, while older data has accumulated a much higher frequency over time.
Space overhead: Tracking access information for all data consumes more memory.

Improvements to LFU

LFU-Aging

LFU-Aging is a hybrid eviction strategy that combines features of LFU and LRU. Like LFU, it tracks the access frequency of each key, but it also considers the key's age, using a decay factor to give higher priority to recently accessed keys.

The LFU-Aging eviction strategy is implemented using a counter. Each time a key is accessed, the counter increments. Over time, the counter decays using a decay factor. Users can configure the decay factor. When a key needs to be evicted, the key with the smallest counter value is removed.

By combining features of LFU and LRU, LFU-Aging aims to strike a balance between the two methods, considering both the access frequency and the recency of access. This can help prevent cache thrashing and improve overall cache performance.

In Redis, to address the three problems mentioned above, LFU-Aging introduces the following three strategies:

Adjust the counter growth rate by configuring the server.lfu_log_factor parameter.
- The larger this parameter, the slower the counter growth rate.
Adjust the counter decay rate by configuring the server.lfu_decay_time parameter.
- This parameter determines how long it takes for the counter to decay to its minimum frequency.
Adjust the initial counter value by setting the LFU_INIT_VAL variable.
- The default value is 5.

Window-LFU

Window-LFU is a variant of the LFU eviction strategy.

Like traditional LFU, Window-LFU tracks the access frequency of keys in the cache, aiming to identify and evict the least frequently used keys.

However, unlike traditional LFU, it uses a sliding window approach to update the tracked access frequency each time a key is accessed.

In Window-LFU, the cache uses a logical sliding window to track access frequency. Each key's counter increments when accessed within the current window. As the window slides forward over time, the counters for each key decrease, so the counter reflects the key's access frequency within the current window. When the cache reaches capacity, keys with lower counters are marked as candidates for eviction.

Window-LFU is attractive because it can adapt to changing access patterns over time and has been shown to perform well in various settings. However, it is not widely used in practice and is not implemented in popular caching applications like Redis.

Summary

In this article, we introduced the LFU (Least Frequently Used) eviction strategy, a cache eviction policy that tracks the access frequency of keys in the cache and evicts the least frequently used keys. We also discussed two variants of LFU, LFU-Aging and Window-LFU, which aim to address potential performance issues by considering the age of keys and using a sliding window method to track access frequency.

References

LeetCode - LFU Cache Question

LeetCode - LFU Cache Solution

An O(1) algorithm for implementing the LFU cache eviction scheme

What is the LFU Cache Eviction Policy?