처리율 제한 장치란?

이상훈·2024년 8월 27일

Project

목록 보기

9/10

처리율 제한 장치란?

처리율 제한 장치(rate limiter)는 특정 기간 내에 전송되는 클라이언트의 요청 횟수를 제한하는 장치이다. API 요청 횟수가 제한 장치에 정의된 임계치를 넘어서면 추가로 도달한 모든 호출은 처리가 중단된다.

다음은 처리율 장치의 몇가지 사례다.

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

다음은 처리율 장치를 두면 얻는 이점이다.

DoS(Denial of Service) 공격 방지 : DoS는 서버에 트래픽을 범람시켜 웹 사이트 또는 리소스를 사용할 수 없게 만든다. 처리율 제한 장치는 추가 요청에 대해서는 처리를 중단함으로써 DoS 공격을 방지한다.
비용 절감 : 추가 요청에 대한 처리를 제한하면 서버를 많이 두지 않아도 되고, 우선순위가 높은 API에 더 많은 자원을 할당할 수 있다. 또한 제3자(third-party) API에 사용료를 지불하고 있는 회사들에게는 그 횟수를 제한하여 비용을 절감할 수 있다.
서버 과부하 방지 : 봇(bot)에서 오는 트래픽이나 사용자의 잘못된 이용 패턴으로 유발된 트래픽을 걸러내는데 처리율 제한 장치를 활용할 수 있다.

구현 위치

그렇다면 처리율 장치는 어디에 두는 것이 좋을까? 크게 1. 클라이언트, 2. 서버, 3. 미들웨어에 둘 수 있을 것이다. 여기서 클라이언트 측에 두는것은 요청 위변조 때문에 추천하지는 않는다. 서버와 미들웨어 중에서는 정답은 없으며 조직의 기술 스택, 우선 순위, 아키텍처 등에 따라 달라질 수 있다.

서버 : redis를 주로 활용한다. redis는 빠르고 시간에 기반한 만료 정책을 지원한다. 다양한 알고리즘을 활용할 수 있다.
미들웨어 : 주로 API gateway를 활용하며 MSA 환경에서 사용하기에 적합하다. 일부 알고리즘이 제한 될 수 있다.

처리율 제한 알고리즘

1. 토큰 버킷 알고리즘

토큰 버킷이라는 지정된 용량(버킷 크기)을 갖는 컨테이너를 활용한다. 이 버킷에는 사전 설정된 양의 토큰(토큰 공급률)이 주기적으로 채워진다. 토큰이 꽉 찬 버킷에는 더 이상의 토큰은 추가되지 않는다. 각 요청은 처리될 때마다 하나의 토큰을 사용한다. 요청이 도착하면 버킷에 충분한 토큰이 있는지 검사하게 된다.

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

이 알고리즘의 핵심은 버킷 크기, 토큰 공급률 2개의 인자이다.

버킷 크기 : 버킷에 담을 수 있는 토큰의 최대 개수
토큰 공급률 : 초당 몇 개의 토큰이 버킷에 공급되는가

버킷은 몇개를 할당해야 하는가? 🧐
case 1 : 사용자마다 하루에 한 번만 포스팅 제한, 친구는 150명까지 추가로 제한, 좋아요 버튼은 다섯 번으로 제한 ==> 사용자마다 3개의 버킷
case 2 : IP 주소별로 처리율 제한 ==> IP 주소마다 버킷
case 3 : 시스템의 처리율을 초당 10000개로 제한 ==> 1개의 버킷

장점
1. 구현이 쉽다.
2. 메모리 사용 측면에서 효율적이다.
3. 짧은 시간에 집중되는 트래픽도 처리 가능하다. 버킷에 남은 토큰이 있기만 하면 요청은 시스템에 전달될 것이다.

단점
1. 두 개의 인자를 적절하게 튜닝해야 하는데 이는 까다로울 수 있다.

2. 누출 버킷 알고리즘

토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정되어 있다는 점이 다르다. 누출 버킷 알고리즘은 보통 FIFO 큐로 구현한다. 요청이 도착하면 큐가 가득 차 있는지 확인한다.

if 빈자리가 있는 경우 : 큐에 요청을 추가한다.
if 빈자리가 없는 경우 : 요청은 버려진다.
그리고 해당 큐에서 고정 속도로 요청들을 처리하게 된다.

누출 버킷 알고리즘의 핵심은 버킷 크기, 처리율 2개의 인자이다.

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

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

