Rate Limiter
처리율 제한 장치, Rate Limiter란?
클라이언트 또는 서비스가 보내는 트래픽의 처리율(rate)을 제어하기 위한 장치
ex. HTTP -> 특정 기간 내에 전송되는 클라이언트의 요청 횟수 제한
API에 처리율 제한 장치를 두면 좋은 점
- DoS(Denial of Service) 공격에 의한 자원 고갈(resource starvation) 방지
- 비용 절감
- 서버 과부하 방지
처리율 제한 알고리즘
토큰 버킷(token bucket) 알고리즘
토큰 버킷: 지정된 용량을 갖는 컨테이너
버킷 크기: 버킷에 담을 수 있는 토큰의 최대 개수
토큰 공급률(refill rate): 초당 몇 개의 토큰이 버킷에 공급되는가
토큰 버킷 알고리즘의 동작 원리
- 버킷에는 사전 설정된 양의 토큰이 주기적으로 채워진다.
- 토큰이 꽉 찬 버킷에는 더 이상의 토큰은 추가되지 않는다.
- 토큰 공급기(refiller)는 버킷에 토큰을 추가하고 버킷이 가득 차면 추가로 공급된 토큰은 버려진다(overflow).
- 각 요청은 처리될 때마다 하나의 토큰을 사용 → 요청이 도착하면 버킷에 충분한 토큰이 있는지 검사
- 충분한 토큰이 있는 경우, 버킷에서 토큰 하나를 꺼낸 후 요청을 시스템에 전달
- 충분한 토큰이 없는 경우, 해당 요청은 버려진다(dropped).
장점
- 구현이 쉽다.
- 메모리 사용 측면에서 효율적이다.
- 짧은 시간에 집중되는 트래픽(burst of traffic) 처리 가능
→ 버킷에 남은 토큰이 있기만 하면 시스템에 요청 전달
단점
- 버킷 크기와 토큰 공급률의 값을 적절하게 튜닝하는 것이 까다로움
누출 버킷(leaky bucket) 알고리즘
요청 처리율 고정, 보통 FIFO(First-In-First-Out) 큐로 구현
버킷 크기: 큐 사이즈와 같은 값. 큐에는 처리될 항목들 보관
처리율(outflow rate): 지정된 시간당 몇 개의 항목을 처리할지 지정하는 값 (보통 초 단위)
누출 버킷 알고리즘 동작 원리
- 요청이 도착하면 큐가 가득 차 있는지 본다.
- 빈자리가 있는 경우 큐에 요청 추가
- 큐가 가득 차 있는 경우 새 요청은 버린다.
- 지정된 시간마다 큐에서 요청을 꺼내어 처리한다.
장점
- 큐의 크기 제한 → 메모리 사용량 측면에서 효율적
- 고정된 처리율 → 안정적 출력(stable outflow rate)이 필요한 경우에 적합
단점
- 단시간에 많은 트래픽이 몰리는 경우
- 오래된 요청들이 쌓이고 제때 처리하지 못하면 최신 요청들은 버려진다.
- 두 인자(버킷 크기, 처리율) 튜닝 까다로움
고정 윈도 카운터(fixed window counter) 알고리즘
고정 윈도 카운터 알고리즘 동작 원리
- 타임라인(timeline)을 고정된 간격의 윈도(window)로 나누고, 각 윈도마다 카운터(counter)를 붙인다.
- 요청이 접수될 때마다 카운터 값 1씩 증가
- 카운터 값이 사전에 설정된 임계치(threshold)에 도달하면 새로운 요청은 새 윈도가 열릴 때까지 버려진다.
문제점
- 윈도의 경계 부근에 순간적으로 많은 트래픽이 집중될 경우 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있다.
ex. 59초에 100번, 00초에 100번 → 1초에 200번
장점
- 메모리 효율이 좋다.
- 이해하기 쉽다.
- 윈도가 닫히는 시점에 카운터를 초기화하는 방식은 특정한 트래픽 패턴을 처리하기에 적합하다.
단점
- 윈도 경계 부근에서 일시적으로 많은 트래픽이 몰려드는 경우, 기대했던 시스템의 처리 한도보다 많은 양의 요청 처리
이동 윈도 로깅(sliding window log) 알고리즘
이동 윈도 알고리즘 동작 원리
- 요청의 타임스탬프(timestamp) 추적
- 타임스탬프 데이터는 보통 레디스(Redis)의 정렬 집합(sorted set) 같은 캐시에 보관
- 새 요청이 오면 만료된 타임스탬프 제거
- 만료된 타임스탬프는 그 값이 현재 윈도의 시작 시점보다 오래된 타임스탬프를 뜻함
- 새 요청의 타임스탬프를 로그(log)에 추가
- 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달
→ 그렇지 않은 경우에는 처리 거부
장점
- 이동 윈도 로깅 알고리즘의 처리율 제한 메커니즘은 아주 정교해서 어느 순간의 윈도를 보더라도 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않는다.
단점
- 거부된 요청의 타임스탬프도 보관 → 다량의 메모리 사용
이동 윈도 카운터(sliding window counter) 알고리즘
고정 윈도 카운터 알고리즘 + 이동 윈도 로깅 알고리즘
요청 수 = 현재 윈도 카운트 현재 윈도 비율 + 이전 윈도 카운트 이전 윈도 비율
장점
- 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에도 잘 대응
- 메모리 효율이 좋다.
단점
- 직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산 → 다소 느슨
처리율 한도 초과 트래픽 처리
어떤 요청이 한도 제한에 걸리면 API는 HTTP 429 응답(too many requests)을 클라이언트에게 보낸다.
경우에 따라서는 한도 제한에 걸린 메시지를 나중에 처리하기 위해 큐에 보관할 수도 있다.
ex. 주문 시스템 과부하 → 해당 주문 추후에 처리
처리율 제한 장치가 사용하는 HTTP 헤더
클라이언트가 자기 요청이 처리율 제한에 걸리고 있는지(throttle), 처리율 제한에 걸리기까지 얼마나 많은 요청을 보낼 수 있는지 → HTTP 응답 헤더(response header)
- X-Ratelimit-Remaining: 윈도 내에 남은 처리 가능 요청의 수
- X-Ratelimit-Limit: 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
- X-Ratelimit-After: 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지 알림
ex. 429 too many requests
