Token Bucket Algorithm Explained

Deep dive into the token bucket rate limiting algorithm. Refill rates, burst capacity, Redis implementation, and production tuning.

Deep Dive: The Token Bucket Algorithm

The Token Bucket algorithm is the most widely deployed rate limiting strategy in production APIs because it balances average rate enforcement with a tolerance for sudden, natural traffic bursts.

1. How the Algorithm Works

Imagine a bucket with a maximum capacity $C$ that holds tokens.

1. Token Refill: Tokens are added to the bucket at a constant refill rate $r$ (tokens per second) up to capacity $C$.
2. Token Consumption: When a request arrives, the limiter checks if the bucket contains enough tokens. If yes, it consumes the tokens (usually 1 token per request) and allows the request. If not, the request is rejected (HTTP 429).
3. Timestamp Refills: Instead of running a background loop that constantly increments tokens, modern limiters calculate refills lazily on request arrival:

$$\text{New Tokens} = \min(C, \text{Current Tokens} + (\Delta t \times r))$$

where $\Delta t$ is the elapsed time since the last request.

2. Redis Lua Script Implementation

To execute this logic atomically in Redis without race conditions, developers use Lua scripts:

`lua

local key = KEYS[1]

local capacity = tonumber(ARGV[1])

local refill_rate = tonumber(ARGV[2])

local now = tonumber(ARGV[3])

local requested = tonumber(ARGV[4])

local state = redis.call('HMGET', key, 'tokens', 'last_refill')

local tokens = tonumber(state[1])

local last_refill = tonumber(state[2])

if tokens == nil then

tokens = capacity

last_refill = now

end

local elapsed = (now - last_refill) / 1000.0

local refilled = math.min(capacity, tokens + (elapsed * refill_rate))

if refilled >= requested then

redis.call('HMSET', key, 'tokens', refilled - requested, 'last_refill', now)

return 1 -- Allowed

end

return 0 -- Blocked

`

3. Benefits and Drawbacks

• Pros: Tolerates sudden traffic bursts (up to bucket capacity $C$) without artificial throttling. Very fast to evaluate (lazy calculation).
• Cons: If $C$ is too high, a client can execute a massive burst of requests, potentially overwhelming downstream database connection pools.

4. Common Execution Pitfalls

• Time Synchronization: In multi-server environments, drift in system clocks can lead to incorrect refill calculations. Centralizing calculations on Redis timestamps prevents this.