[성능 개선] Per 알고리즘을 사용해서 Cache Stampede 현상을 해결해보자

Per 알고리즘

Cache Stampede란?

여러개의 요청이 동시에 발생했을 때 cache가 비어있거나 만료되어있으면

데이터베이스로 요청이 몰려들 수 있는데 이런 현상을 cache stampede라고 한다.

 

Per(Probabilistic Early Recomputation) 알고리즘이란?

cache stampede를 해결하는 방법 중 하나로 확률 알고리즘을 사용해서

cache가 만료되기 전에 cache를 갱신하는 방법이다.

이 알고리즘을 사용하면 cache가 만료되는 시간이 다가올 수록 cache를 갱신할 확률이 높아지고

cache 갱신이 일괄적으로 이루어지지 않고 독립적으로 이루어진다.

 

아래는 per 알고리즘의 의사코드이다.

beta는 1보다 같거나 큰 값으로 cache를 더 일찍 갱신하고 싶은 경우 크게 설정하면 된다.

delta는 cache를 갱신하는데 걸리는 시간이다.

function x-fetch(key, ttl, beta=1) {
    value, delta, expiry ← cache_read(key)
    if (!value || (time() - delta * beta * log(rand(0,1))) ≥ expiry) {
        start ← time()
        value ← recompute_value()
        delta ← time() – start
        cache_write(key, (value, delta), ttl)
    }
    return value
}

 

Per 알고리즘 적용

적용하는 부분

게시글 중에서 댓글이 많이 달린 상위 5개의 게시글을 보여주는 기능이 있다. 조회할 때마다 댓글 개수를 계산해서 정렬하는 과정이 필요하고 쓰기보다는 읽기 요청이 많다고 생각해서 redis를 사용한 cache를 적용했다.

@Cacheable(value = ["top-commented-post"])
fun fetchTop5CommentedPost(): List<Post> {
    return postReader.findTop5ByCommentCount()
}

 

위 방식은 cache aside로 먼저 cache를 조회해서 hit일 경우 cache를 반환하고

miss일 경우 데이터베이스로부터 데이터를 가져오고 cache를 갱신한다.

요청이 몰리는 상황에서 redis에서 top-commented-post라는 key가 만료되는 경우

데이터베이스로 요청이 몰리는 경우가 발생할 수 있다.

 

구현

redis에 데이터를 저장할 때 cache 갱신 시간도 같이 저장하기 때문에 다음과 같은 data class를 만들었다.

data class PerCacheWrapper<T>(
    val data: T,
    val expiryGapMs: Long
)

 

AOP를 사용해서 per 알고리즘 로직을 적용했다.

런타임시 메서드에 적용할 annotation class와 aspect class를 통해서 부가기능 로직을 작성했다.

@Target(AnnotationTarget.FUNCTION)
@Retention(AnnotationRetention.RUNTIME)
annotation class PerCacheable(
    val key: String,
    val ttlSeconds: Long = 300,
    val beta: Double = 1.0
)

@Around("@annotation(perCacheable)")
fun handlePerCache(joinPoint: ProceedingJoinPoint, perCacheable: PerCacheable): Any? {
    val key = perCacheable.key
    val ttl = redisTemplate.getExpire(key, TimeUnit.MILLISECONDS)

    val cachedJson = redisTemplate.opsForValue().get(key) as? String
    if (cachedJson != null && ttl > 0) {
        val wrapperType = object : TypeReference<PerCacheWrapper<List<Post>>>() {}
        val wrapper = objectMapper.readValue(cachedJson, wrapperType)

        val gapScore = wrapper.expiryGapMs * perCacheable.beta * -ln(Random.nextDouble())
        if (gapScore < ttl) {
            return wrapper.data
        }
    }

    val start = System.nanoTime()
    val result = joinPoint.proceed()
    val duration = TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - start)
    val wrapper = PerCacheWrapper(result, duration)
    val json = objectMapper.writeValueAsString(wrapper)

    redisTemplate.opsForValue().set(
        key,
        json,
        perCacheable.ttlSeconds,
        TimeUnit.SECONDS
    )
    return result
}

 

테스트

1. 테스트 시나리오

가상 사용자

- 100명 ~ 150명

테스트 시간

- 20분

테스트 로직

- 댓글이 많은 상위 5개 게시물 조회 요청을 한다.

 

2. 모니터링 항목

RPS(초당 요청수)

- 부하 생성기인 locust를 사용하면서 수집된 지표를 사용하였다.

응답 시간

- 부하 생성기인 locust를 사용하면서 수집된 지표를 사용하였다.

slow query 발생 횟수

- 데이터베이스로 사용하고 있는 mysql에서 slow query 기준을 500ms로 설정했다. 

  mysqld-exporter에서 만들어주는 mysql_global_status_slow_queries 지표를 prometheus로 수집했다.

정렬 작업 횟수

- 정렬 작업이 얼마나 일어나는지 mysqld-exporter에서 만들어주는    

   mysql_global_status_sort_scan 지표를 prometheus로 수집했다.

조회 작업 횟수

- 조회 작업이 얼마나 일어나는지 mysqld-exporter에서 만들어주는

  mysql_global_status_select_scan 지표를 prometheus로 수집했다.

 

3. 결과

다음 2개의 그래프는 per 알고리즘을 적용하기 전 RPS와 응답 시간이다.

 

다음 2개의 그래프는 per 알고리즘을 적용 후 RPS와 응답 시간이다.

 

그 다음 prometheus로 수집한 slow query 발생횟수, 정렬 작업 횟수, 조회 작업 횟수이다.

아래와 같은 식으로 그래프를 나타냈다.

irate(mysql_global_status_slow_queries[1m])

irate(mysql_global_status_sort_scan[1m])

irate(mysql_global_status_select_scan[1m])

 

다음은 per 알고리즘을 적용하기 전 그래프이다.

 

다음은 per 알고리즘을 적용 후 그래프이다.