Rate Limiters at Scale

A rate limiter sits on the hottest path in your architecture — every request from every client passes through it — and its latency budget is brutal: it must decide allow/reject in well under a millisecond, because it is a tax on every request, not a feature of one. The algorithm choice determines burst behavior, memory cost, and how much traffic slips past the limit.

Token bucket: burst-aware and memoryless

The token bucket is two numbers per client: capacity b (the bucket size) and refill rate r (tokens per second). Each request consumes one token; tokens accumulate up to b. A client can burst b requests instantly, then settles into r sustained. It is the default for API gateways (Kong, AWS API Gateway, nginx limit_req with burst) because one integer per key is cheap and the burst semantics match real APIs — mobile clients reconnect and need to catch up.

Its weakness is memorylessness: a client idle for an hour has a full bucket and can dump b requests at once. If the limit exists to protect a downstream with real per-second capacity, a full-bucket burst of 10,000 at t+0 is not gentler than 10,000 spread evenly — it's worse.

Fixed window: Redis INCR, one atomic script

The fixed window is a counter per key per window; in a distributed system it is usually one Redis key:

-- fixed window counter, atomic in Lua
local wkey = KEYS[1] .. ":" .. math.floor(tonumber(ARGV[2]) / 60)
local c = redis.call("INCR", wkey)
if c == 1 then redis.call("EXPIRE", wkey, 61) end
if c > tonumber(ARGV[1]) then return 0 else return 1 end

INCR is atomic, and pairing it with EXPIRE inside one Lua script closes the check-then-act race of a naive INCR-then-check. The failure mode is the boundary burst: limit requests at 59.999s plus limit more at 0.001s — 2× the limit in two seconds. Acceptable for most APIs; exactly what attackers look for otherwise.

Redis is the workhorse for a reason: a single instance does 100k-1M ops/s, and the limiter's full cost is one network round trip (0.1-0.5ms in-region, ~1-2ms across AZs). At 100k req/s that's a dedicated instance — real deployments shard the keyspace or accept per-node approximation instead.

Sliding log: exact, and exactly as expensive as it sounds

The sliding log stores every request timestamp per client (a Redis sorted set) and counts entries inside the true sliding window. It is the only algorithm here that's exact — no boundary burst, no approximation. The cost is memory proportional to traffic, not clients: one client at 1,000 req/s against a 60-second window holds 60,000 timestamps (~4MB in a sorted set with score and member). Multiply by the number of abusive clients and the limiter becomes the biggest consumer in your fleet. It's the right choice only when exactness is a product requirement — quota billing, compliance — and traffic per key is low.

The sliding window counter is the pragmatic middle: keep the current and previous window counters and weight them linearly by time elapsed into the current window. Two keys per client, constant memory, no boundary burst (the approximation error is bounded by one window of rate). Most commercial gateways that claim "sliding window" actually ship this.

Distributed limits: exactness vs latency

A single-node limiter is trivial. The distributed problem is real: N gateway nodes behind a load balancer, each with its own token bucket, and a client can hit any of them. Three honest options:

1. Shared state (Redis): exact global limits; every request pays 1-2ms and one dependency. The dependency is the catch — if Redis dies, you must decide fail-open (limits vanish) or fail-closed (all traffic blocked). Fail-open plus a local fallback limiter is the sane default.
2. Per-node shards: each node enforces limit/N independently. Zero coordination, zero extra latency, and N× the actual limit when the fleet is imbalanced — plus the effective limit silently changes whenever N changes (a scaling event shifts the limit mid-flight).
3. Approximate gossip / periodic sync: nodes exchange local counters every few seconds. Smooths the error to a few percent, adds a background channel, and still lets any single node be hammered within a sync window.

The engineering truth: exact global limits at internet scale cost either latency or coordination. Production systems almost always pick option 1 for strict quotas (billing) and option 2 for protective limits (abuse defense), because an approximate 10% overrun by real users is cheaper than a 1.5ms tax on every request.

What survives to production

The algorithm is the visible part; the operational contract is the hidden one. Log only rejects, not passes (passes are 100x the volume). Return Retry-After on 429s so clients back off in sync instead of retry-storming at t+0. And remember the limiter's real job: it's not fairness, it's protecting a shared resource from its own users — which is why the limit should be derived from the downstream's measured capacity, not a round number from a design doc.