Rate limiting / quota enforcement

The four classic algorithms differ only in how they treat bursts and how much state they need.

Fixed window counts requests per calendar window (e.g. per minute) and resets at the boundary. It needs one integer per identity but has a fatal edge: a client can send B requests in the last second of one window and B in the first second of the next — 2B in two seconds, double the intended rate.

Sliding-window counter fixes this cheaply: keep the current and previous window counts and compute a weighted estimate — current + previous × (overlap_fraction). It needs two integers and a multiply, has no boundary doubling, and is accurate to within a few percent. This is what Cloudflare popularised for edge rate limiting because it is O(1) and approximate-but-good-enough.

Token bucket is the most flexible: B and R are independent knobs, so you can allow a generous burst (B = 100) on top of a modest sustained rate (R = 10/s). State is two fields. It is the right default for API quotas because real clients are bursty — a page load fires ten requests at once, then nothing for a second.

Leaky bucket is token bucket's mirror: it enforces a constant output rate by draining a queue at R/s. Reach for it only when a downstream genuinely needs a smooth drip (e.g. a third-party API with its own strict steady-rate limit you must not exceed).

The interview-grade summary: token bucket for API quotas, sliding window for cheap edge volumetric limits, leaky bucket for smoothing into a rate-sensitive downstream, fixed window never (except as a crude guardrail).

The single most common production incident with rate limiting is throttling legitimate users — and the cause is almost always the wrong identity axis.

Per-IP is cheap and available pre-auth, which makes it tempting as the primary axis. But a corporate office, a university, or a mobile carrier can put thousands of distinct users behind a single NAT'd IP. Rate-limit that IP and you deny service to an entire building. Per-IP belongs at the edge as a volumetric safety net with a generous threshold, not as the primary fairness mechanism.

Per-API-key is the right primary axis for public APIs: it maps to a billing account and a plan tier. But a single key can represent a whole company with many end users, so within a key you may still need per-user fairness.

Per-user-id is the fairest axis but is only available after authentication. Use it at the app layer to stop one user inside a shared tenant from starving the others.

Per-path is orthogonal to all of the above: GET /search and POST /export have wildly different costs, so they deserve separate budgets even for the same identity. Without it, a flood of cheap requests can exhaust the budget an expensive endpoint needed.

Strong designs layer these and tune each independently. The edge blocks obvious floods, the gateway enforces the plan, and the app enforces fairness and protects expensive paths.

A global limit enforced across a fleet needs shared state, and the default is Redis. The naive approach — GET, check, INCR — has a read-modify-write race: two concurrent requests both read count = 99 against a limit of 100 and both proceed. The fix is an atomic server-side operation: either INCR followed by PEXPIRE (for window counters) or a Lua script that does the whole token-bucket refill-and-spend in one round-trip so no interleaving is possible.

The hot-key problem. A celebrity API key, a viral tenant, or an attacker hammering one identity concentrates all traffic on the single Redis shard that owns that key. Mitigations, in order of escalation:

1. 1Shard by identity hash so different identities land on different shards (helps the aggregate, not a single hot identity).
2. 2Local pre-limiting at the gateway: each gateway enforces a fraction of the global limit locally and only consults Redis to reconcile, cutting the per-request load on the hot shard.
3. 3Dedicated quota shard for known-hot tenants, isolating their load from everyone else.

Latency budget. Each Redis hop is ~0.5–1 ms. If your endpoint's p99 budget is 20 ms, one hop is fine; if it is 2 ms, you need the local-counter variant. Always set a tight timeout on the Redis call (e.g. 50 ms) and a fallback, so a slow Redis can't blow your latency SLO or, worse, queue requests until the pool exhausts.

A limiter on the hot path is itself a dependency, and dependencies fail. The question "what happens when the counter store is down?" separates senior answers from junior ones, because the right answer depends on the business meaning of the limit, not the algorithm.

Abuse guardrails should fail open (or fail to a conservative local bucket). The purpose of a volumetric limit is to protect the origin from a flood. If Redis is down and you fail closed, you have just denied 100% of traffic to defend against a hypothetical flood that may not even be happening — you have DoS'd yourself. Far better to admit traffic (the origin's own capacity and load-shedding become the backstop) or fall back to a generous local bucket.

Commercial quotas may fail closed — but carefully. If over-serving a metered, billable resource (e.g. paid LLM tokens) has real cost, a brief fail-closed window may be cheaper than the over-serve. Even then, a conservative local fallback that reconciles later is usually better than hard rejection.

The discipline is to classify each limit as abuse or quota and document its outage behaviour. State it explicitly in the interview: "volumetric limits fail open with a local fallback; billing quotas fail to a conservative local cap and reconcile on recovery; we never take the API down because the limiter's datastore blinked."

Rate limiting is a collaboration with well-behaved clients, not just a wall against bad ones. The response contract is what makes that collaboration possible.

