LRU 캐시 (LRU Cache)

한 줄 정의: 저장 공간이 가득 찼을 때 가장 최근에 사용되지 않은 데이터부터 지우는 방식으로 제한된 캐시 공간을 관리하는 정책입니다.

쉽게 풀면

책상 위에 자료를 몇 개만 올려둘 수 있다고 해봅시다. 새 자료를 올려야 하는데 자리가 없다면, 가장 오랫동안 손대지 않은 자료부터 서랍에 치우는 것이 자연스럽습니다. LRU(Least Recently Used) 캐시는 바로 이 방식을 컴퓨터 메모리에 적용한 것으로, 최근에 사용한 데이터일수록 앞쪽에 유지하고, 가장 오래전에 사용된 데이터부터 밀어냅니다. 보통 해시 테이블과 이중 연결 리스트를 함께 써서 조회와 삭제를 모두 빠르게 처리합니다.

왜 중요한가

제한된 메모리를 최대한 효율적으로 활용하는 문제는 시스템 설계 전반에서 반복적으로 등장하기 때문에, LRU 캐시는 운영체제, 데이터베이스, 분산 시스템, 웹 서비스 논문 전반에서 기본 비교 대상으로 다뤄집니다. 새로운 캐시 교체 정책을 제안하는 논문에서는 거의 예외 없이 LRU를 성능 비교의 기준선(baseline)으로 삼아 얼마나 개선되었는지를 보여줍니다. 또한 접근 패턴을 예측해 캐시 효율을 높이려는 여러 후속 연구들도 LRU가 놓치는 상황을 분석하는 데서 출발하는 경우가 많습니다.

논문에서는 이렇게 쓰입니다

"서버의 응답 지연을 줄이기 위해 자주 조회되는 질의 결과를 LRU 캐시(LRU cache)에 저장하고, 접근 빈도가 낮은 항목부터 자동으로 제거하도록 설계하였다."

이 문장은 모든 요청을 매번 데이터베이스나 원본 서버에서 새로 처리하지 않고, 최근에 쓰인 결과를 임시로 저장해 두었다가 재사용함으로써 시스템 성능을 높였다는 뜻입니다. 시스템·네트워크·분산 컴퓨팅 논문에서 캐시 정책을 설명할 때 자주 등장합니다.

"제안하는 기법은 LRU 캐시를 기준선으로 삼아 캐시 적중률을 비교했을 때 더 우수한 성능을 보였다."

새로운 캐시 정책을 제안하는 연구에서, 기존에 널리 쓰이는 LRU와 비교하여 자신들의 방법이 더 자주 원하는 데이터를 캐시에서 찾아낼 수 있음을 보였다는 뜻입니다.

"모바일 기기의 제한된 메모리 환경을 고려하여 이미지 로딩 라이브러리에 LRU 캐시를 적용하였다."

메모리가 넉넉하지 않은 환경에서 자주 쓰이는 데이터만 남기고 오래된 데이터는 자동으로 정리되도록 LRU 캐시를 실제 애플리케이션 설계에 적용한 사례입니다.

조금 더 깊게 보면

LRU 캐시를 구현할 때는 조회, 삽입, 삭제를 모두 상수 시간에 처리하기 위해 해시테이블과 이중 연결 리스트를 결합한 자료구조가 흔히 쓰입니다. 다만 LRU는 최근 한 번 사용됐다는 사실만으로 계속 캐시에 남기 때문에, 어쩌다 한 번 접근된 데이터가 자주 쓰이는 데이터를 밀어내는 상황(캐시 오염)이 발생할 수 있습니다. 이런 한계를 보완하기 위해 접근 빈도까지 함께 고려하는 LFU, 최근성과 빈도를 함께 반영하는 ARC 같은 변형 정책이 연구되어 왔습니다.

주의할 점

캐시 공간을 무작정 늘리면 성능이 항상 좋아질 것이라 생각하기 쉽지만, 실제 접근 패턴과 맞지 않으면 효과가 크지 않습니다. 또한 LRU는 "최근성"만 기준으로 삼기 때문에, 얼마나 자주 쓰였는지를 기준으로 삼는 LFU 같은 다른 정책과는 판단 기준이 다르다는 점도 함께 이해하면 좋습니다. 캐시가 실제로 어떻게 계층화되어 동작하는지는 캐시 메모리 계층구조 항목을 참고하세요.