Rate Limiting

What it is

A rate limiter decides whether this request is allowed through. It runs on every request — including the ones it is about to reject — so it has to be cheap. And its algorithm has to be judged on what it does to a burst, because steady traffic under the limit passes through every algorithm identically.

Fixed window

Count requests per calendar window and reset at the boundary. One counter per key, trivially cheap, and visibly wrong at the edges: a client that spends its whole allowance just before the reset gets a fresh allowance immediately after, so a 100/minute limit permits 200 requests in a two-second span. The arithmetic was never violated. Set the widget to the boundary burst and watch it happen.

Sliding window log

Store a timestamp for every accepted request and count the ones inside the trailing window. Exactly correct — and the memory grows with traffic, so the busiest clients, the ones you most want to limit, are the most expensive to track. Unusable at volume.

Sliding window counter

Keep the current and previous window's counts and blend them by how far into the current window you are. Two numbers per key, and it approximates the log closely enough that the boundary trick stops working. Slightly inaccurate when traffic within a window is very uneven, which is a good trade.

Token bucket

A bucket holds up to N tokens and refills at a fixed rate; each request spends one. Two numbers per key, and the refill is computed lazily from elapsed time rather than by a timer.

Its burst behaviour is the point rather than a defect: a client that has been idle has a full bucket and may spend it at once, then settles to the refill rate. That is what real clients look like — quiet, then a flurry. Burst size becomes a second dial to tune.

Leaky bucket

Requests enter a queue and drain at a fixed rate. The output is perfectly smooth, which is what an upstream with no burst tolerance wants. It buys that by queueing requests, which adds latency, and it offers no burst allowance at all.

Making it correct across a fleet

Ten gateways each enforcing a limit of 100 enforce a real limit of 1,000. Three ways out: share an atomic counter (correct, one round trip per request, a hard dependency), share local counts periodically (fast, briefly over-permissive), or route each key to a fixed instance (correct locally, uneven load, painful whenever instances change).

Whichever you pick, the read-decide-write must be atomic — GET, decide, SET is a race. And when the counter store is unreachable, fail open: a limiter that takes the whole service down in order to protect it has failed at its job.

What to return

A 429 ("Too Many Requests") with Retry-After, jittered (randomised a little), so every rejected client does not retry in unison. Returning limit, remaining and reset headers on every response — not only rejections — is what actually produces well-behaved clients, because they can slow down before they get rejected at all.

Take this with you

• The one idea: judge a limiter by what it does to a burst. Steady traffic under the limit looks the same under every algorithm.
• In an interview, pick token bucket, explain the fixed-window edge case, and say where the counter lives across many servers.
• At work, send the limit headers on every response, and know whether your limiter fails open or closed when its store is down.