Rate Limiting Algorithms

Start here

This page teaches one rate limiter at three levels of growing scope. The Mid-level enforces one limit for one key correctly across 20 servers. The Senior level adds several limits, many keys and rules that change live. The Architect level asks what the whole system promises. It adds three Regions, billing, attacks, a slow backend and a lost Region.

The table shows what each level teaches, and which round of the interview loop Design a Distributed Rate Limiter it prepares you for.

The page follows one example, and each thing that happens in it is a numbered event (event 1, event 2, and so on). Each level shows only its own events, so the numbers inside a level can jump. Reference lists every event in one table.

The diagram shows the three pages that teach rate limiting, in the order to read them.

Synthesizing vector architecture diagram...

1. On this page you learn each mechanism, on one example.
2. In the interview loop Design a Distributed Rate Limiter you apply the mechanisms. An interviewer raises the scope in three rounds, and you design the system.
3. In the drill The Partner Whose Retry Loop Took Down Everyone Else you defend a design. The drill asks two questions about one incident.

The pages share subjects, never wording. This page asks learning questions at each checkpoint. The loop asks interview prompts.

What you'll be able to do after this page

Mid-level

1. Say what a limit promises as a rate, a burst, a key and a cost, and tell a rate limit from a quota and from load shedding. Section: A limit is two numbers and a key.
2. Explain what a fixed window, a sliding log and a sliding window counter each bound, and where each lets too much through. Section: Counting in windows.
3. Run a token bucket by hand, bound any interval with burst + rate × time, compute Retry-After, and explain GCRA and the two kinds of leaky bucket. Retry-After is the response header that tells a refused client how many seconds to wait. Section: The token bucket.
4. Enforce one limit across 20 servers in four ways, and say for each way whether it admits too much or too little. Section: Twenty servers, one limit.
5. Make the check one atomic step with one clock, and say what a fast clock or a read-then-write costs. Section: One atomic step, one clock.
6. Choose the key, size the memory, and set a TTL that never hands out free tokens. A TTL is the time after which the store deletes a key that nobody has written. Section: Keys, memory and expiry.
7. Decide in advance what each limit does when its store is down, and compute what each choice lets through. Section: When the limiter's store fails.
8. Send the right status code and Retry-After, and know what your proxy and edge send by default. Section: What the client is told.

Senior

9. Check several limits on one request in one all-or-nothing call. Section: Several limits on one request.
10. Change a rule while traffic flows, and launch it in shadow mode first. Section: Changing a rule.
11. Lease blocks of tokens for a key too hot for one shard, and state the overshoot. A shard is one node of the store's cluster, holding a share of the keys. Section: A key too hot for one shard.
12. Place each limit in the layer that can see what it counts. Section: One request, end to end.
13. Map all of it to AWS, and name the look-alikes. Section: On AWS.

Architect

14. Enforce one limit across three Regions with regional shares that move by named grants, and say what the sum of shares bounds. Section: One limit, three Regions.
15. Decide what the other Regions do with a lost Region's share, and tell a lost Region from one that is only cut off. Section: When a Region is lost.
16. Keep billing quotas apart from rate limits, count each admitted request once, and say how late a quota is enforced. Section: A rate limit is not a billing quota.
17. Explain why limits per address and per account do not fire when an attack is spread over many addresses. Section: An attack spread over many addresses.
18. Explain why limits per client cannot protect a backend that slows down. Section: A slow backend when every client is under its limit.
19. Choose between AWS's managed limiters and a limiter you build, by what each promises and what each costs. Section: Build on AWS's limiters or your own.

Every mechanism on this page has an accuracy and a direction in which it errs. The table under What is the accuracy target for each mechanism?, in the Architect checkpoint, lists them all.

If you arrived from a step of an interview loop, Pages that send readers here, near the end of the page, says where that step's material is.

---

Mid-level: one limit, enforced correctly

This level teaches one limit, for one key, enforced correctly by 20 gateways. It starts with the problem, then builds the fix one decision at a time. It matches Round 1 of the rate limiter loop, steps 1.1 to 1.6.

The problem: twenty gateways, each with its own count for one key

This section describes a common failure in distributed systems: local correctness that leads to global failure. Every individual gateway server enforces the rate limit correctly on the requests it receives. The system as a whole still admits 20 times the limit.

Basketly, an online grocery shop, sells to meal-kit partners through a Partner API. The API runs on twenty gateway servers. A load balancer in front of them spreads requests evenly, so each gateway receives one twentieth of the requests.

One of the partners is FreshBox. It has the API key k-7, and its contract allows 10 requests a second. Each gateway is configured with the full limit, 10 a second. Each gateway checks every request against that limit in its own memory. It counts the requests it has admitted for k-7, and it refuses a request that would take its own count over the limit.

No gateway can read another gateway's count. This page calls that design separate local counters.

At 09:00:00 on Tuesday, FreshBox deploys a sync client with a retry bug. The client sends its next request as soon as it gets an answer, even when the answer is a refusal. With the bug, k-7 sends 400 requests a second, and it keeps doing so for two minutes.

The fleet should admit 10 of those requests each second and refuse the rest. Here is what happens instead:

• Gateway 1 receives 400 ÷ 20 = 20 requests a second for k-7.
• Gateway 1 admits 10 a second and refuses the other 10. By its own count, that is correct.
• Every other gateway does the same. The fleet admits 20 × 10 = 200 a second.

The contract allows 10 a second in total. The fleet admitted 200.

The admitted requests go to the shared orders service, which can take 800 requests a second. The other partners send 695 a second. With k-7's 200, orders receives 695 + 200 = 895 a second, more than it can take. Every partner's requests slow down.

The big picture

The diagram shows the system as shipped. Each gateway keeps its own count for k-7. The diagram labels each count a "bucket", the name the later sections use.

Synthesizing vector architecture diagram...

Added to the other partners' 695 a second, that pushes orders to 895 requests a second against the 800 it can take.

The dashed store is where one shared count for k-7 would live. As shipped, that store does not exist. The dashed arrows are the calls the gateways would make to it, and do not make.

---

A limit is two numbers and a key

This section shows what a limit promises, and sets up the example that the rest of the page follows.

The opening gave FreshBox's contract as one number, 10 requests a second. In full, the contract says 600 requests a minute, bursts up to 20. The 600 a minute is the same 10 a second: 600 ÷ 60 = 10.

What does "600 a minute, bursts of 20" promise?

It sounds like one number, 600, plus a small extra condition. It is really four decisions.

This page calls FreshBox's two minutes of 400 requests a second the storm. The storm tests all four decisions.

Rate, burst, key, cost

The table lists the four decisions and their values for k-7.

The burst is there on purpose. A dashboard page load fires 10 to 15 calls in a few milliseconds (section R1.1 of the rate limiter loop).

The key matters as much as the numbers. The same limit keyed on the source IP or on each user gives a different answer. Keys, memory and expiry shows how.

The cost can be more than 1. An export costs 10 in Several limits on one request. A cost can also be bytes or samples. The message queue loop counts bytes a second, and the metrics loop counts samples.

"600 a minute" alone doesn't say whether all 600 may arrive in the same millisecond. The burst says it: at most 20 at once, then 10 a second. Counting in windows shows what happens when a limiter only knows the 600.

Each gateway enforces k-7's contract as a token bucket. A token bucket is a count of tokens that refills at 10 a second up to a maximum of 20, and each admitted request spends one token. The token bucket explains how it counts.

Rate limit, quota, shedding

Three mechanisms refuse requests, and each answers a different question. A rate limit refuses with 429. That is the HTTP status "Too Many Requests", which refuses the request.

Quotas are covered in A rate limit is not a billing quota. Load shedding is covered in the section Backpressure: stock protects itself of Retries, Timeouts, Backpressure & Load Shedding.

Why an overloaded service fails, and how it should shed load, is the subject of Retries, Timeouts, Backpressure & Load Shedding. This page is about why the fleet admitted more than the limit, and how to make the fleet enforce it.

A limit on requests in flight is a fourth mechanism. It caps how many requests run at once, not how many start per second. Stripe's "concurrent requests limiter" is one example, and its general name is a bulkhead. The section Bulkheads and concurrency limits of Retries, Timeouts, Backpressure & Load Shedding covers it.

The broader primitive Distributed Rate Limiting surveys all of these mechanisms. This page follows one key through the mechanisms the loops use.

The example we follow

A real API has thousands of keys, too many to watch. So one story runs through the whole page: one API key bursting across 20 servers.

The shop is Basketly, the online grocery shop from the opening, seen through its Partner API. The same shop appears in Retries, Timeouts, Backpressure & Load Shedding and Queues & Delivery Semantics. The partner FreshBox and its key k-7 are new on this page.

Every trace on this page comes from running a private reference simulation of this setup, not from working it out by hand. The simulation models the arrivals, the 20 gateways, the store and the clocks. Every algorithm and every failure policy is a setting of it.

The table lists the example's settings. The numbers are small so that every decision fits on a line.

Two settings need a few more words.

The storm. FreshBox's client runs 40 workers. Each worker sends a request, waits for the answer, and sends again at once. The answer takes 100 ms, whether the request was allowed or refused. Together the workers send 400 a second, which is one request every 2.5 ms. Over the two minutes that is 48,000 requests in all.

The circuit breaker. A gateway's circuit breaker is a switch that stops calls to the store after repeated failures.

The same settings appear at real scale on other pages:

• Gateways. The rate limiter loop has 6 in Round 1 and 24 in Round 2. The drill The Partner Whose Retry Loop Took Down Everyone Else has 12.
• The contract. The rate limiter loop uses 100 a minute with a capacity of 20. The mobile stock-trading loop uses 5 a second with a burst of 10.
• The page load. "A page load fires 10 to 15 calls" (rate limiter loop).
• The storm. The drill has 40,000 a minute on one key.
• orders. Overload belongs to Retries, Timeouts, Backpressure & Load Shedding.
• The store. The rate limiter loop assumes about 1 ms for a round trip, and "about 60,000 script calls a second per node". The second figure is an assumption to load-test.
• Timeout and breaker. Step 1.4 of the rate limiter loop.
• Key TTL. Step 1.6 of the rate limiter loop.

We replay the same two minutes under each design. Each design is called a rung, and the rungs are named L0 to L6. Counting in windows lists them.

The rungs are alternatives compared on equal terms. They are not guards added one by one. Only L5 and L6 build on L4, which is the fix.

The page also runs failure cases, called side rows or replays:

• a race.
• a fast clock.
• a store that goes away.
• a hot key, which is a single key that receives more checks than one store node can handle.
• an export.
• the edge, which is the first layer that a request from the internet reaches.

Each failure case runs on a copy of the rung it names, so the effect of one event does not hide the effect of another.

The story has one title per section:

• a limit is two numbers and a key: this section.
• the minute that was spent in 1.5 seconds: Counting in windows.
• the bucket that refills: The token bucket.
• twenty servers, one limit: Twenty servers, one limit.
• the calls that read the bucket at the same instant, and the gateway clock that ran fast: One atomic step, one clock.
• the wrong key: Keys, memory and expiry.
• the store that failed: When the limiter's store fails.
• what FreshBox was told: What the client is told.
• one Tuesday, four new failures: The problem: one Tuesday, four new failures.
• the export that cost ten: Several limits on one request.
• the plan that changed while the gateways disagreed: Changing a rule.
• the key too hot for one shard: A key too hot for one shard.
• one request, end to end: One request, end to end.
• one Thursday in three Regions: The problem: one Thursday in three Regions.
• one limit, three Regions: One limit, three Regions.
• the Region that was lost: When a Region is lost.
• the month-end invoice: A rate limit is not a billing quota.
• the attack spread over 4,800 addresses: An attack spread over many addresses.
• the backend that slowed down: A slow backend when every client is under its limit.
• managed limiters or your own, and what each costs: Build on AWS's limiters or your own.

Each section shows only its own events. The full table is in The whole story, event by event.

The first three events run under the fix, L4, which is one central token bucket. They show normal traffic, the page load and the start of the storm.

Events 1 to 3, under the fix (L4: one central token bucket)

In event 1 the bucket stays full because it refills at 10 a second and only 5 a second leave.

In event 2 all 15 calls are allowed because 15 ≤ 20. The normal 5 a second are still arriving, so the bucket gains a net 10 − 5 = 5 tokens a second. It is full again about 15 ÷ 5 = 3 s later. In the run, the bucket is exactly full at the 08:59:33.000 arrival, 2.9 s after the page load.

In event 3 each gateway sees k-7 every 50 ms: 400 ÷ 20 = 20 a second.

---

Counting in windows

This section shows three limiters that count requests per window of time: a fixed window, a sliding log and a sliding window counter. A window is a length of time, here one minute, over which the limiter counts.

At 09:00:01.4975 FreshBox had used its whole minute. Rung L1 is one central fixed window of 600 a minute: one shared counter per clock minute. L1 admitted the storm's first 600 requests back to back. The last of them arrived 599 × 2.5 ms = 1.4975 s into the minute. Then L1 refused everything for 58.5 seconds.

That is 600 requests in 1.5 seconds. In the first second alone L1 admitted 400, which is 40 times the contract's 10 a second. Every one of them reached orders.

The limiter counted correctly. But it counted only the total per minute, not how close together the requests arrived.

Here are the rungs. Each replays the same four minutes of k-7's traffic, from 08:59:00 to 09:03:00. The two-minute storm, from 09:00:00 to 09:02:00, is inside them.

Fixed window

The simplest shared count is a fixed window. It keeps one counter per key per window, and the counter is named after the window.

The pseudocode shows the check.

pseudocodeCopy
FIXED WINDOW (limit L per window of W seconds)
    window = floor(now / W)                       now from the gateway's clock: plain commands can't read the store's clock in the same step
    count  = INCR   rl:{k7}:<window>              atomic; creates the counter at 0 if it is missing
             EXPIRE rl:{k7}:<window> 2 × W        sent with every INCR, in the same pipeline
    if count > L:
        DECR rl:{k7}:<window>                     count only admitted requests
        refuse
    admit

The fixed window splits time into windows of W seconds and lets a key make at most L requests in each one. For rung L1, W is 60 s and L is 600. now is the current time from the gateway's clock. Plain commands can't read the store's clock and use it in the same step, so the gateway supplies the time.

window is the window's number, floor(now / W). Every request in the same 60 s gets the same number, and that number names the counter rl:{k7}:<window>.

INCR adds 1 to that counter and returns the new value as count. If the counter does not exist, INCR first sets it to 0, so the first request of a window creates it. INCR leaves an expiry that the key already has unchanged. The expiry deletes old windows; 2 × W keeps last window's count for the sliding window counter below.

If count is now above L, the request is refused. DECR then takes the 1 back off, so the counter holds only admitted requests. Otherwise the request is admitted.

The DECR never makes the limiter refuse a request that should pass. The first refusal in a window happens only after L requests were admitted.

The result is admit or refuse, and the only state is one counter per key per window. The algorithm never looks at when inside the window the requests arrived. That is why a whole window's limit can pass in one second.

INCR is atomic. That means the store runs it as one step, and no other command can run in the middle of it. EXPIRE is a second command, so the pair is not atomic. Suppose a gateway sends EXPIRE only after the first INCR of a window, and the gateway stops between the two commands. The counter then has no expiry. No later request sets one, because only the first INCR returns 1. The count stays correct, because the next window uses a new key. But the old key stays in memory until something deletes it. Sending EXPIRE with every INCR closes this gap, because the next request sets the expiry. MULTI and EXEC close it too, because the store runs all of the commands between them or none. So a fixed window needs no script. That is why fixed windows are popular.

Envoy's global rate-limit service works this way. It computes the window start as (now / divider) * divider, and it counts with a pipelined INCRBY plus EXPIRE.

Event 4 is the storm under three rungs: the 60 s fixed window (L1), a 1 s fixed window (L1b), and the token bucket (L4) for comparison.

Event 4, on the storm trace

Here is what happened under each rung.

L1. It admits 600 in 09:00:00.000 to 09:00:01.4975, and nothing until 09:01:00.000. Then it admits 600 again by 09:01:01.4975.

The most L1 admits in any 60 s is 907. That is the 60 s from 08:59:01.6 to 09:00:01.5. It holds 292 normal requests, the page load's 15, and all 600 of the storm's first burst.

L1b. It admits 10 at the start of every second. Its 14 in one second comes from 4 normal calls late in one second, then 10 at the start of the next.

But L1b refused 6 of the 15-call page load. The normal call at 08:59:30.000 had used 1 of that second's 10, so the page load got 9. The next 4 normal calls in that second were refused too.

L4. It admits the burst of 20, then 10 a second.

Snapshot T3 shows L1's counter at three moments.

Snapshot T3 (L1)

The totals of the three rungs barely differ. What differs is when the requests are admitted.

The 60 s window meets the contract's total and breaks its rate. It hands out a minute's budget in a second and a half.

Shrink the window to 1 s, and little can pass around the boundary between two windows: at most 20 in any second. But now honest bursts are refused.

A window has only one number, and a limit needs two. The window's total is the rate. No number sets the burst.

The chart compares L1 and L4 second by second.

Synthesizing vector architecture diagram...

The line that spikes is the fixed window (L1). It admits 400 in second 0 and 200 in second 1. It admits zero until second 60, then 400 and 200 again. That is 1,200 in all.

