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

// STL list와 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);
        // 찾지 못함, -1 반환
        if (it == map.end())
        {
            MISS++;
            return -1;
        }
        // 요소를 앞쪽으로 이동
        cache.splice(cache.begin(), cache, it->second);
        // 값 반환
        HIT++;
        return it->second->second;
    }
    void put(const int &key, const int &value)
    {
        const auto it = map.find(key);
        if (it != map.end())
        {
            // 찾음, 값 업데이트
            it->second->second = value;
            // 요소를 앞쪽으로 이동
            cache.splice(cache.begin(), cache, it->second);
            return;
        }
        // 찾지 못함, 새 요소를 앞쪽에 삽입
        // 1. 용량 확인
        if (cache.size() == capacity)
        {
            // 마지막 요소 제거
            const auto &last = cache.back();
            map.erase(last.first);
            cache.pop_back();
        }
        // 2. 새 요소를 앞쪽에 삽입
        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);

    // 순차 접근
    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;


    // 선반입을 사용한 순차 접근
    cout << "Sequential Access with Pre-Fetch" << endl;
    cache.clear();
    int size = 4; // 선반입 크기
    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;

    // 무작위 접근
    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;


    // 선반입을 사용한 무작위 접근
    cout << "Random Access with Pre-Fetch" << endl;
    cache.clear();
    size = 4; // 선반입 크기
    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. 캐시 오염 다음 해결 방법으로 캐시 오염 문제를 해결할 수 있습니다:

캐시 노드에 카운터를 추가하고, 카운터를 사용하여 핫 데이터와 콜드 데이터를 결정합니다.
캐시 노드에 타임스탬프를 추가하고, 타임스탬프를 사용하여 핫 데이터와 콜드 데이터를 결정합니다.

예시

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 캐시 전략이란?