C++ LRU 캐시 알고리즘 완벽 가이드 | Least Recently Used·O(1) 구현

LRU 알고리즘이란?

LRU(Least Recently Used)는 고정 크기 캐시가 꽉 찼을 때 가장 오랫동안 “사용되지 않은” 항목을 제거(evict) 하는 규칙입니다.

• 조회(get) 하거나 갱신(put) 하면 그 키는 “방금 사용됨” → 가장 최근 쪽으로 옮깁니다.
• 용량을 넘기면 가장 오래된(맨 뒤) 항목을 지웁니다. 운영체제 페이지 캐시, HTTP 프록시, DB 버퍼 풀, Redis의 allkeys-lru 정책, CPU/앱 레벨 객체 캐시 등에서 같은 아이디어가 쓰입니다.

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

연산	요구사항	단독 unordered_map	단독 list
키로 값 찾기	O(1) 평균	✅	❌ O(n)
임의 키 삭제	O(1)	✅	❌
“최근 사용” 순서 유지·맨 앞 이동	O(1)	❌	✅ (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

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

키 K는 std::hash<K> 및 operator== 가 가능해야 합니다. 값 타입 V는 복사·이동 가능하다고 가정합니다.

#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");
    }
  }
  /** 키가 없으면 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)

1. 키가 이미 있으면 → 값만 갱신하고 splice로 맨 앞.
2. 없고 자리가 있으면 → emplace_front 후 index_[key] = begin().
3. 없고 꽉 찼으면 → 맨 뒤(LRU) 키를 index_와 items_에서 제거 → 새 항목을 앞에 삽입. get 은 값을 찾으면 반드시 splice로 맨 앞으로 옮겨야 “최근 사용”이 맞습니다.

시간 복잡도

• get / put (기존 키) — 해시 탐색 평균 O(1), splice O(1).
• put (신규 키, eviction) — LRU 하나 pop_back + map erase O(1) 평균. 해시 충돌이 많아지면 unordered_map 이 한 버킷에 몰려 최악에 가까워질 수 있으므로, 키가 많으면 reserve(capacity_) 로 재할당을 줄이는 것이 좋습니다.

// 생성자에서
index_.reserve(capacity_ * 2);  // 부하율 여유

일상 비유로 이해하기: 시간 복잡도는 책에서 원하는 페이지를 찾는 방법으로 비유할 수 있습니다. O(1)은 목차를 보고 바로 찾기, O(log n)은 이진 탐색처럼 중간을 펼쳐 앞뒤 판단하기, O(n)은 첫 페이지부터 하나씩 넘기기, O(n²)은 모든 페이지 조합을 확인하기입니다.

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

std::list는 노드 기반 이중 연결 리스트입니다. splice는 노드 객체의 포인터만 재배선하므로 키·값 페이로드를 복사하지 않습니다. unordered_map이 들고 있는 반복자는 같은 노드를 가리키는 핸들이므로, 노드가 맨 앞으로 옮겨져도 맵 엔트리를 갱신할 필요가 없습니다. 반대로 vector로 순서를 유지하려면 임의 위치 삽입·삭제가 평균적으로 O(n)에 가까워져 LRU의 O(1) 목표와 충돌합니다.

해시 테이블은 평균 O(1)이지만 최악 O(n)입니다. 키 분포가 나쁘거나 재해시가 잦으면 지연이 튀므로, reserve로 재할당을 줄이고, 좋은 해시 함수·키 타입을 쓰는 것이 운영 체크포인트입니다.

프로덕션 패턴

• 샤딩: 멀티스레드 환경에서 단일 전역 LRU 대신 키 해시 샤드별로 캐시 인스턴스를 나누고 샤드 락을 잡으면 경합이 줄어듭니다.
• TTL 혼합: LRU만으로는 “시간 기반 만료”가 없으므로, 엔트리에 expires_at을 두고 get 시 만료를 먼저 확인하거나, 백그라운드 스윕을 병행합니다.
• 메모리 상한: 값 타입이 크면 바이트 예산을 기준으로 capacity를 잡고, eviction 시 바이트 합계를 줄이는 가중 LRU로 확장합니다.
• 통계: 히트율·eviction 횟수·평균 리스트 길이를 노출하면 용량 튜닝이 쉬워집니다.

트러블슈팅

증상	가능 원인	조치
간헐적 크래시	erase 후 반복자 사용, 잘못된 splice 대상	모든 핸들러를 동일 연산 순서로 검토
예상보다 느림	해시 최악 케이스, 재할당	reserve, 키 분포·std::hash 특수화 검토
LRU 순서가 어긋남	get 후 splice 누락	조회·갱신 경로 모두에서 MRU 갱신 확인
스레드 레이스	단일 락 없이 공유	mutex로 get/put 직렬화 또는 샤딩

흔한 실수

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

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

2. 잘못된 반복자 저장

list가 재할당으로 노드 주소가 바뀌는 컨테이너는 아니지만, 해당 노드를 erase한 뒤 그 반복자를 map에 남기면 UB입니다. eviction 시에는 맨 뒤 노드의 키로 map만 먼저 지우고 pop_back 순서를 지키세요.

3. 용량 0

위 구현은 생성자에서 예외를 던집니다. “0이면 캐시 비활성” 같은 정책이면 별도 분기가 필요합니다.

4. 스레드 안전성

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

다른 정책과 한 줄 비교

정책	제거 대상	구현 난이도(개략)
LRU	가장 오래 사용 안 함	해시 + 리스트 O(1)
FIFO	먼저 들어온 것	큐 + 맵 가능
LFU	참조 횟수 최소	힙·추가 맵 등으로 무거워지기 쉬움
실무에서는 LRU 또는 TTL + LRU 조합이 많습니다.

정리

• LRU는 최근성을 기준으로 캐시를 비우는 대표 정책입니다.
• C++에서는 std::list + std::unordered_map<키, list::iterator> 가 정석 패턴입니다.
• splice 로 MRU 갱신, 맨 뒤 제거로 LRU eviction 을 O(1)에 가깝게 유지합니다. 더 넓은 맥락(커스텀 자료구조 시리즈, greedy와의 관계)은 relatedPosts에 연결된 글을 참고하면 좋습니다.

관련 글

• C++ 캐시 교체 알고리즘 총정리 | FIFO·LFU·Clock·MRU·OPT와 LRU 비교
• 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리
• C++ map vs unordered_map 심층 비교 |
• C++ 시리즈 전체 목차
• C++ 기초 문법
• C++ STL 컨테이너

심화 부록: 구현·운영 관점

이 부록은 앞선 본문에서 다룬 주제(「C++ LRU 캐시 알고리즘 완벽 가이드 | Least Recently Used·O(1) 구현」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.

내부 동작과 핵심 메커니즘

flowchart TD
  A[입력·요청·이벤트] --> B[파싱·검증·디코딩]
  B --> C[핵심 연산·상태 전이]
  C --> D[부작용: I/O·네트워크·동시성]
  D --> E[결과·관측·저장]

sequenceDiagram
  participant C as 클라이언트/호출자
  participant B as 경계(런타임·게이트웨이·프로세스)
  participant D as 의존성(API·DB·큐·파일)
  C->>B: 요청/이벤트
  B->>D: 조회·쓰기·RPC
  D-->>B: 지연·부분 실패·재시도 가능
  B-->>C: 응답 또는 오류(코드·상관 ID)

• 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
• 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
• 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
• 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.

프로덕션 운영 패턴

영역	운영 관점 질문
관측성	요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가
안전성	입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가
신뢰성	재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가
성능	캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가
배포	롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가
용량	피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가

스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.

확장 예시: 엔드투엔드 미니 시나리오

앞선 본문 주제(「C++ LRU 캐시 알고리즘 완벽 가이드 | Least Recently Used·O(1) 구현」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.

1. 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
2. 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
3. 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
4. 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
5. 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.

handle(request):
  ctx = newCorrelationId()
  validated = validateSchema(request)
  authorize(validated, ctx)
  result = domainCore(validated)
  persistOrEmit(result, idempotentKey)
  recordMetrics(ctx, latency, outcome)
  return result

문제 해결(Troubleshooting)

증상	가능 원인	조치
간헐적 실패	레이스, 타임아웃, 외부 의존성, DNS	최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검
성능 저하	N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스	프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거
메모리 증가	캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납	상한·TTL·힙/FD 스냅샷 비교
빌드·배포만 실패	환경 변수, 권한, 플랫폼 차이, lockfile	CI 로그와 로컬 diff, 런타임·이미지 버전 핀
설정 불일치	프로필·시크릿·기본값, 리전	스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화
데이터 불일치	비멱등 재시도, 부분 쓰기, 캐시 무효화 누락	멱등 키·아웃박스·트랜잭션 경계 재검토

권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.

배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.

---

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. LRU(Least Recently Used) 캐시 교체 정책을 C++로 구현하는 법. unordered_map과 list로 get·put O(1), splice로 최근 사용 갱신, 용량 초과 시 eviction, 흔… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

---

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

• C++ 캐시 교체 알고리즘 총정리 | FIFO·LRU·LFU·Clock·MRU·OPT 완벽 비교
• C++ map/unordered_map | ‘해시맵’ 완벽 정리 [성능 비교]
• C++ 컨테이너 선택 가이드 | vector/list/deque/map/set 상황별 선택과 성능 최적화
• C++ Cache Optimization | 캐시 친화적 코드·False Sharing 방지 완벽 정리

---

이 글에서 다루는 키워드 (관련 검색어)

C++, LRU, 캐시, 알고리즘, 자료구조, unordered_map, list 등으로 검색하시면 이 글이 도움이 됩니다.