Modern API Rate Limiting: Token Bucket vs Leaky Bucket at High Scale

Quick Summary / Direct Answer: Choose the Token Bucket algorithm for APIs requiring burst traffic capacity with steady-state limits. Choose the Leaky Bucket algorithm when upstream services demand completely smooth, jitter-free traffic outflow. Token Bucket allows accumulated credits for spikes, whereas Leaky Bucket strictly queues and paces requests at a constant rate.

Key Takeaways:

• Token Bucket handles traffic bursts gracefully while protecting downstream dependencies from sustained overload.
• Leaky Bucket enforces rigid output pacing, eliminating micro-bursts entirely at the cost of potential latency inflation under load.
• Distributed high-scale implementations typically rely on Redis Lua scripts to maintain atomic state across multiple API gateway nodes.

Architectural Trade-Offs at Scale

When millions of concurrent users hit your microservice mesh, naive rate limiting fails instantly. Race conditions corrupt counters, lock contention brings down memory stores, and sloppy cache invalidation allows malicious traffic spikes through. Designing resilient API gateways requires picking the right traffic-shaping primitive. Most engineering teams narrow this down to two classic algorithms: Token Bucket and Leaky Bucket.

They look identical on paper. Both use a metaphorical container to throttle request rates. Yet their behavioral mechanics under heavy load diverge dramatically. One prioritizes user experience during flash sales; the other prioritizes strict hardware protection for fragile downstream databases.

Token Bucket Mechanics

The Token Bucket algorithm operates on a simple premise. A bucket has a fixed maximum capacity and fills with tokens at a constant refill rate. Every incoming request consumes a single token. If the bucket is empty, the request is rejected with a 429 Too Many Requests status code.

The beauty of this approach lies in its burst tolerance. If a user sits idle for ten minutes, their bucket fills to capacity. When they return, they can execute a sudden burst of requests equal to the bucket size instantly. Once depleted, the client drops back to the steady-state refill rate.

// Conceptual state representation for Token Bucket
type TokenBucket struct {
    Capacity   int64
    Tokens     int64
    RefillRate float64
    LastRefill int64 // Unix timestamp
}

Most tutorials gloss over the edge case of lazy evaluation. Instead of running a background goroutine or timer for every connected user to add tokens—which completely destroys CPU cache locality—production systems compute token counts lazily upon request arrival based on elapsed time delta.

Leaky Bucket Mechanics

Leaky Bucket flips the paradigm. Instead of metering incoming requests against available tokens, incoming requests are dropped into a queue (the bucket). The bucket has a finite volume and a tiny hole at the bottom. Requests leak out of the bucket at a strictly constant, unyielding rate to be processed.

If requests arrive faster than the leak rate, the bucket fills up. Once full, any newly arriving requests overflow and are immediately dropped or rejected. This creates a beautifully smoothed output stream. Downstream legacy services that collapse under the slightest concurrency spike love Leaky Bucket because it completely eliminates request jitter.

Distributed Redis Lua Implementation

Running rate limiters on a single server is trivial. Scaling horizontally behind a load balancer breaks in-memory counters immediately. You need a centralized atomic store. Redis is the industry standard for this pattern, but doing multi-step read-modify-write operations across network calls introduces race conditions.

The solution? Atomic Redis Lua scripts. By executing the calculation and update logic directly inside the Redis engine, we guarantee atomicity without locking the entire keyspace.

-- Redis Lua Script for Token Bucket Rate Limiting
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local requested = tonumber(ARGV[3])
local now = tonumber(ARGV[4])

local data = redis.call('HMGET', key, 'tokens', 'last_updated')
local tokens = tonumber(data[1])
local last_updated = tonumber(data[2])

if not tokens then
    tokens = capacity
    last_updated = now
else
    local delta = math.max(0, now - last_updated)
    local tokens_to_add = delta * refill_rate
    tokens = math.min(capacity, tokens + tokens_to_add)
    last_updated = now
end

if tokens < requested then
    return {0, tokens}
else
    tokens = tokens - requested
    redis.call('HMSET', key, 'tokens', tokens, 'last_updated', last_updated)
    redis.call('EXPIRE', key, math.ceil(capacity / refill_rate))
    return {1, tokens}
end

When deploying this script via your API gateway, ensure you handle Redis connection failures gracefully. If your rate limiting cache goes down, fail open to preserve user availability, or fail closed if you are protecting a mission-critical billing pipeline.

The Bottom Line: Actionable Next Steps

Selecting between Token Bucket and Leaky Bucket comes down to defining your failure modes. If your infrastructure handles high throughput easily but hates jagged traffic spikes, use Leaky Bucket. If your users expect responsive UI interactions that occasionally spike during form submissions or batch syncs, use Token Bucket. Implement your chosen algorithm using atomic Lua scripts in Redis right at the edge of your gateway for maximum performance and minimum latency overhead.