The flat line is the token bucket (L4). It admits 29 in the first second, which is its burst of 20 plus 9. Then it admits 10 every second. That is 1,219 in all.

The two totals over two minutes match. The difference is in the timing. The fixed window's spikes are 40 times the contract's per-second rate of 10.

The axis is not evenly spaced. It skips most of the seconds in which both lines stay flat.

The edge between two fixed windows

The storm could only send 400 a second. A client that can send faster gets even more requests past a fixed window. It sends at the end of one window and again at the start of the next. The boundary between the two windows is called the edge.

Side row W shows it. It runs on a fresh key, k-9, with no history. k-9 sends 600 requests spread over 09:04:59.000 to 09:04:59.999, and 600 more over 09:05:00.000 to 09:05:00.999.

The table shows what five limiters admit in the same two seconds.

The diagram shows the same five results, one panel per limiter, with the count for each of the two seconds.

Synthesizing vector architecture diagram...

In the panel "Fixed window, 60 s", the first 600 are counted in minute 09:04 and the next 600 in a new count for minute 09:05. So it admits all 1,200, which is twice the limit in two seconds.

The panels "Sliding log" and "Sliding window counter" hold the total near 600. They admit 600 and 609. But both let 600 through in one second.

The panels "Fixed window, 1 s" and "Token bucket" hold the burst down, to 20 and 39 in the two seconds. Of these two, only the token bucket also lets a real page load through (The token bucket). The 1 s window refused part of one in Event 4.

This is the second question of the drill The Partner Whose Retry Loop Took Down Everyone Else. A fixed window lets a client send nearly twice the limit around each window's edge, "which is exactly the kind of burst a misbehaving retry loop would trigger". Anywhere else in the window, it lets the whole window's budget through at once.

Sliding log

Keep the timestamp of every admitted request, and count those in the last 60 s.

The pseudocode shows the check.

pseudocodeCopy
SLIDING LOG (limit L in any W seconds)
    ZREMRANGEBYSCORE rl:{k7}:log  -inf  (now - W)      drop entries older than the window
    if ZCARD rl:{k7}:log >= L:
        refuse
    ZADD rl:{k7}:log  now  <unique id>                  in one script with the lines above
    admit

The sliding log keeps the exact time of every admitted request. It admits a new request only if fewer than L requests were admitted in the last W seconds. Those seconds are counted back from now, not from a window's start. Here W is 60 s and L is 600.

rl:{k7}:log is a sorted set. Each member is one admitted request, stored under a unique id, and its score is the time it was admitted. now is the store's current time.

The check has three commands:

• ZREMRANGEBYSCORE deletes every member older than now - W, so the set holds only the last 60 s.
• ZCARD counts the members left. If there are L or more, the request is refused and nothing is added.
• Otherwise ZADD records this request with the score now, and the request is admitted.

The three commands run in one script, so no other check can change the set between the count and the add. The result is admit or refuse. The cost is memory: one entry for every admitted request in the window.

Event 5 (L2). The log is exact. It never admits more than 600 in any 60 s. It admits 1,200 in the two minutes.

But the log still holds the timestamps from before the storm. When the storm begins, the log holds the 314 requests k-7 made in the 60 s before. So only 290 pass in the storm's first second, and 293 in its first 1.5 s.

After that, the log admits exactly as fast as old entries turn 60 s old. That is 5 a second, the pace of 08:59's normal traffic. From 09:00:30.100 the page load's entries turn 60 s old, and the log admits 15 back to back, one every 2.5 ms.

So a window algorithm's output copies the shape of the previous window.

The log's memory is one entry per request kept. For k-7 that is up to 600 entries. If you log every attempt, it is 400 a second × 60 s = 24,000 entries. You need to log every attempt if you want to refuse by attempts. So the log is largest exactly when you are under attack (Memory per key).

Each check also first deletes the entries that have aged out. A very busy key can pile up millions of stale entries, and that makes its ZREMRANGEBYSCORE slow. Nothing else runs on that node until the command finishes (The atomic script).

Sliding window counter

Keep two numbers, this minute's count and last minute's. Estimate the count of the trailing 60 s, which is the 60 s that end now, by assuming last minute's requests were spread evenly.

The pseudocode shows the estimate and the check.

pseudocodeCopy
SLIDING WINDOW COUNTER (limit L per W seconds)
    elapsed  = now - start of this window
    estimate = previous_count × (W - elapsed) / W  +  current_count
    if estimate + cost > L:
        refuse
    INCR the current window's count                     counting admitted requests only
    admit

The sliding window counter estimates the sliding log's count with two counters per key instead of one entry per request. W is the window length (60 s), L is the limit (600), and cost is the number of requests this call counts as. The cost of a normal call is 1.

The other values:

• current_count is the number of requests admitted so far in the current fixed window.
• previous_count is the number admitted in the window before it.
• elapsed is the number of seconds since the current window started.

The trailing W seconds overlap the previous window by W - elapsed seconds. The algorithm assumes the previous window's requests were spread evenly. So it counts the fraction (W - elapsed) / W of them, and then adds current_count. The sum is estimate.

If admitting this call would take estimate above L, the call is refused. Otherwise the current window's counter is increased, so it counts admitted requests only, and the call is admitted.

The result is admit or refuse. The answer is only an estimate, and it is wrong when the previous window's requests were not spread evenly.

Here is the estimate with the storm's numbers. 15 seconds into minute 09:00, three quarters of the trailing 60 s still lies in minute 08:59. Minute 08:59's count is 315. So it contributes 315 × 45 ÷ 60 ≈ 236.

Event 6 (L3). Minute 08:59 held 315 requests: 300 normal requests and the page load of 15. The counter admits 290 in the storm's first second. It admits 599 in minute 09:00 and 599 in minute 09:01, which is 1,198 in the two minutes. In minute 09:01 it runs smoothly, at 9 or 10 a second.

How wrong the counter's estimate can be

The counter is an estimate, not a bound. A bound is a number that the limiter never goes above.

On real traffic the estimate is very good. Cloudflare built its rate limiting this way. It measured "400 million requests from 270,000 distinct sources". It found "0.003% of requests have been wrongly allowed or rate limited", with "an average difference of 6% between real rate and the approximate rate".

But an adversary who fills the end of a window breaks the even-spread assumption. Side row W2 continues side row W. After k-9's 600 requests at the end of minute 09:04, k-9 sends 1,000 a second through minute 09:05.

The counter admits about 10 a second as the weight of minute 09:04 fades. One trailing 60 s then holds 1,189 requests. That is nearly twice the limit, spread over a minute.

A window can also be made of many small windows, for example 60 one-second counters. That is a finer fixed window. It has a smaller error at the edge and more counters, and it still has only one number.

---

The token bucket

This section shows how a token bucket counts and what it guarantees for any interval of time. It also shows two relatives of the token bucket: GCRA and the leaky bucket.

The token bucket is rung L4. It takes two numbers, so it can say what the contract says: 20 at once, then 10 a second. Here is how it counts, and why it never needs a timer.

The token bucket's check

Each key's bucket is two numbers, tokens and ts. tokens is the number of tokens in the bucket. ts is the time at which tokens was last computed.

Nobody adds tokens on a schedule. Each check works out how many tokens would have been added since ts.

This is the check from step 1.2 of the rate limiter loop, with one rule made explicit: the bucket is written back on every check, allowed or refused.

The pseudocode shows the check.

pseudocodeCopy
CHECK(key, cost, b = 20, r = 10 a second)
    now   = the store's clock                              (One atomic step, one clock)
    state = read(key)                                      { tokens, ts } or nothing
    if nothing:
        tokens = b                                         a new bucket starts full
    else:
        elapsed = max(0, now - state.ts)                   never negative
        tokens  = min(b, state.tokens + elapsed × r)       lazy refill
    if cost > b:
        allowed = false
        retry_after = none                                 no wait is long enough
    else if tokens >= cost:
        tokens = tokens - cost
        allowed = true
        retry_after = 0
    else:
        allowed = false
        retry_after = ceil((cost - tokens) / r)            whole seconds
    write(key, { tokens, ts: now }, expire after TTL)      on every check
    return allowed, floor(tokens), retry_after

CHECK decides whether one request may pass under a token bucket. It refills the bucket at the moment of the check instead of on a timer.

The inputs:

• key names the bucket, here k-7's.
• cost is the number of tokens the request needs: 1 for a normal call.
• b is the bucket's capacity, which is the burst: 20 tokens.
• r is the refill rate: 10 tokens a second.
• now comes from the store's clock.

The stored state holds two values. tokens is the number of tokens left after the key's last check, and ts is the time of that check. A key with no stored state starts with a full bucket of b.

Otherwise elapsed is the time since ts, never below zero. The bucket gains elapsed × r tokens, capped at b.

If the bucket now holds at least cost tokens, the request is allowed and cost tokens are removed. If not, the request is refused. retry_after is then the number of whole seconds until enough tokens will have refilled: (cost - tokens) / r, rounded up.

If cost is larger than b, the bucket can never hold enough tokens. Any retry_after would be a false promise, so the check refuses without one. A rule like this is a configuration error. Several limits on one request rejects it when the rule is saved.

Either way the new tokens and ts = now are written back with an expiry. So the bucket of a key that stops sending is deleted after the TTL.

CHECK returns three values:

• whether the request is allowed.
• the whole tokens left, which the response reports to the client as its remaining budget (The budget on every response).
• retry_after, or none when cost is larger than b.

Events 7 to 9 are the storm under L4.

Events 7 to 9 (L4)

Event 7. The 20th request arrives 47.5 ms into the storm. In that time, 47.5 ms of refill at 10 a second added 0.475 tokens. So the bucket holds 0.475 tokens after the 20th request. Snapshot T1, further down in this subsection, shows that state.

From 09:00:00.050 each request finds a fraction of a token. The bucket reaches exactly 1 every 100 ms, and a request arrives every 2.5 ms. So one request in every 40 is admitted.

Event 8. The most L4 admits in any 1 s is 29, and in any 60 s 619. orders carries 695 + 10 = 705 a second.

Event 9. A refused request finds between 0 and 1 token, so its true wait is under 0.1 s. Retry-After is in whole seconds, so it says 1. All 46,781 refused storm requests got Retry-After: 1.

The chart shows the bucket's tokens during the first 300 ms of the storm.

Synthesizing vector architecture diagram...

The bucket starts full at 20, and the burst is spent once, in the first 47.5 ms. The bucket holds 19 after the first request and 9.25 at 25 ms. At 50 ms it holds 0.5, and the 21st request finds less than one token and is refused.

After that the bucket never holds a whole token for long. It gains 0.25 tokens every 25 ms and reaches 1 every 100 ms. One request takes that token, the bucket is back at 0, and it starts again.

From then on the bucket admits exactly 10 a second, one request in every 40.

Snapshot T1 is the state just after the burst.

Snapshot T1, 09:00:00.048 (L4)

The bound on any interval

In any interval of t seconds, a token bucket admits at most a full bucket plus what refills during the interval. In the formula, b is the burst and r is the rate.

$$\text{admitted in any } t \text{ seconds} \;\le\; b + r \times t$$

For k-7 the formula gives two bounds:

• In any second, at most 20 + 10 × 1 = 30. The run admitted 29.
• In any minute, at most 20 + 10 × 60 = 620. The run admitted 619.

The run is one lower each time. The last of those tokens arrives exactly as the interval ends, and intervals here don't include their end.

So the burst is the overshoot you accept. Overshoot means requests admitted above the rate. With b = 600, "600 a minute" would allow 600 + 600 = 1,200 in a minute. That is the same 2× as the fixed window.

Step 1.2 of the rate limiter loop makes the point with its own numbers: "capacity 100 would allow 200 in a minute".

Keep b small: big enough for an honest page load, and no bigger.

Retry-Afterfrom the refill

The check already knows when the next token arrives: in (cost − tokens) ÷ r seconds. In event 9 that wait was under 0.1 s.

Retry-After carries whole seconds, so the check rounds the wait up. Retry-After in whole seconds explains why. A client that honours the header comes back at a time when it can succeed.

GCRA: the same decisions with one number

GCRA is the generic cell rate algorithm. It comes from ATM (Asynchronous Transfer Mode) networks, where it policed the rate of fixed-size packets called cells.

GCRA stores one number per key, the theoretical arrival time, written tat. It is the time at which the key would be exactly back in step with its rate.

The pseudocode shows the check.

pseudocodeCopy
GCRA(key, cost)                                  T = 1 / r = 100 ms ; tau = (b - 1) × T = 1.9 s
    now = the store's clock
    tat = read(key) or now                         a new key starts "full"
    tat = max(tat, now)
    if tat + T × cost - now <= tau + T:            the same test as tokens ≥ cost
        write(key, tat + T × cost)
        allow
    else:
        refuse
        retry after (tat + T × cost - T - tau - now)

With the same rate, burst and clock, GCRA makes the same allow-or-refuse decisions as the token bucket, 20 at once and then 10 a second. It stores one number per key instead of two.

Its values:

• T is the time one request uses up at the allowed rate: 1 ÷ r = 100 ms for 10 a second.
• tau is how far ahead of schedule a key may run, which is its burst allowance: (b − 1) × T = 1.9 s for a burst of 20.
• tat, the theoretical arrival time, is the one stored number. It is the time at which the key would be back in step with its rate if it sent nothing more.

A key with no stored tat starts at now. A tat in the past is moved up to now, so idle time never builds up more than one full burst.

The test asks whether tat + T × cost − now, how far ahead of now the key would be after this request, is at most tau + T. If it is, the request is allowed and tat moves T × cost further ahead. That is 100 ms for a normal call. For a cost of 1 the test is tat − now ≤ tau: tat may be at most tau ahead of now.

Otherwise the request is refused, and tat stays as it is. The client may retry after tat + T × cost − T − tau − now. For a cost of 1 that is tat − tau − now. It is the moment the key is back within its allowance.

For a new key whose requests, each of cost 1, arrive at the same instant, the first 20 move tat from now to now + 2.0 s. The 21st finds tat 2.0 s ahead, more than tau, and is refused.

The diagram follows tat through the burst and the first refusal.

Synthesizing vector architecture diagram...

When the 21st request arrives, tat − now is 1.95 s. That is more than τ = 1.9 s, so the request is refused and tat stays where it is.

Real time keeps moving, so now comes closer to tat. 50 ms later tat − now is 1.9 s, which is not above τ. So the next request is allowed, and tat moves on by another 100 ms.

From then on, every 100 ms of real time brings now back within τ, and one more request fits. That is 10 a second, the same as the token bucket.

Event 10 (L4g). On the whole trace, GCRA and the token bucket made identical decisions for all 48,615 requests. Those are every storm request, the page load and the normal traffic. Every request on the trace has a cost of 1.

That is not a coincidence. The two limiters store the same information in different forms. A bucket holding tokens is a tat of now + (b − tokens) × T. The test "tokens ≥ cost" is the test "tat + T × cost − now ≤ τ + T". For a cost of 1 it is "tat − now ≤ τ".

GCRA saves one field. It is harder to explain in an interview.

The leaky bucket: a queue or a meter

"Leaky bucket" names two different things, and a third thing is also called by that name. The table lists the three.

The queue. Requests wait in a queue of 20 and are released at 10 a second. A full queue refuses.

Side row Q replays the storm through this queue. The same 10 a second come out, which is 1,200 in the two minutes. But each admitted storm request waits up to 2.0 s (20 ÷ 10). The page load's last call waits 1.4 s.

NGINX limit_req with a burst works this way: "Excessive requests are delayed until their number exceeds the maximum burst size". NGINX passes the first request of a quiet key at once, and holds up to burst more behind it. The hotel reservation loop puts a waiting room in front of its admitter on purpose (step 2.2 of the hotel reservation loop).

The meter. NGINX's documentation calls limit_req "the “leaky bucket” method". With nodelay, it refuses instead of delaying, and its decisions are a token bucket's. NGINX keeps an excess count per key, which time drains at the rate. A request is refused when the excess after it would be above burst.

NGINX measures time in whole milliseconds. With delay=n, NGINX delays only the excess requests beyond the first n.

The counter reset every period. Step 2.3 of the Shopify case study describes one: its "leaky bucket" reset every period.

A queue is the right choice in front of something fragile that must see a smooth rate. For an API it usually is not. Adding up to 2 s of latency to answer "no" later is usually worse than answering "no" now.

---

Twenty servers, one limit

This section explains the opening problem, and compares the designs that make 20 servers enforce one limit.

As shipped (L0), each of the 20 gateways ran a correct token bucket for k-7, and together they admitted 200 a second. The opening named the cause: separate local counters.

This section first shows the numbers behind that failure. Then it shows four ways to make 20 servers enforce one limit. For each way it says whether the design admits too much or too little.

Snapshot T2 puts L0 next to L4, the fix, at the same moment of the storm.

Snapshot T2, 09:00:30: L0 against L4

Synthesizing vector architecture diagram...

The difference is how many buckets there are. L0 has twenty buckets for k-7, one in each gateway. Their admissions add up to 200 a second, twenty times the rate.

L4 has one bucket, rl:{k7} in the store, and every gateway asks it. So k-7 gets 10 a second in total.

Why twenty buckets admit twenty times the rate

