Rate Limiter란? 그리고 방식과 특징

 

1. Rate Limiter란

 

Rate Limiter는 처리율 제한 장치라는 의미로써, 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 컨트롤 하기 위한 장치를 의미한다.

Rate Limiter를 적용하면 서비스에 너무 많은 요청이 몰리는 것을 방지할 수 있고 그로 인해 서비스를 안정적으로 운영할 수 있도록 할 수 있다.

 

 

2. Rate Limiter를 적용하면 좋은점

• 서비스 안정성 유지
  과도한 요청이 몰릴 경우 시스템 과부하를 방지해 서비스 다운이나 성능 저하를 예방.
• 리소스 관리 최적화
  시스템 자원을 특정 사용자나 클라이언트가 독점하지 못하게 하여 공평하게 리소스 분배.
• DDoS 및 비정상 트래픽 방어
  악의적인 대량 요청이나 비정상적인 트래픽을 제한해 보안성 강화.
• 비용 절감
  과도한 요청으로 인한 서버 확장 및 리소스 사용 비용 절감.
• 서비스 품질 보장
  처리량을 제어함으로써 모든 사용자에게 일관된 성능과 안정적인 서비스 제공.
• API 남용 방지
  특정 클라이언트의 과도한 요청을 방지해 시스템을 악용하거나 오용 방지.

 

3. 토큰방식(Toeken Bucket) 알고리즘 

 

토큰 버킷 방식을 간단하게 설명하면 큰 물통에 물이 계속 채워지는 방식이다.

• 물통에 물이 가득 차게 되고 요청이 올때 마다 물통에 물이 하나씩 빠지게 된다.
• 시간이 지남에 따라 주기적으로 물이 채워지게 되고 만약 물통에 물이 가득찬 상태라면 더 이상 물을 채워지지 않게 된다.
• 만약, 토큰이 충분하지 않은 경우(즉, 물통에 물이 없는 경우)에는 해당 요청은 버려지게 된다.

이 과정을 프로세스로 표기하면 다음과 같다.

 

 

4. 누출 버킷(Leaky Bucket) 알고리즘

 

누출 버킷 알고리즘은 버킷 알고리즘과 거의 유사하다. 물통에 물이 채워지고 사용하는 방식은 동일하나 요청 처리율이 고정으로 되어 있다는 점이 다르다. 누출 버킷 알고리즘의 동작 원리는 다음과 같다.

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

이 과정을 프로세스로 표현하면 다음과 같다.

 

 

5. 고정 윈도우 카운터(Fixed Window Counter) 알고리즘

 

시간 단위를 "고정된 윈도우(시간 창)"로 나누어 요청 수를 제한하는 방식이다. 동작 원리는 다음과 같다.

• 고정된 시간 단위(예: 1초, 1분, 1시간)를 기준으로 윈도우를 나눕니다.
• 각 윈도우에서 발생하는 요청 수를 카운터로 기록합니다.
• 요청이 발생할 때마다 카운터를 증가시키고, 설정된 최대 요청 수(Threshold)를 초과하면 새로운 요청은 새 윈도우가 열릴 때까지 버려진다.
• 시간이 지나 새로운 윈도우가 시작되면 카운터는 초기화됩니다.

아래 타임라인을 살펴보면 시스템은 초당 3개의 요청만을 허용할 수 있다. 매초마다 열리는 윈도우의 개수는 3개이며 3개 이상 요청하게 되면 그 초과분은 버려지게 된다.

 

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

예를 들어 분당 최대 5개를 처리한다고 가정한다.

분당 처리이기에 10:00~10:01에 5건이 요청되고 10:01~10:02 사이에 또 다시 5건이 요청 되었다. 이렇게 보면 1분당 5건을 처리한게 맞다.

그러나 위의 그림에서와 같이 각각의 10:00:30에 5건이 순차 인입되고 10:01:30 전까지 5건이 인입되었다고 가정하면

10:00:30~10:01:30는 1분이지만 실제로는 10건이 처리되어 허용 한도를 2배까지 들어오게 되는 문제가 있다.

 

6. 이동 윈도(Sliding Window) 알고리즘

 

시간 창(Window)이 고정된 구간으로 나뉘지 않고, 요청이 발생하는 순간을 기준으로 연속적으로 이동하면서 요청을 제한하는 방식이다.

동작 원리는 다음과 같다.

• 요청이 들어올 때마다 해당 요청의 타임스탬프를 기록한다.
  (이 때 타임스태프 데이터는 보통 레디스의  정렬 집합 같은 캐시에 보관)
• 현재 시간을 기준으로, 설정된 윈도우 크기(예: 1분, 10초) 안에 있는 요청의 수를 계산한다.
• 요청 수가 설정된 최대 허용 값(Threshold)을 초과하면 추가 요청은 버려지게 된다.
• 윈도우는 요청이 들어올 때마다 갱신되며, 과거 윈도우는 자연스럽게 슬라이딩(이동) 된다

예시를 통해 살펴보자. 분당 2개의 처리를 하는 시스템이 있다고 가정하자.

 

