한정된 메모리, 성능을 좌우한다—캐시 교체 알고리즘의 비밀

[한국정보기술신문] 우리는 스마트폰에서 앱을 실행하거나 웹 브라우저로 웹사이트를 로딩할 때, 화면이 빠르게 나타나기를 기대한다. 이러한 빠른 반응 속도를 가능하게 하는 핵심 요소 중 하나가 바로 ‘캐시(Cache)’다. 캐시는 CPU와 주기억장치(RAM) 사이에 위치한 고속 기억장치로, 자주 쓰는 데이터를 임시로 저장해 두었다가 필요할 때 즉시 제공함으로써 전체 시스템 성능을 높인다.

그러나 캐시 메모리의 용량은 제한적이다. 프로세서가 요구하는 데이터가 많아지면, 빈 공간을 마련하기 위해 기존에 캐시에 저장된 데이터를 삭제해야만 한다. 이때 어떤 데이터를 삭제하고 어떤 데이터를 남길지를 결정하는 규칙이 바로 ‘캐시 교체 알고리즘(Cache Replacement Algorithm)’이다. 캐시 교체 알고리즘은 제한된 공간에서 자주 쓰일 데이터를 최대한 보존해 시스템 효율을 높이는 역할을 한다.

캐시와 캐시 교체 알고리즘 개요

캐시는 CPU가 처리해야 할 명령어와 데이터를 빠르게 제공하는 ‘과도기적 저장소’다. CPU가 메모리에서 어떤 데이터를 요청하면, 캐시는 먼저 해당 데이터가 저장돼 있는지 확인한다. 만약 캐시에 데이터가 존재하면 ‘캐시 히트(Cache Hit)’가 발생해 빠르게 데이터를 전달할 수 있고, 없으면 ‘캐시 미스(Cache Miss)’로 판단해 주메모리에서 데이터를 읽어와야 한다.

캐시에 저장 공간이 이미 가득 찬 상태에서 새 데이터를 저장해야 할 경우, 캐시 교체 알고리즘이 어떤 데이터를 삭제할지 결정한다. 이 선택이 잘못되면 향후에 자주 쓰일 데이터를 미리 삭제해 성능 저하가 발생할 수 있기 때문에, 적절한 교체 알고리즘을 선택하는 것은 매우 중요하다.

캐시 교체 알고리즘은 크게 ‘언제’ 데이터를 교체할 것인가(교체 시기 결정)와 ‘어떤’ 데이터를 교체할 것인가(교체 대상 결정)의 두 가지 측면으로 나뉜다. 대부분 시스템은 새로운 데이터가 들어올 때마다 한 번의 교체 여부를 판단하고, 교체 대상은 과거 정보(최근 사용빈도, 사용 시각 등)를 바탕으로 결정한다.

대표적으로 사용되는 캐시 교체 알고리즘에는 FIFO(First-In First-Out), LRU(Least Recently Used), LFU(Least Frequently Used), 그리고 Optimal(OPT) 등이 있다. 각 알고리즘은 교체 대상을 선정하는 기준이 다르며, 주어진 워크로드(데이터 접근 패턴)에 따라 성능 차이가 발생한다.

예를 들어, FIFO는 가장 먼저 캐시에 들어온 데이터를 우선 교체한다. 구현이 간단하지만, 최근에 자주 쓰이는 데이터를 실수로 내보낼 위험이 있다. 반면, LRU는 가장 오랫동안 사용되지 않은 데이터를 삭제하기 때문에, 앞으로도 쓰이지 않을 가능성이 높은 데이터를 제거해 성능을 높인다.

LFU는 사용 횟수가 가장 적은 데이터를 삭제하며, 장기적으로 사용 빈도가 낮은 데이터를 제거해 장점이 있다. 하지만 초기 사용 횟수가 부족해 곧 필요하게 될 데이터를 미리 제거할 위험도 있다. 최적 이론에 기반한 OPT는 이론적으로 이상적인 교체를 보장하지만, 미래까지 알 수 있어야 하기 때문에 실제 운영에서는 사용할 수 없는 ‘오프라인’ 알고리즘이다.

