Scope the requirements
This is infrastructure, so the requirements are about behaviour under pressure, not features. The interviewer wants three things named early: limits are global across the fleet (not per-server), the check must be nearly free, and being slightly wrong is acceptable — being slow is not.
Functional — what it must do
- Identify clients by user ID, API key, or IP, and enforce configurable rules — e.g. 100 requests/min per user per endpoint.
- Reject over-limit requests with 429 plus headers that tell the client its limit, remaining budget, and when to retry.
- Multiple rules and tiers per endpoint; rules updatable without redeploying the fleet.
- Limits are global across all servers — a client hitting 10 gateways shares one budget.
- Explicitly cut: billing/quota accounting (monthly caps with invoices) — that needs durable exactness this design deliberately trades away.
Non-functional — the numbers that shape the design
- Check overhead under 10 ms added to every request — ideally ~1 ms; the limiter must be cheaper than what it protects.
- Scale: 1M requests/s across the fleet, ~100M distinct clients.
- Highly available; eventual consistency is acceptable — admitting a few extra requests during a race is fine, blocking legitimate traffic at scale is not.
- Memory per client small enough that 100M clients fit in a few GB of cache.
- An explicit, decided behaviour when the limiter's own store fails.
The word doing the work is global — per-server counters would let a client multiply its limit by the fleet size. So the counter state has to live somewhere shared, which makes this a question about a fast shared store, atomic updates, and what happens when that store is down.
Back-of-envelope estimates
The numbers here size the Redis tier and — more usefully — kill a common over-engineering instinct: the state is tiny, it's the ops rate that forces sharding.
| Quantity | Estimate | How you got there |
|---|---|---|
| Check rate | 1M/s | One limiter check per request; reads and writes to the counter store are the same operation. |
| Redis shards | ~10 | A Redis node does ~100k ops/s; 1M/s ÷ 100k with headroom → ~10 shards, hashed by client ID. |
| State per client | ~50 B | Token bucket = token count + last-refill timestamp; a small hash per (client, rule). |
| Total state | ~5 GB | 100M clients × 50 B. Tiny — sharding is for throughput, not capacity. Say that out loud. |
| Latency budget | ~1 ms | Same-DC round trip ~0.5 ms with pooled connections; a cold TCP+TLS handshake is 20–50 ms, so pooling is mandatory, not an optimisation. |
| Rules | KBs, in-process | Hundreds of rules cached in gateway memory, refreshed ~30 s — never a per-request fetch. |
Five gigabytes of state but a million operations a second — so I shard Redis for throughput, not size. And the latency budget is dominated by the network round trip, which tells me connection pooling and colocating Redis with the gateways matter more than shaving algorithm CPU.
Sketch the API
The client-facing surface is really a response contract — status code plus headers. Internally it's one function call in gateway middleware, plus a small config API for rules.
X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset, Retry-After. Returned on the fast path, before any backend work.- Headers are part of the design, not decoration: a 429 without
Retry-Afterteaches every client to hammer you in a tight loop. Well-behaved SDKs read the headers and back off with jitter — the limiter and the client SDK are two halves of one protocol. - Rules live in config, never in code. "Change the free tier from 100 to 200 req/min" must be a config write that propagates in seconds, not a fleet redeploy.
Data model
Two kinds of state with opposite lifecycles: slow-moving rules, and counter state that churns millions of times a second.
EXPIRE ≈ 1 h past the window, so idle clients' state evaporates and memory self-cleans.The hot store is Redis, and that's a real decision, not a default: I need atomic operations at a million ops a second with sub-millisecond latency, and I'm allowed to lose the state — a flushed counter means a client briefly gets a fresh budget, which the requirements already tolerate. Rules go in Postgres because they're config: tiny, relational, audited. If the business later demands exact durable quotas — billing — that's a different system with a real ledger, and I'd say so rather than bend this one.
High-level design
The limiter is middleware in the API gateway: check Redis atomically, reject fast or pass through. Rules flow in from a config service; nothing on the request path ever waits on anything but one Redis call.
- A request hits the gateway; middleware resolves which rules apply from its in-memory rule cache — no I/O.
- The gateway runs one Lua script against the Redis shard owning this client's key: refill tokens by elapsed time, decrement if positive, return the verdict — all atomic, one round trip, ~1 ms.
- Allowed → forward to the backend with rate-limit headers attached. Denied → 429 immediately; the backend never sees the request, which is the whole point of the fast-path rejection.
- Rule changes are written through the rules service to Postgres; gateways poll (or subscribe via a watch) and swap their in-memory copy within ~30 s.
- Sampled decisions stream to analytics asynchronously for tuning limits and spotting abuse.
Deep dives — where the interview is won
Token bucket by default; sliding window counter when bursts must die
Walk the ladder rather than naming one winner. Fixed window (counter per minute) is trivial but leaks 2× at the boundary — 100 requests at 0:59 and 100 more at 1:01 is 200 in two seconds, all legal. Sliding window log fixes that exactly by storing a timestamp per request, and pays for the exactness in memory — untenable at 100M clients. Sliding window counter interpolates between the current and previous windows' counts — a close approximation for two integers of memory; it's what Cloudflare runs, and their data shows the error is negligible on real traffic. Token bucket stores a token count and refill timestamp, allowing bursts up to bucket capacity while enforcing the steady rate.
My default is the token bucket, and the reason is product, not maths: real clients are bursty — a page load fires ten API calls at once — and the bucket lets me say "burst to 100, sustain 10/s" as two independent knobs. If the requirement is a hard ceiling with no boundary games (say, protecting a fragile downstream), sliding window counter. What's being scored is knowing why fixed window is wrong and choosing on workload, not reciting five names.
Atomicity: the race condition is the real question
The naive implementation reads the counter, checks it, and writes it back — three steps. Two gateways doing this concurrently for the same client both read "1 token left", both admit, both decrement: the client got 2 for 1. At a million requests a second this isn't a corner case, it's continuous, and a determined client can exploit it deliberately by parallelising requests.
The fix is making check-and-decrement a single atomic operation in the store. In Redis that's a short Lua script — refill by elapsed time, test, decrement, return — which executes atomically because Redis is single-threaded per shard. Distributed locks are the wrong answer: a lock round trip per request doubles latency and adds a failure mode, to serialise something Redis will serialise for free. For the simplest algorithms plain INCR with EXPIRE also works; the point to land is that atomicity lives in the store, not in application-level read-modify-write.
Fail open or fail closed — decide before Redis decides for you
When the counter store is unreachable, there are exactly two behaviours: fail open (admit everything, protection off) or fail closed (reject everything the limiter can't vouch for). Neither is safe as an accident. Fail open means the moment you most need protection — a traffic spike straining Redis — is the moment protection vanishes. Fail closed means a Redis blip becomes a self-inflicted total outage for legitimate users.
My answer: fail open for user-facing product APIs, because the limiter exists to protect capacity and killing all traffic destroys more value than a few minutes of unlimited traffic risks — but with a local in-memory fallback limiter per gateway at a conservative fraction of the global limit, so "open" is never "unbounded". Fail closed where the limiter is a security control — login attempts, OTP sends, password resets — because there the cost of unthrottled traffic is account takeover, not overload. Naming the split, rather than picking one religiously, is what distinguishes the answer.
Sharding by client, and the client who becomes the hot shard
Ten Redis shards, keys distributed by consistent hashing on client ID — each client's state lives on exactly one shard, so atomicity never spans nodes, and adding a shard remaps only a slice of the keyspace. Each shard carries an async replica for failover; losing a shard loses some counters, which is a brief budget refresh for those clients, not an incident.
The residual problem is concentration: one abusive client (or one enormous customer) hammers a single shard by construction. Answers in escalating order: the shard rejecting at 100k ops/s is the limiter working — rejection is cheap; a gateway-local negative cache ("this client is limited until :42") stops even the Redis round trip for repeat offenders; persistent abusers move to a blocklist evaluated in gateway memory; and volumetric DDoS belongs upstream in the CDN/edge layer, not in this system — say that boundary explicitly.
Follow-ups you should expect
Where should the limiter live — client, gateway, or each service?
Could you avoid the Redis round trip entirely?
How does this work multi-region?
What's a well-behaved client supposed to do on 429?
Retry-After and back off with jitter — and I'd ship that behaviour in the official SDKs rather than hope. Jitter matters: without it, every throttled client retries at the same instant and the reset boundary becomes a synchronised stampede. The headers are the API contract that makes throttling cooperative instead of adversarial.How do you roll out a new, stricter limit safely?
Where candidates lose the room
- Per-server in-memory counters as the design — every client's real limit silently becomes limit × N servers, which fails the one-word requirement (global) the question hangs on.
- A single Redis instance in front of 1M req/s with no sharding story — the estimate that catches this takes thirty seconds, and skipping it is the tell.
- Read-check-write on the counter without atomicity — the race condition is the deep-dive interviewers hold in reserve, and application-level locks as the fix trade one failure for a slower one.
- No answer for "Redis is down" — shrugging at the failure mode of the component you added is worse than either fail-open or fail-closed chosen deliberately.
- Returning a bare 429 with no headers, and micro-optimising algorithm CPU while ignoring that the network round trip is 100× the cost of the arithmetic.