Token Bucket and Leaky Bucket — Rate Limiting, Quotas & Abuse Protection

Token bucket: a bucket holds up to capacity tokens and refills at rate tokens/second; each request consumes a token. It allows bursts up to capacity while enforcing the average rate — the most common API limiter (AWS API Gateway, Stripe). Leaky bucket: requests enter a queue that drains at a constant rate — it smooths traffic to a steady flow (traffic shaping), adding latency instead of rejecting until the queue is full.

Bucket algorithms

Criterion	Token bucket	Leaky bucket (queue)
Bursts	Allowed up to capacity	Absorbed by queue, output steady
Excess traffic	Rejected (429)	Queued, then rejected when full
Latency added	None	Queueing delay
State	tokens + last refill time	Queue + drain rate
Typical use	API rate limits	Outbound shaping (calls to a provider), NGINX limit_req

-- KEYS[1]=bucket  ARGV: capacity, refill_per_sec, now_ms, cost
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local cap, rate, now, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[4])
local tokens = tonumber(b[1]) or cap
local ts = tonumber(b[2]) or now
tokens = math.min(cap, tokens + (now - ts) / 1000 * rate)
local allowed = tokens >= cost
if allowed then tokens = tokens - cost end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(cap / rate * 1000) + 1000)
return { allowed and 1 or 0, math.floor(tokens), math.ceil((cost - tokens) / rate) }

import "golang.org/x/time/rate"

limiter := rate.NewLimiter(rate.Limit(10), 20) // 10 req/s, burst 20
if !limiter.Allow() {
    w.Header().Set("Retry-After", "1")
    http.Error(w, "Too Many Requests", http.StatusTooManyRequests)
    return
}

limit_req_zone $binary_remote_addr zone=api:10m rate=10r/s;
server {
  location /api/ {
    limit_req zone=api burst=20 nodelay;   # nodelay: serve bursts immediately, reject beyond
    limit_req_status 429;
  }
}

Common pitfalls

Using server time from different hosts in a shared bucket (clock skew) — use Redis TIME or a single clock.
Capacity so large it defeats the limit.
Leaky bucket queues that hold requests past client timeouts.

Key points

Token bucket: bursts + average rate
Leaky bucket: smoothing/shaping
Atomic updates (Lua) for shared buckets

Bucket algorithms

Common pitfalls

Key points

Practice questions