什麼是 LRU 快取演算法？

什麼是快取 (Cache)？

快取是一種用於儲存經常存取的資料或指令的位置，藉由減少大量昂貴的操作來加快存取速度。它允許處理器更快地存取資料和指令，從而大幅提升系統的效能。

CPU 快取 CPU 快取是一種容量較小的高速記憶體，通常整合在 CPU 晶片上，因此 CPU 可以更快地存取其儲存的資料。它通常用於儲存 CPU 下次可能用到的資料和指令。

運作原理 當 CPU 需要存取資料或指令時，首先會檢查其快取。

如果資料或指令在快取中，CPU 就能快速存取它們。

如果資料或指令不在快取中，處理器會檢查是否在記憶體中，並將資料副本儲存在快取中以供將來使用。

LRU 是什麼？

LRU 是 "Least Recently Used" 的縮寫。

LRU 快取是一種常見的快取替換演算法，其設計目的是在快取容量滿時，自動刪除最近最少使用（最久時間前使用的）的項目。

LRU 快取的思想是將最近使用的項目儲存在快取中，以便程式在需要時可以快速存取它們。

當快取容量達到上限時，最近最少使用的項目將從快取中刪除，以便為新項目騰出空間。這確保了最近使用的項目始終可在快取中取得。

LRU 快取在查詢大量儲存資料時非常有用，它可以有效地將最常使用的項目保留在快取中，以便程式可以快速存取。通常用於網頁瀏覽器、作業系統和資料庫系統中，以提升效能。

介面設計

C++

class LRUCache {

public:
    LRUCache(int capacity);
    int get(int key);
    void put(int key, int value);
};

資料結構設計

LRU 快取通常使用雙向鏈結串列和雜湊表來實現。

雙向鏈結串列用於儲存鍵值對。
雜湊表用於儲存鍵和雙向鏈結串列的迭代器。

雙向鏈結串列的頭部是最近使用的項目，尾部是最久時間前使用的項目。

當存取一個項目時，它將被移動到鏈結串列的頭部。

當快取達到其容量時，鏈結串列的尾部項目將被刪除。

C++ 實作

CPP

// Using STL list and unordered_map
#include <list>
#include <random>
#include <iostream>
#include <unordered_map>

using namespace std;

class LRUCache
{
private:
    int capacity;                                              list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> map; 

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

    LRUCache(int capacity) : capacity(capacity) {}
    int get(const int &key)
    {
        // cout << "get " << key << endl;
        const auto it = map.find(key);
        // not found, return -1
        if (it == map.end())
        {
            MISS++;
            return -1;
        }
        // move the element to the front
        cache.splice(cache.begin(), cache, it->second);
        // return the value
        HIT++;
        return it->second->second;
    }
    void put(const int &key, const int &value)
    {
        const auto it = map.find(key);
        if (it != map.end())
        {
            // founded, update the value
            it->second->second = value;
            // move the element to the front
            cache.splice(cache.begin(), cache, it->second);
            return;
        }
        // not found, insert the new element at the front
        // 1. check the capacity
        if (cache.size() == capacity)
        {
            // remove the last element
            const auto &last = cache.back();
            map.erase(last.first);
            cache.pop_back();
        }
        // 2. insert the new element at the front
        cache.emplace_front(key, value);
        map[key] = cache.begin();
    }

    void clear()
    {
        cache.clear();
        map.clear();
        HIT = 0;
        MISS = 0;
    }

    void print() const
    {
        for (const auto &p : cache)
        {
            cout << p.first << " " << p.second << endl;
        }
    }
};

