Design a rate limiter

Do the numbers before the boxes

An interviewer gives an API and its customers, not a load. A rate limiter has one load that sizes it: calls a second, refused ones included.

A 45-minute version of this answer is at the end.

The API is public. Our customers' servers and apps call it, and each customer app has one API key.

Each key has a limit from its plan, per minute. A call over its limit is refused before it reaches the API.

We assume one AWS Region, us-east-1. Every count on this page is our estimate unless sourced.

A normal peak is 20,000 calls a second, from about 100,000 active keys.

Then a bad release of our client SDK, the library customers call us with, retries every failed call at once. That is a retry storm.

About 5,000 keys run that release. Each normally sends 1 call a second: 5,000 in all.

In the storm each sends 9 a second: 45,000. The other keys still send 20,000 - 5,000 = 15,000.

In all, 45,000 + 15,000 = 60,000 calls a second, three times the normal peak.

Each storm key's limit is 90 calls a minute, which is 1.5 a second. It normally sends 60 a minute.

Check in: Close the page and derive the storm's 60,000 calls a second.

No limiter, and a retry storm

Stage 1 is the API with no limiter, at the moment the storm lands: 60,000 calls a second.

Calls arrive through an ALB, AWS's application load balancer, in 3 availability zones: separate data centres in one Region.

The API runs on Fargate, AWS's managed containers. Each task is one container; here a task has 2 vCPUs, virtual processors, and 4 GB.

A call costs about 4 ms of CPU (our estimate). So a vCPU serves 1,000 / 4 = 250 calls a second, and a task 500.

58 tasks serve 58 x 500 = 29,000 calls a second. That holds the normal peak at 20,000 / 29,000 = 69.0%.

Auto-scaling is off on purpose: the storm lands in seconds, and new tasks take minutes. The API's databases are not on the canvas.

At 60,000 the result names API servers: they saturate, with 60,000 calls a second against the 29,000 they serve.

Nothing sheds the excess. Calls queue and time out, and the bad SDK retries each one at once, so the storm grows.

Why 9 a second? A no-wait loop still waits for each answer. Over a 100 ms internet round trip, one loop sends at most 10 a second.

The latency tile shows "≥ 18ms". Up to 70% busy, the API card counts each call at 4 ms; past that the time rises, to 4 times at full use.

So the tile adds 1.5 ms at the load balancer and 4 x 4 = 16 ms: 17.5 ms. That is a floor: once a part saturates, the real wait is longer.

The cost tile shows $24k/mo: the load balancer $8,310.60, the API $4,123.38, and data out to the internet, called egress, $11,194.28.

Press 20,000, the normal peak: nothing saturates, and the note reads "Busiest: API servers at 69%". The tiles show 6ms, 1.5 + 4 = 5.5 ms, and $11k/mo.

On the canvas, egress counts 1 KiB for each answer. The load balancer card bills 0.6 new connections a call; the bill beat gives the real line.

Its percentage compares the load with the card's own 100,000 calls a second in each zone. AWS publishes no such limit. Nothing here is typed, so any load is honest.

The trade-off:

The API was sized for its callers' habits, with 31% to spare. One bad client release triples the load in seconds.

Stage 1: No limiter, and a retry storm

• Load: 60,000 req/sec
• First to saturate: API servers
• Estimated cost: $24k/mo

• Latency past saturation is a lower bound, not an estimate. API servers is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• API servers: Fargate 2vCPU-4GB ×58 at 100% of a fixed 58-task ceiling.

Check in: The API scales on CPU. Why not let it scale through the storm?

Reading the result tiles

Stage 1 showed a canvas and four result tiles. Four rules hold on every stage.

Load: the buttons count API calls a second, and the tile labels them req/sec.

A card turns red at 90% of its limit, and some cards also warn over 80%. A part that saturates, past 100%, is named in the result.

Otherwise the last tile notes the busiest part.

Latency is server time on the slowest path; a caller also waits its own round trip. Past saturation it is a floor, which is why it prints "≥".

Cost: each card bills its stage load all month, but a storm lasts minutes or hours. Price a storm by what it adds for an hour, not by the month / 720.

Each stage ends with a paragraph that starts "On the canvas". It says where a card counts differently from AWS, and what the editor shows at another load.

Check in: Stage 1's cost tile reads $24k/mo in the storm. What does an hour of the storm cost?

Where the limiter sits

Something must count each key's calls and refuse the excess before the API. A candidate can place it in four ways.

A library inside the API costs no extra hop. But a refused call still holds an API socket and thread, and every service needs the library.

A sidecar, a proxy in each API task, decides locally. It still needs a shared count for a limit across tasks.

