Rate limiting: algorithms, the boundary burst, and the Redis counter

The limit is “100 requests per minute per API key” and the dashboard swears it is enforced. Then a customer pushes 380 requests through in two seconds and every one returns 200 OK. Nothing is broken in the limiter code — it works perfectly on one node. The problem: there are four app servers behind the load balancer, each running its own in-memory counter, so the real limit is 400/min. The extra 180 came from a client that hammered the window boundary across all four nodes at once. The limit was never real; it was four separate limits that happened to share a name.

Fixed window: cheap, and it leaks a 2x burst

The simplest limiter keys a counter by {key}:{minute} and does INCR; if the value exceeds the limit, reject. One integer per key, O(1), trivial to reason about. It is also the one every senior has been burned by, because of the boundary.

A fixed window resets on a wall-clock edge. If the limit is 100/min, a client can send 100 requests at 12:00:59.9 and another 100 at 12:01:00.1 — 200 requests inside a 200ms span, and both bursts are legal because they fall in different windows. The worst case is exactly 2x the configured limit concentrated at the seam between two windows. For a coarse internal throttle that is fine. For abuse protection or anything downstream-sensitive, that 2x is the difference between “protected” and “fell over.”

Sliding window: log is exact, counter is the cheap approximation

The sliding window log fixes the boundary by storing a timestamp for every request (a Redis sorted set), dropping entries older than the window, and counting what remains. It is exact — the limit is enforced over any rolling 60s, not a fixed minute. The cost is memory: a client doing 10k req/min holds 10k timestamps, and you pay ZADD plus a ZREMRANGEBYSCORE trim on every call. At scale the log is the memory hog you regret.

The sliding window counter is the production compromise. Keep two fixed-window counters — current and previous — and estimate the rolling count as current + previous * (overlap fraction). It is an approximation, but a famously good one: Cloudflare measured roughly 0.003% error across ~400 million requests, with two integers per key instead of thousands of timestamps. That accuracy-for-near-nothing trade is why it is the default in most edge limiters.

Token bucket: model the burst instead of fighting it

Real API traffic is bursty — a user opens a page and fires twelve requests at once, then idles. Token bucket embraces this. A bucket holds up to capacity tokens and refills at a steady rate (say 100 tokens/min); each request spends one token, and a request is rejected only when the bucket is empty. A client that sat idle accumulates tokens up to the cap, so it can spend a burst instantly, then is throttled to the refill rate. You enforce an average rate while allowing short spikes — which is exactly what a friendly API wants. It needs only two stored values (current tokens, last-refill timestamp), which is why Stripe and AWS use it as the general default.

Leaky bucket is the mirror image: requests drip out at a fixed rate regardless of how they arrive, smoothing traffic to protect a fragile downstream. The cost is that it adds queuing latency on the client’s side and refuses to let legitimate bursts through. Use it when the thing behind you needs a constant, predictable rate more than it needs responsiveness.

Distributed: the counter has to be shared, and atomic

The Hook bug is the one that bites in production. An in-memory limiter is correct on a single process and silently wrong the moment you scale horizontally — each of N nodes enforces the limit independently, so the effective limit is N times what you configured, and a client spreading requests across nodes blows straight through. The fix is to move the counter to a shared store, almost always Redis, so every node reads and writes the same number.

But shared is not enough — it has to be atomic. The naive fixed-window approach is INCR then EXPIRE, and that is a race: two requests can both INCR, and if the process dies between INCR and EXPIRE the key never gets a TTL and the counter leaks forever. The robust pattern is a single Lua script, which Redis runs atomically — the whole read-decide-update cycle happens with no other command interleaved, so concurrent requests cannot double-spend tokens. A token-bucket check in Lua is a handful of operations and runs in sub-millisecond time, cheap enough to sit on the synchronous request path even at millions of requests per second.

-- token_bucket.lua  — KEYS[1] = bucket key, ARGV = rate, capacity, now, requested
local key       = KEYS[1]
local rate      = tonumber(ARGV[1])   -- tokens added per second
local capacity  = tonumber(ARGV[2])   -- max tokens (the burst size)
local now       = tonumber(ARGV[3])   -- current time, seconds
local requested = tonumber(ARGV[4])   -- tokens this request costs

local bucket    = redis.call("HMGET", key, "tokens", "ts")
local tokens    = tonumber(bucket[1]) or capacity
local ts        = tonumber(bucket[2]) or now

-- refill based on elapsed time, capped at capacity
local elapsed   = math.max(0, now - ts)
tokens          = math.min(capacity, tokens + elapsed * rate)

local allowed   = tokens >= requested
if allowed then tokens = tokens - requested end

redis.call("HSET", key, "tokens", tokens, "ts", now)
redis.call("EXPIRE", key, math.ceil(capacity / rate) * 2)
-- return allowed flag + retry-after seconds for the 429
local retry = allowed and 0 or math.ceil((requested - tokens) / rate)
return { allowed and 1 or 0, retry }

The 429 contract and the thundering herd

When you reject, the response is a contract, not just a status. Return 429 Too Many Requests with Retry-After (seconds, computed from when the next token frees up) so well-behaved clients back off instead of retrying in a tight loop. Add the RateLimit-* fields the IETF is standardizing — RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset — so clients can self-pace before they hit the wall. Crucially the draft specifies RateLimit-Reset as delta-seconds, not a UNIX timestamp: a timestamp would require client clock sync, and it would tell every throttled client to retry at the same absolute instant — a self-inflicted thundering herd at the reset boundary.

That herd is the second production trap. With a fixed window and a hard Retry-After of “32 seconds,” thousands of throttled clients all wake and retry in the same moment, hammering you at the boundary. The mitigations: prefer a sliding/token-bucket model where capacity frees up continuously rather than all at once, and add jitter — spread Retry-After values across a small random range so clients return staggered instead of in a synchronized wave. Decide your per-key dimension deliberately too: per-API-key is fair to paying customers, per-IP catches anonymous abuse but punishes everyone behind a corporate NAT, and per-endpoint lets you protect an expensive route without throttling cheap ones.