int main()
{
    const int CAPACITY = 200;
    const int NUM = 1000;

    LRUCache 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;


    // sequential access with pre-fetch
    cout << "Sequential Access with Pre-Fetch" << endl;
    cache.clear();
    int size = 4; // pre-fetch size
    int key = 0;
    for (int i = 0; i < NUM; ++i)
    {
        if (cache.get(key) == -1)
        {
            for(int j = 0; j < size; ++j)
            {
                cache.put(key + j, key + j);
            }
        }
        key++;
        key = key % NUM;
    }

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

    // random access
    cout << "Random Access" << endl;
    cache.clear();
    std::random_device rd;
    std::mt19937 gen(rd());
    std::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 << "\tMISS: " << cache.MISS
            << "\t\tHit Rate: " << (double)cache.HIT / (cache.HIT + cache.MISS) << endl;


    // random access with pre-fetch
    cout << "Random Access with Pre-Fetch" << endl;
    cache.clear();
    size = 4; // pre-fetch size
    key = 0;
    for (int i = 0; i < NUM; ++i)
    {
        int key = dis(gen);
        if (cache.get(key) == -1)
        {
            for(int j = 0; j < size; ++j)
            {
                cache.put(key + j, key + j);
            }
        }
    }
    cout << "HIT: " << cache.HIT << "\tMISS: " << cache.MISS
         << "\t\tHit Rate: " << (double)cache.HIT / (cache.HIT + cache.MISS) << endl;

    return 0;

// Sequential Access
// HIT: 0          MISS: 1000              Hit Rate: 0
// Sequential Access with Pre-Fetch
// HIT: 750        MISS: 250               Hit Rate: 0.75
// Random Access
// HIT: 181        MISS: 819               Hit Rate: 0.181
// Random Access with Pre-Fetch
// HIT: 195        MISS: 805               Hit Rate: 0.195
}

潛在問題

1.預讀失敗

預讀失敗的情況是，預讀的資料從插入到快取中直到被移除，都從未被存取。

這表示預讀是無效的，同時為了儲存這些無用的預讀資料，還會將潛在的熱資料移除。

在上面的例子中，預讀只在資料順序存取時提高命中率。

2.快取污染

快取污染的情況是，快取中的熱資料被不常存取的資料污染。

在上面的例子中，快取區被大量隨機存取的資料污染。

在這種情況下，快取的命中率會大大降低。

解決方案

1.預讀失敗 下面的解決方法可以解決預讀失敗的問題：

使用分開的快取列表來管理預讀資料和最近最少使用的資料。

例如

在 Linux 系統中：分別使用 active list 和 inactive list 來管理快取的資料。
在 MySQL Innodb 系統中：分別使用容量大小不同的 young 區域和 old 區域來管理快取的資料。

上面兩種解決方案的思想是將資料分為熱資料和冷資料，然後分別使用 LRU 演算法來管理。

2.快取污染 下面的解決方法可以解決快取污染的問題：

給 cache node 增加計數器，然後使用計數器來確定熱資料和冷資料。
給 cache node 增加時間戳記，然後使用時間戳記來確定熱資料和冷資料。

例如

在 Linux 系統中：只有當計數器大於某個閾值時（通常是 2），才將資料從 inactive list 移動到 active list。
在 MySQL Innodb 系統中：只有當時間戳記和計數器大於某個閾值時，才將資料從 young list 移動到 old list。

上面兩種解決方案的思想是增加閾值，使得冷資料更難被移動到熱資料列表中。以此使得熱資料更容易被保留在熱資料列表中，從而避免快取污染。

總結

在這篇文章中，我們介紹了 LRU 快取替換演算法，並且用 C++ 實作了它。

在嵌入式系統中，LRU 快取替換演算法是一種常見且常用的快取替換演算法。

同時他也是 LeetCode 上的一道題目，可以在 LeetCode - 146. LRU Cache 中找到。

但是，LRU 快取替換演算法也有一些潛在的問題，我們在文章中介紹了這些潛在的問題和解決方案。

最後，如何選擇快取替換演算法是一個權衡效能和成本的問題。同時，它也取決於真實的應用場景。

沒有萬能的演算法，只有適合的演算法。

參考資料

LeetCode - 146. LRU Cache

Cache replacement policies - Wikipedia

en.wikipedia.org

什麼是 LRU 快取策略