Loading...

A 20-minute mock system design interview. You drive the pace. Jump to the board when you are ready; skip capacity math if you want. The interviewer grades your thinking, not a template match.
This question has a smaller surface than a crawler or a chat system. The signal concentrates in two places: algorithm tradeoffs, where every algorithm has a sharp, checkable failure mode, and distributed correctness, where the race condition and cross-instance synchronization separate memorized answers from real reasoning. Naming "token bucket in Redis" is not a design.
Two shared surfaces (only one is on screen at a time; use the panel arrow to switch):
Build incrementally while you talk. Trace one request end to end through your diagram — including the third request in a second that gets bounced. Argue the tradeoff, not "industry standard."
Read this before you go in. These are the decisions, and why they matter.
Client-side: no. Clients are forgeable, and you may not control them at all. Inside the API servers: valid — full algorithm control. Middleware in front of the API servers: the standard answer. In a microservice stack that usually means the API gateway, next to SSL termination and auth. The honest decision inputs: if a gateway already exists, add limiting there; a third-party gateway constrains your algorithm choices; limited engineering resources point to a commercial gateway. Under a 2 req/sec rule, a client's third request in one second never reaches an API server — the middleware answers HTTP 429 itself.
Token bucket (Amazon, Stripe): a bucket of fixed capacity refilled at a steady rate; each request spends a token; empty bucket → drop. Accumulated tokens mean short bursts are allowed by design. Two parameters — bucket size, refill rate — and both are genuinely hard to tune. Usually one bucket per rule per entity: "1 post/sec + 5 likes/sec" is two buckets; a global 10K RPS cap is one shared bucket.
Leaking bucket (Shopify): a FIFO queue drained at a fixed outflow rate; full queue → drop. It flattens bursts into a smooth stream — good when downstream needs a constant rate — but a burst fills the queue with old requests and recent ones starve.
The contrast is the point: token bucket permits bursts, leaking bucket erases them. Which one you want is a requirements question (flash sales want token bucket), not an algorithm preference.
Cut time into fixed windows, one counter each, reset at the edge. Cheapest to run and easy to reason about — and broken at the boundary. Limit 5/min: send 5 requests at 2:00:59 and 5 more at 2:01:01, and the rolling minute from 2:00:30 to 2:01:30 saw 10 requests — double the quota. If your product genuinely resets quotas at fixed times, fine; otherwise this flaw is the reason sliding approaches exist. Knowing the boundary burst cold is table stakes for this question.
Sliding window log keeps every request's timestamp in a sorted set: evict entries older than the window, count, insert, decide. Perfectly accurate in any rolling window — and expensive: at 500 requests/hour it is ~12 KB per user, 12 GB for 1M users, and in Xu's variant even rejected requests still write a timestamp, so memory burns fastest under attack.
Sliding window counter is the pragmatic hybrid. Weighted-average form: effective = current_count + previous_count × (1 − position_in_window). Worked example: limit 7/min, 5 last minute, 3 so far, request lands 30% in → 3 + 5 × 0.7 = 6.5, round down to 6, under 7 → allow. Or Grokking's bucket form: per-minute sub-counters summed over the last 60. Cost: ~1.6 KB per user, 1.6 GB for 1M users — about 86% less than the log. It is an approximation (it assumes the previous window was evenly distributed), and the honest defense is empirical: Cloudflare measured 0.003% of 400M requests wrongly allowed or limited. Saying "approximate, but the error is negligible in production" is judgment; pretending it is exact is not.
The naive flow is read counter → compare → write. Counter at 2, limit 3, two requests arrive simultaneously: both read 2, both conclude one more is fine, both write 3. The correct value was 5 — the limit leaked. A per-record lock fixes it but serializes a user's concurrent requests and adds latency. The stronger answers: a Redis Lua script so check-and-increment runs atomically server-side, or sorted-set operations (the ClassDojo rolling-limiter pattern) whose sequence is effectively atomic. Not seeing the race at all is the red flag; seeing it and naming Lua or sorted sets is the strong signal.
Several stateless limiter servers sit behind a load balancer; a client's requests land on different instances. Per-instance counters see only a slice — the cluster-wide limit silently becomes N× the intended one. Sticky sessions technically work; reject them anyway (neither scalable nor flexible) and say why. The canonical answer is a centralized store (Redis): every instance checks and increments the same counter, with INCR for atomic increments and EXPIRE so counters clean themselves up. Shard by entity key with consistent hashing when one Redis is not enough; a write-back cache (update in cache, flush periodically) is acceptable because a briefly stale counter costs far less than a synchronous write per request.
Fail-open or fail-closed? If the counter store is down, most consumer APIs fail open — a limiter outage must not become a service outage. Security-critical endpoints (login, card attempts) may fail closed. Naming the tradeoff unprompted is bonus signal.
IP or user ID? IP works pre-authentication (the login path itself needs protection) but NAT and carrier-grade NAT put thousands of users behind one IP, attackers rotate IPs, and IPv6 makes per-IP state explosive. User ID is precise but only exists after auth — and an attacker triggering wrong-password lockouts can DoS a victim's account. The practical answer is a hybrid: IP-based limits on unauthenticated endpoints, user or API-key limits after auth, sometimes both at once. There is no clean single answer; reasoning through it is the signal.
One complete design you can study, then rebuild in your own words. Do not recite it. In the interview, draw your graph and defend the choices.
This question's estimation is memory per algorithm — it decides the algorithm.
Rough numbers are fine; the method is what gets graded — and the win is using the numbers: "the log is exact but 12 GB; counters are near-exact at 1.6 GB; I take the approximation."
How the graph works: clients hit a load balancer that spreads across a stateless rate-limiter tier (in production, usually middleware in the API gateway). Each limiter instance reads its rules from a local cache that a worker refreshes from config, then runs one atomic check-and-increment against shared Redis. Under the limit, the request forwards to the API fleet; over it, the limiter answers 429 with rate-limit headers — optionally parking the work on a queue instead of dropping it. The API servers never see excess traffic.
Web Client, Mobile Client
→ Load Balancer
→ Rate Limiter (middleware tier, usually in the API Gateway; mark distributed)
↔ Cache (rules cache) ← Worker (pulls rule config periodically)
↔ Redis (counters: INCR + EXPIRE, Lua for atomicity; mark distributed)
→ Service (API server fleet; mark distributed) [under limit]
→ 429 + X-Ratelimit headers back to the client [over limit]
→ Queue (optional: park throttled work instead of dropping)
Components:
X-Ratelimit-Limit and X-Ratelimit-Remaining.X-Ratelimit-Retry-After, and the API fleet never sees it. Optionally the work is parked on the Queue instead of dropped.Two requests race at the threshold: counter at 2, limit 3, both read 2, both write 3 — the correct value was 5. This is why step 3 is one atomic operation, not read-then-write. A lock also works but serializes the user's traffic.
Redis goes down: decide the failure posture per endpoint. Consumer traffic fails open — the limiter must not become the outage. Login and payment attempts fail closed. Say which and why.
The boundary burst: if the counter in step 3 is a fixed window, 5 requests at 2:00:59 plus 5 at 2:01:01 puts 10 in one rolling minute. The sliding window counter closes that hole for 1.6 KB per user.
Rules(domain, descriptor_key, descriptor_value, unit, requests_per_unit) — config files, pulled into the rules cache
Counters(entity_key, window_start, count) — Redis string, INCR + EXPIRE (fixed / sliding-counter windows)
Buckets(entity_key, minute_bucket → count) — Redis hash, one field per sub-window (sliding-counter variant)
RequestLog(entity_key → sorted set of timestamps) — Redis sorted set (sliding-log variant only)
entity_key = user ID or IP, plus the API/endpoint when limits are per-API (createURL and deleteURL get separate limits)entity_key with consistent hashing; replicate for fault toleranceToken bucket as the primary algorithm (Amazon and Stripe run it) if you want bursts and can argue the tuning cost. Leaking bucket where downstream needs a constant rate (Shopify). Sliding log where exactness is worth 12 GB — low-volume, high-stakes limits. Limiting inside the API servers instead of a gateway when the stack is small. A commercial gateway when engineering time is the constraint. What matters is that you can argue the tradeoff.