Search

LINE Corporation이 2023년 10월 1일부로 LY Corporation이 되었습니다. LY Corporation의 새로운 기술 블로그를 소개합니다. LY Corporation Tech Blog

Blog

This post is also available in the following languages. English


고 처리량 분산 비율 제한기

Viacheslav Kapilevich2020-06-17

Viacheslav is a server-side engineer at LINE.

보통 프로덕션 등급의 시스템은 서로 의존하는 여러 개의 컴포넌트로 구성됩니다. 최근 몇 년간 마이크로 서비스 아키텍처가 대중화되면서 컴포넌트의 수가 증가했고, 그에 따라 각 컴포넌트 사이의 연결 수도 증가했는데요. 이때 각 컴포넌트에 과부하가 걸리지 않도록 보호하면서 전체 시스템의 서비스 품질을 보장하기 위해 '비율 제한기(rate limiter)'를 사용할 수 있습니다.

이미 많은 글과 튜토리얼에서 단일 호스트에서 실행되는 서비스를 위한 서버 측 비율 제한기(rate limiter)를 다루고 있기 때문에 이번 글에선 고 처리량(high-throughput) 분산 시스템을 위한 클라이언트 측 비율 제한기에 대해 이야기하려고 합니다. 저는 2020 LINE New Year 캠페인 시스템을 개발하면서 클라이언트 측 비율 제한기에 대해 생각해 보게 되었습니다. 이 캠페인은 LINE 서비스 입장에서 연중 가장 많은 트래픽이 유입되는 1월 1일 자정에 시작했는데요. 당시 저희가 직면한 과제 중 하나가 사용자 경험을 저하시키지 않으면서 내부 서비스에 과부하가 걸리는 것을 막는 일이었습니다.

개념과 용어

엔드 포인트가 외부로 노출되어 있기 때문에 과부하가 발생할 위험이 있는 시스템은 종종 보호 차원에서 몇 가지 종류의 서버 측 비율 제한 기법을 구현합니다. 클라이언트 측에선 일반적으로 모든 요청을 적절하게 처리해야 하기 때문에 서버 측에서 정한 비율 제한을 잘 준수하는 것이 좋습니다. 

복잡한 시스템에선 구성 요소가 관점에 따라서 클라이언트와 서버의 역할을 모두 수행할 수 있기 때문에 '클라이언트 측'과 '서버 측'이란 용어의 개념이 혼동될 수 있습니다. 그에 따라 이번 글에선 아래와 같은 용어를 사용하겠습니다.

  • 제공자((API) provider) - API 소비자의 요청을 수락하는 시스템
  • 소비자((API) consumer) - API 제공자에게 요청하는 시스템
  • 제공자 측 비율 제한기 - 제공자 측의 비율 제한기(수신 요청의 비율을 제한)
  • 소비자 측 비율 제한기 - 소비자 측의 비율 제한기(발신 요청의 비율을 제한)
  • 비율 한도(rate limit) - 특정 기간 동안 허락하는 요청의 수

소비자 측과 제공자 측의 비율 제한

소비자 측과 사업자 측의 비율 제한기는 개념은 유사하지만 일부 차이가 있습니다. 가장 큰 차이는 비율 한도에 도달했을 때 처리하는 방식입니다. 제공자 측 비율 제한기가 그냥 요청을 거절하는 방법을 종종 사용하는 반면, 소비자 측에선 아래와 같이 보다 다양한 방법을 사용합니다.

  • 다시 요청할 수 있을 때까지 대기 - 비동기 방식으로 처리하면서 요청을 생성하는 애플리케이션에 적합
  • 일정 시간 동안 기다린 후, 그때도 비율 제한기를 통과하지 못한다면 요청을 타임아웃 처리 - 사용자 요청을 직접 처리하면서 비율이 제한된 다운스트림 API에 의존하는 시스템에 적합(사용자에게 약속한 최대 지연 시간에 맞춘 단기간 동안만 차단 가능한 경우가 많음)
  • 요청 취소 - 비율 제한기가 요청을 통과시킬 때까지 기다릴 수 없는 상황이거나 각 요청을 처리하는 것이 애플리케이션 로직에서 중요하지 않을 때 적합

