캐시 스탬피드

자주 읽히는 캐시 값이 만료되는 순간, 그 값을 찾던 요청이 한꺼번에 원본으로 몰리는 일입니다. 평소에는 캐시가 대신 답해 주므로 원본은 한가합니다. 몰린 요청은 저마다 같은 값을 다시 만듭니다.

상세

캐시 미스를 다루는 흔한 패턴에서 나옵니다. 요청 하나가 캐시를 읽어 보고, 없으면 값을 다시 만들어 캐시에 넣습니다. VLDB(Very Large Data Bases, 초대형 데이터베이스 학회) 논문은 이 패턴의 결함을 이렇게 적습니다. 여러 요청이 같은 미스를 동시에 볼 수 있고, 그러면 저마다 값이 비싼 계산을 돌려 같은 항목을 다시 만든다는 것입니다.

평소에 안 보이는 이유는 캐시가 잘 맞기 때문입니다. Symfony 문서가 든 예가 이 대비를 그대로 보여 줍니다. 어떤 애플리케이션이 데이터를 계산하는 데 5초가 걸리고 그 데이터를 1시간 캐시하며 초당 10회 접근한다면, 대부분은 캐시 히트라서 아무 문제가 없습니다. 1시간이 지나면 차가워진 캐시로 새 요청 10개가 들어옵니다. 그래서 데이터를 다시 계산합니다. 다음 초에도 같은 일이 벌어집니다. 캐시가 다시 따뜻해질 때까지 데이터가 약 50번 계산됩니다.

같은 항목을 여러 번 다시 만드는 것은 낭비로 끝나지 않습니다. VLDB 논문은 이것이 시스템 과부하나 데이터베이스 지연으로 이어지는 일이 잦다고 적습니다. 애초에 그 항목을 캐시한 이유가 바로 그것이라는 말도 함께 적습니다. memcached 위키는 인기 있고 다시 만들기 어려운 캐시 항목에서 수십, 수백 개의 프로세스가 캐시를 채우려고 동시에 데이터베이스를 때리게 될 수 있다고 적습니다.

되먹임이 붙습니다. VLDB 논문은 이 현상을 연쇄 장애라고 부르는 일이 잦다고 적습니다. 동시 재계산이 시스템을 짓눌러 각 재계산에 걸리는 시간을 늘리고, 그 때문에 더 많은 요청이 스탬피드에 끼게 됩니다.

이름이 여럿입니다. VLDB 논문은 이 문제를 dog-piling, cache miss storm, cache choking 이라고도 부른다고 적습니다. memcached 위키는 stampeding herd, groupcache README 는 thundering herd, Rails 는 dog pile effect 라는 이름을 씁니다.

발생 조건

flowchart TD
    A["같은 캐시 키를 여럿이 읽는다"] --> B{"그 키가 만료됐나"}
    B -- 아니오 --> C["캐시가 답한다"]
    B -- 예 --> D["미스한 요청이 저마다 원본으로 간다"]
    D --> E{"재계산이 끝나기 전에 또 미스가 나나"}
    E -- 아니오 --> F["한 번만 다시 만든다"]
    E -- 예 --> G["재계산이 겹친다"]

네 가지가 함께 서야 합니다.

첫째, 캐시 키 하나가 인기 있어야 합니다. VLDB 논문은 인기 있는 캐시 항목이 만료될 때 일어나는 상황이라고 적습니다. Cloudflare 문서도 같은 자산에 대한 여러 요청이 한 데이터센터에 동시에 도착하는 경우로 적습니다.

둘째, 그 항목에 만료가 있어야 합니다. Symfony 문서는 beta 파라미터가 캐시 항목에 만료가 정의돼 있을 때만 효과가 있다고 못 박습니다. 만료가 없으면 다시 만들 시점 자체가 없습니다.

셋째, 미스를 본 요청이 저마다 원본으로 가야 합니다. VLDB 논문의 Figure 1 이 그 최소 패턴입니다. CacheRead 로 읽고, 값이 없으면 RecomputeValue 를 돌리고, CacheWrite 로 씁니다. 그 사이를 막는 것이 아무것도 없습니다.

넷째, 재계산 시간이 요청 간격보다 길어야 합니다. VLDB 논문은 미스를 보는 요청의 수가 요청률만이 아니라 항목을 다시 만드는 데 드는 시간에도 달렸다고 적습니다. 캐시 항목이 초당 10회 접근되고 재계산에 3초가 걸리면 30개 요청이 그 항목을 다시 만듭니다.

