pkglog
EN

C++ 캐시 교체 알고리즘: FIFO·LRU·LFU·Clock·MRU·OPT 구현과 비교

작성 · · 35분 읽기 · 수정 중급 개념

이 글의 핵심

캐시 용량을 늘렸는데 히트율이 오히려 떨어지는 FIFO의 Bélády 변칙, 한때 인기 있던 항목이 오래 남는 LFU의 문제, 순차 스캔 한 번에 LRU 캐시가 비워지는 현상처럼 정책마다 약점이 다릅니다. 멀티스레드 경합까지 고려해 워크로드에 맞는 교체 정책을 고르는 기준을 제공합니다.

들어가며

LRU(Least Recently Used)는 대표적인 캐시 교체(cache replacement) 정책이지만, 같은 문제를 푸는 다른 규칙들이 많습니다. 이 글에서는 LRU와 목적이 비슷한 정책들을 나란히 놓으며, 직관·장단점·구현 난이도·쓰임을 정리합니다.

모든 교체 정책은 결국 “앞으로 다시 쓰일 가능성이 가장 낮은 항목”을 과거 기록으로 추측하는 방법입니다. LRU는 “최근에 안 쓴 것은 앞으로도 안 쓴다”(시간 지역성)에, LFU는 “많이 쓴 것은 앞으로도 많이 쓴다”(인기도)에 걸고, FIFO와 Random은 추측을 거의 하지 않는 대신 비용이 가장 쌉니다. 그래서 어떤 정책이 좋은지는 알고리즘 자체보다 접근 패턴이 그 가정과 맞는가에 달려 있고, 같은 정책이 한 서비스에서는 최선이고 다른 서비스에서는 최악이 되는 일이 흔합니다. 아래 정책들을 볼 때 “이 정책은 무엇을 가정하는가”를 함께 떠올리면 약점이 자연스럽게 보입니다.

캐시 교체 문제

용량이 정해진 캐시에 새 항목을 넣어야 하는데 자리가 없을 때, 기존 항목 하나를 골라 제거(eviction) 해야 합니다. “무엇을 지울까?”를 정하는 것이 곧 알고리즘입니다.

flowchart LR
  A[캐시 가득] --> B{교체 정책}
  B --> C[FIFO]
  B --> D[LRU]
  B --> E[LFU]
  B --> F[Clock 등]

주요 정책

FIFO (First In First Out)

가장 먼저 들어온 항목을 제거합니다. 줄 서기와 같습니다.

항목내용
직관구현이 단순함
복잡도큐 + 맵이면 삽입·삭제 평균 O(1)
단점자주 쓰는데도 “옛날에 들어왔다”는 이유만으로 지워질 수 있음
참고Bélády 변칙(anomaly) - 프레임 수가 늘어도 페이지 폴트가 늘 수 있음

LRU (Least Recently Used)

가장 오래 “사용되지 않은” 항목을 제거합니다.

항목내용
직관시간 지역성에 잘 맞음
복잡도list + unordered_map으로 O(1)
장점범용적으로 좋은 성능
단점한 번만 스캔하고 끝인 패턴에서는 불리

LFU (Least Frequently Used)

참조 횟수가 가장 적은 항목을 제거합니다.

항목내용
직관인기 있는 키는 오래 유지
복잡도이중 구조 필요 (LeetCode 460 수준)
장점정말 인기 항목 보호
단점”stale popular” 문제 (예전에 많이 쓰였지만 지금은 안 쓰는 항목)

MRU (Most Recently Used)

가장 최근에 사용한 항목을 제거합니다. LRU와 반대입니다.

항목내용
직관순차 스캔에 유리
복잡도LRU와 유사
쓰임특수 워크로드 (순차 스캔)

Random

무작위로 하나 지웁니다.

항목내용
직관구현 단순
복잡도O(1)
장점락 경합 최소화
단점품질 기대치 낮음

Clock (Second Chance)

OS 페이지 교체에서 흔한 LRU 근사입니다.

항목내용
직관참조 비트 기반
복잡도O(1) ~ O(n)
장점메타데이터 비용 적음
쓰임OS 페이지, 임베디드

OPT / MIN (이론적 최적)

앞으로 가장 오랫동안 쓰이지 않을 페이지를 제거합니다.

항목내용
직관미래 참조 필요
복잡도이론만
쓰임성능 상한 분석