For per-client quota throttles, prefer `429 Too Many Requests`. For aggregate load shedding or temporarily reduced capacity, 503 Service Unavailable with Retry-After can be the honest answer. Never drop silently (clients are left to guess). Attach:

• `Retry-After` — seconds (or an HTTP date) until the client may retry. This is the single most important header; without it clients retry immediately and amplify the overload.
• Limit metadata — document the fields your API uses, such as recent IETF RateLimit headers or the older X-RateLimit-Limit / X-RateLimit-Remaining / X-RateLimit-Reset convention, so clients can self-regulate before hitting the limit.

On the client side, the contract is exponential backoff with jitter: on a 429, wait Retry-After if present, otherwise back off exponentially with randomised jitter to avoid a thundering-herd retry storm where every throttled client retries in lockstep.

The anti-pattern is the limit that returns a bare 429 with no headers. Clients can't tell whether to retry in one second or one minute, so they guess — usually too aggressively — and turn your protective limit into a retry amplifier.

Not all requests cost the same, and not all clients matter equally under stress. Three refinements separate a staff-level answer.

Cost-weighted (weighted) rate limiting. Instead of "one request, one token," charge tokens proportional to the work a request triggers. A simple GET costs 1 token; a fan-out search across ten shards costs 10; an LLM completion costs tokens proportional to output length. GitHub's GraphQL API does exactly this — it computes a "point cost" per query and debits the budget accordingly, so a single expensive query consumes more of the quota than a cheap one. This aligns the limit with actual resource consumption rather than request count.

Priority-aware load shedding. When the system is genuinely overloaded (not just one client misbehaving), rate limiting blurs into load shedding. Tag traffic by priority — paid before free, interactive before batch, write-path health checks before analytics — and shed the lowest priority first. This keeps the system up for the traffic that matters when capacity is the hard constraint.

Adaptive concurrency and inference budgets. Static RPS limits age badly under autoscaling and dependency drift. Add adaptive concurrency limits (AIMD/gradient, latency or queue-depth based; Netflix's concurrency-limits library is the classic reference), edge/WAF bot controls for abuse traffic, and LLM/inference quotas measured in tokens per minute as well as requests per minute. The mental model: rate limiting enforces fairness per client; load shedding and adaptive concurrency enforce survival under aggregate overload.

Stripe published one of the most-cited engineering posts on production rate limiting. They run two distinct limiter types because they protect against two different failure modes.

The request rate limiter caps requests per second per API key using a token-bucket scheme backed by Redis, with the refill logic implemented as a Redis Lua script so the read-modify-write is atomic. This handles the common case of a client looping too fast.

The concurrency limiter caps the number of in-flight requests per client — because a handful of slow, expensive requests can exhaust capacity even at a low request rate. This is the in-flight semaphore pattern: increment on entry, decrement on exit, with a safety timeout to release permits leaked by crashed requests.

Crucially, Stripe also separates limiters (protect Stripe's own infrastructure, fail toward protecting the system) from load shedders (shed non-critical traffic first when overloaded — they reserve capacity so that critical request types like charge creation are served before less critical ones). Their guidance: build the limiter as a thin, fast, fail-safe layer, and always return clear 429s with retry guidance so clients back off correctly.

Illustrative example: a public API has both cheap reads and expensive fan-out queries. A flat request budget lets one expensive query cost the same as a small lookup, so the limit does not match the work the server performs.

A better design assigns a cost to each request shape, debits that cost from the caller's budget, and documents the response contract. The server returns a clear throttle response, retry guidance when it knows the reset time, and remaining-budget metadata so well-behaved clients can slow down before they are blocked.

The useful lesson is to tie limits to real work and client behaviour. Primary quotas protect fairness, secondary guardrails catch bursts or abusive creation patterns, and headers turn throttling into a protocol instead of a surprise error.

Cloudflare enforces rate limits at the edge across a global network of data centres, where the per-request cost of the algorithm matters enormously because it runs on every request to millions of sites. They popularised the sliding-window counter approach precisely because it is O(1) in storage and computation while avoiding the fixed-window boundary-doubling problem.

The trick: rather than store a precise timestamp for every request (accurate but expensive — that is the "sliding log" approach, which is O(requests) memory), they keep just the count for the current and previous fixed windows and estimate the rolling rate as current_count + previous_count × (overlap fraction of the previous window). This is approximate because it assumes requests in the previous window were evenly distributed, but the memory cost is two integers per key regardless of traffic.

Cloudflare's 2017 post reports an analysis of 400 million requests from 270,000 sources: 0.003% of requests were wrongly allowed or rate limited, the average difference between real and approximate rate was 6%, three above-threshold sources slipped through slightly (less than 15% above threshold), and there were no false positives among mitigated sources. At edge scale, that approximation is the point: an exact sliding log would require storing and scanning a timestamp per request per identity across the whole network. The lesson is that the "best" algorithm depends on where it runs — cheap, O(1), and measured-good can beat exact but O(n).