LRUキャッシュアルゴリズムとは？

キャッシュとは？

キャッシュとは、頻繁にアクセスされるデータや命令を格納する場所であり、高コストな操作を減らすことでアクセス速度を向上させます。プロセッサはデータや命令に高速にアクセスできるようになり、システム全体のパフォーマンスが大幅に向上します。

CPUキャッシュ CPUキャッシュは、小型で高速なメモリであり、通常CPUチップに統合されています。そのため、CPUは格納されたデータに高速にアクセスでき、次に使用する可能性のあるデータや命令を保存するために使われます。

動作原理 CPUがデータや命令にアクセスする必要がある場合、まずキャッシュを確認します。

データや命令がキャッシュにあれば、CPUはそれらに高速にアクセスします。

データや命令がキャッシュにない場合、プロセッサはメインメモリにあるかどうかを確認し、データのコピーを将来の使用に備えてキャッシュに保存します。

LRUとは？

LRUは「Least Recently Used」の略です。

LRUキャッシュは一般的なキャッシュ置換アルゴリズムであり、キャッシュ容量がいっぱいになったときに、最も長い間使用されていない（最も古い）項目を自動的に削除するように設計されています。

LRUキャッシュの考え方は、最近使用された項目をキャッシュに保持し、プログラムが必要なときに高速にアクセスできるようにすることです。

キャッシュ容量に達すると、最も長い間使用されていない項目がキャッシュから削除され、新しい項目のためのスペースが確保されます。これにより、最近使用された項目が常にキャッシュで利用可能になります。

LRUキャッシュは、大量の保存データを検索する際に非常に有用であり、最も頻繁に使用される項目をキャッシュに効果的に保持し、プログラムが高速にアクセスできるようにします。Webブラウザ、オペレーティングシステム、データベースシステムでパフォーマンス向上のために一般的に使用されています。

インターフェース設計

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領域をそれぞれ使用してキャッシュデータを管理します。

上記2つの解決策の考え方は、データをホットデータとコールドデータに分類し、それぞれLRUアルゴリズムを使用して管理することです。

2. キャッシュ汚染 以下の解決策でキャッシュ汚染の問題を解決できます。

キャッシュノードにカウンターを追加し、カウンターを使用してホットデータとコールドデータを判別します。
キャッシュノードにタイムスタンプを追加し、タイムスタンプを使用してホットデータとコールドデータを判別します。

例

Linuxシステムでは: カウンターが特定のしきい値（通常は2）を超えた場合のみ、データをinactive listからactive listに移動します。
MySQL Innodbシステムでは: タイムスタンプとカウンターが特定のしきい値を超えた場合のみ、データをyoung listからold listに移動します。

上記2つの解決策の考え方は、しきい値を追加することで、コールドデータがホットデータリストに移動されにくくすることです。これにより、ホットデータがホットデータリストに保持されやすくなり、キャッシュ汚染を回避できます。

まとめ

この記事では、LRUキャッシュ置換アルゴリズムを紹介し、C++で実装しました。

組み込みシステムにおいて、LRUキャッシュ置換アルゴリズムは一般的でよく使われるキャッシュ置換アルゴリズムです。

また、LeetCodeの問題としても出題されており、LeetCode - 146. LRU Cache で確認できます。

しかし、LRUキャッシュ置換アルゴリズムにはいくつかの潜在的な問題もあり、この記事ではそれらの潜在的な問題と解決策を紹介しました。

最後に、キャッシュ置換アルゴリズムの選択は、パフォーマンスとコストのバランスを考慮する問題です。また、実際のアプリケーションシナリオにも依存します。

万能なアルゴリズムはなく、適切なアルゴリズムがあるだけです。

参考資料

LeetCode - 146. LRU Cache

Cache replacement policies - Wikipedia

en.wikipedia.org

LRUキャッシュ戦略とは