고 처리량 분산 시스템에 비율 제한기를 구현할 때 발생하는 또 다른 과제는 비율 제한기가 현재 시스템에서 처리하는 요청의 수를 감당할 수 있는지 확인하는 일입니다. 다음으로 분산 시스템을 위한 비율 제한기를 구현하는 몇 가지 방법에 대해 이야기해 보겠습니다.

고 처리량 분산 시스템을 위한 비율 제한기

최근의 마이크로 서비스는 여러 개의 독립된 인스턴스로 배치됩니다. 이를 통해 시스템의 안정성을 향상시키고 필요할 때 시스템을 수평으로 확장할 수 있습니다.

서비스의 모든 인스턴스가 같은 처리를 담당하기 때문에 모든 인스턴스가 같은 API 제공자를 사용합니다. 따라서 제공자의 비율 한도를 공유해야 하는데요. 이때 허용된 비율 한도를 넘지 않도록 소비자 인스턴스 사이에 일부 조정이 필요합니다. 

중앙 저장소 비율 제한기

여러 소비자 인스턴스 사이에서 비율 한도를 조정하는 가장 보편적인 방법 중 하나는 중앙 저장소를 이용하는 것입니다. 이를 가장 간단하게 구현하면 API 제공자당 하나의 카운터를 저장하는 방식으로 구현할 수 있습니다. 카운터는 API 제공자에게 요청할 때마다 하나씩 증가하며 1초가 경과하면 리셋됩니다. 카운터의 값은 현재 초 내에서 요청된 횟수를 나타내며, 비율 한도에 도달했는지 여부를 결정하는데 사용할 수 있습니다. Redis Labs의 공식 문서에서는 아래와 같은 구조로 Redis를 이용해 간단한 비율 제한기를 구현하는 방법을 설명하고 있습니다. 

이 방법은 처리량이 많지 않은 시스템을 위한 간단하면서도 효율적인 해결책이긴 하지만, 확장이 쉽지 않습니다. 설계상 Redis의 단일 카운터는 항상 하나의 노드에 저장됩니다. 만약 이런 상황에서 소비자가 한 제공자에게 너무 많은 요청을 보낸다면 Redis가 시스템의 병목이 되어 버립니다. 더구나 모든 비율 제한기 카운팅을 처리하는 단일 노드는 단일 장애 지점이 됩니다. 복제를 했더라도 즉시 페일오버되지 않고 페일오버 프로세스가 완료될 때까지 모든 API 소비자가 차단되는 것은 좋은 방법이라고 할 수 없습니다. 이 방법은 API 요청마다 각각 Redis 접속이 필요하기 때문에 각 요청의 총 지연 시간이 불가피하게 증가합니다. 또한 Redis는 가장 빠른 저장소 중 하나지만 네트워크 왕복 시간을 고려하지 않을 수 없습니다. 2020 LINE New Year 캠페인에서는 비율이 제한된 트래픽 요청을 초당 30만 건 이상 안전하게 처리해야 했기 때문에 중앙화된 저장소를 이용한 해결책은 사용하지 않기로 결정했습니다.

분산형 인메모리(in-memory) 비율 제한기

중앙화된 저장소 방식의 대안으로 분산형 인메모리 비율 제한기를 생각했습니다. 제공자 API의 비율 제한기를 소비자 인스턴스에 분할, 할당하여 각자 요청을 제어할 수 있도록 만드는 것입니다.

이를 구현하기 위해선 각 소비자 인스턴스는 자신에게 할당된 비율 한도를 알아야 합니다. 만약 트래픽이 각 소비자 인스턴스로 잘 분산된다면 아래와 같은 방법으로 계산할 수 있습니다.

실제 상황에선 애플리케이션이 실행되는 도중 이 변수값들이 바뀔 수 있습니다. 예를 들어 서버 에러나 서버 확장 작업 때문에 소비자 인스턴스의 수가 바뀔 수 있고, 제공자 측에서 가용성 문제가 발생하면 총 비율 한도도 변경될 수 있습니다.

바로 이런 이유로 또 다른 개체인 '설정(configuration) 서버'를 시스템에 도입했습니다. 설정 서버는 각 API 제공자에 대한 총 비율 한도와 소비자 인스턴스 수를 관리하고 제공하며 애플리케이션을 재시작하지 않고 이런 변수의 값들을 수정할 수 있습니다.