조건 하나가 빠지면 달라집니다. 키가 서로 다르면 이 일이 아닙니다. 세는 단위가 키이기 때문입니다. nginx 의 락은 proxy_cache_key 로 식별되는 새 캐시 항목 하나를 기준으로 걸리고, Symfony 의 락은 특정 키 하나를 호스트마다 한 번에 한 프로세스만 계산하게 하며, Cloudflare 의 캐시 락은 한 위치에서 주어진 자산 하나에 대해 걸립니다. 재계산이 짧으면 겹치는 요청의 수가 줄어듭니다. 위 계산식에서 3초 자리가 작아지면 30이라는 수가 그만큼 작아집니다. 만료가 없으면 셋째 조건에 닿기 전에 멈춥니다.

예시

nginx 의 proxy_cache_lock

proxy_cache_lock off;
proxy_cache_lock_age 5s;
proxy_cache_lock_timeout 5s;

proxy_cache_lock 의 기본값은 off 입니다. 켜면 proxy_cache_key 로 식별되는 새 캐시 항목 하나를 채우기 위해 프록시된 서버로 나가는 요청이 한 번에 하나로 제한됩니다. 같은 캐시 항목에 대한 나머지 요청은 응답이 캐시에 나타나거나 그 항목의 캐시 락이 풀릴 때까지 기다립니다. 기다리는 상한은 proxy_cache_lock_timeout 이고 기본값은 5초입니다. 이 시간이 지나면 요청이 프록시된 서버로 넘어가지만 그 응답은 캐시되지 않습니다. proxy_cache_lock_age 의 기본값도 5초입니다. 새 캐시 항목을 채우려고 마지막으로 넘긴 요청이 이 시간 안에 끝나지 않으면 요청이 하나 더 프록시된 서버로 넘어갈 수 있습니다. nginx 문서는 새 캐시 항목을 채울 때 프록시된 서버로 가는 접근 횟수를 최소화하는 데 proxy_cache_lock 을 쓸 수 있다고 적습니다.

Rails 의 race_condition_ttl

cache = ActiveSupport::Cache::MemoryStore.new(expires_in: 1)
cache.write("foo", "original value")
sleep 1

t1 = Thread.new do
  val_1 = cache.fetch("foo", race_condition_ttl: 2) do
    sleep 1
    "new value 1"
  end
end

sleep 0.1
val_2 = cache.fetch("foo", race_condition_ttl: 2) do
  "new value 2"
end

Rails API 문서에 실린 예제입니다. 모든 값이 1초 뒤 만료되고, 두 갈래가 만료 직후 같은 키 "foo" 를 읽습니다. 두 번째 갈래는 첫 번째가 만료를 늘린 뒤 0.1초 만에 들어옵니다. 문서는 결과를 val_1 이 "new value 1", val_2 가 "original value" 라고 적습니다. 두 번째 블록은 실행되지 않습니다. :race_condition_ttl 은 만료된 값을 새 값이 만들어지는 동안 몇 초나 더 쓸 수 있는지를 정하는 옵션입니다. Rails 문서는 이것을 캐시 항목이 만료될 때의 경쟁 조건을 막는 데 쓸 수 있다고 적고, 여러 프로세스가 같은 항목을 동시에 다시 만드는 것을 막는 일이며 dog pile effect 라고도 알려져 있다고 적습니다.

Symfony 의 Cache Contracts

$beta = 1.0;
$value = $cache->get('my_cache_key', function (ItemInterface $item): string {
    $item->expiresAfter(3600);

    return '...';
}, $beta);

get() 의 첫 인자가 키이고 둘째 인자는 키가 캐시에 없을 때 실행되는 콜백입니다. 콜백은 캐시 미스에서만 실행됩니다. 셋째 인자 $beta 는 실수값이고 기본값은 1.0 입니다. 값이 클수록 더 일찍 다시 계산합니다. 0 으로 두면 조기 재계산이 꺼지고, INF 로 두면 즉시 재계산을 강제합니다. 콜백 안에서 isHit() 을 부를 수 있습니다. 참을 돌려주면 그 값이 스탬피드 방지 때문에 만료 시점보다 앞당겨 다시 계산되는 중이라는 뜻입니다. Symfony 문서는 스탬피드 방지가 Cache Contracts 에만 적용된다고 적습니다. getItem() · save() 같은 PSR-6 메서드를 쓸 때는 애플리케이션을 캐시 스탬피드로부터 직접 보호해야 합니다.

동작

