System Design Interview: How Would You Design a Distributed Rate Limiter?

Prompt and context

This question tests whether “N requests per minute” becomes an operable control plane and data plane. A limiter protects capacity while preserving fairness and business priority; distributed nodes and shared state introduce approximation. Cover policy, algorithms, storage, responses, fallback, rollout, and metrics.

What the interviewer tests

Strong answers clarify dimensions, windows, bursts, and failure semantics before comparing token bucket, leaky bucket, fixed window, and sliding window. They separate policy distribution from request decisions, explain atomic counters, hot keys, multi-region behavior, and Redis failure, and return actionable Retry-After signals. They also discuss shadow rollout, error budgets, and audited bypasses.

Questions to clarify

• Is the key an API, tenant, user, IP, or combination? Are premium customers prioritized?
• Do we control sustained rate, burst size, concurrency, or several resources?
• Does an excess request fail, queue, degrade, or receive a small overage? Is global consistency required?
• Should an unavailable limiter fail open or closed? Which routes are high risk?
• How often do policies change, and do we need gradual rollout, audit, rollback, and immediate effect?

30-second answer framework

“I would separate policy control from request-time decisions. Normalize tenant, user, and route into a key; the data plane runs an atomic token bucket in Redis Lua and returns remaining quota and retry time. Versioned policies are cached, while local cache can make fast rejects but shared state makes the final decision. During a short shared-store outage, low-risk routes use a tenant emergency budget and fail open; high-risk routes fail closed and page. Shadow mode, burn rate, hot-key metrics, and regional error bounds guide rollout.”

Step-by-step deep answer

Step 1: Define capacity and fairness

Separate sustained rate, burst size, and concurrency. Tenant quotas prevent one customer consuming the global pool; user quotas contain noise inside a tenant. Critical routes can receive dedicated budgets. Fairness is a business policy, not an accidental algorithm default.

Step 2: Choose an algorithm

Token bucket permits controlled bursts and fits APIs; leaky bucket smooths output; sliding windows are intuitive but cost more state. Use monotonic time for token math, state cleanup, and an explicit precision bound.

Step 3: Model keys and policy

Normalize method, route, tenant, principal, and region so nodes derive the same key. A policy includes limit, burst, scope, priority, version, effective time, and owner. Unknown policy falls back to a safe baseline; clients cannot supply their own quota.

Step 4: Make the decision atomic

One shared operation reads state, refills tokens, deducts cost, and updates TTL. Redis Lua, an atomic database operation, or a sidecar can work; the key is avoiding read-then-write races. Return remaining tokens, reset time, and policy version.

Step 5: Handle hot keys and regions

A popular tenant can turn one key into a hotspot. Shard its budget and merge in a coordinator only if the overage bound is acceptable. Multi-region systems can use regional quotas and async global aggregation; strict global consistency costs availability and latency.

Step 6: Design failure and fallback

Choose fail-open or fail-closed by route risk and set a local emergency budget. When policy storage is unavailable, use the last version with a short TTL. Recovery must not release all accumulated demand at once. Audit every bypass and degraded decision.

Step 7: Roll out changes

Run a new policy in shadow mode first, compare predicted rejects, then enable by tenant or percentage. Include the policy version in logs and keep rollback ready. Every temporary exemption needs an owner and expiry.

Step 8: Measure outcomes

Monitor allow/deny rate, remaining quota, p95 decision latency, hot keys, storage errors, policy versions, false-reject appeals, and backend overload. Correlate them with 5xx, queue depth, and tail latency; too little limiting fails to protect, too much harms business.

Atomic token-bucket pseudocode

now = monotonic_time()
state = load(key) or {tokens: burst, at: now}
elapsed = now - state.at
state.tokens = min(burst, state.tokens + elapsed * rate)
allowed = state.tokens >= cost
if allowed:
    state.tokens -= cost
state.at = now
save_atomically(key, state, ttl)
return allowed, state.tokens, retry_after(state)

Trade-offs and boundaries

Rate limiting is neither a queue nor a substitute for capacity planning, circuit breaking, or authentication. Queues suit requests that may wait; a limiter rejects quickly at a resource boundary instead of hiding overload as latency.

Rollout plan and evidence

Build the policy model and token-bucket data plane for one high-volume API, run shadow mode for a day, then enable a few tenants. Microsoft Well-Architected treats throttling as active overload control; DataInterview and System Design School materials emphasize algorithm choice, shared state, and Retry-After.

Pilot exit criteria

After drills for traffic spikes, shared-store failure, rollback, and a hot tenant, latency goals still hold; every false reject has a reason; fallback budgets work; and policies have owners, versions, and audit records.

How to prove the gain is real

Compare backend overloads, 5xx, p99 latency, reject rate, false-reject rate, and storage cost before and after, segmented by tenant, route, and region. Normalize for capacity so a natural low-traffic period is not mistaken for success.

Common mistakes and follow-ups

Local counters on every node are enough

Each node releases its own quota, so a client can exceed the limit by moving nodes. Quantify approximation or use shared state/regional budgets for critical routes.

Using only a fixed window

Window boundaries permit a short double burst. Use token or sliding windows and explain state cost and precision.

Letting every request through when the limiter fails

High-risk routes lose their last protection. Choose emergency budgets and fail-open/closed by risk, with paging.

How do you avoid hurting premium tenants?

Configure tenant quotas and priority, separate shared and guaranteed pools, and give every exemption an expiry and audit trail.

How should clients retry?

Honor Retry-After, use jittered backoff, and never retry 429 forever. Automatic retries require idempotent requests.

How do you canary a new policy?

Calculate in shadow mode, enable by tenant or percentage, compare rejects, conversion, and backend load, and version the policy for rollback.