How Would You Design a Distributed Rate Limiter for Bursts and Failures?

Problem and Use Cases

Design a distributed rate limiter for a multi-tenant API. Rules apply to (tenantId, routeId), and each rule defines a sustained rate, burst capacity, and per-request cost. The system has 100 stateless API gateways and peaks at one million rate-limit checks per second. For this interview, assume the rate-limit path should add no more than 5 milliseconds at p99 and should be 99.99% available. These numbers are design inputs, not performance promises from any vendor.

An over-limit request receives HTTP 429 with an actionable retry delay. Ordinary business endpoints should remain available during a short rate-limit storage outage, while login and expensive write endpoints may use a stricter failure policy. The design must cover dynamic rule rollout, shadow evaluation, hot tenants, multiple regions, and horizontal scaling. Billing, DDoS scrubbing, queued scheduling, and adaptive backend load shedding are out of scope.

This is a useful question for mid-level and senior backend, platform, and infrastructure roles. The hard part is not naming five algorithms. It is turning “does this request consume quota?” into a synchronous decision path with explicit scaling, observability, and failure semantics.

What the Interviewer Is Evaluating

A strong answer begins by fixing the rate-limit dimension, accuracy requirement, and failure policy. If all 100 gateways keep complete local buckets, one tenant can spend a separate quota at every gateway. The effective allowance changes with instance count and traffic distribution. A shared state or a local state constrained by leases is required for a meaningful global limit.

The next signal is the atomic boundary. One token-bucket decision reads the old balance, refills it according to elapsed time, checks the balance, deducts tokens, and writes the result. Splitting those steps into network calls allows concurrent requests to read the same balance and spend it twice, even if every individual Redis command is atomic. The entire read-compute-write sequence belongs in one short Lua script or an equivalent server-side atomic operation.

A credible answer also contains orders of magnitude. At one million checks per second, the data plane must perform one million synchronous decisions; it cannot query a configuration database on every request. Assume 10 million active buckets, a 64-byte average key, and two 8-byte state fields. The logical data is about 10,000,000 × 80 B = 800 MB. Redis objects, hash tables, expiration indexes, and replicas increase actual memory substantially, so capacity must be measured with the real key shape. If a check request is about 100 bytes and its response about 32 bytes, the system also receives roughly 100 MB/s and sends roughly 32 MB/s before protocol overhead.

Finally, the trade-offs must close: why token bucket matches burst requirements, how to split a hot key, what happens when storage is unreachable, how asynchronous replication changes accuracy, whether multiple regions favor a hard global cap or partition availability, and how shadow mode finds false positives before enforcement.

Clarifying Questions Before Answering

• What forms the rate-limit key? This design uses tenant plus normalized route. It does not put raw URLs, arbitrary query strings, or untrusted forwarded IPs directly into keys because that creates unbounded cardinality or spoofable identity.
• Is this a fixed window or a burst-aware rule? The requirement combines a sustained rate with burst capacity, so token bucket is the default. A strict maximum of N requests in every possible sliding window would require different accuracy and storage trade-offs.
• Does every request cost one token? The default cost is 1, but an endpoint may supply a positive integer cost. Balances and refill rates use scaled integers to avoid accumulated floating-point error.
• How exact must the limit be? The normal single-region path requires an atomic decision per bucket. Acceptable over-admission or under-admission during failover and across regions must be stated separately; “eventually consistent” is not a usable error budget.
• During a storage failure, do we favor availability or protection? Ordinary reads fail open after a short timeout and add a coarse gateway-local emergency cap. Login, billing-related, or expensive endpoints may fail closed or spend only preallocated leases.
• How quickly must a rule change take effect? The control plane assigns monotonically increasing versions and pushes rules to the rate-limit service. The data plane reads a local cache, not the database, and reports instances that lag behind.
• What should a 429 response contain? It returns a machine-readable reason and Retry-After. The IETF defines 429 as too many requests in a given amount of time and permits Retry-After, but it does not prescribe the server's counting algorithm.

30-Second Answer Framework

