Playbook / General system design / Design a distributed rate limiter

Design a distributed rate limiter

Expected question

"Design a distributed rate limiter. How do you enforce per-client limits accurately across many API servers with low overhead?"

Variant forms

Same design, different framing:

  • "Design API rate limiting for 1M requests/second across a global edge."
  • "How do you rate limit by API key, user tier, and IP without a single Redis bottleneck?"
  • "Design sliding window vs token bucket for a SaaS with burst-friendly paid plans."
  • "Our limiter drifted under clock skew — architect consistent counting across regions."
  • "Design rate limiting that survives Redis failover without allowing 10× traffic spikes."
  • "How do you implement global vs per-region quotas for compliance?"
  • "Design adaptive rate limits that tighten during an ongoing DDoS."

Where this actually gets asked

Weakly sourced for company-specific attribution, disclosed honestly: no verified Blind/Glassdoor post was found confirming this exact question at any of the six companies. Several aggregator sites (PracHub, DesignGurus) label it a "Google Interview Question" — but a direct fetch of PracHub's own page found zero citation trail behind that label, the same fabrication- adjacent pattern this repo has caught before. Treat "rate limiter" as a well-known general system-design archetype asked broadly across big tech (not AI-specific, and not company-specific to any of the six) rather than a confirmed leaked question. Useful grounding: Google Cloud's own Cloud Armor rate-limiting documentation describes a real, shipped system (throttle vs. rate-based-ban rules, keyed by IP/header/ forwarded-for) that's excellent grounding material for this question's real-world answer, even without a confirmed interview attribution.

Executive summary

30-second thesis

I'd put a shared Redis (Lua atomic consume) behind a check API, default token-bucket for bursty SaaS tiers, and pick fail-closed for public edges — local counters alone will undercount the moment traffic spreads across boxes.

2-minute answer

Clarify keys (API key / user / IP), multi-rule stacks (RPM + daily), and whether overshoot for ~1–2s (H) is tolerable for multi-region. Default: one round-trip POST /v1/check that evaluates all rules against Redis Lua so read-check-increment can't race. Sliding-window counter if they hate boundary bursts and don't need intentional burst. Across regions I'd start with static fractional budgets; reverse to gossip (~1–2s H) when traffic is skewed and unused regional quota matters. Hot keys get sub-key sharding or edge pre-throttle. Name the store-outage posture out loud — public attack surface fail-closed; internal availability-first may fail-open with a hard timebox.

Quantitative trade-offs

DecisionTrade-off and reversal evidenceEvidence class
Token bucket vs fixed windowBucket allows controlled burst; reverse to sliding/fixed if product wants a hard flat cap and burst is abuse.H
Exact global vs regional approximateExact needs cross-region sync cost; reverse to regional fractions when p99 check must stay ~1–5ms (H) single-region.H
Fail-closed vs fail-open on store outageClosed protects the edge under attack; reverse to open (timeboxed) when availability > strict quota for internal APIs.H

What I'd ask them

  1. Is this a public API under DDoS risk, or an internal service where availability wins?
  2. Multi-region exactness — how much overshoot for 1–2 seconds is acceptable?
  3. Hottest key QPS and whether edge pre-throttle is in scope?

Requirements

Functional

  • Limit the number of requests a client (by API key, user ID, or IP) can make in a given time window, rejecting requests over the limit.
  • Support multiple simultaneous limit rules (e.g., 10 requests/second AND 1000 requests/day per client) rather than a single flat threshold.

Non-functional

  • Must work correctly across multiple servers/regions handling the same client's traffic — a rate limiter that only tracks state on one server undercounts a client hitting multiple servers.
  • Low latency — the rate-limit check happens on every request, so it can't meaningfully add to request latency.
  • Should fail safe in a way that's explicitly chosen, not accidental — deciding whether a limiter-storage outage should fail open (allow all traffic) or fail closed (reject all traffic) is a real design decision, not a detail.

Core entities

  • Client: the entity being rate-limited (API key, user, IP) with one or more applicable limit rules.
  • Limit rule: a threshold (N requests per time window) and the window's semantics (fixed, sliding, or token-bucket).
  • Counter/bucket: the current state of a client's consumption against a rule — this is the piece that must be shared/synchronized across servers.

API / interface

Auth: service identity; limit keys are explicit (api_key / user_id / ip) — never inferred silently.

PUT /v1/rules/{rule_id}
{"key_template":"user:{user_id}","algorithm":"token_bucket","capacity":100,"refill_per_sec":10,
 "fail_mode":"closed"}
→ 200 {"rule_id":"...","version":3}

POST /v1/check
{"rule_ids":["rpm_user","daily_user"],"key_values":{"user_id":"u_42"},"cost":1}
→ 200 {"allowed":true,"results":[{"rule_id":"rpm_user","remaining":91,"reset_at":"..."}]}
→ 429 {"allowed":false,"results":[{"rule_id":"rpm_user","remaining":0,"retry_after_sec":2}]}