단점
1. 단시간에 많은 트래픽이 몰리는 경우 큐에는 오래된 요청들이 쌓이게 되고 그 요청들을 제때 처리 못하면 최신 요청들은 버려지게 된다.
2. 두 개의 인자를 적절하게 튜닝해야 하는데 이는 까다로울 수 있다.

3. 고정 윈도 카운터 알고리즘

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

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

하지만 이 알고리즘의 가장 큰 문제는 윈도의 경계 부근에 순간적으로 많은 트래픽이 집중될 경우 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있다는 것이다.

분당 최대 5개의 요청만을 허용하는 시스템이다. 타임라인 윈도 2:00:00 ~ 2:01:00와 2:01:00 ~ 2:02:00 에 각각 5개 씩의 요청이 들어왔다. 윈도 위치를 2:00:30 ~ 2:01:30 로 옮겨보면 1분 동안 시스템이 처리한 요청은 10개로, 허용 한도보다 많이 처리한 것을 알 수 있다.

장점

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

단점

윈도 경계 부근에서 일시적으로 많은 트래픽이 몰려드는 경우, 기대했던 시스템의 처리 한도보다 많은 양의 요청을 처리하게 된다.

4. 이동 윈도 로깅 알고리즘

이동 윈도 로깅 알고리즘은 앞서 고정 윈도 카운트 알고리즘의 단점을 해결한다. 동작 원리는 다음과 같다.

이 알고리즘은 요청의 타임스탬프를 추적한다. 타임스탬프 데이터는 보통 redis의 정렬 집합 같은 캐시에 보관한다.
새 요청이 오면 만료된 타임스탬프는 제거한다. 만료된 타임스탬프는 그 값이 현재 윈도의 시작 시점보다 오래된 타임스탬프를 말한다.
새 요청의 타임스탬프를 로그에 추가한다.
로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달한다. 그렇지 않은 경우에는 처리를 거부한다.

이에 대한 구체적 사례는 아래와 같다. 이 예제의 처리율 제한기는 분당 최대 2회의 요청만을 처리하도록 설정되었다.

1. 요청이 1:00:01에 도착했을 때, 로그은 비어 있는 상태다. 따라서 요청은 허용된다.
2. 새로운 요청이 1:00:30에 도착한다. 해당 타임스탬프가 로그에 추가된다. 추가 직후 로그의 크기는 2이며, 허용 한도보다 크지 않은 값이다. 따라서 요청은 시스템에 전달된다.
3. 새로운 요청이 1:00:50에 도착한다. 해당 타임스탬프가 로그에 추가된다. 추가 직후 로그의 크기는 3으로, 허용 한도보다 큰 값이다. 따라서 타임 스탬프는 로그에 남지만 요청은 거부된다.
4. 새로운 요청이 1:01:40에 도착한다. [1:00:40, 1:01:40] 범위 안에 있는 요청은 1분 윈도 안에 있는 요청이지만, 1:00:40 이전의 타임스탬프는 전부 만료된 값이다. 따라서 두 개의 만료된 타임스탬프 1:00:01과 1:00:30을 로그에서 삭제한다. 삭제 직후 로그의 크기는 2이다. 따라서 1:01:40의 신규 요청은 시스템에 전달된다.

장점

어느 순간의 윈도를 보더라도, 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않는다. 따라서 매우 정교한 알고리즘이다.

단점

거부된 요청의 타임스탬프도 보관하기 때문에 다량의 메모리를 사용한다.

5. 이동 윈도 카운터 알고리즘

이동 윈도 카운터 알고리즘은 앞서 고정 윈도 카운터 알고리즘과 이동 윈도 로깅 알고리즘을 결합한 것이다.

처리율 제한 장치의 한도가 분당 7개 요청으로 설정되어 있고, 이전 1분 동안 5개의 요청이, 그리고 현재 1분 동안 3개의 요청이 왔다고 해보자. 현재 1분의 30% 시점에 도착한 새 요청의 경우, 현재 윈도에 몇개의 요청이 온것으로 보고 처리해야 할까? 다음과 같이 계산한다.

현재 1분간의 요청 수 + 직전 1분간의 요청 수 * 이동 윈도와 직전 1분이 겹치는 비율

이 공식에 따르면 현재 윈도에 들어 있는 요청은 3+5*70% = 6.5개다. 반내림(or 반올림)하여 그 값은 6이다. 따라서 해당 예제의 경우 처리율 제한 한도가 분당 7개 요청이라고 했으므로, 현재 1분의 30% 시점에 도착한 신규 요청은 시스템으로 전달될 것이다.

장점