캐시 교체 정책

벨레이디의 알고리즘은 캐시 교체 정책의 이론적 최적해로 간주된다. 이 정책은 미래에 가장 오랫동안 사용되지 않을 캐시 항목을 교체 대상으로 선택한다. 벨레이디의 최적 알고리즘이나 선견지명 알고리즘이라고도 불리며, 평균 메모리 참조 시간을 최소화하고 캐시 히트율을 극대화하는 것을 목표로 한다.

그러나 이 알고리즘은 미래의 모든 메모리 접근 패턴을 미리 알고 있어야만 정확한 결정을 내릴 수 있다. 이러한 '미래에 대한 지식'은 실제 운영체제나 컴퓨터 프로그램이 런타임에 가질 수 없는 정보이기 때문에, 실용적인 시스템에서 직접 구현하는 것은 불가능하다.

따라서 벨레이디의 알고리즘은 주로 다른 실용적인 캐시 알고리즘들의 성능을 평가하는 기준(benchmark)으로 사용된다. 다양한 교체 정책을 시뮬레이션한 후, 그 결과를 이 이론적 최적치와 비교하여 각 알고리즘의 효율성을 판단한다. 페이징 시스템에 특화된 상세한 알고리즘에 대해서는 페이지 교체 알고리즘 문서에서 다룬다.

무작위 교체는 캐시가 가득 찼을 때 축출할 항목을 무작위로 선택하는 간단한 교체 정책이다. 이 알고리즘은 항목의 액세스 기록이나 사용 빈도와 같은 메타데이터를 전혀 추적할 필요가 없으며, 단순히 캐시 내의 임의의 위치에 있는 데이터를 교체 대상으로 선택한다. 이러한 단순성 덕분에 구현 오버헤드가 매우 낮고 하드웨어 비용을 절감할 수 있다.

이 방식은 ARM 프로세서와 같은 일부 하드웨어 설계에서 사용된 바 있다. 또한, 알고리즘의 확률적 특성으로 인해 효율적인 추계학적 시뮬레이션이 가능하다는 장점이 있다. 그러나 사용 패턴에 대한 정보를 전혀 고려하지 않기 때문에, 캐시 히트율 측면에서 LRU나 LFU 같은 더 정교한 정책들에 비해 일반적으로 성능이 낮은 것으로 평가된다.

단순 큐 기반 정책은 캐시 교체 정책 중 가장 기본적인 형태로, 데이터 항목이 캐시에 들어온 순서를 기준으로 관리하는 방식이다. 이 정책들은 알고리즘의 복잡도가 낮고 구현이 간단하여 하드웨어나 운영체제의 버퍼 캐시 관리에 널리 활용된다. 핵심 아이디어는 큐 자료구조를 사용하여 항목의 순서를 유지하는 것이다.

대표적인 알고리즘으로는 선입 선출 방식이 있다. 이 방식은 캐시가 가득 찼을 때 가장 먼저 들어온 항목을 교체한다. 구현이 매우 단순하지만, 자주 사용되는 항목이라도 오래되었다는 이유만으로 교체될 수 있어 성능이 최적이 아닐 수 있다. 반대로 후입 선출 또는 선입 후출 방식은 가장 최근에 들어온 항목을 먼저 교체한다. 이는 특정 순환 액세스 패턴을 보이는 워크로드에서 유리할 수 있다.

보다 발전된 형태로 SIEVE 알고리즘이 있다. 이는 콘텐츠 전송 네트워크나 키-값 저장소 같은 웹 캐시를 위해 설계되었으며, '지연 승급'과 '빠른 강등' 개념을 도입한다. 새 객체는 먼저 작은 FIFO 큐에 들어가고, 재참조되지 않으면 신속히 축출된다. 재참조된 객체만 메인 큐로 승급되어 장기 보관되므로, 캐시 오염을 줄이고 히트율을 개선하는 효과가 있다.

단순 최신성 기반 정책은 캐시 항목이 얼마나 최근에 사용되었는지를 기준으로 교체 대상을 결정하는 알고리즘 군을 가리킨다. 이 접근법의 핵심은 시간적 국부성, 즉 최근에 사용된 데이터가 가까운 미래에 다시 사용될 가능성이 높다는 경험적 관찰에 기반한다. 따라서 이러한 정책들은 각 항목의 최근 사용 이력을 추적하여, 가장 오래전에 사용된 항목을 우선적으로 캐시에서 제거함으로써 캐시 히트율을 높이려고 한다.

가장 대표적인 알고리즘은 최근 최소 사용(LRU)이다. LRU는 사용 시점을 정확히 기록하여 가장 오랫동안 참조되지 않은 항목을 교체한다. 그러나 모든 액세스에 대한 타임스탬프를 유지하거나 순서 리스트를 갱신해야 하므로, 구현 복잡도와 오버헤드가 높다는 단점이 있다. 이를 극복하기 위해 의사 LRU(PLRU)나 Clock 알고리즘과 같은 근사화 기법이 하드웨어 캐시 메모리에서 널리 사용된다.