MRU가 이상해 보이는 이유는 “방금 쓴 것을 지운다”는 규칙이 직관과 반대이기 때문인데, 캐시보다 큰 데이터를 반복해서 순회하는 패턴에서는 이것이 정답에 가깝습니다. 1~101번 블록을 100칸 캐시로 계속 반복해서 읽으면, LRU는 매번 곧 다시 읽을 가장 오래된 블록을 지워 히트율이 0이 되지만, MRU는 앞쪽 블록을 붙잡아 두어 대부분 히트합니다. 조인 연산의 내부 루프처럼 순회 패턴을 미리 아는 데이터베이스 엔진이 테이블 스캔용 버퍼에 이런 정책을 쓰는 이유입니다. Random도 생각보다 나쁘지 않은데, 최악의 입력 패턴이 존재하지 않고 메타데이터 갱신이 없어 락 없이 구현하기 쉽다는 장점이 있습니다. CPU 캐시 일부가 의사 난수 교체를 쓰는 것도 같은 이유입니다.

실전 구현

FIFO 캐시

#include <cstddef>
#include <optional>
#include <queue>
#include <stdexcept>
#include <unordered_map>
#include <utility>
#include <iostream>
template <typename K, typename V, typename Hash = std::hash<K>>
class FIFOCache {
public:
    explicit FIFOCache(std::size_t capacity) : capacity_(capacity) {
        if (capacity_ == 0) throw std::invalid_argument("capacity > 0");
    }
    
    std::optional<V> get(const K& key) {
        auto it = map_.find(key);
        if (it == map_.end()) return std::nullopt;
        return it->second;
    }
    
    void put(const K& key, V value) {
        auto it = map_.find(key);
        if (it != map_.end()) {
            it->second = std::move(value);
            return;
        }
        if (map_.size() >= capacity_) {
            evict_fifo();
        }
        order_.push(key);
        map_.emplace(key, std::move(value));
    }
private:
    void evict_fifo() {
        while (!order_.empty()) {
            K victim = order_.front();
            order_.pop();
            if (map_.erase(victim)) return;
        }
    }
    
    std::size_t capacity_;
    std::queue<K> order_;
    std::unordered_map<K, V, Hash> map_;
};
int main() {
    FIFOCache<int, std::string> cache(3);
    
    cache.put(1, "one");
    cache.put(2, "two");
    cache.put(3, "three");
    
    std::cout << cache.get(1).value() << std::endl;  // one
    
    cache.put(4, "four");  // 1 제거 (FIFO)
    
    std::cout << (cache.get(1).has_value() ? "있음" : "없음") << std::endl;  // 없음
    
    return 0;
}

get(1)으로 방금 읽었는데도 put(4)에서 1이 지워지는 것이 FIFO의 본질입니다. 조회는 순서에 아무 영향을 주지 않으므로 get이 맵 조회 한 번으로 끝나고, 읽기 경로에서 공유 자료구조를 수정하지 않는다는 점이 LRU와의 가장 큰 차이입니다. 읽기가 쓰기보다 압도적으로 많은 캐시라면 이 특성 덕분에 읽기 잠금만으로 동시 조회가 가능해집니다. evict_fifo가 루프를 도는 이유는 큐에 이미 맵에서 지워진 키가 남아 있을 수 있기 때문인데, 이 구현에는 명시적 삭제 API가 없어서 실제로는 첫 번째 시도에서 끝나지만 erase를 추가할 때를 대비한 방어 코드입니다. 최근에는 FIFO에 짧은 “수습 큐”를 앞에 두어 한 번만 쓰이고 버려질 항목을 빨리 걸러 내는 S3-FIFO 같은 변형이 LRU에 견줄 만한 히트율을 보여 다시 주목받고 있습니다.

LRU 캐시

LRU는 std::unordered_map<K, list::iterator>와 std::list<std::pair<K, V>>를 함께 두는 구조가 정석입니다. 해시 맵으로 키에서 리스트 노드를 O(1)에 찾고, list::splice로 그 노드를 맨 앞으로 옮기며, 용량을 넘으면 list.back()을 버립니다. splice는 노드를 복사하지 않고 연결만 바꾸므로 맵에 저장해 둔 반복자가 무효화되지 않는다는 점이 이 구조를 성립시킵니다.

