Rate Limiting: The Token Bucket Algorithm

The Token Bucket Algorithm: Mechanics and Burst Semantics

Imagine a bucket that holds up to C tokens. Tokens are added to the bucket at a fixed rate of R tokens per second. Each incoming request must consume one token to proceed; if no tokens are available, the request is dropped or queued.

The core invariant is elegantly simple:

• Tokens never exceed the capacity C.
• Tokens are added at rate R per second.
• Every request consumes exactly 1 token.

What makes the token bucket powerful is the burst window. If the bucket is full and no requests arrive for a time, the bucket remains at capacity. When a burst of requests arrives, they are all allowed up to C tokens before the rate limit kicks in. For example, with a capacity of 10 tokens and a rate of 2 tokens/sec, you can accept 10 requests immediately, then only 2 requests per second thereafter. This is critical for real-world traffic patterns: most APIs see bursty clients, and a strict fixed rate of 2/sec would feel like artificial choking. The bucket absorbs the burst, then enforces the long-term rate.

The implementation detail that makes distributed rate limiting hard: in a single-threaded environment, updating the bucket state is straightforward. The current token count is: tokens = min(C, tokens + elapsed_time_sec * R). This is called lazy refill—tokens are not added by a background job but calculated on each request based on the last-refill timestamp. It avoids the cost of background timers and works even under sporadic traffic. However, in a distributed system with multiple servers and concurrent requests, this calculation must be atomic with the token consumption, or two requests may each see sufficient tokens and both proceed when only one should.

Distributed Implementation: Redis and Lua for Atomicity

Most production rate limiters store state in Redis or a similar low-latency key-value store. The core challenge: a naive two-step approach (read current tokens, check and decrement) is not atomic and fails under concurrency.

The solution is to encode the entire decision logic in a Lua script and execute it atomically on the Redis server. A typical script:

local key = KEYS[1]
local now = tonumber(ARGV[1])  -- current timestamp in milliseconds
local rate = tonumber(ARGV[2])  -- tokens per second
local capacity = tonumber(ARGV[3])  -- bucket capacity
local tokens_to_consume = tonumber(ARGV[4])  -- usually 1

local val = redis.call('GET', key)
local tokens, last_refill
if val then
    local parts = cjson.decode(val)
    tokens = parts.tokens
    last_refill = parts.last_refill
else
    tokens = capacity
    last_refill = now
end

local elapsed_ms = now - last_refill
tokens = math.min(capacity, tokens + (elapsed_ms / 1000) * rate)
last_refill = now

if tokens >= tokens_to_consume then
    tokens = tokens - tokens_to_consume
    redis.call('SET', key, cjson.encode({tokens=tokens, last_refill=last_refill}), 'PX', 3600000)
    return 1  -- allowed
else
    return 0  -- rejected
end

This script runs atomically on the Redis server: the read, calculation, and write are a single indivisible operation. Multiple clients contending on the same key are serialized by Redis, eliminating race conditions.

The catch: Redis Lua scripts are single-threaded and can become a bottleneck under extreme traffic (millions of requests per second), and clock skew matters. If a client's clock is ahead of the Redis server’s clock, the Lua script will calculate a spurious refill, allowing more tokens than the rate allows. Defense: use server time (ARGV[1]) supplied by the caller but derived from the server’s clock, and cap the elapsed_ms calculation to avoid wild jumps. In practice, NTP-synchronized clocks drift by only milliseconds, so this is rarely a real problem—but it is worth knowing about.

The Leaky Bucket Algorithm: Memory at a Cost

The Leaky Bucket algorithm models rate limiting differently: imagine a bucket with a hole in the bottom. Requests flow in; tokens leak out at a constant rate R. If the bucket overflows, new requests are dropped. If it is below capacity, they are queued.

Mechanically, this is nearly identical to the token bucket—both enforce a maximum rate and allow some burst capacity—but the intuition inverts: the bucket represents a queue of pending requests rather than tokens. The practical difference emerges in implementation and semantics:

• Token Bucket: Request is allowed immediately if tokens exist; no queuing by the algorithm itself. The client or a downstream queue handles backpressure.
• Leaky Bucket: Requests are queued and drained at a fixed rate. Guarantees a smooth, constant outflow rate regardless of inflow burstiness.

The leaky bucket is ideal when you want to smooth traffic to a backend that truly needs a steady rate—for example, writing to a disk or database with a fixed I/O budget. It guarantees no burst, just a metronomic drain. The cost is higher memory footprint (you must queue all buffered requests) and queuing latency. Most API rate limiters favor the token bucket instead, which permits bursts and avoids the need for a queue.

Fixed Window Rate Limiting and Its Critical Flaw

The simplest rate limiting approach is the Fixed Window: divide time into fixed intervals (e.g., 1-minute windows) and allow up to N requests per window. Implementation is trivial: increment a counter on each request; reject if it exceeds N; reset the counter at the start of the next window.

The catch is a boundary burst vulnerability: consider a 1-minute window with a limit of 60 requests per minute. At 11:59:59, the counter resets. A client can:

1. Send 60 requests in the last second of the 11:59:59–12:00:59 window.
2. Send another 60 requests in the first second of the 12:00:59–12:01:59 window.

The client has effectively sent 120 requests in 2 seconds, a 2x burst over the intended rate. This is often unacceptable for truly critical limits. The severity depends on the window size and the nature of the backend resource: a 1-hour window is more forgiving than a 1-second window, but the flaw is present in every fixed window scheme. Token bucket and leaky bucket do not have this flaw because their refill is continuous, not episodic.

