C++로 O(1) LRU 캐시 만들기: unordered_map + list, splice, 흔한 반복자 실수

LRU 알고리즘이란?

LRU(Least Recently Used)는 고정 크기 캐시가 꽉 찼을 때 가장 오랫동안 사용되지 않은 항목을 제거(evict)하는 규칙입니다. 키를 조회(get)하거나 갱신(put)하면 그 키는 방금 사용된 것이므로 가장 최근 쪽으로 옮기고, 용량을 넘기면 반대쪽 끝, 즉 가장 오래전에 사용된 항목을 지웁니다.

운영체제 페이지 캐시, HTTP 프록시, DB 버퍼 풀, Redis의 allkeys-lru 정책, CPU/앱 레벨 객체 캐시 등에서 같은 아이디어가 사용됩니다. 다만 이런 시스템 대부분은 교과서적인 LRU를 그대로 쓰지 않습니다. Redis는 모든 키를 연결 리스트로 관리하는 대신 몇 개를 무작위로 뽑아 그중 가장 오래된 키를 지우는 근사 LRU를 쓰고, 리눅스 페이지 캐시는 active/inactive 두 리스트로 나눈 변형을 씁니다. 정확한 LRU는 접근할 때마다 공유 자료구조를 수정해야 하므로, 동시성이 높은 환경에서는 그 비용을 줄이려고 정확도를 조금 포기하는 것입니다. 이 글의 구현은 단일 스레드에서 정확한 LRU가 필요할 때, 그리고 코딩 테스트(LeetCode 146번 같은)에서 요구하는 형태의 기준 구현입니다.

왜 “해시 + 이중 연결 리스트”인가?

연산	요구사항	단독 unordered_map	단독 list
키로 값 찾기	O(1) 평균	O	O(n)
임의 키 삭제	O(1)	O	X
“최근 사용” 순서 유지·맨 앞 이동	O(1)	X	O (splice)

그래서 둘을 함께 씁니다. std::list는 노드 순서로 사용 순서를 표현해 맨 앞이 가장 최근에 사용된 항목(MRU), 맨 뒤가 가장 오래된 항목(LRU)이 되고, std::unordered_map<K, list::iterator>는 키로 그 키의 리스트 노드 위치를 바로 찾아 줍니다.

리스트에서 노드를 떼어 맨 앞으로 붙이는 splice는 포인터만 바꾸므로 O(1)이고, 해당 키의 map 항목은 같은 노드를 가리키는 반복자를 그대로 들고 있으므로 map을 수정할 필요가 없습니다.

flowchart LR
  subgraph list["std list (앞=MRU, 뒤=LRU)"]
    A["(k3,v3)"] --> B["(k1,v1)"] --> C["(k2,v2)"]
  end
  subgraph map[std unordered_map]
    k3 --> A
    k1 --> B
    k2 --> C
  end

std::map(레드블랙 트리)에 “마지막 접근 시각”을 값으로 저장하는 방법도 떠올릴 수 있지만, 그러면 eviction 대상을 찾으려고 전체를 훑거나 시각 기준 인덱스를 하나 더 두어야 해서 O(log n)이 됩니다. 우선순위 큐도 “이미 들어 있는 원소의 우선순위를 올리는” 연산을 표준 라이브러리가 지원하지 않습니다. 결국 “임의 위치의 원소를 O(1)에 떼어 맨 앞으로 붙인다”는 요구를 만족하는 표준 컨테이너는 std::list뿐이고, 그 위치를 O(1)에 찾아 주는 역할을 해시 맵이 맡는 구조입니다.

대가는 메모리입니다. 항목 하나마다 list 노드(앞뒤 포인터 2개 + pair<K,V>)와 해시 맵 노드(다음 포인터 + 키 + 반복자)가 따로 할당되고, 키가 두 번 저장됩니다. int 키라면 문제가 없지만 긴 std::string 키를 수백만 개 담으면 키 복사본과 노드 할당 오버헤드가 값보다 커질 수 있습니다. 이런 경우에는 맵의 키를 list 노드 안의 키를 가리키는 std::string_view로 두거나, Boost.Intrusive처럼 노드에 링크를 내장하는 방식으로 할당을 한 번으로 줄이는 최적화를 고려합니다.

