System Design Prepgo pro
System design interview question

Design a Rate Limiter

A distributed service that decides, in under a millisecond, whether a request from a client is allowed under its quota.

Difficulty: medium. Patterns: algorithms, counters, redis, edge. Reported at Stripe, Amazon, Google, Atlassian, Datadog, LinkedIn, Uber.

Study shows every answer; Practice hides them until you have produced your own.

Functional requirements

  • Limit requests per client per rule. Keyed by API key, user id, or IP. Rules like "100 requests per minute per API key on /search".
  • Multiple rules per request. A request can be subject to a per-user, a per-endpoint, and a global rule; all must pass.
  • Return informative rejections. HTTP 429 with Retry-After and X-RateLimit-Limit / Remaining / Reset headers so clients can back off correctly.
  • Rules configurable without redeploy. Operators change limits per tier or customer; changes take effect within seconds.
  • Allow short bursts. A client at 100/min should be able to send 20 in one second, then be throttled, rather than exactly 1.6 per second.
  • Observability. Per-rule accept and reject counts, and a way to see which clients are being throttled.
  • Out of scope. DDoS mitigation at the network layer, WAF rules, and billing quotas measured in days or months (those are a separate metering system).

Non-functional requirements

  • Decision latency (p99 < 1 ms added). The limiter sits on every request; its latency is paid by everyone. It must be a local computation or a single fast cache round trip.
  • Throughput (1 M decisions/s). Across the fleet. Each decision is cheap, so this is about not creating a central bottleneck.
  • Accuracy (within ~5 % of the limit). Slight over-admission under contention is acceptable; systematic under-admission (rejecting legitimate traffic) is not.
  • Availability (fail open). If the limiter's store is unreachable, requests must be allowed (with alerts), not rejected. A broken limiter must not become an outage.
  • Consistency across nodes (shared counters per key). A client hitting 10 gateway instances is limited as one client, not ten.
  • Memory (bounded per key). Millions of keys live at once; per-key state must be a few bytes and expire on its own.
  • Multi-region. Limits are enforced per region by default; global limits are a stated approximation.

Back-of-envelope estimates

  • Decisions per second: ~1 M. Assume the API fleet serves 300 k requests/s at peak and each request evaluates ~3 rules: ~1 M decisions/s. The store must handle that, or the check must be local.
  • Active keys: ~10 M. Say 5 M distinct clients active in any hour × a couple of rules each = ~10 M live counters. Keys expire after their window so the set self-cleans.
  • Memory per key: ~100 B. Token bucket: tokens (8 B) + last refill timestamp (8 B) + Redis key overhead (~60–80 B) ≈ ~100 B. Sliding-window log would be 8 B per request in the window: 100× more for a 100/min rule.
  • Store memory: ~1 GB. 10 M keys × 100 B = ~1 GB. One Redis node holds it; shard for throughput, not for size.
  • Redis ops per second: ~1 M (or ~0 with local buckets). One Lua script call per decision = 1 M ops/s → ~10 Redis shards at 100 k ops/s each. With local token buckets that sync periodically, the store sees only sync traffic: 10 M keys ÷ 1 s sync interval is worse, so sync per active key per second, roughly 100 k/s.
  • Rule config size: ~10 k rules · < 1 MB. Per-tier defaults plus per-customer overrides: a few thousand to ten thousand rules, each ~100 B = < 1 MB. Small enough to push to every node and hold in memory.
  • Latency budget breakdown: ~0.3 ms Redis RTT. Same-AZ Redis round trip ~0.2–0.5 ms; the Lua script itself is microseconds. That fits a 1 ms budget once, not three times, so multiple rules per request are evaluated in one script call or with local buckets.

Components

  • API client: Any caller: browsers, mobile apps, partner servers. Identified by API key or session; falls back to IP for anonymous traffic. Well-behaved clients read the rate-limit headers and back off before being rejected.
  • Load balancer: Spreads traffic across gateway instances. Not sticky: the same client lands on different instances, which is why limits cannot live only in instance memory.
  • API gateway (limiter middleware): Where the limiter runs, as middleware before routing. Extracts the client identity, looks up applicable rules from its in-memory rule cache, evaluates them, and either forwards the request or returns 429 with headers. Emits decision metrics.
  • Rule cache (in-process · versioned): Each gateway holds the full rule set in memory: (scope, key pattern, limit, window, burst). Refreshed by subscribing to a config change channel or polling a version every few seconds. A rule lookup is a map access, never a network call.
  • Local buckets (in-process LRU): Optional first tier: per-instance token buckets for hot keys that absorb most decisions with zero network cost, periodically reconciled against the shared store. Trades a little accuracy for latency and store load.
  • Counter store (Redis Cluster · Lua): The shared source of truth for counters, sharded by key. Each decision is one atomic Lua script that refills the bucket, checks, decrements, and sets a TTL in a single round trip. Keys expire after the window so memory is bounded.
  • Rule config service: Operator UI and API for rules: per-tier defaults, per-customer overrides, per-endpoint limits. Validates, versions, stores in a small database, and publishes a change notification.
  • Config DB (Postgres): Durable rules with history. Small and rarely written; read once per gateway refresh.
  • Config channel (Redis pub/sub or Kafka): Broadcasts "rules changed, version N" so gateways refetch within seconds instead of polling on a long interval.
  • Upstream services: The actual APIs being protected. They also benefit from the limiter's headers being set consistently and never see rejected traffic.
  • Metrics pipeline (counters → TSDB): Per-rule accept and reject counters, top throttled clients, store latency and fail-open events. Aggregated per instance and flushed every few seconds; never on the request path.
  • Dashboards & alerts: Operators watch reject rates by rule and customer, and get paged on fail-open (store unreachable) because that means limits are not being enforced.

User flows

  1. A request is checked and allowed. The hot path. Identify the client, find the rules, run one atomic script per key, forward with headers. Under a millisecond added.
  2. A client exceeds its limit. The same path with the other outcome. What matters is what the client is told so it can recover without hammering the API.
  3. An operator changes a limit. Rules are data, not code. A change propagates to every gateway within seconds without a deploy.
  4. The counter store is unreachable. The limiter must never become the outage. Decisions degrade to local approximations and operators are paged.
  5. One key generates 50 k requests per second. A single hot client (or a misconfigured integration) concentrates load on one counter shard. The design shifts that key's decisions to local buckets.

Deep dives

  1. Choosing the algorithm. Token bucket, leaky bucket, fixed window, sliding log, sliding window: which one and why?
  2. Where the limiter runs. Gateway middleware, a sidecar, a dedicated service, or the CDN edge?
  3. Distributed counters and accuracy. Ten gateways, one client. How exact does the shared count need to be, and what does exactness cost?
  4. The client contract: headers and 429 semantics. What exactly should a throttled client be told, and why does it matter for the system's own load?
  5. Operating it: config, rollout, and observability. A rule change can lock out a customer or open the floodgates. How do you change rules safely and know what the limiter is doing?