Rate Limiter (intro.)

수많은 사용자들이 동시에 서비스에 접근하게 되면 서비스가 정상적으로 동작하지 못하는 상황이 발생할 수 있습니다. 특히 특정 사용자가 과도한 요청을 보내거나 예상보다 많은 트래픽이 유입되는 경우, 서버의 자원이 빠르게 소모되어 응답 지연이나 장애로 이어질 수 있습니다.이러한 문제를 방지하기 위해 서비스는 사용할 수 있는 자원을 적절히 제어해야 하며, 그중 가장 대표적인 방법이 Rate Limiter입니다. Rate Limiter는 일정 시간 동안 허용되는 요청 수를 제한하여 서비스의 안정성을 보장하고, 모든 사용자에게 공정한 사용 환경을 제공하는 역할을 합니다.

Rate Limiter를 왜 사용해야 할까? 대안은 없을까?

본론적으로 생각해보면 API 요청에 굳이 제한을 두어야 하는지 의문이 들 수 있습니다. 캐시를 활용하여 응답 속도를 개선하거나, 큐를 이용해 요청을 순차적으로 처리하고, 서버를 증설하여 처리량을 늘리는 방법도 존재하기 때문입니다. 이러한 방법들만으로도 충분히 트래픽 문제를 해결할 수 있다고 생각할 수 있습니다.

또한 Rate Limiter를 적용하면 모든 요청에 대해 제한 여부를 확인해야 하므로 API 성능에 영향을 주지 않을까 걱정될 수도 있습니다. 하지만 일반적으로 Rate Limiter가 성능 저하의 원인이 될 정도라면 설계 자체에 문제가 있을 가능성이 높습니다. 대부분의 Rate Limiter는 메모리 기반 저장소를 활용하거나 단순한 카운팅 연산만 수행하기 때문에 오버헤드가 크지 않습니다.

물론 캐시, 큐, 서버 증설과 같은 방법은 시스템의 처리 능력을 높이거나 부하를 분산시키는 데 효과적입니다. 하지만 이러한 방법들은 시스템이 더 많은 요청을 처리할 수 있도록 돕는 역할일 뿐, 과도한 요청 자체를 제어하지는 못합니다.

반면 Rate Limiter는 시스템이 감당할 수 있는 수준 이상의 요청을 사전에 제한함으로써 서비스 전체를 보호합니다. 따라서 Rate Limiter는 캐시나 큐, 서버 증설을 대체하는 기술이 아니라, 예기치 못한 트래픽 증가나 비정상적인 요청으로부터 시스템을 보호하기 위한 안정장치(Safety Net)로 이해하는 것이 적절하다고 생각합니다. 

그렇다면, Rate Limiter는 어느 위치에 둬야할까요?

Rate Limiter는 크게 클라이언트, 서버, 그리고 미들웨어 계층에 배치할 수 있습니다. 어느 위치에 배치하느냐에 따라 목적과 효과가 조금씩 달라집니다. 예를 들어, 클라이언트 측에 Rate Limiter를 적용하면 사용자는 요청 제한 여부를 즉시 확인할 수 있으므로 사용자 경험(UX) 측면에서 유리합니다. 또한 중복 클릭이나 짧은 시간 내 반복 요청을 방지하여 불필요한 네트워크 트래픽을 줄일 수 있습니다.

하지만 클라이언트는 사용자가 제어할 수 있는 영역입니다. 브라우저의 개발자 도구를 이용하거나 직접 API를 호출하는 방식으로 제한을 우회할 수 있기 때문에, 보안이나 서버 보호 관점에서는 신뢰하기 어렵습니다. 따라서, 클라이언트 측 Rate Limiter는 서버를 보호하기 위한 수단이라기보다는 사용자 경험을 개선하고 불필요한 요청을 줄이기 위한 보조적인 수단으로 활용됩니다.

그렇다면, 서버에 Rate Limiter를 두는 이유는 무엇일까요? 