“I would enforce the check at the API gateway. The gateway sends tenant, normalized route, cost, and rule version to a stateless rate-limit service. The service derives a stable (tenantId, routeId) key and runs a short Lua script on one Redis Cluster shard to atomically refill, decide, deduct, set TTL, and calculate the retry delay. A separate control plane versions and pushes rules, so the data plane only reads a local cache. I would scale the stateless service and Redis shards horizontally and use quota leases for hot keys. Ordinary endpoints fail open with local protection during an outage; high-risk endpoints fail closed. I would launch in shadow mode and then enforce gradually while watching latency, rejection rate, errors, hot keys, and rule versions.”

Step-by-Step Deep Dive

Start with capacity. The 100 gateways average 10,000 checks per second each, but connection pools and instance counts should be sized for post-failover peaks plus headroom, not the average. If a Redis shard safely sustains Q decisions per second under the actual Lua script, key size, persistence, and replication settings, the design needs at least ceil(1,000,000 / Q) primary shards plus failure and growth headroom. Quoting a generic “operations per second per Redis node” number would be misleading because script length, hardware, network, and replication mode all change the result.

The data plane has five parts: a gateway rate-limit filter, a stateless rate-limit service, a sharded state store, a rule control plane, and an observability pipeline. The gateway authenticates identity and normalizes the route. The service matches a rule and makes the decision. Redis Cluster stores active buckets. The control plane publishes versioned rules from a database. Metrics record allowed, denied, error, failure-mode-allowed, and latency outcomes. Mature proxies use the same boundary—a filter produces descriptors, calls an external rate-limit service, and returns 429 when over limit—so this interface can evolve independently of application services.

An internal API could look like this:

CheckRateLimitRequest {
  tenant_id: string
  route_id: string
  cost: uint32
  rule_version: uint64
}

CheckRateLimitResponse {
  allowed: bool
  remaining: uint64
  retry_after_ms: uint64
  rule_id: string
  applied_rule_version: uint64
}

The gateway accepts tenantid only from the authentication path. routeid is a route template such as /orders/:id, not a raw path whose cardinality grows with order IDs. A Redis key can be rl:{tenantId:routeId}. The stable value inside braces keeps one bucket in one Redis Cluster hash slot. The state needs only tokens and lastrefillms; a missing key represents a new, full bucket. Rate-limit keys need dedicated capacity with no silent eviction. If the memory policy evicts an active bucket, its next access incorrectly restores a full allowance.

The bucket refills refillperms scaled-integer tokens per millisecond up to capacity. Its core decision is:

elapsed = max(0, now_ms - last_refill_ms)
available = min(capacity, tokens + elapsed * refill_per_ms)

if available >= cost:
  allowed = true
  available = available - cost
  retry_after_ms = 0
else:
  allowed = false
  retry_after_ms = ceil((cost - available) / refill_per_ms)

The script writes the balance and timestamp and sets a TTL equal to the time for an empty bucket to become full, plus a safety margin. Deleting a bucket after it has been idle long enough to refill is safe because its next access should see a full bucket anyway. Time must come from a trusted source used consistently for that bucket, negative elapsed is clamped to zero, and token arithmetic uses scaled integers. Redis documents that scripts execute atomically, but they block other activity on the same instance while running. The script must therefore stay short and must not scan keys or touch unrelated buckets.

The algorithm follows the requirement. A fixed window needs only a counter and expiration per key, but it can admit two batches on opposite sides of a boundary. A sliding log is exact but stores one timestamp per request in the window. A sliding-window counter has fixed space but is approximate. A token bucket expresses sustained rate and controlled bursts with two state values. AWS API Gateway also documents separate rate and burst settings and describes its throttling as a best-effort target. A custom design cannot borrow that implementation evidence and then promise a hard cap through every failure.

The normal request flow is straightforward. The gateway resolves identity and normalized route, then its local route configuration produces a descriptor and expected rule version. It calls a same-region rate-limit service, which reads the parameters from its local rule cache, locates the Redis shard, and executes the atomic script. An allowed request continues to the backend. A denied request returns 429, a reason, and Retry-After calculated from the balance. The internal millisecond delay is rounded up to whole seconds for the HTTP header, while a JSON response may retain millisecond precision. The control plane validates a new rule version before pushing it, and service instances report the version they applied. Emergency changes can be pushed immediately; ordinary rules may tolerate a short propagation delay, but every decision response carries the applied version so version skew can be diagnosed.

