LRU를 대체하는 FIFO 캐시 축출

캐시 축출 연구의 축이 무엇을 지울지에서 여러 스레드가 동시에 지울 때 어떻게 안 막힐지로 옮겨갔습니다.

LRU가 멀티코어에서 막히는 곳

가장 오래 참조되지 않은 항목을 지우는 LRU(Least Recently Used)는 접근이 일어날 때마다 해당 객체를 연결 리스트의 머리로 옮깁니다. 이 순서 리스트는 모든 스레드가 공유하므로, 조회 한 번이 히트하기만 해도 공유 구조에 쓰기 잠금이 걸립니다. 캐시 조회는 읽기인데 메타데이터 갱신은 쓰기라는 불일치가 병목의 출발점입니다.

스레드를 늘려도 처리량이 비례해 늘지 않는 이유가 여기 있습니다. 코어마다 같은 리스트 머리를 잡으려 경합하므로, 코어를 늘린 만큼 락 대기 시간도 함께 늘어납니다. S3-FIFO 저자들의 후속 정리에 따르면 16스레드 환경에서 S3-FIFO는 최적화된 LRU 구현 대비 약 6배 높은 처리량을 기록했습니다.

FIFO(First In First Out) 계열은 갱신 시점을 미뤄 이 지점을 피합니다. 접근이 일어나면 객체에 붙은 비트만 건드리고, 큐 재배치는 축출(eviction)이 실제로 필요한 순간까지 미룹니다. 히트 경로에서 공유 구조를 건드리지 않으므로 잠금이 필요 없습니다.

Yang, Yue, Rashmi는 HotOS 2023에서 이 설계를 lazy promotion과 quick demotion 두 축으로 정리했습니다. 승격은 최대한 늦게, 강등은 최대한 빨리 한다는 뜻입니다. 아래 두 알고리즘은 같은 원칙을 서로 다른 자료구조로 구현합니다.

한 번만 쓰이는 객체를 걸러내는 S3-FIFO

S3-FIFO(SOSP 2023, Yang, Zhang, Qiu, Yue, Rashmi)는 실측 트레이스 관찰에서 출발합니다. 편향된 워크로드에서는 대부분의 객체가 짧은 시간 창 안에 단 한 번만 접근됩니다. 이런 일회성 객체를 메인 캐시에 들이면 재사용될 객체의 자리를 밀어냅니다.

해법은 신규 객체를 작은 대기실에 먼저 세우는 것입니다. S3-FIFO는 크기가 고정된 세 개의 FIFO 큐로 캐시를 나눕니다.

Small 큐가 quick demotion을 담당합니다. 일회성 객체는 캐시 공간의 10% 안에서만 살다 사라지므로, 나머지 90%는 재사용이 확인된 객체로 채워집니다.

Ghost 큐는 제거된 객체의 키만 들고 있어 메모리를 거의 쓰지 않습니다. Small에서 밀려난 키가 다시 요청되면 Ghost에 남아 있는지 확인해 Main으로 바로 올릴지 판단합니다. 조금 긴 간격의 재접근을 놓치지 않으면서도 실제 객체를 두 번 저장하지 않는 구조입니다.

Lazy promotion은 Main 큐 안에서 동작합니다. 재접근된 객체를 즉시 머리로 옮기지 않고, 큐 꼬리에 도달해 제거될 위기에 놓였을 때만 재삽입(reinsertion)으로 승격시킵니다. 승격 연산이 히트마다가 아니라 축출 시점에만 일어나므로 히트 경로가 가벼워집니다.

6,594개 캐시 트레이스와 14개 데이터셋으로 수행한 평가에서 S3-FIFO는 기존 기법보다 미스율을 일관되게 낮췄습니다.

평균값은 작아 보이지만 최대값은 모두 49%를 넘습니다. 워크로드에 따라 격차가 크게 벌어진다는 뜻입니다.

큐 하나와 손가락 포인터로 줄인 SIEVE

SIEVE(NSDI 2024, Zhang, Yang, Yue, Vigfusson, Rashmi)는 S3-FIFO와 같은 통찰을 공유하면서 자료구조를 더 줄입니다. 여러 개의 FIFO 리스트 대신 단일 FIFO 리스트 하나와 이동하는 손가락(hand) 포인터 하나만 씁니다.

