Rate Limiting Algorithms

The shape of what you allow

Rate limiting answers one question: given a stream of requests keyed by some dimension (per-user, per-IP, per-API-key, per-endpoint, or global), do I allow or reject the next one? The interesting part is the shape of what you allow. Two systems can both permit "100 requests per minute" and behave completely differently at the second scale.

Token bucket is the usual default because it is burst-friendly. A bucket holds up to B tokens and refills at R tokens per second. Each request removes one token; if the bucket is empty, reject. A client that has been idle accumulates up to B tokens, so it can fire a burst of B instantly, then settle to the steady rate R. You store just two numbers per key: the current token count and the last-refill timestamp, refilled lazily on each access (tokens = min(B, tokens + elapsed * R)). Capacity B sets the maximum burst; R sets the long-run rate. This is what most APIs want: allow natural bursts, cap sustained abuse.

Leaky bucket is the opposite intent: it smooths output. Requests enter a queue and drain at a fixed rate, so downstream sees a perfectly steady stream. Use it when the thing you protect cannot absorb bursts at all (a payment processor with a hard TPS ceiling). The cost is added latency and a queue to manage.

Fixed window counts requests per aligned interval and resets at the boundary. Trivially cheap (one integer per key per window), but it has the boundary spike: a client can send the full quota in the last second of one window and the full quota in the first second of the next, delivering 2x the intended rate across a two-second span.

Sliding-window log stores a timestamp per request and counts those in the trailing window: exact but memory-heavy (1000 req/min = 1000 stored timestamps). The practical compromise is the sliding-window counter: keep the current and previous fixed-window counts and weight the previous one by how much still overlaps the trailing window (count = current + previous * overlap_fraction). It kills the boundary spike with roughly the memory of fixed window.

Interview nuance: the response contract matters as much as the algorithm. On rejection return HTTP 429 Too Many Requests with a Retry-After header and the standard RateLimit headers (RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset) so well-behaved clients back off. Decide fail-open vs fail-closed: if the limiter's state store is unavailable, do you allow traffic (protect availability, risk overload) or block it (protect the backend, risk an outage)? Most public APIs fail open on the limiter and rely on downstream load shedding as the real backstop.

token bucket (burst-friendly)        fixed window (boundary spike)
  cap B, refill R/sec                  [--59 reqs--|--59 reqs--]
  idle -> save up to B tokens                    ^ 118 in ~1s
  req  -> take 1 or 429                sliding-window counter fixes it

Recap: default to token bucket for burst-friendly per-key limits, use sliding-window counter when you need window accuracy without the log's memory, avoid raw fixed window for anything abuse-sensitive, and always return 429 plus Retry-After and RateLimit headers with a stated fail-open or fail-closed policy.