Design a Rate Limiter

• 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).

• 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.

• 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.

• 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.

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.
   2. Middleware looks up applicable rules in the in-memory rule cache.
   3. For each rule, run the token-bucket script against the counter store in one round trip.
   4. All rules allowed: forward upstream and add rate-limit headers to the response.
   5. Decision is counted asynchronously for metrics.
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.
   2. The script finds the bucket empty and returns a rejection with the time until the next token.
   3. Gateway returns 429 with Retry-After and does not call upstream.
   4. Reject counters increment; a sustained reject rate on one key shows up on the throttled-clients dashboard.
   5. A well-behaved client sleeps for Retry-After and resumes; a badly behaved one keeps getting cheap 429s.
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.
   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.
   4. The gateway swaps its in-memory rule set atomically; the next request uses the new limit.
   5. Metrics show the propagation: the fraction of gateways on version 1187 reaches 100 % within seconds.
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.
   2. Gateway falls back to its local bucket for that key, scaled by the instance count.
   3. If no local state exists either, allow the request (fail open) and tag it.
   4. Fail-open events are counted and alert immediately.
   5. Store recovers; the breaker closes; local buckets reconcile with shared counters.
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.
   2. For a hot key, each gateway serves decisions from a local token bucket sized as its share of the limit.
   3. Local buckets reconcile with the shared counter every 100–500 ms.
   4. The 429s for the hot key are served locally too, so the abusive client never touches the store.
   5. When the key cools, it leaves the hot set and returns to the shared path.

Ask: Token bucket, leaky bucket, fixed window, sliding log, sliding window: which one and why?

Good answers name: Token bucket, Sliding window log, Sliding window counter (weighted two fixed windows), Fixed window counter, Leaky bucket (queue).

Our pick: Token bucket per (client, rule), implemented as a Redis Lua script that refills based on elapsed time, checks, decrements, and sets a TTL in one atomic step. Rules specify limit, window, and burst; capacity = burst, rate = limit / window. Expose the standard headers computed from the bucket state. Offer sliding-window-log as an option for a handful of sensitive, low-limit rules like authentication attempts, where exactness beats cost.

1. A rule says 100 per minute with burst 20. A client sends 20 instantly, then what?
   Then it gets one token every 600 ms. Over any full minute it still averages 100. Over the first second it sent 20, which is 12× the average rate, and that is the point of burst. If the interviewer wants the instantaneous rate capped too, add a second, tighter rule: 20 per second.
2. Why not compute the token bucket in the gateway without Redis?
   Because the same client hits many gateways. Per-instance buckets multiply the effective limit by the instance count and are wrong the moment traffic is uneven. Local buckets work as a first tier for hot keys or as a fallback, but the shared store is what makes ten gateways behave as one limiter.
3. Clock skew between gateways: does it break the bucket?
   The script uses the Redis server's clock (redis.call TIME) rather than a timestamp passed by the gateway, so all decisions for a key see one monotonic clock. If you pass the client time you inherit skew; never do that.
4. How does the script avoid a race when two gateways decrement the same bucket at once?
   Redis executes a Lua script atomically on its shard: no other command interleaves. Both scripts run in sequence, the second sees the first's decrement. The race exists only if you do GET then SET from the client side, which is why the logic lives in the script.

Ask: Gateway middleware, a sidecar, a dedicated service, or the CDN edge?

Good answers name: Library or middleware in the gateway, shared store behind it, Dedicated rate-limit service (gRPC), Sidecar (Envoy / service mesh filter), CDN edge rules.

Our pick: Middleware inside the API gateway, packaged as a library, talking directly to the counter store; rules pushed to every instance and cached in memory. Add coarse IP and path limits at the CDN edge as an outer layer for anonymous abuse. Keep a dedicated service only if the organisation has many gateways in different languages; even then, the service should be a thin wrapper around the same store and script.

1. What is the failure mode of a dedicated rate-limit service, and how do people mitigate it?
   It becomes a synchronous dependency of every request. When it is slow, every API is slow; when it is down, callers must choose between failing open and failing closed. Mitigations are aggressive timeouts, fail-open defaults, and local caching of recent decisions, which is most of the way back to a library design.
2. Limits per API key versus per user versus per IP: how do you pick the identity?
   Prefer the most specific authenticated identity: key for machine clients, user for sessions. IP only for anonymous traffic and abuse, with high limits because of NAT and mobile carriers. A single request can be checked against more than one identity; the cost is one script call per rule, or one batched call when keys share a hash tag.
3. Should upstream services trust the gateway or also limit?
   Internal services should have their own coarse protections (concurrency limits, load shedding) because not all traffic comes through the public gateway. Business rate limits belong at the edge; resource protection belongs at the service.

