System Design: Rate Limiting — Token Bucket Algorithm — Belgavi.AI Lab

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.