What is Rate Limiter?

클라이언트 또는 서버가 보내는 트래픽의 처리율(rate)을 제어하기 위한 장치입니다.
단위 시간 동안 얼마만큼의 실행을 허용할 것인지 제한하는 매커니즘 입니다.

Why Rate limiting?

Resource 고갈 방지

DOS(Denial of Service) 공격 시 자원의 고갈을 방지 할 수 있습니다.

Security

로그인, 이벤트와 같은 기능에 Broute force 공격을 방어할 수 있습니다.

비용 절감

auto-scaling 되고, 사용한 만큼 비용을 지불하는 시스템에서는 상한선을 설정하여 운영 비용을 제어하는데 도움이 됩니다.

Rate Limiting Strategies

User

가장 일반적인 방법으로, 지정된 기간동안 사용자에게 허용된 요청수에 제한을 두는 방법 입니다.

Concurreny

주어진 시간내에서 사용자에게 허용될 수 있는 세션 수를 적용하는 방법 입니다.
DDOS 공격에 도움이 됩니다.

Location/ID

위치나 지역을 가지고 비율을 제한하는 방법 입니다.
위치나 인수 통계 중심의 캠페인을 실행하는데 도움이 됩니다.

Server

Rate Limit Algorithms

Leaky Bucket

요청을 큐에 추가하고, 큐가 가득차 있는 경우 새 요청은 버립니다.
지정된 시간 동안 몇 개의 항목을 처리할 지 지정합니다.

고정된 처리율을 가지고 있어 안정적인 출력이 필요한 경우에 적합 합니다.
단시간에 많이 몰리는 경우 최신 요청들은 모두 버려지는 단점이 있습니다.
요청이 주어진 시간이 완료된다는 보장도 없어 제대로 동작하지 않을 수 있습니다.

Token Bucket

leaky Bucket과 유사합니다.
정해진 시간동안 버킷에 토큰이 있으면 요청을 허용하고, 토큰이 고갈되면 요청을 버립니다.
이 버킷에는 사전에 설정된 토큰이 주기적으로 채워집니다.

적은 양의 데이터를 저장하여 메모리 사용 측면에서 효율적 입니다.
단, 분산 환경에서 두 개의 서로 다른 애플리케이션 서버에서 동시에 토큰을 가져오려고 하면 경쟁 조건을 유발할 수 있습니다.
서로 다른 애플리케이션 서버에서 동시에 토큰을 가져오려는 요청이 있을 때 발생할 수 있습니다.

Fixed Window Counter

Timeline을 고정된 간격의 window로 나누고, 각 window마다 count를 붙입니다.
요청이 접수될 때 마다 카운터의 값을 1씩 증가 시킵니다.
카운터의 값이 사전에 설정된 threshold에 도달하면, 새로운 요청은 새 윈도우가 열릴때까지 버려집니다.

메모리 효율이 좋고, 이해하기 쉬운 장점이 있습니다.
window 경계 부근에 순간적으로 많은 트래픽이 집중될 경우 window에 할당된 양보다 더 많은 요청이 처리될 수 있는 단점이 있습니다.

Sliding Window Log

Fixed window counter의 단점을 대응하기 위한 알고리즘 입니다.
하지만 window 요청건에 대한 log를 남겨야 하기 때문에 구현 및 메모리 비용이 높은 단점이 있습니다.

Time stamp의 log를 보통 Redis의 정렬집합(sorted set) 과 같은 캐시에 보관합니다.

Sliding window counter

Fixed window counter의 경계 문제와 Sliding window log의 로그 보관 비용 등의 문제점을 보완하는 알고리즘 입니다.

처리하는 계산식은 1분 동안 n개수로 한도가 있다면
현재 1분간의 요청수 + 직전 1분간의 요청수 X 이동 윈도우와 직전 1분이 겹치는 비율
계산을 통해 나온 값이 n개의 한도를 넘는지를 판단하여 처리합니다.
다소 정확성이 떨어질 수 있지만, 두 알고리즘의 단점이 개선된 알고리즘 입니다.

RateLimiter 저장소에 따른 처리

중앙 저장소(Redis)를 이용

API 제공자 당 카운터를 중앙 저장소에 저장하는 방식으로 구현할 수 있습니다.

처리량이 많지 않은 시스템에 적합하지만, 확장성이 떨어집니다.
설계상 Redis를 단일 노드로 구성한다면 너무 많은 요청 시 Redis가 시스템의 병목이 되고 단일 장애 지점이 됩니다.

분산형 in-memory를 이용

요청을 받는 서비스의 요청 한도를 요청 하는 서비스에 분할, 할당하여 각자 요청을 제어하는 방식 입니다.
각 요청하는 서비스는 자신에게 할당된 비율의 한도를 알아야 합니다.
트래픽이 잘 분산된다면 총 Rate Limit/ 전체 요청하는 서비스 인스턴스로 계산할 수 있습니다.
하지만 서버 에러나 확장 시 문제가 될 수 있습니다.

이때에는 설정 서버를 도입하여 문제를 해결할 수 있습니다.
설정 서버에서 각 요청 받는 서비스에 대한 총 비율 한도와
요청을 하는 서비스의 인스턴수 수를 관리하여 제공하고 설정 서버를 통해 값을 수정할 수 있도록 하여 문제를 해결할 수 있습니다.

요청 제한에 대한 API provider 처리 방안

• 초과된 요청을 버리기
• Http Header의 Response 429(too many requests) 오류를 반환

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

요청 제한에 대한 API consumer 처리 방안

• 다시 요청할 수 있을 때까지 대기
  비동기 방식으로 처리하면서 요청을 생성하는 애플리케이션에 적합합니다.
• 타임아웃 처리
  사용자 요청을 직접 처리하면서 비율이 제한된 다운스트림 API에 의존하는 시스템에 적합합니다.
• 요청 취소
  요청을 통과시킬 때까지 기다릴 수 없는 상황이거나 각 요청을 처리하는 것이 애플리케이션 로직에서 중요하지 않을 때 적합합니다.
• API Consumer는 캐시를 사용하여 API 호출 횟수를 줄이는 방법

Rate Limit 선택은?

Rate Limit 알고리즘은 트래픽 패턴을 분석하여 알고리즘을 선택 해야 합니다.
트래픽 증감에 민감하지 않다면 다소 느슨한 Token Bucket알고리즘을 선택할 수 있고, 그 외에는 Fixed Window나 Sliding Window 알고리즘을 선택 해야 합니다.

참고 URL

https://engineering.linecorp.com/ko/blog/high-throughput-distributed-rate-limiter/#1
https://medium.com/geekculture/system-design-basics-rate-limiter-351c09a57d14