완전한 C++ 구현 (템플릿)

키 K는 std::hash<K> 및 operator== 가 가능해야 합니다. 값 타입 V는 복사·이동 가능하다고 가정합니다. get이 std::optional<V>로 값의 복사본을 돌려주는 점도 설계상의 선택입니다. 포인터나 참조를 돌려주면 복사 비용은 없지만, 다음 put이 그 항목을 evict하는 순간 호출자가 들고 있던 참조가 댕글링이 됩니다. 값이 크다면 V를 std::shared_ptr<T>로 두어 복사를 포인터 복사로 바꾸는 편이 안전합니다.

#include <cstddef>
#include <list>
#include <optional>
#include <stdexcept>
#include <unordered_map>
#include <utility>
template <typename K, typename V, typename Hash = std::hash<K>>
class LRUCache {
public:
  explicit LRUCache(std::size_t capacity) : capacity_(capacity) {
    if (capacity_ == 0) {
      throw std::invalid_argument("LRUCache: capacity must be > 0");
    }
    index_.reserve(capacity_);  // 이후 재해시가 일어나지 않도록 (아래 "시간 복잡도" 참고)
  }
  /** 키가 없으면 std::nullopt */
  std::optional<V> get(const K& key) {
    auto it = index_.find(key);
    if (it == index_.end()) return std::nullopt;
    // 최근 사용: 해당 노드를 맨 앞으로
    items_.splice(items_.begin(), items_, it->second);
    return it->second->second;
  }
  void put(const K& key, V value) {
    auto it = index_.find(key);
    if (it != index_.end()) {
      it->second->second = std::move(value);
      items_.splice(items_.begin(), items_, it->second);
      return;
    }
    if (items_.size() >= capacity_) {
      evict_lru();
    }
    items_.emplace_front(key, std::move(value));
    index_[key] = items_.begin();
  }
  std::size_t size() const noexcept { return items_.size(); }
  std::size_t capacity() const noexcept { return capacity_; }
private:
  using Item = std::pair<K, V>;
  using ItemList = std::list<Item>;
  using Iterator = typename ItemList::iterator;
  void evict_lru() {
    if (items_.empty()) return;
    const K& victim = items_.back().first;
    index_.erase(victim);
    items_.pop_back();
  }
  std::size_t capacity_;
  ItemList items_;
  std::unordered_map<K, Iterator, Hash> index_;
};

사용 예시

#include <iostream>
#include <string>
int main() {
  LRUCache<int, std::string> cache(2);
  cache.put(1, "a");
  cache.put(2, "b");
  cache.get(1);           // 1이 최근 사용
  cache.put(3, "c");      // 용량 2 → LRU인 키 2 제거
  std::cout << cache.get(2).has_value() << '\n';  // 0 (없음)
  std::cout << cache.get(1).value() << '\n';      // a
  std::cout << cache.get(3).value() << '\n';      // c
}

동작을 단계로 따라가기 (put)

put은 세 경우로 나뉩니다. 키가 이미 있으면 값만 갱신하고 splice로 노드를 맨 앞으로 옮깁니다. 키가 없고 자리가 있으면 emplace_front로 새 노드를 넣고 index_[key] = items_.begin()으로 위치를 기록합니다. 키가 없고 꽉 찼으면 맨 뒤(LRU) 항목의 키를 index_와 items_에서 지운 뒤 새 항목을 앞에 넣습니다. get도 값을 찾으면 반드시 splice로 맨 앞으로 옮겨야 “최근 사용” 순서가 맞습니다.

