Cache Stampede을 대응하는 최후의 수단 중 하나, Request Collapsing

Cache Stampede

Cache Stampede(또는 Thundering Herd)는 읽기 요청이 몰리는 특정 Resource(또는 Reosurce Collection)을 Cache에 저장하고 Look Aside 전략을 사용하고 있는 상황에서 Cache Server에서 어떠한 사유로 인해 Cache Miss가 발생하였을 때 SSoT(Single Source Of Truth, 여기서는 DBMS, Upstream API 등을 의미)로 다량의 요청이 동시에 몰려 심한 경우 일정 시간 장애도 발생시키는 위험한 상황을 의미합니다.

 

여기서 어떠한 사유란 다른 글에서 자주 언급하는 Cache의 TTL 만료를 대표적인 예로 들 수 있으나, 잘못된 만료 정책 설정, Global Cache Server를 사용하는 경우에 Cache를 조회하는 Server(Edge, Downstream API)와 Global Cache Server 간의 네트워크 순단으로 인한 Cache Miss 또는 Global Cache Server 장애로 인한 요청 처리 불가(또는 복구는 되었으나 Cache가 메모리에서 유실된 경우) 상태도 포함될 수 있습니다.

 

네트워크 순단으로 인한 Cache Miss나 장애로 인한 메모리 내에서의 Cache 유실은 (TTL 만료에 비해) 흔한 상황이 아니지만 대표적인 대응책으로 언급되는 Pre-Warming이나 PER(Probablistic Early Recomputation)으로는 대응할 수 없는 영역의 문제입니다.

PER 알고리즘은 Cache가 만료되기 전, 지수 분포(Exponential Distribution)를 바탕으로 TTL을 재 계산하여 Cache의 TTL을 연장하는 알고리즘입니다.

해당 알고리즘은 다음의 공식을 사용하고 있는데
currentTime−(Δ×β×log(rand()))≥expiryTime
이를 살펴보면 고정적인 TTL에 대비하여 Cache의 남은 TTL과 해당 Cache를 계산하는데 걸리는 시간(Δ), 가중치 상수 (β), rand 함수를 이용해 요청을 통해 확률적으로 TTL을 연장되도록 하는 것임을 확인할 수 있습니다.

 

이러한 상황이 발생했을 때 어떻게 대응할 수 있을까요? 이때 Request Collapsing 기법을 고민해 볼 수 있습니다.

 

 

Request Collapsing

Request Collapsing이란 말 그대로 동일한 Resource에 대해 동시에 접근하는 요청들을 병합하여 실제 SSoT에 도달하는 요청 수를 최소화하는 기법입니다. 해당 기법을 사용하는 대표적인 서비스로는 Discord(Data Service)가 있으며, HTTP Rever Proxy 중 하나인 Varnish Cache에서도 이를 제공하고 있습니다. 이 기법을 실제 구현 래밸에서 분석하고 싶다면 각 언어의 GraphQL DataLoader 구현체, Golang의 singleflight, 유지 관리 중인 (사실상 방치된) Netflix Hystrix의 HystrixCollapser를 살펴 보실 수 있습니다.

 

Request Collapsing를 구현하는 것은 생각보다 간단합니다. 각 Resource 별로 Unique Key를 할당하고 (e.g. identifier), Atomic 한 Map을 통해 해당하는 Key가 이미 in-flight(접근 중인)인지 확인하며 맞다면 Lock 등을 이용해 접근을 막는 형태로 구현하면 됩니다. (이때 Map은 Local Memory 위에 올려둘 수 있습니다.)

 

Kotlin의 Coroutine을 이용해서는 다음과 같이 간단하게 구현해볼 수 있습니다.

class RequestCollapser<K, V>(
    private val coroutineScope: CoroutineScope,
) {
    private val calls = ConcurrentHashMap<K, Deferred<V>>()

    suspend fun execute(key: K, block: suspend () -> V): V {
        val deferred = calls.computeIfAbsent(key) {
            coroutineScope.async {
                try {
                    block()
                } finally {
                    calls.remove(key)
                }
            }
        }

        return deferred.await()
    }
}

 

이러한 RequestCollapser는 중복된 요청을 최소화함으로써 SSoT가 받는 부하를 획기적으로 감소시킬 수 있습니다. 실제 운영 중인 서비스 내에 도입했을 때 (동일한 코드는 아니지만) 실제 요청 수 대비하여 90%가량의 요청이 SSoT에 접근하지 않고 대기한 뒤 동일한 결과를 받는 것을 확인할 수 있었습니다.

(그렇다고 막무가내로 이를 도입하는 것은 지양하시길 바랍니다. 최소한 각 Server 별로 트래픽 기준 같은 시간동안 대기하는 스레드의 수를 고려해 메모리 사용량을 검토할 필요가 있고, 철저한 성능 테스트가 필요합니다.)

 

이번 글을 통해 가볍게 Request Collapsing 기법에 대해서 다루어보았습니다. 오랜만에 글을 작성하다보니 힘을 빼고 가볍게 작성해 보았는데 어떤 느낌일지 아직 잘 모르겠네요. ㅎㅎ

 

좀 더 자세한 내용은 아래의 링크를 참고하시길 바랍니다.

 

Reference

• https://en.wikipedia.org/wiki/Single_source_of_truth
• https://en.wikipedia.org/wiki/Cache_stampede
• https://discord.com/blog/how-discord-stores-trillions-of-messages