LRU를 대체하는 FIFO 캐시 축출

캐시 축출 연구는 제거할 항목의 선택과 여러 스레드의 동시 처리 비용을 함께 다룹니다.

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

LRU(Least Recently Used)는 가장 오래 참조되지 않은 항목을 제거합니다. 항목에 접근할 때마다 해당 객체를 연결 리스트의 머리로 옮깁니다. 모든 스레드가 이 리스트를 공유하므로 캐시 히트에도 공유 구조의 쓰기 잠금이 필요합니다. 조회는 읽기지만 메타데이터 갱신은 쓰기이므로 병목이 생깁니다.

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

FIFO(First In First Out) 계열인 S3-FIFO와 SIEVE는 큐 재배치를 축출 시점까지 미룹니다. 히트 시에는 객체별 공유 메타데이터인 원자적 카운터나 방문 비트를 갱신합니다. 연결 리스트 재배치에 필요한 락을 줄이는 것이며, 공유 상태 쓰기가 전부 사라지는 것은 아닙니다.

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

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

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

신규 객체를 작은 임시 큐에 먼저 넣어 재접근 여부를 확인합니다. S3-FIFO는 크기가 고정된 세 개의 FIFO 큐로 캐시를 나눕니다.

논문 설정은 Small에 캐시 공간의 10%, Main에 90%를 배분합니다. Small에서 축출할 때 접근 카운터가 1보다 크면 Main으로 승격하고, 그렇지 않으면 Ghost에 키를 남깁니다. 이 비율과 기준의 효과는 워크로드에 따라 달라집니다.

flowchart LR
    NEW[신규 객체] --> S[Small 큐<br/>캐시 공간 10%]
    S -->|접근 카운터 1 초과| M[Main 큐<br/>캐시 공간 90%]
    S -->|접근 카운터 1 이하| G[Ghost 큐<br/>키만 보관]
    G -->|다시 요청됨| M
    M -->|재접근 후 꼬리 도달| M
    M -->|재접근 없이 꼬리 도달| OUT[캐시에서 제거]

Ghost는 객체 내용 대신 키나 지문을 저장하지만, 항목과 인덱스의 메모리 비용은 남습니다. 제거된 키가 다시 요청될 때 Ghost에 있으면 Main으로 바로 넣습니다. 객체 내용을 중복 보관하지 않고도 축출 후 재접근을 알아냅니다.

Lazy promotion은 Main 큐 안에서 동작합니다. 재접근된 객체를 즉시 머리로 옮기지 않고, 제거 대상이 되는 큐 꼬리에 도달했을 때 재삽입(reinsertion)합니다. 승격을 매 히트 대신 축출 시점에 수행하므로 히트 처리 비용이 줄어듭니다.

논문은 14개 데이터셋의 6,594개 트레이스로 평가했습니다. 캐시 크기를 트레이스 내 고유 객체 수의 10%로 정한 조건에서 데이터셋별 결과는 다음과 같습니다.

평가한 트레이스 전반에서 효과를 보였지만, 개별 워크로드마다 항상 가장 낮은 미스율을 보장하는 수치는 아닙니다.

큐 하나와 hand 포인터로 줄인 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는 히트나 축출 때 객체를 옮기지 않습니다. hand 포인터는 꼬리에서 머리 방향으로 이동합니다. 방문 비트가 설정된 객체를 만나면 비트만 초기화하고 다음 객체로 이동합니다.

신규 객체의 삽입 위치가 quick demotion을 가능하게 합니다. 새 객체는 항상 머리에 들어가고 포인터는 그 뒤쪽을 탐색합니다. 재접근되지 않은 새 객체는 포인터가 도달하면 바로 제거합니다.

SIEVE 논문은 CDN1 데이터셋의 큰 캐시 조건에서 FIFO 대비 평균 21% 미스율 감소를 보고합니다. 그중 상위 10% 트레이스의 감소폭은 42%를 넘습니다. 별도의 Meta 트레이스 실험에서는 16스레드 처리량이 최적화한 LRU와 TwoQ의 2배를 넘습니다.

저자들은 groupcache, lru-rs, lru-dict, mnemonist 등을 포함한 5개 운영용 캐시 라이브러리에 SIEVE를 이식했습니다. 변경량은 평균 20줄 미만입니다. 이는 이식 실험 결과이며 특정 회사의 SIEVE 운영 채택을 입증하는 수치는 아닙니다.

히트는 방문 비트에 재사용 여부를 기록합니다. 축출 탐색은 객체를 승격하지 않고 이 비트를 초기화합니다.

남은 병목은 큐 자체

S3-FIFO와 SIEVE는 히트 경로의 락을 줄였지만 큐는 여전히 공유합니다. 여러 스레드가 동시에 삽입하거나 제거하면 큐의 머리와 꼬리에서 경합이 발생합니다. 따라서 미스율을 개선해도 처리량 병목은 남을 수 있습니다.

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

Mobius는 축출 절차도 바꿉니다. Consecutive detection은 한 번의 제거에 필요한 여러 상태 변경을 하나의 원자적 연산으로 묶습니다. 상태 변경 횟수가 줄어 다른 스레드와 데이터 레이스가 발생할 기회도 줄어듭니다.

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

SOLAR는 교체 시점과 보관할 콘텐츠를 나누고, 후회 누적과 베이지안 온라인 학습으로 판단합니다. 작은 용량에서 FIFO 대비 5~75% 상대 개선을 보고합니다. 앞선 실험의 이진 히트·미스율이 아니라 연속적인 유사도로 평가하는 의미 검색 품질 결과입니다.

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

정리

S3-FIFO와 SIEVE는 큐 갱신을 미루고 재사용될 가능성이 낮은 객체를 걸러냅니다. Mobius는 lock-free 큐로 동시 삽입과 축출의 경합을 줄입니다.

미스율과 처리량을 함께 측정하고, 원본 접근 비용에 따라 어느 개선이 더 큰지 판단합니다. 특히 의미 유사도가 히트의 뜻을 바꾸는 캐시에서는 실제 워크로드를 재생해 도입 효과를 확인해야 합니다.