Design a Rate Limiter

Prompt

"Design a rate limiter for our public APIs. Each client gets a quota like 1,000 requests per minute; requests over the quota are rejected. It has to work across all our API servers."

Clarifying questions

• Where does it sit? As a component of the API gateway, in the request path, before the request reaches backend services.
• What is the limit keyed on? Per API key by default; also per user and per IP for unauthenticated endpoints. Multiple rules can apply to one request.
• What kinds of rules? N requests per window (second, minute, hour), plus a burst allowance. Rules are configured by operators and change rarely.
• How exact must it be? Small overshoot (a few percent over quota for a brief moment) is acceptable. Systematic under-counting that lets a client run far above quota is not.
• What happens when the limiter itself fails? Fail open for most APIs (let traffic through) unless the API is marked critical, in which case fail closed.
• Scale? Hundreds of thousands of requests per second across the gateway fleet, millions of distinct clients.
• Response to rejected requests? HTTP 429 with headers describing the limit, remaining quota, and retry-after time.
• Latency budget? The limiter may add at most a millisecond or two to each request.

Requirements

Functional

• Evaluate configured rules for each request and allow or reject it.
• Return limit, remaining, and retry-after information to the client.
• Support rule changes without redeploying the gateway.
• Expose metrics on rejections per client and per rule.

Non-functional

• Very low latency: sub-millisecond in the common case, so the decision must be local or a single fast round trip to a nearby store.
• Highly available; the limiter must never become the reason the API is down.
• Approximately accurate across many gateway nodes; bounded, explainable overshoot.

Back-of-envelope

• Gateway traffic: assume 500,000 requests/s across the fleet. Every request touches the limiter, so the limiter's decision rate is 500,000/s, peak perhaps 1M/s.
• Clients: 10M API keys, of which perhaps 1M are active in any given minute.
• Counter state per active client per rule: key (16 B), count (4 B), window timestamp (8 B) → ~30 B, call it 64 B with overhead. For 3 rules per client: 1M × 3 × 64 B ≈ 200 MB of live counter state. Tiny. A single in-memory store shard could hold it; we shard for throughput and availability, not size.
• Store operations: if every request did one synchronous increment on a shared store, that is 500,000 ops/s. A sharded in-memory store handles this, but the round trip (0.3-1 ms within a data centre) is most of the latency budget, and the store becomes a hard dependency. This number is the motivation for local counting with periodic sync.
• Sync traffic with local counting: 200 gateway nodes each flushing their per-client deltas every 100 ms → 2,000 flushes/s, each carrying maybe 5,000 active keys × 20 B = 100 KB. That is 200 MB/s of aggregate sync traffic, mostly within the data centre. Acceptable, and tunable via the flush interval.
• Rule config: thousands of rules × 200 B, negligible; cached on every node and refreshed on change.