Event 11 (L0). Each gateway sees k-7 every 50 ms, because 400 a second ÷ 20 gateways is 20 a second for each.

The gateway's bucket starts full at 20, and it refills 0.5 tokens between arrivals. So the gateway admits everything for a while: 39 requests in its first 1.9 seconds, until the burst is spent.

Then the gateway admits 10 a second, which is one request in two. Twenty gateways × 10 = 200 a second.

Over the two minutes of the storm, the fleet admits 24,380 requests in the run. The most it could admit is 20 × (20 + 10 × 120) = 24,400. The contract allows 20 + 10 × 120 = 1,220.

The table compares L0 with L4 over those two minutes.

Under L0 the most in any 1 s is 400, because every gateway spends its burst in the same second. The orders load under L0 is 695 + 200 = 895 a second.

Other pages and products describe the same failure:

• The drill The Partner Whose Retry Loop Took Down Everyone Else. This is the drill's first question. Local counters on 12 gateways each see about a twelfth of the key's traffic, and they let the key have 12 times its limit. The drill's limit is 1,000 requests a minute per key, and its retry storm is 40,000 a minute. A retry storm is the partner's client resending every refused request at once, so the retries multiply its traffic. Every other partner's p99 latency goes up from 60 ms to 900 ms. The p99 latency is the time within which 99% of requests finish.
• The rate limiter loop. Step 1.0 of the rate limiter loop is this design. Step 1.1 of the rate limiter loop tells the same story at six gateways: "a scraper made 580 requests in one minute against a limit of 100. Each of our six gateways counted about 97."
• The email loop. In step 2.6 of the email loop, 63 mail transfer agents counting locally send 63 times too much. Mail transfer agents are the servers that send the email.
• The mobile stock-trading loop. Step 2.6 of the mobile stock-trading loop says: "30 order API tasks each counting locally would let one account send 30 times its limit".
• Envoy. Envoy's documentation states the effect in one sentence, for its own per-process limiter. Without its cluster-wide setting, "the total rate limit of whole gateway will be N * X tokens per second".

Split the limit into exact shares

Give each gateway its share of the limit. N is the number of gateways.

• The share of the rate is r ÷ N = 10 ÷ 20 = 0.5 a second.
• The share of the burst is b ÷ N = 1. A share of the burst is never less than 1.

Side row X replays the storm with exact shares, under two ways of spreading the requests over the gateways.

The bound for exact shares is 20 × (1 + 0.5 × 120) = 1,220.

Exact shares never admit too much, and they admit too little when traffic is uneven.

Two systems use exact shares. Envoy's local rate limit filter offers them as local_cluster_rate_limit. That setting divides the limit by the number of Envoy instances, so the whole gateway enforces X a second "regardless of how N changes". And step 2.6 of the mobile stock-trading loop has each task admit "the fleet's safe rate … divided by the current task count, recomputed on every scale event".

The shares must be recomputed whenever the fleet scales. Step 2.4 of the notification loop shows why. With each of 20 workers enforcing "quota ÷ 20", "autoscaling to 30 overshoots by 50%".

A burst of 1 per gateway has a cost too. It admits a page load only if the load balancer happens to spread the page load over enough gateways.

Send the key to one server

This design is called sticky routing. The load balancer routes by hash(k-7), so every request for k-7 goes to the same gateway.

Side row Y replays the storm this way. All of k-7 goes to G3, which keeps a local bucket of 10 a second and 20. G3 counts every request once, so it admits like L4, and it needs no store.

Sticky routing has two costs:

• G3 alone now carries all 400 a second of k-7's storm, far more than any other gateway.
• At 09:01:00 the fleet scales out to 21 gateways. The hash moves k-7 to G21, and G21's bucket starts full. That admits +19 extra requests at once: 1,238 in the two minutes instead of 1,219.

Each membership change hands out one extra burst per moved key. Step 1.1 of the rate limiter loop rejects sticky routing for the same reasons.

Count the key in one place

Event 12 (L4). Keep one bucket in the shared store. Every gateway asks it, so k-7 gets 10 a second whichever gateway a request lands on.

The cost is one round trip on every request, which is 1 ms here. It is also 400 store calls a second for k-7, because a refused request costs a call too.

The store is now on every request's path. Three sections deal with that: One atomic step, one clock, When the limiter's store fails and A key too hot for one shard.

Which way each design errs

The diagram puts five designs next to each other: the local buckets, and the ways to count once. Each box says whether its design admits too much or too little.

Synthesizing vector architecture diagram...

• Local buckets admit too much: N times the limit.
• Exact shares of r ÷ N never admit too much, but admit too little when traffic is spread unevenly.
• Sticky routing is exact, but puts the whole key on one hot server. It also hands out one extra burst b whenever the key moves to another server.
• The central store is exact and costs one extra round trip per request.
• Leased blocks admit too much by at most N × 1.2 × B tokens (gateways × 1.2 × block). A key too hot for one shard explains them.

So every design except the central store gives up exactness somewhere. Only local buckets err by an amount that grows with the number of servers: up to N times the limit.

The table compares the five on equal terms.

The same bucket when you are the caller

A limit set by someone else, such as a payment provider's or a push service's, is a shared limit too. Every caller in your system spends from it.

Stripe's documentation advises clients to "implement a client-side token bucket". It documents 100 live-mode requests a second per account, and 25 per endpoint unless noted.

The rule is one bucket per outside limit, shared by every caller. Two pages apply it. Step 2.3 of the crowdfunding loop keeps one bucket per payment endpoint and one for the account. The section Shared limits of Idempotency & Effectively-Once Processing gives the resolver that replays payments its own cap inside the provider's limit. So replays can't use up the tokens that live charges need.

The other side of a throttle is deferring work that got a 429. The section Deferring healthy work of Queues & Delivery Semantics covers it.

A cap on concurrency, such as Lambda's reserved concurrency, is not a pace. It limits calls in flight, and the rate is concurrency ÷ call duration.

A limit enforced per node is right when it protects that node itself. Step 2.5 of the chat loop lets each gateway accept at most 300 new connections a second, because each gateway's own TLS work is the resource.

---

One atomic step, one clock

This section shows how the central bucket must be updated.

At 09:03:00 the storm is over and k-7's bucket holds 5 tokens. FreshBox's dashboard fires 15 calls, and they land on 15 different gateways within half a millisecond.

How many get through?

It depends on two things: whether the check is one step or three, and whose clock the check reads.

Fifteen calls, five tokens

Side row C runs on a copy of L4. k-7's normal traffic is removed after 09:02:00, and the bucket is set to 5 tokens at 09:03:00.000. The 15 calls leave 15 gateways 33 µs apart.

First, each gateway does the check in three steps: GET the bucket, decide, SET it. A GET reaches the store 0.5 ms after it is sent. The SET follows 1 ms later.

The diagram shows three of the fifteen gateways.

Synthesizing vector architecture diagram...

So every gateway reads the same 5 tokens, decides that 5 is enough, allows its call and writes back 4. Fifteen calls passed on five tokens. The bucket even says 4 were left, because each SET overwrites the one before and the last one wins.

The note at the end gives the other version. With the atomic script, each check sees the previous check's result, so 5 calls are allowed and 10 are refused.

Snapshot T4 compares the two versions.

Snapshot T4, 09:03:00.0015

This failure is a check-then-act race. The check and the action are separate steps, and other actors change the value in between.

A lock around the three steps would cost two more round trips per request. And a gateway that dies while it holds the lock blocks the key until the lock expires.

The atomic script

Redis and Valkey can run a server-side script: a small program that is loaded into the store, and that the store runs as one command. Valkey's documentation says: "Valkey guarantees the script's atomic execution. While executing the script, all server activities are blocked during its entire runtime."

So the whole check runs inside the store. The pseudocode shows the call a gateway makes.

