rate limiter 설계 : rate limit 알고리즘 5가지

rate limiter는 요청을 일정량 이상 보내지 못하게 제한하는 장치다.

요청이 과하게 몰려 api 서버가 터지는걸 막을 수 있고

특정 클라이언트가 과도하게 요청을 점유하는걸 막을 수 있다.

rate limit 알고리즘엔 여러가지가 있는데 이 책에서는 5가지를 간단하게 소개한다.

 

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

토큰 버킷은 지정된 용량을 갖는 컨테이너.

요청이 오면 토큰을 하나씩 소비하면서 요청을 api서버에 전달.

토큰이 다 떨어지면 요청을 실패시킴.

일정 시간마다 토큰 버킷을 채움

 

장점

1. 구현이 쉬움

2. 메모리 사용 측면에서 효율적

3. 짧은 시간에 집중되는 트래픽ㄷ ㅗ처리 가능.

 

단점

1. 버킷 크기와 토큰 공급률이라는 두 개의 인자를 적절하게 튜닝하기가 어렵다

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

토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정되어 있다.

FIFO큐로 다음과 같이 구현

1. 요청이 도척하면 큐가 가득 차 있는지 본다. 빈자리가 있으면 큐에 추가한다.

2. 큐가 가득 차 있으면 새 요청은 버린다.

3. 지정된 시간마다 큐에서 요청을 꺼내 처리한다.

 

장점

1. 큐의 크기가 제한되어 있어 메모리 사용 측면에서 효율적이다.

2. 고정된 처리율을 갖고 있어 안정적 출력이 필요한 경우에 적합하다.

 

단점

1. 단시간에 많은 트래픽이 몰리면 큐에는 오래된 요청들이 쌓이게 되고, 최신 요청들은 버려진다.

2. 두 개의 인자 (큐 크기, 처리율) 튜닝이 어렵다.

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

타임라인을 고정된 간격의 윈도로 나누고 각 윈도마다 카운터를 둔다.

요청이 들어오면 매핑되는 윈도의 카운터를 증가시키는데 만약 카운터가 한계(threshold)에 도달하면 새로운 요청은 버려진다.

 

윈도 경계 부근에 트래픽이 몰리면 원래 의도했던것보다 훨씬 많은 요청이 처리될 수 있다는 단점이 있다.

가령 초당 10개를 처리하려고 했고 윈도를 1~2초, 2~3초로 나눠놨는데

1.5~2.0초대에 요청 10개가 들어오고 2.0~2.5초대에 요청 10개가 들어오면

1.5~2.5초의 1초 동안 원래 의도했던 요청 10개보다 2배 많은 20개의 요청을 처리하는 일이 발생한다.

 

장점

1. 메모리 효율

2. 이해하기 쉬움

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

 

단점

1. 윈도 경계 부근에서 트래픽이 많이 몰리면 원래 기대했던 것보다 더 많이 처리하게 됨

4. 이동 윈도 로그 (sliding window log)

이 알고리즘은 요청의 타임스탬프를 추적한다.

새 요청이 오면 만료된  타임스탬프는 제거하고 (현재 윈도의 시작지점보다 오래된 타임스탬프)

새 요청의 타임스탬프를 로그에 추가한다.

로그의 크기가 허용치보다 같거나 적으면 요청을 시스템에 전달, 그렇지 않으면 거부.

 

장점

1. 이 알고리즘이 구현하는 처리율 제한 메커니즘은 아주 정교하다.

 

단점

1. 많은 메모리를 쓴다. 거부된 요청의 타임스탬프도 보관하기 때문.

5. 이동 윈도 카운터 (sliding window counter)

두 가지 구현 방법이 있는데 하나만 설명한다.

 

고정 윈도 카운터 알고리즘에 기반한다.

윈도를 고정 간격으로 나누고 카운터를 두는 것까진 똑같다.

다만 새로운 요청이 들어왔을 때 하는 행동이 다른데,

새 요청이 오면 새 요청을 기준으로 현재 이동 윈도를 따로 계산한다.

현재 이동 윈도의 카운터값은

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

이다.

 

장점

1. 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽도 잘 대응한다.

2. 메모리 효율이 좋다.

 

단점

1. 직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨하다.

하지만 클라우드플레어가 실시했던 실험에 따르면 40억개의 요청 가운데 시스템의 실제 상태와 맞지 않게 허용되거나 버려진 요청은 0.003%에 불과했다고 한다.