LRU 캐시에 대량 순차 조회가 들어온 뒤 자주 쓰던 항목까지 사라집니다. 왜 이런 일이 생기며 항목 크기와 접근 패턴을 반영해 정책을 어떻게 조정하나요?

LRU는 최근에 사용한 항목이 곧 다시 사용될 것이라는 가정에는 잘 맞지만, 대량의 순차 스캔에는 취약합니다. 한 번만 읽는 항목이 계속 캐시에 들어오면 오래 유지되던 핫 항목이 뒤로 밀려나고, 스캔이 끝난 뒤 정상 요청이 연속 miss를 내며 원본 저장소를 다시 압박합니다. 이 현상을 스캔 오염(scan pollution)이라고 부릅니다.

적재·퇴출·관리 비용을 함께 측정합니다

캐시 용량이 3이고 A, B, C를 반복해서 읽고 있는데 D, E, F, G를 한 번씩 순차 조회하면 LRU는 매 접근을 ‘최근 사용’으로 보고 A, B, C를 차례로 내보냅니다. 스캔 직후 A를 다시 요청하면 캐시에서 찾지 못하고, 일회성 데이터가 핫 데이터의 공간을 차지한 대가를 치릅니다. LRU가 잘못된 것이 아니라 시간 지역성이라는 가정과 실제 작업 패턴이 어긋난 것입니다.

모든 항목을 무조건 admission하지 않고 두 번째 접근이 확인된 항목만 캐시에 올리는 정책, 스캔 요청을 별도 캐시나 우회 경로로 보내는 정책을 검토하겠습니다. 빈도가 중요한 접근이라면 LFU나 최근성과 빈도를 결합한 정책이 맞을 수 있지만, 인기가 갑자기 바뀐 키가 오래 남거나 카운터 관리 비용이 생길 수 있습니다. 항목 크기가 다르면 개수 대신 바이트 예산을 사용하고, 큰 항목은 별도 상한을 둡니다. 이를 admission 정책(cache admission policy)과 교체 정책(eviction policy)의 분리라고 설명할 수 있습니다.

캐시 자체의 비용도 측정합니다

정확한 LRU는 읽을 때마다 연결 리스트의 위치를 갱신합니다. 동시 요청이 많으면 이 갱신 락이 원본 조회보다 큰 병목이 될 수 있습니다. 샤드별 LRU, 근사 LRU, 빈도와 최근성을 샘플링하는 구조를 비교하되, 샤드 용량이 고정돼 특정 핫키 그룹이 한 곳에 몰리는 부작용도 봅니다. TTL 만료는 용량 eviction과 별개의 이유이므로 제거 사유를 구분해 기록하겠습니다.

검증은 핫키 반복, 순차 스캔, 핫키 변화, 큰 항목, 동시 접근을 재생합니다. 적중률만 높이면 되는 것이 아니라 원본 DB 부하, p99 지연, eviction churn, 캐시 관리 CPU, 메모리 피크, 만료 후 재조회 폭주를 함께 보겠습니다. 캐시는 정확한 원본을 대신하지 않으며, 오래된 값 허용 범위와 무효화 정책을 별도 계약으로 둡니다.

LRU는 최근 접근 항목이 다시 필요하다는 시간 지역성 가정을 사용합니다. 용량이 3이고 A, B, C를 반복하던 중 D, E, F를 한 번씩 읽으면, LRU는 각각을 최근 항목으로 취급해 A, B, C를 밀어냅니다. 스캔 직후 핫키가 모두 miss가 되는 것이 scan pollution의 구체적인 반례입니다.

모든 miss를 admission하지 않고 재접근한 항목만 올리거나 스캔을 별도 캐시로 보내면 핫키를 보호할 수 있습니다. LFU는 빈도에 강하지만 인기 변화에 늦고, 정확한 LRU는 hit 때마다 목록을 갱신해 락 경합을 만들 수 있습니다. 항목 수 대신 바이트 예산과 큰 항목 상한을 두고, TTL 만료와 용량 eviction의 원인을 나눠 기록합니다. hit ratio뿐 아니라 원본 부하·p99·관리 CPU·eviction churn을 같은 접근 trace로 비교하겠습니다.

항목 크기가 다르면 가장 오래된 항목 하나를 제거해도 새 값이 들어갈 공간이 부족할 수 있습니다. 필요한 바이트가 확보될 때까지 여러 항목을 제거하거나 큰 항목은 저장하지 않는 상한을 둡니다. 같은 hit ratio라도 1KB 값과 10MB 값의 원본 비용은 다르므로 요청 적중률과 바이트 적중률을 구분해 비교하겠습니다.