Ask: Ten gateways, one client. How exact does the shared count need to be, and what does exactness cost?

Good answers name: Shared atomic counter per key, local buckets for hot keys and fallback, Always local with periodic sync, Sticky routing by client to one gateway, Strongly consistent counter in a database.

Our pick: Redis Cluster as the shared counter with the Lua token bucket; keys hashed so a client's rules for the same identity land on one slot (hash tag on the identity) and can be checked in one call. Detect hot keys per instance and switch them to local buckets with shares reconciled every few hundred milliseconds. On store failure, fall back to local shares and then fail open. Document the accuracy contract: exact for normal keys, within ~5 % for hot keys, best effort during store outages.

1. How do you shard the counter store and what happens on resharding?
   Redis Cluster hashes keys to 16 384 slots across shards; a client's keys share a hash tag so they co-locate. Resharding moves slots live with brief redirection; a counter in flight during a move might be lost, which costs one window of leniency for that client. Acceptable, and far better than any design that pauses decisions.
2. Two regions, one global limit of 1 000 per minute. Options?
   Split the limit statically (500 each) if traffic is balanced; split dynamically by recent share if not; or pick one region as the authority and accept cross-region latency for that key. Exact global limits across regions are not worth their latency; say so and offer per-region enforcement as the default.
3. Memory: what if a bug makes keys never expire?
   Every script sets PEXPIRE on every write, so expiry does not depend on a separate cleanup path. Belt and braces: Redis maxmemory with an LRU or TTL eviction policy, and an alert on key count growth. Losing an evicted counter is one window of leniency, not an incident.

Ask: What exactly should a throttled client be told, and why does it matter for the system's own load?

Good answers name: Limit / Remaining / Reset headers on every response, Retry-After on 429, report the most restrictive rule, 429 only, no headers, Queue the request until a token is available.

Our pick: On every response: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset (unix seconds) for the most restrictive applicable rule, plus a RateLimit-Policy header listing all rules so advanced clients can see the full picture. On 429: Retry-After in seconds (rounded up), a JSON body naming the rule, and no upstream call. Publish client guidance: honour Retry-After, add jitter, and treat Remaining as advisory. Escalate persistent offenders with a penalty rule that lengthens their lockout.

1. Remaining says 5, the client sends 5 in parallel, 2 get 429. Bug?
   No. Remaining was true at the instant of the previous response; other requests in flight consumed tokens. Document it as advisory. Clients that need certainty should serialise or keep a margin.
2. How do you stop a retry storm from a popular open-source client with a bad backoff?
   Retry-After plus a penalty rule that counts 429s per key: after N rejections in a minute, the effective lockout doubles each time, capped. Combine with a gateway-level cap on connections per key. And reach out to the maintainers; the fix belongs in the client, the penalty just buys time.
3. Should the limiter distinguish reads from writes?
   Often yes: writes are more expensive and more dangerous under abuse. Model it as separate rules per method or endpoint group, or as different token costs within one bucket (a write costs 5 tokens). The script already takes a cost parameter.

Ask: 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?

Good answers name: Versioned rules, push-based refresh with poll fallback, shadow mode for new rules, Rules baked into gateway config, deployed with code, Rules read from the database per request.

Our pick: Rules live in a small database behind a config service with validation and audit. Every change bumps a version, is published on a channel, and gateways fetch the compiled snapshot; a 30 s poll catches missed notifications. New or tightened rules start in shadow mode, reporting would-be rejections per customer for a day before enforcing. Metrics: decisions per rule per outcome, top throttled keys, store latency, fail-open count, and rule version per instance. Alerts: fail-open above zero, reject rate for a tier jumping after a version change, any instance more than one version behind.

1. A customer says they are being limited far below their tier. Where do you look?
   Their key's decisions by rule in the metrics: which rule rejected and how often. Common causes: a per-endpoint rule tighter than the tier rule, an IP rule catching them behind a shared NAT, a client bug retrying without backoff, or a rule override from a past incident nobody removed. The audit log on rules answers the last one.
2. How do you test a rate limiter?
   Unit test the script against a deterministic clock. Load test with synthetic clients at known rates and assert admitted counts within tolerance across window boundaries. Chaos test the store: kill a shard under load and verify fail-open plus alerts. And keep a canary key with a tiny limit that a probe hits continuously; if the probe ever stops seeing 429s, enforcement is broken.
3. What is the cost of the limiter itself at 1 M decisions per second?
   Roughly ten small Redis shards and a few percent of gateway CPU. Trivial next to the upstream capacity it protects. The interesting cost is the engineering time on hot-key handling and multi-region semantics, which is why the accuracy contract should be explicit and modest.