API Gateway usage plans give a managed limit per API key. AWS calls them "best-effort", "targets rather than guaranteed request ceilings".

This page draws a separate tier: a thin proxy fleet between the load balancer and the API. Refused calls never reach the API.

Each limiter task reads the call's API key and finds its plan's limit. Then it checks the key's counters in a shared store, and refuses or forwards.

The store is Valkey, an in-memory key-value store that AWS runs as ElastiCache.

Rules live in a config table, pushed to every task every 30 s (our choice). No call reads them from a store.

The tier has 10 tasks of 2 vCPUs, at about 0.2 ms of CPU a check (our estimate).

So each task serves 2 x 1,000 / 0.2 = 10,000 checks a second, and 10 tasks serve 100,000: five times the normal peak.

A storm lands at once, and the tier cannot wait minutes for new tasks.

The tier adds one hop to the API. ECS Service Connect, a proxy that AWS's container service puts in each task, or an internal ALB carries it.

The canvas draws neither.

The trade-off:

One more hop and one more fleet. In exchange, one place holds the rules, and a refused call costs the API nothing.

Check in: Why not put the limit in a library inside the API?

Six ways to count

An interviewer expects the classic algorithms, and a reason for your pick. Compare round trips, what the store runs, the burst each allows, and what you can size.

At launch there are 100,000 keys and 20,000 calls a second. Every design here checks a key in one round trip to the store.

Token bucket: each key holds tokens and a refill time. A script, a small program run inside Valkey, refills, takes one and writes back. It is exact, and it allows a burst of the bucket size at once. Stripe and API Gateway use it.

Leaky bucket, as a meter: a level drains at a fixed rate, each call adds 1, and a full bucket refuses. It is also one script.

As a queue, it holds calls and releases them at a fixed rate. Calls wait, so it does not suit an API that answers at once.

GCRA, the generic cell rate algorithm, keeps one timestamp a key: when the next call is due. One script, exact, with no window edge.

A fixed window counts each key's calls in each minute with 2 plain commands, each reading or writing one value. It allows the whole limit at once.

Across the edge between two windows, a key can send up to 2 times its limit. Stage 2 shows a worse effect.

A sliding window log keeps a sorted set, ordered by time, with one entry for each allowed call in the window. It is exact.

On this page a refused call does not use the limit, so the log holds at most keys x limit. Each entry is 30 to 75 B. At launch, 20,000 x 60 = 1.2M entries take 36 MB to 90 MB. In the storm, 22,500 x 60 = 1.35M take 40.5 MB to 101 MB.

The usual version also keeps refused calls, so it grows with every arriving call. In the storm: 60,000 x 60 = 3.6M entries, 108 MB to 270 MB.

A sliding window counter keeps two counters a key, this minute and the last, and sends 3 plain commands a check. Stage 3 shows how it estimates.

After a quiet minute it allows the whole limit at once. If the last minute's calls bunched at its end, a true 60 s window can see nearly 2 times the limit.

Cloudflare measured 0.003% of 400M real calls wrongly allowed or limited. Real calls are close to even; the 2 times needs a client that bunches on purpose.

Memory does not decide among the counters. Every design but the log needs 10 MB to 40 MB at launch, under 0.5% of one store node.

Step through the figure to compare them.

The trade-off:

Each design trades exactness, burst and cost. The log is exact but costs the most; the scripts are exact but their cost is unpublished.

Six ways to count, at launch

1. Token bucket: one round trip, one script on the node. Exact, with a burst of the bucket size. No published figure sizes the script.
2. Leaky bucket as a meter: one round trip, one script. A level drains at a fixed rate; a full bucket refuses. No published figure.
3. GCRA: one round trip, one script, one timestamp a key. A set burst on a smooth rate, with no window edge. No published figure.
4. Fixed window: one round trip of 2 plain commands, the kind AWS measured. It allows the whole limit at once, and up to 2 times across an edge.
5. Sliding log: one round trip of 4 or more sorted-set commands, which nobody has measured. Exact: never over the limit in any 60 s.
6. Sliding counter, on the canvas: one round trip of 3 plain commands, sized on AWS's measured figure. Up to about 2 times the limit if calls bunch.
7. Memory at launch: all under 0.5% of a node except the log. The other designs need 10 MB to 40 MB; the log needs 36 MB to 90 MB.
8. The pick: plain commands are what AWS measured, so the counter can be sized. A script is exact, but load-test it before you size on it.

Check in: In the storm, why does the usual sliding log need more memory than this page's?

Why the sliding counter, and when a script wins

A token bucket or GCRA in one script is exact, needs no refund, and holds one value a key, not two. So why draw the counter?

