Thundering Herd, Cache Stampede의 관계와 PER 알고리즘

Thundering Herd

특정 이벤트가 발생했을 때, 대기하던 수많은 프로세스나 스레드가 한꺼번에 깨어나 자원을 점유하려고 몰리는 현상

웹 서브의 accept 큐, API 재시도, 서버 재시작 등 다양한 시나리오에서 발생

Cache Stampede (캐시 스탬피드)

• 캐시 데이터가 만료된 직후 다수의 요청이 동시에 백엔드를 호출해 과부화가 발생하는 것
• Thundering Herd 현상이 캐시환경에서 나타나는 구체적인 사례
• 캐시 TTL 만료에 특화

발생 매커니즘

1. 데이터 캐시 저장 : 인기가 많은 데이터가 캐시에 저장됨
2. 캐시 만료 : 설정된 TTL(유효 기간)이 다 되어 캐시에서 데이터가 삭제됨
3. 동시 요청 : 그 순간 많은 양의 조회 요청이 들어옴
4. 폭주 : 캐시에 데이터가 없으므로, 많은 양의 요청이 동시에 DB로 직접 쿼리를 날림
5. 시스템 부하 : DB 부하로 인해, 시스템이 느려짐

Thundering Herd와의 관계

Thundering Herd는 사실상 Cache Stampede의 상위 개념으로 보면됨

Cache Stampede 완화 방법

• 분산 락 : 캐시 미스 발생 시, 한 명만 DB에 접근할 수 있도록 Lock을 검
• 백그라운드 갱신 : TTL을 두지 않거나 매우 길게 잡고, 별도 Batch 프로세스가 주기적으로 캐시 최신화하여 만료되는 순간 자체를 없앰
• TTL 지터(Jitter) : TTL에 랜덤 오프셋을 추가해 만료 시간을 분산 -> 모든 키가 동시에 만료되지 않아 확률이 낮아짐
• PER : 캐시 완전히 갱신 전, 확률적으로 일부 요청이 미래 캐시를 갱신하게 만드는 알고리즘

PER 알고리즘

PER (Probabilistic Early Recomputation) 알고리즘의 핵심 아이디어는
캐시가 만료되기 직전, 누군가 한 명 만 미리 갱신하게 하자는 것

수학적 공식

$currentTime - (recomputeTime \times \beta \times \log(random())) > expiryTime$

• $currentTime$ : 현재 시간
• $recomputeTime$ : 캐시를 다시 계산하는 데 걸리는 평균 시간, 캐시에 저장해야 PER 결정 가능
• $\beta$ : 알고리즘 민감도 조절 가중 치
• $log(random())$ : 0과 1사이 부동 소수점 난수
• $expiryTime$ : 캐시가 실제로 만료되는 시간

$log(random())$ 이유

$log(random())$은 음수 값을 가지며, random값이 0에 가까울수록 큰 음수가 됨
-> 아직 많이 남았더라도 아주 낮은 확률로 갱신이 일어날 수 있음
=> 만료 시간에 가까워질수록 갱신 조건이 충족될 확률이 기아급수적으로 높아짐

PER 알고리즘 장점

• Race Condition 방지 : 명시적인 Lock을 걸지 않고도 단 한 명의 사용자만 갱신을 수행하게 유도할 수 있음
• 지연 시간 없음 : Lock 방식은 지연 시간이 발생하지만, PER은 갱신 당첨자가 아닌 사람들은 즉시 기존 캐시를 받음
• 유연성 : $\beta$값을 조정하여 트래픽 양, 데이터 중요도에 따라 갱신 타이밍 튜닝 가능

PER 알고리즘 단점

• 트래픽이 적을 떄 효과 미미
• 재계산 횟수 증가 => $\beta$로 조정 가능

PER 알고리즘 동작 프로세스

1. 사용자가 캐시에 접근
2. 현재 시점이 확률적 갱신 구간에 들어왔는지 계산
3. 구간 내 -> 난수 생성하여 특정 조건 부합 시, 캐시 만료되지 않았어도 DB로 부터 새로 읽어 캐시 갱신
4. 조건에 맞지 않으면 기존 캐시 데이터 반환

수천 개의 요청 중 단 한 개의 요청이 갱신을 수행하게 되고,
그 직후 요청은 갱신된 새로운 캐시를 보게되므로 DB 부하가 줄어듦