대표적인 캐시 교체 알고리즘

가장 기본적인 FIFO(First-In First-Out)는 큐(Queue) 구조를 이용해 먼저 들어온 데이터를 우선 교체 대상에 올린다. 캐시가 가득 찼을 때 새로운 데이터가 들어오면 큐의 맨 앞에 있는 데이터를 제거하고 그 자리를 새 데이터로 채우는 방식이다. FIFO는 구현이 단순하고 예측 가능하지만, 최근에 자주 쓰이는 데이터도 오래되어 곧 교체될 수 있다는 단점이 있다.

LRU(Least Recently Used)는 “가장 오랫동안 사용되지 않은 것”을 교체 대상으로 선정한다. 실제로 LRU를 구현할 때는 doubly linked list(이중 연결 리스트)와 해시맵을 활용해, 데이터 접근 시마다 해당 노드를 리스트 맨 앞으로 이동시키며, 리스트 맨 뒤 노드를 교체한다. 이렇게 하면 시간 복잡도를 상수 시간(O(1))으로 유지할 수 있다.

LRU는 “최근에 사용된 데이터가 앞으로도 사용될 확률이 높다”는 지역성(Locality) 원칙을 반영해 실무에서 널리 활용된다. 운영체제의 페이지 교체와 웹 브라우저 캐시, 데이터베이스 버퍼 관리 등 다양한 분야에서 LRU 기반 정책이 적용된다. 그러나 데이터 접근 패턴이 순환적(주기적)일 경우, LRU는 캐시를 비효율적으로 사용할 수 있다.

LFU(Least Frequently Used)는 “전체 실행 기간 동안 사용 빈도가 가장 낮은 것”을 교체 대상으로 삼는다. 즉, 장기적으로 자주 사용되지 않는 데이터를 제거하는 방식이다. LFU를 구현하려면 각 데이터에 대한 참조 횟수를 기록해야 하며, 참조 횟수가 동일할 때는 LRU 정책을 덧붙여 교체 대상을 결정하기도 한다.

LFU는 장기적인 사용 패턴을 고려하기 때문에, 안정적인 사용 빈도 기반 정책이다. 그러나 초기 단계 데이터에 대해서는 참조 횟수가 적어도 앞으로 많이 쓰일 수 있어 불리할 수 있으며, 이를 보완하기 위해 SSI(Segmented LRU)나 WLFU(Weighted LFU) 같은 변형 기법이 고안되기도 했다.

Optimal(OPT, Bélády’s Algorithm)은 이론적으로 “가장 나중에 다시 참조될 데이터”를 삭제하는 방식이다. 미래의 모든 참조 정보를 미리 알아야 하기 때문에 오프라인 알고리즘으로 분류된다. OPT 알고리즘은 캐시 미스를 최소화하는 최적 해를 보장하지만, 실제 시스템에 구현하기는 불가능하다.

이상의 대표 알고리즘 외에도 MRU(Most Recently Used), Random Replacement, ARC(Adaptive Replacement Cache), CAR(Cache Array Routing) 등 수많은 변형 알고리즘이 존재한다. 각 알고리즘은 시스템 구조, 워크로드 패턴, 구현 비용 등을 고려해 선택된다.

교체 알고리즘의 성능 평가와 비교

캐시 교체 알고리즘의 성능을 평가할 때 주요 지표는 ‘캐시 히트율(Cache Hit Rate)’과 ‘캐시 미스율(Cache Miss Rate)’이다. 히트율이 높을수록 캐시가 효과적으로 동작하고 있음을 의미한다. 각 알고리즘은 워크로드가 달라질 때 히트율이 크게 변동하므로, 실제 응용 환경에서 평가해야 한다.

