Rate limiting: four algorithms, two philosophies

Rate limiting decides, for a stream of requests, which ones may proceed and which must wait or be refused — so that a resource (CPU, a downstream service, a quota, a human inbox) is consumed at a rate it can survive. Every design answers three questions: what is counted (per IP, per user, per API key, per recipient — the key defines who shares a budget), how the budget refills, and what happens to the excess.

Fixed window. Count requests in discrete time buckets (this minute, this hour). Over the limit → refuse. Cheapest to implement (one counter per key per bucket) and easy to reason about. Its known hole is the boundary: a client can fire the full quota at the end of one window and again at the start of the next, doubling the instantaneous rate.

Sliding window. Count over a rolling span ending now, so no fixed boundary exists to straddle. Two implementations: a log of timestamps (exact, but memory grows with traffic) or the weighted estimate — previous window's count weighted by how much of it still overlaps the rolling span, added to the current window's count (approximate, constant memory). Sliding window is fixed window with the boundary hole closed, at the price of either memory or exactness.

Leaky bucket. Requests join a queue that drains at a constant rate. Excess is not refused but delayed (until the queue is full). The outflow is perfectly smooth no matter how bursty the inflow is. This is shaping: it protects things that are hurt by bursts themselves — a fragile downstream, a third-party API with a strict queries-per-second cap.

Token bucket. A bucket holds up to N tokens and refills at a steady rate; each request spends tokens, and proceeds if enough are there. The long-term rate is capped by the refill, but saved credit can be spent at once: bursts up to the bucket size pass immediately. This is admission with a burst allowance — the dual of leaky bucket. (The two are meter-equivalent: water level in one is capacity minus token balance in the other, the equivalence the GCRA formulation makes exact. The behavioural difference is where the burst goes — a token bucket lets it through now; a queued leaky bucket converts it into waiting.)

The two philosophies underneath. Policing drops or rejects the excess (fixed/sliding windows, token bucket) — the caller learns immediately, usually as HTTP 429 with a Retry-After hint. Shaping delays the excess (leaky bucket, job-level snoozing) — nothing is refused, but latency absorbs the burst. Which one is right depends on whether the caller can use a refusal (retry later, back off) or whether refusal loses something irreplaceable (a queued email, a paid-for job).

Failure policy is part of the design, not an afterthought. A limiter depends on a counter store; when that store is unreachable the limiter must choose: fail open (let traffic through — availability wins, right for public read surfaces) or fail closed (refuse — protection wins, right for login and other brute-force targets). A limiter that has not decided this has decided it accidentally.

Distributed counting is the hard part, not the algorithm. If requests land on many machines, a shared central counter is exact but adds a round trip (and a dependency) to every request; per-node local counters are fast but only approximate the global limit (N nodes × local limit ≠ global limit). Most real systems pick exactness for small, security-critical surfaces and approximation for bulk traffic. Algorithms also compose: a coarse long-window quota on top, a fine short-window or token bucket below, because each layer answers a different question — how much in total, at what rhythm, with how much burst.