[4장] 처리율 제한 장치의 설계

처리율 제한 장치 (Rate Limiter)

• 클라이언트 혹은 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치.
• ex) HTTP 내에서는 특정 기간 내 전송되는 클라언트 요청 횟수를 제한.
• 임계치(threshold)를 넘어선 요청은 중단(block)됨
  • ex) 사용자는 초당 2회 이상 새 글을 올릴 수 없다.
  • ex) 같은 IP 주소로 하루에 10개 이상 계정 생성을 할 수 없다.
  • ex) 같은 디바이스로 주 5회 이상 리워드를 요청할 수 없다.
• 장점
  • DoS 공격에 의한 자원 고갈 방지.
  • 처리 제한을 통해 비용 절감 가능.
  • 써드파티 API 호출에 따라 사용료를 지불하고 있을 땐 더더욱 횟수를 제한해야 한다.

 

처리율 제한 장치의 요구사항

• 낮은 응답시간 : 처리율 제한 장치로 인해 API 성능 (HTTP 응답시간) 에 영향을 주어서는 안된다.
• 메모리를 적게 사용하자.
• 분산형 처리율 제한 : 하나의 처리율 제한장치를 여러 서버에서 사용할 수 있으면 좋다.
• 높은 결함 감내성 : 제한 장치의 장애가 SPOF가 되어서는 안된다.

 

처리율 제한 장치는 어디에 둘 것인가?

 

• API 서버 측에 제한장치를 둘 수 있고, 미들웨어를 만들어 API 서버로 가는 요청 자체를 통제할 수 있다.
• MSA 에서는 API 게이트웨이에 처리율 제한 장치를 구현함.
  
  • 역할 : 처리율 제한, SSL 종단, 인증&인가, IP 화이트리스트 관리

 

처리율 제한 알고리즘

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

가장 보편적인 알고리즘

• 지정된 용량을 갖는 토큰 버킷(컨테이너)에 토큰이 주기적으로 채워진다. 토큰이 꽉 차면 추가되지 않는다.
• 토큰 공급기가 주기적으로 토큰을 버킷에 추가한다.
• 각 요청이 처리될때마다 토큰을 사용
• 요청이 도착하면 버킷에 토큰이 있는지 검사
  • 토큰이 있다면 토큰을 사용하여 요청을 처리
  • 토큰이 없다면 요청은 버려진다.
• 토큰 버킷 알고리즘의 인자
  • 버킷 크기 : 버킷에 담을 토큰의 최대 개수
  • 토큰 공급률 (refill rate) : 초당 몇개의 토큰을 버킷에 공급하는가
• 장점
  • 구현이 쉽고 메모리 사용측면에서 효율적이다.
  • 짧은 시간에 집중되는 트래픽도 처리 가능하다.,
• 단점
  • 버킷 크기 & 토큰 공급률의 튜닝이 까다롭다.

---

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

토큰 버킷 알고리즘과 유사하나, 요청 처리율이 고정되어 있다. FIFO (Queue) 로 구현됨.

1. 요청이 도착하면 Queue 에 요청을 추가
2. Queue 가 가득차있으면 새 요청은 버린다.,
3. 지정된 시간마다 큐에서 요청을 꺼내 처리

• 누출 버킷 알고리즘의 인자
  • 버킷 크기 : 큐 사이즈
  • 처리율 (outflow rate) : 지정된 시간당 몇개의 항목을 처리할 지 지정하는 값.
• 장점
  • 큐 크기가 제한되어 있어 메모리 사용량 측면에서 효율적이다. 안정적인 출력이 가능하다.
• 단점
  • 단시간에 많은 트래픽이 몰리는 경우 Queue 가 가득차면 최신 요청들이 버려진다.
  • 튜닝이 까다롭다.

---

3. 고정 윈도우 카운터 알고리즘 (fixed window counter)

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

• 장점
  • 이해하기 쉽다.
• 단점
  • 윈도우의 경계부분에 많은 트래픽이 집중될 경우 순간적으로 많은 요청이 처리될 수 있다.

---

4. 슬라이딩 윈도우 로그 알고리즘 (sliding window log)

1. 요청의 타임스탬프 데이터를 캐시에 담아 추적.
2. 새 요청의 타임스탬프를 로깅
3. 로그의 크기가 허용치보다 큰 경우 처리를 거부

• 장점
  • 어느 순간의 window 를 보더라도 허용되는 요청의 개수는 처리율 한도를 넘지 않는다.
• 단점
  • 요청이 거부된 타임스탬프도 보관해야 하기 때문에 메모리를 많이 사용한다.

 

---

5. 슬라이딩 윈도우 카운터 알고리즘 (sliding window counter)

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

알고리즘에서는 현재 윈도에 들어온 요청의 개수를 다음과 같이 구한다.

 

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

• 장점
  • 이전 시간대의 평균 처리율에 따라 현재 윈도우 상태를 계산하므로, 짧은 시간에 몰리는 트래픽에도 대응 가능
  • 메모리 효율이 좋다.