세 번째 경우에서 eviction을 삽입보다 먼저 하는 순서도 의미가 있습니다. 삽입을 먼저 하면 잠깐 동안 capacity + 1개가 되는데, 용량이 1인 캐시에서는 방금 넣은 항목과 지울 항목을 헷갈려 새 항목을 지우는 버그가 나기 쉽습니다. 또 put의 키가 이미 있을 때는 eviction이 일어나면 안 되므로, 존재 여부 검사를 용량 검사보다 앞에 두어야 합니다. 이 순서를 바꾸면 꽉 찬 캐시에서 기존 키를 갱신할 때 엉뚱한 항목 하나가 사라집니다.

시간 복잡도

get과 기존 키에 대한 put은 해시 탐색(평균 O(1))과 splice(O(1))로 끝납니다. 새 키를 넣는 put은 eviction이 필요하면 pop_back과 map의 erase를 한 번씩 더 하므로 역시 평균 O(1)입니다.

unordered_map은 원소 수가 bucket_count × max_load_factor를 넘으면 전체를 재해시하는데, 이때 한 번의 put이 O(n)이 되어 지연이 튑니다. 캐시는 최대 크기를 미리 알고 있으므로 위 구현처럼 생성자에서 reserve(capacity_)를 호출해 두면 재해시가 일어나지 않습니다. reserve(n)은 이미 max_load_factor를 고려해 n개를 담을 버킷 수를 잡으므로 2배로 부풀릴 필요는 없습니다.

해시 충돌로 한 버킷에 키가 몰리는 문제는 reserve로 해결되지 않습니다. 이것은 해시 함수의 품질 문제이고, 외부 입력을 키로 쓰는 서버라면 의도적으로 충돌을 유발하는 입력(hash flooding)도 고려해야 합니다.

내부 동작 원리: 왜 splice 한 번이 O(1)인가

std::list는 노드 기반 이중 연결 리스트입니다. splice는 노드끼리 연결하는 포인터만 바꾸므로 키·값 페이로드를 복사하지 않고, 표준은 옮겨진 원소를 가리키는 반복자와 참조가 계속 유효하다고 보장합니다. 그래서 unordered_map이 들고 있는 반복자는 노드가 맨 앞으로 옮겨진 뒤에도 같은 노드를 가리키고, 맵 엔트리를 갱신할 필요가 없습니다. 반대로 vector로 순서를 유지하려면 임의 위치 삭제와 맨 앞 삽입이 원소를 밀어야 하므로 O(n)이 되어 LRU의 O(1) 목표와 충돌합니다.

프로덕션 패턴

실제 서비스에 넣을 때는 이 기본 구조에 몇 가지를 덧붙이게 됩니다. 멀티스레드 환경에서는 전역 LRU 하나에 락 하나를 두는 대신, 키 해시로 샤드를 나누고 샤드마다 캐시 인스턴스와 락을 따로 두면 경합이 줄어듭니다. 대신 각 샤드가 독립적으로 evict하므로 전체로 보면 정확한 LRU가 아니게 됩니다.

LRU에는 시간 기반 만료가 없으므로, 오래되면 안 되는 데이터라면 엔트리에 expires_at을 두고 get에서 만료를 먼저 확인하거나 백그라운드에서 주기적으로 만료 항목을 지웁니다. 값 크기가 제각각이라면 항목 개수 대신 바이트 예산을 상한으로 두고, 바이트 합계가 예산 아래로 내려갈 때까지 뒤에서부터 evict하는 방식으로 확장할 수 있습니다. 히트율과 eviction 횟수를 지표로 노출해 두면 용량을 조정할 근거가 생깁니다.

흔한 실수

splice 없이 “순서만” 바꾸려 함

맵만 갱신하고 리스트 순서를 안 바꾸면 LRU 판별이 틀어집니다. get과 put 모두에서 사용된 항목을 맨 앞으로 옮겨야 합니다.

잘못된 반복자 저장

list는 재할당으로 노드 주소가 바뀌는 컨테이너가 아니지만, 노드를 erase한 뒤에도 그 반복자를 map에 남겨 두면 다음 접근이 미정의 동작입니다. eviction에서는 맨 뒤 노드의 키로 map 항목을 먼저 지우고 그다음 pop_back하는 순서를 지켜야 합니다.

