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.

When you throttle, return `429 Too Many Requests` — never 503 (which implies your fault) and never a silent drop (which forces clients 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.
• `RateLimit-Limit`, `RateLimit-Remaining`, `RateLimit-Reset` — the IETF draft standard headers that let clients self-regulate before hitting the limit, smoothing their own traffic.

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. Two 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. The mental model: rate limiting enforces fairness per client; load shedding enforces survival under aggregate overload. A mature system does both, and a strong candidate names the distinction.

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.

GitHub's REST API enforces 5,000 requests/hour for authenticated users (much lower for unauthenticated, keyed by IP), and every response carries X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset. Clients are expected to read these and self-throttle; GitHub's own documentation tells integrators to watch Remaining and pause before they hit zero.

The more interesting design is the GraphQL API's cost-weighted limit. Because a single GraphQL query can request wildly different amounts of work, GitHub computes a point cost for each query based on the number of nodes it will touch, and debits a 5,000-point-per-hour budget. A trivial query costs 1 point; a deeply nested one fetching thousands of connected objects costs hundreds. This decouples the limit from raw request count and ties it to actual server work — the same query-cost idea that protects expensive endpoints.

GitHub also layers secondary rate limits that catch abusive patterns (too many concurrent requests, too many points per minute, too many content-creating requests) on top of the primary hourly budget — a concrete example of defence in depth.

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 — it assumes requests in the previous window were evenly distributed — but the error is small (single-digit percent) and bounded, and the memory cost is two integers per key regardless of traffic.

At edge scale, that approximation is the entire 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 — at the edge, "cheap, O(1), and 99% accurate" beats "exact but O(n)."