Token Bucket, Leaky Bucket, and GCRA

In one line

A token bucket allows bursts up to its capacity and refills at a steady rate; a leaky bucket smooths output to a fixed rate. Both fit in one small Redis hash updated by a Lua script. GCRA achieves the same with a single timestamp.

0/4 · 0%

Think of it like this

An arcade card that earns one play token every 6 seconds and holds at most 10. Save up and you can play 10 games in a row (burst), but over the long run you can't average more than 10 per minute. A leaky bucket is a funnel: water pours in at any rate but drips out at a steady rate, and if the funnel overflows, the extra is spilled.

Key ideas

01
Token bucket state: tokens and last_refill time. On each request: tokens = min(capacity, tokens + (now − last) × rate); if tokens ≥ cost, subtract and allow; else reject with a retry time of (cost − tokens) / rate. Store both fields in a hash with a TTL of about capacity / rate so idle buckets disappear.
02
Why it's popular: it expresses "average rate plus allowed burst", which matches real API policies (for example 10 requests/sec, bursts of 50), and supports different costs per request (an expensive endpoint costs 5 tokens).
03
Leaky bucket as a meter is mathematically equivalent to a token bucket. Leaky bucket as a queue actually delays requests to release them at a fixed rate, which smooths load for downstream systems (for example a payment provider that allows 20 calls/sec). In Redis, the queue form is a list or stream drained by a worker at a fixed rate.
04
GCRA (generic cell rate algorithm) stores only a "theoretical arrival time" (TAT) per key: allow if now ≥ TAT − burst_tolerance, then set TAT = max(TAT, now) + interval. One number per key, exact, with bursts. The redis-cell module and several libraries use it.
05
Time source: inside Lua, redis.call('TIME') gives the server's time, avoiding app-server clock skew. That's allowed because scripts replicate their effects, not the script itself.

Code & diagrams

token-bucket.lualua

-- KEYS[1] = bucket hash; ARGV: capacity, refill_per_sec, cost
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])
local t        = redis.call('TIME')
local now      = tonumber(t[1]) + tonumber(t[2]) / 1e6

local state  = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity
local ts     = tonumber(state[2]) or now

tokens = math.min(capacity, tokens + (now - ts) * rate)
local allowed = tokens >= cost
if allowed then tokens = tokens - cost end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) * 2)

local retry_after = allowed and 0 or (cost - tokens) / rate
return {allowed and 1 or 0, tostring(tokens), tostring(retry_after)}

gcra.lualua

One number per key. emission = 1/rate seconds; burst = how many requests can arrive at once.

-- KEYS[1] = tat key; ARGV: emission_interval_ms, burst
local interval = tonumber(ARGV[1])
local burst    = tonumber(ARGV[2])
local t        = redis.call('TIME')
local now      = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local tat      = tonumber(redis.call('GET', KEYS[1]) or now)
tat = math.max(tat, now)
local allow_at = tat - interval * burst
if now < allow_at then
  return {0, allow_at - now}                       -- rejected, retry in ms
end
local new_tat = tat + interval
redis.call('SET', KEYS[1], new_tat, 'PX', new_tat - now + interval)
return {1, 0}

buckets.mermaiddiagram

Rendering diagram…

Interview problem

The problem

Limit a partner API: average rate with bursts

Partners may call your API at 10 requests/sec on average with bursts of up to 50. Export calls cost 10 units. Separately, your payment provider allows you only 20 calls/sec. Design both limits.

You're given

10 rps average, burst 50
Export endpoint costs 10
Outbound: max 20 calls/sec to the payment provider

The interviewer follows up

Why use Redis TIME instead of the app's clock?

When it breaks

Token bucket state stored without a TTL

What you see

Millions of idle bucket hashes accumulate from one-time clients; memory grows steadily.

Fix & prevent

Set the TTL to about 2× the time needed to refill completely; a missing bucket simply means "full".

Explain it without notes

Explain how a token bucket allows bursts but enforces an average rate.

What's the difference between a leaky bucket used as a meter and as a queue?

Practice

Load-test the token bucket script: capacity 5, refill 1/sec. Send 10 requests instantly, then one per second for 5 seconds. Predict and verify the results.

Trade-offs

↔
Token bucket: bursts plus average in two fields. GCRA: same behaviour in one field, harder to explain. Leaky queue: protects downstreams by delaying, not rejecting.

Done when you can

I can implement a token bucket and GCRA in Lua using the server clock.
I can choose between rejecting (bucket) and delaying (queue).

Command Palette