System Design Arena
Design a Rate Limiter
Protect APIs from abuse and overload: token buckets, sliding windows, distributed counters, and the fail-open/fail-closed decision.
Case Study
Rate Limiter
Same conversation, diagrams, and wrap-up you expect—now framed with clearer scaffolding and iconography.
Prompt
Design a rate limiter that caps each client at N requests per time window across a fleet of API servers.
Interview snapshot
- • Topic: Rate Limiter
- • Expected depth: 45 - 60 minutes
- • Focus areas: APIs, scale estimation, resilient architecture
- • Wrap-up: risk, monitoring, disaster recovery
Key takeaways
- • Per-key limits (API key, user id, IP) with configurable window and burst.
- • Sub-millisecond decision latency at p99.
- • check(key, cost=1) → {allowed, remaining, retryAfter} — the only hot call.
🎙️ Interview mode
Practice this like a real interview
Don't read the answer first. Work the framework against the bare prompt, then compare against what the interviewer expected at each step.
Scorecard
What the interviewer is evaluating
Staff-level signal
Does the candidate pick an algorithm with a reason, keep the check atomic, and make the fail-open/fail-closed call explicitly tied to blast radius?
🧠 Staff engineer judgment
The rate limiter must never become the outage. If your protection layer can take down the API it protects, you designed a single point of failure and called it safety.
Calibration
The common (bad) answer
if (count[key]++ > limit) reject count stored in each API server’s memory
❌ Why this scores poorly: Per-server counters multiply the real limit by the server count, reset on deploys, and the increment races with itself. It limits nothing reliably.
✓ What a strong answer adds
- Token bucket: allows bursts, enforces the average — pick it and say why.
- Centralized atomic check (Redis + Lua): refill and decrement in one step.
- Shard by key; each key owned by one shard — counting stays exact.
- Explicit failure policy: fail-open with local fallback for rate limits.
- Hot-key rejection cache so abusers get cheap 429s.
Video walkthrough
Design a Distributed Rate Limiter
Hello Interview · ex-Meta staff engineer · 55 min
Token bucket vs sliding window, then the distributed-state problem that makes this question hard.
Work the prompt yourself first — guided practice grades your own answer step by step. Watching someone else design it feels like progress and teaches you far less.
Interview flow
Dialogue timeline
Interviewer
What exactly should it do?
Candidate
Enforce per-key limits — say 100 req/min per API key — across all API servers, return 429 with a Retry-After when exceeded, and support different limits per plan tier. Latency budget: sub-millisecond per check.
Interviewer
Which algorithm would you start with?
Candidate
Token bucket: capacity N, refill rate R. It allows short bursts up to capacity while enforcing the average rate — matching how real clients behave. Fixed windows have the boundary-burst flaw: 2N requests straddling a window edge.
Interviewer
Show me the bucket math.
Candidate
Store tokens and lastRefill per key. On request: tokens = min(capacity, tokens + (now−lastRefill)×rate); if tokens ≥ 1, decrement and allow, else reject. Two floats per key — the whole state is tiny.
Interviewer
Now make it work across 50 API servers.
Candidate
Centralize state in Redis: the check is a Lua script doing read-refill-decrement atomically — one round trip, no race between servers. Shard keys across a Redis cluster by hash; each key lives on exactly one shard, so counting stays consistent.
Interviewer
Redis adds a network hop. Isn't that slow?
Candidate
~0.5ms in-datacenter, inside budget. If it isn't, split the limit: each server enforces limit/serverCount locally with periodic sync — approximate but zero-hop. Precision versus latency is the actual trade-off to present.
Interviewer
Redis goes down. What now?
Candidate
Decide fail-open vs fail-closed out loud. For rate limiting, usually fail-open with a local fallback limiter — degraded protection beats a self-inflicted outage. For a billing quota, fail-closed. The failure policy IS the design decision.
Interviewer
A single hot key — one client at 1M req/sec.
Candidate
That key's shard becomes the bottleneck. Front it with a local pre-filter: once a key is known-exceeded, servers cache the rejection for the window remainder and stop asking Redis. Abusers get cheap 429s.
Interviewer
Where does this sit in the request path?
Candidate
As API-gateway middleware, before auth-heavy work — cheap rejection early. Config lives in a control plane: per-tier rules, hot-reloaded, so product can change limits without deploys.
Scoping
Requirements & trade-offs
Functional Requirements
- —Per-key limits (API key, user id, IP) with configurable window and burst.
- —429 + Retry-After on exceed; headers exposing remaining quota.
- —Per-plan tiers, hot-reloadable rules.
- —Out of scope: billing quotas, DDoS scrubbing.
Non-Functional Requirements
- —Sub-millisecond decision latency at p99.
- —Accuracy: no boundary-burst leaks; bounded overshoot on failover.
- —The limiter must never be the outage: explicit fail-open policy.
- —Scales linearly with API fleet size.
Blueprint
Architecture modules
Module 1
API / Interface
- •check(key, cost=1) → {allowed, remaining, retryAfter} — the only hot call.
- •Response headers: X-RateLimit-Limit / -Remaining / -Reset.
- •Control plane: PUT /rules {tier, capacity, refillRate}.
- •Lua script keeps refill+decrement atomic in Redis.
Module 2
Back-of-the-Envelope
- •1M req/sec API fleet → 1M limiter checks/sec; Redis cluster shard ~100K ops/sec each → ~10 shards.
- •State per key ~50 bytes → 100M active keys ≈ 5GB — memory is a non-issue.
- •Local rejection cache turns hot-key floods into ~zero Redis load.
- •0.5ms hop × 1 per request — batch or pipeline if gateway fans out.
Module 3
System Diagram Notes
- •API Gateway middleware → Redis cluster (sharded token buckets, Lua CAS).
- •Local fallback limiter + rejection cache inside each gateway.
- •Control plane pushes rules to gateways (config bus).
- •Metrics stream: per-key allow/deny rates feed abuse detection.
Module 4
Design Playbook
- •Compare algorithms in one breath (fixed/sliding window, token bucket) and commit to one with a reason.
- •The atomic Lua check is the correctness core — name the race it kills.
- •Present precision-vs-latency as tunable, not as a flaw.
- •The fail-open/fail-closed choice is the senior signal; tie it to blast radius.
- •Mention the hot-key rejection cache — it separates you from textbook answers.