Design a Rate Limiter

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

Last updated 2026-09-22. Difficulty: medium. Patterns: algorithms, counters, redis, edge. Reported at Anthropic and 7 more with Pro.

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.
   1. Request arrives at a gateway instance; the middleware extracts the client identity. Identity precedence: API key, then authenticated user id, then IP. Anonymous IP-based limits are looser and separate, because NAT puts many users behind one address.
   2. Middleware looks up applicable rules in the in-memory rule cache. Match by endpoint pattern and client tier. Typical result: a per-key rule (1 000/min), a per-endpoint rule (100/min on /search), and a global safety rule. Map lookups, no I/O.
   3. For each rule, run the token-bucket script against the counter store in one round trip. The Lua script computes tokens = min(capacity, tokens + elapsed × rate), checks tokens ≥ 1, decrements, writes back, and sets a TTL of the time to refill fully. Atomic on the shard, so concurrent gateways cannot double-spend. Multiple rules for the same client can be evaluated in a single script call when their keys hash to the same slot (use a hash tag).
   4. All rules allowed: forward upstream and add rate-limit headers to the response. Headers reflect the most restrictive rule so clients can pace themselves. Remaining is approximate by design.
   5. Decision is counted asynchronously for metrics. In-process counters per (rule, decision), flushed every few seconds. No per-request network call for telemetry.
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.
   1. A burst of requests from one key lands across several gateway instances. Because the counter lives in the shared store, it does not matter that the 21 requests hit 6 different instances; they all decrement the same bucket.
   2. The script finds the bucket empty and returns a rejection with the time until the next token. retry_after = (1 − tokens) / rate. The script does not decrement below zero and does not extend the TTL for rejected calls, so a client that keeps retrying does not keep itself locked out longer than the window.
   3. Gateway returns 429 with Retry-After and does not call upstream. Rejections are cheap: no upstream work, a tiny response. This is the whole point: the limiter protects the expensive tier by doing the cheap thing early.
   4. Reject counters increment; a sustained reject rate on one key shows up on the throttled-clients dashboard. A single client being throttled is normal. A whole tier being throttled usually means a rule change was wrong or a client library has a retry bug.
   5. A well-behaved client sleeps for Retry-After and resumes; a badly behaved one keeps getting cheap 429s. For abusive clients, escalate: a secondary rule counts 429s per key and, above a threshold, applies a longer penalty window or blocks at the load balancer.
3. An operator changes a limit. Rules are data, not code. A change propagates to every gateway within seconds without a deploy.
   1. Operator raises a customer's search limit in the config UI. Validation: window and limit are positive, burst ≤ limit, no overlapping rule with a different value for the same scope. Stored with a new version number and an audit record.
   2. Config service publishes a change notification with the new version.
   3. Each gateway sees the notification and fetches the rules snapshot for that version. Fetch is a single request returning the full compiled rule set (under 1 MB) with an ETag. Gateways also poll every 30 s as a fallback in case a pub/sub message was missed.
   4. The gateway swaps its in-memory rule set atomically; the next request uses the new limit. Swap a pointer, never mutate in place. Existing buckets keep their tokens; only capacity and rate change, so a raised limit takes effect immediately and a lowered one drains naturally.
   5. Metrics show the propagation: the fraction of gateways on version 1187 reaches 100 % within seconds. Each gateway tags its metrics with the rule version. A gateway stuck on an old version is a visible anomaly.
4. The counter store is unreachable. The limiter must never become the outage. Decisions degrade to local approximations and operators are paged.
   1. Redis shard times out or returns errors for a key. Timeout is short (a few ms) so the request is not delayed. A circuit breaker per shard opens after a burst of failures so subsequent decisions do not even try.
   2. Gateway falls back to its local bucket for that key, scaled by the instance count. Each instance allows roughly limit ÷ N per window, where N is the number of healthy gateways from service discovery. Approximate but bounded: a client cannot exceed the limit by more than the imbalance across instances.
   3. If no local state exists either, allow the request (fail open) and tag it. The response carries X-RateLimit-Policy: degraded so upstream services and clients can tell. Rejecting here would turn a cache blip into an API outage for everyone.
   4. Fail-open events are counted and alert immediately. This alert is high priority precisely because nothing is visibly broken to users. Limits are silently not being enforced.
   5. Store recovers; the breaker closes; local buckets reconcile with shared counters. Reconciliation is simple: the shared bucket is authoritative; local state is dropped. A short period of slight over-admission during recovery is acceptable.
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.
   1. Gateways notice that one key dominates decision volume. A per-instance top-K sketch of keys by decision count, checked every second. Above a threshold the key is marked hot.
   2. For a hot key, each gateway serves decisions from a local token bucket sized as its share of the limit. Share = limit × (this instance's recent traffic for the key ÷ total), estimated from the reconciliation data. This removes 50 k ops/s from one Redis shard and makes decisions in-process.
   3. Local buckets reconcile with the shared counter every 100–500 ms. One script call per instance per interval instead of one per request: report tokens consumed, receive the global remaining and the instance's new share. Accuracy stays within a few percent.
   4. The 429s for the hot key are served locally too, so the abusive client never touches the store. Rejections are the cheapest response the system produces. Making them local means an abusive client costs almost nothing.
   5. When the key cools, it leaves the hot set and returns to the shared path. Hysteresis: the key must stay below the threshold for several intervals before demotion, to avoid flapping between modes.

Deep dives

Related

• Run this question for a friend: the interviewer kit