이 순서가 중요한 이유는 evict_lru의 const K& victim = items_.back().first;가 list 노드 안의 키를 참조로 잡기 때문입니다. pop_back()을 먼저 호출하면 노드가 해제되어 victim이 댕글링 참조가 되고, 그 뒤의 index_.erase(victim)은 해제된 메모리를 읽습니다. 이런 버그는 디버그 빌드에서는 해제된 메모리가 그대로 남아 있어 멀쩡히 동작하다가, 릴리스 빌드나 다른 할당자에서 엉뚱한 키가 지워지는 식으로 나타나서 찾기 어렵습니다. AddressSanitizer(-fsanitize=address)로 테스트를 돌리면 heap-use-after-free로 바로 잡힙니다.

list 대신 std::vector나 std::deque로 바꿔 보려는 시도도 같은 이유로 실패합니다. vector는 재할당이 일어나면 모든 반복자가 무효화되고 중간 삭제는 그 뒤의 반복자를 무효화합니다. deque는 앞뒤 끝에 삽입하기만 해도 모든 반복자가 무효화되고(참조는 유지), 중간 삽입·삭제는 참조까지 무효화하므로 map에 저장한 위치 정보를 믿을 수 없게 됩니다.

용량 0

위 구현은 생성자에서 예외를 던집니다. “0이면 캐시 비활성” 같은 정책이면 별도 분기가 필요합니다. 예외를 던지지 않고 용량 0을 허용하면 put에서 evict_lru()가 빈 리스트를 보고 그냥 반환한 뒤 항목을 넣으므로, “용량 0인데 항목 1개가 들어 있는” 상태가 됩니다. 설정 파일에서 캐시 크기를 읽는 서비스라면 0이 “끄기”를 뜻하는지 오타인지부터 정해 두는 것이 좋습니다.

스레드 안전성

위 클래스는 스레드 안전하지 않습니다. 여러 스레드에서 쓰려면 std::mutex 로 get/put 전체를 감싸거나, 샤딩된 캐시 등을 검토하세요.

처음 멀티스레드로 옮길 때 흔히 하는 실수가 “get은 읽기니까 std::shared_mutex의 공유 락이면 충분하다”고 생각하는 것입니다. LRU의 get은 splice로 리스트를 수정하므로 읽기 연산이 아닙니다. 공유 락으로 여러 스레드가 동시에 splice하면 리스트 포인터가 꼬여 무한 루프나 크래시로 이어집니다. 그래서 LRU는 읽기 비중이 높아도 배타 락이 필요하고, 이것이 경합이 심할 때 샤딩이나 근사 LRU(접근 시 플래그만 세우는 CLOCK 등)로 넘어가는 이유입니다.

다른 정책과 한 줄 비교

정책	제거 대상	구현 난이도(개략)
LRU	가장 오래 사용 안 함	해시 + 리스트 O(1)
FIFO	먼저 들어온 것	큐 + 맵 가능
LFU	참조 횟수 최소	빈도별 리스트로 O(1) 가능하지만 구현이 복잡

실무에서는 LRU 또는 TTL과 LRU를 섞은 조합이 많습니다. LRU가 약한 대표적인 경우는 한 번만 읽히는 대량 스캔입니다. 배치 작업이 테이블 전체를 한 번 훑으면 그 키들이 모두 “최근 사용”이 되어, 정작 자주 쓰이던 항목이 전부 밀려납니다. 이 문제 때문에 DB 버퍼 풀은 새로 읽은 페이지를 리스트 중간에 넣는 midpoint 삽입(MySQL InnoDB)을 쓰고, 애플리케이션 캐시 라이브러리(Caffeine 등)는 빈도와 최근성을 함께 보는 W-TinyLFU 같은 정책을 씁니다.

---

같이 보면 좋은 글

• C++ 캐시 교체 알고리즘: FIFO·LRU·LFU·Clock·MRU·OPT 구현과 비교
• C++ STL 컨테이너: 연산별 성능 비교와 상황별 선택 기준
• C++ 시리즈 전체 목차