insert(obj):
    visited[obj] = false
    push_head(queue, obj)        # 신규 객체는 항상 큐 머리에 삽입
 
on_hit(obj):
    visited[obj] = true          # 위치 이동 없이 비트만 설정
 
evict():
    while true:
        obj = hand.current()
        if visited[obj]:
            visited[obj] = false     # 방문 기회를 한 번 소진시키고
            hand.move_toward_head()  # 포인터만 이동, 재배치 없음
        else:
            remove(obj)              # 미방문 객체를 실제로 제거
            hand.reset_if_needed()
            return

히트 경로에서 하는 일은 비트 하나를 세우는 것이 전부입니다. S3-FIFO는 승격 시점에 재삽입이 일어나지만, SIEVE는 히트에서도 축출에서도 객체를 옮기지 않습니다. 손가락 포인터가 꼬리에서 머리 방향으로 이동하며 방문 비트가 선 객체는 비트만 초기화하고 지나갑니다.

이 구조가 quick demotion을 만드는 지점은 삽입 위치입니다. 신규 객체는 항상 머리에 들어가고 포인터는 그보다 뒤쪽을 훑으므로, 한 번도 재접근되지 않은 신규 객체는 포인터가 도달하는 즉시 제거됩니다.

평가는 콘텐츠 전송 네트워크(Content Delivery Network, CDN) 트레이스로 수행했습니다. SIEVE는 FIFO 대비 평균 21% 낮은 미스율을 보였고, 상위 10% 트레이스에서는 42% 이상 낮췄습니다. 16스레드에서 LRU, TwoQ 대비 처리량은 2배를 넘었습니다.

구조가 작은 덕분에 groupcache, lru-rs, lru-dict, mnemonist 등 5개 오픈소스 캐시 라이브러리에 평균 20줄 미만 변경으로 이식됐습니다. 각각 Go, Rust, Python과 C, JavaScript 구현이며 Google, VMware, Redpanda가 채택했습니다.

남은 병목은 큐 자체

S3-FIFO와 SIEVE는 히트 경로에서 락을 걷어냈지만 큐는 여전히 공유 자료구조입니다. 다수 스레드가 동시에 삽입하고 제거하면 큐의 머리와 꼬리에서 경합이 다시 생깁니다. 히트율 문제를 푼 자리에 처리량 문제가 남은 셈입니다.

Mobius(SIGMETRICS 2025, Dong, Wang, Jiang, Feng)는 이 지점을 정면으로 다룹니다. 캐시 항목을 두 개의 lock-free FIFO 큐로 관리해 삽입과 제거가 잠금 없이 동시에 실행되게 합니다. lock-free는 어떤 스레드가 멈춰도 다른 스레드가 계속 진행할 수 있도록, 잠금 대신 원자적 명령으로 공유 상태를 갱신하는 설계를 뜻합니다.

축출 절차도 함께 손봤습니다. 제거 한 번에 여러 차례 일어나던 상태 변경을 consecutive detection 메커니즘으로 하나의 원자적 연산에 묶어 데이터 레이스를 줄입니다. 상태 변경 횟수가 줄면 다른 스레드와 부딪힐 창도 같이 줄어듭니다.

합성 워크로드와 실제 고동시성 클러스터 워크로드 평가에서 Mobius는 기존 최고 수준 기법 대비 1.2배에서 8.5배의 동시 처리량 향상을 보였습니다. 지연 시간은 더 낮았고 히트율은 비슷한 수준을 유지했습니다. CacheLib과 RocksDB에 실제로 구현해 검증한 점이 연구용 프로토타입과 다릅니다.

세 알고리즘은 서로 경쟁하기보다 최적화 축이 다릅니다. S3-FIFO와 SIEVE가 무엇을 지울지 정확하게 만들었다면, Mobius는 그 결정을 여러 스레드가 동시에 내릴 때의 비용을 낮췄습니다.

두 축 사이의 선택 기준