가장 큰 이유는 서버가 신뢰할 수 있는 영역이기 때문입니다. 클라이언트 측에 적용된 Rate Limiter는 사용자가 직접 수정하거나 우회할 수 있지만, 서버 측 Rate Limiter는 모든 요청이 반드시 거쳐야 하는 지점에서 동작하므로 우회가 어렵습니다. 또한, 서버는 전체 트래픽 현황을 파악할 수 있습니다. 특정 사용자가 짧은 시간 동안 과도한 요청을 보내고 있는지, 특정 IP에서 비정상적인 트래픽이 발생하고 있는지, 혹은 서비스 전체가 처리 가능한 한계를 초과하고 있는지 등을 판단할 수 있습니다. 무엇보다 서버 측 Rate Limiter는 애플리케이션 로직이 수행되기 전에 요청을 차단할 수 있다는 장점이 있습니다. 만약 제한 없이 모든 요청을 애플리케이션까지 전달한다면 CPU, 메모리, 데이터베이스 커넥션과 같은 자원이 불필요하게 소모될 수 있습니다. 반면 Rate Limiter를 통해 초기에 요청을 거부하면 시스템 자원을 보호하고 서비스 전체의 안정성을 유지할 수 있습니다.

따라서 클라이언트 측 Rate Limiter가 사용자 경험 향상을 위한 보조 수단이라면, 서버 측 Rate Limiter는 시스템을 보호하기 위한 핵심 방어 수단이라고 볼 수 있습니다.

추가적으로 애플리케이션 서버 앞단에 위치한 게이트웨이를 통해 Rate Limiter를 적용할 수도 있습니다. 게이트웨이는 클라이언트의 요청을 가장 먼저 수신하는 계층으로, 인증, 로깅, 라우팅, Rate Limiting과 같은 공통 기능을 처리하는 역할을 담당합니다.

Rate Limiter를 게이트웨이에 배치하면 애플리케이션 서버에 요청이 전달되기 전에 제한 여부를 판단할 수 있습니다. 이를 통해 불필요한 요청이 서버까지 도달하는 것을 방지하고, 애플리케이션의 자원을 더욱 효율적으로 보호할 수 있습니다.

실제로 스프링 생태계에서는 Spring Cloud Gateway를 제공하며, Redis 기반의 Rate Limiting 기능을 지원합니다. 이를 활용하면 별도의 Rate Limiter를 직접 구현하지 않고도 요청 수를 효과적으로 제어할 수 있습니다.

그렇다면, 단순히 요청을 count하면 되지 않을까요?

단순하게 생각하면 API 요청 횟수를 데이터베이스에 저장하고, 요청이 들어올 때마다 조회하여 제한 여부를 판단하면 될 것 같습니다. 하지만 Rate Limiter를 설계할 때 가장 중요한 점은 Rate Limiter 자체가 시스템에 큰 부하를 주어서는 안 된다는 것입니다.

만약 모든 API 요청마다 데이터베이스에 접근하여 요청 횟수를 조회하고 갱신한다면, 트래픽이 증가할수록 데이터베이스에 과도한 부하가 발생할 수 있습니다. 극단적인 경우에는 서비스 로직보다 Rate Limiter가 더 많은 자원을 소비하는 상황이 발생할 수도 있습니다.

따라서 Rate Limiter는 요청을 제한하는 기능뿐만 아니라, 매우 빠른 속도로 동작해야 한다는 요구사항도 함께 만족해야 합니다. 이상적인 Rate Limiter는 요청 처리에 미치는 영향을 최소화하면서도 정확하게 요청 횟수를 제어할 수 있어야 합니다.

그렇다면 데이터베이스의 부하를 최소화하면서도 효과적으로 요청 수를 관리할 수 있는 방법은 무엇일까요?
Rate Limiter를 구현하기 위한 알고리즘은 다양하지만, 큰 관점에서 보면 버킷(Bucket) 기반 알고리즘과 윈도우(Window) 기반 알고리즘으로 구분할 수 있습니다.

버킷 기반 알고리즘

버킷(Bucket)을 바구니라고 생각해봅시다. 그리고 바구니 안에는 요청을 처리할 수 있는 권한인 토큰(Token)이 들어있다고 가정하겠습니다.