To stay within the 5-millisecond p99 target, both gateway-to-service and service-to-Redis paths use persistent connections and connection pools. Each decision makes one Redis round trip, and the internal call gets a deadline of about 3 milliseconds to reserve time for gateway work. The gateway prefers a nearby rate-limit service instance. If peak-load testing still misses the target, reduce network hops or use local leases for high-volume tenants. Only end-to-end percentiles under peak load prove the target; the average latency of one Redis command does not.

The likely bottlenecks are hot keys, shared storage, and synchronous network hops. A large tenant generating 100,000 checks per second can saturate one hash slot even when aggregate cluster throughput is adequate. A global bucket can instead issue small, short-lived token leases to multiple rate-limit nodes, which spend locally and renew near a low-water mark. Leases reduce shared-store traffic but waste unused tokens, delay recovery after a node disappears, and complicate fairness. The sum of all unexpired leases must remain within the global budget. Ordinary tenants should stay on the shared bucket so a rare hot tenant does not make the entire design complex.

Failure policy depends on endpoint risk. If the service times out or Redis is briefly unavailable, ordinary read endpoints can fail open while every gateway applies a coarse emergency limiter and increments failuremodeallowed. That local cap protects backend capacity; it does not promise an exact global tenant quota. Login, expensive writes, and anti-abuse endpoints can fail closed or spend only an existing lease. With asynchronous Redis replication, a primary failover may lose recent deductions and briefly over-admit. That possibility belongs in the error budget; the presence of replicas does not imply zero loss.

A single strict bucket shared by every region puts cross-region latency and partitions on every request. A more practical design has a central allocator issue short-lived token leases to each region, followed by atomic consumption inside the region. If the sum of leases never exceeds the global budget, the allocator does not create extra quota, but a partitioned region can spend only its remaining lease and loses some availability. Allowing each region to admit independently and reconcile later gives higher availability, but the over-admission bound must be calculated from region count and local allocations. The business must choose this accuracy-availability boundary.

Rollout starts in shadow mode: compute decisions without blocking and inspect which tenants and routes would be rejected. Enforcement then expands by rule and tenant. At minimum, monitor decision p50/p95/p99, allowed/denied/error/failure-mode-allowed counts, Redis script time, shard load and hot keys, rule-version lag, and backend saturation before and after enforcement. Stripe's published engineering practice likewise emphasizes dark launches, kill switches, clear errors, and safe failure behavior. Those operational details make the design more production-ready than a component diagram alone.

High-Quality Sample Answer

“I will make token spending atomic for (tenantId, routeId) on the normal single-region path. The inputs are 100 gateways, a peak of one million checks per second, and no more than 5 milliseconds of added p99 latency. Each rule has a sustained rate, burst capacity, and request cost. An over-limit request gets 429 and Retry-After.

The gateway derives a trusted tenant identity and normalizes the raw URL to a route template, then calls a stateless service in the same region. The service reads a versioned rule from its local cache and maps rl:{tenantId:routeId} to one Redis Cluster slot. A short Lua script reads tokens and the last refill time, refills up to capacity, checks and deducts the cost, and writes the state with a TTL. Read, compute, and write share one atomic boundary, so two gateways cannot both spend the final token.

I will benchmark the real script to obtain a safe per-shard throughput Q, deploy at least ceil(1,000,000 / Q) primaries, and add failover headroom. Ten million active buckets with a 64-byte key and two 8-byte fields are about 800 MB of logical data; Redis objects, expiration indexes, and replicas add to that. Adding ordinary shards does not solve a hot tenant, so I will issue small, short-lived leases to rate-limit nodes and keep all unexpired leases inside the global budget.

Failure semantics vary by route. Ordinary reads fail open after a timeout, but gateway-local protection remains active and failure-mode admissions are measured. Login and expensive writes fail closed or use only an existing lease. Multi-region enforcement uses quota leases as well, with an explicit choice between a hard cap and partition availability. I will launch in shadow mode, canary by tenant, and watch decision latency, rejections, errors, failure-mode admissions, hot keys, and rule versions. That gives the normal accuracy, failure error, and rollback path a testable boundary.”