미스율과 처리량은 같이 움직이지 않습니다. 미스율이 1% 낮아지면 백엔드 요청이 줄지만, 캐시 자체의 처리량이 절반으로 떨어지면 그 이득이 사라질 수 있습니다. 어느 쪽이 병목인지부터 재는 것이 순서입니다.

미스 한 번의 비용이 큰 환경에서는 미스율이 우선입니다. 원본이 원격 저장소나 데이터베이스라면 미스 하나가 밀리초 단위 지연을 만들고, 캐시 내부 연산 비용은 그에 비해 무시할 만합니다. 이 경우 S3-FIFO와 SIEVE의 낮은 미스율이 그대로 응답 시간으로 바뀝니다.

반대로 미스 비용이 작고 요청 빈도가 아주 높으면 처리량이 우선입니다. 메모리 안에서 끝나는 인메모리 캐시나 스토리지 엔진의 블록 캐시가 여기 해당하며, 코어 수가 많을수록 락 경합이 전체 지연을 지배합니다. Mobius가 CacheLib과 RocksDB에서 검증한 것도 이 계열의 워크로드입니다.

도입 비용도 판단에 들어갑니다. SIEVE는 5개 오픈소스 라이브러리에 평균 20줄 미만 변경으로 들어갔지만, lock-free 자료구조는 메모리 회수와 재시도 경로까지 직접 다뤄야 합니다. 이미 쓰는 캐시 라이브러리가 SIEVE를 지원한다면 그쪽이 먼저입니다.

FIFO의 전제가 깨지는 워크로드

여기까지의 알고리즘은 모두 같은 가정 위에 서 있습니다. 짧은 시간 창 안에 시간적 지역성(temporal locality)이 있고, 접근이 소수의 인기 객체에 몰린다는 가정입니다. 신규 객체를 빠르게 강등하는 quick demotion은 이 가정이 맞을 때만 이득입니다.

SOLAR 연구(2026, arXiv:2607.00394)는 이 가정이 깨지는 사례를 보고합니다. 대상은 대규모 언어 모델(Large Language Model, LLM) 에이전트의 의미론적 검색 버퍼(semantic retrieval buffer)입니다. 시간적 지역성도 빈도 집중도 없는 접근 패턴을 가진 워크로드입니다. 이런 환경에서는 정교하게 다듬은 정책이 LRU, LFU보다, 나아가 단순 FIFO보다도 낮은 성능을 낼 수 있다는 것입니다.

SOLAR가 제시한 대안은 언제 교체할지와 무엇을 남길지를 분리하는 것입니다. 교체 시점은 후회 누적(regret accumulation)으로 정하고, 남길 콘텐츠는 베이지안 온라인 학습으로 고릅니다. 타이트한 캐시 크기에서 FIFO 대비 5~75%의 상대 개선을 보고했습니다.

이 결과가 S3-FIFO나 SIEVE를 부정하지는 않습니다. 웹 캐시, CDN, 스토리지 블록 캐시처럼 시간적 지역성이 뚜렷한 워크로드가 여전히 다수이고, 세 알고리즘의 평가도 그런 트레이스 위에서 이뤄졌습니다. 다만 임베딩 유사도로 접근 패턴이 결정되는 캐시라면 도입 전에 자기 트레이스로 재현 실험을 하는 편이 안전합니다.

정리

캐시 축출 알고리즘의 최근 흐름은 두 단계로 나뉩니다. S3-FIFO와 SIEVE는 lazy promotion과 quick demotion으로 한 번만 쓰이는 객체를 걸러 LRU보다 낮은 미스율을 냈습니다. 히트 경로에서 공유 리스트를 건드리지 않아 락 경합도 함께 줄였습니다. Mobius는 그다음 병목인 큐 자체를 lock-free로 바꿔 기존 최고 수준 대비 1.2배에서 8.5배의 동시 처리량을 보고했습니다.

선택 기준은 미스 한 번의 비용입니다. 원본 접근이 비싸면 미스율을 먼저 보고, 캐시 내부 연산이 지연을 지배하면 처리량을 먼저 봅니다. 다만 세 알고리즘 모두 시간적 지역성을 전제하므로, SOLAR가 지적한 의미론적 검색 버퍼 같은 워크로드에서는 자기 트레이스로 먼저 재현해 봐야 합니다.