It can be sized on a published figure. Each of its plain commands is of the class AWS measured. Nobody publishes what a script costs.

A script runs several key operations plus its interpreter on the store. Sized on a script, the store is sized on a guess until you load-test it.

A plain script is lost when a node restarts or is replaced, and must be sent again.

A Valkey function, a script stored on the node, survives a restart. Both must still be loaded on every node that takes writes, including new ones.

The limit here is per minute, which a window states directly. And the counter's error is published: 0.003%.

A script is the better answer when the contract is a rate with a burst, such as 100 a second with bursts of 20.

It is also better when every refusal must be exact, or when you can measure the script on your own node.

Say it like this: "A sliding window counter on plain commands, for a per-minute limit. I can size it on a measured figure, and its error is known."

And: "If the API promises a rate and a burst, GCRA in a Valkey function, and I load-test its cost before I size the store."

The trade-off:

The counter gives up exactness and one value a key. In exchange, the store is sized on a measured figure, and its error is known.

Check in: An interviewer asks why you did not use a token bucket in one script. What do you say?

Fixed windows, at the start of a minute

The interviewer asks: Limit each key to 90 calls a minute. Start simple.

Stage 2 adds the limiter tier and the simplest counter, one per key per minute, in the same storm.

The counters run in Valkey in store mode: nothing is ever evicted.

The fixed window names each counter by the minute: rl:{key}:m, where m is the minute number.

A check is INCR, which adds 1 and returns the count, then EXPIRE 60 NX, which sets a lifetime only if none is set.

Both go in one round trip. A count over 90 refuses the call, and DECR gives that count back, so a refusal does not use up the limit.

The store is a primary node and a replica, a copy in another zone that takes over if the primary fails.

The trouble is the minute. Every key's window starts at the same second, and a storm key spends its 90 in 90 / 9 = 10 s.

So for the first 10 s of every minute nothing is refused, and all 60,000 calls a second reach the API.

Averaged over the minute, the API gets (10 x 60,000 + 50 x 15,000) / 60 = 22,500 a second. For 10 s of each minute it gets 60,000.

The result names API servers again, and calls queue and time out as in Stage 1. The latency tile shows "≥ 18ms": 1.5 + 0.2 + 16 = 17.7 ms.

Counters: 60,000 x 2 = 120,000 commands a second, with no DECR. The card rates the node, a cache.m6g.xlarge, at 348,000 commands a second: 34.5%.

AWS measured 348,550 a second on a cache.r6g.xlarge, which has the same 4 Graviton2 vCPUs. Graviton is AWS's ARM processor.

AWS measured single GET and SET calls, 80% reads, on Redis 7.0.5 with 2,000 clients. Valkey is a fork of a later Redis, 7.2.4.

This page counts each of our commands as one such call. Commands sent together cost the node less; our writes, each INCR copied to the replica, may cost more.

No vendor publishes either effect, so this page sizes on the measured figure. The cost tile shows $25k/mo: Stage 1 plus the limiter and the counters.

On the canvas, the share that passes to the API is typed on the limiter's edge: 1.0, from this working. At any other load the editor still passes every call.

That is true only while every key's minute is fresh, so Stage 2 has no load buttons.

The trade-off:

A fixed window keeps the average and loses the shape. An offset per key spreads the resets; a sliding window removes them.

Stage 2: Fixed windows, at the start of a minute

• Load: 60,000 req/sec
• First to saturate: API servers
• Estimated cost: $25k/mo

• Latency past saturation is a lower bound, not an estimate. API servers is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• API servers: Fargate 2vCPU-4GB ×58 at 100% of a fixed 58-task ceiling.

Check in: An offset per key spreads the resets over the minute. What can one key still do at its own window edge?

A sliding window counter

Stage 3 keeps the storm and replaces the fixed window with the sliding window counter, Cloudflare's method.

Each key has two counters, this minute and the last. The estimate is the last minute's count x the share of it still in the window, plus this minute's.

Cloudflare's example: 15 s into a minute, 42 calls last minute and 18 this one. The estimate is 42 x (60 - 15) / 60 + 18 = 49.5.

A check is INCR this minute, EXPIRE 120 NX, and GET the last minute, in one round trip: 3 commands. A refusal adds a DECR.

Both counters carry the key in braces, rl:{key}:m, so they sit together on one node; Stage 4 explains why.

There is no reset moment. Room comes back as the last minute fades, so each storm key can send about 1.5 calls a second.

So the storm keys pass at their limit: 5,000 x 1.5 = 7,500 calls a second. With the other keys, 7,500 + 15,000 = 22,500 pass.