반대로 최근 최다 사용(MRU) 알고리즘은 가장 최근에 사용된 항목을 교체 대상으로 선정하는 특이한 전략이다. 이는 데이터베이스의 순환 액세스 패턴이나 특정 루프 순차 참조와 같이, 한 번 액세스된 데이터가 당분간 다시는 필요하지 않은 워크로드에서 오히려 LRU보다 더 나은 성능을 보일 수 있다. 이처럼 단순 최신성 기반 정책은 워크로드의 접근 패턴에 따라 적절한 변형 알고리즘을 선택하는 것이 중요하다.

단순 빈도 기반 정책은 캐시 항목이 참조된 횟수, 즉 빈도를 주요 기준으로 하여 교체 대상을 결정하는 알고리즘군이다. 최근 최소 사용 정책이 참조된 시점의 최신성을 추적하는 것과 달리, 이 정책은 장기적인 인기도를 추적하려는 접근법을 취한다. 가장 기본적인 형태는 최소 빈도 사용 알고리즘으로, 참조 횟수가 가장 적은 항목을 우선적으로 캐시에서 축출한다.

이 방식은 장기적으로 매우 자주 사용되는 항목을 캐시에 유지하는 데 유리하지만, 단점도 존재한다. 한 번 많이 참조된 항목은 이후에는 전혀 사용되지 않더라도 오랫동안 캐시를 점유할 수 있는 '캐시 오염' 현상이 발생할 수 있다. 또한 각 항목의 참조 횟수를 지속적으로 기록하고 정렬해야 하므로 구현 오버헤드가 크다는 문제점이 있다.

이러한 문제를 완화하기 위해 여러 변형 알고리즘이 개발되었다. 동적 에이징 LFU는 시간에 따라 참조 횟수의 가치를 감소시켜 오래된 인기 항목이 자연스럽게 교체되도록 한다. 최소 빈도 최근 사용 알고리즘은 빈도와 최신성이라는 두 가지 요소를 결합하여 성능을 개선하려고 시도한다. 2023년에 제안된 S3-FIFO 알고리즘도 단일 히트 워너를 효율적으로 걸러내기 위해 빈도 정보를 간접적으로 활용하는 정책에 속한다.

단순 빈도 기반 정책은 웹 캐시나 콘텐츠 전송 네트워크처럼 특정 콘텐츠의 인기도가 뚜렷하고 장기간 유지되는 워크로드에서 효과적으로 적용될 수 있다.

RRIP 스타일 정책은 재참조 간격 예측이라는 개념을 기반으로 하는 캐시 교체 정책의 한 계열이다. 이 정책들은 각 캐시 라인에 재참조 예측 값이라는 메타데이터를 부여하여, 해당 라인이 미래에 다시 사용될 것으로 예상되는 시점을 예측하고 이를 바탕으로 교체 대상을 선정한다. 이 접근법은 스캔 저항성을 높이면서도 재사용되지 않는 오래된 라인을 효과적으로 제거할 수 있도록 설계되었다.

기본적인 RRIP 알고리즘에서는 캐시 미스가 발생해 새로운 데이터를 삽입할 때, 해당 라인의 재참조 예측 값을 가능한 최대값으로 설정한다. 이는 새로 삽입된 데이터가 당장 재사용되지 않을 가능성이 있음을 의미하며, 이후 캐시가 가득 찼을 때 우선적으로 교체 후보가 될 수 있게 한다. 만약 해당 라인이 나중에 재사용되면, 그 재참조 예측 값은 0으로 재설정되어 향후 다시 사용될 가능성이 높은 '핫' 데이터로 간주된다. 교체 시에는 재참조 예측 값이 가장 높은 라인, 즉 재사용될 가능성이 가장 낮다고 예측되는 라인이 선택된다.

RRIP의 대표적인 변종으로는 정적 RRIP, 이봉 RRIP, 동적 RRIP이 있다. 정적 RRIP는 모든 새 데이터를 동일한 높은 재참조 예측 값으로 삽입하는 단순한 방식이다. 이봉 RRIP는 작업 집합이 캐시 크기를 초과하여 스래싱이 발생하는 상황을 완화하기 위해, 대부분의 데이터는 높은 값으로 삽입하되 일부 데이터는 약간 낮은 값으로 삽입하여 캐시에 더 오래 머물게 한다. 동적 RRIP는 세트 듀얼링 기법을 사용해 런타임에 워크로드의 특성을 감지하여 정적 RRIP와 이봉 RRIP 중 더 적합한 정책을 동적으로 선택한다.

이러한 RRIP 스타일 정책의 유연성과 효율성은 이후 Hawkeye나 Mockingjay와 같은 더 진보된 캐시 교체 알고리즘의 기반이 되었다. 이러한 알고리즘들은 벨레이디의 알고리즘을 근사화하기 위해 RRIP의 프레임워크를 활용한다.

