Redis 기반 Token bucket 벤치마크 기록

개요

여러 플랫폼에서 공개하는 API들은 서버 자원을 보호하기 위해 Rate Limiting을 적용한다.
클라이언트는 응답 헤더에 담긴 남은 토큰 개수나 다음 요청 가능 시점을 확인하고, 이를 근거로 리소스 접근 여부를 판단하게 된다.

문제는 이러한 정보를 알기 위해서는 결국 API를 직접 호출해야 한다는 건데, 만약 접근이 불가능한 상태라면, 다수의 클라이언트가 동일하게 실패 응답을 받기 위해 반복적으로 리소스를 호출하는 비효율이 발생한다.

 

이를 줄이기 위해 캐싱이나 서킷브레이커(circuit breaker)를 활용할 수 있지만,

캐시는 관리가 까다롭고(e.g. 캐시 무효화 전략의 복잡성,  TTL 설정), 서킷은 RPS 제한이 초 단위로 걸려 있는 경우 너무 자주 열리고 닫혀 비효율적일 수 있다.

그렇다면, 클라이언트 측에서 Rate Limiting 관련 정보를 직접 저장·활용할 수 있다면 어떨까?

이런 접근은 불필요한 요청을 줄이고, 더 효율적으로 트래픽을 제어할 수 있다.

 

당시 회사에서도 Rate Limiting 적용이 필요한 서비스가 있었는데, 선택 기준은 다음과 같았다:

• 트래픽 패턴이 일정 주기마다 치솟는 형태(burst traffic)였고, 이를 유연하게 처리할 수 있어야 함
• 서비스가 여러 Pod로 구성된 분산 환경이었기 때문에, 여러 인스턴스에서 동일한 용량을 공유할 수 있는 방식이 필요
• 가능하면 초저지연시간 내 응답이 가능

위 조건을 만족하는 Bucket4j를 선택했었는데, Redis와의 통합을 지원하며 burst traffic 처리에 가장 유연한 Token Bucket 알고리즘을 기반으로한 라이브러리였기 때문이다.

 

 

Token Bucket을 구현하기 위해 필요한 데이터로 최소 두 가지 정도가 있다:

1. 현재 토큰 개수
2. 마지막 토큰 소비 시각(greedily refill) 또는 마지막 버킷 리필 시각(intervally refill)

Redis를 활용해 이 정보를 관리하려면, 두 개 이상의 key에 대해 명령을 실행해야 한다.

이 과정에서 격리성(단일 실행 단위)의 보장이 필요하므로 multi/exec 트랜잭션이나 lua script 방식을 선택할 수 있다.

 

Bucket4j는 multi/exec 커맨드를 이용해 격리성을 보장한다.

실제 코드 일부를 보면, while 루프 내에서 CAS 연산이 성공할 때까지 반복하는 구조임을 확인할 수 있다.

@Override
public <T> CommandResult<T> execute(K key, Request<T> request) {
    Timeout timeout = Timeout.of(getClientSideConfig());
    CompareAndSwapOperation operation = timeout.call(requestTimeout -> beginCompareAndSwapOperation(key));
    while (true) {
        CommandResult<T> result = execute(request, operation, timeout);
        if (result != UNSUCCESSFUL_CAS_RESULT) {
            return result; // CAS 성공 시 종료
        }
        // 실패 시 재시도
    }
}

 

하지만, CAS 연산은 고경합 상황에서 실패할 가능성이 높다.

 

bucket4j의 maintainer도 CAS 연산을 lua script를 이용한 방식으로 옮겨보려고 했으나, lua script에서 지원하는 타입(실수형, double)과 라이브러리에서 사용하는 타입(정수형, long)이 불일치해 옮기지 않기로 결정했다고 한다.

https://github.com/bucket4j/bucket4j/issues/410

 

Lua script를 이용한 방식은 1-RTT로 처리가 가능하니 경합 상황에서도 안정적인 지연 시간을 기대할 수 있다.

실제로 두 방식의 지연 시간이 얼마나 차이나는지 확인하기 위해 벤치마크 테스트를 진행해보기로 했다.

---

테스트 환경

• Apple M1, 10 CPUs
• JDK 17
• Redis 7.2.1 standalone, loopback(localhost)
• 토큰 버킷 명세: 5,000 토큰, 5,000/s로 greedily refill

---

벤치마크 결과

1. Bucket4j와 Lua script 간 latency(μs) 비교

---

2. Client별 latency(μs) 비교

---

3. Client별 처리량(벤치마크 메서드 호출) 비교

Lettuce > Redisson > Jedis

---

견해

Bucket4j vs Lua script

Bucket4j는 CAS 재시도로 인해 고경합 상황에서 꼬리 지연시간이 증가할 가능성이 높은 것으로 확인된다.

반면에 스크립트를 이용한 호출은 한 번의 EVAL 명령(1-RTT)으로 처리하기 때문에 꼬리 지연 폭이 작다. 

따라서 고경합 상황에서 지연 시간의 단축이 중요한 경우 스크립트를 이용한 Rate limiting 구현이 도움이 될 것이다.

Bucket4j는 다양한 어플리케이션(RDB, In-memory Cache, ...)과의 통합을 제공하고, 사용이 단순하며 블로킹 호출같은 여러 유틸 기능을 제공하므로 이러한 측면에서 선택할 수 있다.

 

Client 비교

Lettuce, Redisson이 대체적으로 낮은 지연시간을 보여주는데, 이는 기저에 Netty를 사용해 네트워크 통신 부분에서 많은 최적화가 이뤄졌기 때문으로 추측된다. Jedis는 동기 + 블로킹 호출이라 다른 클라이언트 라이브러리에 비해 호출 오버헤드가 크다. 

Lettuce가 Redisson 보다 높은 처리량(벤치마크 함수 호출 횟수)을 보여주는데, 이는 Redisson이 다양한 추상화를 제공하기 위해 호출 경로가 더 두꺼운 경향이 있어 호출 당 오버헤드에서 차이가 발생하는 것으로 보인다. Lettuce는 명령 -> 인코딩 -> 쓰기 -> 디코딩 수준의 단순한 계층으로 구성돼있다.

---

결론

블로킹 같은 부가 기능없이 현재 토큰 소비 가능 여부에 대한 의사 결정만 필요한 경우 스크립트를 이용한 방식을 채용하는 것이 좋다. Bucket4j를 이용하게 되면 고경합 상황에서 CAS 재시도로 인한 꼬리 지연시간 증폭이 발생한다.

클라이언트의 경우 네트워크 호출 오버헤드면에서 Netty를 이용하는 Redisson/Lettuce를 선택하는 것이 좋다.

 

Bucket4j를 유지한다면, 재시도 backoff + jitter로 동시 충돌을 완화해줘야 하며, 경합이 발생하는 수를 줄이기 위한 고민이 필요하다.

 

https://github.com/bidulgi69/redis-token-bucket-benchmarks

GitHub - bidulgi69/redis-token-bucket-benchmarks: Benchmark tests comparing different approaches to implement token bucket rate