That is 22,500 / 60,000 = 0.375 of the calls. The other 37,500 get 429 Too Many Requests.

The store carries every call, the refused ones too: 60,000 x 3 + 37,500 x 1 = 217,500 commands a second. That is 3.625 a call.

On the card, 217,500 / 348,000 = 62.5%. The API gets 22,500 of its 29,000: 77.6%. Nothing saturates; the note reads "Busiest: API servers at 78%".

The latency tile shows 9ms. At 77.6% busy the API card counts its 4 ms as 7.03 ms: 1.5 + 0.2 + 7.03 = 8.73 ms.

The cost tile shows $25k/mo, the same $24,681.33 as Stage 2: the algorithm costs nothing on the bill.

Limits are not capacity: the storm keys still send 7,500 a second against their usual 5,000.

On the canvas, the check and the API are parallel arms, and the tile takes the slower. A real call is checked, then forwarded, so it also waits on the store.

That round trip is about 0.3 ms in a zone and 0.5 to 1 ms across zones. In a zone, 1.5 + 0.2 + 0.3 + 7.03 = 9.03 ms.

The 0.375 share and the 3.625 commands a call are typed for this storm. The editor keeps them at any load, so Stage 3 has no load buttons.

Step through the figure to compare a fixed window with the sliding counter over one minute.

The trade-off:

The store sees every call: 217,500 commands for 22,500 served calls. In exchange, the API sees a flat 22,500 and never the storm.

A fixed window against a sliding counter

1. Fixed windows: every key's minute starts at the same second. For the first 10 s, all 60,000 calls a second pass; then 15,000.
2. A storm key spends its 90 calls in 90 / 9 = 10 s. Then every call it sends is refused until the next minute.
3. Sliding counter: room comes back as the last minute fades, so each storm key sends about 1.5 calls a second. 22,500 pass every second.
4. The fixed window averages (10 x 60,000 + 50 x 15,000) / 60 = 22,500 a second, the same as the sliding counter. Only the sliding counter stays under the API's 29,000 every second.

Stage 3: A sliding window counter

• Load: 60,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $25k/mo

Check in: Each storm key gets 90 calls a minute in Stages 2 and 3. Why does the API see 60,000 a second in one and 22,500 in the other?

One check, from key to answer

A check must stay correct when many tasks check one key at once. Walk one call through its states.

Arrives. The load balancer sends the call to any limiter task.

Identified. The task reads the API key and finds its plan's limit in memory, with no store read.

Checked. One round trip sends INCR, EXPIRE 120 NX and GET, and the task computes the estimate.

Allowed. The estimate is at or under the limit, so the call goes to the API. The answer carries headers with the quota and the room that remains.

Refused. The estimate is over the limit, so the task sends DECR in a second round trip and answers 429.

Its Retry-After header gives the wait in whole seconds, rounded up, so at least 1. The task keeps the exact time.

Why INCR first? Two tasks check one key with 89 of 90 counted. Valkey runs commands one at a time, so they get 90 and 91.

The task that sees 91 refuses and gives its count back. A GET, then a SET of count + 1, would let both read 89 and both pass.

A script also works: the check and the increment run as one step, with no DECR. GitHub runs one; this page draws the commands.

EXPIRE NX goes on every check, so no counter outlives two minutes, even if a task dies between two calls. In store mode a counter with no lifetime stays forever.

429 Too Many Requests is RFC 6585, and Retry-After is RFC 9110. The RateLimit-Policy and RateLimit headers are an IETF draft, not an RFC yet.

Many APIs send X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset instead, as GitHub does.

Rules that guard against abuse, such as password tries, send no quota numbers, so an attacker learns nothing from them.

Step through the figure to follow one call.

The trade-off:

A refusal costs a second round trip, for the DECR. In exchange, two tasks never share a count, and a refusal does not use up the limit.

One check, from key to answer

1. Arrives: the load balancer sends the call to any limiter task.
2. Identified: the task finds the key and its plan's limit in memory. No store read.
3. Checked: INCR, EXPIRE 120 NX and GET go to Valkey in one round trip. The task computes the estimate.
4. Allowed: the estimate is at or under the limit. The call goes to the API, and the answer carries the quota headers.
5. Refused: DECR gives the count back in a second round trip. The caller gets 429, with Retry-After.
6. Two tasks at once, with 89 of 90 counted: INCR runs one at a time, so they get 90 and 91. Only 90 passes.

Check in: Two limiter tasks check one key at the same moment, and the key has room for one more call. What stops both getting it?

A year on, on one shard

The interviewer asks: A year on, traffic is four times bigger.

Stage 4 has 4 times the keys with the same habits: 80,000 calls a second at the peak, from about 400,000 keys.