sequenceDiagram
    participant 요청들
    participant 캐시
    participant 원본
    요청들->>캐시: 키 읽기
    캐시-->>요청들: 미스
    요청들->>원본: 저마다 다시 만들기
    원본-->>요청들: 값
    요청들->>캐시: 저마다 쓰기

VLDB 논문의 Figure 1 이 이 순서를 의사코드로 적습니다. CacheRead(key) 로 값을 읽습니다. 값이 없으면 RecomputeValue() 를 부릅니다. 이 호출은 대개 값이 비쌉니다. 그 결과를 CacheWrite(key, value, ttl) 로 씁니다. 쓰고 나면 그 키는 ttl 시간만큼 캐시에 남아 있다가 만료됩니다. 마지막으로 값을 돌려줍니다.

단계가 한 요청 안에서는 어긋나지 않습니다. 어긋나는 자리는 같은 단계를 여럿이 동시에 밟을 때입니다. 읽기와 쓰기 사이에 재계산이 끼어 있고, 그동안 캐시에는 아무 값도 없습니다. 그 구간에 도착한 요청은 전부 미스를 보고 같은 재계산으로 들어갑니다.

요청 합치기

한 요청만 원본으로 보내고 나머지에 같은 값을 나눠 주는 방식이 여러 자리에 있습니다. Cloudflare 는 이것을 request collapsing 이라고 부릅니다. 첫 요청만 오리진으로 전달되고, 나머지 요청은 첫 요청이 끝나기를 기다렸다가 그 응답을 함께 받습니다. groupcache 는 복제된 프로세스 전체에서 한 프로세스의 적재 하나만 캐시를 채우고 그 값을 모든 호출자에게 다중화합니다. 같은 프로세스 안에서 오든 피어의 RPC 로 오든 다른 호출자들은 적재가 끝날 때까지 블록되었다가 같은 답을 받습니다. memcached 위키는 gearmand 를 예로 듭니다. 같은 파라미터로 들어온 작업을 합쳐, 먼저 작업을 낸 프로세스가 워커를 받고 그 뒤의 프로세스들은 그 결과를 구독합니다. 첫 작업이 끝나면 gearmand 가 응답을 모든 청취자에게 방송합니다.

경계

epoll 이 말하는 thundering herd 도 캐시 스탬피드인가. 아닙니다.

epoll(7) 은 여러 스레드나 프로세스가 같은 epoll 파일 디스크립터에서 epoll_wait(2) 로 블록된 상황을 설명하면서 이 이름을 씁니다. 관심 목록의 파일 디스크립터가 에지 트리거 알림으로 표시돼 있으면 그중 한 스레드만 깨어납니다. 문서는 이것이 어떤 시나리오에서 thundering herd 깨우기를 피하는 데 쓸모 있는 최적화라고 적습니다. epoll_ctl(2) 의 EPOLLEXCLUSIVE 플래그도 어떤 시나리오에서 thundering herd 문제를 피하는 데 쓸모 있다고 적습니다. 이 자리에는 캐시 항목도 만료도 미스도 없습니다. 발생 조건의 첫 칸부터 성립하지 않습니다.

같은 이름이 캐시 쪽에서도 쓰입니다. groupcache README 는 memcached 가 캐시 미스라고 알려 주는 데 그쳐 수가 정해지지 않은 클라이언트에서 데이터베이스 적재의 thundering herd 가 일어나는 일이 잦고 그 결과로 몇 번의 장애가 있었다고 적습니다. 이쪽은 이 표제어가 맞습니다. 캐시 항목과 미스가 조건에 들어 있습니다. 이름이 겹치는 것이지 같은 자리가 아닙니다.

관련 항목

발생 조건을 이루는 개념

캐시 키 · 캐시 미스 · 캐시 히트 · ttl · 경쟁 조건

이 문제가 보고되는 캐싱 소프트웨어

nginx · Symfony · Rails · memcached · groupcache · Cloudflare

이것을 막는 대응 기법

락 · 조기 재계산 · request collapsing

대응 기법을 실제로 구현한 설정·도구

proxy_cache_lock · proxy_cache_key · race_condition_ttl · Cache Contracts · gearmand

이 문제가 낳는 장애 결과

연쇄 장애 · 지연 · 과부하

재계산 요청이 몰리는 지점

오리진 · 데이터베이스 · 프록시

재현에 관여하는 실행·통신 단위

프로세스 · 스레드 · RPC

이름이 겹치는 캐시 밖 개념

epoll · 에지 트리거 · 파일 디스크립터 · epoll_wait · epoll_ctl · EPOLLEXCLUSIVE