이 절에서 FIFO·Clock과 나란히 놓고 볼 점은 접근할 때마다 쓰기가 일어난다는 것입니다. FIFO는 hit 때 아무것도 바꾸지 않고, Clock은 참조 비트 하나만 켭니다. LRU는 hit 때마다 리스트 순서를 바꾸므로 읽기가 대부분인 캐시에서도 락을 잡거나 노드를 옮겨야 하고, OS 페이지 교체처럼 접근이 매우 잦은 곳에서 아래 Clock 같은 근사를 쓰는 이유가 이것입니다. 전체 템플릿 구현, put 단계별 추적, 용량 0이나 잘못된 반복자 저장 같은 경계 조건은 C++로 O(1) LRU 캐시 만들기에서 따로 다룹니다.

Clock (Second Chance) 알고리즘

#include <vector>
#include <unordered_map>
#include <optional>
#include <iostream>
template <typename K, typename V>
class ClockCache {
private:
    struct Entry {
        K key;
        V value;
        bool referenced;
    };
    
    size_t capacity_;
    size_t hand_;
    std::vector<Entry> entries_;
    std::unordered_map<K, size_t> map_;
    
public:
    explicit ClockCache(size_t capacity) 
        : capacity_(capacity), hand_(0) {
        entries_.reserve(capacity);
    }
    
    std::optional<V> get(const K& key) {
        auto it = map_.find(key);
        if (it == map_.end()) return std::nullopt;
        
        entries_[it->second].referenced = true;
        return entries_[it->second].value;
    }
    
    void put(const K& key, V value) {
        auto it = map_.find(key);
        if (it != map_.end()) {
            entries_[it->second].value = std::move(value);
            entries_[it->second].referenced = true;
            return;
        }
        
        if (entries_.size() < capacity_) {
            size_t index = entries_.size();
            entries_.push_back({key, std::move(value), true});
            map_[key] = index;
        } else {
            evict_clock(key, std::move(value));
        }
    }
private:
    void evict_clock(const K& key, V value) {
        while (true) {
            if (!entries_[hand_].referenced) {
                K victim = entries_[hand_].key;
                map_.erase(victim);
                
                entries_[hand_] = {key, std::move(value), true};
                map_[key] = hand_;
                hand_ = (hand_ + 1) % capacity_;
                return;
            }
            
            entries_[hand_].referenced = false;
            hand_ = (hand_ + 1) % capacity_;
        }
    }
};
int main() {
    ClockCache<int, std::string> cache(3);
    
    cache.put(1, "one");
    cache.put(2, "two");
    cache.put(3, "three");
    
    cache.get(1);  // referenced = true
    
    cache.put(4, "four");  // 이 구현에서는 1을 제거 (아래 설명 참고)
    
    return 0;
}

주석과 실제 동작이 다를 수 있다는 점이 Clock을 처음 구현할 때 흔히 헷갈리는 부분입니다. 이 구현은 새 항목을 넣을 때 referenced = true로 시작하므로, 캐시가 막 찬 시점에는 모든 항목의 참조 비트가 1입니다. put(4)가 오면 시계 바늘이 1, 2, 3을 돌며 비트를 전부 0으로 내리고 한 바퀴를 돌아 다시 1에 도착해, 결국 방금 get한 1이 지워집니다. 모든 항목이 참조된 상태에서는 Clock이 FIFO로 퇴화한다는 뜻입니다. 새 항목을 referenced = false로 넣는 구현도 흔하며, 그 경우에는 한 번도 다시 읽히지 않은 2가 먼저 제거됩니다. 어느 쪽이든 LRU의 정확한 순서를 포기하는 대신 조회 시 비트 하나만 세우면 된다는 것이 Clock의 장점이고, 그래서 MMU가 페이지 접근 시 하드웨어로 참조 비트를 세워 주는 OS 페이지 교체에 잘 맞습니다. 바늘이 한 바퀴를 모두 돌아야 하는 최악의 경우는 O(n)이지만, 비트를 내리면서 지나가므로 분할 상환하면 교체당 O(1)입니다.

성능 비교

알고리즘 비교