벨레이디의 알고리즘 근사 정책은 최적의 성능을 보이는 벨레이디의 알고리즘을 실제 시스템에서 구현 가능하도록 근사화한 정책들을 말한다. 벨레이디의 알고리즘은 미래의 모든 메모리 접근 패턴을 미리 알고 있어야 하기 때문에 실현 불가능한 이론적 최적 정책이다. 따라서 연구자들은 과거 액세스 패턴을 분석하여 미래의 재사용 거리를 예측함으로써 벨레이디의 알고리즘을 모방하는 다양한 정책을 개발했다.

대표적인 예로 Hawkeye 정책이 있다. Hawkeye는 샘플링된 캐시 세트와 긴 액세스 히스토리를 사용하여, 특정 프로그램 카운터가 생성하는 접근이 향후 재사용될 가능성이 높은지(캐시 친화적) 낮은지(캐시 혐오적)를 학습한다. 이렇게 학습된 정보는 재참조 간격 예측 스타일의 정책에 피드백되어, 캐시 친화적 라인은 오래 유지되고 캐시 혐오적 라인은 빠르게 축출되도록 한다.

또 다른 정책인 Mockingjay는 Hawkeye를 개선하여 더 세분화된 예측을 수행한다. 이 정책은 시간차 학습을 기반으로 한 재사용 거리 예측기를 사용하여 각 캐시 라인의 예상 재참조 시간을 동적으로 계산한다. 캐시에서 공간이 필요할 때는 이 예상 시간이 가장 먼 라인을 우선적으로 축출하는 방식을 취한다. 이러한 접근법을 통해 벨레이디의 최적 정책에 매우 근접한 성능을 달성할 수 있다.

이러한 근사 정책들은 하드웨어 구현 복잡도와 성능 간의 균형을 추구하며, 기계 학습 기법을 활용한 보다 정교한 예측자 연구로도 이어지고 있다.

기계 학습 정책은 인공지능의 한 분야인 기계 학습 기술을 활용하여 캐시 교체 결정을 내리는 접근법이다. 기존의 고정된 규칙 기반 알고리즘과 달리, 워크로드의 동적 패턴을 학습하고 예측하여 더 지능적인 교체 결정을 가능하게 한다. 이는 벨레이디의 알고리즘과 같은 최적 정책을 근사화하거나, 특정 애플리케이션의 접근 특성에 적응하는 것을 목표로 한다.

주요 방법으로는 퍼셉트론이나 마르코프 연쇄와 같은 모델을 사용하여 특정 캐시 라인이 재참조될 가능성이나 시점을 예측하는 것이 있다. 예를 들어, 프로그램 카운터(PC)나 과거 액세스 기록을 입력 특징으로 사용하여 미래의 재사용 거리를 예측하는 모델을 훈련시킬 수 있다. 이러한 예측값은 RRIP 스타일 정책의 예측값이나 직접적인 축출 우선순위로 변환되어 활용된다.

이러한 정책의 장점은 다양한 워크로드에 대해 보다 강력한 적응성을 보일 수 있다는 점이다. 그러나 기계 학습 모델의 훈련 및 추론에 따른 오버헤드, 하드웨어 구현 복잡성, 그리고 학습된 모델이 새로운 또는 변화하는 패턴에 대해 일반화되지 못할 위험과 같은 도전 과제도 존재한다. 일부 연구에서는 강화 학습을 적용하거나, 학습 강화 알고리즘을 통해 기존 알고리즘의 성능을 보조하는 하이브리드 형태의 접근법도 탐구되고 있다.

기타 정책에는 앞서 언급된 주요 정책군에 완전히 속하지 않거나, 여러 접근법을 혼합한 혁신적인 캐시 교체 알고리즘들이 포함된다. 대표적으로 낮은 상호 참조 최신성 세트(LIRS) 알고리즘은 재사용 거리라는 개념을 도입하여 최근 최소 사용 정책의 한계를 극복하고자 한다. LIRS는 단순히 가장 오래전에 사용된 항목을 교체하는 대신, 항목의 상호 참조 최신성을 평가하여 보다 정교한 교체 결정을 내린다.

적응형 교체 캐시(ARC)는 최근 최소 사용과 최소 빈도 사용 정책의 장점을 결합한 자기 조정 알고리즘이다. ARC는 최근에 축출된 항목의 역사를 지속적으로 모니터링하여 수습 세그먼트와 보호 세그먼트의 크기를 동적으로 조정함으로써 변화하는 워크로드에 적응한다. 이와 유사하게 적응형 교체 클록(CAR)은 ARC의 적응성과 클록 알고리즘의 단순함과 효율성을 융합한 정책이다.

멀티 큐(MQ) 알고리즘은 여러 단계의 LRU 큐를 계층 구조로 운영하며, 각 큐는 블록의 예상 수명을 기준으로 관리된다. 또한 Pannier는 플래시 캐시 환경을 위해 설계된 컨테이너 기반 메커니즘으로, 가변적인 액세스 패턴을 보이는 데이터 블록 그룹을 식별하고, 그 생존 시간을 기준으로 효율적으로 관리한다. 이러한 다양한 기타 정책들은 특정 애플리케이션 또는 하드웨어 환경에서 더 나은 캐시 성능을 달성하기 위해 지속적으로 연구되고 있다.