Appearance
11.3 — Distributed Rate Limiter
A customer is told they get 100 requests per second. They send exactly 100 requests per second and get rejected. You investigate and find that their traffic landed on eight different servers, each of which independently thought it was seeing a small fraction of the limit, and the shared counter they all incremented was being read and written without coordination — so three of the eight read the same value and all three decided there was room.
The opposite failure is just as common and worse. The same customer sends 200 requests in a single second across those eight servers and every one is allowed, because each server was tracking its own counter and none of them ever saw the total.
9.7.5 built the algorithms inside one process, where the counter was a variable and correctness was a matter of holding a lock. This study turns them into a service for an API platform: shared across replicas, correct while thousands of requests hit the same key at once, fast enough to sit in front of every request in the company, and — the part that decides whether the design is any good — sensible when its own dependencies are down.
1. Requirements
Functional. Enforce a limit per key, where a key can be an API key, a user, an IP address, or a combination of one of those with an endpoint. Support several tiers with different limits. Allow bursts within a defined allowance. Return the standard RateLimit-* headers and Retry-After. Let limits change without a deploy.
Non-functional, with numbers.
- Decision latency under 5 ms at the 99th percentile. This sits in front of every request the platform serves, so its latency is added to every endpoint's latency. A limiter that costs 20 ms is a tax on the entire product.
- Accuracy within a few per cent. Not exact. Exactness costs coordination, and the product promise "100 requests per second" was never a precise physical claim — but 100 must not silently mean 300.
- It must not be a single point of failure. The limiter protects the platform; it must never be the thing that takes the platform down.
- It must survive hot keys, where one customer sends 40% of all traffic and therefore hammers one key.
Out of scope today: volumetric denial-of-service defence, which belongs at the edge and works on different signals (10.9), and billing-grade metering, which needs an audit trail the limiter deliberately does not keep.
The clarifying questions, and what each answer changes
"Is this protecting a backend, or enforcing a commercial quota?" These sound the same and are not. Protection wants to be fast and approximate and may fail open. A commercial quota is something a customer paid for and will dispute, which pulls the accuracy requirement up sharply and adds an audit obligation. Most limiters are asked to do both, and separating them is half the design.
"What are we limiting on — identity or address?" Identity is fair and requires authentication before limiting, which means unauthenticated abuse hits the auth service. Address is available immediately and punishes everyone behind a shared connection, and it is trivially rotated by anyone determined. Almost every real system uses both, at different points in the pipeline.
"When we reject, what should the client do?" If the answer is "back off and retry", you owe them a Retry-After value that is actually correct, which constrains which algorithm you can use — some cannot compute when the next request will be allowed.
"Is a burst acceptable?" "Ten per second" can mean ten spread evenly, or sixty in one second as long as the ten-minute average holds. These are different products and different algorithms, and the answer usually is that bursts are fine because real clients are bursty.
"What happens if the limiter is down?" Ask this in minute three, not minute forty. It is the most important decision in the entire design and it is a product decision, not a technical one.
2. Estimation
Decision volume. 100,000 requests a second across the platform, each needing one decision. If every decision is a network round trip to a shared store, that is 100,000 operations a second to that store. What that forces: one modest shared store instance handles roughly this, which means the design works and has no headroom at all. A single busy customer, a retry storm, or a second service adopting the limiter doubles it. So the architecture must have a way to remove load from the shared store rather than only a way to add capacity to it.
Latency budget. A round trip to the shared store inside one datacentre is about 0.5 ms, plus the store's own work. Against a 5 ms budget that seems comfortable — until you notice that this is per request, and any queueing at the store shows up directly in every endpoint's tail. What that forces: a local tier that answers some decisions with zero network work, and a circuit breaker on the limiter call so that a slow store cannot become the latency it was supposed to prevent.
Key space and memory. 1 million active API keys × ~100 bytes of state (a token count, a timestamp, a little overhead) = 100 MB. What that forces: nothing. The state is tiny, which is worth saying because it kills a whole class of wrong instincts — you do not need a database for this, and you do not need to worry about the size of the key space. Adding a TTL so idle keys evaporate keeps it that way forever.
Traffic concentration. If one customer is 40% of traffic, one key is receiving 40,000 operations a second. What that forces: the most interesting problem in this design. Sharding distributes keys, and this is one key, so no amount of cluster capacity fixes it. Section 6.3 is entirely about this number.
Rejection volume during an incident. Under an abuse event, rejections can outnumber successes ten to one, so the limiter's rejection path must be cheaper than its accept path, not more expensive. What that forces: the local tier must be able to reject without touching the network at all, because otherwise an attack turns into a self-inflicted load test of your shared store.
3. API
The limiter is consumed two ways. Inside services written in your main language it is a library in the request pipeline, which is the fastest option because the local tier lives in the same process. For a fleet with many languages it runs as a sidecar or a small service (10.8.3), which costs one local network hop and buys one implementation instead of five.
http
POST /check
{ "key": "acct_8812", "scope": "api:search", "cost": 10 }http
200 OK
{ "allowed": true, "remaining": 4390, "limit": 5000,
"resetAt": "2026-07-31T09:15:00Z", "retryAfterMs": 0 }http
200 OK
{ "allowed": false, "remaining": 0, "limit": 5000,
"resetAt": "2026-07-31T09:15:00Z", "retryAfterMs": 740 }Note that a rejection is still a 200 from the limiter. The limiter answers a question; it does not serve the user's request. The caller turns allowed: false into a 429:
http
429 Too Many Requests
Retry-After: 1
RateLimit-Limit: 5000
RateLimit-Remaining: 0
RateLimit-Reset: 37
{ "error": { "code": "rate_limited",
"message": "Rate limit exceeded. Retry in about 1 second.",
"requestId": "req_01J9F41K2" } }Three decisions worth stating.
The headers go on successful responses too. RateLimit-Remaining: 4390 on a 200 lets a well-behaved client slow itself down before it ever gets rejected. Sending the headers only on the 429 means the only feedback a client gets is failure, which trains clients to retry rather than to pace (9.6.1).
retryAfterMs must be computed, not guessed. A client told to retry in one second when the correct answer is 30 seconds will retry 30 times and make the incident worse. This constrains the algorithm: whatever you pick must be able to answer "when will there be room for a request of this cost?" Section 6.1 shows which algorithms can and which cannot.
cost is a parameter, not a constant. A search that runs a heavy query spends 10 tokens; a health check spends 0. Weighted limiting for free, decided by policy rather than by code.
4. Data model and the atomic decision
The state per (key, scope) is two numbers: how many tokens are left, and when that number was last updated.
bucket:{key}:{scope} → { tokens: 4390.0, ts: 1754003722145 } TTL 3600sThe whole difficulty is that reading it, deciding, and writing it back must be one indivisible step. Split it into a read and a write and two concurrent requests both read "3 tokens left", both decide there is room, and both spend the same three tokens. That is the check-then-act race from 9.5.1, and it is at its worst exactly when the limit matters most, because bursts are when concurrent requests for the same key are most likely.
In Redis the mechanism is a Lua script, because Redis runs scripts single-threaded and therefore atomically with respect to every other command:
lua
-- KEYS[1] = bucket key
-- ARGV = { nowMs, refillPerSec, capacity, cost }
local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts') -- (1)
local capacity = tonumber(ARGV[3])
local tokens = tonumber(state[1]) or capacity -- (2)
local ts = tonumber(state[2]) or tonumber(ARGV[1])
local elapsed = (tonumber(ARGV[1]) - ts) / 1000 -- (3)
tokens = math.min(capacity, tokens + elapsed * tonumber(ARGV[2])) -- (4)
local cost = tonumber(ARGV[4])
local allowed = tokens >= cost -- (5)
if allowed then tokens = tokens - cost end -- (6)
redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', ARGV[1]) -- (7)
redis.call('EXPIRE', KEYS[1], 3600) -- (8)
local waitMs = 0
if not allowed then
waitMs = math.ceil(((cost - tokens) / tonumber(ARGV[2])) * 1000) -- (9)
end
return { allowed and 1 or 0, math.floor(tokens), waitMs } -- (10)(1) reads both fields in one call, so the script starts with a consistent snapshot rather than two reads that could straddle another script. (2) a key that does not exist means a customer who has not been seen for an hour, and the right starting state is a full bucket — treating an unseen key as empty would reject a returning customer's first request, which is exactly backwards. (3) elapsed time in seconds since the bucket was last touched. This is the only clock reading in the whole decision, and it comes from the caller as nowMs, which matters for section 6.5. (4) lazy refill: instead of a background job topping up a million buckets every second, the bucket refills itself the next time anyone looks at it. math.min caps it at capacity so an idle month does not accumulate a month of tokens. (5) and (6) the decision and the spend, inside the same script, which is the entire point. (7) writes the new state. Note that the timestamp is written whether or not the request was allowed — otherwise a rejected request would leave ts stale and the next refill would double-count elapsed time. (8) the TTL is what keeps the key space at 100 MB forever. An hour of inactivity and the key disappears; the next request recreates it full, which is the same state it would have refilled to anyway. (9) the deficit divided by the refill rate is exactly how long until there is room. This is what makes Retry-After honest rather than a guess. (10) one round trip returns the decision, the remaining count for the headers, and the retry hint.
The client side, in TypeScript, with the failure policy visible rather than implied:
ts
type Verdict = { // (1)
allowed: boolean;
remaining: number;
retryAfterMs: number;
source: 'local' | 'shared' | 'degraded'; // (2)
};
async function check(key: string, scope: string, cost: number): Promise<Verdict> {
const local = localBucket(key, scope); // (3)
if (!local.tryConsume(cost)) {
return { allowed: false, remaining: 0, retryAfterMs: local.waitMs(cost), source: 'local' };
}
try {
const [ok, remaining, waitMs] = await redis.evalsha( // (4)
SCRIPT_SHA, 1, `bucket:${key}:${scope}`,
Date.now(), policy.refillPerSec, policy.capacity, cost
);
return { allowed: ok === 1, remaining, retryAfterMs: waitMs, source: 'shared' };
} catch (err) { // (5)
metrics.increment('limiter.shared_unavailable');
return { allowed: true, remaining: -1, retryAfterMs: 0, source: 'degraded' };
}
}(1) the return type carries everything the HTTP layer needs, so the caller never has to ask a second question. (2) source is not decoration. When you are debugging why a customer was rejected, knowing whether the local tier or the shared authority said no is the first thing you want, and it goes into the log line. (3) the local tier runs first, with no network involved. A flood is rejected here and never becomes load on the shared store. (4) evalsha sends the script's hash rather than its body, so the script is uploaded once and each call is a few dozen bytes. (5) the failure policy in three lines: count it, allow the request, and mark the verdict degraded so downstream logging and alarms can tell the difference between "we checked and allowed" and "we could not check". Section 8 argues why allowing is right here, and why it is only safe because line (3) already ran.
5. Architecture
The reason for two tiers becomes obvious when you draw what happens to load under an attack.
And the degradation path, which is the decision the whole design turns on.
6. Deep dives
6.1 Which algorithm, and what each one gets wrong
Five algorithms, each with a specific failure. Naming the failure is what shows you have used them rather than read a list.
Fixed window. Count requests in the current clock minute, reset at the boundary. Simple, one counter, tiny. Its failure is the boundary burst: a client sends 100 requests at 11:59:59.9 and 100 more at 12:00:00.1, so 200 requests land in 200 milliseconds and both windows are technically within the limit. For a limiter protecting a backend, that is the exact event you built the thing to prevent.
Sliding window log. Store a timestamp for every request and count how many fall inside the last 60 seconds. Perfectly accurate. Its failure is memory and cost: a customer doing 5,000 requests a second needs 300,000 timestamps kept per key, which turns 100 MB of state into something else entirely.
Sliding window counter. Keep the current and previous fixed windows and interpolate — if you are 25% into the current minute, count the current window plus 75% of the previous one. Cheap, and much better than fixed window at the boundary. Its failure is that it assumes traffic was evenly spread across the previous window, so a client that bursts at the end of a window is under-counted, and can therefore exceed the limit slightly. Knowing which direction the error goes is the tell.
Leaky bucket. Requests join a queue that drains at a constant rate. It smooths output perfectly, which is exactly right when you are protecting something that cannot handle bursts at all. Its failure is that it adds latency by design — a request may wait rather than be rejected — which is wrong for a synchronous API where the caller is holding a connection open.
Token bucket. A bucket holds up to capacity tokens and refills at refillPerSec. A request spends cost tokens if they are there. Its two knobs are independent and both map onto something a product manager actually wants: refillPerSec is the sustained rate, capacity is how big a burst you tolerate. It computes Retry-After exactly, from the deficit and the refill rate. And it handles weighted costs naturally.
Choose token bucket. It is the only one of the five that answers all three product questions — sustained rate, burst allowance, and when to retry — with two numbers and no extra state.
6.2 Why two tiers rather than one
A single shared store is correct and it is also a round trip on every request in the company plus a hard dependency for every service. A single local counter per instance has no round trip and is wrong, because eight instances each enforcing the full limit means the customer gets eight times their limit.
The two-tier design takes the useful half of each. The local tier is an in-process token bucket configured loosely — say twice the customer's true limit, or the true limit divided by the expected instance count, depending on which failure you fear more. Under normal traffic it never fires, because normal traffic is well below the loose threshold. Under a flood it fires constantly, and every rejection costs nothing but a few CPU cycles.
The shared tier is the authority. It is what makes eight replicas agree, and it is the number the customer's dashboard shows.
The cost, stated plainly: there are now two places where a request can be rejected, and they can disagree. A request rejected locally was never counted by the shared store, so the customer's "remaining" figure will be slightly wrong during a flood. That is acceptable, and it is why the verdict carries a source field — so an engineer debugging a complaint can see which tier said no.
6.3 The hot key
One customer at 40% of traffic means one key taking 40,000 operations a second. This is not a capacity problem you can solve by adding nodes, because sharding distributes keys and this is one key (10.6). The shard holding it runs hot, its latency rises, and because the limiter is in front of everything, the whole platform's tail latency follows.
Three cures, in increasing order of how much they actually help.
Key splitting. Replace one key with key:0 through key:9, each holding one tenth of the limit, and have the caller pick one at random. The load spreads across ten slots and the aggregate enforcement stays roughly correct. The cost is lumpiness: with random assignment, one sub-bucket can exhaust while others still have room, so the customer may be rejected slightly early. Larger N spreads load better and increases the lumpiness, so N is a tuning knob rather than a free win.
Token leasing. The shared store grants each instance a block of tokens — say 100 — which the instance spends locally and returns the unused remainder of periodically. Round trips drop by roughly the block size, so 40,000 operations a second becomes 400. This is what high-scale limiters actually do. The cost is bounded over-admission: at the moment a burst starts, up to (instances × block size) tokens can be in flight across the fleet, so with 20 instances and 100-token blocks the customer can momentarily exceed by 2,000. You choose the block size by deciding how much over-admission you can live with, which is a much better conversation than choosing it by feel.
Dedicated capacity. Route the handful of very large customers to their own limiter shard. Operationally this is special-casing, which is a real cost, but it isolates the blast radius so that one customer's traffic cannot degrade everyone else's decisions.
Whichever you choose, add per-key metrics. A hot key is invisible in an average — 40,000 operations a second on one key inside a 100,000 per second total looks like a slightly busy cluster — and it becomes visible the moment you plot operations by key and look at the top ten.
6.4 Policy as data, and the dry run
"Change limits without a deploy" is a requirement that decides where the limits live. They go in a policy table that maps (tier, key-type, endpoint-class) to {algorithm, refillPerSec, capacity, cost}, pushed from a control plane and hot-reloaded by every instance.
Three things make this survivable rather than dangerous.
A documented resolution order. When a customer has an enterprise tier, an endpoint-specific override, and a global safety ceiling, which wins? Write it down: the most specific match sets the rate, and the global ceiling caps it regardless. Undocumented resolution order is how a customer ends up with either no limit or a limit of zero, and both have happened to real platforms.
Dry-run mode. A new policy first runs in a mode where it logs what it would have rejected without rejecting anything. You then look at the counts, discover that your new limit would have rejected 4% of a major customer's legitimate traffic, and fix the number before anyone notices. Rolling out an enforcement change without this is a choice to find out in production.
Alarms on rejection-rate deltas, not absolutes. A steady 0.3% rejection rate is healthy. The alarm should fire when that number moves — a jump to 40% is nearly always a policy mistake rather than an attack, because attacks ramp and configuration errors are instant. This distinction is worth stating explicitly, because it is the difference between an alarm that catches your own mistakes and one that only catches other people's.
6.5 Keying, clocks, and the two details that quietly break it
Key on identity first, address as a fallback. An API key or user identifier is fair — it limits the actual customer regardless of how many machines they use. An IP address punishes everyone behind one office connection or one mobile carrier's gateway, and is trivially rotated by anyone who is actually attacking you. So limit on identity where you have it, and on address only on unauthenticated endpoints, where you must.
The address you limit on must be the real one. Behind a load balancer, the connection's source address is the balancer, so every request in the world appears to come from one address and shares one bucket. The client's real address arrives in a forwarded header, which is trivially spoofable unless the framework is configured to trust only your own proxies (9.9.2). Getting this wrong produces one of two failures, and both are silent: either every user shares one limit, or any attacker sets a header and gets a fresh limit per request.
Which clock, and what happens when it moves. The refill calculation uses elapsed time. If the caller passes its own wall-clock time and two servers disagree by 200 ms, buckets refill slightly wrong — harmless. If a server's clock jumps backwards — a time sync correction, a virtual machine resuming from a snapshot — then elapsed goes negative and the bucket loses tokens, rejecting a customer who did nothing wrong. Two protections: clamp elapsed time to a minimum of zero, and prefer the shared store's own clock as the time source, so all instances refill against one timeline (10.3).
7. Decision Ledger
| Decision | Alternatives | Why this | What it costs |
|---|---|---|---|
| Token bucket | fixed window; sliding log; sliding counter; leaky bucket | independent rate and burst knobs, exact Retry-After, weighted costs | two fields of state instead of one counter |
| Atomic script at the shared store | read then write from the client | closes the check-then-act race that admits bursts | logic lives in the store; harder to change than application code |
| Two tiers, local first | shared store only | rejection becomes nearly free, so an attack cannot overload the limiter | two places can reject; remaining is slightly wrong during floods |
| Lazy refill | background job topping up buckets | no timers for a million keys; state is created on demand | every read does a little arithmetic |
| TTL on every key | keep state forever | key space stays at ~100 MB permanently | a returning customer starts full, which is correct but must be intended |
| Identity first, address as fallback | address only | fair per customer; address punishes shared connections | needs authentication before limiting on the precise path |
| Policy as hot-reloadable data | limits in code | limits change in minutes, with an audit trail | a control plane to build, secure and get right |
| Fail open at the shared tier | fail closed | the limiter can never take the platform down | you run without exact enforcement until it recovers |
8. Scale and failure
The failure policy is the most important decision in this design, and it must be explicit. When the shared store is unavailable, do you allow everything or reject everything?
Fail closed means a limiter outage becomes a total platform outage. Your protective control is now your largest availability risk, which is an absurd position to be in — you have made the platform less reliable by adding protection to it.
Fail open means that during the outage there is no aggregate enforcement, and if the outage coincides with an attack (which is not a coincidence, since an attack can cause the outage) you are unprotected exactly when it matters.
The defensible answer is layered. Fail open at the shared tier while the local tier keeps enforcing a conservative per-instance limit. Legitimate traffic continues. Flagrant abuse is still bounded, because the local bucket is still counting. Protection degrades from exact to approximate rather than vanishing. Three additions make it complete: tighten the local limits automatically while the shared tier is down, trading a small amount of false rejection for containment; alarm loudly, because running without aggregate enforcement is an incident even though no user can see it; and put a circuit breaker on the limiter call itself, so that a slow store fails fast instead of adding its latency to every request in the company (10.9).
At 10× (1 million decisions a second). Shard the shared store by key hash. Push most decisions into the local tier with token leasing, which cuts round trips by roughly the block size. Then consider the biggest lever: move enforcement to the edge, so that rejected traffic never enters your infrastructure at all. The cheapest request is the one you never receive (10.2).
| What breaks | Blast radius | How you find out | What keeps it running | Recovery |
|---|---|---|---|---|
| Shared store unreachable | no aggregate enforcement | limiter.shared_unavailable counter; breaker state | local tier keeps enforcing, tightened | breaker half-opens; buckets refill from empty state |
| Shared store slow | every request in the platform gets slower | limiter p99 latency, separate from endpoint p99 | circuit breaker fails the call fast | breaker recovers on probe success |
| One hot key | that shard's latency, then everyone's | per-key operation counts, not the average | key splitting or token leasing | move the key to dedicated capacity |
| Store failover, state lost | brief over-admission | failover event; a dip in rejection rate | buckets restart full, which is the safe direction | none needed; do not treat a cold store as billing truth |
| Bad policy pushed | mass rejection of legitimate traffic | rejection-rate delta alarm | dry-run mode before enforcement | roll the policy back; it is data, so this takes seconds |
| Clock jumps backwards | one instance rejects unfairly | negative-elapsed counter | clamp elapsed to ≥ 0; prefer the store's clock | resolves itself once the clock settles |
| Proxy header misconfigured | everyone shares one bucket, or nobody is limited | rejection rate near 100% or near 0% for anonymous traffic | trust only your own proxies | fix configuration; no state to repair |
The two rows worth dwelling on are the ones where nothing errors: a slow store and a misconfigured proxy header both produce a system that appears to work. The first shows up only if you measure the limiter's own latency separately from the endpoints it fronts, and the second shows up only if you watch the rejection rate for anonymous traffic. Neither is visible in an error rate.
What the interviewer will push on
"Walk me through the race that makes a non-atomic check wrong." They want the mechanism, not the word "atomic". Good answer: three requests for the same key arrive at three instances within a millisecond, all three read tokens = 2, all three subtract 1 and write back 1, and three requests were allowed against two tokens. The tell is naming when this happens — during bursts, which is precisely when the limit is doing its job — and the fix is that the read, the compare and the write must be one operation the store executes without interleaving.
"Why token bucket and not a sliding window?" They are checking whether you can compare algorithms by their failures rather than their names. Name the boundary burst that kills fixed windows, the memory cost that kills the log variant, the direction of the sliding counter's error (it under-counts a late burst, so it lets slightly too much through), and the added latency that makes leaky bucket wrong for a synchronous API. Then say the deciding property: token bucket is the only one that answers all three product questions with two numbers, including the exact Retry-After.
"One customer is 40% of your traffic. What happens?" The trap is to answer "we shard". Sharding distributes keys; this is one key. The strong answer names key splitting with its lumpiness cost, token leasing with its over-admission bound of instances × block size, and dedicated capacity with its operational cost — and finishes on the observability point, that a hot key is invisible in an average and needs per-key metrics.
"Your limiter's store is down. Allow or reject?" This is the question the whole round is really about, and a single word is the wrong answer. Explain that fail-closed makes your protection the biggest availability risk in the platform, that fail-open removes protection at the worst possible moment, and that the layered answer — fail open at the shared tier while the local tier keeps enforcing a tightened limit, with an alarm and a circuit breaker — degrades accuracy rather than removing protection or removing the platform. Then say who you would tell: the security stakeholder gets "protection is never zero and the ceiling is documented", the availability stakeholder gets "the limiter cannot take the platform down".
"Rejection rate just went to 100%. Attack or bug?" Almost always a bug. Attacks ramp; configuration changes are instant and total. The tell is that you alarm on the delta rather than an absolute threshold, and that a new policy goes through dry-run mode first, so you have the counts before you have the incident.
"How do you know the limit is even being applied to the right thing?" They are fishing for the proxy header problem. Behind a load balancer the connection address is the balancer's, so limiting on it puts the whole internet in one bucket; and trusting a forwarded header from anyone lets an attacker mint a fresh limit per request. Both failures are silent. The fix is to trust the forwarded header only from your own proxies, and the check is to watch the rejection rate for anonymous traffic — near 100% or near 0% both mean the configuration is wrong.
Volunteer this, because nobody asks: the limiter's rejection path must be cheaper than its accept path, and most naive designs get this backwards. If a rejected request costs a network round trip, then an attack of 500,000 requests a second becomes 500,000 operations a second against your shared store, and the limiter falls over before the backend it was protecting. The local tier is not a latency optimisation; it is the thing that makes the limiter survive the event it exists for.
Next: 11.4 — the shared store this design depends on, built from the inside. Everything here assumed a fast in-memory store that is always there; the next study is what it takes to make that assumption true.
Recall
- Two tiers: an in-process pre-filter with no network work (absorbs floods, so rejection is cheaper than acceptance) plus a shared authority that makes replicas agree. Budget: under 5 ms p99 on every request in the platform.
- The decision must be one atomic operation. Read-modify-write across instances lets several requests spend the same tokens — a check-then-act race that is worst during bursts. Mechanism: a server-side script, or a conditional
UPDATEwhose affected-row count is the verdict. - Token bucket, because it is the only algorithm answering all three product questions:
refillPerSec= sustained rate,capacity= burst allowance, deficit ÷ rate = exactRetry-After. Plus lazy refill (no timers for a million keys), acostparameter (weighted endpoints), and a TTL so idle keys evaporate. - The other four, by their failures: fixed window — boundary burst (2× the limit in a moment); sliding log — memory; sliding counter — under-counts a late burst; leaky bucket — adds latency by design.
- Hot key (one customer at 40% of traffic) is one key, so sharding cannot help: key splitting (limit ÷ N, slightly lumpy) or token leasing (round trips ÷ block size, over-admission bounded by instances × block) or dedicated capacity. Watch per-key metrics; averages hide it.
- Policy as hot-reloadable data, with a documented resolution order, dry-run mode before enforcing, and alarms on rejection-rate deltas — a jump to 100% is a config bug, not an attack.
- Keying: identity first, address as fallback, and the forwarded header trusted only from your own proxies. Clamp elapsed time to ≥ 0 and prefer the store's clock.
- Failure policy, layered: fail open at the shared tier while the local tier keeps enforcing a tightened limit, alarm loudly, and put a circuit breaker on the limiter call so a slow store does not become the latency it was preventing.
Self-test: Give the race that a non-atomic check allows, and when it happens. Name each algorithm's specific failure. Two cures for a hot key, with the cost of each. Why must rejection be cheaper than acceptance? State the failure policy and justify it to both stakeholders.
Quiz Bank
FoundationalWhy must the rate-limit check be atomic, and how is that achieved?
Because the decision is a read-modify-write. Read the bucket, add the tokens that accrued since it was last touched, compare the total against the request's cost, subtract, write back. Split that into a read and a separate write and the sequence has a gap in the middle where another request can do the same thing.
Concretely: three requests for the same API key arrive at three different service instances within the same millisecond. All three read tokens = 2. All three decide there is room for a request costing 1. All three write back tokens = 1. Three requests were admitted against two tokens. This is the check-then-act race from 9.5.1, and the detail that makes it serious is when it happens: concurrent requests for one key are most likely during a burst, which is exactly the moment the limit exists to control. So the error is not evenly distributed noise, it is a systematic hole that opens under load.
Achieved by making the whole sequence one operation the store executes without interleaving. In Redis that is a Lua script, because scripts run single-threaded with respect to every other command. In a relational database it is a conditional update — UPDATE buckets SET tokens = tokens - :cost WHERE key = :k AND tokens >= :cost — where the number of rows affected is the verdict: one row means allowed, zero rows means rejected, and no separate read ever happened (10.4).
Two things worth putting in the same operation while you are there. Compute the lazy refill inside it, so a million buckets need no background job — each one tops itself up the next time anyone looks at it. And compute retryAfterMs from the deficit and the refill rate, so a single round trip returns the decision, the remaining count for the response headers, and honest guidance for the client.
AppliedCompare the five rate-limiting algorithms by what each one gets wrong.
Fixed window. One counter per key per clock minute, reset at the boundary. Cheapest possible. Its failure is the boundary burst: 100 requests at 11:59:59.9 plus 100 at 12:00:00.1 is 200 requests in 200 milliseconds, and both minutes are within a limit of 100. The system sees double the limit at the worst possible instant, and no counter ever recorded a violation.
Sliding window log. Keep a timestamp per request and count those inside the trailing window. Exactly accurate. Its failure is cost: a customer at 5,000 requests a second needs 300,000 timestamps per key for a one-minute window, which turns a 100 MB key space into tens of gigabytes and makes every decision a range operation rather than an arithmetic one.
Sliding window counter. Keep the current and previous window counts and interpolate by how far into the current window you are. Cheap and much better at the boundary. Its failure is the assumption underneath the interpolation: it assumes the previous window's traffic was evenly spread. A client that sent everything in the last two seconds of the previous window is under-counted, so it can slightly exceed the limit. Knowing the direction of that error — it lets too much through, not too little — is the part that shows understanding.
Leaky bucket. Requests enter a queue draining at a fixed rate, so output is perfectly smooth. Right when the thing behind you cannot absorb any burst at all. Its failure is that it adds latency by design: a request waits instead of being rejected, which is wrong for a synchronous API where a client is holding a connection and would rather be told no immediately.
Token bucket. A bucket of up to capacity tokens refilling at refillPerSec; a request spends cost tokens if available. Two independent knobs that map directly onto product language — sustained rate and burst allowance — plus an exact answer to "when will there be room", plus natural support for weighting expensive endpoints.
Choose token bucket, because it is the only one of the five that answers all three questions the product actually asks with two numbers and a subtraction.
InterviewWhat breaks when one customer generates 40% of your traffic, and how do you fix it?
What breaks. That customer's limit state lives in one key, so one shard receives roughly 40,000 operations a second while its neighbours idle. Cluster sharding cannot help, because hashing distributes keys and this is a single key (10.6). The consequences cascade: that shard's latency rises, the limiter's p99 blows through its 5 ms budget, and since the limiter sits in front of every request in the platform, everyone's latency follows — including customers who have nothing to do with the one causing it.
Fix one: key splitting. Replace key with key:0 … key:9, each carrying one tenth of the limit, with the caller choosing a sub-key at random. Load spreads across ten slots and aggregate enforcement stays approximately right. The cost is lumpiness: random assignment means one sub-bucket can empty while others still hold tokens, so the customer is rejected a little early. Bigger N spreads load better and increases lumpiness, so N is a knob you tune rather than a free improvement.
Fix two: token leasing. The shared store grants each instance a block of, say, 100 tokens, which the instance spends locally and returns unused portions of on a timer. Round trips fall by roughly the block size — 40,000 a second becomes 400. This is what genuinely high-scale limiters do. The cost is bounded over-admission: at the start of a burst, up to instances × block size tokens can be held across the fleet, so 20 instances with 100-token blocks means up to 2,000 requests of overshoot. That is a number you can choose deliberately, which is much better than a vague feeling.
Fix three: dedicated capacity. Route the few very large customers to their own limiter shard. Operationally it is special-casing, which is a real ongoing cost, but it isolates the blast radius so one customer's traffic cannot degrade decisions for everyone else.
And the observability point, which is the reason this becomes an incident rather than a ticket: a hot key is invisible in an average. Forty thousand operations a second on one key inside a hundred-thousand-per-second cluster looks like a moderately busy day. Plot operations by key and look at the top ten, and the next hot key announces itself weeks before it hurts.
StaffDesign the failure policy for the limiter and justify it to both the security and the availability stakeholders.
The question. When the shared store is unavailable, does the limiter allow or reject?
Why both extremes are indefensible on their own. Fail closed converts a limiter outage into a total platform outage — your protective control becomes the single largest availability risk you own, and you have made the system less reliable by protecting it. Fail open removes aggregate enforcement precisely when it is most likely to be needed, since one common reason for the store to be unavailable is that an attack is under way.
The layered answer. On shared-store failure, fail open at the shared tier while the local pre-filter keeps enforcing a conservative per-instance limit — the customer's limit divided by the expected instance count, or a fixed safety ceiling, whichever you can defend. Legitimate traffic continues to flow. Flagrant abuse is still bounded, because every instance is still counting locally. What degrades is accuracy, not protection.
Three things complete it. Tighten automatically while the shared tier is down, accepting a little false rejection in exchange for containment. Alarm loudly, because running without aggregate enforcement is an incident even though not a single user can see it — a silent degradation nobody is told about will still be running six months later. And put a circuit breaker on the limiter call itself (10.9), because the worst version of this failure is not a store that is down, it is a store that is slow: without a breaker, every request in the company waits on it, and the limiter becomes the latency it was built to prevent.
To the security stakeholder: protection never reaches zero. The local ceiling is documented, it is exercised, and an alarm guarantees a human knows within a minute rather than discovering it in a post-mortem.
To the availability stakeholder: the limiter cannot take the platform down. Its worst case is degraded accuracy for the duration of the incident, and the tightened local limits mean the backend behind it is still shielded from the traffic that would actually hurt it.
The principle to write into the design document: a protective control must fail into a state that is safer than removing it and less harmful than enforcing it blindly. That is three mechanisms — two tiers, an explicit written policy, and an alarm — not a boolean called failOpen.
Flashcards
FlashTwo-tier limiter, and why
Local in-process pre-filter (no network, absorbs floods) + shared authority (atomic script, ~0.5 ms). The point is that rejection must be cheaper than acceptance, or an attack overloads the limiter itself.
FlashThe race a non-atomic check allows
Three instances read tokens = 2, each subtracts 1, each writes 1 — three requests admitted against two tokens. Worst during bursts. Fix: one server-side script, or UPDATE … WHERE tokens >= cost with rows-affected as the verdict.
FlashAlgorithms by their failure
Fixed window — boundary burst (2× at the seam). Sliding log — memory. Sliding counter — under-counts a late burst, so lets too much through. Leaky bucket — adds latency by design. Token bucket — the one that answers rate, burst and Retry-After.
FlashHot key cures with their costs
Key splitting: limit ÷ N sub-keys, cost is lumpy early rejection. Token leasing: round trips ÷ block size, cost is over-admission bounded by instances × block. Dedicated shard: isolation, cost is special-casing.
FlashFailure policy
Fail open at the shared tier, local tier keeps enforcing a tightened limit, alarm loudly, circuit breaker on the limiter call so a slow store fails fast. Never a single boolean.
FlashSignals that catch the silent failures
Rejection-rate deltas (100% = config bug). Per-key operation counts (averages hide hot keys). Limiter p99 measured separately from endpoint p99. Anonymous-traffic rejection rate (catches proxy-header misconfiguration).
Scenario Drill
DrillProduct wants free/pro/enterprise tiers, per-endpoint costs, burst allowances, a customer-facing usage dashboard, and soft limits that warn before enforcing. Extend the design and identify the one requirement that changes the architecture.
Tiers and per-endpoint costs are already policy data. The policy table gains rows keyed by (tier, endpoint-class) mapping to {refillPerSec, capacity, cost}, and the cost parameter already threaded through the atomic script carries the weight. A search costing 10 tokens and a health check costing 0 needs no code change at all — which is the payoff for having made policy data in the first place.
Burst allowances are the capacity knob, which is precisely why token bucket was chosen over a windowed counter. Nothing to build.
Soft limits are cheap and genuinely useful. The decision already returns remaining, so the caller can emit a warning header, and the platform can notify a customer at 80% consumption. Implement the threshold check inside the same atomic script — it is one comparison against a number you already computed — and emit the notification asynchronously, so a notification service being slow can never add latency to a rate-limit decision (10.8.1).
The requirement that changes the architecture is the usage dashboard. The limiter's state is deliberately ephemeral: a token count and a timestamp with an hour's TTL, holding no history whatsoever. "Show me my usage over the last 30 days, broken down by endpoint" cannot be answered from it, and it should not be. Bolting historical accounting onto the hot path would violate the 5 ms budget, and worse, it would make the failure policy incoherent — you cannot fail open on something that produces an invoice.
The correct extension is a separate metering pipeline. Every decision emits {key, endpoint, cost, allowed, timestamp} to a stream. Consumers roll it into per-customer time-series aggregates that back the dashboard (11.19 builds this machinery in full). Two properties make this right rather than merely convenient. The metering path is asynchronous and loss-tolerant for display purposes — a dropped event costs a pixel on a chart, not an enforcement decision. And it is completely separable in its guarantees, which matters for the next request the product will make.
The next request, which you should anticipate out loud: "can we bill from the dashboard numbers?" The moment usage becomes an invoice line, the requirement changes from approximate to auditable, and the pipeline must move to a durable log with exactly-once aggregation and a retained raw record you can recompute from when a customer disputes a figure (10.4). That is a materially different system and a materially different cost, and it should be decided deliberately rather than discovered when finance asks why the invoice and the dashboard disagree by 3%.
The lesson the drill teaches: enforcement and accounting look like the same data and are not. One is a hot, tiny, ephemeral counter updated atomically millions of times a second and allowed to be slightly wrong. The other is a durable, historical, exactly-aggregated record that someone may dispute in writing. Keeping them in separate systems protects the request path from the accounting requirements and lets each one have the guarantees it actually needs — and it is the reason the limiter can fail open at all.