Rate limiting looks like a solved checkbox — “add the middleware” — until the incident review where the limiter itself was the problem: it let a double burst through at a window boundary, or it hammered Redis into the ground, or it returned bare 429s that taught every client to retry instantly in lockstep. The algorithm space is small and worth knowing exactly, because each option fails in a characteristic way.

The Window Family, and Its Boundary Problem

Fixed window — a counter per (key, minute) — is one INCR with TTL and everyone’s first implementation. Its defect is structural: a client sending its full limit at 11:59:59 and again at 12:00:01 moves 2× the limit in two seconds, perfectly legally. Whether that matters depends on why you limit: for billing-ish fairness, fine; for protecting a fragile backend from bursts, it’s the whole failure.

Sliding window log fixes it exactly — store a timestamp per request (a Redis ZSET; ZREMRANGEBYSCORE the tail, ZCARD to count) — at O(rate) memory per key, which is real money at scale. The industry-standard compromise, sliding window counter, keeps two fixed windows and weights the previous one by overlap (prev × 63% + curr at 37% into the window): one counter’s memory, boundary spike smoothed to a small approximation error. Cloudflare famously runs this at edge scale.

The Bucket Family: Rate and Burst as Separate Dials

The token bucket is the one to internalize, because it makes the two policy questions explicit — sustained rate (refill: r tokens/sec) and burst tolerance (capacity: b). And it needs no timer thread; lazy refill is three lines:

text
  on request:
    tokens = min(b, tokens + (now - last) * r);  last = now
    if tokens >= 1: tokens -= 1; allow
    else: deny (or compute wait time)

An idle client accumulates up to b tokens — bursts are forgiven, by design and by dial. Its sibling the leaky bucket enforces the opposite: a queue drained at fixed rate, output perfectly smooth, no burst ever — right for pacing writes into a fragile downstream, wrong for user-facing APIs (nobody enjoys being smoothed). GCRA — the elegant single-timestamp formulation from ATM networking — is leaky/token math unified, and it’s what the better Redis limiter libraries actually implement. This family is everywhere the stakes are real: tc and traffic policers are token buckets; nginx limit_req is leaky-bucket with a burst= queue and the much-misunderstood nodelay (forgive the burst without pacing it); GitHub/Stripe-class APIs advertise bucket semantics in their headers.

Distributed: Now It’s a Consistency Problem

One process, one bucket — easy. N gateway replicas sharing a limit face a genuine trade:

  • Centralized state (Redis, atomic via Lua): exact, adds a round-trip on the hot path, and the limiter becomes a dependency with its own failure story. The decision nobody writes down until the outage: fail open or fail closed when Redis is gone? (Protecting a fragile backend → closed; protecting revenue → open. Decide in a design review, not mid-incident.)
  • Local buckets × N: zero latency, limit enforced only approximately (N× worst case if traffic is unbalanced) — often fine, since infrastructure protection is approximate by nature.
  • The grown-up hybrid: local enforcement with async global reconciliation (Envoy’s global limiter + local descriptors, or periodic quota redistribution) — bounded error without a synchronous dependency.

Whichever you pick, the response contract decides whether limiting stabilizes or destabilizes the system: return 429 (or 503 for “protect me” cases) with Retry-After, publish RateLimit-Remaining/-Reset-style headers so well-behaved clients pace themselves, and remember the counterparty: clients must treat 429 as back off with jitter, never retry-now — a fleet of naive retriers converts a rate limiter into a synchronized load generator (the retry-storm incident every large platform has had). Limit by the key that matches the resource you’re protecting (token/tenant first, IP as fallback — CGNAT makes pure-IP limits punish neighborhoods), and exempt health checks before, not after, the first 3 a.m. page.

Takeaways

  • Fixed windows leak 2× at boundaries; sliding-window-counter is the cheap accurate compromise; window-log is exact at O(rate) memory.
  • Token bucket separates rate from burst and runs on lazy-refill arithmetic; leaky bucket smooths — pick by whether bursts are a feature or the threat; GCRA unifies both.
  • Distributed limiting is a consistency choice: exact-central, approximate-local, or reconciled-hybrid — and fail-open vs closed is a policy decision to make in advance.
  • The response is part of the algorithm: 429 + Retry-After + quota headers, and jittered client backoff, or you’ve built a retry amplifier.
  • Key by the protected resource; per-IP alone punishes NAT’d crowds and misses distributed abuse.