LRU & TTL (캐시 비우기 전략)

캐시에서 데이터를 비우는 두 가지 기준, 메모리가 찼을 때의 LRU와 시간이 지났을 때의 TTL을 정리합니다.

LRU - 가장 오래 안 쓴 것부터 버리기

LRU (Least Recently Used) = 메모리가 가득 차면 가장 오래전에 마지막으로 사용된 데이터부터 삭제하는 정책.

세 자료구조를 조합하면 됩니다:

구조	역할
해시맵	key → 값 저장 (빠른 찾기)
이중 연결 리스트	사용 순서 기록 (맨 앞 = 최신, 맨 뒤 = 가장 오래됨)
힙	TTL 만료 추적 (별개 담당)

동작 흐름:

1. SET 성공 → 리스트 move_to_front (최신 표시)
2. GET 성공 → 리스트 move_to_front
3. SET 후 used_memory > maxmemory → 리스트 맨 뒤부터(가장 오래된 것) 제거, evicted_keys += 1

해시맵 덕분에 "이 키가 리스트 어디 있나"를 O(1)에 알 수 있고, 연결 리스트 덕분에 이동/삭제도 O(1)입니다. 둘의 조합이 LRU를 O(1)로 가능하게 합니다.

used_memory는 요구 공식대로: len(key.encode('utf-8')) + len(value.encode('utf-8'))의 합계.

TTL - 데이터의 유통기한

위 표에서 힙이 따로 맡는 TTL 만료 추적이 바로 이 기능입니다.

TTL (Time To Live) = 키에 만료 시간을 설정하는 기능.

• EXPIRE user:2 3 → user:2는 지금부터 3초 후 만료 예약 (힙에 (만료시각, 키) push)
• 키 조회 시점에 먼저 만료 여부 검사: time.time() >= expire_at이면 삭제 후 없는 키처럼 처리
• 힙에 쌓인 오래된 항목은 나중에 pop될 때 "이미 삭제된 키면 무시"하는 방식(lazy deletion)으로 처리 가능

TTL 코드 반환값 규칙 (헷갈리기 쉬움):

상황	반환
키 없음	(integer) -2
키 있는데 만료 설정 없음	(integer) -1
남은 초	(integer) N

정리

개념	비전공자 버전 요약
LRU	안 쓴 지 제일 오래 된 것부터 버리기 (해시맵+연결리스트 조합)
TTL	데이터 유통기한. 만료 예약은 힙으로 관리

출처: Codyssey-B1/B5-1