The limiter grows to 40 tasks: 40 x 10,000 = 400,000 checks a second, five times the new peak.

The API is off the canvas from here. Stage 3 showed it protected, and its load is the calls that pass.

Almost nothing is refused at a normal hour, so the page counts none: 3 commands a check.

The store gets 80,000 x 3 = 240,000 commands a second: 240,000 / 348,000 = 69.0%. Nothing saturates; the note reads "Busiest: Counters (Valkey) at 69%".

Count the store as calls x commands a check, refused or not. One node carries 348,000 / 3 = 116,000 calls a second.

Cluster mode is on, with one shard: a primary and its replica. Valkey hashes each key name to a hash slot, and each shard owns a set of slots.

The braces in rl:{key}:m make Valkey hash only the key. So both counters share a hash slot, and one round trip reaches one shard.

The replica is not spare capacity. It is the failover target: if the primary is lost, the replica takes over in seconds.

Building a new node takes many minutes. Counters are never read from the replica: it can lag the primary, and the check would split into two round trips.

Memory: 400,000 x 2 x 200 B = 160 MB, under 2% of the 9.70 GiB usable once AWS reserves its default 25%.

The latency tile shows 2ms: 1.5 + 0.2 + 0.2 ms for Valkey = 1.9 ms.

The cost tile shows $28k/mo: the load balancer $11,075.40, the limiter $2,843.71, the counters $342.14 and egress $13,773.90. The store is 1.2% of it.

Press 20,000, a quiet hour a year on: the store is at 17.2%, and the cost tile shows $10k/mo.

Press 210,000: two years on, with the same habits. The result names Counters (Valkey), and the warnings show its load. Fixing it is your turn, after the quiz.

On the canvas, 3 commands a check holds at any load with these habits, so every load you try here is honest.

The trade-off:

The store's load is calls x commands a check, refused or not. In exchange for one shared count, every call costs the store 3 commands.

Stage 4: A year on, on one shard

• Load: 80,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $28k/mo

Check in: At 80,000 a second one node is at 69.0%. At what peak does it first warn, and when does it saturate?

A leaked key floods one shard

The interviewer asks: One of your customers leaked their API key. A scraper is using it.

Stage 5 is Stage 4's hour, 80,000 calls a second, plus 100,000 a second on one leaked key. Its plan allows 3,000 a minute, 50 a second.

The first move is outside the limiter: revoke the key and issue the customer a new one. The limiter must hold until then.

Every flood call is checked and refused: INCR, EXPIRE NX, GET, then DECR, 4 commands. The key's 50 allowed calls cost 3 each: 99,950 x 4 + 50 x 3 = 399,950.

That is about 400,000 commands a second on one key. With the other keys' 240,000, about 640,000 reach the node: 640,000 / 348,000 = 184%.

The result names Counters (Valkey). Its warning says a key lives on one shard, so the shard count does not raise this ceiling.

A key hashes to one hash slot, on one shard. Shards cannot split it.

With one shard, a flood past (348,000 - 240,000) / 4 = 27,000 calls a second saturates the store. With any shard count, past 348,000 / 4 = 87,000.

More shards shrink the blast radius, the keys that suffer: with S shards, only the 1/S of keys sharing the flooded shard stall. On the card, 4, 10 and 100 shards leave it at 132%, 122% and 116%.

One bigger node does clear this flood on the card: cache.m7g.4xlarge reads 640,000 / 1,000,000 = 64%.

Valkey runs every command on one main thread, whatever the key. So a bigger node helps one key as much as many keys.

AWS reports over 1 million requests a second for nodes this size: GET and SET from 500 clients over 3 million keys. Our mix from 40 tasks is unmeasured, so 64% is the card's reading, not a promise.

A node costs $1.0056 an hour against $0.2376. Two for 720 hours: $1,105.92 a month more, every month, for an attack that lasts hours.

And the flooder picks the next flood's size. Past 1,000,000 / 4 = 250,000 calls a second on one key, no node on the card holds it.

ElastiCache Serverless does not lift it. AWS caps one hash slot at 30,000 ECPUs a second, its unit of work, and a simple command uses 1.

The lesson: the store's load must not grow with the attacker's rate.

The latency tile shows "≥ 3ms", a floor. A check on that shard waits out the limiter's 10 ms deadline, then the task decides locally; the failure beat explains.

On the canvas, Valkey counts its 0.2 ms like the API card: 1.5 + 0.2 + 0.2 x 4 = 2.5 ms. The cost tile shows $54k/mo.

The 3.5556 commands a call and the key's 62.5% share of them are typed for this flood. At another load the editor grows the flood and every key together.

