캐시 교체 정책(Cache replacement policies)은 컴퓨팅에서 컴퓨터 프로그램 또는 하드웨어 유지 구조가 정보 캐시(Cache)를 관리하는 데 활용할 수 있는 명령 또는 알고리즘을 최적화한 것이다. 캐싱은 일반 메모리 저장소보다 액세스 속도가 더 빠르거나 계산 비용이 저렴한 메모리 위치에 최근 또는 자주 사용되는 데이터 항목을 보관하여 성능을 향상시킨다. 캐시가 가득 차면 알고리즘은 새 데이터를 위한 공간을 확보하기 위해 삭제할 항목을 선택해야 하는데, 이때 어떤 데이터를 제거할지 결정하는 규칙이 바로 캐시 교체 정책이다.
캐시 교체 정책은 일반적으로 히트율(Hit ratio)과 레이턴시(Latency)라는 두 가지 주요 성능 지표 간의 절충점을 찾는 방향으로 설계된다. 더 효율적인 교체 전략은 더 많은 사용 정보를 추적하여 주어진 캐시 크기에서 히트율을 높이는 반면, 빠른 교체 전략은 사용 정보를 적게 추적하여 레이턴시를 줄이는 경향이 있다.
주요 캐시 교체 정책은 다음과 같이 분류된다.
먼저, 최적 알고리즘으로 벨레이디의 최적 알고리즘(Bélády's optimal algorithm)이 있다. 이는 가장 오랜 시간 동안 필요하지 않을 정보를 폐기하는 방식으로 이론상 가장 효율적이지만, 미래를 예측해야 하므로 실제 구현은 불가능하며 다른 알고리즘의 성능 비교 기준으로 사용된다.
무작위 교체(Random Replacement, RR)는 캐시 내의 블록 중 하나를 무작위로 선택해 제거한다. 액세스 기록을 보관할 필요가 없어 단순하며, ARM 프로세서 등에서 사용된 사례가 있다.
큐 기반 정책으로는 선입선출(FIFO)과 후입선출(LIFO)이 있다. FIFO는 추가된 순서대로 블록을 축출하며, LIFO는 가장 최근에 추가된 블록을 먼저 축출한다. SIEVE는 웹 캐시를 위해 설계된 단순 축출 알고리즘으로, 지연 승급(lazy promotion)과 빠른 강등(quick demotion)을 사용한다.
최신성 기반 정책 중 가장 널리 알려진 것은 LRU(Least Recently Used, 최근 최소 사용)이다. 가장 오랫동안 사용되지 않은 항목을 먼저 폐기하며, 캐시 라인에 '나이 비트(age bits)'를 부여하여 추적한다. MRU(Most Recently Used, 최근 최다 사용)는 LRU와 반대로 가장 최근에 사용된 항목을 먼저 폐기하며, 루프 순차 참조 패턴에서 더 효과적이다. 세그먼트 LRU(SLRU)는 캐시를 수습(probationary) 세그먼트와 보호(protected) 세그먼트로 나누어 관리한다.
빈도 기반 정책으로는 LFU(Least Frequently Used, 최소 빈도 사용)가 있다. 항목이 사용된 횟수를 카운터로 기록하여 가장 적게 사용된 항목부터 폐기한다. LFUDA(LFU with Dynamic Aging)는 동적 에이징을 추가하여 인기 객체 세트의 변화에 적응한다. S3-FIFO는 2023년에 설계된 알고리즘으로, 세 개의 FIFO 큐만 사용하여 단일 히트 객체를 걸러내고 인기 객체를 유지한다.
RRIP 스타일 정책으로 RRIP(Re-Reference Interval Prediction)이 있다. 인텔에서 제안한 정책으로, 각 캐시 라인에 RRPV(Re-Reference Prediction Value)라는 예측 값을 부여하여 재참조 간격을 예측한다. 여기에는 정적 SRRIP, 이봉 BRRIP, 동적 DRRIP 등의 변형이 있다.
벨레이디의 알고리즘을 근사하는 정책으로는 Hawkeye와 Mockingjay가 있다. Hawkeye는 과거 액세스 패턴을 분석하여 캐시 친화적인지 여부를 예측하고 RRIP와 결합하여 동작하며, 2017년 CRC2 캐시 챔피언십에서 우승하였다. Mockingjay는 이진 예측을 버리고 더 세분화된 결정을 내릴 수 있도록 개선된 방식이다.
기타 주요 정책으로는 LIRS(Low Inter-reference Recency Set), ARC(Adaptive Replacement Cache), CAR(Clock with Adaptive Replacement), 멀티 큐(MQ) 등이 있다. ARC는 LRU와 LFU 사이의 균형을 지속적으로 유지하며, CAR은 ARC와 Clock의 장점을 결합하였다.
캐시 교체 정책은 CPU 캐시, 운영체제의 페이지 교체, 데이터베이스 버퍼 관리, 웹 캐시, 콘텐츠 전송 네트워크(CDN) 등 컴퓨팅 전반에 걸쳐 광범위하게 활용되는 핵심 개념이다.
