처리율 제한 알고리즘

토큰 버킷(Token Bucket)

토큰 버킷(Token Bucket)은 네트워크 트래픽이나 시스템 자원을 관리하기 위해  사용되는 속도 제한(Rate Lmiting) 알고리즘이다.

주로 요청 처리 속도를 일정하게 유지하거나 과도한 사용을 방지하는 데 활용 된다. 

 

 

 

 

 

동작원리

bucket 이라는 토큰을 담는 컨테이너

토큰 공급기는 주기적으로 bucket에 토큰을 채워줌 

토큰이 꽉찬 버킷에는 토큰 추가되지 않고 버려진다.

각 요청마다 하나의 토큰 사용(토큰이 있는 경우 버킷에서 토큰을 할당, 충분한 토큰이 없는 경우 해당 요청 drop)

 

장/단점

• 간단함, 유연성(버스트 허용시), 평균 속도 유지.
• 버스트로 인한 부하, 세밀한 제어 부족, 설정의 복잡함

 

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

토큰 버킷과 비슷하게 트래픽제어나 속도제한(Rate Limiting)에 사용되는 알고리즘이지만, 동작 방식과 특징에서 차이가 있다.

누출 버킷은 물이 담긴 양동이에 비유할 수 있다. 양동잉 바닥에 작은 구멍이 있어 물이 일정한 속도로 새어 나가고, 물(데이터)이 양동이에 너무 빨리 들어오면 넘치게 된다.

동작원리

버킷에 데이터 입력

일정한 속도로 출력 

버킷이 비었을때  - 새 데이터가 들어올떄까지 아무 액션도 일어나지 않는다.

트래픽 평활화 - 데이터가 갑자기 많이 들어와도 버킷에서 나가는 속도는 같다.

 

장/단점

• 출력 트래픽 평활화,  시스템 과부하 덜 취약(일정한 출력 속도), 간단한 구현(토큰 버킷 대비)
• 버스트 불허용, 데이터 손실 가능성 (버킷이 꽉차면 버려짐), 지연 발생(데이터 쌓이면 대기시간이 늘어난다)

 

고정 윈도 카운터 알고리즘(fixed window Counter)

속도 제한(Rate Limiting)을 구현하는 데 사용되는 간단한 방법중 하나이다. 주로 API 요청이나 네트워크 트래픽 제어 활용, 시간단위를 고정된 윈도로 나누어 처리량을 관리한다.

 

 

 

동작원리

시간 윈도 설정 - 시간을 고정된 간격으로 나눈다 ex)  1분을 하나의 윈도로 설정

카운터 관리 - 각 윈도 마다  카운터가 있어 들어오는 요청 추적하여 관리

요청 처리 - 요청이 들어오면 카운터 1씩 증가 (최대 허용치 넘지 않게 처리하면 넘을 경우 거부하거나 대기)

윈도 리셋 - 정해진 시간이 지나면 윈도가 끝나고 카운터가 0으로 리셋 되며 새로운 윈도가 시작된다.

 

 

장/단점

• 구현이 간단하고 메모리 효율성이 좋다. 예측 가능성(고정된 시간동알 일정 요청수 보장)
• 윈도 경계문제(윈도 끝과 시작 점이 트래픽이 물릴경우 동작 하지 않을 수 있음)
• 유연성이 부족하고, 짧은시간 단위 제어가 어려움

이동 윈도 로깅 알고리즘(sliding wondow log)

고정 윈도 카운터 알고리즘의 단점을 보완하기 위해 개발되어졌다.

 

동작원리

타임스탬프 추적 - 각 요청의 타임스탬프를 기록 하고 캐시(redis)에 저장

만료된 타임스탬프 제거 - 새로운 요청이 들어오면 현재 윈도의 시작 시점보다 오래된 타임스탬프 제거

새 요청 타임스탬프 추가 - 새로운 요청의 타임스탬프 로그 추가

요청 처리 결정 - 로그의 크기가 허용치보다 작거나 같으면 요청을 시스템에 전달 아닌경우 거부

 

장/단점

• 호용되는 요청의 개수는 시스템 처리율 한도를 넘지 않는다. 
• 짧은시간 에 몰리는 트래픽에도 대응 가능
• 거부된 요청의 타임스탬프도 보관하여 다량의 메모리가 필요할 수 있다.

 

이동 윈도 알고리즘(sliding wondow counter)

고정 윈도 카운터 +  이동 윈도 로그 결합 한 방식

 

 

동작원리

현재 윈도 요청 수 계산- 현재 시간부터 과거 특정 시간까지 요청 수 계산.

이전 윈도 요청 수 계산 - 이전 시간부터 과거 특정 시간까지 요청 수 계산

가중 평균 계산 - 현재 윈도와 이전 윈도의 요청수를 가중 평균하여 현재 윈도 요청 수 추정

요청 처리 결정 - 추정된 요청 수가 허용치보다 적거나 같으면 요청을 시스템에 전달 그렇지 않으면 요청 거부

 

 

장/단점

• 짧은시간 몰리는 트래픽에도 대응 가능, 메모리 효율이 좋다.
• 이전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기에 다소 느슨.

 

실제 스프링부트에서 사용가능한 대표 라이브러리들은 

Bucket4j - 토큰 버킷 알고리즘 기반 java 속도 제한 라이브러리로 동시lock-free한 구현으로 멀티스레딩 환경에서 확정이 우수하면 추가적인 동시성 전략도 제공.

Guava - 구글에서 개발한 라이브러리로 토큰 버킷 알고리즘 기반

RateLimitJ - 이동 윈도 알고리즘 기반. java 속도제한 라이브러리

 

 

 

특정 업체의 요청량이 워낙 적어서  개발중이 서버에는  이동 윈도 알고리즘(rateLimitJ)을 적용하여    초당 제한량을 제한하여 최대한 안전성 을 높여 처리하도록 구현하였다.