Problem statement
Design a distributed rate limiter that sits in front of a public API and decides, per caller, whether each incoming request is allowed or rejected — enforcing quotas like "1000 requests per minute per API key" across a fleet of stateless gateway nodes (think the throttling layer a large SaaS API puts on every tenant).
Operating context. The API is fronted by 30–60 gateway nodes behind a load balancer, each terminating requests in any region. Callers are identified by an API key (millions of distinct keys, long-tailed: a handful of keys drive most traffic). Aggregate ingress is ~200k requests/sec at steady state with 3× bursts. Each rate check must add p99 < 5 ms to the request. Limits are per-key and per-route, with a few named tiers (free / pro / enterprise). A caller that is over its limit gets an HTTP 429 with a Retry-After hint; an allowed caller passes through untouched.
Out of scope. The API business logic itself, authn/authz of the API key, billing/quota purchasing, an admin UI for editing limits, and DDoS/WAF-layer scrubbing. Assume limit definitions arrive from a separate control plane you may read from.
What to produce. A high-level design covering: where the limiter runs relative to the gateway, the counting algorithm (and why), how per-key counters stay consistent across nodes, the shared-store-vs-local-cache decision and any sync path, how you handle clock skew between nodes, and the behavior when the counter store is slow or unreachable. Sketch the components and the allow/deny request flow; we will drill into the coordination cost and the failure behavior at checkpoints.
Functional requirements
- Given an API key, route, and tier, decide allow or reject for each incoming request against the configured quota.
- Return HTTP 429 with a Retry-After hint when the caller has exceeded its limit for the current window.
- Enforce distinct per-key, per-route limits driven by the caller's named tier (free / pro / enterprise).
- Load and refresh limit definitions from the external control plane without restarting gateway nodes.
- Expose the caller's remaining quota and window reset time (e.g. via response headers) on allowed requests.
Non-functional requirements
- Rate check adds p99 < 5 ms and p50 < 1 ms to each request's latency.
- Sustain ~200k requests/sec aggregate at steady state with 3x bursts (~600k/sec) for tens of seconds.
- Support millions of distinct keys with a long-tailed skew where a few hot keys drive most traffic.
- Limiter availability >= 99.99% for the allow/deny decision; a store outage must not hard-fail the whole API.
- Counting error stays within a small bounded slack (e.g. <= 1% over the nominal limit) under concurrent nodes.
- Correct enforcement despite bounded clock skew (tens of ms) across gateway nodes.
Topics
- System Design HLD
- Data Cache
- Data KV
- Scaling Write-Heavy
- Consistency Eventual