정책무엇을 지우나시간 복잡도공간 복잡도구현 난이도
FIFO가장 먼저 들어온 것O(1)O(n)낮음
LRU가장 오래 안 쓴 것O(1)O(n)중간
LFU가장 적게 쓴 것O(1) ~ O(log n)O(n)높음
MRU가장 최근 쓴 것O(1)O(n)중간
Random아무거나O(1)O(n)매우 낮음
Clock참조 비트 기반O(1) ~ O(n)O(n)중간
OPT미래 안 쓰는 것이론만-불가능

히트율은 어떻게 비교해야 하나

정책별 히트율을 숫자 하나로 비교하는 표는 의미가 거의 없습니다. 같은 LRU도 접근 패턴이 시간 지역성이 강한 웹 세션 캐시라면 90%를 넘고, 균등 분포 무작위 접근이라면 어떤 정책이든 대략 “캐시 크기 ÷ 전체 키 수”에 수렴하며, 순차 스캔이 섞이면 0% 근처까지 떨어집니다. 실무에서 정책을 고르는 정석은 실제 접근 로그를 재생하는 시뮬레이션입니다. 운영 환경에서 키 접근 순서를 일정 기간 기록한 뒤, 위 구현들처럼 정책별 캐시에 그대로 흘려 보내며 캐시 크기를 바꿔 가며 히트율 곡선을 그립니다. 같은 로그로 미래를 아는 OPT도 계산할 수 있으므로, “현재 정책이 이론적 최적과 얼마나 떨어져 있는가”를 보면 정책을 바꿀 가치가 있는지 판단할 수 있습니다. 대개는 정책을 바꾸는 것보다 캐시 크기를 조금 늘리는 쪽이 효과가 큰지부터 이 곡선에서 확인하게 됩니다.

실무 사례

사례 1: Redis 캐시 정책

Redis eviction policies:

# redis.conf
maxmemory 100mb
maxmemory-policy allkeys-lru
# 정책 옵션:
# - noeviction: 제거 안함 (에러 반환)
# - allkeys-lru: 모든 키 중 LRU
# - volatile-lru: TTL 있는 키 중 LRU
# - allkeys-lfu: 모든 키 중 LFU
# - volatile-lfu: TTL 있는 키 중 LFU
# - allkeys-random: 무작위
# - volatile-random: TTL 있는 키 중 무작위
# - volatile-ttl: TTL 짧은 키 먼저

Redis의 allkeys-lru는 이 글의 LRU 구현처럼 모든 키를 연결 리스트로 관리하지 않습니다. 키마다 마지막 접근 시각(24비트)만 저장해 두고, 메모리가 부족해지면 maxmemory-samples(기본 5)개의 키를 무작위로 뽑아 그중 가장 오래된 키를 지우는 근사 LRU입니다. 키마다 포인터 두 개를 더 두는 메모리 비용과 접근마다 리스트를 수정하는 비용을 피하려는 선택이고, 샘플 수를 10으로 올리면 정확한 LRU에 더 가까워지는 대신 CPU를 더 씁니다. allkeys-lfu도 접근 횟수를 로그 스케일 8비트 카운터로 세고 시간이 지나면 감쇠시키는 근사 방식이라, 아래 트러블슈팅의 “stale popular” 문제가 어느 정도 완화되어 있습니다. 흔한 실수는 기본값인 noeviction을 그대로 두는 것으로, 이 경우 메모리가 차면 키를 지우는 대신 쓰기 명령이 OOM command not allowed when used memory > 'maxmemory' 에러로 실패합니다.

C++ 클라이언트 예제:

#include <iostream>
#include <string>
// Redis 클라이언트 (hiredis 등)
void configureRedis() {
    // redis.conf 설정
    std::cout << "maxmemory 100mb" << std::endl;
    std::cout << "maxmemory-policy allkeys-lru" << std::endl;
}
int main() {
    configureRedis();
    
    // 캐시 사용
    // SET key1 value1
    // GET key1
    
    return 0;
}

사례 2: OS 페이지 교체

OS 페이지 교체: Clock 알고리즘은 교과서적인 페이지 교체 방식이고, 실제 커널들은 이를 변형해 씁니다. 리눅스는 오랫동안 active/inactive 두 개의 리스트로 나눈 LRU 근사를 써 왔고(한 번 접근된 페이지는 inactive에 들어가 두 번째 접근이 있어야 active로 승격), 6.1부터는 여러 세대로 나누는 MGLRU를 선택적으로 쓸 수 있습니다. 두 리스트 구조는 아래 “순차 스캔 문제”를 막기 위한 장치이기도 합니다. 아래 시뮬레이터는 그 출발점인 기본 Clock을 페이지 번호로 보여 줍니다.