그렇다면 버킷 기반 알고리즘은 크게 두 가지 관점으로 생각해볼 수 있습니다. 첫 번째는 일정한 속도로 버킷에 토큰을 채우는 방법이고, 두 번째는 요청이 발생할 때 버킷에서 토큰을 소비하는 방법입니다.

결국 버킷 기반 알고리즘은 토큰을 어떻게 채우고, 어떻게 소비하느냐에 따라 다양한 형태로 구현될 수 있습니다. 대표적으로 Token Bucket은 요청이 발생할 때 토큰을 소비하는 방식으로 동작하며, Leaky Bucket은 일정한 속도로 요청을 처리하도록 제어하는 방식으로 동작합니다.

Token Bucket

이에 해당하는 그림을 그려보면 다음과 같이 그릴 수 있습니다.

토큰은 일정한 주기에 따라 버킷에 충전됩니다. 그리고 API 요청이 들어오면 버킷에 저장된 토큰을 하나 소비하여 요청을 처리합니다.

하지만 버킷에 사용할 수 있는 토큰이 남아 있지 않다면 요청은 거부되며, 일반적으로 HTTP 429(Too Many Requests)를 반환합니다.

이 알고리즘에서 가장 중요한 것은 토큰의 충전 속도(Refill Rate) 와 버킷의 최대 크기(Capacity) 를 어떻게 설정할 것인가입니다. 예를 들어, 초당 2개의 토큰을 충전하는 경우와 2초마다 1개의 토큰을 충전하는 경우는 장기적인 처리량은 비슷할 수 있지만, 순간적인 요청을 처리하는 방식에는 차이가 발생합니다.

또한, 버킷의 크기가 크다면 평소 사용하지 않은 토큰을 저장해 두었다가 순간적으로 많은 요청(Burst Traffic)이 발생했을 때 이를 처리할 수 있습니다. 반대로 버킷의 크기가 작거나 충전 속도가 너무 느리다면 정상적인 사용자도 요청이 제한될 수 있습니다.

따라서 Token Bucket 알고리즘은 토큰을 얼마나 빠르게 충전할 것인지와 버킷의 크기를 어떻게 설정할 것인지가 성능을 결정하는 핵심 요소라고 볼 수 있습니다.

Leaky Bucket

Token Bucket은 버킷에 토큰을 일정한 속도로 충전(Refill)하고, 요청이 들어올 때마다 토큰을 소비하여 처리율을 제한하는 방식입니다.

반면 Leaky Bucket은 요청을 버킷에 저장한 뒤, 일정한 속도로 요청을 처리합니다. 버킷의 용량을 초과하는 요청이 들어오면 더 이상 저장할 수 없기 때문에 해당 요청은 거부됩니다.

갑작스럽게 많은 트래픽이 유입되면 버킷은 빠르게 가득 차게 됩니다. 버킷의 용량을 초과한 요청은 더 이상 저장할 수 없으므로 거부됩니다. 반면 일반적인 트래픽 환경에서는 요청이 일정한 속도로 버킷을 통과하며 정상적으로 처리됩니다.

개인적으로 Leaky Bucket은 바리게이트와 비슷한 방식이라고 생각합니다. 한 번에 많은 요청이 몰리더라도 모두를 처리하는 것이 아니라, 미리 정해진 속도로만 요청을 통과시킵니다. 이를 통해 갑작스러운 트래픽 증가에도 시스템이 일정한 처리율을 유지할 수 있도록 도와줍니다.

그렇다면 언제 Token Bucket을 선택하고, 언제 Leaky Bucket을 선택해야 할까요? 두 알고리즘 모두 요청을 제한한다는 공통점이 있지만, 트래픽을 처리하는 방식은 분명한 차이가 있습니다. 

순간적으로 많은 요청을 허용하면서도 평균 처리율을 제한하고 싶다면 Token Bucket이 적합하고, 요청을 항상 일정한 속도로 처리하여 시스템의 안정성을 우선시한다면 Leaky Bucket이 적합하다고 생각합니다.

윈도우 기반 알고리즘

