Rate limiting is often described as a solved problem—you just count requests and reject when they exceed a threshold. But production systems need something more nuanced: the ability to handle legitimate bursts while still enforcing long-term limits. The token bucket algorithm provides exactly that balance, and it’s the mechanism behind rate limiting in everything from AWS API Gateway to Redis to Cloudflare Workers.

How Token Buckets Work

A token bucket is a container with a fixed capacity that refills at a constant rate. Each incoming request consumes one or more tokens. If tokens are available, the request proceeds. If the bucket is empty, the request is rejected or delayed.

The algorithm has two parameters: bucket capacity and refill rate. A bucket with capacity 100 and refill rate 10 tokens per second allows an immediate burst of 100 requests, then sustains 10 requests per second indefinitely. The capacity acts as burst allowance; the refill rate enforces the long-term average.

This differs from fixed window counters, which reset all quotas at fixed intervals. A fixed window that allows 100 requests per 10 seconds can be gamed: send 100 requests at 9.9 seconds, then 100 more at 10.1 seconds, achieving 200 requests in 0.2 seconds. Token buckets eliminate this boundary exploit because they smooth consumption over time.

Implementation and State Management

The naive implementation maintains a counter and timestamp per user or API key. On each request, calculate how many tokens have been added since the last request, cap the total at the bucket capacity, and subtract the cost of the current request.

def allow_request(bucket, refill_rate, capacity):
    now = time.now()
    elapsed = now - bucket.last_refill
    bucket.tokens = min(capacity, bucket.tokens + elapsed * refill_rate)
    bucket.last_refill = now
    
    if bucket.tokens >= 1:
        bucket.tokens -= 1
        return True
    return False

The challenge is state. Each bucket requires persistent storage that survives restarts and is shared across instances. In-memory stores like Redis are common, but they add latency and failure modes. Distributed rate limiting introduces consistency questions: if two requests arrive simultaneously at different nodes, can both succeed when only one token remains?

Some systems use local buckets with periodic synchronization, accepting temporary over-limit conditions in exchange for lower latency. Others use atomic compare-and-swap operations or Lua scripts in Redis to guarantee correctness at the cost of throughput.

Variants and Tradeoffs

The leaky bucket algorithm is often confused with token bucket but behaves differently. Leaky bucket enforces a strict constant output rate by queuing requests and processing them at a fixed pace, regardless of input timing. Token bucket allows bursts up to the capacity, making it more flexible for APIs where occasional spikes are legitimate.

Hierarchical token buckets support multiple limits simultaneously—per-second, per-minute, and per-hour—by chaining buckets. A request must pass all levels to proceed. This prevents attacks that stay just under each individual threshold but exceed reasonable aggregate usage.

Cost-per-request weighting extends the model to heterogeneous workloads. A lightweight read might cost one token while an expensive batch operation costs 50. The bucket parameters remain constant, but request costs vary based on resource consumption.

When Bursts Matter

The distinction between burst allowance and sustained rate matters most when legitimate usage is spiky. Mobile apps that sync on launch, batch jobs that query APIs in tight loops, and user-facing dashboards that fire parallel requests all benefit from burst tolerance.

Too little capacity creates false positives—rejecting valid users during normal behavior. Too much capacity undermines the rate limit, allowing attackers to inflict damage before exhausting tokens. The right balance depends on understanding real traffic patterns and the cost of serving bursts.

Token buckets solve the core problem of API rate limiting: enforcing average behavior without punishing momentary spikes. The algorithm is simple enough to implement in a few lines but flexible enough to handle complex multi-tier limits and weighted costs. That’s why it remains the standard approach decades after its introduction in network traffic shaping.