실무 캐시는 LRU만 쓰면 되나요?

워크로드에 따라 FIFO·LFU·Random이 더 나을 수 있습니다. 접근 지역성이 강하면 LRU가 유리하고, 스캔 패턴이면 LRU가 불리할 수 있습니다.

LFU가 LRU보다 항상 정확한가요?

아닙니다. 빈도만 보면 최근에 중요해진 키를 못 밀어낼 수 있고 구현·메모리 비용도 큽니다. 용도에 맞게 선택하세요.

Clock(Second Chance) 알고리즘은 언제 쓰나요?

LRU 근사를 하드웨어·OS 페이지처럼 저비용으로 구현할 때 흔합니다. 정확한 LRU 순서가 꼭 필요하지 않을 때 후보입니다.

OPT는 왜 실제 시스템에 못 쓰나요?

미래 참조를 알아야 해서 이론적 상한입니다. 비교·연구용으로 쓰고 실제 정책과의 갭을 분석하는 데 의미가 있습니다.

C++ 캐시 교체 알고리즘 총정리 | FIFO·LRU·LFU·Clock·MRU·OPT 완벽 비교

2026년 3월 27일 · 35분 읽기 · 수정 2026년 3월 31일 중급 개념

이 글의 핵심

고정 크기 캐시가 가득 찰 때 무엇을 지울지 정하는 규칙이 캐시 교체 알고리즘입니다. LRU만 있는 것이 아니라 FIFO·LFU·MRU·Random·Clock·OPT 등 여러 정책이 있고, 각각 구현 난이도와 적합한 워크로드가 다릅니다.

들어가며

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

이 글을 읽으면

FIFO, LRU, LFU, MRU, Random, Clock, OPT의 차이를 이해합니다
각 정책의 시간 복잡도와 구현 난이도를 비교합니다
워크로드에 맞는 정책을 선택하는 기준을 익힙니다
C++ 구현 예제와 실무 사례를 확인합니다

캐시 교체 문제

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

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

주요 정책

1. FIFO (First In First Out)

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

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

2. LRU (Least Recently Used)

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

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

3. LFU (Least Frequently Used)

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

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

4. MRU (Most Recently Used)

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

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

5. Random

무작위로 하나 지웁니다.

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

6. Clock (Second Chance)

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

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

7. OPT / MIN (이론적 최적)

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

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

실전 구현

1) 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;
}

2) LRU 캐시

#include <list>
#include <unordered_map>
#include <optional>
#include <iostream>

template <typename K, typename V>
class LRUCache {
public:
    explicit LRUCache(size_t capacity) : capacity_(capacity) {}
    
    std::optional<V> get(const K& key) {
        auto it = map_.find(key);
        if (it == map_.end()) return std::nullopt;
        
        // 맨 앞으로 이동
        list_.splice(list_.begin(), list_, it->second);
        return it->second->second;
    }
    
    void put(const K& key, V value) {
        auto it = map_.find(key);
        if (it != map_.end()) {
            it->second->second = std::move(value);
            list_.splice(list_.begin(), list_, it->second);
            return;
        }
        
        if (map_.size() >= capacity_) {
            auto victim = list_.back().first;
            list_.pop_back();
            map_.erase(victim);
        }
        
        list_.emplace_front(key, std::move(value));
        map_[key] = list_.begin();
    }

private:
    size_t capacity_;
    std::list<std::pair<K, V>> list_;
    std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> map_;
};

int main() {
    LRUCache<int, std::string> cache(3);
    
    cache.put(1, "one");
    cache.put(2, "two");
    cache.put(3, "three");
    
    cache.get(1);  // 1 사용
    
    cache.put(4, "four");  // 2 제거 (LRU)
    
    std::cout << (cache.get(2).has_value() ? "있음" : "없음") << std::endl;  // 없음
    
    return 0;
}

3) 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");  // 2 또는 3 제거 (referenced = false)
    
    return 0;
}

성능 비교

알고리즘 비교

정책	무엇을 지우나	시간 복잡도	공간 복잡도	구현 난이도
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	미래 안 쓰는 것	이론만	-	불가능

히트율 비교

테스트: 10,000번 접근, 캐시 크기 100

정책	히트율	특징
OPT	95%	이론적 최적
LRU	85%	시간 지역성 강함
LFU	80%	빈도 기반
FIFO	70%	단순
Random	60%	무작위

결론: LRU가 범용적으로 우수

실무 사례

사례 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 짧은 키 먼저

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 페이지 교체

Linux 페이지 교체: 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: CDN 캐시 - LFU 변형

#include <unordered_map>
#include <map>
#include <list>
#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");  // 2 또는 3 제거 (freq = 1)
    
    return 0;
}

트러블슈팅

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

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

// 접근 패턴: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

// 캐시 크기 3: 히트율 25%
// 캐시 크기 4: 히트율 10%

// ✅ LRU 사용
// 캐시 크기 3: 히트율 50%
// 캐시 크기 4: 히트율 60%

문제 2: LFU의 “stale popular” 문제

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

// 접근 패턴:
// 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번 참조된 것만 보호

문제 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);
}

마무리

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

핵심 요약

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

선택 가이드

워크로드	추천 정책	이유
범용 앱 캐시	LRU	시간 지역성
순차 스캔	MRU	LRU 불리
인기 콘텐츠 보호	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();

다음 단계

LRU 구현: C++ LRU 캐시 알고리즘 완벽 가이드
캐싱 전략: C++ 캐싱 전략
map vs unordered_map: C++ map vs unordered_map

참고 자료

“Operating System Concepts” - Silberschatz, Galvin, Gagne
Redis Documentation: https://redis.io/docs/manual/eviction/
LeetCode 146 (LRU Cache), 460 (LFU Cache)

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