설정 서버로는 Central Dogma1를 사용했습니다. 소비자 인스턴스는 시작할 때 Central Dogma의 데이터로 초기화되며, 설정 서버에서 변경 사항을 통지하면 업데이트됩니다. API 소비자 인스턴스에겐 각각 비율 한도가 주어지며, 제공자에게 보내는 모든 요청의 합계가 할당된 비율 한도를 초과해서는 안 됩니다. 이를 위해선 모든 소비자 인스턴스가 제대로 동기화되면서 시간 창(time window)이 시작하고 끝나는 시간에 합의해야 합니다. 이 문제를 해결하기 위해 'wall-clock'과 엄격히 연결된 시간 창(time window)를 사용합니다. 실제 wall-clock의 초가 바뀔 때마다 각 소비자 인스턴스의 요청 카운터가 리셋됩니다.

이 시스템이 잘 작동하기 위해선 소비자 서버의 시계가 네트워크 시간 프로토콜을 사용해 동기화되어야 합니다. 다만 그렇게 한다고 하더라도 완벽한 동기화가 보장되는 것은 아닙니다. 네트워크의 복잡성은 최악의 경우 100ms 이상의 오류를 발생시킬 수 있기 때문입니다.

각 비율 제한기 비교

중앙 저장소 분산 인메모리
✅ 요청을 분산할 필요가 없다. ✅ 높은 처리량을 제공할 수 있다.
✅ 비율 한도를 최대한 사용할 수 있다. ✅ 지연 시간이 증가하지 않는다.
❌ DB 요청 때문에 지연 시간이 증가한다. ❌ 트래픽이 균등하게 분산되지 않는다면 비율 한도를 최대한 활용하지 못한다.
❌ 확장하기 어렵다. ❌ 시스템 시계 동기화가 필요하다.
❌ 단일 장애 지점이 발생한다. ❌ 소비자 인스턴스 수를 관리하기 위해 추가 설정 시스템이 필요하다.

논 블로킹 고 처리량 분산 비율 제한기 구현

이제 논 블로킹 고 처리량 분산 비율 제한기를 구현하는 한 가지 방법을 소개하겠습니다. 

논 블로킹 비율 제한기 구현

최근 리액티브 프로그래밍 패러다임이 서버 측에서 인기를 얻고 있습니다. 블로킹 방식의 구현은 일반적으로 DB 요청이나 네트워크 호출과 같은 I/O 작업을 처리하는 애플리케이션에선 자원 낭비가 발생할 수 있습니다. 2020 LINE New Year 캠페인 시스템은 자바 기반 비동기 웹 서비스 프레임워크인 Armeria2와 비동기 리액티브 스트림 처리 라이브러리인 RxJava2를 사용해 완전한 논 블로킹 애플리케이션으로 개발했습니다. 아래는 비율 제한기를 구현하기 위해 사용한 Kotlin 인터페이스입니다.

interface ApiRateLimiter {
    /**
     * Acquire a permit for request from rate limiter.
     * @param maximumWaitForMillis Maximum time to wait for rate limiter to open in milliseconds.
     * @return Completable that will complete when permit is acquired
     *         or Completable.error(RateLimiterTimeoutException) if rate limiter was closed
     *         for longer than maximumWaitForMillis.
     */
    fun acquire(maximumWaitForMillis: Long): Completable
}

acquire 메서드는 비율 제한기가 요청 실행을 허락했을 때 RxJava2 Completable을 리턴합니다. 메서드는 비율 제한기가 최대로 기다릴 수 있는 시간을 maximumWaitForMillis 인자를 통해 건네받습니다. 만약 현재 초에서 비율 한도에 도달하면 프로그램은 다음 초가 시작할 때  재귀적으로 acquireInternal을 호출하기 위한 일정을 수립하기 위해 RxJava2를 사용합니다. 아래는 이런 기능을 갖춘 기본적인 비율 제한기의 코드입니다.

