Design a Rate Limiter

Problem Design a rate limiter for an API that restricts how many requests a client may make within a given time window.

Functional requirements

• Enforce N requests per M seconds per client key.
• Support different limits per tier and per endpoint.
• Return 429 with Retry-After and remaining-quota headers.
• Share limiter state across all API instances.
• Allow limits to change without a redeploy.

Non-functional requirements

• ~50k requests/sec across ~200 API instances; ~5M distinct client keys.
• Decision latency < 2 ms at p99 — it runs before every single request.
• Accuracy within ~5% of the nominal limit is acceptable; exactness is not worth a distributed lock on the hot path.
• Must fail open (or fall back to local limits) if the shared store is down — a limiter outage must never become an API outage.

Areas to go deep

• Choosing among the algorithms (fixed window, sliding-window log, sliding-window counter, token bucket, leaky bucket).
• Burst tolerance as a product decision.
• Distributed shared state, atomicity of the check, and where to enforce.