처리율 제한 장치 설계 알고리즘

네트워크 시스템에서 처리율 제한장치는 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치이다

특정 기간 내에 전송되는 클라이언트의 요청 횟수를 제한한다

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

이점

• DoS 공격에 의한 자원 고갈을 방지
• 비용 절감
• 서버 과부하를 막는다

설계

클라이언트와 API 서버 사이에 처율을 체크하는 장치를 둔다

 

처리율 제한 알고리즘 종류

1. 토큰 버킷
2. 누출 버킷
3. 고정 윈도 카운터
4. 이동 윈도 로그
5. 이동 윈도 카운터

1. 토큰 버킷 알고리즘

간단하여 이해도가 높고 많은 기업들이 보편적으로 사용

토큰 버킷은 지정된 용량을 갖는 컨테이너, 사전에 설정된 양의 토큰이 버킷에 주기적으로 채워진다

토큰이 꽉 찬 버킷은 더 이상 추가되지 않는다

 

각 요청 시 하나의 토큰 사용 -> 요청 도착 시 버킷에 충분한 토큰이 있는지 검사 -> 있으면 토큰을 하나 꺼내 전달, 없으면 해당 요청은 버려진다

- 인자 -

버킷 크기: 버킷을 담을 수 있는 토큰의 최대 개수

토큰 공급률: 초당 공급되는 토큰의 수

 

버킷의 수는 공급 제한 규칙에 따라 달라짐 (기능별로 구현 가능)

 

단점

버킷 크기와 토큰 공급률이 두 개의 인자를 가지는데 튜닝이 어렵다

 

2. 누출 버킷 알고리즘

토큰 알고리즘과 비슷하지만 요청 처리율이 고정, FIFO(First-In-First-Out)

요청이 도착하면 큐가 가득 차 있는지 확인 -> 비어있으면 큐에 요청 추가, 큐가 가득 차 있으면 요청 버림

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

- 인자 -

버킷 크기: 큐 사이즈

처리율: 지정된 시간 당 몇 개의 항목을 처리할지 지정하는 값(보통 초 단위)

 

장점

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

고정된 처리율을 가지고 있어 안정적 출력이 필요한 경우에 적합

 

단점

단시간에 많은 트래픽이 몰리는 경우 큐에 오래된 요청이 쌓임, 최신 요청들은 버려짐

두 개의 인자를 올바르게 튜닝하기 까다로움

 

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

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

요청이 접수될 때마다 카운터의 값은 1씩 증가

카운터의 값이 사전에 설정된 임계치에 도달하면 새로운 요청은 새 윈도가 열릴 때까지 버려진다

장점

메모리 효율이 좋음

이해하기 쉬움

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

 

단점

윈도의 경계 부근에 순간적으로 많은 트래픽이 집중될 경우 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있음

ex) 1분에 5개를 처리하는 윈도우라 가정, 1분 30초에 5개 2분 30초에 5개 이렇게 들어오면 1분에 10개를 처리함

 

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

요청의 타임스탬프를 추적한다. Redis의 정렬 집합 sorted set과 같은 캐시에 보관

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

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

로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달, 아니면 처리 거부

장점:

처리율 제한 메커니즘은 아주 정규함, 어느 순간의 윈도를 보더라도 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않음

 

단점:

다량의 메모리를 사용하는데 거부된 요청의 타임스탬프도 보관하기 때문(그렇지만 안정성 높지 않나?)

 

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

고정 윈도 카운터 + 이동 윈도 로깅 알고리즘

윈도 계산 방법:

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

1분의 30% 시점에 도착한 요청은 처리, 그 후의 요청은 받을 수 없음

 

장점:

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

메모리 효율이 좋음

 

단점:

직전 시간대에 도착한 요청이 균등하게 분포한 상태에서 추정치 계산, 다소 느슨 but 심각한건 아님

 

 

더 궁금한 점

클라이언트 측 제한 장치는 어떠한게 있나요

고정 윈도 카운터 알고리즘 누출 버킷 알고리즘과 비슷한데 하나는 토큰 하나는 시간의 차이인가요