Sliding Window: Better Accuracy, Higher Cost

The Sliding Window algorithm fixes the fixed-window boundary burst by tracking request timestamps. Every request records its timestamp; when a new request arrives, the algorithm counts requests from the last W seconds (where W is the window size) and rejects if the count would exceed the limit.

There are two variants:

Sliding Window Log: Store the exact timestamp of every request in a sorted list or log. When a new request arrives, prune old timestamps outside the window and count the remaining ones. Precise but memory-intensive: each request adds an entry to the log, and the log grows until entries age out of the window.

Sliding Window Counter: Divide the window into small buckets (e.g., 60 buckets for a 60-second window, one per second) and store a counter per bucket. When a new request arrives, calculate a weighted sum of the current bucket and the previous bucket(s) in the window to approximate the count of requests. Lower memory overhead and faster to query, but slightly less precise (it is an approximation, not an exact count). Most production systems use sliding window counter for the balance of accuracy and efficiency.

Sliding window eliminates the boundary-burst problem: the rate limit is enforced across a continuous rolling window, not at discrete boundaries. The trade-off is cost: every request must write a log entry or update a counter, and on high-traffic keys this becomes a contention point. Token bucket avoids this by not tracking individual requests, only aggregate token state—far cheaper at scale.

Comparison and Trade-offs

Each algorithm has distinct properties. Here is a cheat sheet:

For most use cases—API gateways, microservice throttling, DDoS mitigation—the token bucket is the default choice: simple, efficient, and burst-friendly. Leaky bucket makes sense when you control the queue and want to smooth traffic to a backend with a fixed processing rate. Sliding window counter is the pick when you need high accuracy with moderate cost and your traffic is spiky enough that fixed windows would feel wrong.

Use Cases: API Throttling, Traffic Shaping, and Cost Control

Rate limiting is not a monolithic concept; different layers and use cases favor different strategies.

Tiered API Rate Limits: Cloud APIs (AWS, Stripe, GCP) often expose multiple tiers. A free tier might allow 100 requests/minute, a paid tier 10,000/minute. Each tier is a separate rate limit bucket, keyed by API key or user ID. Within each bucket, a token-bucket implementation allows bursts up to the tier capacity. The rate limiter sits at the API gateway and rejects requests with HTTP 429 (Too Many Requests) and a Retry-After header indicating when the client should retry.

Traffic Shaping: ISPs and cloud providers shape traffic to ensure no single customer monopolizes bandwidth. A leaky-bucket approach is common here: enforce a maximum throughput (e.g., 100 Mbps per customer) by draining packets at a fixed rate, dropping excess. The goal is to smooth not just limit; downstream routers and links are easier to operate when traffic is steady.

Protecting Databases and Microservices: Internal rate limits protect backends from cascading failures. If a database connection pool is limited to 100 concurrent queries, a token bucket with capacity 100 and refill rate matching average query latency prevents requests from overwhelming the pool. This is often paired with circuit breaker patterns: if too many requests are rejected, stop accepting new ones upstream to fail fast.

Cost Control: Serverless platforms (AWS Lambda, Google Cloud Functions) meter usage by invocations and compute time. A rate limit on invocations per minute or per day controls costs and prevents runaway bills from a bug or compromised API key. This is typically a fixed window (simple, hard limit) rather than a token bucket, because the goal is strict control, not burst absorption.

HTTP Headers for Clarity: Modern APIs include rate-limit metadata in response headers: X-RateLimit-Limit (the limit), X-RateLimit-Remaining (tokens left), X-RateLimit-Reset (Unix timestamp when the limit resets). Clients can read these headers and back off before hitting the limit, improving the experience and reducing rejected requests. The 429 status code signals that the limit has been exceeded, and Retry-After hints when to retry.

Choosing a Rate-Limiting Strategy

When designing a rate limiter, ask these questions:

Is your traffic bursty? If yes, token bucket is the answer. It allows short bursts while enforcing a long-term rate, matching real-world traffic patterns. Fixed window and leaky bucket are worse here.

Do you need accuracy or simplicity? Token bucket is simpler and cheaper at scale. Sliding window counter offers higher accuracy if boundary bursts are a deal-breaker. Sliding window log is the most precise but also the most costly; use it only if you need to audit every single request.

Is memory a constraint? Token bucket and fixed window use O(1) memory per key. Sliding window counter uses O(window_size_in_buckets). Sliding window log and leaky bucket (with queuing) use unbounded memory in the worst case.

Is the backend truly best protected by a smooth rate? If you have a database with a fixed query throughput and you want to avoid its queue overflowing, leaky bucket is the right model. For almost everything else—protecting an API endpoint from abuse, preventing a customer from dominating a shared resource, controlling costs—token bucket is the standard.

Do you have a distributed system? All algorithms work in distributed systems if you store state in a shared cache (Redis, Memcached) and use atomic operations (Lua scripts, CAS loops). Token bucket is still the most efficient: one Redis GET and SET per request, with minimal contention. Sliding window counter requires multiple increments per request. Sliding window log requires SET operations to track timestamps.

In practice, start with token bucket backed by Redis. It is the de facto standard for a reason: it is fast, understandable, and handles the full range of real-world traffic patterns. Optimize or switch algorithms only if profiling shows a bottleneck.