Rate Limit, Leaky Bucket, Token Bucket Algorith

출처: https://etloveguitar.tistory.com/128

Rate Limit

 

Rate Limit: 일정 시간 내 클라이언트가 할 수 있는 요청의 수, 정책

ex) 1분당 60회의 임계치, 60회 넘어가면 에러 리턴

필요성: 안정성, 신뢰성, 가용성, 보안, 운영 비용 관리, 공정성(서버 자원 독점 방지), 과금 BM

Throttling: 임계치를 넘어서 에러를 리턴

Throttling의 구현 방식

1. Hard Throttling: 엄격한 관리
2. Soft Throttling: 특정 %까지 허용 (ex. 10%일 때 rate limit 100회이면 110회까지 허용)
3. Elastic or Dynamic Throttling: 리소스의 여유에 따라 rate limit 넘긴 요청 허용

Rate Limit의 요구 조건: 임계치까지만 요청을 허용하고 넘어서면 에러 반환, 트래픽이 많아져도 정상 동작해야하고 지연되지 않아야한다.

 

구조:

Client ↔ Load Balancer ↔ Rate Limiter ↔ Cached Storage ↔ Backend Storage

                        ↑

                 App Server

 

1. Load Balancer가 Rate Limiter에게 Rate Limit 조회

2. Rate Limiter는 두 개의 Storage에서 Rate Limiting Data 관리

3. Load Balancer의 요청에 따라 Rate Limit 여부 리턴

4. Rate Limit을 초과했으면 App Server에 요청을 전달하지않고 Client 요청 거절

 

App Server 분산 환경에서는 Race Condition이 발생할 수 있어 Synchronization이 필요하다.

---

Leaky Bucket

 

Leaky Bucket: Flow Control의 대표적인 알고리즘으로, 일정한 처리속도와 요청의 양을 제어하는 방법.

양동이의 구멍: 서버의 지속적인 처리 속도

양동이의 깊이: 서버가 처리 가능한 요청의 양

 

동작 방식:

1. 요청이 Queue에 들어온다.
2. Queue에 요청이 가득하지 않다면 요청을 받아들인다.
3. Queue에 요청이 가득하다면 요청을 거절한다.

Request Processor ← |R1|R2|R3|R4| ← R5 ← R6 ← R7

                                          Queue

 

R1이 처리되면서 R5는 받아들이고 R6, R7은 거절한다.

 

특징: 일정한 속도로 요청을 처리한다.

---

Token Bucket

 

Token Bucket: Leaky Bucket과 유사하지만, Bucket을 Queue로 사용하지않고 토큰을 관리하는 용도로 사용한다.

버스트 요청의 처리도 가능하다.

토큰을 일정 속도에 맞춰 추가한다. (ex. 1분에 10개라면 6초에 1개씩 추가)

토큰: 트래픽을 제어하기 위한 수단.

토큰 1개 당 1개의 요청을 받아들인다.

 

방식:

1. 버킷에 토큰이 존재하면 요청을 허용하고, 부재하면 에러를 리턴한다.
2. 토큰은 정해진 속도에 맞춰 리필된다.
3. 특정 시간 동안 모든 토큰을 다 사용한 유저는 요청을 허용하지않는다.
4. 토큰 리필 속도에 맞춰 액세스 속도를 제어한다.

특징: 버스트 요청에 대한 처리가 가능하다.