#include <vector>
#include <iostream>
struct Page {
    int page_number;
    bool referenced;
};
class PageReplacementSimulator {
private:
    size_t capacity_;
    size_t hand_;
    std::vector<Page> pages_;
    
public:
    explicit PageReplacementSimulator(size_t capacity) 
        : capacity_(capacity), hand_(0) {}
    
    void access(int page_number) {
        for (auto& page : pages_) {
            if (page.page_number == page_number) {
                page.referenced = true;
                std::cout << "Page " << page_number << " hit" << std::endl;
                return;
            }
        }
        
        std::cout << "Page " << page_number << " miss" << std::endl;
        
        if (pages_.size() < capacity_) {
            pages_.push_back({page_number, true});
        } else {
            evict_clock(page_number);
        }
    }
private:
    void evict_clock(int page_number) {
        while (true) {
            if (!pages_[hand_].referenced) {
                std::cout << "Evict page " << pages_[hand_].page_number << std::endl;
                pages_[hand_] = {page_number, true};
                hand_ = (hand_ + 1) % capacity_;
                return;
            }
            
            pages_[hand_].referenced = false;
            hand_ = (hand_ + 1) % capacity_;
        }
    }
};
int main() {
    PageReplacementSimulator sim(3);
    
    sim.access(1);
    sim.access(2);
    sim.access(3);
    sim.access(1);  // hit
    sim.access(4);  // miss, evict 2 or 3
    
    return 0;
}

사례 3: 인기 콘텐츠 보호 - LFU

#include <unordered_map>
#include <map>
#include <list>
#include <optional>
#include <iostream>
template <typename K, typename V>
class LFUCache {
private:
    struct Node {
        K key;
        V value;
        int freq;
    };
    
    size_t capacity_;
    int min_freq_;
    std::unordered_map<K, typename std::list<Node>::iterator> key_map_;
    std::map<int, std::list<Node>> freq_map_;
    
public:
    explicit LFUCache(size_t capacity) : capacity_(capacity), min_freq_(0) {}
    
    std::optional<V> get(const K& key) {
        auto it = key_map_.find(key);
        if (it == key_map_.end()) return std::nullopt;
        
        auto node_it = it->second;
        int freq = node_it->freq;
        
        Node node = *node_it;
        freq_map_[freq].erase(node_it);
        
        if (freq_map_[freq].empty()) {
            freq_map_.erase(freq);
            if (min_freq_ == freq) min_freq_++;
        }
        
        node.freq++;
        freq_map_[node.freq].push_front(node);
        key_map_[key] = freq_map_[node.freq].begin();
        
        return node.value;
    }
    
    void put(const K& key, V value) {
        if (capacity_ == 0) return;
        
        auto it = key_map_.find(key);
        if (it != key_map_.end()) {
            auto node_it = it->second;
            node_it->value = std::move(value);
            get(key);
            return;
        }
        
        if (key_map_.size() >= capacity_) {
            auto& list = freq_map_[min_freq_];
            K victim = list.back().key;
            list.pop_back();
            key_map_.erase(victim);
        }
        
        min_freq_ = 1;
        freq_map_[1].push_front({key, std::move(value), 1});
        key_map_[key] = freq_map_[1].begin();
    }
};
int main() {
    LFUCache<int, std::string> cache(3);
    
    cache.put(1, "one");
    cache.put(2, "two");
    cache.put(3, "three");
    
    cache.get(1);
    cache.get(1);  // freq = 2
    
    cache.put(4, "four");  // freq=1인 2와 3 중 더 오래된 2 제거
    
    return 0;
}

이 LFU는 빈도별로 리스트를 두고(freq_map_), 같은 빈도 안에서는 앞쪽에 최근 항목을 넣어 빈도가 같으면 LRU로 동점을 가르는 구조입니다. min_freq_를 따로 유지하는 이유는 제거할 때 가장 낮은 빈도의 리스트를 바로 찾기 위해서입니다. 새 항목은 빈도 1로 들어오므로 put에서 min_freq_ = 1로 되돌리고, get에서 최소 빈도 리스트가 비었다면 그 항목이 한 단계 올라갔을 뿐이므로 min_freq_++로 충분합니다. 이 두 규칙 덕분에 LeetCode 460에서 요구하는 O(1) LFU가 되는데, 여기서는 std::map을 써서 빈도 조회가 O(log F)이고, unordered_map으로 바꾸면 평균 O(1)이 됩니다.

