什麼是 LFU 快取演算法？

LFU 是什麼？

LFU 是 “Least Frequently Used” 的縮寫。

LFU Cache 是一種常見的快取管理演算法，它的設計思想是當快取滿時，淘汰快取中最不常使用的資料。透過這個簡單的機制來保證快取中儲存的資料盡可能的有用，從而提高快取的命中率。

LFU 的應用場景

LFU 的經典應用場景是 HTTP 快取代理(proxy)應用，它位於網路服務和使用者之間，如下圖所示：

(圖片來源 Oracle)

快取代理的作用是在快取伺服器上有限的儲存空間中，盡可能快取熱門的靜態檔案，從而加快網路服務的回應速度和最佳化網路的利用率。其實現的代價應盡可能的小，以保證在高負載下代理仍能正常工作。

LRU 也是一個不錯的選擇，但在某些特定的場景下，例如存取一系列不同的資料，這些資料的存取順序是輪詢的，這會導致快取不斷的被替換，LFU 可能會失效。

介面設計

CPP

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) {}
}

資料結構設計

LFU 快取的實現依賴於兩個雜湊表，以實現 get 和 put 操作的時間複雜度為 O(1)。

第一個雜湊表用於儲存鍵值對。
第二個雜湊表用於儲存每個鍵的存取頻率。
每個鍵的存取頻率用於確定最不常使用資料的順序。

最不常使用的資料是指存取頻率最小的資料，如果多個資料的存取頻率相同，那麼最不常使用的資料是最近最久未被存取的資料。

C++ 範例程式碼

CPP

#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;
}

LFU 的潛在問題

熱點資料不易被移出快取：有些資料可能只是在短時間內被高頻存取。但是它在這段時間內累積了很高的頻率，所以在它的熱點期過後也會長時間留在快取中不易被移出。
新加入的資料更容易被移出快取：如果只是移出頻率最小的資料，那麼新加入的資料會更容易被移出。這是因為新加入的資料的頻率預設為 1，而老資料累積了很長時間，所以頻率比新資料要高多。
空間問題：如果記錄了所有資料的存取資訊，那麼會佔用更多的記憶體空間。

LFU 的一些改進

LFU-Aging

LFU-Aging 是一個混合的淘汰策略，它結合了 LFU 和 LRU 的一些特點。和 LFU 一樣，它會記錄每個 key 的存取頻率，但是它也會考慮 key 的年齡，使用衰減因子來賦予最近存取過的 key 更高優先順序。

LFU-Aging 淘汰策略是透過一個計數器來實現的。每次存取一個 key 時，計數器都會增加。隨著時間的推移，計數器會使用衰減因子進行衰減。使用者可以透過配置來設定衰減因子。當一個 key 被移出快取時，計數器值最小的 key 會被移出。

透過結合 LFU 和 LRU 的一些特點，LFU-Aging 旨在在兩種方法之間取得平衡，考慮到 key 的存取頻率和存取的最近性。這可以幫助防止快取淘汰和填充的問題，可以提高快取的整體效能。

在 Redis 中，為了解決上面三個問題，LFU-Aging 引入了以下三種策略：

透過配置 server.lfulogfactor 參數來 調整計數器的增長速率。
- 該參數越大，計數器的增長速率越慢。
透過配置 server.lfudecaytime 參數來 調整計數器的衰減速率。
- 該參數決定計數器在多長時間內衰減到最小頻率。
透過設定 LFUINITVAL 變數的值來 調整計數器的初始值。
- 預設值為 5。

Window-LFU

Window-LFU 是 LFU 淘汰策略的一種變體。

和傳統的 LFU 一樣，Window-LFU 也會追蹤快取中 key 的存取頻率，目的是識別並移出存取頻率最低的 key。

但是不同於傳統的 LFU，它每次存取一個 key 時，使用滑動視窗的方法來更新追蹤 key 的存取頻率。

在 Window-LFU 中，快取被分成一系列固定大小的視窗，每個視窗都會追蹤 key 的存取頻率。當存取一個 key 時，它的計數器會在當前視窗中增加。隨著時間的推移，視窗會向前滑動，每個 key 的計數器都會減少，這樣計數器就會反映出 key 在當前視窗中的存取頻率。當快取達到容量時，計數器較低的 key 會被標記為淘汰的候選者。

Window-LFU 是非常有吸引力的，因為它可以適應隨著時間推移而變化的存取模式，並且已經被證明在各種設定中表現良好。但是，它在實踐中並不廣泛使用，也沒有在 Redis 等流行的快取應用中實現。

總結

在這篇文章中，我們介紹了 LFU（Least Frequently Used）淘汰策略，它是一種快取淘汰策略，用來追蹤快取中 key 的存取頻率，並淘汰存取頻率最低的 key。同時，我們還介紹了 LFU 的兩個變體，LFU-Aging 和 Window-LFU，它們旨在透過考慮 key 的年齡以及使用滑動視窗方法來追蹤 key 的存取頻率來解決 LFU 潛在的效能問題。

參考資料

LeetCode - LFU Cache Question

LeetCode - LFU Cache Solution

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

什麼是 LFU 快取策略