[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://medium.com/@NlognTeam/design-a-scalable-rate-limiting-algorithm-system-design-nlogn-895abba44b77

https://dev.to/satrobit/rate-limiting-using-the-fixed-window-algorithm-2hgm​