POST /v1/check:batch
{"checks":[{"rule_ids":["rpm_user"],"key_values":{"user_id":"u_1"}},{"rule_ids":["rpm_user"],"key_values":{"user_id":"u_2"}}]}
→ 200 {"results":[...]}

GET /v1/rules/{rule_id}/stats?window=5m
→ {"allows":12040,"denies":330,"store_errors":0,"p99_check_ms":1.8}

Staff+ callout: multi-rule check is one round-trip; fail_mode is part of the rule contract, not an ops toggle.

Data Flow

Every request path calls check before work; multi-rule evaluation is one round-trip against shared atomic state.

Rendering architecture diagram…

High-level design

Rendering architecture diagram…

The decision that matters: the counter store must be shared across every server instance handling that client's traffic — an in-process counter per server undercounts a client distributing requests across multiple servers/regions, defeating the limiter entirely.

Deep dive 1: algorithm choice

AlgorithmBurst handlingMemoryAccuracyWhen it's the right call
Fixed window counterPoor — allows 2x burst at window boundaryLowestApproximateSimple cases where boundary bursts are acceptable
Sliding window logBest — exactHighest (stores every request timestamp)ExactLow-volume, high-precision limits
Sliding window counter (weighted average of two fixed windows)Good — smooths boundary burstsLowApproximate, close to exactThe common real-world default — good accuracy/memory trade-off
Token bucketGood — allows controlled bursts up to bucket sizeLowApproximate by design (bursts are intentional)APIs that want to allow occasional bursts, not just a flat cap

Trap: proposing a fixed-window counter without recognizing its boundary-burst flaw — a client can send the full limit at the very end of one window and the full limit again at the very start of the next, doubling the effective rate for a brief period. Call it before they prompt you.

Deep dive 2: distributed synchronization — the actual hard part

A single-server rate limiter is a solved problem; the distributed version's real difficulty is keeping the shared counter both fast and consistent across concurrent requests hitting different servers simultaneously. A shared Redis instance with an atomic increment-and-check (via a Lua script or INCR + EXPIRE) is the standard real answer — the atomicity matters because a naive "read counter, check, increment" sequence has a race condition where two concurrent requests can both read the same under-limit value before either increments it, allowing both through when only one should have passed.

Deep dive 3: making "regionally approximate" a concrete mechanism, not a hand-wave

Naming "each region enforces a fraction of the global limit" is a Staff+-level answer; a Principal-level one specifies how regions actually stay approximately in sync without a synchronous cross-region call on every request. Two real mechanisms, with different cost profiles: static fractional allocation (each of N regions gets limit/N as a fixed local budget — zero coordination cost, but wastes capacity when traffic is skewed toward one region and a client legitimately needs more than their region's fixed share) versus periodic gossip/ reconciliation (each region tracks its own local counter and asynchronously exchanges counts with other regions on a short interval, e.g., every 1-2 seconds, allowing each region to adjust its effective local limit based on other regions' recent consumption). The gossip approach recovers much of the accuracy of a globally-exact limiter while keeping the hot path single-region and synchronous-call-free — the real cost is a bounded window (the gossip interval) during which the global limit can be modestly over-enforced, which is an explicit, quantifiable trade-off (e.g., "up to 2 seconds of staleness means at most ~2 extra seconds' worth of over-limit traffic can slip through across all regions combined") rather than an unstated approximation.

Deep dive 4: hot keys and the limiter's own SLO

A single hot API key/IP can pin one Redis counter and melt a shard — Staff+ mentions sub-key sharding, local shadow buckets, or edge pre-throttle before the shared store. Also define an SLO for the check path itself (e.g., p99 <2–5ms (H)): store errors and check latency should drive fail-open/closed automatically, not just a dashboard. In 45 minutes, pick one algorithm deeply; do not survey every variant.

What's expected at each level

  • Mid-level: fixed-window counter; misses boundary burst and shared-state problem.
  • Senior: shared counter store + sliding window or token bucket; names the boundary-burst flaw.
  • Staff+: atomic check-and-increment (Lua); states fail-open vs fail-closed when the store is down.
  • Principal: names the cross-region mechanism (static fraction vs gossip) with a quantified staleness window and a traffic-skew assumption.

Follow-up questions to expect

  • "What if the rate-limit store dies?" — Say the posture out loud. Public edge under attack: fail-closed. Internal service where availability matters more than quotas: fail-open with a short timebox and a loud page, not forever.
  • "Global users without one global Redis?" — Shard regionally; each region enforces a fraction (or gossip-adjusted share). Exact global counts aren't free — name the staleness you're buying.
Design a real-time chat/messaging system at scale →