캐시는 원본의 대체 저장소가 아니라 제한된 공간에서 재사용 가능성이 높은 결과를 보존하는 성능 계층입니다. 따라서 입장(admission), 퇴거(eviction), 만료(expiry), 원본의 정확성 계약을 분리해 어떤 요청을 보존하고 어떤 요청을 통과시킬지 먼저 결정해야 합니다.
일회성 스캔에 따른 반복 사용 데이터 퇴거
용량 3의 캐시에 A·B·C가 있고 이 셋을 반복해서 읽는다고 합시다. 갑자기 큰 보고서가 한 번만 사용할 X·Y·Z를 순서대로 읽습니다. LRU는 가장 오래 사용하지 않은 항목부터 제거하므로 보고서가 끝나면 캐시에 X·Y·Z만 남을 수 있습니다. 다음 A·B·C 요청은 다시 원본을 읽습니다.
LRU는 최근 접근을 미래 접근의 단서로 쓰는 정책이지 일회성 스캔과 반복 사용을 구분하는 완벽한 예측기가 아닙니다. 캐시에 넣을지 정하는 입장 정책과, 꽉 찼을 때 무엇을 내보낼지 정하는 퇴거 정책을 나누면 대응이 분명해집니다.
LRU 순서 추적
아래 목록은 왼쪽이 최근 사용, 오른쪽이 퇴거 후보입니다.
| 접근 | 캐시 순서 | 퇴거 |
|---|---|---|
| 시작 | [A,B,C] | 없음 |
| X | [X,A,B] | C |
| Y | [Y,X,A] | B |
| Z | [Z,Y,X] | A |
| A | [A,Z,Y] | X |
그림을 글로 읽기
- LRUCache: get(key) · put(key,value)
- HashMap: key → 목록 노드
- 이중 연결 목록: 앞: 최근 사용 · 뒤: 퇴거 후보
- LRUCache → HashMap: 조회
- LRUCache → 이중 연결 목록: 순서 유지
- HashMap → 이중 연결 목록: 노드 참조
이론적 평균 O(1)도 해시 계산·락·할당·큰 값 해제 비용을 포함한 요청 지연이 일정하다는 뜻은 아닙니다. 동시 접근에서는 맵과 목록의 원자적 일치와 노드 수명을 함께 보호해야 합니다.
이 표를 코드 검증에 사용할 때는 hit와 miss를 구분해 hit가 목록 앞쪽으로 이동하는지, miss의 insert가 실제로 capacity를 넘길 때만 victim을 제거하는지 확인합니다. 동시 구현에서는 map에 노드가 있는데 목록에서 사라지거나, 목록에는 있는데 map에서 조회되지 않는 중간 상태가 관측되지 않아야 합니다. 예상 진단은 hit rate가 높아도 X·Y·Z 스캔 직후 A·B·C가 모두 miss라면 LRU 자체가 고장이라기보다 admission 부재일 수 있다는 것입니다.
캐시 입장과 퇴거의 분리
앞의 X·Y·Z처럼 한 번만 읽을 가능성이 큰 대형 스캔이 miss로 들어오면, 원본에서 값을 받아 사용자에게 반환하되 캐시에는 넣지 않을 수 있습니다. estimatedReuse가 낮거나 value.bytes가 한 항목 상한을 넘으면 그대로 통과시키고, 다시 쓰일 가능성이 있는 작은 값일 때만 여유 공간을 확인해 필요하면 victim을 내보낸 뒤 넣습니다. 이렇게 하면 이미 들어온 값을 누구부터 퇴거할지와, 애초에 스캔 값을 캐시에 들일지를 별개의 결정으로 다룰 수 있습니다.
onMiss(key):
value = loadOriginWithinBudget(key)
if estimatedReuse(key) is low or value.bytes > maximumEntryBytes:
return value # 조회는 성공, 캐시 입장은 생략
while usedBytes + value.bytes > capacityBytes:
evict(policyVictim())
insert(value)
return value
원본 조회와 동시 캐시 변경 사이에 값이 낡는 문제는 별도의 버전 게시 계약이 필요합니다. 이 슈도코드는 용량 정책이며 강한 일관성 구현이 아닙니다.
정책 선택은 재사용 가능성 × 원본 비용 × 바이트 비용 × 유효 기간으로 설명하면 구체화됩니다. 큰 값이 비싸게 재생성되더라도 한 번만 쓰이고 곧 만료되면 입장하지 않는 편이 나을 수 있고, 반대로 작은 권한 결과는 hit가 아니라 최신성 실패가 더 큰 비용일 수 있습니다. loadOrigin과 insert 사이에 version이 바뀌는 시험을 두어, 용량 판단이 일관성 보장을 암묵적으로 약속하지 않는지 확인합니다.
LFU 누적 인기도의 감쇠 수명
사용 빈도가 낮은 항목을 제거하는 LFU는 자주 쓰는 A를 스캔으로부터 지킬 수 있습니다. 하지만 어제 A가 백만 번 읽혔고 오늘 B가 인기라면, 누적 카운터를 영원히 유지하는 LFU는 A를 너무 오래 남길 수 있습니다. 주기적 감소·시간 창·최근 빈도 추정 등 감쇠가 필요합니다.
감쇠가 빠르면 급변에 잘 적응하지만 짧은 버스트에 흔들릴 수 있고, 느리면 오래된 인기에 집착합니다. 큰 카운터의 포화, 같은 빈도의 동점 퇴거, 새 항목이 언제 재입장할 수 있는지도 정합니다. LRU와 LFU라는 이름만으로 구체적인 비용·분포를 결정하지 않습니다.
TTL 만료와 메모리 퇴거의 분리
TTL 만료는 값의 시간 유효성, 메모리 퇴거는 공간 예산에 관한 정책입니다. TTL이 1분 남았어도 용량이 부족하면 제거될 수 있습니다. 반대로 TTL이 지났다고 시스템 전체에서 즉시 메모리가 회수되는지도 구현마다 다릅니다.
| 기준 | 질문 | 주의점 |
|---|---|---|
| 최근성 | 최근에 다시 썼는가 | 순차 스캔 오염 |
| 빈도 | 얼마나 자주 썼는가 | 과거 인기 감쇠 |
| 크기 | 얼마나 메모리를 차지하는가 | 적은 큰 항목이 용량 독점 |
| 재생성 비용 | miss 때 얼마나 비싼가 | 비싼 값이 다시 쓰일 확률도 필요 |
| 유효 시간 | 아직 써도 되는가 | 값 보존과 최신화 기한은 다름 |
권한·재고처럼 최신 판단이 필요한 데이터는 오래된 값을 유지한다고 안전해지지 않습니다. 재생성 비용이 비싸도 유효하지 않은 값은 최종 결정에 쓰지 않습니다. 필수 원장이나 중복 방지 기록을 일반 캐시처럼 퇴거시키면 정확성 계약이 깨질 수 있습니다.
읽기 시점 만료와 백그라운드 만료를 각각 시험해야 합니다. TTL이 지난 항목을 읽었을 때 즉시 miss가 되는지, 아무도 읽지 않아도 메모리에서 제거되는지, stale-while-revalidate를 허용하는지가 구현 계약입니다. 장애 진단에서는 stale 응답 수와 eviction 수를 같은 지표로 합치지 않고 expired, evicted, admission_rejected, origin_error를 분리합니다.
샤드별 상한과 전체 여유 공유의 부재
캐시를 네 샤드로 나누고 각각 1GB로 제한하면 한 샤드에 인기 키가 몰릴 때 그 샤드만 계속 퇴거할 수 있습니다. 다른 샤드의 여유 2GB가 자동으로 이동하지 않습니다. 해시 분포·값 크기·핫키 접근률을 각각 봐야 합니다.
샤드 용량 재배분이나 공용 여유 풀은 편중을 완화하지만 동기화·격리 비용이 늘고, 키 이동에는 cache miss와 버전·소유권 전환이 필요합니다. 한 키의 호출이 집중되는 문제는 용량 균등 배치만으로 해결되지 않습니다. 전체 miss 시 원본 진입 제어도 별도입니다.
접근 이력·원본 비용 기반 정책 평가
반복 집합 A·B·C, 그 사이 일회성 스캔, 인기 키 교체, 크기가 다른 항목, TTL 동시 만료를 재현합니다. 적중률뿐 아니라 적중 바이트·원본 조회 비용·사용자 지연·퇴거 비용·메모리 피크를 비교합니다. 값이 작고 싼 요청의 hit만 늘어도 큰 원본 비용은 그대로일 수 있습니다.
정책 변경 전후 같은 접근 이력을 재생하되 실제 동시성·재생성 지연도 별도로 시험합니다. “LRU를 썼으니 캐시가 최적”이 아니라 어떤 부하에서 무엇을 보존하고 무엇을 버릴지 설명할 수 있어야 합니다.
같은 trace를 재생할 때 warm-up 구간을 제외할지, 캐시를 비울지, 동시성을 고정할지 먼저 정합니다. 예상 결과는 A·B·C 반복 workload에서 admission을 켠 정책이 스캔 뒤의 재가열 miss를 줄이고, hit rate만 보던 비교보다 원본 CPU·bytes·p99를 함께 볼 때 정책 선택이 달라질 수 있다는 것입니다. 샤드별 p95 사용량과 키별 편중도도 전체 평균과 함께 기록합니다.