Rate Limiter 시리즈 - 이론편

배경

최근 사내 OpenAPI에 Rate Limiter를 적용하면서, 분산 환경에서 가장 구현이 간편한 Fixed Window Rate Limiter를 설계하고 도입하였습니다. Rate Limiter에는 여러 방식이 존재하는데, 이번 기회를 통해 각 방식의 개념과 특징을 정리하고자 합니다.

Rate Limiter Algorithm

Token Bucket

Token Bucket은 일정 개수의 토큰을 저장하는 버킷(Bucket)을 이용하여 요청을 제어하는 알고리즘입니다. API 요청을 처리하려면 버킷에 남아 있는 토큰이 필요하며, 토큰이 모두 소진되면 추가 요청은 제한됩니다.

동작 방식

토큰 생성 방식

토큰은 1 / 제한 요청량을 단위로 생성됩니다. 예를 들어서, 1분당 10개를 제한한다고 하면 6초에 1개씩 생성합니다.

요청 처리 방식

1. API 요청이 들어왔을 때 버킷에 토큰이 남아있는지 확인합니다.
2. 버킷에 토큰이 존재하면 토큰을 하나 소모하고, 요청을 허용합니다.
3. 버킷이 토큰이 남아있지 않으면 추가 요청은 거부합니다.

장점

1. 구현이 다른 알고리즘에 비해서 상대적으로 간단합니다.
2. 짧은 시간 안에 집중되는 트래픽을 커버 할 수 있습니다.

단점

1. 동시성 문제가 발생 할 수 있습니다.
2. 기준에 따라 버킷에 담아야 할 적절한 토큰 공급량을 정하기 어렵습니다.

예시

1) 토큰이 존재하는 경우

Token Bucket 토큰이 존재하는 경우(1)

2) 토큰이 존재하지 않는 경우

Token Bucket 토큰이 존재하지 않는 경우(2)

Leaky Bucket

Token Bucket이 버킷 내에 있는 토큰을 순서 없이 사용하는 방식이라면, Leaky Bucket은 큐(Queue) 형태로 동작합니다.

동작 방식

1. 버킷의 최대 크기를 지정합니다.
2. 요청이 들어오면 버킷의 남은 공간을 확인합니다.
   1. 공간이 남아 있다면 요청을 큐에 추가합니다.
   2. 공간이 부족하면 요청을 버립니다.
3. 버킷에 담긴 요청이 처리되면 큐에 새로운 공간이 생깁니다.
4. 새로운 요청이 들어오면 다시 큐에 추가합니다. (2-4 반복)

장점

1. 큐의 크기를 제한하여 메모리를 효율적으로 관리 할 수 있습니다.

단점

1. 큐에 쌓인 요청이 제때 처리되지 못하면 이후 요청도 밀릴 수 있습니다.

예시

결제 요청을 처리하는 스레드 풀이 있다고 가정해보겠습니다. 만약 특정 결제 PG사가 장애를 일으켜 스레드들이 요청을 계속 재시도한다면, 이 스레드들이 계속 점유되어 새로운 결제 요청을 처리하지 못하는 문제가 발생할 수 있습니다.

이는 Leaky Bucket에서 큐가 가득 찬 상태로 요청이 지연되어 이후 요청이 차단되는 상황과 유사합니다.

1) Bucket에 공간이 충분한 경우

Leaky Bucket (1)

2) Bucket에 공간이 부족한 경우

Leaky Bucket(2)

Fixed Window Counter

이름에 Window가 포함된 것처럼, 고정된 시간 단위를 기준으로 요청을 제한하는 방식입니다.

시간에 따라 처리 가능한 요청량을 미리 정해두고, 해당 임계치를 초과하면 요청을 거부합니다.

동작 방식

1. 고정된 시간 단위 동안 들어온 요청 수를 확인합니다.
2. 요청 수가 임계치를 넘지 않았다면 요청을 처리합니다.
3. 임계치를 넘었다면 요청을 거부합니다.

장점

1. 시간 단위 기준으로 요청을 제한하므로 구현이 비교적 간단합니다.
2. 고정된 시간 동안 일정한 요청량을 처리하므로 메모리를 효율적으로 사용할 수 있습니다.

단점

1. 시간 경계에서 요청이 집중되는 Traffic Burst 문제가 발생 할 수 있습니다.
2. 초기에 너무 많은 요청이 몰리면 다음 윈도우까지 대기해야 합니다.

예시

1) 정상적으로 처리되고 있는 Fixed Window Counter

Fixed Window Counter(1)

2) 요청이 거부 된 Fixed Window Counter

Fixed Window Counter(2)

3) 짧은 시간에 요청이 몰리는 Traffic Burst 요청

Fixed Window Counter(3)

위 처럼, 한 윈도우의 끝과 다음 윈도우의 시작 지점에 요청이 몰릴 경우 많은 요청이 처리 될 수 있습니다.
예시처럼 0.2초 사이에 10건의 요청이 처리 될 수 있습니다.

4) 윈도우의 시작 시간에 요청이 몰린 경우

Fixed Window Counter(4)

위 처럼 

Sliding Window Log

Fixed Window Counter의 단점을 보완한 알고리즘입니다. 기존 Sliding Window 방식과 동일하게, 시작점과 끝점이 현재 시간에 따라 동적으로 변경됩니다.

동작 방식

1. 현재 시간을 기준으로 시작점과 끝점을 설정합니다.
2. 해당 시간 구간 내 요청 수를 확인합니다.
   1. 임계치를 넘지 않았다면, 요청을 받아들입니다.
   2. 임계치를 초과했다면, 해당 요청과 타임스탬프를 저장하지만 요청은 수행되지 않습니다.

장점