도우 기반 알고리즘을 이해하기 위해서는 먼저 윈도우(Window) 라는 개념을 이해할 필요가 있습니다. 지금까지 살펴본 버킷 기반 알고리즘과 달리, 윈도우 기반 알고리즘은 시간을 일정한 구간(Window)으로 나누어 요청을 관리합니다.

윈도우 기반 알고리즘은 시간 구간을 어떻게 관리하느냐에 따라 여러 방식으로 나뉩니다. 대표적으로 고정 윈도 카운터(Fixed Window Counter), 이동 윈도 로깅(Sliding Window Log), 이동 윈도 카운터(Sliding Window Counter) 의 세 가지 알고리즘이 있습니다.

고정 윈도 카운터

윈도우가 시간을 일정 구간으로 나눠서 요청을 관리한다고 하였습니다. 그렇다면 고정 윈도(Fixed Window) 는 이름 그대로 시간을 동일한 크기의 구간으로 나누어 요청을 관리하는 알고리즘입니다.

예를 들어 윈도우의 크기를 1분으로 설정했다면, 시간은 00:00 ~ 00:01, 00:01 ~ 00:02, 00:02 ~ 00:03과 같이 고정된 구간으로 나뉘게 됩니다. 그리고 각 구간마다 요청 수를 별도로 계산하여, 설정한 임계치를 초과하는 경우 더 이상 요청을 처리하지 않습니다.

하지만 실제 트래픽은 윈도우의 경계에 맞춰 발생하지 않습니다. 평소에는 요청이 적더라도 특정 시점에 많은 요청이 한꺼번에 몰릴 수 있으며, 이러한 특성 때문에 고정 윈도 카운터는 예상하지 못한 문제가 발생할 수 있습니다.

예를들어,

특정 시점에 트래픽이 몰리는 상황을 가정해보겠습니다. Rate Limiter의 정책은 1분 동안 최대 100개의 요청을 허용한다고 가정합니다.

먼저 00:00 ~ 01:00 구간의 마지막 20초인 00:40부터 80개의 요청이 발생했다고 해보겠습니다. 그리고 새로운 윈도우가 시작된 직후인 01:00 ~ 01:40 사이에 40개의 요청이 추가로 발생했다고 가정하겠습니다.

고정 윈도 카운터는 두 요청을 서로 다른 윈도우로 판단합니다.

• 00:00 ~ 01:00 → 80개
• 01:00 ~ 02:00 → 40개

따라서 두 윈도우 모두 임계치인 100개를 넘지 않았기 때문에 Rate Limiter는 정상이라고 판단합니다.

하지만 실제 시간을 기준으로 보면 00:40 ~ 01:40 사이에는 총 120개의 요청이 발생한 것입니다. 즉, 매우 짧은 시간 동안 임계치를 초과하는 트래픽이 유입되었음에도, 고정된 시간 구간으로 나누어 계산했기 때문에 이를 감지하지 못하는 문제가 발생합니다.

이처럼 윈도우의 경계(Boundary) 에서 발생하는 문제를 해결하기 위해 등장한 알고리즘이 이동 윈도 로깅(Sliding Window Log) 입니다.

이동 윈도 로깅

이동 윈도 로깅은 고정 윈도 카운터에서 발생하는 경계 문제(Boundary Problem) 를 해결하기 위해 등장한 알고리즘입니다.

이 알고리즘은 모든 요청의 발생 시각을 로그 형태로 기록합니다. 이후 새로운 요청이 들어올 때마다 현재 시점을 기준으로 최근 일정 시간(예: 최근 1분) 동안의 요청 개수를 계산하여 처리 여부를 결정합니다.

따라서 특정 시점에 트래픽이 집중되더라도 고정된 시간 구간에 영향을 받지 않으며, 실제 트래픽 흐름을 기준으로 Rate Limiting을 수행할 수 있다는 장점이 있습니다.

하지만 모든 요청의 로그를 저장해야 하기 때문에 메모리 사용량이 증가한다는 단점이 있습니다. 또한 새로운 요청이 들어올 때마다 현재 시점을 기준으로 오래된 로그를 제거하고, 남아 있는 요청 수를 계산해야 하므로 처리 비용이 증가할 수 있습니다.

