Design a rate limiter

System design Medium OpenAIGoogleMetaMicrosoft
Reference
Anonymous engineer's solution Endorsed
Switch reference
Start your answer

Remix this answer and make it yours, or start blank. Either way you work beside the reference, one chapter at a time, and it stays private until you publish it.

Sign in to start your answer
Problem statement

Design a service that limits how many requests each API client can make. It sits in front of every API endpoint at high traffic. Remix: limits must hold across three regions.

Requirements

Functional requirements

  • Limit each client (API key, user, or IP) to N requests per window, per endpoint or tier.
  • Return 429 Too Many Requests with Retry-After and X-RateLimit-Remaining headers.
  • Rules change without a deploy (per-customer overrides for enterprise plans).

Non-functional requirements

  • Adds under 2 ms p99 to every request; the limiter sits on the hot path.
  • Works across many gateway instances, so counts must be shared.
  • Fails open: if the limiter store is down, serve traffic rather than reject it.
  • Roughly accurate is fine; a few percent over the limit at the edges is acceptable.

Back-of-the-envelope estimation

  • 1M requests/s at peak across 200 gateway pods, 10M active keys.
  • One counter per (key, rule, window) ≈ 50 bytes → 10M × 3 rules × 50 B ≈ 1.5 GB in memory. Fits in a small Redis cluster.
API design

Internal, called by the gateway: check(key, rule) → {allowed, remaining, reset_at}. Rules are config: {match: "POST /v1/charges", tier: "pro", limit: 100, window: "1s"}.

Data model

Redis keys rl:{rule}:{key}:{window_start} holding a count with a TTL of two windows. Rules live in a config store (e.g. a table plus a pushed cache in each gateway).

High-level design 
flowchart LR
  C[Client] --> G[API gateway]
  G -->|check + incr| R[(Redis cluster)]
  G --> S[Service]
  CFG[Rules store] -. push .-> G
  1. The gateway matches the request to rules from its in-memory rule cache.
  2. It runs one Redis Lua script per rule that increments and reads in one round trip.
  3. Allowed → forward; denied → 429 with headers.
Deep dives

Algorithm choice.

Algorithm Accuracy Memory Notes
Fixed window Bursts of 2× at edges 1 counter Simplest
Sliding log Exact 1 entry per request Too much memory at 1M rps
Sliding window counter ~exact 2 counters Pick this: weight the previous window by overlap
Token bucket Smooth, allows bursts tokens + timestamp Good for "burst of 20, then 5/s" APIs

Sliding window counter: estimate = prev_count × (1 − elapsed/window) + curr_count.

Atomicity. Do the read-increment-compare in a Lua script so two gateways can't both take the last slot.

Hot keys. One huge customer can pin a Redis shard. Shard by key hash, and for the top keys keep a local token bucket per gateway with a share of the global limit (limit ÷ pods), synced every 100 ms.

Failure. Timeout of 5 ms on the Redis call; on timeout, allow and emit a metric. A circuit breaker stops calling Redis when it's down.

Multi-region. Keep limits per region (simplest), or divide the global limit across regions by traffic share and rebalance every few seconds.

Trade-offs
  • Local-only counters are fastest but inaccurate with many pods; central Redis is accurate but adds a hop. The hybrid (local for hot keys, Redis otherwise) gets both.
  • Fail open protects availability at the cost of letting abuse through briefly; for login endpoints, fail closed instead.