Rate Limiting Algorithms

Part 0. Start here

The problem: twenty servers, each one right, and one key at twenty times its limit

Basketly, the grocery shop of pages 10 and 12, sells to meal-kit partners through a Partner API. Twenty gateway servers sit behind a load balancer that spreads requests evenly. Each gateway checks every request against the caller's contract in its own memory. The meal-kit partner FreshBox has the API key k-7, and its contract says 600 requests a minute, bursts up to 20. Each gateway enforces that as a token bucket that refills at 10 a second and holds up to 20.

At 09:00:00 on Tuesday, FreshBox deploys a sync client with a retry bug. Its 40 workers resend every answer at once, 429 included, so k-7 sends 400 requests a second for two minutes.

Every gateway did exactly what it was told. 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". 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 drill The Partner Whose Retry Loop Took Down Everyone Else tells it at twelve: 1,000 requests a minute per key, a retry storm of 40,000 a minute, and every other partner's p99 up from 60 ms to 900 ms.

Why an overloaded service falls over, and how it should shed load, is Retries, Timeouts, Backpressure & Load Shedding. This page is about why the limit didn't hold, and how to make it hold.

The big picture

Synthesizing vector architecture diagram...

What to notice: every gateway has its own bucket, each correctly admitting 10 a second, so k-7 reaches orders at 200 a second and pushes it to 895 of its 800. The dashed store, where one count for k-7 would live, doesn't exist as shipped.

What you'll be able to do after this page

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 (Part 1).
2. Explain what a fixed window, a sliding log and a sliding window counter each bound, and where each lets too much through (Part 2).
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 (Part 3).
4. Enforce one limit across 20 servers in four ways, and say which way each one errs (Part 4).
5. Make the check one atomic step with one clock, and say what a fast clock or a read-then-write costs (Part 5).
6. Choose the key, size the memory, and set a TTL that never hands out free tokens (Part 6).
7. Decide in advance what each limit does when its store is down, and compute what each choice lets through (Part 7).
8. Lease blocks of tokens for a key too hot for one shard, and state the overshoot (Part 8).
9. Check several limits on one request in one all-or-nothing call, and keep billing quotas apart from rate limits (Part 9).
10. Send the right status code and Retry-After, and know what your proxy and edge send by default (Part 10).
11. Place each limit in the layer that can see what it counts (Part 11).
12. Map all of it to AWS, and name the look-alikes (Part 12).

You may have arrived from a step that relies on this: steps 1.1 to 1.3 of the rate limiter loop (six gateways, which algorithm, the race), 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), or the drill The Partner Whose Retry Loop Took Down Everyone Else, whose two questions this page answers in full (Parts 2 to 4, and drill 1 in Part 13). In all, 26 of the 38 interview loops depend on a rate-limiting mechanism in at least one step.

---

Part 1. A limit is two numbers and a key

"600 a minute, bursts of 20." What does that promise? It sounds like one number, 600, with a footnote. It is really four decisions, and the storm tests all of them. This Part names them, separates a rate limit from two things that look like it, and sets up the example.

Rate, burst, key, cost

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

Rate limit, quota, shedding

Three mechanisms refuse requests, and each answers a different question.