즉, 이동 윈도 로깅은 정확도가 높은 대신, 많은 요청이 발생하는 환경에서는 메모리 사용량과 연산 비용이 커질 수 있다는 단점을 가지고 있습니다.

이러한 문제를 해결하기 위해 나온것이 이동 윈도 카운터입니다.

이동 윈도 카운터

이동 윈도 로깅의 가장 큰 단점은 모든 요청의 로그를 저장해야 한다는 점입니다. 요청이 많아질수록 메모리 사용량이 증가하고, 요청을 계산하는 비용도 함께 커질 수 있습니다.

이러한 문제를 개선하기 위해 등장한 것이 이동 윈도 카운터(Sliding Window Counter) 입니다. 이동 윈도 카운터는 모든 요청을 저장하지 않고, 이전 윈도우의 요청 수와 현재 윈도우의 요청 수만을 이용하여 현재 시점의 요청 수를 계산합니다.

즉, 모든 로그를 관리하는 대신 두 개의 윈도우 정보를 활용해 현재 요청량을 추정하는 방식입니다. 이로 인해 이동 윈도 로깅보다 메모리 사용량이 적고 연산 비용도 낮아지지만, 실제 요청 수를 계산하는 것이 아니라 추정하는 방식이므로 약간의 오차가 발생할 수 있습니다.

계산식은 다음과 같습니다.

예상 요청 수 = 이전 윈도우 요청 수 × (남은 시간 비율) + 현재 윈도우 요청 수

그렇다면 왜 이러한 계산식을 사용하는 것일까요?

그렇다면 어째서 이러한 계산식을 사용하는 것일까요? 이전 윈도우의 요청 수는 이미 집계가 완료된 값이지만, 현재 윈도우는 아직 진행 중이기 때문에 최종 요청 수를 알 수 없습니다.

따라서 현재 윈도우가 얼마나 진행되었는지를 시간의 비율로 계산하여, 이전 윈도우에서 현재 시점까지 영향을 미치는 요청 수를 추정합니다. 이후 여기에 현재 윈도우에서 발생한 요청 수를 더하면, 현재 시점을 기준으로 최근 1분 동안의 요청량을 근사치로 계산할 수 있습니다.

예를 들어, 이전 윈도우의 요청 수가 80개, 현재 윈도우의 요청 수가 30개라고 가정해보겠습니다. 또한 윈도우는 1분 단위로 갱신되며, 현재 시각은 새로운 윈도우가 시작된 지 20초가 지난 시점이라고 가정하겠습니다.

그렇다면 현재 시점을 기준으로 최근 1분인 00:20 ~ 01:20 구간에는 총 몇 개의 요청이 발생했을까요?

이동 윈도 카운터는 이 값을 직접 계산하지 않습니다. 대신 이전 윈도우의 요청이 시간 전체에 고르게 분포되어 있다고 가정하고 계산합니다.

현재 윈도우가 20초 진행되었다는 것은, 최근 1분에는 이전 윈도우의 마지막 40초만 포함된다는 의미입니다. 따라서 이전 윈도우의 요청 수 80개 중 2/3만 반영하여 다음과 같이 계산합니다.

80 × 2/3 ≒ 53

여기에 현재 윈도우에서 발생한 요청 수 30개를 더하면,

53 + 30 = 83

즉, 00:20 ~ 01:20 구간에서는 약 83개의 요청이 발생한 것으로 추정할 수 있습니다.

이렇게 하면 이동 윈도 로깅 방식에서 문제가 되었던 메모리 사용량을 크게 줄일 수 있습니다. 하지만 한편으로는 모든 요청을 저장하지 않고 추정값을 이용한다는 점에서, 정확도가 떨어지는 것은 아닐까 하는 의문이 생길 수 있습니다.

그렇다면 과연 이러한 근사 계산만으로도 트래픽을 안전하게 제어할 수 있을까요?

이러한 의문에 대한 대표적인 사례로 Cloudflare의 실험을 들 수 있습니다. Cloudflare는 이동 윈도 카운터(Sliding Window Counter) 와 이동 윈도 로깅(Sliding Window Log) 을 비교하기 위해 약 4억 건의 요청을 대상으로 실험을 진행했습니다.

