DevRoutine — 매일 기술 면접 질문

LRU Cache는 Least Recently Used, 즉 가장 오랫동안 사용되지 않은 항목을 먼저 제거하는 캐시 교체 정책입니다. 최근에 사용한 데이터가 다시 사용될 가능성이 높다는 시간 지역성에 기반합니다.

핵심 개념

조회 또는 삽입된 항목은 '가장 최근 사용' 위치로 이동합니다.
용량을 초과하면 가장 오래 전에 사용된 항목을 제거합니다.
일반적으로 Hash Map + Doubly Linked List 조합으로 get/put을 O(1)에 구현합니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

Text

capacity = 3
put A -> [A]
put B -> [B, A]
put C -> [C, B, A]
get A -> [A, C, B]
put D -> [D, A, C]  // B 제거

JavaScript

// JavaScript Map은 삽입 순서를 보존하므로 간단한 LRU 구현에 활용 가능
class LRU {
  constructor(limit) { this.limit = limit; this.map = new Map(); }
  get(key) {
    if (!this.map.has(key)) return undefined;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.limit) this.map.delete(this.map.keys().next().value);
  }
}

실무에서 주의할 점

순차적으로 한 번만 읽는 workload에서는 LRU가 캐시를 계속 오염시킬 수 있습니다.
캐시 값의 메모리 크기가 제각각이면 항목 개수 기준 capacity만으로 부족합니다.
분산 환경에서는 각 인스턴스의 로컬 LRU가 서로 다른 상태를 가질 수 있습니다.

실무 적용 가이드

API 응답, 계산 결과, DB 조회 결과처럼 반복 접근이 많은 데이터에 적합합니다.
TTL, 최대 메모리, invalidation 조건을 LRU와 함께 설계합니다.
hit rate, eviction count, memory usage를 모니터링해 용량을 조정합니다.

함께 연결해서 보면 좋은 키워드

LRU Cache, Cache Policy, Time Locality, Hash Map, Doubly Linked List

정리

LRU Cache는 Least Recently Used, 즉 가장 오랫동안 사용되지 않은 항목을 먼저 제거하는 캐시 교체 정책입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.

LRU Cache는 어떤 원리로 동작하나요?

답변 포인트

정답 및 해설