LFU를 실제 캐시에 쓸 때의 가장 큰 문제는 새 항목이 불리하다는 점입니다. 막 들어온 항목은 빈도 1이라 다음 교체 대상 1순위가 되므로, 앞으로 인기 있을 콘텐츠가 빈도를 쌓기 전에 계속 쫓겨날 수 있습니다. Java 캐시 라이브러리 Caffeine이 쓰는 W-TinyLFU는 새 항목을 작은 LRU 창에 먼저 넣고, 빈도 추정치(Count-Min Sketch)로 기존 항목과 비교해 이길 때만 본 캐시에 들이는 방식으로 이 문제와 빈도 카운터의 메모리 비용을 함께 해결합니다.

트러블슈팅

문제 1: FIFO의 Bélády 변칙

증상: 캐시 크기를 늘렸는데 히트율이 떨어짐

// 접근 패턴: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 (12회)
// FIFO 캐시 크기 3: 미스 9회, 히트 3회 (25%)
// FIFO 캐시 크기 4: 미스 10회, 히트 2회 (약 17%)  ← 크기를 늘렸는데 더 나빠짐
// ✅ LRU 사용
// LRU 캐시 크기 3: 미스 10회, 히트 2회 (약 17%)
// LRU 캐시 크기 4: 미스 8회, 히트 4회 (약 33%)   ← 크기를 늘리면 항상 같거나 좋아짐

이 패턴에서 크기 3일 때만 보면 LRU가 FIFO보다 오히려 나쁩니다. 중요한 것은 크기를 늘렸을 때의 방향입니다. LRU와 OPT는 “크기 k 캐시의 내용이 항상 크기 k+1 캐시 내용의 부분집합”이 되는 스택 알고리즘이라 크기를 늘려서 히트율이 떨어지는 일이 수학적으로 불가능하지만, FIFO는 이 성질이 없어서 위처럼 역전이 일어납니다. 실무에서 이 변칙을 직접 만나는 일은 드물지만, “메모리를 늘렸는데 왜 캐시 효율이 떨어졌지?”라는 질문에 정책 자체가 원인일 수 있다는 것을 알려 주는 예입니다.

증상: 예전에 많이 쓰였지만 지금은 안 쓰는 항목이 남음

// 접근 패턴:
// 1, 1, 1, 1, 1 (freq = 5)
// 2, 3, 4, 5, 6 (각 freq = 1)
// LFU: 1이 계속 남음 (지금은 안 쓰는데도)
// ✅ LFU with decay
// 시간마다 빈도 감쇠
freq = freq * 0.9

문제 3: LRU의 순차 스캔 문제

증상: 순차 스캔 시 캐시 전체가 교체됨

// 접근 패턴: 1, 2, 3, ..., 1000 (순차)
// 캐시 크기: 100
// LRU: 히트율 0% (모든 페이지가 한 번씩만)
// ✅ MRU 또는 LRU-K
// MRU: 최근 것을 지움
// LRU-K: K번 참조된 것만 보호

이 예제처럼 모든 키가 한 번씩만 나오면 어떤 정책도 히트할 수 없으니, 진짜 문제는 스캔이 기존의 자주 쓰던 항목을 밀어낸다는 데 있습니다. 백업 작업이나 리포트 배치가 새벽에 테이블 전체를 한 번 읽고 나면 아침 트래픽의 캐시 히트율이 한동안 바닥을 치는 식으로 나타납니다. 이를 막는 방법은 크게 두 가지입니다. 하나는 한 번만 접근된 항목을 별도 영역에 두고 두 번째 접근이 있어야 본 영역으로 올리는 것(LRU-2, 2Q, 리눅스의 active/inactive 리스트, MySQL InnoDB의 midpoint 삽입이 모두 이 계열)이고, 다른 하나는 스캔 경로가 아예 캐시를 거치지 않도록 하는 것(posix_fadvise(POSIX_FADV_NOREUSE), DB의 스캔 전용 버퍼 링)입니다.

문제 4: 멀티스레드 경합

증상: 캐시 락 경합으로 성능 저하