So Stages 5 and 6 have no load buttons.

The trade-off:

A refusal costs the store 4 commands, so the attacker sets the store's load. Shards shrink the blast radius but cannot split a key.

Stage 5: A leaked key floods one shard

• Load: 180,000 req/sec
• First to saturate: Counters (Valkey)
• Estimated cost: $54k/mo

• Latency past saturation is a lower bound, not an estimate. Counters (Valkey) is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• Counters (Valkey): Hottest shard's primary draws 640,008 ops/s, against cache.m6g.xlarge's 348,000 ops/s. 400,005 of them are one key's, and a key lives on one shard, so the shard count does not raise this ceiling.

Check in: Why do more shards not help against the leaked key?

A deny cache

Stage 6 keeps the flood. A refusal must cost less than the call it refuses.

A deny cache lives in every task. After a refusal, the task keeps the key and the time the key's next call slot opens: room for one more call.

A call slot is not a hash slot. From here on, "slot" means a call slot.

Until then, it answers that key from memory with 429 and a Retry-After from that time. No command reaches Valkey. At 50 calls a second, a slot opens every 1,000 / 50 = 20 ms.

At each opening each of the 40 tasks sends one check. One wins, 3 commands; 39 lose and give their count back, 4 each.

So the flood costs at most 50 x (3 + 39 x 4) = 7,950 commands a second, not 400,000.

The store gets 240,000 + 7,950 = 247,950: 247,950 / 348,000 = 71.25%. Nothing saturates and nothing warns; the note reads "Busiest: Counters (Valkey) at 71%".

The flood's cost to the store now follows the key's limit and the task count, not the flood. A flood twice as big costs the same. The limiter tier still carries the calls: 180,000 of its 400,000 checks a second, 45%.

The deny cache refuses only a key that was just refused. It is never early: a key's estimate only falls as its last minute fades.

It can be late. At a slot opening, the 40 tasks' INCRs land together, and a loser's count includes other losers' +1s not yet given back.

Besides itself and the winner, a loser sees up to 40 - 2 = 38 such +1s. So it can compute its slot up to 38 slots late. At 20 ms a slot, that is 38 x 20 ms = 0.76 s of refusals that Valkey would not have made.

Late slots only lower the probes, so 7,950 is a ceiling. A script that never increments on a refusal has no such gap.

The cost tile shows $54k/mo, the same as Stage 5: the deny cache is a map in each task's memory.

The store stays clean while the flood's probes stay under 348,000 - 240,000 = 108,000 commands a second, 13.6 times our estimate.

On the canvas, the latency tile shows 2ms. At 71.25% the Valkey card counts its 0.2 ms as 0.225 ms: 1.5 + 0.2 + 0.225 = 1.925 ms.

The 1.3775 commands a call are typed for this flood. The editor cannot grow the flood alone: at another load it grows every key with it.

Step through the figure to follow one slot opening.

The trade-off:

A map in each task, and refusals that can last up to 0.76 s too long. In exchange, the flood costs the store at most 7,950 commands a second, whatever its size.

One slot opening for the leaked key

1. Between call slots, every task answers the leaked key from memory with 429. No command reaches Valkey.
2. A call slot opens every 1,000 / 50 = 20 ms. Each of the 40 tasks sends one check.
3. One task wins the slot: 3 commands. 39 lose and give their count back: 4 commands each, 159 in all.
4. 50 call slots a second x 159 commands = 7,950 commands a second, at most. A flood twice as big costs the same.
5. A loser's count can include up to 38 other losers' +1s. So it may wait up to 38 x 20 ms = 0.76 s too long.

Stage 6: A deny cache

• Load: 180,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $54k/mo

Check in: Can the deny cache refuse a call that Valkey would let through?

When the store is slow or lost

Every check waits on the counter store. When it is slow or lost, the limiter must fail open or fail closed.

Fail open with a local limit. If Valkey does not answer within 10 ms, the task decides alone: the key's limit / the number of tasks.

Take a key with a limit of 50 calls a second, and 40 tasks. Each task allows it 50 / 40 = 1.25 calls a second.

The load balancer spreads a key's calls over the tasks, so the total stays near 50.

A small limit breaks this: 10 a minute over 40 tasks is under one call for each task. So each task allows 1 call a window, up to 40 a minute in all.

A deadline does not shed load: commands already sent still run on the slow shard.

So each task keeps a circuit breaker per shard. Past 5% of calls timing out in 1 s, it stops calling that shard for 5 s.

Then it sends one probe, and a success closes the breaker. These are our numbers. The breaker, not the deadline, takes load off a stalled shard.