A limit on requests in flight (Stripe's "concurrent requests limiter", a bulkhead) is a fourth thing: it caps how many run at once, not how many start per second (Retries & Backpressure, Part 8 there). The broader primitive Distributed Rate Limiting surveys all of them; 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. It is Basketly again (pages 10 and 12), now through its Partner API; the partner and the key are new. Every trace on this page comes from running a private reference simulation of this setup (the arrivals, the 20 gateways, the store, the clocks, and every algorithm and failure policy as a setting), not from working it out by hand. The example's numbers are small so that every decision fits on a line.

We replay the same two minutes under each design, called rungs L0 to L6 (Part 2 lists them). The rungs are alternatives compared on equal terms, not guards added one by one; only L5 and L6 build on L4, the fix. The failure cases (a race, a fast clock, a store that goes away, a hot key, an export, the edge) each run on a copy of the rung they name, so no event swamps another.

The story in eleven beats: a limit is two numbers and a key (Part 1); the minute that was spent in 1.5 seconds (Part 2); the bucket that refills (Part 3); twenty servers, one limit (Part 4); the burst that raced and the clock that lied (Part 5); the wrong key (Part 6); the store that went away (Part 7); the key too hot for one shard (Part 8); the export that cost ten (Part 9); what FreshBox was told (Part 10); one request, end to end (Part 11). Each Part shows only its own events; the full table is in Part 13.

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

---

Part 2. Counting in windows

At 09:00:01.4975 FreshBox had used its whole minute. A central fixed window of 600 a minute (rung L1) admitted the storm's first 600 requests back to back, the last one 599 × 2.5 ms = 1.4975 s into the minute, and then refused everything for 58.5 seconds. That is 600 requests in 1.5 seconds: 400 in one second, 40 times the contract's 10 a second, and every one of them reached orders. The limiter counted correctly. It just counted the wrong thing.

Here are the rungs. Each replays the same two minutes, from 08:59:00 to 09:03:00, with all of k-7's traffic.

Fixed window

The simplest shared count: one counter per key per window, named after the window.

textCopy
FIXED WINDOW (limit L per window of W seconds)
  window = floor(now / W)                       now from the store's clock
  count  = INCR  rl:{k-7}:<window>              atomic; EXPIRE the key on first use
  if count > L:
      DECR rl:{k-7}:<window>                    count only admitted requests
      refuse
  admit

INCR is atomic, so this needs no script: that is why fixed windows are popular. Envoy's global rate-limit service works this way, with the window start computed as (now / divider) * divider and a pipelined INCRBY plus EXPIRE.

Event 4, on the storm trace

Snapshot T3 (L1)

The totals barely differ. What differs is when. 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 the edge is small (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, and nothing is the burst.

Synthesizing vector architecture diagram...

What to notice: the line that spikes is the fixed window: 400 in second 0, 200 in second 1, zero until second 60, then 400 and 200 again, 1,200 in all. The flat line is the token bucket: 29 in the first second (its burst of 20 plus 9), then 10 every second, 1,219 in all. The totals match; the spikes are 40 times the contract's per-second rate. (The axis is not evenly spaced.)

The edge

The storm could only send 400 a second. A client that can send faster does worse. Side row W runs on a fresh key, k-9, with no history: 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. Five limiters, the same two seconds:

Synthesizing vector architecture diagram...

What to notice: each panel is one limiter on the same 1,200 requests. "Fixed window, 60 s" admits them all, twice the limit in two seconds. "Sliding log" and "Sliding window counter" hold near 600 but let 600 through in one second. "Fixed window, 1 s" and "Token bucket" hold the burst down. Only the token bucket also lets a real page load through (Part 3).

This is the drill's second question. 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", and the whole window's budget at once anywhere else.

Sliding log

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

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

Event 5 (L2). The log is exact: never more than 600 in any 60 s. It admits 1,200 in the two minutes. But it remembers the past. When the storm begins, the log still holds the 314 requests k-7 made in the 60 s before, so only 290 pass in the storm's first second (293 in its first 1.5 s). After that, it admits exactly as fast as old entries turn 60 s old: 5 a second, the pace of 08:59's normal traffic, and 15 back to back from 09:00:30.100, one every 2.5 ms, when the page load ages out. A window algorithm's output copies the shape of the previous window.

Its memory is one entry per request kept: up to 600 entries for k-7, and 24,000 (400 a second × 60 s) if you log every attempt, which you need to do to refuse by attempts. That is exactly when you are under attack (Part 6). And each check first deletes the entries that have aged out, so a hot key that has piled up millions of stale entries makes that ZREMRANGEBYSCORE slow, on a node where nothing else runs until it finishes (Part 5).

Sliding window counter

Keep two numbers, this minute's count and last minute's, and estimate the trailing 60 s by assuming last minute's requests were spread evenly.

textCopy
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

In words: 15 seconds into minute 09:00, three quarters of the trailing 60 s still lies in minute 08:59, so 08:59's count of 315 contributes 315 × 45 ÷ 60 ≈ 236.

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

How wrong the estimate can be

The counter is an estimate, not a bound. On real traffic it is very good: Cloudflare, which built its rate limiting this way, measured "400 million requests from 270,000 distinct sources" and 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 W: after k-9's 600 at the end of minute 09:04, it sends 1,000 a second through minute 09:05. The counter admits about 10 a second as 09:04's weight fades, and one trailing 60 s holds 1,189 requests: nearly twice the limit, spread over a minute.

A window made of many small windows (60 one-second counters, say) is a finer fixed window: a smaller edge error, more counters, and still one number.

---

Part 3. The bucket that refills

The token bucket (L4) 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 check

Each key's bucket is two numbers: tokens and ts, the time they were last computed. Nobody adds tokens on a schedule. Each check works out how many would have been added since ts. This is the rate limiter loop's check (step 1.2 there), with one rule made explicit: the bucket is written back on every check, allowed or refused.

textCopy
CHECK(key, cost, b = 20, r = 10 a second)
  now   = the store's clock                              (Part 5)
  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 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

Events 7 to 9 (L4)

Synthesizing vector architecture diagram...

What to notice: the burst is spent once, in the first 47.5 ms, falling from 20 to under 1. After that the bucket never holds a whole token for long: it climbs to 1 in 100 ms, one request takes it, and it starts again. The rate holds from then on.

Snapshot T1, 09:00:00.048 (L4)

The bound

In any interval of t seconds, a token bucket admits at most a full bucket plus what refills during the interval:

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

For k-7: at most 20 + 10 × 1 = 30 in any second (the run: 29), and 20 + 10 × 60 = 620 in any minute (the run: 619). The run is one lower because 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. With b = 600, "600 a minute" would allow 600 + 600 = 1,200 in a minute, 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, no bigger.

Retry-Afterfrom the refill

The check already knows when the next token arrives: (cost − tokens) ÷ r seconds. Retry-After carries whole seconds (Part 10), so it is rounded up. A client that honours it comes back when it can succeed.

GCRA: the same decisions with one number

The generic cell rate algorithm comes from ATM networks, where it policed fixed-size cells. It stores one number per key, the theoretical arrival time (tat): the time at which the key would be exactly back in step with its rate.

textCopy
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 - now <= tau:                           not too far ahead of schedule
      write(key, tat + T × cost) ; allow
  else:
      refuse ; retry after (tat - tau - now)

Synthesizing vector architecture diagram...

What to notice: each allowed request pushes tat 100 ms further ahead. After the 20 of the burst, tat is 2 s ahead of now, more than τ = 1.9 s, so the next request is refused. Every 100 ms of real time brings now back within τ, and one more request fits: 10 a second.

Event 10 (L4g). On the whole trace, GCRA and the token bucket made identical decisions for all 48,615 requests (every storm request, the page load and the normal traffic). That is not a coincidence: a bucket holding tokens is a tat of now + (b − tokens) × T, and "tokens ≥ 1" is "tat − now ≤ τ". GCRA saves one field and is harder to explain in an interview.

One trap when you use it: implementations disagree on what "burst" means. The redis-cell module's CL.THROTTLE key max_burst count period returns a total limit of "max_burst + 1", so for b = 20 you pass max_burst 19.

The leaky bucket: a queue or a meter

"Leaky bucket" names two different things, and a third one borrows the name.

NGINX adds one more default to check: "By default, the maximum burst size is equal to zero", so without a burst setting even a page load of two calls in the same instant is refused. A queue is right in front of something fragile that must see a smooth rate; for an API, adding up to 2 s of latency to answer "no" later is usually worse than answering "no" now.

---

Part 4. Twenty servers, one limit

Now the hook, explained. As shipped (L0), each of the 20 gateways ran a correct token bucket for k-7, and together they admitted 200 a second. This Part shows why, and the four ways to make 20 servers enforce one limit, each with the direction it errs in.

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

Synthesizing vector architecture diagram...

What to notice: in "L0: twenty buckets" every gateway's bucket looks exactly like the one in "L4: one bucket", a fraction of a token refilling at 10 a second. Each is correct. There are just twenty of them, so k-7 gets twenty times the rate.

Why the hook happened

Event 11 (L0). Each gateway sees k-7 every 50 ms (400 a second ÷ 20). Its bucket starts full at 20 and refills 0.5 tokens between arrivals, so it admits everything for a while: 39 requests in its first 1.9 seconds, until the burst is spent. Then it admits 10 a second, one request in two. Twenty gateways × 10 = 200 a second.

This is the drill's first question: local counters on 12 gateways each see about a twelfth of the key's traffic and let the key have 12 times its limit. It is also step 1.0 of the rate limiter loop, step 2.6 of the email loop (63 MTAs counting locally send 63 times too much) and step 2.6 of the mobile stock-trading loop ("30 order API tasks each counting locally would let one account send 30 times its limit").

Split it exactly

Give each gateway its share: r ÷ N = 10 ÷ 20 = 0.5 a second, and a burst of b ÷ N = 1 (never less than 1). Side row X replays the storm with exact shares:

Exact shares never admit too much, and they admit too little when traffic is uneven. Envoy's local rate limit filter offers this as local_cluster_rate_limit, which divides the limit by the number of Envoy instances so the whole gateway enforces X a second "regardless of how N changes"; step 2.6 of the 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%". And a burst of 1 per gateway admits a page load only if the load balancer happens to spread it over enough gateways.

Send the key to one server

Side row Y: route by hash(k-7), so all of k-7 goes to G3, which keeps a local bucket of 10 a second and 20. It counts once, so it admits like L4, and it needs no store. But G3 alone now carries all 400 a second of k-7's storm, a hot gateway. And at 09:01:00 the fleet scales out to 21 gateways, the hash moves k-7 to G21, and G21's bucket starts full: +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 it in one place

Event 12 (L4). 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 (1 ms here) and 400 store calls a second for k-7: a refused request costs a call too. The store is now on every request's path, which is Parts 5, 7 and 8's problem.

Which way each errs

Synthesizing vector architecture diagram...

What to notice: every design but the central store gives up exactness somewhere, and each says in its box which way it errs. Only local buckets err without a bound; leased blocks (Part 8) err by at most gateways × 1.2 × block.

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", and 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: step 2.3 of the crowdfunding loop keeps one bucket per payment endpoint and one for the account, and Idempotency & Effectively-Once Processing (Part 12 there) gives the resolver that replays payments its own cap inside the provider's limit, so replays can't starve live charges. The other side of a throttle, deferring work that got a 429, is replay T of Queues & Delivery Semantics (Part 4 there). 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.

---

Part 5. One atomic step, one clock

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 whether the check is one step or three, and on whose clock it reads.

Fifteen calls, five tokens

Side row C runs on a copy of L4, with k-7's normal traffic removed after 09:02:00 and the bucket set to 5 tokens at 09:03:00.000. The 15 calls leave 15 gateways 33 µs apart. First, each gateway does it 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.

Synthesizing vector architecture diagram...

What to notice: all 15 reads arrive before the first write, so every gateway sees the same 5 tokens, allows its call and writes back 4. Fifteen calls passed on five tokens, and the bucket even says 4 were left.

Snapshot T4, 09:03:00.0015

This 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 it would cost two more round trips per request, and a gateway that dies holding the lock blocks the key until the lock expires.

The script

Redis and Valkey run a server-side script as one command: "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:

textCopy
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 (Part 6)
  inside the script:
    now = TIME                        the store's clock
    tokens, ts = HMGET KEYS[1] tokens ts
    refill, decide, HSET tokens and ts, EXPIRE ttl    (Part 3's CHECK)
    return allowed, floor(tokens), retry_after

EVALSHA calls a script already loaded by its hash, so each check sends a few bytes. Keep scripts short: while one runs, nothing else on that node does, for any key. That single thread is the ceiling Part 8 runs into.

Is TIME inside a script safe? Scripts are replicated by their effects (the writes they made), 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), and Valkey's documentation notes that verbatim replication was removed.

Whose clock

The script reads TIME from the store instead of taking now from the gateway. Side row S shows why, on a copy of L4 where the script uses the time each gateway passes in, and gateway G7's clock is 2 seconds fast:

Synthesizing vector architecture diagram...

What to notice: G7 writes a timestamp 2 s in the future; the next gateway clamps the negative elapsed time to 0 and writes its own, true time back. So every 50 ms G7 finds 2 s "elapsed" and refills the bucket to 20, and the other gateways spend it.

Any difference between callers' clocks mints tokens. One clock removes the question. A small one remains: after a failover (Part 7), the new primary's clock may be ahead of the old one's by δ, which hands each bucket at most δ × r extra tokens, once. Leases, Fencing Tokens & Distributed Locks has the general rule, "whose clock decides" (Part 3 there).

DynamoDB instead

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 Part 8, 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, with side row S's problem.
• TTL deletes expired items "within a few days", so a reader must treat an expired item as absent itself.

Step R1.11 of the rate limiter loop (follow-up 3) prices it: milliseconds per check, and at its traffic about USD 6,500 a month for DynamoDB's reads and writes against about USD 231 for the cache. DynamoDB suits limiter rules and billing quotas; the per-request check belongs in memory.

---

Part 6. Keys, memory and expiry

A reviewer, to be safe, keys the bucket on hash(api_key + 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 different keys:

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 (rl:{k7}:plan, rl:{k7}:user:<id>, rl:{ip}:unauth), all checked together in one call (Part 9).

What to key on

A bot that walks through random ids makes every lookup a miss, and Caching & Invalidation (side row 17c there) sends it here: limit each client, by API key, or by IP where there is no key.

Memory

Event 15. What one key costs to keep:

NGINX's limit_req keeps its state in each node's shared memory: "The stored state always occupies 64 bytes on 32-bit platforms and 128 bytes on 64-bit platforms", and 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 (step R1.11 of the rate limiter loop: 6.4 GB against 96 MB).

TTL and eviction

Every key needs a TTL, set on every write, or the store fills with keys of clients who called once. How long? Side row 6t runs L4 with a TTL of 1 s, shorter than the bucket's full refill (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:

No request is admitted extra here: 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). They matter when the key bursts right after the reset: it gets 20 at once instead of 13.

With the 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 one is created full, exactly as it was. The rule: TTL ≥ b ÷ r makes expiry harmless.

Eviction is not harmless. A bucket the store evicts under memory pressure comes back full, whatever it held: up to +20 at once for k-7, and a free burst of 5 for a login limit of 5 a minute. The 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 (step R2.8 of the rate limiter loop). Size the store so it doesn't evict, and alarm on evictions.

Changing a rule

Pass a rule's numbers (b, r, cost, TTL) to the script as arguments, so 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). And launch a new or tighter rule in shadow mode first: it 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, NGINX has limit_req_dry_run.

---

Part 7. When the limiter's store fails

At 09:01:00, halfway through the storm, the limiter store's primary fails. ElastiCache promotes the replica; AWS says writes "can resume as soon as the promotion process is complete, typically just a few seconds", and our copy (replay F, a copy of L4 rewound to 09:00:00) takes 12 seconds. For those 12 seconds no gateway can get an answer. What does each one do with the requests in front of it?

Don't wait for it

The limiter has its own timeout and breaker, exactly as Retries & Backpressure builds them for any dependency (Parts 2 and 7 there): a check waits at most 3 ms (a normal round trip is 1 ms), and after 5 timeouts in a row the gateway's breaker opens and stops calling the store, sending one probe a second.

Event 16. Each gateway checks about 55 times a second: 20 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, and five 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 it opens, then one a second, and they 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, and every check in that time, including the few that timed out before the breaker opened, is decided by the failure policy.

Snapshot T5, 09:01:05

Synthesizing vector architecture diagram...

What to notice: the same open breakers lead to three different outcomes. "Open" lets the storm straight through, "Closed" turns the cache failure into an outage for all 40 partners, and "Local share" keeps k-7 near its contract while everyone else carries on.

Three policies

Events 17 to 19, the same 12.1 seconds under each policy:

The local share is the exact shares of side row X (Part 4), switched on while the store is away: each gateway's bucket for k-7 refills at 0.5 a second, holds 1, and starts full at that gateway's first timeout. It 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 (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 (failure_mode_deny is false, and its call to the rate-limit service times out after 20 ms by default).
• A security limit (logins, one-time codes, card tests): never open. A local share keeps the endpoint up and bounded.
• Closed only for one route whose abuse costs more than its outage, and then for that route alone.

Count every decision made without the store, and alarm on it, or you'll never know it happened.

Security limits when N > L

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. Side row 7s has an attacker spray one account's logins across all 20 gateways during an outage:

When there are more servers than the limit, a local share still lets up to N through at once. Three answers, and the loops choose differently: accept it for short outages; send that key to one gateway while the store is away (by hashing, as in Part 4); or close that one route. The rate limiter loop falls back to local limits (step 1.4); the bot-defense case study also pauses scale-out while it is degraded (step R1.9).

Coming 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, 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: 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, already counted in event 19's 140). Our copy assumes the replica had every write; real replication is asynchronous, so a failover also loses the last writes before it and hands their tokens back (Replication, Quorums & Read-Your-Writes, Part 6 there). 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 page 10 cover that storm.

---

Part 8. A key too hot for one shard

Replay H leaves FreshBox and rewinds on a copy with a bigger customer. k-big is an enterprise key with a contract of 10,000 a second, burst 20,000. It 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 misfiring batch job 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: 100,000 script calls a second on the one shard that holds rl:{kbig}. That is 100,000 ÷ 60,000 ≈ 167% of the rate limiter loop's working assumption of about 60,000 small-script calls a second per node. Scripts on a node run one at a time (Part 5), so every other key on that shard, belonging to other tenants, waits behind k-big's refusals. Adding shards doesn't help: a key lives in one hash slot, on one shard. Sharding, Hot Keys & Rebalancing owns hot keys in general (Part 3 there, "A limit per key"); this Part owns the limiter's own fix.

Lease a block

Stop asking once per request. Each gateway leases a block of tokens, spends it in memory, and asks again only when the block runs low. This is pre-aggregation for a limiter (Sharding, Part 5 there, "Leasing and striping"), and step 2.3 of the rate limiter loop is its source.

Synthesizing vector architecture diagram...

What to notice: G5 talks to the shard once per block, not once per request. When the bucket can't give a whole block, the shard says "not until" one block cycle from now, and G5 refuses locally until then, so k-big's refusals cost the shard nothing.

textCopy
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

The numbers:

• Block size about 0.25 s of one gateway's share: B = max(10, ⌈0.25 s × 10,000 ÷ 20⌉) = 125.
• Block cycle, 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 so the 20 don't return together.
• Whole blocks or nothing. A lease that granted whatever was left (a few tokens) would be answered again a moment later, and the fleet would make about one lease call per admitted request, which is where it started.

The overshoot, bounded

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

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 others lease new ones, and 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 below 20%, plus the next), so the overshoot is at most gateways × 1.2 × block = 20 × 1.2 × 125 = 3,000 tokens: 0.3 s of the rate. The undershoot is the tokens stranded in leases when traffic stops or moves.

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

Leasing is for capacity limits above about 500 a second. Never for a security limit: a login limit of 5 a minute can't survive 20 gateways each holding a block. And a lease here is a grant of quota, not ownership of anything, so it needs no fencing token (Leases, Fencing Tokens & Distributed Locks makes the same distinction).

One limit, three Regions

A contract that holds across Regions can't make a cross-Region call on every request. Side row 8r uses the rate limiter loop's numbers (step 3.1 there): each Region enforces a share with the machinery above, and shares follow recent usage, with a floor so an idle Region can still serve a sudden burst.

Regions compute shares from views a second or more apart, so if each simply took its new target, shares could briefly add up to more than L. The ad-click loop (step 3.2) moves them by handoff: a Region may lower its share at any time, but may raise it only into budget another Region has already published as released. Each Region writes only its own record, so nothing conflicts. (ElastiCache's Global Datastore can't be the shared counter: "A secondary cluster only accepts read requests".) When a Region is lost, its share is frozen or handed out again (step 3.5 of the rate limiter loop; Multi-Region Failover owns the failover itself).

---

Part 9. Several limits on one request

At 09:03:00.100, after the storm, FreshBox starts two data exports. An export is expensive: it costs 10 tokens from k-7's plan bucket, and 1 token from a route bucket for POST /v1/exports that refills at 0.2 a second and holds 1 (one export every 5 s). Replay M runs on a copy of L4; by 09:03 the storm's debt is repaid and the plan bucket is full again.

One script, all buckets

Synthesizing vector architecture diagram...

What to notice: the script refills and checks both buckets before it charges either. Because the route bucket is short, neither is charged, and the wait sent back comes from the bucket that was short.

Events 24 and 25

Separate calls are also not atomic with each other (a bucket can be charged for a request another refuses, as in 25'), and their latencies add up. So:

textCopy
CHECK_ALL(keys, costs, rules)                 one EVALSHA; every key in KEYS
  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

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, and a script whose keys land in different slots is refused with a CROSSSLOT error. 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. Pass every key as a KEYS argument ("must be explicitly provided as input key arguments", Valkey's documentation), never built inside the script. The cost: a tenant's buckets all live on one shard, which is Part 8's problem when the tenant is huge.

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. At its full rate of 10 a second it would use 10 × 86,400 = 864,000 a day, so the daily quota decides after 100,000 ÷ 10 = 10,000 s ≈ 2.8 hours (event 26). 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. Its buckets refill, expire, are evicted, overshoot with leases and fail open during outages: fine for "slow down", wrong for money. Step 3.2 of the rate limiter loop counts billed usage in a separate metering pipeline (a stream, deduplication, absolute totals), and 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" (Part 12).

The same rule holds for outside limits with two layers. Stripe limits each account (100 live requests a second) and each endpoint (25 a second, unless noted), and tells you which one you hit in a Stripe-Rate-Limited-Reason header; the crowdfunding loop (step 2.3) keeps one bucket for each and checks both in one call.

---

Part 10. What the client is told

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.

textCopy
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 }

429or 503

429 means this client sent too much; 503 means the service can't take the request, whoever sent it. Retries & Backpressure has the full table (Part 6 there, "503, 429 or backpressure?"). So orders, overloaded by L0's 895 a second, should shed with 503 and Retry-After by its own health; a 429 from orders would tell every partner that it, personally, was over its limit (event 28).

Retry-After

RFC 6585 defines 429: "the user has sent too many requests in a given amount of time", and the response "MAY include a Retry-After header". It also says "Responses with the 429 status code MUST NOT be stored by a cache". RFC 9110 allows Retry-After as a date or as delay-seconds, "a non-negative decimal integer": whole seconds. So the refill's 50 ms becomes Retry-After: 1. Rounding up is right: a client that comes back sooner would be refused again.

The budget on every response

The draft defines no mapping for a token bucket, so the headers above 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, and 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". Step R1.11 of the rate limiter loop (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.

Defaults that send something else

Event 28. Several common limiters don't send 429 unless you tell them to:

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

A client that listens

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 limiter admits exactly the same, to exactly the same workers, and the gateways, the store and the network see about a ninth of the traffic. The lopsided split is not caused by Retry-After: it is an artifact of our perfectly regular model, and the diagram shows why.

Synthesizing vector architecture diagram...

What to notice: worker 1's requests arrive exactly as each token does, because an allowed answer takes exactly 100 ms and a token takes exactly 100 ms. Every other worker arrives a few milliseconds after a token has been taken, finds less than one, and is refused, whether it resends at once or waits a second. In the model nothing ever breaks that tie. 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 is fair between keys, not between 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 (Retries & Backpressure, Part 4 there). Here jitter changes nothing (the run tried waits jittered by up to 0.1 s, 0.5 s and 1 s), because worker 1 still arrives exactly as each token does. A server can help by computing Retry-After from the refill, as here, rather than sending a fixed number.

---

Part 11. One request, end to end

Basketly also has an edge limit: an AWS WAF rate-based rule on its CloudFront distribution, 3,000 requests per 60 s per source IP, action Block. Replay E runs it on a copy of L6. FreshBox's traffic, k-7 and its second app k-8 (20 a second from 08:59:00 on), all 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 counts requests per IP over the trailing 60 s, checks the count every 10 s (AWS: it "checks the rate about every 10 seconds"), 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), and counts blocked requests toward the rate.

Events 29 and 30

Synthesizing vector architecture diagram...

What to notice: the count crosses 3,000 at about 09:00:04 (drawn to the second), but nothing happens until a check sees it at 09:00:10, and nothing is blocked until 30 s (or 50 s) after that: 16,800 requests (or 25,200) pass from 09:00:00 until the block starts. The block then outlives the storm, which ended at 09:02:00, by a minute and a half, and 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 are useful. The edge is cheap and stops a flood before it costs compute; it is approximate, late and coarse. The gateway is exact per key; it runs after TLS, routing and authentication.

Layer by layer

Synthesizing vector architecture diagram...

What to notice: each arrow back to the client is a different layer refusing for a different reason, with a different status: the edge by IP with 403, the gateway by key with 429, and orders by its own health with 503. The load balancer refuses nothing; its even spread is what made local counts fail in Part 4.

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

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. Many IPs each under every limit (a distributed attack) is a detection problem, not a counting one: step 3.3 of the rate limiter loop and the bot-defense case study own it, and the broader primitives API Gateway & Reverse Proxy and Bot Defense, Sybil Resistance & Registration Abuse cover the layers around it.

---

Part 12. On AWS

AWS runs rate limiters in two managed places, API Gateway and WAF, and both say plainly that they are approximate. Anything exact, weighted, or keyed on something they can't see, you build yourself, usually on ElastiCache. Three rules carry over from the rest of the page: know what each one keys on, know what it sends when it refuses, and know which limits are shared by more than one of your APIs.

Managed services that use it

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

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 noisy API can throttle the rest, and no usage plan can raise a client above it. A WAF rule's count is shared by everyone behind one IP (event 30), and one rule can limit at most 10,000 IPs at once.

Running it yourself

Look-alikes that are not this mechanism

---

Part 13. What you've learned

Back to FreshBox

As shipped, twenty gateways each enforced k-7's contract correctly and admitted 200 a second between them: 24,380 requests in two minutes against a contract of 1,220, and orders at 895 of its 800 a second. With one central token bucket in one atomic script, k-7 got 1,219: its burst of 20, then 10 a second, and orders stayed at 705. Here is what each piece did:

• Two numbers and a key (Part 1) let the 15-call page load through and told us what "600 a minute" really promises.
• Knowing what windows count (Part 2) ruled out a fixed window that spent the minute in 1.5 s and allowed 1,200 in two seconds at its edge.
• A token bucket, or GCRA (Part 3), bounded every interval to burst + rate × time: 29 in any second, 619 in any minute.
• One count instead of twenty (Part 4) removed the 20×; exact shares stayed ready as the fallback.
• One atomic script with the store's clock (Part 5) let 5 of 15 racing calls through instead of 15, and stopped a fast clock from admitting all 48,000.
• The right key and a TTL of at least b ÷ r (Part 6) kept 40 accounts from becoming 40 limits and expiry from handing out tokens.
• A local share when the store failed (Part 7) admitted 140 instead of 4,840, and refused nobody else.
• Leased blocks (Part 8) cut a hot key's store calls from 100,000 a second to about 148, with at most 3,000 tokens of overshoot.
• One all-or-nothing script (Part 9) stopped a refused export from costing 10 tokens.
• 429 with Retry-After from the refill (Part 10) let a listening client 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.
• Each limit in its layer (Part 11) kept the precise 429s in the gateway, and the late, coarse WAF block for real floods.

The snapshots, side by side

What it costs

1. A round trip on every request, and a store on the request path: 400 calls a second for one busy key, refusals included.
2. A failure policy to decide and keep correct: 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: it is the overshoot you accept.
4. Bounded error wherever the count is split: shares under-admit, leases over-admit by 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 best-effort targets, WAF's late, per-IP count, and defaults that send 403, 500 or 503.

The whole story, event by event

Side rows and replays run on copies and are marked "(side)". Seeds 1 and 2 where a row is random.

The cheat card

Failure checklist

• 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?

Words we use

Think-first drills

Interview questions

Where to go next

• Retries, Timeouts, Backpressure & Load Shedding: Retry-After from the caller's side (Part 3 there), backoff and jitter (Part 4 there), retry budgets (Part 5 there), 503 and shedding (Part 6 there), breakers (Part 7 there) and concurrency limits (Part 8 there).
• Sharding, Hot Keys & Rebalancing: hot keys in general, and leasing as pre-aggregation (Parts 3 and 5 there).
• Leases, Fencing Tokens & Distributed Locks: whose clock decides (Part 3 there).
• Idempotency & Effectively-Once Processing: a provider's limit shared by live traffic and replays (Part 12 there), and keys for requests retried after a 429.
• Queues & Delivery Semantics: deferring work that got a 429 (replay T, Part 4 there).
• Caching & Invalidation: the enumerating bot that a per-client limit stops (side row 17c, Part 6 there).
• 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 questions answered in Parts 2 to 4, with its numbers in drill 1.
• 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 (R1.9), nearby friends (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 (R2.8), payment processing (step 3.3), the Netflix case study (R1.4) and the digital wallet (R2.6).