Rate Limiter 와 구현 알고리즘

개요

네트워크 시스템에서 처리율 제한 장치(rate limiter)는 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치이다. 예를 들어 HTTP 통신을 수행하는 클라이언트와 서버가 존재한다고 가정해보자. 서버는 특정 기간 내에 전송되는 클라이언트의 요청 횟수를 제한하고 싶을 수 있을 것이다. API 요청 횟수가 제한 장치에 선언된 임계치를 넘어서면 해당 클라이언트의 다음 요청은 block 되며 버려지거나, 추후 처리를 위해 큐에 보관된다.

 

요청이 block된 경우 HTTP status code 429 - Too many requests 를 응답한다. 또한 아래의 HTTP 헤더 값을 사용하여 클라이언트에게 적절한 정보를 응답할 수 있다.

• X-Ratelimit-Remaining: 윈도 내 남은 처리 가능 요청 수
• X-Ratelimit-Limit: 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
• X-Ratelimit-After: 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지

 

rate limiter는 특정 IP address 혹은 디바이스 등의 식별가능한 네트워크 장치로부터의 비정상적으로 많은 요청을 감지하여 처리하거나 서버의 전체적인 부하를 감당하기 위해 혹은 단순히 처리율을 제어하기 위해 사용되는 기술이다. 상황에 맞게 구현하는 여러 알고리즘이 존재한다.

 

 

사용처

예시를 생각해보면 클라우드 기반의 SaaS 모델 플랫폼을 생각해볼 수 있다. 해당 플랫폼은 단위 시간당 트래픽 혹은 전체 트래픽 처리에 대한 차등적인 요금제를 적용시킬 수 있을 것이다. 각 요금제 마다의 트래픽을 관리할 수 있어야 한다. 또한 클라이언트의 요금제에 해당하는 트래픽의 임계치를 넘어서는 경우 block 시켜야 할 것이다.

 

또, 웹 애플리케이션 서버를 운영한다고 가정했을 때, 트래픽이 급증하는 것을 고려하여 예산 범위 내의 오토 스케일링을 걸어 둘 것 같다. 따라서 rate limiter를 구현하는 것이 의미가 없을 것이라고 생각했다.

하지만 예상을 뛰어넘은 트래픽 발생으로 서버에 과부하가 발생하여 마비된다면 문제가 발생할 수 있을 것이라고 예상된다. 이런 경우를 대비해서 rate limiter를 구현하고 트래픽을 제어할 수 있을 것이라 예상한다. 아직 확실하진 않기에 해당 방식의 사용은 실무에서 정답을 찾아보려 한다.

 

대규모 시스템 설계 기초 라는 도서에서는 다음과 같은 사용처 사례를 예시로 든다.

• 사용자는 초당 2회 이상 새 글을 올릴 수 없다.
• 같은 IP 주소로는 하루에 10개 이상의 계정을 생성할 수 없다.
• 같은 디바이스로는 주당 5회 이상 리워드를 요청할 수 없다.

이렇게 정책과 트래픽이 엮여있는 문제를 rate limiter를 통해 해결할 수 있을 것이다.

 

 

장점

DoS 공격에 의한 자원 고갈을 방지할 수 있다. 대형 IT 기업들이 공개한 거의 대부분의 open API는 어떤 형태로든 처리율 제한 장치를 가지고 있다고 한다. 예를 들어 트위터는 3시간 동안 300개의 트윗만 올릴 수 있도록 제한하고 있다고 한다.

 

비용을 절감하며, 서버 과부하을 막는다. 개요에서 말했듯이 요청에 대한 처리를 제한한다면 서버를 많이 두지 않고도 원하는 만큼의 요청을 처리할 수 있을 것이다. 또한 우선순위가 높은 API에게 더 많은 자원을 할당할 수 있을 것이다. 

처리율 제한은 제3자(third-party) API에 사용료를 지불하고 있는 회사들에게는 아주 중요하다. 예를 들어, 신용을 확인하거나, 신용카드 결제를 하거나, 건강 상태를 확인하거나 하기 위해 호출하는 API에 대한 과금이 횟수에 따라 이루어진다면, 그 횟수를 제한할 수 있어야 비용을 절감할 수 있을 것이다. <대규모 시스템 설계 기초>

 

 

설계 시 고려할 점

• 어떤 종류의 rate limiter를 설계해야 하는가? (클라이언트 측 혹은 서버 측)
• 어떤 기준을 사용하여 API 호출을 제어해야 하는가 (IP 주소, 사용자 식별자, 특정 기준 등)
• 시스템 규모는 어느정도여야 하는가 (스타트업 정도, 사용자가 많은 큰 기업)
• 시스템이 분산 환경에서 동작해야 하는가
• rate limiter는 독립된 서비스인가 혹은 애플리케이션  코드에 포함될 것인가
• 처리율 임계값을 어느정도로 강력하게 지킬 것인가 (+-10% 는 허용, 1번의 요청 조차 허용하지 않음 등)

 

처리율 제한 알고리즘

처리율 제한을 구현하는 알고리즘은 여러 가지가 존재한다. 각기 다른 장단점을 가지고 있기에 상황에 맞게 선택하여야 한다.