// ❌ 단일 락
std::mutex cache_mutex;
LRUCache<int, std::string> cache(1000);
void access(int key) {
    std::lock_guard<std::mutex> lock(cache_mutex);  // 경합
    cache.get(key);
}
// ✅ 샤딩
std::vector<LRUCache<int, std::string>> shards(16, LRUCache<int, std::string>(1000 / 16));
std::vector<std::mutex> shard_mutexes(16);
void access(int key) {
    size_t shard_id = std::hash<int>{}(key) % 16;
    std::lock_guard<std::mutex> lock(shard_mutexes[shard_id]);
    shards[shard_id].get(key);
}

LRU에서 락 경합이 특히 심한 이유는 get이 리스트를 수정하는 연산이라 읽기만 하는 요청도 배타 락이 필요하기 때문입니다. 샤딩은 이 락을 16개로 쪼개 경합을 줄이는 가장 단순한 방법이지만 대가가 있습니다. 전체 용량을 샤드 수로 나누므로 인기 키가 한 샤드에 몰리면 그 샤드만 가득 차서 자주 쓰는 항목을 밀어내는 동안 다른 샤드는 비어 있을 수 있고, 캐시 전체로 보면 정확한 LRU가 아니게 됩니다. 또 std::hash<int>는 대부분 구현에서 값을 그대로 돌려주므로 % 16이 키의 하위 4비트만 보게 되어, 키가 16의 배수로 증가하는 패턴이라면 모든 요청이 한 샤드로 갑니다. 샤드 번호를 정할 때는 해시값을 한 번 더 섞는 것이 안전합니다. 경합을 더 줄이고 싶다면 Caffeine처럼 조회 기록을 버퍼에 모아 두었다가 나중에 한꺼번에 리스트에 반영하거나, 조회 시 비트만 세우는 Clock 계열로 바꾸는 방법이 있습니다.

마무리

캐시 교체 알고리즘은 워크로드에 따라 최적의 선택이 다릅니다.

핵심 요약

  1. FIFO
    • 가장 먼저 들어온 것 제거
    • 구현 단순, 히트율 낮음
  2. LRU
    • 가장 오래 안 쓴 것 제거
    • 범용적으로 우수
  3. LFU
    • 가장 적게 쓴 것 제거
    • 인기 항목 보호, 구현 복잡
  4. Clock
    • 참조 비트 기반 LRU 근사
    • OS 페이지 교체에 흔함
  5. Random
    • 무작위 제거
    • 락 경합 최소화

선택 가이드

워크로드추천 정책이유
범용 앱 캐시LRU시간 지역성
순차 스캔MRULRU 불리
인기 콘텐츠 보호LFU빈도 기반
단순 버퍼FIFO구현 단순
락 경합 최소화Random오버헤드 적음
OS 페이지Clock하드웨어 지원

코드 예제 치트시트

// FIFO
std::queue<K> order;
std::unordered_map<K, V> map;
// LRU
std::list<std::pair<K, V>> list;
std::unordered_map<K, iterator> map;
// Clock
std::vector<Entry> entries;
size_t hand;
// Random
std::vector<K> keys;
std::unordered_map<K, V> map;
int victim = rand() % keys.size();

다음 단계

참고 자료

한 줄 정리: 캐시 교체 알고리즘은 워크로드에 따라 FIFO·LRU·LFU·Clock 등을 선택하며, 범용적으로는 LRU가 시간 지역성에 강해 가장 많이 쓰입니다.

자주 묻는 질문 (FAQ)

Q. 대용량 순차 스캔이 한 번 지나가면 LRU 캐시의 히트율이 급격히 떨어지는 이유는 무엇인가요?

A. LRU는 가장 최근에 쓴 항목을 남기는 정책이라, 한 번만 읽고 다시 쓰지 않을 데이터가 캐시 크기보다 많이 연속으로 들어오면 자주 쓰던 항목까지 모두 밀어냅니다. 스캔이 끝난 뒤에는 캐시에 다시 쓰지 않을 데이터만 남아 있어 히트율이 크게 떨어집니다. 이런 접근 패턴이 흔하다면 여러 번 참조된 항목만 보호하는 LRU-K 같은 변형이나, 스캔 전용 경로는 캐시를 거치지 않게 하는 설계를 검토해야 합니다.

같이 보면 좋은 글