처리율 제한 장치의 설계

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=278536695

[전자책] 가상 면접 사례로 배우는 대규모 시스템 설계 기초

 

개요

---

네트워크 시스템에서 처리율 제한 장치(Rate Limiter)는 클라이언트 또는 서비스가 보내는 트래픽의 처리율(rate)을 제어하기 위한 장치다. API 요청 횟수가 제한 장치에 정의된 임계치(threshold)를 넘어서면 추가로 도달한 모든 호출은 처리가 중단(block)된다.

이와 관련하여 몇 가지 사례들은 다음과 같다.

• 사용자는 초당 2회 이상 새 글을 올릴 수 없다.
• 같은 IP 주소로 하루에 10개 이상의 계정을 생성할 수 없다.

 

이처럼 이번 포스팅에서는 처리율 제한 장치를 설계하는데, API에 처리율 제한 장치를 두면 좋은 점은 다음과 같다.

• DoS(Denial of Service) 공격에 의한 자원 고갈을 방지할 수 있다.
• 비용을 절감할 수 있다. (추가 요청에 대한 처리를 제한하여 서버 비용, 우선순위 고려 등) 아울러 처리율 제한 장치는 third-party API에 사용료를 지불하는 회사들에게는 아주 중요하다. 예를 들어 신용 확인, 건강 상태 확인 등에 호출하는 API에 대한 과금이 횟수에 따라 이루어진다면, 그 만큼 많은 비용이 발생할 수 있다.
• 서버의 과부하를 막을 수 있다.

실제 트위터는 3시간 동안 300개의 트윗만 올릴 수 있도록 제한하고 있다.

구글 독스 API는 사용자당 분당 300회의 read 요청만 허용한다.

 

https://docs.x.com/x-api/fundamentals/rate-limits

https://docs.x.com/x-api/fundamentals/rate-limits

책의 내용은 과거 기준이다보니, 현재 트위터(X)의 Rate-Limiter의 기준은 조금 다릅니다. (Basic Limit이 3시간에 300건)

Elon Musk의 2023.07.02 트윗
https://x.com/elonmusk/status/1675187969420828672

 

 

https://developers.google.com/docs/api/limits?hl=ko

구글 Docs의 API는 책의 내용과 동일하게 읽기 요청에 대한 분당 처리율 제한은 300으로 설정되어 있습니다.

 

 

개략적 설계안 제시 및 동의 구하기

---

처리율 제한 장치는 어디에 둘 것인가?

처리율 제한 장치는 클라이언트, 서버, 미들웨어(게이트웨이)에 두는 방식이 있을 수 있겠다.

 

클라이언트 요청은 쉽게 위변조가 가능하고, 모든 클라이언트의 구현을 통제하는 것도 어렵기에 클라이언트는 선택 대상에서 제외한다.

그렇다면, 서버나 미들웨어가 될 텐데 당연하게도 이에 대한 정답은 없고 각 환경에 맞게 선택하면 될 것 같다.

Server vs MiddleWare

• 서버 측에서 모든 것을 구현하기로 했다면, 자유도가 보장이 되는 방면, 미들웨어의 게이트웨이를 사용하기로 했다면 선택지는 제한이 될 수도 있다.
• 아키텍처가 마이크로서비스에 기반하고 있고, 인증/인가 등을 처리하기 위해 API 게이트웨이를 이미 설계에 포함시켰다면, 처리율 제한 기능 또한 게이트웨이에 포함시키는 것이 좋을 수 있다.
• 처리율 제한 장치를 구현하기에 충분한 인력/리소스 등이 없다면 상용 API 게이트웨이를 사용할 수 있다.

 

처리율 제한 알고리즘

처리율 제한 알고리즘의 기본 아이디어는 단순하다. 얼마나 많은 요청이 왔는지 추적할 수 있는 카운터를 대상별(사용자, IP, API 엔드포인트 등)로 설정하고, 카운터의 값이 설정한 한도를 넘어선다면 추가 요청은 거부하는 것이다.

 

처리율 제한을 실현하는 알고리즘은 여러 가지인데, 각기 다른 장단점을 가지고 있다. 따라서 각각의 특성을 이해하고 상황에 맞는 알고리즘 조합을 찾도록 하자.

 

 

토큰 버킷 (token bucket) 알고리즘

토큰 버킷 알고리즘은 처리율 제한에 폭넓게 이용되고 있는데, 간단하고 알고리즘에 대한 이해도가 높으며, 인터넷 기업들이 보편적으로 사용하고 있기 때문이다.

• Amazon Throttle API requests for better throughput
• Stripe rate limiters

토큰 버킷 알고리즘의 동작 원리는 다음과 같다.

• 토큰 버킷은 지정된 용량을 갖는 컨테이너로, 버킷에는 사전에 설정된 양의 토큰이 주기적으로 채워진다. 토큰이 꽉 찬 버킷에는 더 이상의 토큰이 추가되지 않는다.
• 토큰 공급기(refiller)는 버킷에 매초 n개의 토큰을 추가한다.

각 요청은 처리될 때마다 토큰이 충분한지 검증하여 하나의 토큰을 사용한다.

• 충분한 토큰이 있는 경우, 버킷에서 토큰 하나를 꺼낸 후 요청을 시스템에 전달한다.
• 충분한 토큰이 없는 경우, 해당 요청은 버려진다.

 

토큰 버킷의 크기 = 4, 토큰 공급률 = 분당 4

위 이미지는 토큰 버킷 알고리즘에서 각 요청에 대한 토큰의 동작 방식을 나타낸다.

