Introduction to LFU Cache

Introduction

LFU (Least Frequently Used) Cache Algorithm is a common cache management algorithm. Its basic idea is to eliminate the least frequently used data in the cache when the cache is full. This can effectively ensure that the data stored in the cache is as useful as possible, thereby improving the hit rate of the cache.

Application Scenatio

(Source from Oracle)

The cache proxy is used to optimize network utilization and improve the response speed of the service by caching hot static files in the limited storage resources at cache server. The cost of implementation should be as small as possible to ensure that the proxy can work normally under high load.

When the cache is full, the LFU algorithm is used to eliminate the least frequently used data in the cache. LRU is also a good choice for this scenario, but in a specific scenario, such as accessing a series of different data in a round-robin fashion, which causes the cache to be replaced continuously, LFU may fail.

Interface Design

class LFUCache {
Public:
    // 1. Construct a cache with capacity size
    LFUCache(int capacity) {}
    
    // 1. retrieve the value by its key
    // 2. return -1 if not found
    int get(int key) {}

    // 1. put the key-value pair into the cache
    // 2. delete the least frequently used data if the cache is full
    // 3. if multiple data have the same frequency, delete the least recently used one
    void put(int key, int val) {}
}

Data Structure

The LFU cache is implemented by two hash maps in order to achieve O(1) time complexity for both get and put operations.

The first hash map is used to store the key-value pairs.
The second hash map is used to store the frequency of each key.

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

The data with the smallest frequency is the least frequently used data.

If multiple data have the same frequency, the data that has not been accessed for the longest time is considered to be the least frequently used data.

C++ Implementation

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

using namespace std;

struct Node
{
    int key;
    int value;
    int freqeuncy;
    Node(int k, int v, int f) : key(k), value(v), freqeuncy(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->freqeuncy;
        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_freq
            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->freqeuncy;
            freq_table[freq].erase(node);
            if (freq_table[freq].size() == 0)
            {
                // remove old frequency
                freq_table.erase(freq);
                // if the min_freq = cur_freq, update the min_freq
                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 Issues

Hot data are resistant to eviction: Some data may only be highly accessed during a short period of time. However, it accumulated a high frequency during this period, so it is difficult to be evicted after its hot period.
New data is easy to be evicted: If only evicting the data with the smallest frequency, the new data will be evicted more easily. This is because the new data has a frequency of 1, and the old data accumulated a high frequency than the new data.
Space problem: If you record the all information of all the data that has accessed, it will take up more memory space.

Solution

LFU-Aging

LFU-Aging is a hybrid eviction policy that combines elements of both LFU and LRU (Least Recently Used). Like LFU, it tracks the frequency of access to keys, but it also takes into account the age of the key, using a decay factor to give preference to keys that have been accessed more recently.

In Redis, the LFU-Aging eviction policy is implemented using a counter that is incremented every time a key is accessed. The counter is then decayed over time using a decay factor, which can be configured by the user. When a key is evicted, the key with the lowest counter value is removed from the cache.

By combining elements of both LFU and LRU, LFU-Aging aims to strike a balance between the two approaches, taking into account both the frequency of access to keys and the recency of access. This can help to prevent the problem of cache thrashing, where the cache is constantly being evicted and refilled, and can improve the overall performance of the cache.

In order to solve the above three problems, LFU-Aging introduces the following three strategies:

Adjust the growth rate of the counter by configuring the server.lfu_log_factor parameter. The parameter is bigger, the counter will grow slower.
Adjust the decay rate of the counter by configuring the server.lfu_decay_time parameter. That determines how quickly the counter decays over time.
Adjust the initial value of the counter by set the value of LFU_INIT_VAL variable. The default value is 5.

Window-LFU

Window-LFU is a variant of the LFU (Least Frequently Used) eviction policy.

Like traditional LFU, Window-LFU tracks the frequency of access to keys in a cache, with the goal of identifying and evicting keys that are accessed least frequently.

However, unlike traditional LFU, which increments a counter every time a key is accessed, Window-LFU uses a sliding window approach to track the frequency of access to keys.

In the Window-LFU approach, the cache is divided into a series of fixed-size windows, and the frequency of access to each key is tracked within each window. When a key is accessed, its counter is incremented within the current window. As the window slides forward over time, the counter for each key is decremented, so that the counter reflects the frequency of access to the key within the current window. Keys with low counters are identified as candidates for eviction when the cache reaches capacity.

Window-LFU is attractive because it can adapt to changing access patterns over time, and it has been shown to perform well in a variety of settings. However, it is not widely used in practice, and it is not implemented in popular cache eviction libraries such as Redis.

Summary

In this article, we have introduced the LFU (Least Frequently Used) eviction policy, which is a cache eviction policy that tracks the frequency of access to keys in a cache, and evicts keys that are accessed least frequently. We have also introduced two variants of LFU, LFU-Aging and Window-LFU, which aim to improve the performance of LFU by taking into account the age of keys, and by using a sliding window approach to track the frequency of access to keys.