[Rate Limit - step 4] Fixed Window 알고리즘 구현 (rate limiting)
필자는 현재 API서버를 열심히 개발 하고 있다. 개발한 서비스가 트래픽을 많이 받다보니, 트래픽을 적절히 제한하지 않았을 때 장애가 발생했고, 그에 따라 API의 Rate Limit을 구현해야 했다.
공부하다보니 흥미가 생겨 나중에 내가 다시 챙겨보기 위해 글을 정리하려고 한다.
Rate Limit시리즈의 목차는 다음과 같다.
[Rate Limit - step 1] Rate Limit이란? (개념, Throttling, 분산환경에서의 구현)
[Rate Limit - step 2] Leaky Bucket 알고리즘 구현 (rate limiting) (p.s. memory estimation 하는 법)
[Rate Limit - step 3] Token Bucket 알고리즘 구현 (rate limiting)
[Rate Limit - step 4] Fixed Window 알고리즘 구현 (rate limiting) <- 이번 글
[Rate Limit - step 5] Sliding Window 알고리즘 구현 (rate limiting)
본 글은 step 4로 Rate Limit의 대표적인 알고리즘 중 하나인 Fixed Window 알고리즘에 대해 알아본다.
개인적으로 이전 시리즈 글 들을 읽고 보는 것을 추천한다. 물론 이것만 보고도 알 수 있지만, 더 잘 이해할 수 있을거라 생각한다.
Fixed Window 알고리즘
1. 버킷에는 정해진 시간 단위로 window가 만들어진다.
2. window에 요청 건수가 기록된다
3. 해당 window의 요청 건수가 정해진 건수보다 크면 해당 요청은 처리가 거부된다.
위 그림은 Fixed Window로 시간당 10번 호출로 ratelimit 설정 후 1:40에 요청이 들어왔을 때 각 시나리오 별로 요청이 어떻게 처리되는지에 대한 예시다. 각 라인 별로 다른 예시기 때문에 숫자를 잘 읽어보길 바란다.
Fixed Window의 장점
1. 구현이 쉽다.
2. memory efficient하다.
3. new request의 starvation이 발생하지 않는다.
Fixed Window 단점
1. 기간 경계의 트래픽 편향 문제 : 설정한 경계의 시간대에 요청이 오면 두 배의 부하를 받게 된다.
2. distributed환경에서 그냥 그대로 사용할 경우 race condition이 발생할 수 있다. (뒤에 더 자세히 다룰 예정)
Fixed Window 샘플 코드
from time import time, sleep
class FixedWindow:
def __init__(self, capacity, forward_callback, drop_callback):
self.current_time = int(time())
self.allowance = capacity
self.capacity = capacity
self.forward_callback = forward_callback
self.drop_callback = drop_callback
def handle(self, packet):
# check if we're in the current time frame or not.
if (int(time()) != self.current_time):
# if we're not in the current time frame, update the current_time and reset the allowance.
self.current_time = int(time())
self.allowance = self.capacity
# check if we have any allowance left.
if (self.allowance < 1):
# drop the packet if we don't have any allowance left.
return self.drop_callback(packet)
# in this part, we already know that there is allowance left, so we remove one from the allowance and forward the packet.
self.allowance -= 1
return self.forward_callback(packet)
def forward(packet):
print("Packet Forwarded: " + str(packet))
def drop(packet):
print("Packet Dropped: " + str(packet))
throttle = FixedWindow(1, forward, drop)
packet = 0
while True:
sleep(0.2)
throttle.handle(packet)
packet += 1- 1 packet per second형태의 구현체
자 이렇게 Rate Limit 시리즈의 알고리즘 중 하나인 Fixed Window 알고리즘에 대해 알아보았다. 필자는 실제로 본 시리즈에서 소개한 알고리즘을 현재 내가 개발하고 있는 API 서비스에 적용해보았고, 서비스의 안정성을 높여볼 수 있었다. 각 알고리즘마다 장단점이 있고, 내 서비스의 특성에 따라 다르게 적용해야 할 수 있으니 본 시리즈의 글들을 다 읽어보는 것을 추천한다!!
참고 자료
https://www.mimul.com/blog/about-rate-limit-algorithm/
https://dev.to/satrobit/rate-limiting-using-the-fixed-window-algorithm-2hgm