토큰 버킷 알고리즘은 버킷 크기와 토큰 공급률 총 2개의 파라미터를 받는다.

• IP 주소별로 처리율 제한을 적용해야 한다면 IP 주소마다 버킷을 하나씩 할당해야 한다.
• 시스템의 처리율을 초당 10,000개 요청으로 제한하고자 한다면, 모든 요청이 하나의 버킷을 공유하도록 해야 한다.

장점

• 구현이 쉽다.
• 짧은 시간에 집중되는 트래픽도 처리 가능하다. 버킷의 상태에 따라 요청이 처리되기 때문이다.

단점

• 2개의 파라미터(버킷 크기, 토큰 공급률)의 값을 적절하게 튜닝하는 것이 까다로운 일이 될 것이다.

 

누출 버킷 (leaky bucket) 알고리즘

Shopfiy의 누출 버킷 알고리즘을 사용한 처리율 제한 구현
- https://shopify.dev/docs/api/admin-rest/usage/rate-limits

누출 버킷 알고리즘은 토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정되어 있다는 점이 다르다. 누출 버킷 알고리즘은 보통 FIFO 큐로 구현하며, 동작 원리는 다음과 같다.

• 요청이 도착하면 큐가 가득 차 있는지 보고, 빈자리가 있는 경우 큐에 요청을 추가한다.
• 큐가 가득 차있다면 새 요청은 버린다.
• 지정된 시간마다 큐에서 요청을 꺼내 처리한다.

누출 버킷 알고리즘은 다음 두 인자를 사용한다.

• 버킷 크기: 큐 사이즈와 같은 값 (큐에는 처리될 항목들을 관리)
• 처리율(outflow rate): 지정된 시간당 몇 개의 항목을 처리할지 지정하는 값, 보통 초 단위로 표현

장점

• 큐의 크기가 제한되어 있어 메모리 사용량 측면에서 효율적이다.
• 고정된 처리율을 갖고 있기에 안정적인 출력이 필요한 경우 적합하다.

단점

• 단시간에 많은 트래픽이 몰리는 경우 큐에는 오래된 요청들이 쌓이게 되고, 요청들을 제시간에 처리하지 못하면 최신 요청들은 버려지게 된다.
• 토큰 버킷 알고리즘과 마찬가지로 두 인자를 올바르게 튜닝하기가 까다로울 수 있다.

 

고정 윈도 카운터 (fixed window counter)

고정 윈도 카운터 알고리즘은 다음과 같이 동작한다.

• 타임라인을 고정된 간격의 윈도로 나누고, 각 윈도마다 카운터를 붙인다.
• 요청이 접수될 때마다 카운터의 값은 1씩 증가한다.
• 카운터의 값이 사전에 설정된 임계치에 도달하면 새로운 요청은 새 윈도가 열릴 때까지 버려진다.

위 이미지에서 타임라인의 시간 단위는 1초이고, 시스템은 초당 3개까지의 요청만을 허용한다.

따라서 매초마다 열리는 윈도에 3개 이상의 요청이 온다면, 초과 요청은 버려지게 된다.

 

이 알고리즘에서 타임라인의 주기가 길어질수록 경계 부근에서 순간적으로 많은 트래픽이 집중될 경우 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있다.

예를 들어, 분당 최대 5개의 요청만을 허용하는 시스템에서 카운터는 매분마다 초기화된다고 가정한다면,,

• 2:00 ~ 2:01 사이에 5개의 요청이 들어왔고,
• 2:01 ~ 2:02 사이에 5개의 요청이 들어왔다.
• 하지만 2:00:30 ~ 2:01:30 으로 위치를 옮겨서 본다면 처리한 요청은 총 10개로, 허용 한도의 2배가 된다.

장점

• 이해하기 쉽다.
• 윈도가 닫히는 시점에 카운터를 초기화하는 방식은 특정 트래픽 패턴을 처리하기에 적합하다.

단점

• 경계 부근에서 일시적으로 많은 트래픽이 발생한다면, 처리 한도보다 많은 양의 요청을 처리하게 될 수 있다.

고정 윈도 카운터 알고리즘의 문제점을 개선하고자 이동 윈도 로깅 알고리즘, 이동 윈도 카운터 알고리즘 등이 존재한다.

 

 

상세 설계

• 클라이언트가 요청을 서버에 보내면 요청은 먼저 처리율 제한 미들웨어에 도달한다.
• 처리율 제한 미들웨어는 제한 규칙 및 카운터, 마지막 요청의 타임스탬프 등을 캐시(Redis)에서 가져온다. 가져온 값들에 근거하여 미들웨어는 다음과 같은 결정을 내린다.
  • 해당 요청이 처리율 제한에 걸리지 않은 경우 API 서버로 전송한다.
  • 해당 요청이 처리율 제한에 걸린다면, 429: too many requests 에러를 클라이언트에 보내는데, 이 때 요청은 그대로 버릴 수 있고(옵션1), 메시지 큐에 보관(옵션2)할 수도 있다.

처리율 제한을 회피하기 위한 클라이언트는 어떻게 설계하는 것이 최선일까? 다음 방법을 고려해볼 수 있겠다.

• 클라이언트 측 캐시를 활용하여 API 호출 횟수를 줄인다.
• 처리율 제한의 임계치를 파악하고, 이를 고려하여 짧은 시간에 많은 메시지를 전송하지 않는다.
• 재시도(Retry) 로직을 구현할 때는 충분한 백오프(back-off) 시간을 둔다.