Interviewer — distributed rate limiter (SDS medium)
Candidate prompt: prompt. Method: Method. SDS: Design a Distributed Rate Limiter (medium).
Do not let the candidate read this file. Give numbers only when they ask.
Why this problem for this domain: API-first, multi-tenant banks, and a hose you must not hammer. Limits are per tenant/API key/agent, not per anonymous internet user. Fail-open vs fail-closed is an exec call: hammering an agent or leaking a flood onto voting submit is worse than a 429. Hot key = one mega-bank at a deadline. EM JD: platform, predictability, talk trade-offs upstairs.
This is not Twitter QPS trivia. Accuracy vs coordination cost is the design.
How to run it (45–60 min)
| Step | Time | Do not leave until |
|---|---|---|
| 1. Requirements | 8–10 min | Key, window, accuracy, fail-open vs closed, 429 contract |
| 2. API / placement | 3–5 min | Where it sits (gateway); what deny looks like |
| 3. High-level design | 12–15 min | Shared atomic counter (or they can defend local+sync); two servers cannot double the quota |
| 4. Deep dives | 12–15 min | Two of: race on increment, hot key, limiter down, burst vs average, multi-region |
| 5. EM close | 3–5 min | v1 Redis token/sliding window; separate SLOs for vote vs read; this domain keys |
If time dies, skip multi-region consensus. Keep atomic increment and fail policy.
Step 1 — Requirements
Open
“Two app servers, one customer, limit 100/min. Both see 99. What happens?”
If they say in-memory map per box: “You just doubled the quota. Is that OK?”
They should ask
- Key (user, API key, IP, tenant, endpoint)?
- Window and burst?
- Hard cap vs soft?
- QPS on the limiter?
- Single region?
- Fail-open or fail-closed?
- What does the client see?
Answers when asked
| Question | Give them |
|---|---|
| Key | Tenant / API key / agent id, optionally × endpoint. this domain: one bank must not exhaust another’s budget. Cardinality is thousands of tenants, not billions of IPs — unless they also rate-limit by IP for abuse. |
| Window | e.g. 100 rps burst and 100k/day. Let them pick one primary window for v1. |
| Accuracy | Soft cap to protect backends and agent APIs is enough for v1. Hard billing-grade cap is out of scope (SDS). A few extra allows under race is OK if they name it. |
| Placement | API gateway / sidecar. Not inside every random service with a different Redis. |
| Fail | Product decision. this domain default to offer: fail-closed on writes that hit an agent or vote submit; fail-open on unauthenticated health; discuss reads. Do not pick fail-open for everything because “availability.” |
| Deny | HTTP 429, Retry-After, remaining quota if cheap. Hidden 429 causes thundering retries. |
| Region | Start single-region Azure. Global exact limit is harder; overage by design if they go multi-region. |
| Scale | Gateway QPS in the thousands–tens of thousands is plenty. Don’t invent 40M quote/sec unless they drift to Robinhood. |
Gate
They have a key, a window, and a failure policy.
Weak: nginx limit_req on one box, hope.
Strong: “Shared counter with atomic INCR; fail-closed on vote/agent; 429 with Retry-After.”
Step 2 — API / placement
Want: check happens before the expensive handler. Return 429 + Retry-After. Optionally headers for remaining.
Admin: configure limit per key/tier (can be a file/config v1).
Gate
Limiter is in the request path they can point to, not a batch job.
Step 3 — High-level design
One box at a time.
- Clients → LB → app/gateway
- Rate-limit library or service: atomic get-and-increment on a shared store (Redis INCR + TTL is enough for v1)
- Config for limits
- Metrics: allowed, denied, limiter latency, limiter errors
- Optional local token cache only if they accept bounded overage
Push
- “Two servers, same key, same millisecond.”
- “Redis blips for 2 seconds. Vote submit?”
- “One agent’s adapter job storms the limiter key.”
Traps
| Trap | Follow-up |
|---|---|
| Read, add, write in app code | Classic race. Need INCR / Lua / single-threaded counter. |
| Per-pod counter with no shared state | Silent 2×, 3×, N× quota. |
| Global lock | Latency. |
Same limit for GET position and POST vote | Different blast radius. |
| Fail-open always | “We just DDoS’d the agent during an outage of our Redis.” |
Gate
They can explain why N servers do not each grant a full quota (or they explicitly accept overage of N× and you make them say it to an exec).
Step 4 — Deep dives (pick 2–3)
A. Atomic increment
INCR + expire. If they name token bucket / sliding window, good. Fixed window boundary burst is OK if they know it.
B. Hot key
One bank at voting deadline. Shard sub-counters or isolate that key, or raise limit with admission control. Don’t pretend hash(user) saves you when the key is the bank.
C. Limiter down
Fail-closed vs fail-open by route class. Circuit breaker. Cache last decision only with a short TTL if they must.
D. Burst vs average
Token bucket: agent batch vs smooth poll. Protect the agent with a leaky/smooth limit on outbound connector calls (Phia rate-limit instinct).
E. Multi-region
v1 skip. If they insist: eventual overage or a regional limit. Don’t invent Paxos in 5 minutes.
Step 5 — EM close
- v1: Redis INCR per
(tenant, route_class), 429 + Retry-After, metrics, fail-closed on agent-write and vote submit. Not a global exact window across continents. - Topology: platform / gateway owns it; product teams don’t each ship a limiter. DX: one library, one dashboard.
- KPI: 429 rate by tenant, limiter p99, accidental overage, outbound agent 429s (are we the bad client?)
- Exec: “We can be slightly loose on reads, or we can knock JPM’s servicing API over because Redis blinked. I fail-closed the write path.”
- this domain: noisy-neighbor banks; voting deadline stampede; don’t hammer agent on reconnect (pair with webhook / ingest).
Rubric
| Weak | Hireable | Strong | |
|---|---|---|---|
| Requirements | “100 req/s” only | Key + window | Fail-open/closed as a product/risk call |
| Design | Per-server map | Redis INCR | Race explained; hot tenant; 429 contract |
| EM | Algorithm soup | Mentions gateway | Route-class policy, platform ownership, agent protection |