그 결과, 오분류율(Misclassification Rate)은 0.003%에 불과했으며, 평균 추정 오차는 약 6% 수준으로 나타났습니다. 또한 임계치 이하의 요청이 잘못 차단된 사례는 없었고, 임계치를 초과했음에도 허용된 요청 역시 대부분 임계치 근처에서만 발생한 것으로 확인되었습니다.

즉, 이동 윈도 카운터는 모든 요청을 저장하지 않더라도, 실제 서비스에서는 이동 윈도 로깅과 매우 유사한 수준의 정확도를 제공하면서 메모리 사용량과 연산 비용을 효과적으로 줄일 수 있는 알고리즘이라는 것을 확인할 수 있습니다.

Rate Limiting Strategies: Token Bucket, Leaky Bucket, and Sliding Window — Sujeet Jaiswal - Principal Software Engineer

하지만 그렇다고 해서 이동 윈도 카운터를 모든 상황에서 만능 해결책처럼 사용할 수 있는 것은 아닙니다. 이동 윈도 카운터는 이전 윈도우와 현재 윈도우를 기반으로 요청 수를 추정하는 방식이기 때문에, 실제 요청 수와는 약간의 오차가 발생할 수 있습니다.

일반적인 웹 서비스에서는 이러한 오차가 거의 문제가 되지 않을 수 있습니다. 하지만 대규모 이벤트나 티켓 예매처럼 짧은 시간 동안 트래픽이 폭발적으로 몰리는 환경에서는 작은 오차도 큰 차이를 만들어낼 수 있습니다. 따라서 서비스의 특성과 트래픽 패턴을 고려하여, 필요한 경우에는 이동 윈도 로깅과 같이 더 높은 정확도를 제공하는 알고리즘을 선택하는 것이 적절할 수 있습니다.

 

알고리즘	장점	단점	추천 사용 환경
고정 윈도 카운터	구현이 단순하고 메모리 사용량이 적다.	윈도우 경계에서 순간적으로 많은 요청을 허용하는 Boundary Problem이 발생할 수 있다.	내부 시스템, 간단한 Rate Limiter, 정확도가 크게 중요하지 않은 서비스
이동 윈도 로깅	최근 요청을 정확하게 계산하여 가장 높은 정확도를 제공한다.	모든 요청을 저장해야 하므로 메모리 사용량과 연산 비용이 크다.	로그인, 결제, 금융, 보안 정책 등 정확도가 중요한 서비스
이동 윈도 카운터	적은 메모리로 높은 정확도를 제공하며 성능과 정확도의 균형이 좋다.	근사치를 계산하므로 약간의 오차가 발생할 수 있다.	API Gateway, 일반 REST API, 대부분의 웹 서비스, 대규모 서비스

마무리

이번 글에서는 Rate Limiter의 대표적인 알고리즘에 대해 학습해보았습니다. 크게 버킷 기반 알고리즘과 윈도우 기반 알고리즘으로 구분할 수 있으며, 각각의 특징과 장단점을 살펴보았습니다.

개인적으로 버킷 기반 알고리즘은 순간적으로 몰리는 트래픽을 제어하는 1차 방어막이라는 느낌을 받았습니다. 또한 Token Bucket과 Leaky Bucket은 목적이 조금 다르기 때문에, 상황에 따라 함께 사용하더라도 크게 문제되지 않을 수 있다고 생각합니다.

반면 윈도우 기반 알고리즘은 일정 시간 동안의 요청을 기준으로 트래픽을 관리하는 방식입니다. 따라서 고정 윈도우 카운터, 이동 윈도 로깅, 이동 윈도 카운터는 각각의 특성을 고려하여 서비스 환경에 맞게 선택하는 것이 더 적합하다고 생각합니다.

결국, 어느 알고리즘이 절대적으로 우수하다고 말하기는 어렵습니다. 중요한 것은 서비스의 트래픽 특성과 요구사항을 이해하고, 그에 맞는 Rate Limiting 알고리즘을 선택하는 것이라고 생각합니다.