An INCR that ran after its task gave up is never given back. After recovery counts run high, so the error is toward refusing, for at most two minutes.

Fail closed for rules that guard money or abuse: sign-ups, password tries and paid sends. Each rule carries its own mode.

Failover: AWS says the replica is promoted, typically in seconds. It states no detection time, so plan for under a minute.

Replication is asynchronous, so the last milliseconds of counts are lost, and a few calls over a limit may pass.

Stripe's published design also fails open when its limiter or Redis is down.

The trade-off:

A local limit is rough. In exchange, a store outage never takes the API down.

Check in: The counter store's primary is lost. What does a caller see in the next minute?

Keys you never issued

A per-key limit trusts the key. A call with an unknown or forged key never trips a limit, and each one makes a counter.

100,000 random keys a second, each counter kept 120 s, hold 100,000 x 120 = 12M counters. At 200 B each, that is 2.4 GB.

So each task checks the key against a key table pushed with the rules: 400,000 keys in a hash map, tens of MB in memory.

An unknown key gets 401 Unauthorized before any counter is touched.

A new key is pushed to every task when it is issued, not on the 30 s rules cycle. Otherwise a reissued key would get 401 for up to 30 s.

Calls with no valid key are limited by source address, with rate-based rules in AWS WAF, AWS's web application firewall, on the load balancer.

A leaked key is different: it is valid. The first move is to revoke it and issue the customer a new one.

Until then, the limiter and its deny cache hold the flood.

The trade-off:

A key table in every task, and a push at every issue. In exchange, a forged key costs a lookup in memory, not a counter.

Check in: A scraper sends 100,000 calls a second, each with a new random key. Why does no per-key limit stop it?

The limiter chain on one screen

Skip on a first read; come back before the interview. Every number on Stages 1 to 6 comes from the one before it.

Units: memory sizes on this page are decimal, so 1 MB is 1,000,000 B. Answers are in binary KiB, and AWS bills GiB as GB.

A 30-day month has 2,592,000 s and 720 hours.

Fargate 2vCPU-4GB: 2 x $0.04048 + 4 x $0.004445 = $0.09874 an hour, $71.09 a task-month.

API, 58 tasks: $4,123.38. Limiter, 10 tasks: $710.93; 40 tasks: $2,843.71.

Counters: Valkey at $0.2376 an hour a node. Two nodes for 720 hours: $342.14.

Load balancer: an LCU is its billing unit. The card counts one per 25 new connections a second, at 0.6 a call.

At 60,000: 60,000 x 0.6 / 25 = 1,440 LCU, and ($0.0225 + 1,440 x $0.008) x 720 = $8,310.60. At 20,000 it is 480 LCU.

At 80,000: 1,920 LCU, $11,075.40. At 180,000: 4,320 LCU, about $24,899.

Answers: calls x 1 KiB x 2,592,000 s a month. At 60,000 that is 148,315.43 GB; at 80,000, 197,753.91 GB.

Egress: the first 100 GB a month are free. Then AWS's tiers of 10, 40 and 100 TB cost $0.09, $0.085 and $0.07 a GB, and $0.05 after.

A TB here is 1,024 GB, so the tiers end at 10,340, 51,300 and 153,700 GB.

So 148,315.43 GB is $11,194.28, and 197,753.91 GB is $13,773.90.

Stage 1: $8,310.60 + $4,123.38 + $11,194.28 = $23,628.26. Stages 2 and 3 add $710.93 + $342.14: $24,681.33.

Commands: Stage 2, 60,000 x 2 = 120,000. Stage 3, 60,000 x 3 + 37,500 = 217,500.

Stage 4: $11,075.40 + $2,843.71 + $342.14 + $13,773.90 = $28,035.15, and 80,000 x 3 = 240,000 commands.

Stages 5 and 6: the load balancer, the limiter, the counters and about $26,134 of egress on 444,946 GB round to the tile's $54k/mo.

Commands: the canvas draws Stage 5 as (400,000 + 240,000) / 180,000 = 3.5556 a call, and 180,000 x 3.5556 = 640,008.

Stage 6: (240,000 + 7,950) / 180,000 = 1.3775 a call, so 247,950 commands.

Check in: Close the page and rebuild Stage 3's commands from the storm.

The limiter's real bill

Skip on a first read; come back before the interview. The canvases bill each load all month, and two lines differ from AWS.

This is Stage 4 at its 80,000 peak, held all month, at AWS prices. The canvas there comes to about $28,035.

Load balancer: our callers are servers that keep connections open, so new connections are rare. Processed bytes bind instead.

An LCU also covers 1 GB of processed bytes an hour. At 2 KiB a call, 80,000 x 2 x 3,600 / 1,048,576 = 549.3 LCU.