예를 들어, 순차적 조회(Sequential Access) 패턴에서는 FIFO나 LRU 모두 유사한 히트율을 낼 수 있다. 그러나 반복적 순환(Looping Access) 패턴에서는 LRU가 더 좋은 성능을 보인다. 반대로 한 번만 접근하고 다시 접근하지 않는 스트리밍(Streaming) 패턴에서는 LFU가 오히려 낮은 성능을 낼 수 있다.

웹 브라우저 캐시에서는 방문 빈도가 높은 페이지가 반복해서 요청되므로 LFU나 LFU 변형 알고리즘이 선호된다. 반면 운영체제의 페이지 교체에서는 최근에 사용된 페이지가 곧 다시 쓰일 확률이 높아 LRU 기반 기법이 널리 쓰인다.

실제 대규모 분산 시스템에서는 단일 캐시 교체 알고리즘만으로는 충분하지 않아, 여러 알고리즘을 조합하거나 적응형(Adaptive) 방식을 채택한다. 예컨대 ARC(Adaptive Replacement Cache)는 LRU와 LFU의 장점을 모두 살리기 위해 두 개의 리스트를 유지하면서 동적으로 정책을 전환한다.

캐시 메모리뿐 아니라 웹 서버, CDN(Content Delivery Network), 데이터베이스 버퍼 풀 등 다양한 시스템에서도 캐시 교체 알고리즘이 핵심 요소로 작동한다. 이때 중요한 점은, 시스템 특성과 워크로드를 정확히 이해해 적합한 기법을 적용해야 히트율을 극대화할 수 있다는 것이다.

알고리즘을 비교 평가할 때는 시뮬레이션이나 벤치마크를 통해 다양한 접근 패턴과 캐시 크기를 시험한다. 이를 통해 히트율, 응답 지연(Latency), 오버헤드(Overhead) 등을 종합적으로 고려해 최적의 정책을 선택하게 된다.

한편, 캐시 크기가 커지면 히트율도 함께 높아지는 경향이 있지만, 비용과 전력, 실리(반도체 면적) 제약을 고려할 때 무작정 캐시 용량을 늘리는 것은 현실적으로 어렵다. 따라서 효율적인 교체 알고리즘이 더욱 중요해진다.

현대 시스템에서의 활용과 발전 방향

최근에는 빅데이터와 인공지능(AI) 시대를 맞아, 캐시 교체 알고리즘도 더욱 정교해지고 있다. 예를 들어 머신러닝 모델을 활용해 다음에 어떤 데이터가 요청될지 예측한 뒤, 그 결과를 바탕으로 교체 결정을 내리는 ‘예측 기반 캐시 교체’ 기법이 연구되고 있다. gazelle-and-cs.tistory.com

모바일 환경에서는 전력 소모가 중요한 문제다. 따라서 캐시 교체 시 과도한 메모리 접근을 줄이기 위해, 전력 효율을 고려한 저전력 캐시 교체 알고리즘이 개발되고 있다. 예컨대, 교체 후보를 미리 계산해 메모리 접근을 줄이는 방식 등이 제안됐다.

클라우드 컴퓨팅과 분산 캐시 시스템에서는 네트워크 비용과 동기화 문제를 고려해야 한다. 분산 환경에서는 캐시 일관성 유지와 네트워크 오버헤드를 최소화하며, 글로벌 히트율을 최적화하는 방안이 중요한 연구 주제다.

또한, 보안 측면에서도 새로운 도전과제가 생겼다. 캐시 타이밍 공격(Cache Timing Attack)처럼, 캐시 접근 패턴을 분석해 민감 정보를 탈취하는 보안 위협이 등장하면서, 보안 강화 기능을 포함한 캐시 교체 정책이 필요해졌다.

앞으로 캐시 교체 알고리즘은 단순히 성능을 최적화하는 것을 넘어, 전력 효율, 보안, 분산 협업 등 다양한 요구사항을 통합해 진화할 것으로 전망된다. 최적의 교체 정책을 찾기 위한 연구는 계속될 것이며, 이를 통해 우리의 디지털 환경은 더욱 빠르고 안전하게 발전할 것이다.

한국정보기술신문 정보기술분과 전호재 기자 news@kitpa.org