Rate limiting & quotas

Which rate-limit algorithm to reach for

Four you will be asked about.

Fixed window counts requests in a fixed slot (per calendar minute). In Redis it is INCR key where the key embeds the minute, plus an EXPIRE so old slots clean themselves up. Cheapest option, O(1) memory, but it lets a burst through at the window edge (below).

Sliding window log stores a timestamp per request in a sorted set and counts the ones inside the trailing 60 seconds. Exact, no edge burst, but memory grows with traffic because every request is a stored entry.

Sliding window counter keeps two numbers, the current slot's count and the previous slot's, weighting the previous one by how much of it is still in view. Near-exact at O(1) memory, which is why it is a common production default.

Token bucket refills tokens at a steady rate up to a capacity; each request spends one, an empty bucket rejects. It allows short bursts up to the bucket size while holding the long-run average, so it fits APIs that want to tolerate spikes.

How the fixed-window boundary burst happens

Wrong "A fixed window of 100/min caps each client at 100 per minute." Across the boundary it does not. A client can send 100 in the last second of one minute and 100 in the first second of the next, delivering 200 inside a two-second span. Right the cap holds only within each aligned window, not across the edge. A sliding window (log or counter) smooths the boundary, so reach for it when the burst matters.

What to send the client on a 429

HTTP 429 (Too Many Requests) is the signal. Retry-After may be included, not must, and its value is either a number of seconds or an HTTP date. The current IETF draft also defines RateLimit (with r remaining and t reset-seconds) and RateLimit-Policy (with q quota and w window) as structured fields; the older X-RateLimit-Limit/-Remaining/-Reset trio is a de-facto convention, not the standard. A server may attach these headers to any response, including a 200, so a client can slow down before it hits the wall.

On the client side, honor Retry-After when it is present, otherwise back off exponentially with jitter. Retrying a 429 in a tight loop turns one rejection into a retry storm.

Keying: per-user vs per-IP

Authenticated endpoints key on the API key or user id, which is precise and fair (GitHub's REST API allows 5,000 requests per hour authenticated). Unauthenticated endpoints (login, signup, password reset) have no identity yet, so they fall back to the client IP, the way GitHub caps unauthenticated calls at 60 per hour per address. IP is a weak identity: carrier-grade NAT and shared proxies put many users behind one address, so an IP limit throttles bystanders when one of them misbehaves. Behind your own proxy the socket address is the proxy, so you read X-Forwarded-For, but that header is client-appendable; trust only the hop your proxy added, never the left-most value a client can forge.

Why per-node counters break, and the atomic fix

Wrong "Each app server keeps its own counter, that is fine." Behind a load balancer a client's requests spread across N instances, and N independent counters of 100 each let it send close to 100N. Right the counter has to live in one shared store (Redis) that every node hits on the request path, fast enough to sit synchronously there.

That store has to make the decision atomic. Read the count, compare to the limit, then increment is a check-then-act race: two nodes both read 99, both decide "under the limit", both write 100, and the limit is breached. INCR returns the incremented value in one atomic step, so for a fixed window you INCR and pair it with EXPIRE inside MULTI/EXEC. For token-bucket refill math or sliding-window logic, run the whole read-decide-update as a Lua script via EVAL; Redis runs it atomically, so concurrent requests cannot double-spend a token or lose a counter update. GCRA is the same shape of fix built on a single stored timestamp instead of a counter.

The sliding-window counter and what it costs

The approximation keeps two numbers and weights the previous window by the fraction still in view. Cloudflare's worked case: a 50/min limit, 42 requests in the previous minute, 18 in the current minute that started 15 seconds ago, gives 42 * ((60-15)/60) + 18 = 49.5, under 50, so allowed. Across 400 million requests from 270,000 sources they measured 0.003% of requests decided wrongly and zero false positives. A sliding-window log is exact because it stores every timestamp, but that memory and CPU grows with request volume, which is why the two-counter approximation is the default at scale.

Fail open or fail closed when the limiter is down

If Redis is unreachable, does the request pass or get blocked? Stripe fails open: it catches limiter errors at every level so an outage in the limiter cannot take down the whole API. The trade-off is that protection disappears for the duration of the outage, so a security-sensitive limit (login, password reset) is a reasonable place to fail closed instead. Which way it fails is a design choice with a security dimension, not a default to leave unexamined.

Rate limit vs quota vs load shedding

A rate limit is a short-window rate (per second or minute) for fairness. A quota is a long-window budget (per day or month) tied to a plan; the IETF RateLimit-Policy field can advertise both at once, a burst window and a daily window in one header. Load shedding is a different axis: it sheds traffic on whole-system overload regardless of who sent it, where a rate limit is per-client. Reject early, at the cheapest layer, before the expensive work; running the DB query and then returning 429 burns the resource the limit was protecting. Under overload, accepting everything collapses goodput as clients time out and retry, so shed the excess and honor Retry-After so retries do not amplify into a storm.