1. 시간이 지남에 따라 시작점과 끝점이 이동하므로 특정 시간 경계에서의 Traffic Burst를 예방 할 수 있습니다.
2. 어떤 시간대이든 균일하게 Rate Limit가 적용됩니다.

단점

1. 요청과 타임스탬프를 함께 저장해야 하므로 기존보다 메모리 사용량이 증가 할 수 있습니다.

예시

정상 처리 되고 있는 Sliding Window Log

Sliding Window Log (1)

Sliding Window가 꽉차서 채울 수 없는 경우

Sliding Window Log (2)

Sliding Window가 꽉찬 상태에서 들어온 요청이 거부되어 남은 경우

Sliding Window Log (3)

요청이 거부 된 경우에도 실패한 요청이 기록되어 있기 때문에 4개의 요청만 수용이 가능합니다.

의문점

Alex Xu의 System Design Interview 책에서는 위와 같은 방식으로 설명되고 있습니다. 그런데, 윈도우 크기 내에서 이미 초과된 요청도 타임스탬프와 함께 저장되며, 이후 윈도우 계산 시 버려진 요청까지 포함된다는 점은 상당히 의문이었습니다. 이로 인해 거부된 요청이 이후 요청에도 영향을 미치기 때문입니다. 그 예시를 살펴보도록 하겠습니다.

Sliding Window Log 의문 (1)

먼저, 앞서 실패한 요청으로 인해서 슬라이딩 윈도우에서 다음 들어오는 요청들이 실패 상태로 남게 됩니다. 그리고, 이후 요청에서도 아래 사진과 같이 거부된 요청이 지속적으로 다음 요청에 영향을 미치게 됩니다.

Sliding Window Log 의문 (2)

Sliding Window Log 의문 (3)

위 사진과 같이 지속적으로 요청이 들어온다면 이전에 실패한 요청들에 의해서 다음으로 들어오는 요청이 지속적으로 실패하게 되고 성공하는 요청이 하나도 없는 상태가 되면서 결과적으로 불필요하게 메모리를 낭비하면서 정상적인 요청의 처리가 불가능해집니다. 의문을 가지고 있는 것은 저 뿐만이 아니라 다른 포럼에서도 논의가 되고 있는 것을 확인 할 수 있었습니다.

https://www.reddit.com/r/AskComputerScience/comments/xktn2j/rate_limiting_why_log_rejected_requests/

From the AskComputerScience community on Reddit: Rate limiting - why log rejected requests' timestamps in Sliding window log alg

위 포럼에서도 거부된 요청을 기록하지 않아야 한다는 의견이 많았습니다. 책에서는 "성공한 요청만을 저장해야 한다."는 내용을 "모든 요청을 저장해야 한다." 로 잘못 기술 했을 가능성이 있을 것 같다는 생각이 들었습니다.

Sliding Window Counter

이름에서 유추할 수 있듯이, Fixed Window Counter와 Sliding Window Logs의 장점을 결합한 방식입니다. 고정된 시간대에서 현재 시간 대비 윈도우 크기를 차지하는 비율을 계산하여, 허용할 수 있는 요청량을 조정합니다.

동작 방식

요청 수 계산 방식

{  (이전 시간대의 window size에서 sliding window가 겹치는 비율) * (이전 시간 대에 sliding window에 포함된 요청 수)  }
+ { (현재 시간대의 고정 window size에서 sliding window가 겹치는 비율) * (현재 시간 대에 sliding window에 포함된 요청 수) }

1. 요청이 들어오면 현재 시간대에서 이전 시간대의 요청과 현재 시간대의 요청 비율을 계산하여 요청 수를 계산한다.
2. 위에서 계산한 요청 수와 Limit Size를 비교한다.
   1. 만약, Limit Size를 넘어섰다면 들어오는 요청을 거부합니다.
   2. 만약, Limit Size를 넘어서지 않았다면 들어오는 요청을 수용합니다.
3. 위 과정을 반복하여 요청을 처리합니다.

장점

1. 고정된 윈도우와 슬라이딩 윈도우를 함께 고려하므로, 특정 시간 경계에서 요청이 몰리는 문제를 줄일 수 있습니다.

단점

1. 비율을 기반으로 요청을 허용하므로, 전체적으로 더 많은 요청이 처리 될 수 있습니다.

예시

Sliding Window Counter (1)

위와 같은 예시는 다음과 같이 계산됩니다. (3 * (7 / 10)s  + (8 * (3 / 10)s ) = 2.1 + 2.4 = 4.9
현재 윈도우 슬라이스에서 8개의 요청이 짧은 시간 내 들어왔지만, 윈도우가 일정한 요청 패턴을 유지한다고 가정하여 계산 된 요청 수가 2.4건으로 조정되었습니다.

 

위와 같이, 예상한 것보다 더 많은 요청이 수용 될 수 있습니다.

마치며

이번 글에서는 Rate Limiter를 적용하기 전 참고한 자료들을 바탕으로 개념을 정리했습니다. 이를 통해 다양한 Rate Limiting 방식과 그 장단점을 살펴볼 수 있었습니다. 다음 글에서는 Rate Limiter를 어떻게 구현했는지에 대해 소개하겠습니다.

 

참고자료

• https://www.reddit.com/r/AskComputerScience/comments/xktn2j/rate_limiting_why_log_rejected_requests/
• https://en.wikipedia.org/wiki/Token_bucket
• https://kdh0518.tistory.com/64#:~:text=Rate%20Limiter%EB%8A%94%20Request%EB%A5%BC,%EB%A1%9C%20%EB%B6%84%EB%A5%98%ED%95%A0%20%EC%88%98%20%EC%9E%88%EB%8B%A4.