/**
* Acquire a permit for a request from the rate limiter.
* @param maximumWaitForMillis Maximum time to wait for the rate limiter to open in milliseconds.
* @param beforeWaitedForMillis Accumulative time that has been spent waiting for the rate limiter to open
*                              up until now now. Due to the recursive nature of this function,
*                              beforeWaitedForMillis is used to account for previously waited time.
*                              When this function is called for the first time the value of this parameter
*                              should be 0L (because no time has been waited yet).
* @return Completable that will complete when the permit has been acquired
*         or Completable.error(RateLimiterTimeoutException) if the rate limiter was closed
*         for longer than [maximumWaitForMillis].
*/
private fun acquireInternal(
      maximumWaitForMillis: Long, 
      beforeWaitedForMillis: Long
): Completable {
// Each call, including recursive ones gets a new rate limit, because it might be changed while waiting.
val currentLimit = consumerInstanceRateLimit
val waitForMillis = tryToIncreaseCounter(clock.instant(), currentLimit)
val totalWaitForMillis = beforeWaitedForMillis + waitForMillis
return when {
        // open rate limiter
        waitForMillis == 0L -> {
        Completable.complete()
        }

        // waited too long for rate limiter to open, throwing error
        maximumWaitForMillis <= totalWaitForMillis -> {
            Completable.error(RateLimiterTimeoutException())
        }

        // wait for rate limiter to open and recursively try to acquire again
        else -> Completable
            .complete()
            .delay(waitForMillis, TimeUnit.MILLISECONDS)
            .andThen(Completable.defer {
                acquireInternal(maximumWaitForMillis, totalWaitForMillis)
            })
    }
}

/**
 * Holds the epoch second for which the limit is being counted.
 * Checking [rateLimitedSecond] and increasing [counter] is done in a critical section
 * in [tryToIncreaseCounter]. They must be checked and updated together, atomically.
 */
private var rateLimitedSecond: Long = clock.instant().epochSecond

/**
 * Holds count for the current epoch second.
 * Checking [rateLimitedSecond] and increasing [counter] is done in a critical section
 * in [tryToIncreaseCounter]. They must be checked and updated together, atomically.
 */
private var counter: Long = 0

/**
 * Try to increase the rate limiter counter.
 * If the current rate limiter's fixed window has ended, start counting for the next one.
 * If we are still within the current rate limiter's fixed window, try to increase the counter and if the
 * rate limit is hit, calculate how many milliseconds until the next fixed window starts.
 *
 * @return 0L - if the counter was increased.
 *         amount of milliseconds until the next fixed window - if the rate limit has been reached.
 */
@Synchronized
fun tryToIncreaseCounter(now: Instant, currentLimit: Long): Long {
    return if (rateLimitedSecond == now.epochSecond) {
        if (counter >= currentLimit) {
            val nextSecondStart = now.truncatedTo(ChronoUnit.SECONDS).plusSeconds(1)
            nextSecondStart.toEpochMilli() - now.toEpochMilli()
        } else {
            counter++
            0
        }
    } else {
        rateLimitedSecond = now.epochSecond
        counter = 1
        0
    }
}

비율이 제한된 API를 호출하기 전에 acquire 메서드를 호출한 뒤 Completable가 리턴되길 기다립니다. 

acquire(MAX_TIMEOUT)
  .andThen(Single.defer { someService.someApiCall() })
  .map { ... }

위 예시 코드에선 RxJava의 andThen 메서드를 사용해서 비율 제한기를 획득한 후 순차적으로 API 호출을 수행하고 있습니다. 

논 블로킹 비율 제한기 사용법

API 사용법은 애플리케이션에서 요청을 발행하는 방식에 따라 두 가지로 나눌 수 있습니다. 

  • 즉각적인 반응이 필요한 경우
    • 예) 타임아웃 시간이 고정된 HTTP 요청 처리의 일부로 API가 호출됐을 때
  • 즉각적인 반응이 필요하지 않은 경우
    • 예) Apache Kafka와 같은 기술에 기반한 스트림 처리 애플리케이션의 메시지 처리 과정에서 요청이 생성됐을 때

첫 번째 경우에선 비율 한도에 도달했을 때 대기 시간을 제한하기 위해 위 예시에서 언급했던 maximumWaitForMillis를 사용할 수 있습니다. 