• 요청이 10:00:01에 도착하였을 때는, 로그는 빈 상태이므로 이 요청은 허용된다.
• 새로운 요청이  10:00:30에 도착하였다. 타임스탬프가 로그에 추가되었고 로그의 크기는 2가 되며 허용범위이므로 이 요청 또한 허용된다.
• 새로운 요청이 다시 10:00:40초에 도착하였고 이 타임스탬프 역시 로그에 추가되었다. 추가된 이후 로그의 크기는 3이 되었기 때문에 타임스탬프에 대한 로그는 남아있는 상태로 유지하지만 요청은 거부, 즉 버려지게된다.
• 새로운 요청이 10:01:30초에 도착하였다. 이 타임스탬프 역시 로그에 추가된다. 10:00:30~10:01:30 범위 안에 있는 요청이 아닌 이전에 요청된 10:00:01, 10:00:30는 전부 만료된 값이므로 로그에서 삭제한다. 삭제 이후에 로그의 크기는 2이브로 10:01:30 신규 요청은 허용된다.

 

 

7. 이동 윈도우 카운터(Sliding Window Counter) 알고리즘

 

이 방식은 고정 윈도우 카운터 알고리즘과 이동 윈도우 로깅 아록리즘을 결합한 알고리즘이다. 요청 제한(Throttle)을 위해 시간 창(Window)을 연속적으로 슬라이딩(이동)하면서 계산하는 방식이다. 고정된 윈도우와 이벤트가 시간적으로 겹치는 비율을 고려하여 요청 수를 계산하게 된다.

 

동작 원리는 다음과 같다.

• 두 개의 윈도우 계산
  • 현재 요청이 속한 윈도우(즉, 현재 1분간)의  요청 수
  • 직전 윈도우(직전 1분간)  요청 수
• 겹치는 비율 계산:
  • 현재 요청이 속한 슬라이딩 구간과 직전 윈도우가 겹치는 비율을 계산한다.
    (예를 들어, 현재 시점이 1분 윈도우 기준으로 마지막 10초에 해당하면 겹치는 비율은 10/60 = 0.1667이다)
• 가중치 기반의 최종 요청 수 계산:
  • 최종 요청 수 = (현재 윈도우의 요청 수)+(직전 윈도우의 요청 수×겹치는 비율)
    

예를 들어, 1분에 5개의 요청을 처리하는 시스템이 있다.

아래 그림과 같이 현재 시간은 12:01:30이고 아래와 같이 현재 1분간 요청된 건은 3건, 직전 1분간 요청건은 4건이다. 

이 예제를 통해 현재 요청 수를 계산해보자.

 

1. 윈도우 정의:
   • 현재 윈도우: 12:01:00 ~ 12:02:00
   • 직전 윈도우: 12:00:00 ~ 12:01:00
   • 현재 시각: 12:01:30
2. 겹치는 시간 계산:
   • 현재 시각(12:01:30) 기준으로 직전 윈도우와 현재 윈도우가 겹치는 시간:
     • 겹치는 구간은 12:01:00 ~ 12:01:30.
     • 총 겹치는 시간: 30초.
3. 겹치는 비율 계산:
   • 겹치는 비율 = 3060=0.5\frac{30}{60} = 0.56030​=0.5 (60초 기준 30초가 겹침).
4. 요청 수 데이터:
   • 현재 윈도우의 요청 수: 3건.
   • 직전 윈도우의 요청 수: 4건.
5. 최종 요청 수 계산:
   • 계산식: (현재 윈도우 요청 수)+(직전 윈도우 요청 수×겹치는 비율)
   • 대입: 3+(4×0.5)=3+2=5
6. 결론:
   • 최종 요청 수 = 5.
   • 허용 한도(5건)에 도달했으므로, 추가 요청은 제한됩니다.

 

7. 알고리즘의 특징, 그리고 장단점

 

각각의 알고리즘을 정리하면 다음과 같다,

방식	특징	장점	단점
토큰 버킷	- 요청을 처리하려면 토큰이 필요. - 일정 간격으로 토큰이 추가되며 초과 토큰은 버려짐. - 처리량 초과 요청은 거부됨.	- Burst(일시적 트래픽 폭증) 처리 가능. - 평균 속도 제어에 적합.	- 복잡한 구현. - 적절한 토큰 refill rate 설정이 필요.
누출 버킷	- 고정된 속도로 물(요청)이 버킷에서 새어나감. - 요청이 들어오면 버킷에 채워지고 버킷이 가득 차면 거부.	- 요청이 일정하게 처리되도록 보장. - 네트워크 품질 보장에 유리.	- 짧은 시간 동안 요청이 급격히 증가하는 상황(=Burst) 처리에 약함. - 요청이 초과되면 처리 지연 발생.
고정 윈도우 카운터	- 고정된 시간 구간(윈도우) 내에서 요청 수를 카운트. - 윈도우가 갱신되면 요청 수 초기화.	- 구현이 간단. - 트래픽 제어가 명확하고 직관적.	- 윈도우 경계 문제(경계 직후 트래픽 폭증 가능). - 부드러운 제어가 어려움.
이동 윈도우 로깅	- 각 요청의 타임스탬프를 기록. - 주어진 시간 구간 내 요청 타임스탬프를 확인하여 요청 수를 계산.	- 요청 시간 데이터를 정확히 관리. - 부드러운 제어 가능.	- 요청 타임스탬프를 저장해야 하므로 메모리 사용량 증가. - 대량 요청 시 성능 저하.
이동 윈도우 카운터	- 현재 윈도우와 직전 윈도우의 요청 수를 합산하고 겹치는 비율로 가중치 적용.	- 정밀한 트래픽 제어 가능. - 윈도우 경계 문제를 완화. - 메모리 사용량 적음.	- 구현이 복잡. - 겹치는 비율 계산 시 시간 동기화 필요. - 과거 요청 일부만 반영.