LRU 캐시의 정의
LRU는 ‘Least Recently Used’의 약자로, 가장 오랫동안 사용되지 않은 데이터를 우선적으로 제거하는 캐시 교체 전략입니다. 캐시는 메모리 공간이 한정되어 있기 때문에 새로운 데이터를 저장하려면 기존 데이터 중 일부를 버려야 하는 상황이 생기는데, 이때 ‘언제 마지막으로 사용됐는가’를 기준으로 삼는 것이 LRU입니다. 최근에 쓰인 데이터는 앞으로도 다시 쓰일 가능성이 높다는 경험적 가정(지역성의 원리)에 기반한 방식입니다.
동작 원리와 예시
책상 위에 자주 보는 책 몇 권만 올려둘 수 있는 상황을 떠올려보세요. 새 책을 꺼내려는데 자리가 없다면, 가장 오랫동안 펼쳐보지 않은 책을 책장에 다시 꽂아 넣고 그 자리에 새 책을 올려두는 것과 같은 원리입니다.
LRU 캐시는 보통 해시맵과 이중 연결 리스트를 함께 사용해 구현합니다. 해시맵은 특정 데이터를 빠르게 찾기 위해, 연결 리스트는 사용 순서를 기록하기 위해 쓰입니다. 데이터를 조회하거나 추가할 때마다 해당 노드를 리스트의 맨 앞(최근 사용)으로 옮기고, 용량이 초과되면 리스트의 맨 뒤(가장 오래된 항목)를 제거합니다. 이렇게 구현하면 조회, 삽입, 삭제 모두 O(1) 시간 복잡도로 처리할 수 있어 효율적입니다. 실제로 Python에서는 collections.OrderedDict를 활용하거나, functools의 lru_cache 데코레이터를 통해 간단히 LRU 방식을 적용할 수 있습니다.
실무에서 왜 쓰는지
LRU 캐시는 웹 서버, 데이터베이스, CDN, 브라우저 등 거의 모든 시스템에서 사용됩니다. 예를 들어 데이터베이스 쿼리 결과를 매번 디스크에서 읽어오면 느리기 때문에, 자주 조회되는 결과를 메모리에 캐싱해두고 오래 안 쓰인 항목은 자동으로 정리합니다. Redis 같은 인메모리 캐시 시스템도 메모리가 가득 찼을 때 LRU 정책을 기본 옵션으로 제공합니다.
결국 LRU 캐시는 ‘무한한 메모리는 없다’는 현실적인 제약 속에서, 통계적으로 다시 쓰일 확률이 낮은 데이터를 합리적으로 골라내는 실용적인 전략입니다. 단순하면서도 성능 개선 효과가 커서 캐시 설계의 기본 전략으로 널리 채택되고 있습니다.