Optimal Probabilistic Cache Stampede Prevention

캐시 스템피드는 캐시가 만료되었을 때 여러 요청이 동일한 캐시 항목을 갱신하기 위해 처리를 진행하는 현상이다. 이 포스트에서는 캐시 스템피드 문제를 완화 하기 위한 기존 전략들과 논문에서 공개된 전략들을 살펴본다.

캐시 스템피드는 데이터베이스와 웹 서버의 성능을 심각하게 저하시킨다. 캐시 누락이 확인된 모든 요청들은 잠재적으로 많은 비용이 드는 계산을 진행해 항목을 재계산한다. 여기서 발생할 수 있는 문제는 동일한 캐시 항목을 여러 번 다시 계산하기 때문에 낭비가 발생한다. 이 문제를 완화하는 방법은 크게 3가지 범주로 분류된다.

Locking

동일한 값을 여러 번 동시에 다시 계산하는 것을 방지하기 위해 캐시 미스가 발생하면 프로세스는 해당 캐시 키에 대한 잠금을 획득하려고 시도하고, 획득한 프로세스만 재계산을 한다. 잠금이 획득 되지 않은 경우에는 다양한 옵션을 통해 처리한다.

• 값이 다시 계산될 때 까지 대기
• “찾을 수 없음”을 반환하고 클라이언트에서 적절히 처리하도록 기대
• 새 값이 다시 계산되는 동안 사용할 수 있도록 오래된 항목을 캐시에 보관

이 방식은 잠금을 위한 추가 쓰기 연산을 진행해야 하는 것 외에도 잠금을 획득한 프로세스의 실패, 잠금의 수명 주기 제어, 경합 조건 등 다양한 엣지 케이스를 처리해야 하는 단점이 있다.

External recomputation

이 솔루션은 캐시 값의 재계산을 캐시 값이 필요한 프로세스에서 외부 프로세스로 이동시킨다. 외부 프로세스의 재계산은 다양한 방식으로 트리거될 수 있다.

• 캐시 값이 만료에 가까워 질 때
• 주기적으로
• 해당 값을 필요로하는 프로세스에 캐시 누락이 발생할 때

이 접근 방식은 유지 관리 및 모니터링 해야 하는 외부 프로세스가 추가로 생성된다. 또한 이 솔루션은 부자연스러운 코드 분리 / 중복이 생성되며 주기적으로 재계산할 항목과 시기를 추적해야 하므로 관리에 어려움이 생긴다. 또한 이런 백그라운드 프로세스는 요청되지 않은 캐시 항목도 재생성할 수 있으므로 일부 환경에서는 불필요한 연산이 발생한다.

Probablistic Early Recomputation

위 논문에서 공개된 확률론 조기 갱신 방식은 각 프로세스가 독립적인 확률적 결정을 내려 캐시 값이 만료되기 전에 캐시 값을 재계산할 수 있으며, ttl 만료에 가까워질수록 재계산을 수행할 확률을 증가시킨다. 각 프로세스가 독립적으로 확률적 결정을 내리기 때문에 동시에 만료되는 프로세스의 수가 줄어들어 스탬피드 효과가 완화된다.

지수 분포에 기반한 이 솔루션은 스탬피드를 방지하는 효과와 조기 재계산의 효율성 측면에서 좋은 효과를 보이는 것으로 나타난다.

function XFetch(key, ttl; β = 1)
	value, ∆, expiry ← CacheRead(key)
	if !value or Time() − ∆β log(rand()) ≥ expiry then
		start ← Time()
		value ← RecomputeValue()
		∆ ← Time() – start
		CacheWrite(key, (value, ∆), ttl)
	end
	return value
end

논문에서 공개한 내용에 의하면 delta 값은 재계산을 하는데 걸리는 시간을 나타내며 확률 분포의 크기를 적절히 조율하는데 사용된다. 또한 beta 값은 1을 기준으로 더 큰 값을 설정하면 초기 재계산이 수행될 확률을 높이게 되어 스템피드를 더욱 줄일 수 있지만, 1로 설정하는 것 만으로도 부하를 줄일 수 있음을 스트레스 테스트로 확인했다.

위 방식은 확률 분포에 기반한 초기 재계산이라는 테크닉을 통해 캐시 스템피드를 효과적으로 완화시킨다. 아래는 스트레스 테스트를 진행한 결과다.

• key size : 100KB
• vuser : 1000

Read Through

PER Algorithm

Large key를 대상으로 JVM 웜업만 진행하고 별 다른 튜닝 없이 5분간 스트레스 테스트를 지속했다. PER 알고리즘을 기반으로 한 테스트는 널리 사용되는 캐시 전략인 read through 패턴대비 약 80%의 재계산에 대한 부하가 감소했음을 확인할 수 있었다.