Distributed API rate limiter — a full worked answer
The whole thing, start to finish, in the order you would actually say it. Read it to learn the shape of a strong answer — then go and produce one yourself, because reading is not the same skill as producing.
The question
Design a rate limiter for a public API served from many machines across several regions. Each customer has a plan with a request quota. The limiter must not become the reason the API is slow or down.
Limits and abuse. Deciding whether to say no, cheaply, on every request.
The decision has to be faster than the work it protects, which rules out most of the accurate answers.
Before anything: where is the slack?
How long the system has before a person notices. Ask this before you draw a single box — it decides more of the design than scale does.
No time slack at all, because the decision sits in front of every request. But a lot of accuracy slack, and the design is built on that trade.
There is no latency to spend. The limiter runs before the work it protects, on every request, so it must cost a fraction of what it saves. A limiter that adds 20 ms to protect a 30 ms endpoint has made things worse. A realistic budget is about a millisecond, which rules out anything that needs coordination between regions.
But the accuracy budget is wide, and seeing that is what makes the problem tractable. If a customer's limit is 1,000 requests a minute and they occasionally get 1,050 through, the backend barely notices. The limit exists to protect capacity and prevent abuse, and both goals survive a few percent of error, as long as capacity was planned with that margin.
That asymmetry is unusual. Most systems in this app trade latency for accuracy in small amounts; here you can trade a lot of accuracy for a little latency, and you should say so out loud.
The one place accuracy tightens is security limits: login attempts and password resets. There, being generous means letting an attacker have more guesses, so those get exact counting and a slower path, because they are rare enough to afford it.
So: A millisecond budget plus generous accuracy means local decisions with asynchronous reconciliation instead of a globally consistent counter. It also means capacity limits must fail open, because a limiter outage must not become an API outage.
Requirements
about 5 minWhy this stage exists: Because the question is deliberately vague, and every box you draw before this is a guess.
Assumptions: a public API on tens of thousands of servers across several regions. Customers authenticate with an API key. Plans differ, so limits are per-key configuration rather than a constant. Request volume is hundreds of thousands per second, and the limiter sits in front of all of it.
First question, and it decides whether this is easy or hard: is the quota global across all regions, or per region? A global quota means every decision needs information from every region, and a cross-region round trip is up to 150 ms against a 1 ms budget. So a strictly global quota is not achievable, and I need to say that rather than pretend. I will assume the quota is global as a business promise, but enforced approximately, with the error bounded and stated.
Second question: how exact must it be? Exact counting forces coordination and approximate counting does not, so the answer changes the architecture. I will assume a few percent of over-admission is acceptable for normal quotas, and separately that security-sensitive limits like login attempts need exact counting on a slower path.
Scope: decide allow or reject per request, support per-key limits, work across regions, and degrade safely. Out of scope: billing, quota purchasing, and the abuse detection system that decides who deserves a limit change.
What an interviewer is ticking off in this stage
- Asked global versus per-region quota and named the latency problem with global
- Asked how exact the limit must be, and treated it as an architecture question
- Separated security limits from capacity limits
- Stated that limits are per-key configuration, not constants
- Proposed a scope and excluded billing and abuse detection
Actors and lifecycle
about 6 minWhy this stage exists: Because the happy path is the easy half. The failure branches are where the design actually lives.
Actors: the API client, the API itself, the operator who sets limits, and the system. The system decides what key to count against, whether a request is cheap or expensive, what to do when it cannot reach the counter store, and whether a rejection should be counted at all.
The chain: request arrives → identity resolved to a limit key → limit configuration looked up → counter checked and incremented → allowed or rejected → counters reconciled across regions.
The failure branches matter more than usual because this component sits in front of everything. At identity resolved: there is no API key, so the request is anonymous and falls back to an IP-based limit. That punishes shared networks (an office behind one NAT), so it needs a looser threshold. At configuration lookup: the config store is unreachable. So configuration must be cached locally with a long TTL, because fetching it per request would be both slow and fragile.
At counter checked: the counter store is down. This is the branch that defines the design. The choice is fail open (allow everything and lose protection) or fail closed (reject everything and take the API down). Fail open is almost always right, because a limiter outage that becomes a total API outage is a much worse incident than a window of unlimited traffic. But it must be a stated decision with a fallback: fall back to a coarse per-server local limit, so we are degraded rather than defenceless. The exception is security limits, which fail closed, because allowing unlimited password attempts is worse than rejecting logins.
At counter checked: the store is slow rather than down. That is more dangerous than being down, because requests pile up waiting. So there is a hard timeout of a couple of milliseconds and the same fallback applies.
At rejected: the client retries immediately and makes it worse. So the rejection must carry Retry-After, and it must be cheap to produce, since during an attack most responses are rejections. At reconciled: a region is partitioned, so counts drift and the customer gets more than their quota until it heals. That is bounded and acceptable, and worth saying.
One decision the system makes without anyone asking: not all requests cost the same. A cheap read and an expensive export should not consume the same quota, so the design needs a notion of cost per request, or one export endpoint will let a customer consume everything.
What an interviewer is ticking off in this stage
- Named the system as an actor with real decisions
- Traced a request through the limiter as a chain
- Handled anonymous requests with an IP fallback and noted the shared-network problem
- Cached limit configuration locally
- Made an explicit fail-open decision with a stated fallback
- Made security limits fail closed instead
- Handled a slow store, not just a dead one, with a hard timeout
- Rejections carry Retry-After and are cheap to produce
- Raised weighted cost per request
The lifecycle, drawn
Numbers
about 6 minWhy this stage exists: Because one part of this is hard and the rest is easy, and they look identical until you do the arithmetic.
Requests: 500,000 per second across the platform at peak. Every one needs a limit decision, so the limiter runs on every request. Nothing behind it runs more often.
Naively that means 500,000 counter operations per second against a shared store, plus 500,000 network round trips. Even at 0.5 ms each, that is a network hop on every request and a store handling half a million operations a second. That is expensive and fragile.
State size, which is the number that changes my mind: a counter is a key, a count and a window timestamp — under 100 bytes. Even a million active API keys is 100 MB. All the state fits comfortably in memory on one machine.
That reframes the problem. This is a coordination problem, not a data problem: the state is small, and the difficulty is keeping many machines roughly in agreement about it, cheaply.
Cross-region: up to 150 ms round trip against a 1 ms budget. So no request-path decision may cross a region. This is a structural constraint rather than something to tune, and it rules out global consistency on the request path.
Rejection volume during an attack: an attacker sending 10 million requests a second means the limiter produces 10 million rejections a second, so the rejection path must be cheaper than the accept path: no database read, no logging of full request bodies, no expensive work at all.
So the hard part here is making a decision without coordination, on every request, while keeping many machines approximately in agreement, and failing safely when that breaks.
What an interviewer is ticking off in this stage
- Noted the limiter runs more often than anything it protects
- Calculated naive counter operations and identified the per-request network hop as the problem
- Concluded total state is tiny and fits in memory
- Reframed it as a coordination problem rather than a data problem
- Checked the cross-region latency against the budget and ruled global consistency out
- Noted the rejection path must be cheaper than the accept path
- Finished the sentence
The numbers, drawn
A cross-region hop is 150x the budget, so global consistency on the request path is ruled out. So the hard part is deciding without coordinating: trade accuracy, which you have plenty of, for latency, which you have none of.
High-level design
about 12 minWhy this stage exists: Because now — and only now — you have a reason for every box you are about to draw.
Algorithm: token bucket. Tokens refill at a steady rate up to a maximum; a request takes one or is rejected. I choose it because real API traffic arrives in bursts, and the bucket size gives me an explicit, tunable burst allowance separate from the sustained rate. Fixed windows do not. It is also cheap to represent: a token count and a last-refill timestamp, with refill computed lazily on read rather than by a background process. So there are no timers and no sweeper.
The architecture is local-first with asynchronous reconciliation, and this follows from the numbers. Each server keeps in-memory buckets for the keys it has recently seen and decides locally with no network call, which is what fits the 1 ms budget. Servers periodically, every hundred milliseconds or so, publish their consumption to a shared store and read back the aggregate, adjusting their local view. So the decision is instant and the agreement is eventual.
The consequence: a customer can briefly exceed their quota, roughly by the number of servers times the amount consumed between syncs. I would bound that by making servers sync more often as a key approaches its limit (cheap, because only a few keys are near their limit at any moment) and by giving each server a share of the quota rather than the whole thing. Cost: a customer whose traffic is unevenly spread may be limited slightly early on some servers.
Placement: the limiter runs at the gateway, before requests reach any service. Rejecting at the edge is what makes rejection cheap. Letting a request through to a service before rejecting it wastes the resources you were protecting.
Configuration: limits per key are held in a config store, cached locally with a TTL of minutes and updated by push when changed. This comes from the Stage 2 branch: a per-request config lookup would be both a latency cost and a dependency on the request path.
Regions: each region enforces its share of the global quota independently, with counts reconciled asynchronously across regions. There is no cross-region call on the request path, which is a hard requirement from the latency numbers. Cost: a customer spreading traffic across regions gets more than their nominal quota until reconciliation catches up. That is bounded, and I would state the bound.
Security limits take a different path on purpose: login attempts go to a strongly consistent counter with an exact check, accepting the higher latency, because those are rare and being generous there has a real security cost. Two paths for two purposes.
The response: 429 with Retry-After and headers showing limit, remaining and reset. This answers the retry-storm branch: a well-behaved client that knows when to come back waits, and a client that gets a bare error tends to retry immediately.
What an interviewer is ticking off in this stage
- Chose token bucket and justified it with burst behaviour
- Local in-memory decision with no network call on the request path
- Asynchronous reconciliation, with the sync interval stated
- Quantified and bounded the over-admission error
- Placed the limiter at the gateway and said why
- Configuration cached locally rather than fetched per request
- Per-region enforcement with async reconciliation and a stated bound
- Separate exact path for security-sensitive limits
- Proper 429 with Retry-After and quota headers
The architecture, drawn
Deep dive and tradeoffs
about 14 minWhy this stage exists: Because naming what a decision costs is the single clearest signal of seniority there is.
Hard part one: failure behaviour, which is what this component is judged on. If the shared store is unreachable, servers keep deciding from their local buckets. We degrade to per-server limits rather than losing all protection, which is better than either extreme. So the local bucket must always be maintained, not only used as a cache. If a server is new and has no local state, it starts with a conservative share of the quota rather than the whole thing, so a fleet-wide restart does not multiply everyone's effective limit by the server count. Cost: a newly started server is slightly stingy for its first few seconds.
The fail-open decision, stated plainly: capacity limits fail open, security limits fail closed. The reasoning is what each failure costs. An outage of the limiter should not be an outage of the API, but unlimited password guessing is worse than rejected logins. I would also alert loudly in degraded mode, because failing open without an alert means running unprotected without knowing.
Hot key: one large customer generating most of the traffic means their counter is updated by every server constantly, and their reconciliation traffic dominates. Since only a few keys are hot, handle them specifically: give a large customer a dedicated quota shard per region, and sync theirs more often. Cost: special handling for a small set of keys, which needs to be automatic (detected by traffic) rather than a manual list someone maintains and forgets.
Hard part two: not punishing legitimate customers, which is where a limiter does business damage. Weighted costs so a cheap read and an expensive export do not draw on the same budget in the same way. Separate limits per endpoint class, so a burst of exports cannot lock a customer out of everything. And soft limits before hard ones: start shaping or queueing before rejecting outright, because for most API clients a slow answer is better than an error. Cost: shaping means holding requests, which consumes resources, so it needs a bound and a queue that can itself be rejected from.
Because limits are per-key configuration, raising one during an incident is a config change rather than a deploy. That sounds minor, but it can be the difference between a five-minute fix and an hour. It is a day-one design decision and I would call it out.
Time windows and clock skew: refill is computed from timestamps, so servers whose clocks disagree will compute different refills. Bound it by using a monotonic local clock for elapsed time rather than wall clock, so skew affects reconciliation rather than the local decision. Cost: a little more care in the implementation, and reconciliation needs to tolerate slightly inconsistent timestamps.
Consistency per feature: capacity counters are eventually consistent with a bounded error I can state. Configuration is eventually consistent within minutes, or immediately on push. Security counters are strongly consistent. Say those three separately. A single blanket statement would be wrong for two of them.
What I would monitor: rejection rate by customer (a jump means the customer is being attacked, is misbehaving, or has been misconfigured), decision latency at p99, reconciliation lag, and the count of servers currently in degraded local-only mode. That last number tells you the limiter is failing open right now. Without it you will not know.
What an interviewer is ticking off in this stage
- Degrades to per-server limits rather than losing protection entirely
- New servers start with a conservative share to survive a fleet restart
- Fail open for capacity, fail closed for security, with reasons
- Alerts when in degraded mode
- Hot keys detected automatically and given dedicated shards
- Weighted request costs and per-endpoint-class limits
- Soft limiting before hard rejection, with a bound
- Limits changeable by config, not deploy
- Handled clock skew by using monotonic elapsed time locally
- Per-feature consistency answer and a monitoring list
- Cost named after every decision
The decision this turns on
- —Zero network calls on the request path, so comfortably inside 1 ms.
- —Survives the counter store being down: degrades to per-server limits.
- —Over-admission bounded by servers × sync interval, and you can state the bound.
- —A customer spreading across regions gets somewhat more than their quota.
- —Accurate within a region, and easy to explain to a customer.
- —Adds a network hop to the most-executed code path in the system.
- —The store becomes a hard dependency of every request.
- —Still cannot be globally accurate: a cross-region hop is 150x the budget.
And then they push back
A complete answer is where the interview starts, not where it ends. These are the questions this design invites — the interview is decided here far more often than in the diagram.
The cache just died. What happens?
"Requests would go to the database instead, so it would be a bit slower." At the ratios that justify a cache, the database cannot take that load. This answer means you added a cache without checking what it was protecting you from.
"Every read that was being served from memory lands on the database at once. My cache was absorbing something like 99% of reads, so the database sees roughly 100x its normal load, and it will not survive that. A naive design goes down. What I would do about it, designed in advance: coalesce misses so a thousand simultaneous requests for the same key produce one database read rather than a thousand; keep a small in-process cache on each server as a second layer so the hottest keys never leave the machine; shed load at the edge rather than let the database die, because a degraded site beats a dead one; and bring the cache back warm rather than empty, because restarting into an empty cache reproduces the outage. Cost of the in-process layer: servers can briefly disagree with each other."
One key gets 90% of the traffic. What breaks, and what do you do?
"Consistent hashing spreads the load evenly." It spreads keys evenly, not traffic. All requests for one key go to one place no matter how the keys are hashed. This answer confuses two different problems.
"Whichever node owns that key is saturated while the rest idle, and no partitioning scheme fixes it because partitioning distributes keys, not requests for a single key. Three options. Replicate the hot key across N nodes with a suffix and read a random one. It costs N times the memory and a fanned-out invalidation, and it is the right answer for a read-hot key. For a write-hot key, shard the counter and sum on read, accepting that the total is now a computed value. Or handle it on a separate path: an in-process cache on every server absorbs a read-hot key almost completely. I would also detect hot keys automatically with a count-min sketch rather than maintaining a manual list, because yesterday's hot key is not today's."
Two users click at the same millisecond. What happens?
"We would use a lock." Which lock, held where, and what happens if the holder pauses? A lock is a mechanism, and reaching for it before asking whether the resource is contested at all is a reflex rather than an answer.
"First I would ask whether the thing is contested. If it is a like button, both writes land, the count converges, and I would choose not to spend a transaction on it. If it is the last seat, exactly one must win, and I get that by making the decision at a single point of serialisation: a conditional update that only succeeds if the seat is still free, or a unique constraint so the second insert simply fails. I am not proposing to read and then write in application code, because that gap is the race itself. The loser gets a clear message and an alternative, not an error. Cost: that path is now strongly consistent, so it is slower and it becomes unavailable if the owning partition is unreachable, which I accept, because selling one seat twice is worse than an error message. I would specifically not add a distributed lock, because the database row is already a single point of serialisation and a lock adds a failure mode where a paused holder's lease expires and two processes both think they won."
Why a queue instead of just calling the service directly?
"Queues decouple services and are more scalable." True in the abstract and it does not explain why this particular call needs one. Queues also add duplicate delivery, ordering questions and debugging difficulty, and not mentioning those means you added one by reflex.
"Because the user does not need to wait for this work to finish, and because the downstream cannot absorb my spikes. Concretely: sending the receipt email takes 800 ms and can fail, and there is no reason to make the customer wait for it or to fail their order because a mail provider is down. The queue absorbs a 10x spike into a longer backlog instead of a broken service. What it costs: the customer gets 'received' rather than 'done', so the product has to be honest about that; every consumer must be idempotent because delivery is at-least-once; and a failure now happens in a worker minutes later, which is harder to debug. I would not queue the stock check or the payment, because the user needs a real yes-or-no answer before they leave the page. A queue there adds latency and buys nothing."
Which alert fires first when this system starts failing?
"We would alert on CPU and memory." Those are symptoms of the machine, not of the user experience, and they fire either far too late or constantly for no reason.
"I would alert on user-visible symptoms first and causes second. The first alert should be error rate or latency at p99 on the main user path, because that is what maps to someone being unhappy. Then a small number of leading indicators that fire before users notice: queue age (not depth), because age maps directly to how late the work is; replication lag; cache hit rate dropping, which precedes database saturation; and connection pool wait time, which is the earliest sign of a slow dependency. For this system specifically, the earliest signal is usually cache hit rate, because everything downstream is sized assuming the cache absorbs most reads. I would not page on CPU. It is a dashboard metric, not an alert, because a machine at 90% CPU serving requests fine is not an incident, and a machine at 20% CPU timing out is."
A whole region is down. What do users see?
"We failover to another region." That is the mechanism, not the answer. The question is what a user experiences, for how long, and what is lost.
"I would answer per path rather than globally. Reads: if replicas exist elsewhere, they keep working, possibly stale, and I would say how stale. Writes: if the leader was in the dead region, writes fail until a new leader is promoted. That takes seconds to a minute, and being aggressive about promotion risks promoting during a brief network blip and ending up with two leaders. For contested resources like inventory I would rather be unavailable for that region's writes than risk selling the same thing twice, and I would say that explicitly as a choice. For non-contested writes like posting a comment, take it locally and reconcile. Data loss: with async replication, anything committed in the last few seconds and not yet replicated is gone, so I would use semi-synchronous replication for anything I cannot lose. And DNS-based failover is slow because clients cache DNS for minutes, so I would not rely on it alone."
There is an option that is 40% cheaper but 10% slower. Do you take it?
"I would take the faster one because user experience matters." Reflexive. 10% slower may be entirely invisible, and 40% is a large amount of money that could fund things users would actually notice.
"It depends where in the system, and I would answer with the slack budget. On the playback start path, where the budget is two seconds and users leave past it, 10% slower is meaningful and I would not take it. On the transcoding pipeline, where I have hours of slack, 10% slower is invisible and I would take the 40%. That is what the slack is for. So my answer is: take it everywhere the user cannot perceive the difference, refuse it on the paths where a human is waiting. Concretely that means interruptible capacity for batch work, cheaper storage tiers for cold data, and premium capacity only for the request path. And I would want to know whether the 10% is on the median or the tail, because a 10% worse p99 can be much more damaging than a 10% worse median."
10x traffic tomorrow. What fails first?
"We would add more servers and scale horizontally." This says nothing. Every system has a first thing to break, and not naming it means you do not know your own design well enough to have found it.
Name a specific component and the reason. "The stateless services scale out fine, so they are not the constraint. The database primary is, because every write goes through one machine and I am at roughly 40% of its write capacity now. So at 4x I am at the ceiling, and I would see write latency climb and connection pool waits before anything errors. The second thing is the cache, because 10x reads on a fixed working set is fine but 10x on a growing key space means my hit rate drops and the misses land on the database that is already the constraint. In order: database writes, then cache hit rate, then the connection pool. And I would find out from p99 write latency, not from errors."
The topics this answer used
You have read a good answer. That is worth very little until you can produce one on a blank page — so go and write this problem without looking, and compare afterwards.