Design a Rate Limiter for an API Service

Problem Design a rate limiter that throttles requests to an API per client (API key or IP) to protect backend capacity, with configurable limits of the form N requests per M seconds.

Functional requirements

• Enforce a configurable limit per client key.
• Allow different limits per tier/endpoint.
• Return 429 with Retry-After and remaining-quota headers.
• Share limiter state across all API instances.
• Update limits without a redeploy.

Non-functional requirements

• ~100k requests/sec across ~500 API instances; ~10M distinct client keys.
• Limiter decision must add < 2 ms at p99 — it sits in front of every request.
• Memory: a sliding-window log at 100k/sec over 60 s = 6M timestamps; bucketed counters keep it to a few counters per key instead.
• The limiter must fail open (or degrade to local limits) if the shared store is unavailable — a limiter outage must not become an API outage.
• Accuracy target: within ~5% of the nominal limit is acceptable; exactness is not worth a distributed lock.

Key components

• Algorithm choice: Fixed Window Counter, Sliding Window Log, Sliding Window Counter, Token Bucket, or Leaky Bucket.
• Shared state: Redis with atomic INCR + EXPIRE, or a Lua script when the check-and-decrement must be atomic as a unit.
• Sharding limiter state by client key so no single Redis node serves all keys.
• Local in-process pre-filter absorbing the obvious cases before the network hop.
• Config service holding per-tier limits, hot-reloadable.
• Edge enforcement (API gateway/CDN) so rejected traffic never reaches origin.

Deep dives / trade-offs

• Algorithms: Fixed Window is one counter and one TTL — trivially cheap, but allows 2x the limit across a window boundary (N at 0:59, N at 1:00). Sliding Window Log is exact but stores every timestamp — memory grows with rate. Sliding Window Counter blends the previous and current window and is the usual production sweet spot: near-exact, O(1) memory. Token Bucket permits bursts up to bucket size then settles to the refill rate, which matches real client behaviour and is friendlier to legitimate spikes. Leaky Bucket smooths output to a constant rate — good for protecting a fragile downstream, bad for latency since it queues.
• Distributed state: Redis makes the count global but adds a hop to every request and becomes a SPOF and a throughput bottleneck at 100k/sec. Local per-instance counters are fast and need no coordination, but with 500 instances each enforcing N, the effective global limit is 500N. Middle grounds: shard by key so one node owns one key, or let instances count locally and sync approximate totals periodically, accepting overshoot.
• Atomicity: a GET-then-SET race lets concurrent requests both pass at the boundary. INCR is atomic; token-bucket refill logic is not, so it needs a Lua script or a Redis data structure that does the whole operation server-side.
• Failure mode: decide fail-open vs fail-closed explicitly. Fail-closed on a Redis blip turns a cache outage into a full API outage; fail-open means an attacker who can kill Redis has removed your limiter. Local fallback limits are the usual compromise.
• Where to enforce: at the edge/gateway rejection is cheapest and protects everything behind it, but the edge may not know per-user tier. Per-service limiting knows more but has already paid for the request.