Token Bucket

이 알고리즘의 핵심 아이디어는, "요청을 처리할 수 있는 토큰(Token)을 미리 정해진 속도로 버킷(Bucket)에 채워두고, 요청이 들어올 때마다 토큰을 소모하여 요청을 처리하는 방식" 이다.

간단하게 비유하면, 충전식 교통카드와 비슷하다.

• 버킷(Bucket): 교통카드. 카드에 충전할 수 있는 최대 금액(토큰)이 정해져 있다.

• 토큰(Token): 교통카드에 충전된 잔액이다.

• 토큰 공급기(리필속도, Refiller): 일정 시간마다(예: 1초에 1,000원씩) 카드에 잔액을 자동으로 충전하는 장치

교통카드에 잔액(토큰)이 있어야만 버스를 탈 수 있고, 잔액이 없으면 탈 수 없다. 카드는 계속해서 자동으로 충전되지만, 최대 충전 한도(버킷 크기)를 넘어서는 금액이 쌓이지는 않는다.

동작 방식

1. 버킷 생성: 각 사용자(또는 IP)마다 정해진 크기(Capacity)의 버킷을 만든다. 이 버킷은 토큰을 담는 역할을 한다.

2. 토큰 공급: 정해진 속도(Refill Rate)로 버킷에 토큰을 주기적으로 추가한다. 예를 들어, "1초에 1개씩 토큰을 추가"하는 방식이다. 버킷이 가득 차 있다면 더 이상 토큰은 추가되지 않는다.

3. 요청 처리 및 토큰 소모: 요청이 들어오면, 버킷에 토큰이 있는지 확인한다.

4. 한도 확인:

   • 허용 (Allow): 버킷에 1개 이상의 토큰이 있다면, 토큰 1개를 사용하고 요청을 처리한다.

   • 거부 (Deny): 버킷에 토큰이 없다면, 요청을 거부한다.

👍 장점

• 유연한 트래픽 제어 (Burst 트래픽 허용): 요청이 없는 동안 토큰이 버킷에 계속 쌓인다. 덕분에 사용자는 순간적으로 몰리는 요청(Burst) 을 모아둔 토큰만큼 처리할 수 있다. 예를 들어, 1초에 1개씩 토큰이 채워지고 버킷 크기가 10이라면, 10초 동안 요청이 없다가 한순간에 10개의 요청을 보내도 모두 처리된다. 이는 전체 평균 요청률은 유지하면서도 일시적인 트래픽 폭증에 유연하게 대응할 수 있게 해준다.

• 직관적인 로직: 알고리즘의 동작 방식이 "토큰을 채우고, 사용한다"는 개념으로 매우 직관적이어서 이해하기 쉽다.

• 높은 예측 가능성: 토큰이 채워지는 속도가 고정되어 있어, 장기적으로 시스템이 처리할 수 있는 평균 요청량을 예측하기 쉽다.

👎 단점

• 구현 복잡성: 여러 상태를 함께 관리해야 한다. 각 사용자마다 버킷 크기(Capacity), 현재 토큰 수(Token Count), 그리고 마지막 토큰 리필 시간(Last Refill Timestamp) 이라는 3가지 상태를 모두 기록하고 관리해야 하므로 구현이 상대적으로 복잡할 수 있다.

• 메모리 사용량: 관리해야 할 상태가 많기 때문에, 사용자 수가 많아질수록 더 많은 메모리를 사용하게 된다.

💥 결과: 토큰 버킷 알고리즘은 순간적인 트래픽 폭증은 허용하면서도 전체적인 평균 요청률은 제어하고 싶을 때 매우 효과적인 방식이다. API 게이트웨이나 네트워크 트래픽 제어 등에서 널리 사용되는 정교한 Rate Limiting 기법 중 하나이다.