That is about $3,180 a month, not the card's $11,075.

Data moved between zones is not on the canvas. A check moves about 0.2 KiB, and two thirds of the limiter tasks are not in the primary's zone.

80,000 x 2/3 x 0.2 KiB x 2,592,000 s = 26,367 GiB a month. The application pays $0.01 a GB: about $264.

The limiter tier is about $2,844 and the counters about $342. The counters cost a little more than the bytes that cross zones to reach them.

The answers' egress, about $13,774, is the API's either way.

By hand the month comes to about $20,400: $3,180 + $2,844 + $342 + $13,774 + $264.

In a storm, a refused call gets a 429 of about 0.3 KiB. In Stage 3 the answers average 0.375 x 1 + 0.625 x 0.3 = 0.56 KiB, not 1.

The trade-off:

The limiter and its store are about a sixth of the real bill, and the store alone a sixtieth. The answers to callers are about two thirds.

Check in: Why does the real load balancer line come to under a third of the card's?

Other Regions, hard quotas and a big tenant

Three questions usually follow. None changes a canvas, so we reason by hand.

Other Regions: Global Datastore, ElastiCache's copies in other Regions, is read-only there, so another Region cannot INCR.

One global counter would put every check across Regions, tens of ms. So each Region runs its own cluster with a share of each key's limit.

A small job sums each Region's counts per key every 10 s, and sends each Region its share plus 10% headroom. Over-admission stays within that headroom.

Or pin each key to a home Region and forward its checks: exact, and slower for callers far from it.

Hard quotas: a paid monthly allowance needs a commit, not an estimate. In DynamoDB, AWS's key-value database, one item for each key and month holds what remains.

A commit is a conditional write: subtract n only if at least n remain. The limiter in front refuses the obvious excess cheaply.

Do not commit every call. One item takes at most 1,000 writes a second, and 80,000 x 2,592,000 = 207.36 billion writes a month.

At $0.625 a million on demand, that is about $129,600 a month. So each task takes a block of the quota and counts it down in memory.

A big allowed tenant: a key allowed 100,000 calls a second puts 300,000 commands on one shard, 86% of 348,000.

Leases fix it: each task takes 100 tokens at once with one INCRBY. 100,000 / 100 x 3 = 3,000 commands a second.

At most 40 x 100 = 4,000 tokens sit taken and unused, 0.07% of the minute's 6M. The error refuses early, never late.

Rollout: a new rule ships in shadow mode first. It counts and logs what it would refuse, and refuses nothing.

Monitor refusals by key and rule, keys over 80% of a limit, store use, the fallback's share and clock offset.

The trade-off:

Each answer trades a little exactness for speed: a share per Region, a block per task, a lease per task. Each error is small and bounded.

Check in: Why can another Region not check its keys on a Global Datastore copy?

Say this in 45 minutes

The interviewer asks: What fails in this design, and what does a caller see?

A design that works on a good day is half an answer. The interviewer asks what fails, who notices, and what it costs.

The Valkey primary fails: the replica takes over in seconds; plan for under a minute. Tasks use local limits meanwhile.

A shard stalls: each task's breaker opens, and the task decides locally until a probe succeeds. The API stays up.

A task's clock is seconds off: it counts into the wrong minute. So the fleet alarms on clock offset.

The bad SDK ships: the limiter holds the API to its limits. The SDK fix is backoff, a longer wait after each failure.

Add jitter, a random part of the wait, so clients do not retry together. And respect Retry-After.

Old SDK versions run for weeks, so the server cannot depend on clients.

A key leaks: revoke and reissue it. The deny cache holds the flood until then.

Say it out loud: "A limiter tier in front of the API, a sliding window counter in Valkey, INCR first and DECR on refusal."

And: "The store sees every call, refused ones too. Size it for the storm, and make a refusal cheap with a deny cache."

Minutes 0 to 5: requirements. Per key, per minute, 429 and headers, fail open with a local limit.

Minutes 5 to 10: Stage 1, why a limiter, and where it sits.

Minutes 10 to 20: the algorithms and the pick; Stages 2 and 3, window edges, the sliding counter and INCR first.

Minutes 20 to 28: Stage 4. The store sees every call; shards and hash slots.

Minutes 28 to 36: Stages 5 and 6. A hot key, the deny cache, leases for a big tenant.

Minutes 36 to 45: failure, failover, other Regions, hard quotas and monitoring.

The trade-off:

Each answer has a price. A tier and a store see every call, an outage gives rough limits, and a refusal can last a little long.

Check in: Set a timer for 45 minutes. Give the whole answer out loud, and check it against the pacing plan.