두 번째 경우에선 논 블로킹 비율 제한기 구현을 충분히 활용할 수 있습니다. 실제 사례로 아래 그림에서 볼 수 있는 2020 LINE New Year’ 캠페인의 'Onedari(おねだ, 애원하는 일본어 표현)' 기능을 살펴보겠습니다. 이 기능은 사용자가 친구에게 특별한 형식의 메시지를 보내 새해 캠페인 스티커를 요청할 수 있는 기능입니다.

이런 경우 애플리케이션은 특정 사용자에게 메시지를 전송하기 위해 내부 LINE API를 사용합니다. 이를 구현하기 위해서 발신인이 보낸 Onedari 요청을 받아서 Onedari Kafka topic으로 이벤트를 생산하고, 성공을 표시하는 송신자에게는 즉시 응답합니다. 이벤트를 비동기 방식으로 처리할 수 있고, 비율 한도를 준수하면서 내부 API를 호출할 수 있기 때문에 Onedari Kafka topic의 소비자는 사용자가 응답을 기다리는 것에 대해 신경 쓸 필요가 없습니다.

향후 개선 사항

지금까지 고정 창(fixed-window) 알고리즘에 기반한 기본적인 고 처리량 분산 비율 제한기를 구현한 방법에 대해 말씀드렸는데요. 아직 몇 가지 개선 사항이 있습니다. 

균등하지 않은 시간 내 요청 분포

첫 번째는 시간 윈도 내 요청 비율 분배를 제어하지 않았다는 점입니다. 아래 그림은 이번 글에서 제안한 비율 제한기 구현을 사용했을 때 볼 수 있는 일반적인 요청 분배 형태입니다. 대부분의 요청이 초가 시작할 때 발행된 뒤 비율 한도에 도달한 후에는 더 이상 발행되지 않았습니다.

위 예시에서 소비자는 비율 한도를 준수하고는 있지만 분포가 균일하진 않습니다. 이런 현상은 비율 한도가 충분히 작을 땐 문제되지 않습니다. 하지만 비율 한도가 높게 설정되어 있을 땐 초기에 발생한 높은 피크가 API 제공자에게 상당한 부하를 초래할 수 있습니다. 이 문제는 이전 시간대의 비율 분배 데이터를 이용해 분배를 개선할 수 있는 짧은 지연을 도입하는 것과 같은 방법으로 해결할 수 있습니다.

균등하지 않은 인스턴스 간 요청 분포

또 다른 잠재적 문제는 부하가 제대로 분산되지 않았을 때 소비자 인스턴스의 하위 집합이 더 많은 요청을 제공자 API로 보내는 경우입니다. 만약 애플리케이션에 이런 문제가 발생한다면, 각 소비자 인스턴스의 필요에 따라 비율 한도를 분할해야 하는데요. 그러기 위해선 비율 한도 사용량을 관찰하며 실시간으로 재분배하는 별도의 조정 시스템이 필요합니다. Google의 YouTube 팀에서 개발한 Doorman 같은 시스템을 이런 조정 시스템으로 사용할 수 있을 것입니다.

마치며

저희는 2020 LINE New Year 캠패인을 위한 고 처리량 비율 제한기를 성공적으로 개발하고 적용했습니다. 당시 시스템은 아주 높은 부하를 견뎌내야 했는데요. 비율 제한기는 Kafka를 이용한 비동기 처리와 함께 LINE 내부 서비스에 과부하가 걸리지 않게 하면서 모든 사용자에게 높은 가용성을 제공했습니다. 저희는 운영에 적용하기 전에 96개의 소비자 인스턴스로 비율 제한기 부하 테스트를 실시했는데요. 초당 10개의 요청에서부터 초당 2백만 개의 요청까지 완벽하게 소화했습니다. 운영에 적용할 준비가 끝났으며 확장도 문제없이 잘 이뤄진다는 게 증명된 것입니다. 향후 시스템을 좀 더 개선하여 LINE의 다른 시스템에도 적용할 예정입니다.

  1. Central Dogma – Git과 ZooKeeper, HTTP/2에 기반한 오픈 소스로 고가용성 버전 제어 서비스 설정 저장소입니다.
  2. Armeria – Java 8과 Netty, Thrift, gRPC에 기반한 비동기식 HTTP/2 RPC/REST 클라이어트 서버 라이브러리입니다.