• 토큰 버킷 (token bucket)
• 누출 버킷 (leaky bucket)
• 고정 윈도 카운터 (fixed window counter)
• 이동 윈도 로그 (sliding window log)
• 이동 윈도 카운터 (sliding window counter)

 

토큰 버킷 알고리즘

토큰 버킷은 지정된 용량을 가지는 컨테이너이다. 이 버킷에는 사전에 설정된 양의 토큰이 주기적으로 채워진다. (예를 들어 토큰 공급기를 통해 매초 2개의 토큰을 추가하는 방식) 토큰이 가득 찼다면 추가하지 않는다. 각 요청이 처리될 때마다 하나의 토큰을 소비하는 방식으로 처리율을 제한한다. 알고리즘에 필요한 인자로는 버킷의 크기와 토큰 공급률이 있다. 통상적으로 API 엔드포인트 마다 별도의 버킷을 두어 관리한다고 한다. 

 

토큰 버킷 알고리즘은 간단하고, 알고리즘에 대한 세간의 이해도가 높은 편이라 인터넷 기업들이 보편적으로 사용한다. (아마존과 스트라이프가 API 요청을 통제하기 위해 해당 알고리즘을 사용한다고 한다.) 두 개의 인자 값만을 가지기에 튜닝하기 까다롭다.

 

누출 버킷 알고리즘

누출 버킷 알고리즘은 큐를 통해 요청을 제어하는 알고리즘이다. 요청이 도착하면 큐가 가득 차 있는지 확인하고, 큐에 요청을 추가한다. 지정된 시간마다 큐에서 요청을 꺼내어 처리하는 방식으로 처리율을 제한한다. 지정된 시간 마다 큐에서 일정 개수의 요청을 꺼내어 처리하기에 고정된 처리율(보통 초 단위)을 가진다.

 

고정된 처리율을 가지고 있기에 안정적인 출력이 필요한 경우 적합하다. 하지만 단기간에 많은 트래픽이 몰리는 경우 버려지는 최신 요청이 많아지게 된다는 단점을 가지고 있다. 또한 토큰 버킷 알고리즘과 동일하게 두 개의 인자를 통해 알고리즘을 구현하므로 튜닝이 까다롭다.

 

고정 윈도 알고리즘

고정 윈도 카운터 알고리즘은 타임라인을 고정된 간격의 윈도로 나누고, 윈도마다 카운터를 붙인다. 해당 타임라인에 받은 요청은 카운터를 1씩 증가시키고 임계치가 도달하면 버려진다. 

 

해당 알고리즘의 가장 큰 문제가 있는데, 슬라이딩 윈도우로 바라보면 타임라인 경계에 순간적으로 많은 트래픽이 집중될 경우 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있다는 점이다. 만약 1분에 5개의 요청을 허용하도록 고정 윈도 알고리즘을 설정했다고 가정한다면 아래와 같은 문제가 발생할 수 있다.

 

 

이동 윈도 로깅 알고리즘

요청에 대한 시간 값을 레디스와 같은 캐시에 저장하고, 현재 요청이 들어온 시간을 기준으로 윈도를 만들어 캐시 데이터를 확인한다. 예를 들어 1분에 5개의 요청을 처리하도록 이동 윈도 로깅 알고리즘을 구현했다고 가정했을 때, 현재 요청이 들어온 시간을 기준으로 이전 1분동안 몇개의 요청이 들어왔는지 캐시에서 확인하는 방식으로 처리율을 제한한다.

 

해당 알고리즘은 고정 윈도 알고리즘의 슬라이딩 윈도우 문제를 해결하지만 거부된 요청의 시간 정보도 캐시에 저장되므로 많은 메모리를 사용한다는 단점이 존재한다.

 

이동 윈도 카운터 알고리즘

이동 윈도 카운터 알고리즘은 고정윈도 알고리즘처럼 카운터를 통해 처리율을 제한하는 방식을 베이스로 슬라이딩 윈도우에 대한 카운터를 계산하는 수식을 추가하여 처리율을 제한한다. 아무래도 정확하게 밀리초 단위로 슬라이딩 윈도우를 측정하는 것은 무리가 있기에 수식을 통해 예측하여 카운터를 측정한다.

 

1분동안 7개의 요청을 처리하도록 이동 윈도 카운터 알고리즘을 구현했다고 가정했을 때 수식은 이렇게 세울 수 있다.

현재 처리 요청 수 = 현재 타임라인의 요청 수 + (직전 타임라인의 요청 수 * 현재 슬라이딩 윈도우와 겹치는 비율)

즉, 5(02:02 ~ 02:03 사이의 요청 수) + (5 * 70%) = 6.5, 현재 슬라이딩 윈도우의 처리 수는 6.5개로 반올림하거나 내림하여 요청을 처리할지 버릴지 결정하는 방식이다.

 

 

---

 

마무리

rate limiter는 모 빅테크 기업의 면접에서 받았던 질문이었는데, 나에겐 생소한 지식이고 제대로된 답변을 하지 못한 아쉬움이 남았다. 따라서 이번 기회에 학습해보았다.

 

학습을 통해 rate limiter는 트래픽 당 비용이 발생하는 등의 일부환경에서 적용하기에 적합하다는 생각이 들었다.

실무에서 실제로 어떻게 구현되는지 혹은 어떤 제품을 사용하는지 확인해보고 내 지식으로 흡수하고 싶다.