안녕하세요. 자바파커입니다.

LRU(Least Recently Used)는 캐시가 가득 찼을 때 가장 오래 사용하지 않은 항목을 버리는 정책입니다. 교과서 구현은 모든 키의 사용 순서를 정확히 유지합니다.

그런데 Redis의 allkeys-lru는 정확한 LRU가 아닙니다.

Redis는 전체 키를 정렬하지 않고 일부 후보를 샘플링해 가장 오래 사용하지 않은 키를 제거합니다.

정확도를 조금 포기하는 대신 메모리와 갱신 비용을 줄이는 근사 알고리즘입니다.

정확한 LRU는 어떻게 동작할까

일반적인 정확한 LRU 캐시는 해시 맵과 이중 연결 리스트를 함께 사용합니다.

Hash Map           → 키를 O(1)에 찾음
Doubly Linked List → 사용 순서를 O(1)에 변경

MRU [C] [A] [F] [D] [E] [G] [H] [B] LRU

GET A가 발생하면 A를 리스트 맨 앞으로 옮깁니다. 새 키 X를 넣어야 한다면 맨 뒤의 B를 제거합니다.

정확하지만 모든 키마다 리스트 포인터와 순서 갱신이 필요합니다. 수백만 키를 관리하는 Redis에서는 이 부가 메모리와 쓰기 비용이 무시하기 어렵습니다.

Redis의 근사 LRU

Redis는 각 키에 마지막 접근 시각과 관련된 정보를 보관하고, 메모리가 한도를 넘으면 일부 키를 무작위로 뽑습니다.

전체 키: A B C D E F G H
샘플:       C D E   G H

idle time
C 8s · D 56s · E 62s · G 47s · H 73s
→ 샘플 중 H 제거

전체에서 실제로 가장 오래 사용하지 않은 키가 B(91초)여도 B가 샘플에 포함되지 않으면 H가 제거될 수 있습니다. 이것이 근사 LRU입니다.

Redis 3.0 이후에는 좋은 퇴거 후보를 모아두는 eviction pool도 사용해 이전 버전보다 정확도를 높였습니다.

핵심 설정

maxmemory 2gb
maxmemory-policy allkeys-lru
maxmemory-samples 5

maxmemory

캐시 데이터에 사용할 메모리 한도입니다. 새 데이터 추가로 한도를 넘으면 선택한 정책에 따라 키를 제거합니다.

maxmemory-policy

대표 정책은 다음과 같습니다.

순수 캐시라면 모든 키를 퇴거 대상으로 삼는 allkeys-* 계열이 보통 자연스럽습니다. 영구 데이터와 캐시 데이터를 같은 Redis에 섞어 놓고 volatile-*에 의존하면 TTL 누락 키가 퇴거되지 않는 운영 문제가 생길 수 있습니다.

maxmemory-samples

한 번의 선택에서 살펴볼 후보 수입니다. 값을 높이면 정확한 LRU에 가까워질 가능성이 커지지만 검사 비용도 늘어납니다. 기본값을 무작정 올리기보다 hit ratio와 latency를 함께 측정해야 합니다.

LRU와 LFU 중 무엇을 선택할까

LRU는 최근에 사용했는가, LFU는 얼마나 자주 사용했는가를 봅니다.

LRU: 최근 트래픽 변화에 빠르게 반응
LFU: 반복적으로 인기 있는 키를 오래 유지

특정 키가 짧은 시간에 한 번씩 순회되는 workload에서는 LRU가 인기 키를 밀어낼 수 있습니다. 반대로 유행이 빠르게 바뀌는 서비스에서 LFU의 빈도 이력이 너무 오래 남으면 새 인기 키 적응이 느릴 수 있습니다. Redis LFU는 확률적 카운터와 decay를 사용해 이 문제를 완화합니다.

운영에서 확인할 지표

redis-cli INFO stats
redis-cli INFO memory

다음 항목을 함께 봅니다.

• evicted_keys: 메모리 압력으로 제거된 키 수
• keyspace_hits: 캐시 적중 횟수
• keyspace_misses: 캐시 미스 횟수
• used_memory: Redis가 인식하는 사용 메모리
• used_memory_rss: 운영체제에서 본 실제 메모리

hit_ratio = hits / (hits + misses)

퇴거량이 급증하면서 hit ratio가 떨어지고 원본 DB latency가 상승한다면 캐시 크기, 정책, TTL, 키 크기를 함께 점검해야 합니다. 퇴거 자체는 장애가 아니지만, cache churn이 원본 시스템을 압박하면 장애로 번질 수 있습니다.

자주 발생하는 실수

Redis를 원본 저장소로 쓰면서 퇴거 정책을 켠다

퇴거는 데이터를 삭제합니다. 다시 만들 수 없는 원본 데이터와 캐시 데이터를 같은 인스턴스에서 관리하면 안 됩니다.

TTL과 LRU를 같은 의미로 본다

TTL은 데이터의 유효기간이고 LRU는 메모리 압력 시 제거 우선순위입니다. TTL이 남아 있어도 LRU로 제거될 수 있고, TTL이 없어도 allkeys-lru의 대상이 됩니다.

평균 hit ratio만 본다

전체 평균이 높아도 특정 테넌트나 엔드포인트에서 thrashing이 발생할 수 있습니다. 서비스·키 공간·시간대별로 나눠 봐야 합니다.

큰 키 하나가 만드는 순간 메모리를 무시한다

큰 명령 하나가 일시적으로 maxmemory를 크게 초과할 수 있습니다. large key와 batch write도 별도로 감시해야 합니다.

마무리

정확한 LRU → 전체 사용 순서를 정확히 유지
Redis LRU → 일부 후보를 샘플링해 근사

Redis가 근사 방식을 택한 이유는 정확한 한 개의 희생자를 찾는 비용보다, 충분히 오래 사용하지 않은 키를 싸게 찾는 것이 대규모 캐시에서 더 실용적이기 때문입니다.

자주 묻는 질문

Redis에서 LRU가 기본 정책인가요?

환경과 배포 형태에 따라 기본값을 확인해야 합니다. Redis Open Source의 기본 maxmemory-policy는 보통 noeviction이므로 캐시로 사용할 때 명시적으로 설정하는 편이 안전합니다.

volatile-lru와 allkeys-lru의 차이는 무엇인가요?

volatile-lru는 TTL이 설정된 키만 후보로 삼고, allkeys-lru는 모든 키를 후보로 삼습니다.

sample 수를 높이면 무조건 좋은가요?

정확도는 개선될 수 있지만 후보 검사 비용이 늘어납니다. 실제 hit ratio와 tail latency를 측정해 결정해야 합니다.

LRU가 캐시 스탬피드를 막아주나요?

아닙니다. LRU는 메모리 부족 시 무엇을 제거할지 결정합니다. 동일 키가 동시에 만료돼 원본으로 몰리는 캐시 스탬피드는 락, 요청 병합, TTL jitter 같은 별도 대책이 필요합니다.

참고 자료

• Redis — Key eviction
• Redis — Configuration, using Redis as a cache
• 캐시 스탬피드란?