pseudocodeCopy
EVALSHA <sha of CHECK> 1 rl:{k7}  <cost> <b> <r> <ttl>
    KEYS[1] = rl:{k7}                   every key the script touches is passed in KEYS
    ARGV    = cost, b, r, ttl           rule parameters are arguments (Changing a rule)
    inside the script:
        now = TIME                      the store's clock
        tokens, ts = HMGET KEYS[1] tokens ts
        refill                          (CHECK, in The token bucket's check)
        decide
        HSET tokens and ts
        EXPIRE ttl
        return allowed, floor(tokens), retry_after

This is how a gateway runs CHECK inside the store as one atomic step. The first line is the call, and it has four parts:

• EVALSHA runs a script that was loaded into the store earlier. The script is identified by the SHA-1 hash of its text, so the gateway sends only the hash and the arguments.
• The 1 says that one key follows.
• KEYS[1] is that key, rl:{k7}. It is stored as a hash, a record with named fields, and it holds the bucket. Every key the script touches must be passed in KEYS. That way the store knows which node must run the script, and in a cluster the client's routing knows it too.
• ARGV carries the rule: cost, b, r and the ttl. So one script serves every rule.

Inside the script, now comes from the store's own TIME command, not from the gateway's clock. HMGET reads tokens and ts. The script then refills and decides exactly as CHECK does. HSET writes both fields back, and EXPIRE resets the key's expiry.

The script returns the same three values as CHECK: whether the request is allowed, the whole tokens left, and the retry time.

EVALSHA calls a script already loaded by its hash, so each check sends a few bytes.

Keep scripts short. While a script runs, nothing else runs on that node, for any key. A node runs one script at a time, so it can run only a limited number of scripts a second. A key too hot for one shard reaches that limit.

Is TIME inside a script safe?

The question is about the replica, the second copy of the store. Scripts are replicated by their effects, which are the writes they made, and not by re-running them. So a replica receives "tokens = 0.01, ts = …" rather than a script that would read a different clock.

Effects replication has long been Redis's default: "Use commands (effects) replication by default in scripts", in its release notes. Valkey's documentation notes that verbatim replication was removed.

Whose clock the script reads

The script reads TIME from the store instead of taking now from the gateway. Side row S shows why.

Side row S runs on a copy of L4 where the script uses the time each gateway passes in. Gateway G7's clock is 2 seconds fast. The diagram shows three checks in a row.

Synthesizing vector architecture diagram...

The next check comes from G8, whose clock is right. Its now is t + 2.5 ms, so the elapsed time is negative. The script clamps it to 0, gives no refill, allows the call and writes G8's own true time back as ts. The next 18 checks, from other gateways, spend the remaining tokens.

Then G7 checks again with now = t + 2.05 s. It finds about 2 s "elapsed" again, and refills the bucket to 20 for everyone. So every 50 ms G7 refills the bucket to 20, and the other gateways spend it.

The table gives the storm's result under three clocks.

Here is where the 2,359 comes from. Each of G7's checks gains 50 ms × 10 = 0.5 tokens. The next gateway's clamp throws away 0.025 of them. That gives 19.5 a second after the burst, and 19.66 a second averaged over the two minutes.

Any difference between callers' clocks creates extra tokens. Reading one clock removes this problem.

A small problem remains. In a failover, the replica takes over from a failed primary (When the limiter's store fails). The new primary's clock may be ahead of the old one's by δ. That hands each bucket at most δ × r extra tokens, once.

Leases, Fencing Tokens & Distributed Locks has the general rule in its section Time: whose clock decides?.

DynamoDB as the limiter's store

A durable, serverless store is tempting. Event 14 is the same check on DynamoDB:

• An update expression can only add and subtract, so it can't compute a refill. The check becomes a strongly consistent read, then a write conditioned on the ts it read, retried when another check wrote first. A fixed window is simpler: one UpdateItem with ADD and a condition.
• k-7's 400 checks a second become 400 reads and 400 writes on one item. Checks from 20 gateways overlap, so conditional writes fail and retry, which adds more reads and writes.
• One partition takes at most 1,000 write units a second. k-7 fits. The hot key of A key too hot for one shard, at 100,000 a second, does not.
• A condition can't read DynamoDB's clock, so the gateway's time is back in the refill. That brings back the problem that side row S showed.
• TTL deletes expired items "within a few days", so a reader must treat an expired item as absent itself.

Section R1.11 of the rate limiter loop, in its follow-up 3, prices this design. A check takes milliseconds. At that loop's traffic, DynamoDB's reads and writes cost about USD 6,500 a month, against about USD 231 for the cache (two Redis OSS nodes; about USD 185 on Valkey).

DynamoDB suits limiter rules and billing quotas. The per-request check belongs in memory.

---

Keys, memory and expiry

This section shows what to key a limit on, what each key costs in memory, and when the store may delete a key.

A reviewer, to be safe, keys the bucket on hash(api_key + user_id). This is a composite key: a key built from two values, the API key and the user id.

FreshBox's 40 sync workers each act for a different grocery store account. During the storm, all 400 requests a second are admitted. The algorithm and the store are right. The key is wrong.

40 accounts, 40 buckets

Side row K runs on a copy of L4 with three different keys.

The composite key. There are 40 workers, one account each. That makes 40 buckets, each seeing 10 a second, so none ever runs dry.

The source IP. FreshBox has one NAT address. That is the single public address that all its servers share. FreshBox's second app, k-8, is behind the same NAT and sends an honest 20 a second.

k-8 gets 0.58 and 0.39 a second, with random arrivals and seeds 1 and 2. Which of the two it gets depends on whether k-7 or k-8 last found the bucket full, because that sets the refill's timing. Another seed gives 0.

With evenly spaced arrivals the answer depends only on phase, which is the fixed offset between the two keys' arrival times. Then k-8 gets all 20 a second or nothing.

Step 2.1 of the rate limiter loop lists the composite key as its first common wrong answer.

The fix is one bucket per dimension. A dimension is one thing a limit counts by, such as the plan, the user or the IP. The buckets are rl:{k7}:plan, rl:{k7}:user:<id> and rl:{ip}:unauth. All of them are checked together in one call (Several limits on one request).

What to key on

The table lists the common keys. For each key it says who shares one bucket, and what the trap is.

A bot that walks through random ids makes every lookup a miss. Caching & Invalidation sends that problem here, in its section Negative caching: the keys you don't have. The answer is to limit each client: by API key, or by IP where there is no key.

Memory per key

Event 15 is what one key costs to keep, under each algorithm.

NGINX's limit_req keeps its state in each node's shared memory, in an area it calls a zone. Its documentation says: "The stored state always occupies 64 bytes on 32-bit platforms and 128 bytes on 64-bit platforms". When the zone is full, "the least recently used state is removed".

At a million active keys, two numbers each is about 100 megabytes. A log at 100 entries each is gigabytes. Section R1.11 of the rate limiter loop gives 6.4 GB against 96 MB.

TTL and eviction

Every key needs a TTL, set on every write. Without one, the store fills with keys of clients who called once.

How long should the TTL be?

Side row 6t runs L4 with a TTL of 1 s. That is shorter than the bucket's full refill, which takes b ÷ r = 20 ÷ 10 = 2 s.

k-7 sends nothing from 09:02:00.000 to 09:02:01.200. Then its normal 5 a second resumes. The table follows the bucket.

No request is admitted extra here, because k-7's 5 a second never needs the 7 tokens. The run admits the same number with a TTL of 1 s and of 60 s.

The 7 tokens matter when the key bursts right after the reset. It then gets 20 at once instead of 13.

With the rate limiter loop's TTL of 60 s nothing changes. Any idle bucket is full again after 2 s. So if its key then expires, the new bucket is created full, exactly as the old one was.

The rule: TTL ≥ b ÷ r makes expiry harmless.

Eviction means that the store deletes keys because it is short of memory.

The rate limiter loop's volatile-ttl policy evicts the keys closest to expiry first. With the TTL reset on every write, those are the longest-idle buckets. But any bucket evicted before it has fully refilled comes back full (section R2.8 of the rate limiter loop).

Size the store so it doesn't evict, and alarm on evictions.

---

When the limiter's store fails

This section shows what each gateway can do when the store does not answer, and what each choice lets through.

At 09:01:00, halfway through the storm, the limiter store's primary fails. ElastiCache promotes the replica, which means the replica becomes the new primary. AWS says writes "can resume as soon as the promotion process is complete, typically just a few seconds".

Replay F runs this failure on a copy of L4 rewound to 09:00:00. In replay F the promotion takes 12 seconds. For those 12 seconds no gateway can get an answer.

What does each gateway do with the requests in front of it?

A timeout and a breaker on the limiter's store

The limiter has its own timeout and its own circuit breaker. The sections Timeouts and deadlines and Circuit breakers of Retries, Timeouts, Backpressure & Load Shedding build them for any dependency, and the limiter uses them exactly as built there:

• A check waits at most 3 ms. A normal round trip is 1 ms.
• After 5 timeouts in a row, the gateway's breaker opens and stops calling the store.
• An open breaker sends one probe a second.

Event 16. Each gateway checks about 55 times a second. That is 20 checks for k-7 and about 35 for the other 39 partners (695 ÷ 20).

The first timeouts come at 09:01:00.000 to 09:01:00.020. Five timeouts in a row take about 0.09 s, so every breaker is open within about a tenth of a second.

The first probe goes 1 s after the breaker opens, and then one probe goes every second. The probes fail until the store is back. The probe at about 09:01:12.09 succeeds.

So each gateway is degraded for 12.09 to 12.10 s. Every check in that time is decided by the failure policy. The failure policy is the rule for what a gateway does with a request it cannot check. It also decides the few checks that timed out before the breaker opened.

Snapshot T5 shows the fleet five seconds into the outage, under three failure policies.

Snapshot T5, 09:01:05

Synthesizing vector architecture diagram...

• In the panel "Open", every check is allowed. All 400 a second of k-7's storm pass, and orders receives 1,095 a second.
• In the panel "Closed", every check is refused. Every partner is refused and orders is idle, so the cache failure becomes an outage for all 40 partners.
• In the panel "Local share", each gateway enforces 0.5 a second for k-7, about 10 a second across the fleet. It passes the other partners' requests, so orders receives about 707 a second.

Under the local share, k-7 stays near its contract while everyone else carries on.

Three failure policies

Events 17 to 19 are the same 12.1 seconds under each policy.

Open. All of the storm is admitted: 400 × 12.1 = 4,840 requests. The orders load is 695 + 400 = 1,095 a second, so orders is at 137% of its 800. That hurts every partner.

Closed. All of the other partners' requests are refused: 695 × 12.1 = 8,400. A 12-second cache failure became an outage of the whole API.

Local share. k-7 is admitted 20 × (1 + 0.5 × 12) = 140 requests, which is about its contract. No other partner is refused, because the others are under their own limits.

The local share is the exact shares of side row X (Split the limit into exact shares), switched on while the store is away. Each gateway's bucket for k-7 refills at 0.5 a second and holds 1. It starts full at that gateway's first timeout.

The local share errs on the safe side. It never admits more than 20 at once plus the rate. And it needs no network.

The choice is per limit, made before the outage:

• A capacity or fairness limit, such as k-7's contract: a local share, or fail open for short outages if the backend has headroom. Stripe's rate limiters "fail open". Envoy's global rate-limit filter does too by default. Its failure_mode_deny is false, and its call to the rate-limit service times out after 20 ms by default.
• Closed only for one route whose abuse costs more than its outage, and then for that route alone.

Security limits with more servers than the limit

A login limit of 5 a minute per account on 20 gateways has a share of 5 ÷ 20 = 0.25 a minute, with a burst of 1. Here the number of gateways, N, is larger than the limit, L.

In side row 7s an attacker sprays one account's logins across all 20 gateways during an outage. The table shows what two local fallbacks let the attacker have.

When there are more servers than the limit, a local share still lets up to N through at once. There are three answers:

• accept it for short outages.
• send that key to one gateway while the store is away, by hashing, as in Send the key to one server.
• close that one route.

The loops choose differently. The rate limiter loop falls back to local limits (step 1.4 of the rate limiter loop). The bot-defense case study also pauses scale-out while it is degraded (section R1.9 of the bot-defense case study).

When the store comes back

Event 20. From about 09:01:12.09 the probes succeed and the breakers close.

The promoted replica holds k-7's bucket as it was last written before 09:01:00. That was a fraction of a token, and 12 seconds of refill have filled it to 20. So k-7 gets one burst of 20 and then 10 a second. That is 28 more from the central bucket in 09:01:12 to 09:01:13, once each breaker closes.

Under L5 the local shares also admitted their 20 at about 09:01:12.003. Those are already counted in event 19's 140.

Our copy assumes the replica had every write. Real replication is asynchronous. That means the primary confirms a write before the replica has it. So a failover also loses the last writes before it, and hands their tokens back. The subsection How many writes an asynchronous failover can lose of Replication, Quorums & Read-Your-Writes covers this.

All of that is at most one extra burst per key.

The other risk is the recovery itself. When a failover finishes, every gateway reconnects at once. Step 2.4 of the rate limiter loop and Retries, Timeouts, Backpressure & Load Shedding cover these simultaneous reconnections.

---

What the client is told

This section shows what a refused client receives: a status code, a time to wait, and its remaining budget.

At 09:00:00.050, FreshBox's 21st storm request is refused. The bucket holds 0.5 tokens, so one more token arrives in 50 ms.

Event 27 is what L6 sends back.

httpCopy
HTTP/1.1 429 Too Many Requests
Retry-After: 1
RateLimit-Policy: "k7-burst";q=20;w=2, "k7";q=600;w=60
RateLimit: "k7-burst";r=0;t=1
Content-Type: application/json

{ "error": "rate_limited", "limit": "k7", "retry_after_seconds": 1 }

The next subsections explain this response: the status code, Retry-After, and the two RateLimit headers.

429or 503

429 means this client sent too much. 503 means the service can't take the request, whoever sent it.

Retries, Timeouts, Backpressure & Load Shedding has the full table, under "503, 429 or backpressure?" in its section Backpressure: stock protects itself.

Event 28. orders is overloaded by L0's 895 a second. So orders should shed with 503 and Retry-After, by its own health. A 429 from orders would tell every partner that it had sent more than its own limit.

Retry-Afterin whole seconds

RFC 6585 defines 429: "the user has sent too many requests in a given amount of time". The response "MAY include a Retry-After header". The RFC also says "Responses with the 429 status code MUST NOT be stored by a cache".

RFC 9110 (section 10.2.3) allows Retry-After as a date or as delay-seconds, "a non-negative decimal integer". That means whole seconds. RFC 9110 also lets a 503 carry Retry-After (section 15.6.4).

So the refill's 50 ms becomes Retry-After: 1. Rounding up is right, because a client that comes back sooner would be refused again.

The budget on every response

Three groups of headers can tell the client its budget. The table gives the status of each group.

The X-RateLimit headers. Each API defines them itself. Reset is seconds in some APIs and a timestamp in others.

RateLimit-Policy and RateLimit. The draft is draft-ietf-httpapi-ratelimit-headers-11 (23 May 2026, expiring 24 November 2026). RateLimit-Policy carries policies as a quota q over a window w. RateLimit carries the current state as the available quota r and an "effective window" t. The draft describes t as "the time within which the client can use no more than the available quota".

The draft defines no mapping for a token bucket. So the headers in event 27's response are our mapping:

• the burst as its own policy: 20 over the 2 s the bucket needs to refill (b ÷ r).
• the rate as 600 over 60 s.
• r as the whole tokens left.
• t as the same wait we put in Retry-After.

The draft settles any conflict: "If a response contains both the RateLimit and Retry-After fields, the Retry-After field MUST take precedence".

Section R1.11 of the rate limiter loop, in its follow-up 2, asks the classic question. With capacity 20 and a limit of 100 a minute, Remaining says at most 20, because it counts what the client can send now. Say so in the docs, and send the policy.

Limiters that do not send 429by default

Event 28, continued. Several common limiters don't send 429 unless you tell them to. The table lists what each one sends by default.

Check what your proxy and your edge send before a client's retry logic meets it.

A client that honours Retry-After

Side row 10r replays the storm on a copy of L6, with a FreshBox client that honours Retry-After. Each of the 40 workers, on a 429, waits the seconds it was told before sending again. Allowed answers still come back in 100 ms.

The table compares that client with the client as shipped.

The limiter admits exactly the same, to exactly the same workers. The gateways, the store and the network see about a ninth of the traffic.

The uneven split between the workers is not caused by Retry-After. It is an artifact of our perfectly regular model. An artifact is a result that comes from the model's exact timing, not from the design. The diagram shows why.

Synthesizing vector architecture diagram...

Worker 21 arrives at 09:00:00.050, finds less than one token and is refused with Retry-After: 1. Worker 1 arrives at 09:00:00.100, the moment the bucket reaches 1 token, and is allowed.

Worker 21 waits 1 s, as told, and returns at 09:00:01.150. That is 50 ms after worker 1 took the token at 1.100, so worker 21 is refused again. It is refused again at 2.250 and at 3.350.

Every other worker likewise arrives a few milliseconds after a token has been taken. It finds less than one token and is refused, whether it resends at once or waits a second. In the model the arrival times never shift, so worker 1 is always the first to arrive after a token.

The split changes when answer times vary:

• With answer times that vary by ±10 ms, every one of the 40 workers is served, and the busiest gets 55 to 84 of the 1,219 (seeds 1 and 2).
• With ±1 ms, nobody is starved when workers honour Retry-After, but the split is still uneven.

Real answer times vary, so one worker doesn't hold every token in practice. But a limiter that refuses rather than queues serves whoever arrives first after a token appears. It limits each key to that key's rate. It does not divide the key's tokens evenly among one client's workers.

If FreshBox wants its budget shared evenly, its workers share one client-side bucket, paced by the RateLimit fields.

Clients still add jitter to whole-second waits, so that many refused clients don't all return together. The section Backoff and jitter of Retries, Timeouts, Backpressure & Load Shedding covers jitter.

Here jitter changes nothing, because worker 1 still arrives exactly as each token does. The run tried waits jittered by up to 0.1 s, 0.5 s and 1 s.

A server can help by computing Retry-After from the refill, as here, rather than sending a fixed number.

---

Mid-level checkpoint

This checkpoint tests the Mid-level. Three exercises come first, each a think-first question with its answer. The first uses the numbers of the drill The Partner Whose Retry Loop Took Down Everyone Else on 12 gateways. The second builds one limit in three ways, and the third takes the store away for 20 s. Four questions with model answers follow.

Check yourself: Mid-level

What does each counting method bound, and which one would you choose for a limit of 100 a minute when page loads send 10 to 15 calls at once?

• A fixed window bounds only the total per window. It allows 2× across an edge, and the whole window at once.
• A sliding log bounds every trailing window exactly. But it still allows the whole budget in one burst, and it costs memory per request.
• A sliding counter is a good estimate that an adversary can push near 2×.
• A token bucket bounds any interval of t seconds to b + r × t, so it limits the rate and the burst separately.

For 100 a minute with page loads of 10 to 15 calls, choose a token bucket: rate 100 a minute, burst 20, in one atomic script. Then at most 120 pass in any minute, and a page load always passes.

On AWS An Amazon API Gateway usage plan takes the same rate and burst, but applies them on a best-effort basis.

Why does a limit that every server enforces correctly add up to N times the limit, and which way does each count-once design err?

Local buckets on each server give up to 20× (the naive design). Three designs count the key once:

1. Exact shares, r ÷ 20 per server. They are never over. They are under when traffic is spread unevenly. Recompute them on every scale event.
2. Route the key to one server by hash. This is exact until membership changes, then +b per moved key. It also makes one hot server.
3. A central store with an atomic check. This is exact. It costs one round trip per request, and it is a store whose failure needs a policy.

For a very hot key there is a fourth design, leased blocks (A key too hot for one shard). They are over by at most servers × 1.2 × block.

On AWS The central store is Amazon ElastiCache, and exact shares on Envoy are its local_cluster_rate_limit setting.

What can change between a read and a write of the bucket, and what does a caller's fast clock add?

The check is one EVALSHA with the key in KEYS and the rule in ARGV. Inside the script:

1. read TIME.
2. read tokens and ts.
3. refill as min(b, tokens + elapsed × r), with elapsed clamped at 0.
4. allow if tokens ≥ cost.
5. write tokens and ts, and set the TTL.
6. return allowed, remaining and Retry-After.

The store runs it as one command, so concurrent checks can't all read the same value. With 15 calls on 5 tokens, 5 pass, not 15.

The script reads the store's clock because callers' clocks differ. A gateway 2 s fast refills the bucket every time it checks and lets everything through. A gateway 50 ms fast doubles the rate. Scripts replicate by their effects, so TIME inside is safe.

On AWS Amazon ElastiCache runs the script with EVALSHA, and it supports TIME inside the script.

Which failure policy suits a capacity limit, which suits a login limit, and why do the two differ?

First, a 3 ms timeout and a breaker, so no request waits on a dead store. Then a policy per limit, decided in advance.

• A capacity limit: a local share of r ÷ N on each gateway, or fail open for short outages if the backend has headroom. Count and alarm every bypass.
• A login limit: never open. A local share keeps it bounded. But with more gateways than the limit, it allows up to N attempts at once. So either accept that, route the key to one gateway, or close just that route.

Failing closed on everything turns a short cache failure into an outage for every client.

On AWS Envoy's global rate-limit filter fails open by default, because its failure_mode_deny is false. ElastiCache Multi-AZ promotes the replica, typically within a few seconds.

---

Senior: many limits, many keys, live rules

This level moves from one limit to many limits, many keys and rules that change while traffic flows. It matches Round 2 of the rate limiter loop, steps 2.1 to 2.6.

The problem: one Tuesday, four new failures

This section describes a common failure when a working limiter grows: one limit per key, in one place, under one rule, cannot express what the system now needs. The Mid-level fix holds k-7 to 10 a second. Four other things still go wrong on the same Tuesday morning.

Basketly's Partner API still runs on 20 gateways. The Mid-level fix is in place:

• one central token bucket per key, in the shared store;
• one atomic script that reads the store's clock;
• a local share on each gateway when the store does not answer.

In front of the gateways sits the edge. AWS WAF, Amazon's web application firewall, runs a rule there. The rule allows 3,000 requests per 60 s from one source address.

Each of the four failures below is a replay of the same Tuesday morning. Each replay runs on its own copy of the fixed design, as the Mid-level's failure cases did. They are not one timeline. In one timeline, the edge's block from 09:00:40 would stop FreshBox's later requests before they reach a gateway.

1. 09:00:40, at the edge. FreshBox's servers share one public address, called a NAT address. Through it come k-7's 400 requests a second and 20 a second from FreshBox's second app, k-8. That is 400 + 20 = 420 a second. The edge rule allows 3,000 per 60 s, which is 3,000 ÷ 60 = 50 a second. The WAF checks each address's count only about every 10 s, and it starts blocking some time after the first check that sees the count over the limit. In this replay the first such check is at 09:00:10, and blocking starts 30 s later, at 09:00:40. Until then the edge lets all 420 a second through to the gateways: 420 × 40 = 16,800 requests, far more than the 50 a second the rule allows. From 09:00:40 the rule refuses everything from that address, including k-8's honest 20 a second.

   The storm ends at 09:02:00. The address's count over the last 60 s then falls, and the first check that sees it under 3,000 is at 09:03:00. The block lifts 30 s after that check, at 09:03:30. One request, end to end derives these times.

2. 09:01:00, a rule change. FreshBox moves to the larger plan it has bought: 20 a second with a burst of 40. The new rule reaches the 20 gateways one at a time, one every 0.5 s. Basketly's gateways name each bucket after the rule's version, so old and new gateways spend two different buckets. While both kinds of gateway run, the fleet admits the old plan's 10 a second plus the new plan's 20 a second. That is 10 + 20 = 30 a second, more than the new plan allows.

3. 09:03:00, an export. An export costs 10 tokens from k-7's plan bucket and 1 token from an export bucket that refills one token every 5 s. FreshBox's first export, at 09:03:00.100, empties the export bucket. Its second export follows 1 ms later. The second export makes two separate calls. The first call charges the plan bucket 10 tokens. The second call finds the export bucket empty and refuses the export. FreshBox loses 10 tokens, one second of its contract, for a request it never got.

4. 09:10:00 to 09:11:00, a hot key. A bigger partner's key, k-big, runs a batch job that sends 100,000 requests a second for one minute. Every check, refused or not, is a script on the one shard that holds k-big's bucket. A shard is one node of the store's cluster. This page assumes that one shard runs about 60,000 such scripts a second. So the shard is asked for 100,000 ÷ 60,000 ≈ 167% of what it can do, and every other key on that shard waits.

The chart puts the four replays on one time axis.

Synthesizing vector architecture diagram...

This level teaches the four in this order: Several limits on one request (the export), Changing a rule, A key too hot for one shard, and then One request, end to end (the edge).

The shared, atomic token bucket from the Mid-level is the building block of every design on this level.

Several limits on one request

This section shows how to check one request against several limits.

At 09:03:00.100, after the storm, FreshBox starts two data exports. An export is expensive, so it is charged in two buckets:

• It costs 10 tokens from k-7's plan bucket. The plan bucket is the bucket for k-7's contract, the one this page has followed so far.
• It costs 1 token from a route bucket for POST /v1/exports. The route bucket refills at 0.2 a second and holds 1, which allows one export every 5 s.

Replay M runs on a copy of L4. By 09:03 the plan bucket has refilled after the storm and is full again.

One script, all buckets

The diagram shows the second export, checked by one script that looks at both buckets.

Synthesizing vector architecture diagram...

The script refills and checks both buckets before it charges either. rl:{k7}:plan holds 10.01 tokens, enough for 10. But rl:{k7}:route:exports holds 0.0002, short of 1.

Because one bucket is short, the answer to "every bucket has enough?" is no. Neither bucket is charged, so the plan stays at 10.

The refusal is 429 with Retry-After: 5. That wait comes from the bucket that was short. The route bucket needs 5 s to refill one token at 0.2 a second.

Events 24 and 25 are the two exports. Row 25' is export 2 again, checked with two separate calls instead of one script.

Events 24 and 25

In event 25 the wait is 5 s, since (1 − 0) ÷ 0.2 = 5 s. The remaining budget in the answer is the smallest bucket's, which is 0.

In row 25' FreshBox lost 10 tokens, a second of its rate.

Separate calls have two problems. They are not atomic with each other. A bucket can be charged for a request that another bucket refuses, as in row 25'. And their latencies add up.

So one script checks all the buckets. The pseudocode shows it.

pseudocodeCopy
CHECK_ALL(keys, costs, rules)                 one EVALSHA; every key in KEYS
    if any cost is larger than its bucket's burst:
        refuse, with no retry_after              no wait is long enough
    now = TIME
    for each bucket:
        refill it to now
    if any bucket has fewer tokens than its cost:
        write the refilled buckets
        charge none
        return refused, retry_after = the largest wait among the short buckets
    charge every bucket its cost
    write all
    set every TTL
    return allowed, remaining = the smallest remaining

CHECK_ALL checks one request against several limits in a single script, so either every bucket is charged or none is.

Its inputs:

• keys lists the buckets' keys. All of them are passed in KEYS, so that the script may touch them.
• costs gives the tokens the request costs in each bucket. The export costs 10 in FreshBox's plan bucket and 1 in the route's bucket.
• rules gives each bucket's burst and refill rate.
• now is the store's TIME.

The script first checks every cost against its bucket's burst. If any cost is larger than the burst, that bucket can never hold enough tokens, so the script refuses without a retry_after.

Then the script refills every bucket to now.

If any bucket holds fewer tokens than its cost, the script writes the refilled values back, charges nothing, and refuses. It sets retry_after to the longest wait among the buckets that are short, because the request can pass only when every bucket has enough.

Otherwise the script charges every bucket its cost, writes them all with their expiry times, and allows the request. It reports as remaining the smallest number of tokens left in any bucket, because that bucket runs out first.

When a rule is saved, check that its cost fits its burst: cost ≤ b. An export that costs 10 against a bucket that holds 5 would never pass.

Hash tags

A script can only touch keys in one hash slot. In cluster mode each key is placed by a hash of its name. A script whose keys land in different slots is refused with a CROSSSLOT error.

A hash tag solves this. Wrap the part of the name that should decide the slot in braces. rl:{k7}:plan and rl:{k7}:route:exports both hash only k7. So they share a slot, and one script reaches both.

The cost: a tenant's buckets all live on one shard. When the tenant is huge, that is the problem of A key too hot for one shard.

---

Changing a rule

This section shows what a bucket does while a new rule reaches the gateways one at a time.

A rule changes while traffic flows. Each gateway learns the new rule some time after it is published, and the 20 gateways do not learn it at the same instant. For a few seconds, some gateways run the old rule and some run the new one.

A rule that reaches 20 gateways one at a time

Side row V runs on a copy of L4, the fix, during the storm. At 09:01:00 FreshBox upgrades its plan. This is a loosening with a plain business cause: FreshBox paid for the larger plan.

• Rule v1, the old plan: r = 10 a second, b = 20.
• Rule v2, the new plan: r = 20 a second, b = 40.

Rule v2 is published at 09:01:00.000. Gateway G1 uses it from 09:01:00.000, G2 from 09:01:00.500, and so on, one gateway every 0.5 s. G20 uses it from 09:01:09.500. This spacing is a choice of the model. A real rollout depends on how often each gateway polls for rules and on how the deployment is staged.

The run compares five designs on the same storm and the same rollout. The load balancer is round-robin, as everywhere on this page.

One bucket. The bucket refills at the rate of whichever gateway checks it. A gateway that has moved refills with 20 a second, and a gateway that has not refills with 10. In the k-th half second of the rollout, k gateways run v2, so the fleet's rate is about 10 + 0.5 × k a second. Adding 0.5 s × (10 + 0.5 × k) for k = 1 to 20 gives 152.5, and the run admits 153. From 09:01:10 every gateway refills at 20 a second, so the fleet admits 20 × 50 = 1,000.

Two buckets. At 09:01:00 G1 makes its first check under v2. The v2 bucket is new, so it starts full, at 40 tokens. The gateways that have not moved keep spending the v1 bucket at 10 a second. So the fleet admits the new bucket's burst on top of the old rate, and then 10 + 20 = 30 a second until the last gateway moves.

The new plan's own bound for any 10 s is b + r × t = 40 + 20 × 10 = 240. Two buckets admit 334 in the first 10 s, more than even the larger rule allows. Measured over any sliding second, two buckets admit up to 66. The new plan's bound for one second is 40 + 20 × 1 = 60.

Every gateway at once. The bucket holds less than 1 token at 09:01:00, because of the storm. So switching every gateway at once adds no burst. The fleet admits 20 a second, 200 in the first 10 s.

The late copy. G5 runs v1 again from 09:01:20 to 09:02:00. G5 makes one check in 20 and refills with 10 a second, while the other 19 gateways refill with 20. So the bucket refills at (19 × 20 + 10) ÷ 20 = 19.5 a second. From 09:01:10 that gives 20 × 10 + 19.5 × 40 = 980 instead of 1,000. Here the stale rule lowers the rate by 2.5%. A late copy of a looser rule, after a tightening, would raise the rate instead. Either way the fleet runs a rule that nobody chose.

With a random spread instead of round-robin (seeds 1 and 2), the totals agree within 4: 153 and 154, 332 and 330, 200 and 200, 980 and 979. The busiest second of the two-bucket design admits 60 and 65.

The chart shows the requests admitted in each second, from 09:00:55 to 09:01:19, under three designs.

Synthesizing vector architecture diagram...

1. The line that climbs in small steps is one bucket with the rule numbers as arguments. It rises from 10 to 20 a second as the gateways move, one every 0.5 s, and reaches 20 in second 69.
2. The line that jumps to 40 and 59 is two buckets named after the version. The new bucket's burst of 40 is spent on top of the old rate. The line then stays at 30 a second, the old rate plus the new one, until the last gateway moves.
3. The line that steps straight to 20 is every gateway switching at once, for comparison.

In the first 10 s the three lines admit 153, 334 and 200. The new plan allows at most 240 in any 10 s.

Rule numbers as script arguments

Pass a rule's numbers (b, r, cost, TTL) to the script as arguments. Then every gateway uses the rule it was given, and the bucket in the store keeps its state.

When a rule tightens, the refill clamps the stored tokens to the new b. It never resets the bucket to full (step 2.2 of the rate limiter loop).

The bucket's key names the rule, rl:{k7}:plan, never the rule's version. So both the old and the new rule spend the same tokens.

A version in the key behaves like the composite key of 40 accounts, 40 buckets: it splits one count into two.

The pseudocode shows both halves: how a gateway accepts a rule set, and how the check uses the rule's numbers.

pseudocodeCopy
ON_RULE_SET(rule_set)                        a gateway receives rules from the rule store
    if rule_set.version <= running.version:
        ignore it                            a late or repeated copy never rolls back
    else:
        running = rule_set

CHECK(key, cost, r, b, ttl)                  key names the rule, never its version: rl:{k7}:plan
    now = TIME                               the store's clock
    tokens, ts = read(key)                   a key with no state starts full, at b
    elapsed = max(0, now - ts)
    tokens = min(b, tokens + elapsed × r)    refill at the r given, clamp to the b given
    if tokens >= cost:
        tokens = tokens - cost
        allowed = true
    else:
        allowed = false
    write(key, tokens, now)
    EXPIRE key ttl                           the TTL is an argument too
    return allowed

ON_RULE_SET runs in each gateway whenever the gateway receives a rule set. A rule set holds every rule's numbers and a version, a number that only goes up. running is the rule set the gateway uses now. If the new copy's version is not greater than running.version, the gateway ignores it. Otherwise the copy becomes running.

CHECK runs inside the store as one atomic script, as in The atomic script. Its inputs are the bucket's key, the request's cost, and the rule's rate r, burst b and ttl, which the gateway takes from running. now is the store's own clock. tokens and ts are the bucket's stored state.

The script refills with the r it was given and caps the tokens at the b it was given. So while gateways disagree, the bucket refills at the rate of whichever gateway checks it. The fleet's rate lies between the old rule and the new one, and it is never above the larger of the two. The script writes tokens and now back, resets the key's expiry to ttl, and returns whether the request is allowed.

Side row V, above, is the trace of this check during a rollout.

The clamp has no visible effect in side row V, because the storm keeps the bucket under one token. Suppose instead that the plan were tightened to a burst of 5 at 09:03:00. Replay M finds the plan bucket full, at 20 tokens, at that time. The next check would clamp the bucket to 5 tokens. It would not reset it to 20.

Versions that only go up

A rule set carries a version number that only goes up. A gateway keeps a rule set it receives only when that rule set's version is higher than the version it runs. So a late copy can never roll it back.

In side row V, G5 then ignores the late copy of v1. The fleet admits 1,000 from 09:01:10, as with no late copy.

How the rule store itself works, with conditional writes on a version, polling and staged deployment, is step 2.2 of the rate limiter loop.

Shadow mode before a rule refuses

Launch a new or tighter rule in shadow mode first. In shadow mode the rule computes its decisions and records them, but refuses nothing. Stripe's advice is "Dark launch each rate limiter". Envoy's rate-limit service has shadow_mode, and NGINX has limit_req_dry_run.

---

A key too hot for one shard

This section shows what happens when one key receives more checks than one node of the store can run, and how the gateways can ask the store less often.

Replay H leaves FreshBox. It runs on a copy, with a bigger customer. k-big is an enterprise key with a contract of 10,000 a second, burst 20,000.

k-big sends nothing before 09:10:00. So its bucket is full, and no gateway holds any of its tokens. From 09:10:00.000 to 09:11:00.000 a batch job with a bug sends 100,000 a second, spread evenly over the 20 gateways.

100,000 a second on one shard

Event 21, without leasing. Every request is a script call, refused or not. That is 100,000 script calls a second on the one shard that holds rl:{kbig}.

The rate limiter loop's working assumption is about 60,000 small-script calls a second per node. k-big alone is 100,000 ÷ 60,000 ≈ 167% of that.

Scripts on a node run one at a time (The atomic script). So every other key on that shard waits behind k-big's refusals, and those keys belong to other tenants.

Adding shards doesn't help. The cluster places each key in one hash slot, chosen by a hash of the key's name. Each slot lives on one shard. So one key is always on one shard.

Sharding, Hot Keys & Rebalancing covers hot keys in general, in its section A limit per key. This section covers the limiter's own fix.

Lease a block of tokens

Stop asking the store once per request. Each gateway leases a block of tokens, spends it in memory, and asks again only when the block runs low. To lease a block is to take it for a limited time.

Many per-request updates are combined into one call to the store. For a limiter, this is called pre-aggregation. The section Leasing and striping of Sharding, Hot Keys & Rebalancing describes it, and step 2.3 of the rate limiter loop is its source.

The diagram follows one gateway, G5, through one block.

Synthesizing vector architecture diagram...

G5 leases 125 tokens. The shard grants them because the bucket held at least 125, and G5 keeps the block in its own memory with an expiry of 10 s. For about 20 ms G5 then spends one token for each k-big request, with no network call.

When the block is down to 20% (25 tokens left), G5 asks for the next block. This time the bucket can't give a whole block. So the shard grants 0 and answers "denied until 0.25 s + jitter", one block cycle from now.

When its block is empty, G5 refuses k-big locally until that time. So k-big's refusals cost the shard nothing.

When a block expires, G5 gives any unused tokens back, and the bucket never goes above 20,000.

The pseudocode gives the three procedures: LEASE in the store, and SPEND and GIVE BACK in the gateway.

pseudocodeCopy
LEASE (in the store, one script)          B = 125, N = 20, r = 10,000 a second, b = 20,000
    refill the bucket from the store's clock
    if tokens >= B:
        tokens = tokens - B
        return granted B
    else:
        return granted 0, denied_until = now + N × B / r        (0.25 s)

SPEND (in the gateway, no network)
    if the local block has a token:
        spend it
        admit
    else:
        refuse locally
    if the block is at or below 20% of B, no lease is in flight, and now >= denied_until:
        send LEASE                                   at most one in flight per gateway
    on "granted 0":
        denied_until = the answer + random 0 to 50 ms

GIVE BACK (in the gateway)
    every block expires 10 s after it was granted, by the gateway's own monotonic clock
    at expiry, or on a clean shutdown:
        add the unused tokens back, capped at b

These three procedures let 20 gateways share one very busy key's bucket while calling the store about once per block instead of once per request.

The settings:

• B is the block size, 125 tokens.
• N is the number of gateways, 20.
• r is the key's refill rate, 10,000 tokens a second.
• b is its burst, 20,000 tokens.

LEASE runs in the store as one script. It refills the bucket from the store's clock as CHECK does. If the bucket holds at least B tokens, it removes B and grants the whole block. Otherwise it grants nothing and returns denied_until. That is now plus one block cycle: N × B / r = 0.25 s, the time the bucket needs to refill one block for every gateway.

SPEND runs in the gateway's memory for every request. It admits the request if the local block still has a token, and refuses it locally if not.

SPEND asks for the next block early, when the block is down to 20% of B (25 tokens). It asks only if no lease is already in flight and denied_until has passed. After a refusal it adds a random 0 to 50 ms to denied_until, so the 20 gateways don't all ask again at the same moment.

GIVE BACK limits how long leased tokens can sit unused. Each block expires 10 s after it was granted, timed by the gateway's own monotonic clock. A monotonic clock only moves forward, and it is not changed when the system time is corrected.

At expiry, or on a clean shutdown, the gateway adds its unused tokens back to the bucket, which never goes above b.

The price of admitting from memory is a bounded overshoot. The overshoot of leasing and its bound measures it.

The numbers:

• Block size. A block is about 0.25 s of one gateway's share: B = max(10, ⌈0.25 s × 10,000 ÷ 20⌉) = 125.
• Block cycle. This is the time the bucket needs to refill one block for every gateway: N × B ÷ r = 20 × 125 ÷ 10,000 = 0.25 s. A denied gateway waits that long, plus a little jitter. Jitter is a random extra delay, so that the 20 don't return together.
• Whole blocks or nothing. Suppose a lease granted whatever was left, a few tokens. The gateway would ask again a moment later. The fleet would then make about one lease call per admitted request, the same store load as without leasing.

The overshoot of leasing and its bound

Events 22 and 23 are the batch job's minute with leasing, run with two random seeds.

Events 22 and 23 (replay H), seeds 1 and 2

Each row needs a few words.

• Calls to the shard. About 83 of the 148 calls a second grant a block. At the steady rate that is 10,000 ÷ 125 = 80 grants a second. The first 20,000 tokens add the rest.
• Admitted in the minute. The bound is b + r × 60 = 20,000 + 600,000 = 620,000. It applies because k-big was idle before 09:10 and no gateway held any tokens.
• Most in any 1 s. The bound is b + r × 1 s = 30,000. The busiest second is the first second: the burst of 20,000 plus the rate.
• Worst excess over r × t. It is measured for intervals that start while the batch job is sending. Both results are inside the bound of 3,000 that the next paragraphs derive.
• Tokens that gateways hold at 09:11:00. The 113 tokens are unspent. They go back to the bucket when their leases expire, within 10 s. Until then the bucket is short by that much.

Here is where the excess comes from. The shared bucket is charged when a block is leased, not when it is spent. So a gateway may spend a block it leased a moment ago while other gateways lease new ones. An interval that starts while gateways hold blocks can see those tokens spent on top of r × t.

Each gateway holds at most 1.2 blocks: the rest of one block below 20%, plus the next block. So the overshoot is at most gateways × 1.2 × block = 20 × 1.2 × 125 = 3,000 tokens. That is 0.3 s of the rate.

The undershoot is the tokens stranded in leases when traffic stops or moves. A stranded token is one that a gateway holds and does not spend.

Snapshot T6 shows where k-big's tokens are in the middle of the minute.

Snapshot T6, 09:10:30 (seed 1)

Leasing is for capacity limits above about 500 a second.

A lease here is a grant of quota, not ownership of anything. So it needs no fencing token. A fencing token is a number that grows with each new lease and that the protected resource checks to reject an old lease holder. Leases, Fencing Tokens & Distributed Locks makes the same distinction.

---

One request, end to end

This section follows one request through every layer between FreshBox and orders, and shows what each layer can limit.

The edge is the outermost layer, the first one that a request from the internet reaches. Basketly also has a limit there. It is an AWS WAF rate-based rule on its CloudFront distribution: 3,000 requests per 60 s per source IP, action Block.

Replay E runs this rule on a copy of L6. FreshBox has two apps: k-7, and its second app k-8, which sends 20 a second from 08:59:00 on. All of FreshBox's traffic leaves through one NAT address.

The WAF blocked FreshBox 40 seconds late, and it blocked k-8's honest traffic too.

This replay is a model, not AWS's algorithm. AWS says only that the rule "gives more importance to more recent requests" and is "not intended for precise request-rate limiting".

Our model has four rules:

• It counts requests per IP over the trailing 60 s.
• It checks the count every 10 s. AWS says the rule "checks the rate about every 10 seconds".
• It starts blocking 30 s after the first check that sees the count over the limit. AWS gives "Usually, this delay is below 30 seconds" on one page and "usually 30-50 seconds. Can be up to several minutes" on another, so we also run 50 s.
• It counts blocked requests toward the rate.

Events 29 and 30 are what the WAF sees and does.

Events 29 and 30

Event 29. The 1,515 requests at 09:00:00 are 1,200 from k-8 and 315 from k-7. From then on 420 a second arrive (400 + 20), and the count passes 3,000 at 09:00:03.760.

Blocking starts at 09:00:40. By then 420 × 40 = 16,800 requests have passed. With the 50 s delay, blocking starts at 09:01:00 and 25,200 pass.

Event 30. The 403 goes to three kinds of traffic:

• the rest of k-7's storm, 32,000 requests.
• k-7's normal traffic after 09:02.
• 3,400 of k-8's honest requests, which is 20 a second for 170 s.

The count falls under 3,000 at the 09:03:00 check, and the block lifts 30 s later. If blocked requests didn't count, the block would lift at 09:02:10 instead.

The timeline shows the same events for both delays.

Synthesizing vector architecture diagram...

Nothing happens yet, because the WAF checks the count only every 10 s. The section "Checks every 10 s" marks the first check that sees the count over the limit, at 09:00:10. It also marks the first check that sees the count back under, at 09:03:00.

In the section "30 s delay", blocking starts 30 s after that first check, at 09:00:40. So 16,800 requests pass from 09:00:00 until the block starts. In the section "50 s delay", blocking starts at 09:01:00, and 25,200 pass.

With the 30 s delay, the block then continues until 09:03:30. That is a minute and a half after the storm ended at 09:02:00. The whole time it refuses k-8 too, because the rule sees one IP, not two apps.

Meanwhile the gateway's 429s were precise from the storm's 21st request, and for k-7 only. Both layers are useful.

The edge is cheap, and it stops a flood before the flood costs compute. But it is approximate, late and coarse.

The gateway is exact per key. But it runs after TLS, routing and authentication.

Layer by layer

The diagram shows the layers that a request passes, and which layer sends which refusal.

Synthesizing vector architecture diagram...

Each arrow back to the client is a different layer refusing for a different reason, with a different status:

• The edge refuses by IP, with 403 by default and for the whole IP.
• The gateway refuses by key, with 429 and Retry-After.
• orders refuses by its own health, with 503 and Retry-After when it is overloaded.

The load balancer refuses nothing. It only spreads requests, and its even spread is what made local counts fail in Twenty servers, one limit.

Event 31 follows one refused request through every layer. For each layer, the table says what it can see, what it limits, what it answers and how it fails.

Event 31: one refused k-7 request at 09:00:00.050, through every layer (L6):

One more fact about the WAF layer. Changing a rule's rate settings resets its counts and "can pause the rule's rate limiting activities for up to a minute" (section R2.8 of the bot-defense case study).

Put each limit where it can see what it counts:

• IP floods at the edge.
• keys and tenants in the gateway.
• overload in the service.

---

On AWS

This section maps the page to AWS services.

AWS runs rate limiters in two managed places, API Gateway and WAF. Both say plainly that they are approximate.

Anything exact, weighted, or keyed on something they can't see, you build yourself, usually on ElastiCache. A weighted limit is one where some requests cost more tokens than others.

Three rules carry over from the rest of the page:

• know what each one keys on.
• know what it sends when it refuses.
• know which limits are shared by more than one of your APIs.

Managed services that use it

The table lists the five services and what each provides. The facts that AWS documents for each service follow the table.

Amazon API Gateway. What AWS documents:

• The algorithm. "API Gateway throttles requests to your API using the token bucket algorithm, where a token counts for a request".
• The precision. "Both throttles and quotas are applied on a best-effort basis and should be thought of as targets rather than guaranteed request ceilings."
• The account limit. There is an account limit per Region, shared by all HTTP, REST, WebSocket and WebSocket callback APIs. The limit is "10,000 requests per second (RPS) with an additional burst capacity … maximum bucket capacity of 5,000 requests". It is raisable on request, and it is 2,500 and 1,250 in some newer Regions. The burst "is not a quota that a customer can control or request changes to".
• The order of the limits. Limits apply in order: per client or per method in a usage plan, per method in a stage, the account, the AWS Region. Per-client limits "can't be higher than the per-account limits".
• Usage plans. A usage plan's throttling rate is "the rate … that tokens are added to the token bucket" and its burst is "the capacity of the token bucket". Its quotas are per DAY, WEEK or MONTH. Usage-plan throttling and quotas "are not hard limits, and are applied on a best-effort basis". AWS also says: "Don't use API keys for authentication or authorization".
• HTTP APIs. HTTP APIs have route-level throttling and no usage plans.
• The response. Throttled clients "may receive 429 Too Many Requests".
• What it does not have. No weights (one token per request) and no limit across Regions.

AWS WAF (rate-based rules). What AWS documents:

• The window and the limit. The evaluation window is 60, 120, 300 or 600 s, "and 300 (5 minutes) is the default". The limit is 10 to 2,000,000,000 per window.
• The precision. "AWS WAF checks the rate about every 10 seconds". "It's not intended for precise request-rate limiting". It "gives more importance to more recent requests".
• The delay before it acts. "Usually, this delay is below 30 seconds" on one page, and "Usually 30-50 seconds. Can be up to several minutes" on another.
• The keys. The source IP (default), an IP in a header, the ASN, all requests (with a scope-down statement), or up to 5 custom keys. The ASN is the number of the network the request comes from. A custom key is a header, cookie, query argument, query string, URI path, JA3 or JA4 fingerprint, HTTP method, IP or label namespace.
• The number of IPs. "The maximum number of IP addresses that AWS WAF can rate limit using a single rate-based rule instance is 10,000."
• Changing a rule. Changing a rate setting "resets the rule's rate limiting counts".
• The actions. Block, Count, CAPTCHA or Challenge. Block answers 403 (Forbidden) by default, and a custom response may use 429.
• Bot Control. Bot Control's targeted rules add their own token-based rate limiting.

Amazon CloudFront. What AWS documents:

• "Rate limiting" is among a distribution's security protections. "CloudFront always enables rate limiting in monitor mode" until you choose to block. It is offered for custom (non-S3) origins.
• CloudFront itself keeps no count per client. The rule is a WAF rule.

Amazon ElastiCache (Valkey or Redis OSS). What AWS documents:

• EVAL, EVALSHA, SCRIPT LOAD and TIME are supported, on serverless caches too.
• A script runs atomically. In cluster mode its keys must share one slot (hash tags).
• Multi-AZ failover: writes "can resume as soon as the promotion process is complete, typically just a few seconds".
• Global Datastore: "A secondary cluster only accepts read requests", and replication is asynchronous.
• MODULE is not a supported command, so modules such as redis-cell can't be loaded.

Amazon DynamoDB. What AWS documents:

• Per partition, "maximum capacity of 3,000 read units per second and 1,000 write units per second".
• Atomic counters are "not idempotent".
• TTL deletes expired items within a few days, so readers filter them.
• Conditions can't read the server's time.

DynamoDB is good for rules and billed totals, and poor for a check on every request (DynamoDB as the limiter's store).

Running it yourself

The table lists three ways to run a limiter on your own instances. The facts for each one, and the sizing, follow the table.

Envoy on Amazon EC2 or Amazon EKS.

• The local filter. It is a token bucket, "applied per Envoy process" by default. local_cluster_rate_limit divides the limit so the whole gateway enforces X a second "regardless of how N changes" (without it, "N * X"). It refuses with 429 and x-envoy-ratelimited, optionally Retry-After.
• The global filter. It makes one gRPC call per request, with a 20 ms timeout by default. failure_mode_deny is false by default (fail open). The filter answers 500 by default when it is set.
• The global service. It counts fixed windows (per second, minute, hour, day, and month). Each window is keyed by the window's start from the service's own clock, and counted with pipelined INCRBY and EXPIRE.
• Its options. Its local cache of over-limit keys is off by default. near_limit fires at 80% by default. shadow_mode and hits_addend (weights) exist.

NGINX on EC2.

• "The limitation is done using the 'leaky bucket' method".
• burst is 0 by default. With a burst, excess requests are delayed. nodelay or delay= change that.
• It refuses with 503 by default.
• It keeps 128 bytes per state on 64-bit. The least recently used state is removed when the zone is full.
• It has limit_req_dry_run.
• Each node counts alone. The commercial NGINX Plus can synchronize the zone between nodes (the sync parameter), by sending updates between them.

Redis or Valkey on EC2, with redis-cell.

• CL.THROTTLE <key> <max_burst> <count per period> <period> [<quantity>] returns allowed, the total limit (max_burst + 1), remaining, retry after and reset after.
• For b = 20 pass max_burst 19.
• Its README marks it "best effort" maintenance.
• It is not available on ElastiCache (no modules).

Sizing in words.

• Memory. About 96 bytes a key for a token bucket (the rate limiter loop's estimate, to measure) × active keys, with no eviction.
• CPU. About 60,000 small-script calls a second per node is the rate limiter loop's assumption. Load-test it, and plan shards for calls and nodes for memory.
• Nodes. Steady-CPU nodes, not burstable ones.
• Alarms. Alarms on the limiter's own latency, on every decision made without the store, and on evictions.

Look-alikes that are not this mechanism

These AWS features look like a rate limiter and are not one. For each, the table says why it looks like one and why it isn't.

---

Senior checkpoint

This checkpoint tests the Senior level with one question and its model answer.

Check yourself: Senior

Why can't more shards help one key, and what does leasing a block bound?

What breaks: every request, refused or not, is a script call on the one shard holding the tenant's key. That is 100,000 calls a second, and every other key on that shard waits. More shards don't split one key.

What to change: lease blocks of about 0.25 s of each gateway's share, granted whole or not at all. The gateway spends locally. It refuses locally once a denied lease tells it to wait one block cycle. It gives unused tokens back at expiry. Calls fall to about 150 a second.

What it costs:

• a bounded overshoot, at most gateways × 1.2 × block tokens.
• some undershoot from stranded tokens.
• a lease lifecycle to get right.

On AWS No service on this page leases tokens, so leasing runs in your gateways on EC2 or EKS, in front of ElastiCache.

---

Architect: what the whole system promises

This level asks what the whole system promises. It covers one limit across three Regions, a Region that is lost, a billing quota, an attack spread over many addresses and a slow backend. It ends with the choice between AWS's limiters and your own, and what each costs. It matches Round 3 of the rate limiter loop, steps 3.1 to 3.6.

The problem: one Thursday in three Regions

This section describes the failure class of the Architect level: every Region works as designed, and a promise that spans all three Regions still breaks. k-big pays for 10,000 requests a second in total. After a Region is lost, it gets 7,800.

Basketly now runs the Partner API in three AWS Regions. This page calls them A, B and C. Each Region runs the whole Senior design on its own: 20 gateways, a central store, leases for hot keys and a WAF rule at the edge. No request waits for another Region.

k-big is one of Basketly's partners. Its batch jobs go to a separate catalog service in each Region, not to orders.

k-big's contract changes. It is now 10,000 a second in total, across all three Regions, with a burst of 20,000. It is no longer 10,000 in each Region.

k-big's batch jobs send 12,000 a second in total, 20% more than the contract, so the limit decides. They send 7,200 a second to A, 3,600 to B and 1,200 to C.

1. Before coordination. Each Region enforces the full 10,000 on its own. Each Region receives less than 10,000, so each admits all it receives. k-big gets 7,200 + 3,600 + 1,200 = 12,000 a second, which is 2,000 over its contract. Three Regions without coordination could admit up to 3 × 10,000 = 30,000 a second. That is only the ceiling, reached if k-big sent 10,000 to each Region.
2. With shares. Each Region enforces a share of the 10,000. k-big then gets close to its contract. One limit, three Regions shows how the shares are set and moved.
3. 14:00:00, the demand moves. k-big's traffic in C grows from 1,200 to 7,200 a second. The demands are now 7,200 in A, 3,600 in B and 7,200 in C, 18,000 in all. The shares follow demand: each Region keeps a floor of 500, and the other 8,500 is split by demand. So within about 18 s A's share falls from 5,600 to 500 + 8,500 × 7,200 ÷ 18,000 = 3,900, B's falls from 3,050 to 500 + 8,500 × 3,600 ÷ 18,000 = 2,200, and C's grows from 1,350 to 3,900. What run G shows follows this move step by step.
4. 14:05:00, Region B is lost. At that moment B holds 2,200 a second of k-big's limit. The other two Regions cannot know whether B is gone or only silent. If they keep reserving B's 2,200 a second, k-big gets at most 10,000 − 2,200 = 7,800 a second. That is 22% under the contract it pays for.

The diagram shows the three Regions at 13:59, with shares in place.

Synthesizing vector architecture diagram...

1. Each Region holds a share of the 10,000 and measures its demand, the requests it receives for k-big. At 13:59 the shares are 5,600, 3,050 and 1,350, and the demands are 7,200, 3,600 and 1,200.
2. A and B receive more than their shares, so each admits its share. C receives less than its share, so it admits all 1,200.
3. The dashed arrows go to the share records, off the request path. Every 5 s each Region writes its own record and reads the others'.

So k-big gets 5,600 + 3,050 + 1,200 = 9,850 a second. One limit, three Regions derives the shares.

---

One limit, three Regions

This section shows how one limit can hold across three Regions without a cross-Region call on every request.

Without coordination, the three Regions admit all of k-big's 12,000 a second against a contract of 10,000. The limiter can't make a cross-Region call on every request. A central counter in one Region would put a cross-Region round trip on every request. It would also make that Region a dependency of every other Region. Without a cross-Region call on each request, no design has all three of these properties. The first is that each Region can admit up to the whole limit. The second is that the Regions together never admit more than the limit. The third is that no Region waits for another. A Region learns what the others admitted only seconds later. So the design must choose its error. This page chooses to admit too little while shares move, and to stay within the contract's burst + rate × time.

Shares that follow demand

Each Region enforces a share of the limit, with the mechanisms this page has shown so far. The shares follow recent usage. Each share has a floor, a minimum, so that an idle Region can still serve a sudden burst.

For k-big the shares work like this:

• Each Region's bucket for k-big refills at its share and holds a burst of 2 seconds of its share. While the shares add up to at most 10,000, the three bursts add up to at most 20,000, k-big's burst.
• A share change is a rule change. The share is an argument to the script, so the tokens are clamped, never reset (Changing a rule).

Shares follow demand, not admissions. Each Region measures the requests it received for k-big over its last 5 s, allowed or refused. This page calls that the Region's demand. A share computed from admissions could never grow, because a Region never admits more than its share.

The target. This page chooses this rule for each Region's target share. Each live Region gets a floor of 5% of the limit, 500 a second. The rest, 10,000 − 3 × 500 = 8,500, is split in proportion to the Regions' demands.

At 13:59 the demands are 7,200, 3,600 and 1,200: 60%, 30% and 10% of 12,000. So the targets are:

• A: 500 + 8,500 × 0.6 = 5,600
• B: 500 + 8,500 × 0.3 = 3,050
• C: 500 + 8,500 × 0.1 = 1,350

k-big then gets 5,600 + 3,050 + 1,200 = 9,850 a second, not 10,000. C's floor gives C 150 more than C's demand uses. That is the floor's price.

Side row 8r uses the numbers from step 3.1 of the rate limiter loop. The loop's numbers, L = 1,000 a second with a floor of 50 for each Region, give 560, 305 and 135.

The table gives the three shares.

Moving room by named grants

Regions compute their shares from views that are a second or more apart. So if each Region simply took its new target, the shares could briefly add up to more than L.

The ad-click loop moves the shares by handoff (step 3.2 of the ad-click loop). A Region may lower its share at any time. It may raise its share only into budget that another Region has already published as released. Each Region writes only its own record, so nothing conflicts.

Every 5 s each Region writes one record, its own. The record holds four things:

• its demand;
• its share;
• its unmet need, which is its target minus its share;
• the room it has granted to each other Region so far.

Each Region reads the other Regions' records from its local copy.

This page makes "released" precise with named grants. A grant is room that one Region hands to another Region by name. At its own rebalance, every 5 s, a Region does four things in order:

1. It takes the room that other Regions have granted to it by name, and that it has not taken before, into its own pool of free room.
2. If its target is lower than its share, it lowers its share at once and adds the difference to its pool.
3. If its target is higher, it raises its share from its pool only, by at most 1,000 a second (10% of the limit) per rebalance.
4. It grants what is left in its pool to the other Regions by name, in proportion to the unmet needs they last published, never more than the unmet need that Region published. If no other Region has published an unmet need, it keeps the room in its pool.

Room moves only from one named Region to another. So the shares, the pools and the grants not yet taken always add up to exactly 10,000. The sum of shares can never be more than the limit. Run G, below, checks this at every 10 ms step.

Why a simpler rule for taking room fails. Suppose each Region that raises took part of the released room, in proportion to the unmet needs it can see. Two Regions that raise at the same instant would each see the other's old unmet need. Both would take the same room, and the sum of shares would pass the limit. A named grant goes to one Region only, so it cannot be taken twice.

The diagram follows the first moves after C's demand rises at 14:00:00, in run G.

Synthesizing vector architecture diagram...

C's demand at 14:00:03.3 is an average over the last 5 s: (1.7 × 1,200 + 3.3 × 7,200) ÷ 5 = 5,160. A's target at 14:00:05 is 500 + 8,500 × 7,200 ÷ (7,200 + 3,600 + 5,160) ≈ 4,335.

What run G shows

Run G is a model of k-big's shares, in steps of 10 ms. It is a fluid model: it treats requests as a smooth flow, because k-big's rates are too high to follow one request at a time. Its settings, which are choices:

• Each Region rebalances every 5 s: A at :00.0, B at :01.7 and C at :03.3 of each 5 s.
• A record written at one instant is visible to the other Regions 1 s later.
• The demand in each Region is constant between changes.

Event G1. At 14:00:00 C's demand rises from 1,200 to 7,200. The demands now total 7,200 + 3,600 + 7,200 = 18,000. The new targets are 500 + 8,500 × 0.4 = 3,900 for A, 500 + 8,500 × 0.2 = 2,200 for B, and 3,900 for C.

The table compares two designs on the same demand and the same rebalance times. In the first, each Region sets its share to its new target at once. In the second, room moves by named grants.

Each row needs a few words.

• Highest sum. At 14:00:03.3 C jumps to 500 + 8,500 × 5,160 ÷ 15,960 ≈ 3,248. A and B still see C's old demand and keep 5,600 and 3,050. So the sum is 5,600 + 3,050 + 3,248 = 11,898. If all three Regions rebalance at the same instants, the sum is 5,600 + 3,050 + 3,900 = 12,550 for 5 s.
• Lowest sum. With named grants, A and B lower first, and C raises only when their grants reach it. From 14:00:06.7 to 14:00:08.3 the sum is 4,335 + 2,417 + 1,350 = 8,102. With all three at the same instants, it dips to 7,450 and settles after 25 s.
• Share-seconds below 10,000. This is how far the sum of shares stays under the limit, added up over time. 1,000 a second below the limit for 2 s is 2,000 share-seconds.
• Admitted above 10,000. C had been under its share, so its bucket was full: 2 × 1,350 = 2,700 tokens. In both designs C spends them in the first 0.46 s, on top of the shares. That gives 2,700 above the limit in each design. The design without grants adds 8,480 − 2,700 = 5,780 more, from shares that add up to more than 10,000.

Both designs admit 5,600 + 3,050 + 1,350 + 2,700 = 12,700 in the busiest second, 14:00:00 to 14:00:01, because of C's banked tokens.

The handoff turns a short overshoot into a short undershoot.

The chart shows the sum of the three shares at each whole second, from 14:00:00 to 14:00:30.

Synthesizing vector architecture diagram...

1. The line that rises above 10,000 is the design where each Region jumps to its target. It reaches 11,898 at second 4, when C has jumped and A and B have not yet seen C's new demand. It returns to 10,000 by second 12.
2. The line that falls below 10,000 is the design with named grants. A lowers at second 5 and B at second 7, so the sum falls to 8,102. C raises at seconds 9, 14 and 19 as the grants reach it, and the sum is back at 10,000 from second 19.

So the first design runs above the contract for seconds, and the second runs below it for seconds.

Event G1c. This run is the hardest case for the claim rule: two Regions raise at the same instant. From 14:00:00, A's demand falls to 1,200 while B's and C's rise to 7,200. All three Regions rebalance at the same instants.

• The run checks the sum of shares at every 10 ms step. It never passes 10,000.
• The new targets are 500 + 8,500 × 1,200 ÷ 15,600 ≈ 1,154 for A, and 500 + 8,500 × 7,200 ÷ 15,600 ≈ 4,423 for B and for C.
• Every share is within 1% of its target after 30 s. On the way, the sum of shares dips to 5,554, because A lowers by more than B and C may raise at once.

A wider search tried the three rebalance times in all 27 combinations, with both demand changes. The sum of shares never passed 10,000.

What the sum of shares bounds

The sum of shares bounds the rate the Regions admit, not each second's admissions. A Region that was under its share has banked tokens: C held 2 × 1,350 = 2,700 at 14:00. C spends them on top of its share. So admissions passed 10,000 in one second, 12,700, even with named grants.

The contract still holds. It allows at most b + L × t in any interval of t seconds: 20,000 + 10,000 × t. While the shares add up to at most 10,000, the bursts add up to at most 20,000. In run G, with named grants, the largest excess of admissions over 10,000 × t in any interval was 2,700, far under 20,000.

The design without grants breaks the contract in two ways:

• The regional bursts follow the shares. While the shares add up to 12,550, the bursts add up to 2 × 12,550 = 25,100, more than 20,000.
• An excess that lasts long enough uses up the 20,000. In run G1 the excess stays short: its largest was 8,480, and 15,450 with all three Regions at the same instants. When a Region is lost shows a case where it lasts.

Leases inside each Region add their own overshoot (A key too hot for one shard).

Security limits across Regions

A login limit of 5 a minute per account, enforced in each of three Regions, allows 3 × 5 = 15 a minute. There are two choices:

• Keep each account's security limit in one home Region, and send that account's login checks there. This is the one exception to "no cross-Region call on the request path", and it is on one route.
• Give each Region 5 ÷ 3 a minute, and accept a lower limit for an honest user who stays in one Region.

Alarm on a Region's share record that stops changing, and on a sum of computed shares above the limit. A rate limit is not a billing quota adds the alarms for metering.

Why one counter that every Region writes fails

A DynamoDB global table fails as the shared counter too. Its default mode is called multi-Region eventual consistency (MREC). When two Regions write the same item at about the same time, DynamoDB keeps only one of the two writes. AWS calls this "last writer wins". A condition is checked only against the local copy: "Conditional writes evaluate the condition expression against the version of the item in the Region." Suppose Regions A and C each read 5,000 tokens and each write back 4,999. One of the two decrements is lost.

Its other mode, multi-Region strong consistency (MRSC), checks conditions against the latest version of the item. It is a poor fit for a limiter. It runs in exactly three Regions (three replicas, or two replicas and a witness). Each write waits until at least one other Region has it, so every admission would pay a round trip between Regions, and this design avoids that round trip. And MRSC does not support TTL, so idle buckets would never expire.

---

When a Region is lost

This section shows what the other Regions do with a lost Region's share, and what each choice lets through.

At 14:05:00 Region B is lost. It held 2,200 a second of k-big's 10,000 at that moment. With named grants, only B can grant its room, and B can no longer publish anything.

When a Region is lost, its share is frozen or handed out again (step 3.5 of the rate limiter loop). Multi-Region Failover covers the failover itself.

Three rules for a silent Region

Freeze. The survivors keep counting B's last published share as taken. They never admit too much. They admit too little, by B's share, for as long as B is gone.

Reclaim on two signals. A survivor treats B's share as free only when two signals agree:

• B's record has not changed for 3 of the survivor's own rebalances, which is 15 s on the survivor's own clock;
• an outside health check reports B unhealthy.

Then the survivors split B's last published share in halves. Both survivors apply this fixed rule in the same way, so no room is taken twice. After that, room moves by named grants, as before. The targets now cover two live Regions: a floor of 500 each, and the rest, 9,000, by demand.

A Region that is cut off, not lost. Suppose B is up and still enforces its share, but no record crosses between B and the others. A survivor that reclaims on silence alone adds B's room to its own. B sees A and C silent, and reclaims their room too. So the sum of shares goes above the limit. The outside health check still reaches B and reports it healthy, so the two-signal rule does not reclaim.

Coming back. A returning Region starts with a share of 0, and raises it only with room granted to it by name. The survivors include it in their targets once its record is fresh again. This page does not simulate a return.

Traffic itself moves between Regions by DNS and health checks, in the section Moving the users of Multi-Region Failover. Step 3.5 of the rate limiter loop sizes the survivors. Section R3.8 of the rate limiter loop makes a different choice for the cut-off case. It first keeps the last shares. After 60 s without sync, it lets each Region grow toward its own measured demand, one step per rebalance, for capacity limits only.

Run G2: Region B is lost

Event G2 continues run G1. B is lost at 14:05:00.000, holding 2,200. B's clients' 3,600 a second fail until 14:06:00. Then they arrive in A, so A's demand becomes 7,200 + 3,600 = 10,800, and C's stays 7,200. This move is a simplification of the model.

The health check reports B unhealthy from 14:05:30. That is an assumption, for example 3 failed checks 10 s apart.

The table gives k-big's admitted rate under each rule, for a lost B and for a B that is only cut off.

Freeze. k-big gets at most 10,000 − 2,200 = 7,800 a second, 22% under its contract. It stays at 7,800 after B's clients reach A at 14:06:00, apart from a dip to about 7,233 between 14:06:08.3 and 14:06:10, while C's grant reaches A. B's 2,200 stays taken.

Two signals. A sees B's record unchanged for 3 rebalances at 14:05:15, and C at 14:05:13.3. The health check fails from 14:05:30. So A reclaims at its rebalance at 14:05:30 and C at 14:05:33.3, each taking 1,100. Each raises by at most 1,000 per rebalance.

The targets are 500 + 9,000 × 0.5 = 5,000 for each, because A's and C's demands are both 7,200. Both shares are within 1% of 5,000 at 14:05:38.3, and k-big gets 10,000 from 14:05:39.

At 14:06:00 B's clients arrive in A. The targets become 500 + 9,000 × 0.6 = 5,900 for A and 500 + 9,000 × 0.4 = 4,100 for C. C lowers at 14:06:08.3 and grants 900 to A, which takes it at 14:06:10. For those 1.7 s the sum is 9,100. From 14:06:10, k-big gets 10,000 again.

Cut off, silence alone. B reclaims A's 3,900 at 14:05:11.7 and C's 3,900 at 14:05:16.7, each after 3 unchanged records. In this model B divides by the Regions on its side of the cut, which is B alone. C takes half of B's 2,200 at 14:05:13.3, and A at 14:05:15. B keeps admitting up to its demand of 3,600. A and C rise to 5,000 each.

From 14:05:20 k-big gets 5,000 + 5,000 + 3,600 = 13,600 a second, 36% over its contract, for as long as the cut lasts. The sum of shares reaches 20,000 by 14:06:00, because B believes it is alone and raises toward the whole 10,000. That peak depends on how B divides the silent shares: if every Region divided a silent share by 2, the sum would peak at 16,100. The admissions of 13,600 and the break below are the same either way, because B only ever uses its demand of 3,600.

At the full excess of 3,600 a second, the contract's 20,000 lasts 20,000 ÷ 3,600 ≈ 5.6 s. In the run the excess builds up while the shares rise. Measured from 14:05:11.70, the admissions pass 10,000 × t + 20,000 at 14:05:19.58. From then on the contract is broken.

Cut off, two signals. The health check passes, so nobody reclaims. k-big stays at 10,000.

The diagram puts the three outcomes side by side.

Synthesizing vector architecture diagram...

1. In "Freeze", A and C keep their 3,900 each and count B's 2,200 as taken. k-big gets 7,800 a second, under the contract, for as long as B stays frozen.
2. In "Reclaim on two signals", B's record has been silent for 15 s and the health check fails. A and C each take half of B's 2,200 and settle at 5,000 each. k-big gets 10,000.
3. In "Reclaim on silence alone, B cut off", B is alive. A and C take B's room, and B takes A's and C's room. B keeps using 3,600, so k-big gets 13,600, over the contract.

Only the two-signal rule gives 10,000 when B is lost and 10,000 when B is cut off.

---

A rate limit is not a billing quota

This section shows limits counted over a day or a month, and why an invoice needs its own count.

At month end FreshBox asks for its usage, for its invoice. The limiter cannot answer, and this section shows what can.

Per second and per day

A request can hit limits of different lengths. k-7 also has a quota of 100,000 requests a day.

Event 26. At its full rate of 10 a second, k-7 would use 10 × 86,400 = 864,000 a day. So the daily quota starts refusing after 100,000 ÷ 10 = 10,000 s ≈ 2.8 hours.

A per-day or per-month quota is a fixed calendar window on purpose. The customer's day or the billing month really does reset at midnight.

Step 2.6 of the notification loop caps messages per user's local day with one INCR per day.

Quotas that bill

A limiter's counts are the wrong source for an invoice. A limiter's buckets:

• refill.
• expire.
• are evicted.
• overshoot with leases.
• fail open during outages.

That is acceptable for telling a client to slow down. It is wrong for billing.

Step 3.2 of the rate limiter loop counts billed usage in a separate metering pipeline: a stream, deduplication and absolute totals. The limiter only reads a "near" or "over" flag from it.

Amazon API Gateway says the same about its own usage plans. Their throttling and quotas "are not hard limits, and are applied on a best-effort basis" (On AWS).

Limits set by an outside provider can have two layers, and the same check applies to them. Stripe limits each account, at 100 live requests a second. It also limits each endpoint, at 25 a second unless noted. It tells you which one you hit in a Stripe-Rate-Limited-Reason header.

Step 2.3 of the crowdfunding loop keeps one bucket for each and checks both in one call.

A bucket is not a count

The page's own runs show three reasons why a bucket cannot produce an invoice:

• After the storm, k-7's plan bucket is full again by 09:03, at 20 tokens (Several limits on one request). It would hold the same 20 tokens if FreshBox had made 1,219 requests, or none.
• While the store was down, fail open admitted 4,840 of k-7's requests (Three failure policies, event 17). None of them reached the store. Under the local share, the 140 of event 19 never reached it either.
• A leased block is charged to the bucket when it is leased, not when it is spent. In event 23, the gateways gave 113 unspent tokens back at expiry (The overshoot of leasing and its bound).

So an invoice needs a separate count of admitted requests. Each gateway makes that count, whatever decided the request. This page calls it metering: counting each admitted request for billing.

Counting each admitted request once

Each gateway sends a usage record every 5 s. With 20 gateways that is 20 ÷ 5 = 4 records a second in each Region, whatever the request rate.

Event 32. During replay F with fail open, each gateway receives 20 of k-7's requests a second and admits all of them. So gateway G4's record for 09:01:05 to 09:01:10 says k-7: 100, from 20 × 5.

Suppose the record is delivered twice. A total built by adding each record's count says 200.

So let each record carry G4's running total for k-7, not only the last 5 s. Store one total per gateway and key, and write a new total only if it is larger than the stored one. The duplicate carries the same total, so it changes nothing.

The diagram shows the duplicate under both ways of counting.

Synthesizing vector architecture diagram...

A gateway that crashes. Suppose G4 crashes just before that flush. Its unflushed counts never get a record. A restarted gateway is a new identity, so its sequence numbers start again and show no gap. What shows that a crash happened is an identity that ended without a clean end record. The amount lost is unknown, at most 5 s of that gateway's admissions. Here that is at most 100 of k-7's requests. It is an under-bill, never an over-bill.

The sections Idempotent by design: absolute writes and conditions on the durable record and Streams: exactly-once state plus idempotent sinks of Idempotency & Effectively-Once Processing build such writes in general. Step 3.2 of the rate limiter loop builds the whole pipeline.

Alarm on metering lag, and on gateway identities that end without a clean end record.

How late a quota is enforced

The limiter does not count the quota. It reads a "near" or "over" flag that the metering side sets. Our settings are choices:

• each gateway flushes its records every 5 s;
• a key's total is written every 5 s once it passes 80% of its quota;
• each gateway reads the flags every 1 s.

Event 33. The flag then arrives up to about 5 + 5 + 1 = 11 s after the request that crossed the quota. That does not count the time the record spends in the stream and in the job that adds the records up.

At k-7's contract of 10 a second, up to about 11 × 10 = 110 requests pass after its daily 100,000. That is 0.11%. If the store is down and the gateways fail open, k-7 sends 400 a second, and up to about 400 × 11 = 4,400 pass before the flag arrives. Across Regions, add the time to replicate the record.

---

An attack spread over many addresses

This section shows an attack in which every count stays under its limit.

Basketly's shopper login, POST /login, has the security limit that the Mid-level used: 5 attempts a minute per account (Security limits with more servers than the limit). Normal login traffic is 20 a second.

Event 34. An attacker runs credential stuffing. OWASP defines it as "the automated injection of stolen username and password pairs ("credentials") in to website login forms, in order to fraudulently gain access to user accounts". The pairs leak from other sites, and the attacker hopes that people reuse their passwords.

The attacker uses 4,800 addresses. Each address sends one attempt every 2 minutes, and each attempt uses a different leaked pair. These numbers are assumptions of this page.

• In total, that is 4,800 ÷ 120 s = 40 attempts a second.
• From each address, that is 600 s ÷ 120 s = 5 attempts in 10 minutes.

The table shows what each limit sees.

The last row needs a sentence. A cap of 30 a second on the route refuses half of the 60 attempts, and it refuses honest logins in the same proportion as the attacker's.

The attacker controls how its attempts spread. So it can keep every count that it can spread below its limit. The one count it cannot spread, the route's total, also holds every honest login. A defence has to use something that stays the same across the attacker's 4,800 addresses.

A distributed attack is many IPs that each stay under every limit. That is a detection problem, not a counting one. Step 3.3 of the rate limiter loop and the bot-defense case study cover it. The bot-defense case study's step 2.1, IPs Rotate Endlessly, and step 3.2, Credential Stuffing on Login, build those signals. The broader primitive Bot Defense, Sybil Resistance & Registration Abuse surveys them.

The diagram shows the four counts the attack passes through.

Synthesizing vector architecture diagram...

---

A slow backend when every client is under its limit

This section shows a backend that is overloaded while every client stays within its contract.

Event 35. Region A's orders service runs 80 workers, and each request takes 100 ms. So it serves 80 ÷ 0.1 = 800 a second, the figure this page has used for orders. Its database slows, and each request now takes 250 ms. Now orders can serve 80 ÷ 0.25 = 320 a second. The 80 workers and the slowdown are assumptions of this page.

k-big's batch traffic goes to the separate catalog service, so it does not reach orders. The partners keep sending 700 order calls a second: 695 from the other partners and k-7's normal 5. Every call is within its contract, so every limiter allows it.

Little's law says that the requests in flight equal the arrival rate times the time each request takes. The section Little's law of Retries, Timeouts, Backpressure & Load Shedding derives it.

• At 700 a second and 0.25 s each, 700 × 0.25 = 175 requests would need to be in flight, against 80 workers.
• The queue grows by 700 − 320 = 380 a second.
• After 10 s, 380 × 10 = 3,800 requests wait, and a new request waits about 3,800 ÷ 320 ≈ 11.9 s.

The limiter cannot see this. Each limiter counts one client's requests against that client's contract. None of them sees how long orders takes. Only orders itself, or its proxy, sees its own latency and the requests in flight.

Protecting a slow backend is load shedding, not rate limiting. Load shedding refuses by the service's own health (Rate limit, quota, shedding). Retries, Timeouts, Backpressure & Load Shedding builds it. Its sections Backpressure: stock protects itself, Bulkheads and concurrency limits and Limits that adapt cover 503 with Retry-After, caps on requests in flight, and limits that follow latency. Step 3.4 of the rate limiter loop designs it for the loop's system.

The diagram follows the order calls from the partners to the queue.

Synthesizing vector architecture diagram...

---

Build on AWS's limiters or your own

This section compares AWS's two managed limiters with a limiter you build on ElastiCache, on equal terms.

API Gateway, WAF and a limiter you build, on equal terms

The next table compares the two managed limiters with a limiter you build, row by row.

The account throttle is a shared limit. Every REST, HTTP and WebSocket API in the account and Region draws from the same 10,000 a second. So one API with heavy traffic can use up that limit and cause the other APIs to be throttled. No usage plan can raise a client above it.

A WAF rule's count is shared by everyone behind one IP, as event 30 showed in One request, end to end. One rule can limit at most 10,000 IPs at once.

What each mechanism costs

Each mechanism does a different amount of work for each request it admits. The table measures that work on this page's own examples.

The arithmetic behind the table:

• Central bucket. 400 ÷ 10 = 40 store calls for each admitted request, because refused requests cost a call too.
• Leased blocks. 148 ÷ 10,000 ≈ 0.015 calls for each admitted request.
• WAF rule. From 09:00:00 to 09:03:30 the rule inspects every request from FreshBox's address: the storm's 48,000, k-7's 450 after the storm (5 a second for 90 s), and k-8's 20 × 210 = 4,200. That is 52,650. It blocks 32,000 + 450 + 3,400 = 35,850 of them, and each blocked request is inspected and billed too.

One month of Region A's edge, in dollars. Region A's edge inspects the partners' order calls, 700 a second, and k-big's batch traffic in A, 7,200 a second. That is 7,900 a second. In a 730-hour month that is 7,900 × 3,600 × 730 = 20,761,200,000 requests.

• AWS WAF lists USD 0.60 per million requests in us-east-1, for web ACLs within the default capacity. Web ACLs that use more capacity units pay more per million.
• So the requests cost 20,761.2 × USD 0.60 ≈ USD 12,457 a month. The web ACL adds USD 5 a month, and each rule USD 1 a month.
• This price assumes no AWS Shield Advanced. Shield Advanced costs USD 3,000 a month. With it, the price list charges nothing for the first 50 billion WAF requests a month for protected resources, and USD 0.15 per million above them. This month's 20.8 billion requests would fit in the 50 billion.

The limiter's store, for comparison, is one primary and one replica. Each is a cache.m7g.large Valkey node at USD 0.1264 an hour in us-east-1. That is 2 × 0.1264 × 730 ≈ USD 185 a month, whatever the request rate, until the calls need another shard.

Prices are AWS list prices for us-east-1, on demand, checked on 2 October 2026. ElastiCache nodes are priced on the Valkey engine. Redis OSS nodes cost 25% more: cache.m7g.large is USD 0.1264 an hour on Valkey and USD 0.158 on Redis OSS. Prices change, so recompute them before you rely on them.

The edge's cost grows with every request it inspects. The limiter's cost grows mainly with the number of store nodes.

---

Where the loop designs each decision

This section links each decision of this level to the step of the loop that applies it to the loop's own system.

The broader primitives API Gateway & Reverse Proxy and Bot Defense, Sybil Resistance & Registration Abuse cover the layers around the limiter.

The loop designs each decision in one step:

• Step 3.1 of the rate limiter loop: one global limit across three Regions. The mechanism: One limit, three Regions.
• Step 3.2 of the rate limiter loop: monthly quotas that must bill correctly. The mechanism: A rate limit is not a billing quota.
• Step 3.3 of the rate limiter loop: an attack from many IPs, each under every limit. The mechanism: An attack spread over many addresses.
• Step 3.4 of the rate limiter loop: a slow backend while nobody is over their limit. The mechanism: A slow backend when every client is under its limit.
• Step 3.5 of the rate limiter loop: a Region that is gone. The mechanism: When a Region is lost.
• Step 3.6 of the rate limiter loop: whether to build the limiter at all. The mechanism: Build on AWS's limiters or your own.

---

Architect checkpoint

This checkpoint tests the Architect level with three questions and their model answers.

Check yourself: Architect

What do API Gateway's and WAF's own documents promise about precision, and what does each send by default?

Both are approximate by design.

• API Gateway. Its throttles and quotas are "best-effort … targets rather than guaranteed request ceilings". It has one token per request, no weights, and it works per Region. Its account limit (10,000 a second, burst 5,000 by default) is shared by all your APIs. It sends 429.
• WAF. Its rate rules are "not intended for precise request-rate limiting". They check about every 10 s and act tens of seconds late. They key on IPs and a few request fields. They block with 403 unless you set a custom 429.

Use WAF against floods at the edge, and API Gateway where its targets are good enough. Build your own limiter where you need exact, weighted, per-tenant limits.

What is the accuracy target for each mechanism?

The table gives each mechanism's accuracy, the direction in which it errs, and where this page shows it.

Three sentences sum the table up. Be exact where money depends on it, as in billing, or where the contract is sold, as with the central bucket. Be bounded where capacity is protected, with shares, leases and local shares, and approximate at the edge, where speed and cost matter more. Keep security limits conservative: never leased, never failing open.

Load shedding makes no promise to any client. It protects the service (A slow backend when every client is under its limit).

Why does a Region that is cut off but alive differ from one that is lost, and what does each reclaim rule admit?

A lost Region admits nothing, while a cut-off Region keeps enforcing its own share. From outside, both look silent. Run G2 gives the four results for k-big's contract of 10,000 a second:

• B lost, survivors freeze its share: 7,800 a second.
• B lost, survivors reclaim on two signals: 10,000 a second from 14:05:39.
• B cut off, every Region reclaims on silence alone: up to 13,600 a second. Measured from 14:05:11.70, the contract is broken at 14:05:19.58.
• B cut off, two signals: 10,000 a second, because the health check still passes.

On AWS The second signal can be an Amazon Route 53 health check on each Region's endpoint, read through its HealthCheckStatus metric in CloudWatch. Route 53 publishes this metric only in US East (N. Virginia), so each Region reads it from there.

---

Reference

This section returns to the opening problem and says how each part of the page solved it. Then it gives the page's reference material: the snapshots, the costs, every event, a cheat card, a failure checklist and the words we use. It ends with where to go next.

Back to FreshBox

As shipped, twenty gateways each enforced k-7's contract correctly and admitted 200 a second between them. That was 24,380 requests in two minutes against a contract of 1,220. orders received 895 a second, against the 800 it can take.

With one central token bucket in one atomic script, k-7 got 1,219: its burst of 20, then 10 a second. orders stayed at 705.

In general, a rate limit is one count of one key over time. A count per minute keeps only one number, so it lets a whole minute's budget through at once. A token bucket keeps both numbers of the contract, the rate and the burst. Each check is one atomic step, which means no other check can run in the middle of it, and each check reads one clock, the store's. And we decide in advance what a gateway does when the store can't answer.

Everything else on this page changes what is counted and which requests are refused:

• keys and memory;
• hot keys, meaning single keys that receive more checks than one store node can handle;
• several limits on one request;
• response headers;
• the edge and the managed limiters.

We must also choose a burst size and be able to defend it.

Here is what each piece did:

• Two numbers and a key let the 15-call page load through and told us what "600 a minute" really promises. Section: A limit is two numbers and a key.
• Knowing what windows count ruled out a fixed window that spent the minute in 1.5 s and allowed 1,200 in two seconds at its edge. Section: Counting in windows.
• A token bucket, or GCRA, bounded every interval to burst + rate × time: 29 in any second, 619 in any minute. Section: The token bucket.
• One count instead of twenty stopped the fleet from admitting 20 times the limit. Exact shares stayed ready as the fallback. Section: Twenty servers, one limit.
• One atomic script with the store's clock let 5 of 15 calls that arrived at the same instant through instead of 15. It also stopped a fast clock from admitting all 48,000. Section: One atomic step, one clock.
• The right key and a TTL of at least b ÷ r kept 40 accounts from becoming 40 limits, and kept expiry from handing out tokens. Section: Keys, memory and expiry.
• A local share when the store failed admitted 140 instead of 4,840, and refused nobody else. Section: When the limiter's store fails.
• 429 with Retry-After from the refill let a client that honours the header drop from 400 to about 46 requests a second, for the same 1,219 admitted. How those are shared among one client's workers is the client's own job. Section: What the client is told.
• One all-or-nothing script stopped a refused export from costing 10 tokens. Section: Several limits on one request.
• One bucket named after the rule, and versions that only go up, admitted 153 in the first 10 s of a plan change instead of 334. Section: Changing a rule.
• Leased blocks cut a hot key's store calls from 100,000 a second to about 148, with at most 3,000 tokens of overshoot. Section: A key too hot for one shard.
• Each limit in its layer kept the precise 429s in the gateway, and the late, coarse WAF block for real floods. Section: One request, end to end.
• Shares that move by named grants kept k-big's three Regions at or under 10,000 a second, where jumping to each target reached 11,898. Section: One limit, three Regions.
• Two signals before a reclaim brought k-big back to 10,000 after a lost Region, and kept a cut-off Region from pushing it to 13,600. Section: When a Region is lost.
• Metering with running totals made a record delivered twice change nothing. Section: A rate limit is not a billing quota.
• A table of what each limit sees showed that 4,800 addresses keep every count per address and per account small. Section: An attack spread over many addresses.
• A cap inside orders protects it when every partner is within its contract and the backend slows. Section: A slow backend when every client is under its limit.
• The work per admitted request showed that the edge bills every request it inspects, and the limiter mostly per node. Section: Build on AWS's limiters or your own.

The snapshots, side by side

The table lists the six snapshots. Each snapshot's name links to the section that shows it.

What it costs

The fix has seven costs.

1. A round trip on every request. The store is on the request path. One busy key makes 400 calls a second, refusals included.
2. A failure policy to decide and keep correct. That means a second, local limiter in every gateway, and alarms on every decision made without the store.
3. A burst to choose and defend for every limit. The burst is the overshoot you accept.
4. An error of limited size in every design that splits the count across servers. Shares admit too little when traffic is uneven. Leases admit too much, by at most gateways × 1.2 × block. Sticky routing hands out a burst when a key moves.
5. Scripts that block their node while they run. And a hot key that no number of shards can split.
6. Managed limiters that are approximate. API Gateway's limits are best-effort targets. WAF's count is late and per IP. And some defaults send 403, 500 or 503.
7. Pipelines for what spans Regions and months. A share sync between Regions, with a rule for a lost Region. And a metering pipeline, with its own lag.

The whole story, event by event

The table lists every event of the page. The events keep the numbers of the full run, so the table does not follow the order of the sections. Each event's number links to the section that shows it.

Side rows and replays run on copies and are marked "(side)". Where a row is random, it gives seeds 1 and 2.

The cheat card

One row per topic, for a last look before an interview.

Failure checklist

Ask these questions of any rate limiter design.

• Does every limit have both a rate and a burst, and a reason for each?
• Is the burst sized for an honest burst, not for the per-window total?
• Is each limit counted once for the whole fleet (central, or exact shares), not once per server?
• Do refill, decision and write run in one atomic script in the store?
• Does the script read the store's clock, never a time passed in by the caller?
• Is each limit keyed on exactly what it limits, with one bucket per dimension and no composite keys?
• Is IP used only for unauthenticated traffic, and taken from your own edge?
• Is every key's TTL at least b ÷ r, set on every write, and do you alarm on evictions?
• Is there a decided policy per limit for when the store can't answer, with a local share for security limits, and an alarm on every bypass?
• Are hot keys leased in whole blocks, with a stated overshoot, and never for security limits?
• Does each request's set of limits run in one all-or-nothing script under one hash tag?
• Are billed quotas counted by metering, not by the limiter?
• Does every refusal send 429 with Retry-After from the refill, and is every proxy's and edge's status code set explicitly?
• Is each new or tighter rule launched in shadow mode first?
• Is each bucket named after its rule, never after the rule's version, and does a gateway ignore an older rule set?
• Does a limit across Regions move room only by named grants, and reclaim a silent Region only when an outside health check agrees?
• Are security limits kept out of leases and share sync, in one home Region or split per Region?
• Does the backend protect itself by its own latency, whatever the partners' limits allow?

Words we use

The table gives the meaning of each term as this page uses it.

Pages that send readers here

You may have arrived from a step that relies on this page:

• steps 1.1 to 1.3 of the rate limiter loop: six gateways, which algorithm, and two checks on one key at the same instant.
• step 2.4 of the notification loop: one bucket per provider for every worker.
• step 2.6 of the mobile stock-trading loop: a per-account bucket in Valkey.
• step 2.3 of the Shopify case study: a "leaky bucket" that was a fixed window.
• step 1.1 of the bot-defense case study: WAF rate rules and a sliding counter.
• the drill The Partner Whose Retry Loop Took Down Everyone Else. This page answers both of its questions in full, in Counting in windows, The token bucket and Twenty servers, one limit. The first exercise in Check yourself: Mid-level works through its numbers.

In all, 26 of the 38 interview loops depend on a rate-limiting mechanism in at least one step.

Where to go next

• Retries, Timeouts, Backpressure & Load Shedding covers six related topics:
  • Retry-After from the caller's side (section Retries: what, where and how many).
  • backoff and jitter (section Backoff and jitter).
  • retry budgets (section Retry budgets and hedged requests).
  • 503 and shedding (section Backpressure: stock protects itself).
  • breakers (section Circuit breakers).
  • concurrency limits (section Bulkheads and concurrency limits).
• Sharding, Hot Keys & Rebalancing: hot keys in general, and leasing as pre-aggregation (sections A hot key appears and Hot writes, and every fix on equal terms).
• Leases, Fencing Tokens & Distributed Locks: whose clock decides (section Time: whose clock decides?).
• Idempotency & Effectively-Once Processing: a provider's limit shared by live traffic and replays (section Shared limits), and keys for requests retried after a 429.
• Queues & Delivery Semantics: deferring work that got a 429 (section Deferring healthy work).
• Caching & Invalidation: the enumerating bot that a per-client limit stops (section Negative caching: the keys you don't have).
• Replication, Quorums & Read-Your-Writes and Multi-Region Failover: what a failover loses, and Regions that go away.
• Drill: The Partner Whose Retry Loop Took Down Everyone Else. Both of its questions are answered in Counting in windows, The token bucket and Twenty servers, one limit. The first exercise in Check yourself: Mid-level works through its numbers.
• Background: Distributed Rate Limiting, the broader primitive; API Gateway & Reverse Proxy; Bot Defense, Sybil Resistance & Registration Abuse.
• Loops that rely on this page:
  • the rate limiter: steps 1.0 to 1.6, R1.4, R1.7, R1.9, R1.11, 2.1 to 2.6, R2.7 to R2.9, R2.11, 3.1, 3.2, 3.4 to 3.6 and R3.7
  • notifications: steps R1.7, 2.4 and 2.6
  • email: steps 2.6 and R2.9
  • mobile stock trading: step 2.6
  • the Shopify case study: step 2.3
  • the bot-defense case study: steps 1.1, R1.7, R1.9, 2.5 and R2.8
  • crowdfunding: steps 2.2, 2.3, R2.9 and 3.5
  • the key-value store: step 2.7
  • the unique ID generator: step 2.4
  • the message queue: step 2.7
  • S3-like storage: step 3.6
  • metrics and alerting: step 2.4
  • the URL shortener: steps 2.4, 2.6 and R2.5
  • hotel reservations: step 2.2
  • ad-click aggregation: step 3.2
  • the proximity service: section R1.9
  • nearby friends: section R1.9
  • the web crawler: steps 1.3 and 3.4
  • the job scheduler: step 2.6
  • chat: step 2.5
  • the Discord case study: step 2.1
  • the gaming leaderboard: step 1.4
  • Google Drive: section R2.8
  • payment processing: step 3.3
  • the Netflix case study: section R1.4
  • the digital wallet: section R2.6

Ready to apply this?

You have learned the mechanisms. Next, apply them, then defend them:

1. Apply: the interview loop Design a Distributed Rate Limiter designs the same system in three rounds.
2. Defend: the drill The Partner Whose Retry Loop Took Down Everyone Else asks two questions about one incident.