Common Mistakes

• Keeping a complete local bucket at every gateway → the allowance is multiplied by instance count and changes with load balancing → use shared atomic state for ordinary traffic and globally constrained leases for hot-key optimization.
• Calling GET, calculating in the application, and then calling SET → concurrent requests can read and spend the same balance → put refill, decision, deduction, and write-back in one short server-side script.
• Saying “Redis can handle it” without a budget → throughput, memory, replication, and hot-key limits remain unknown → benchmark the real script for Q, calculate shards from it, and report key skew.
• Allowing the memory policy to evict rate-limit keys silently → an active bucket can disappear and be recreated as full without an alert → use dedicated capacity with a no-eviction policy and alert on memory pressure and write failures.
• Using raw URLs or client-asserted identity as keys → cardinality becomes unbounded or clients bypass quotas → derive descriptors from authenticated tenants and route templates.
• Treating 429 as specific to fixed windows → the protocol status does not define the internal algorithm → return 429, a reason, and Retry-After computed by the chosen algorithm.
• Failing open for every endpoint → login, expensive writes, and anti-abuse paths lose protection → configure fail-open, fail-closed, or preallocated leases by route risk.
• Claiming Redis replicas prevent all over-admission → asynchronous replication and failover can lose recent deductions → include replication loss in the error budget and choose stronger consistency or less availability for strict cases.
• Giving every region the full quota → the global cap can be multiplied by the number of regions → allocate regional leases centrally or calculate and accept the asynchronous design's over-admission bound.
• Turning on blocking globally on day one → a bad rule immediately rejects real traffic → shadow first, canary by rule, tenant, and percentage, and retain a kill switch.

Follow-up Questions and Responses

Follow-up 1: How would you enforce a strict global limit?

The direct answer is one strongly consistent quota service synchronously used by every region, but every request pays cross-region latency and partitions must reject some traffic. A common alternative is a central allocator that issues short-lived regional leases while keeping the sum of all valid leases within the global budget. Regions spend locally with low latency, but idle leases reduce utilization and a partitioned region can spend only what remains. If the business requires full service during a partition, it must accept a calculable amount of over-admission; all three properties are not free.

Follow-up 2: What if one very large tenant creates a hot key?

Adding Redis shards does not split one key. The global bucket can lease, for example, a few hundred tokens at a time to several rate-limit nodes. Each node spends atomically in memory and renews at a low-water mark. Larger batches reduce shared-store pressure but increase waste and short-term unfairness when a node fails. Smaller batches improve precision but renew more often. Adapt the batch size to observed heat and monitor unused leases and renewal latency.

Follow-up 3: How do you protect the backend if Redis is completely unavailable?

Fail-open endpoints need independent local protection. Each gateway enforces a coarse aggregate entrance cap, connection-pool limits, and circuit breaking without pretending to maintain exact tenant quotas. High-risk endpoints fail closed or spend only prefetched leases. The rate-limit timeout is much shorter than the business request budget, and failure-mode admissions have a separate counter and alert. Do not retroactively charge allowed requests when storage recovers, which would create a second traffic shock.

Follow-up 4: Can a retry after a rate-limit service timeout deduct twice?

Yes. The server may have committed the deduction while its response was lost. For low-cost requests, the gateway should not retry on the synchronous path; it should apply the route's failure policy. If deduction must be idempotent, send a unique requestId and have the script store a short-lived deduplication record in the same Redis Cluster slot as the bucket, returning the first result. That adds memory and write amplification, and its TTL must cover the caller's retry window. Enabling transparent RPC retries alone is unsafe.

Follow-up 5: How do you atomically enforce both tenant-wide and endpoint limits?

Change the key scheme to rl:{tenantId}:global and rl:{tenantId}:route:<routeId>, which places the relevant keys for one tenant in the same Redis Cluster slot. The script computes every bucket first and deducts only if all of them allow the request. As the number of rules grows, script cost and hot-key pressure grow too. Keep the most important two levels on the atomic path and treat others as independent protection if partial accounting is acceptable. Cross-slot transactions add substantial complexity and should not be the default without a strict business need.