Design a Distributed Rate Limiter

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.