# Rate Limiting: Token Buckets, Burst Math, and the 429 You Deserve

> Fixed windows let 2x through at the boundary, token buckets are three lines of arithmetic, and the distributed version is a consistency problem wearing an ops costume. The algorithms, their failure modes, and what to return when you say no.

URL: https://harshith.in/blog/rate-limiting-algorithms/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: distributed-systems, systems, algorithms

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.