C03 hands-on — Rate limiting, block by block

Five algorithms, the burst bug in the obvious one, and what distribution costs.

Source: handson/c03_rate_limiter.py --- run it with python3 handson/c03_rate_limiter.py
Full project spec: d03 — Distributed Rate Limiter

Rate limiting is the most-asked system design warm-up because it is small enough to finish and deep enough to separate candidates. The separation is not whether you know the token bucket. It is whether you can say what the fixed-window counter does at a boundary, why the sliding-window log is correct and unaffordable, and what breaks the moment there are two servers.

This page builds five limiters as independent blocks, measures the failure of each, and then assembles them into the version you would actually deploy. Every number below came from running the code.

Run it

cd swe-interview-prep/handson

python3 c03_rate_limiter.py            # every block, then the assembly
python3 c03_rate_limiter.py --block 3  # block 3 and its prerequisites only
python3 c03_rate_limiter.py --quiet    # the assembly only
python3 c03_rate_limiter.py --verify   # re-derive and assert every claim below

What to expect. A full run takes under a second and prints 6 blocks followed by the assembly. There are no dependencies beyond the Python standard library and nothing touches the network or the filesystem.

Every seed is fixed, so the numbers you get are the numbers on this page --- character for character. If yours differ, the code changed, not the machine. --verify re-derives 10 claims from scratch and exits non-zero if any of them stops holding, which is what makes the prose here checkable rather than assertable.

Predict before you read

Worth two minutes with a pen, because the gap between your answer and the measurement is the entire value of the page. Write down a number for each:

1. Limit 5 per second, fixed window. A client sends 5 requests at t=0.98 and 5 more at t=1.001. How many are allowed, and over what span?
2. Same pattern against a sliding-window log. How many?
3. Same pattern against a token bucket at rate 5, burst 5. How many?
4. The sliding-window counter is the standard compromise. What is its worst-case over-admission --- and how does that compare to the fixed window it exists to replace?
5. Cloudflare publishes "0.003% of requests wrongly allowed". At 1.5x the configured limit, what over-admission rate would you actually measure?
6. Ten concurrent workers, limit 5, GET then SET against a shared store. How many are admitted?

Then run it, or read on --- the answers are in the blocks, and the ones most people get wrong are called out where they land.

Contents

• Run it
• Predict before you read
• Block 1 — Fixed window
• Block 2 — Sliding window log
• Block 3 — Token bucket
• Block 4 — Sliding window counter
• Block 5 — Two servers
• Block 6 — Atomicity
• The assembly
• Verify the claims
• The design space
• Cost model: why distribution dominates everything
• Advanced algorithms
• Hardware and placement
• How this connects to the rest of the program
• Failure modes at scale
• Primary sources
• What to do with this

How to read this page

Each block below is a self-contained lego piece: it builds one mechanism, proves it works on its own, and returns what the next block needs. The code is the real source, sliced out of the script. The output underneath it is the real output, captured by running that script --- not transcribed, not idealised. Where a measurement contradicted what I expected, the contradiction is in the output and the prose says so.

The assembly at the end wires every block into one working thing and measures it.

Block 1 — Fixed window

Teaches: the obvious algorithm, and the boundary bug that fails interviews

The problem. A counter and a clock is the design everyone reaches for first, and it is genuinely O(1) in both time and space. It is also wrong in a way that a client discovers by accident and an attacker discovers on purpose, and the discovery costs nothing: no coordination, no timing precision, just sending requests near a boundary the server published in its own Retry-After header.

@block(1, "Fixed window", "the obvious algorithm, and the boundary bug that fails interviews")
def b1(s, show):
    class FixedWindow:
        def __init__(self, limit, window): self.limit, self.w = limit, window; self.c = {}
        def allow(self, now):
            k = int(now // self.w)
            self.c = {k: self.c.get(k, 0)}          # only the current window matters
            if self.c[k] < self.limit:
                self.c[k] += 1; return True
            return False
    if show:
        lim = FixedWindow(limit=5, window=1.0)
        # the adversarial pattern: 5 at the END of window 0, 5 at the START of window 1
        times = [0.98, 0.98, 0.99, 0.99, 0.999] + [1.001, 1.001, 1.002, 1.002, 1.003]
        got = [lim.allow(t) for t in times]
        print(f"  limit = 5 per 1.0s window")
        print(f"  requests at t=0.98..0.999 : {sum(got[:5])} allowed")
        print(f"  requests at t=1.001..1.003: {sum(got[5:])} allowed")
        print(f"  ALL {sum(got)} allowed inside a {times[-1]-times[0]:.3f}s span "
              f"-- {sum(got)/ (times[-1]-times[0]):.0f}x the configured rate")
        print("  The counter resets on a wall-clock boundary, so a client that")
        print("  straddles it gets 2x the limit in an arbitrarily short interval.")
        print("  Memory: one integer per client. Correctness: 2x burst. This is the")
        print("  algorithm to name, then reject, in the first minute of the interview.")
    return {"FixedWindow": FixedWindow}

Reading the implementation

• k = int(now // self.w) — the window key is derived from the clock, not from the client's first request. That is the entire bug in one line. Every client on the fleet shares the same boundary, so the boundary is a public, predictable instant. A per-client window anchored at first-contact would remove the synchronised stampede but not the 2×, and it costs a second field.
• self.c = {k: self.c.get(k, 0)} — rebuilding the dict is how this implementation garbage-collects. Without it the map grows one entry per window forever, which is a memory leak that takes days to show up. Production implementations get this free by making the window key part of the Redis key and setting a TTL, so expiry is the store's problem rather than the application's.
• The check is < and the increment follows it. Check-then-act, single-threaded, correct here and a race the moment there are two threads — which is block 6.

What the numbers say

Output:

  limit = 5 per 1.0s window
  requests at t=0.98..0.999 : 5 allowed
  requests at t=1.001..1.003: 5 allowed
  ALL 10 allowed inside a 0.023s span -- 435x the configured rate
  The counter resets on a wall-clock boundary, so a client that
  straddles it gets 2x the limit in an arbitrarily short interval.
  Memory: one integer per client. Correctness: 2x burst. This is the
  algorithm to name, then reject, in the first minute of the interview.

Ten requests inside a 23-millisecond span against a limit of five per second. The headline ratio in the output is arithmetic on that span and is deliberately absurd; the honest statement of the bug is the bounded one: a fixed window admits up to 2× the limit in any window-length interval, and the worst case is exactly the one shown — limit at the end of one window, limit at the start of the next.

Try it yourself

Every mechanism on this page is importable. parts() runs the blocks silently and hands back what each one built, so you can drive them directly:

from c03_rate_limiter import parts
FixedWindow = parts()["FixedWindow"]

# Same 10-request burst, 4 ms apart, slid across the window boundary at t=1.0.
for offset in (0.20, 0.60, 0.90, 0.97, 0.98, 0.99):
    fw = FixedWindow(limit=5, window=1.0)
    burst = [offset + i * 0.004 for i in range(10)]      # spans 36 ms
    got = sum(fw.allow(t) for t in burst)
    crosses = burst[0] < 1.0 <= burst[-1]
    print(f"  burst at t={offset:.2f}s (ends {burst[-1]:.3f}) -> {got} of 10 allowed"
          f"{'   <- STRADDLES the boundary' if crosses else ''}")

  burst at t=0.20s (ends 0.236) -> 5 of 10 allowed
  burst at t=0.60s (ends 0.636) -> 5 of 10 allowed
  burst at t=0.90s (ends 0.936) -> 5 of 10 allowed
  burst at t=0.97s (ends 1.006) -> 7 of 10 allowed   <- STRADDLES the boundary
  burst at t=0.98s (ends 1.016) -> 10 of 10 allowed   <- STRADDLES the boundary
  burst at t=0.99s (ends 1.026) -> 8 of 10 allowed   <- STRADDLES the boundary

Note what the sweep actually shows, which is sharper than "it doubles at the edge": the full 2× occurs in a narrow band — 10 of 10 at t=0.98, but only 7 and 8 a hundredth of a second either side, because those bursts split unevenly across the two windows. The exposure is a function of exactly where the burst lands relative to a boundary the client can see and you cannot control.

That narrowness is precisely why the bug survives testing. A load test with randomly-phased traffic hits the peak in a small fraction of runs and reports a mean over-admission of a few percent; an adversary — or a client retrying on a schedule derived from your own Retry-After — hits it every time.

Beyond the toy

The 2× is not the reason to reject it. The reason is that the bound is reached by ordinary traffic, not just by an adversary: any client that retries on a schedule derived from your own Retry-After header lands on the boundary by construction, so the failure is self-inflicted at the protocol level.

Two mitigations that are cheaper than changing algorithm, and worth naming because they show you understand where the cost is:

• Jitter the window origin per client, k = int((now + hash(client)) // w). The 2× per client remains; the fleet-wide synchronised burst disappears, which is usually the failure that actually pages someone.
• Shorten the window and scale the limit: 5/s has a 23 ms exposure, 300/min has a 60-second exposure of the same shape. The interval over which the 2× can be delivered shrinks linearly with the window, so a smaller window is strictly safer at equal average rate — at the cost of forbidding legitimate bursts entirely.

That second point is the one that generalises: window length is a burst tolerance, and choosing it is choosing how much burst you will accept. The token bucket in block 3 makes that parameter explicit instead of implicit, and that is its real advantage over this — not the boundary bug.

Block 2 — Sliding window log

Teaches: exactly correct, and you cannot afford it

The problem. Block 1's counter is wrong because it throws away when requests arrived. Keeping all of it makes the answer exact by construction. This block exists to establish the correctness reference, and then to price it, because the price is what rules it out.

@block(2, "Sliding window log", "exactly correct, and you cannot afford it")
def b2(s, show):
    class SlidingLog:
        def __init__(self, limit, window): self.limit, self.w = limit, window; self.q = deque()
        def allow(self, now):
            while self.q and self.q[0] <= now - self.w: self.q.popleft()
            if len(self.q) < self.limit:
                self.q.append(now); return True
            return False
        def bytes_used(self): return len(self.q) * 8
    if show:
        lim = SlidingLog(limit=5, window=1.0)
        times = [0.98, 0.98, 0.99, 0.99, 0.999] + [1.001, 1.001, 1.002, 1.002, 1.003]
        got = [lim.allow(t) for t in times]
        print(f"  same adversarial pattern: {sum(got)} allowed (fixed window let "
              f"{10}) ")
        print(f"  {'clients':>9}{'limit':>8}{'memory':>12}{'at 1M clients':>16}")
        for limit in (5, 100, 10_000):
            per = limit * 8
            print(f"  {1:>9}{limit:>8}{per:>10} B{per*1_000_000/1e9:>14.1f} GB")
        print("  Exact, because it stores every timestamp. That is also why it is")
        print("  unusable: memory is O(limit) PER CLIENT, so a 10k/min limit across")
        print("  a million clients is 80 GB. Name it as the correctness reference,")
        print("  not as the answer.")
    return {"SlidingLog": SlidingLog}

Reading the implementation

• while self.q and self.q[0] <= now - self.w: self.q.popleft() — eviction is amortised O(1) per request, not O(limit): every timestamp is appended once and popped once. The loop looks like it makes allow linear and does not. Saying that unprompted is worth a point, because the interviewer is checking whether you can distinguish "there is a loop" from "the operation is linear".
• deque, not list. list.pop(0) shifts every remaining element, so the same algorithm on a list is O(n) per eviction and O(n²) to drain — measured at 390× slower at n=100k in the follow-up bank. This is the most common accidental quadratic in Python and it hides inside a correct algorithm.
• The window is sliding and continuous: there is no boundary anywhere, which is why this is the reference the other three are scored against.

What the numbers say

Output:

  same adversarial pattern: 5 allowed (fixed window let 10) 
    clients   limit      memory   at 1M clients
          1       5        40 B           0.0 GB
          1     100       800 B           0.8 GB
          1   10000     80000 B          80.0 GB
  Exact, because it stores every timestamp. That is also why it is
  unusable: memory is O(limit) PER CLIENT, so a 10k/min limit across
  a million clients is 80 GB. Name it as the correctness reference,
  not as the answer.

Five allowed on the pattern that let ten through in block 1 — the correct answer. The memory table is the reason nobody ships it: state is O(limit) per client, so it scales with the limit rather than with the traffic. A 10,000/min limit costs 80 KB per client and 80 GB across a million clients, and that is before the store's own per-key overhead, which for Redis is on the order of 50–100 bytes per key on top.

The asymmetry worth noticing: raising a customer's limit raises your memory bill even if they never use it. That is a genuinely bad property for a product where "enterprise tier gets 10× the limit" is the pricing page.

Try it yourself

Price the memory directly, for a limit you might actually sell:

from c03_rate_limiter import parts
SlidingLog = parts()["SlidingLog"]

for limit in (100, 1_000, 10_000):
    log = SlidingLog(limit=limit, window=60.0)
    for i in range(limit):                    # fill it
        log.allow(i * 1e-6)
    per = log.bytes_used()
    print(f"  limit {limit:>6}/min: {per:>7,} B per client"
          f" -> {per * 1_000_000 / 1e9:>6.1f} GB across 1M clients")

  limit    100/min:     800 B per client ->    0.8 GB across 1M clients
  limit   1000/min:   8,000 B per client ->    8.0 GB across 1M clients
  limit  10000/min:  80,000 B per client ->   80.0 GB across 1M clients

Note the shape of the growth: it is linear in the limit, not in the traffic. A customer on a bigger plan costs you more memory whether or not they use it, which is a genuinely bad property for the thing your pricing page advertises.

Beyond the toy

Real deployments that need exactness do not store timestamps — they store counts in small buckets, which is a sliding log with the resolution turned down until it is affordable. Ten 100 ms buckets per second gives you an error bounded by one bucket instead of by one whole window, at 10 integers per client rather than limit floats. That is the design point between block 2 and block 4, and it is the one to reach for when the interviewer says "the counter's error is too big but the log is too expensive" — which is the follow-up this block sets up.

Redis's ZREMRANGEBYSCORE + ZCARD + ZADD on a sorted set is the literal implementation of this block, and the reason it is a Lua script in practice is block 6: three commands is two races.

Block 3 — Token bucket

Teaches: the one to actually implement, and why it is lazy

The problem. Both previous algorithms think in windows, which is why both have a boundary or a memory bill proportional to the limit. The token bucket throws the window away entirely and thinks in rate plus credit, which turns out to need two floats and no bookkeeping at all.

@block(3, "Token bucket", "the one to actually implement, and why it is lazy")
def b3(s, show):
    class TokenBucket:
        def __init__(self, rate, burst):
            self.rate, self.burst = rate, burst
            self.tokens, self.last = float(burst), 0.0
        def allow(self, now, cost=1.0):
            self.tokens = min(self.burst, self.tokens + (now - self.last) * self.rate)
            self.last = now
            if self.tokens >= cost:
                self.tokens -= cost; return True
            return False
    if show:
        tb = TokenBucket(rate=5.0, burst=5)
        times = [0.98, 0.98, 0.99, 0.99, 0.999] + [1.001, 1.001, 1.002, 1.002, 1.003]
        got = [tb.allow(t) for t in times]
        print(f"  rate = 5/s, burst = 5")
        print(f"  adversarial pattern: {sum(got)} allowed "
              f"(fixed window 10, sliding log 5)")
        print(f"  {'t':>7}{'tokens before':>15}{'allowed':>9}")
        tb2 = TokenBucket(rate=5.0, burst=5)
        for t in (0.0, 0.1, 0.2, 0.4, 1.0, 2.0):
            before = min(tb2.burst, tb2.tokens + (t - tb2.last) * tb2.rate)
            a = tb2.allow(t)
            print(f"  {t:>7.1f}{before:>15.2f}{str(a):>9}")
        print("  No timer, no background thread, no per-request state cleanup: tokens")
        print("  are computed LAZILY from elapsed time on each call. Two floats per")
        print("  client, O(1) time, and burst is an explicit parameter rather than an")
        print("  accident. This is the answer.")
    return {"TokenBucket": TokenBucket}

Reading the implementation

• self.tokens = min(self.burst, self.tokens + (now - self.last) * self.rate) — the refill is lazy: computed from elapsed time at the moment of the call. No timer, no background thread, no scheduled job per client. That is the property that makes a million idle clients free, and it is the answer to "how do you refill a million buckets every second" — you do not, you never touch a bucket nobody is using.
• min(self.burst, ...) must come before the check, not after. Clamping late lets an idle client accumulate unbounded credit and then spend a month of quota in one second, which is the same 2× failure as block 1 with a much bigger constant.
• self.last = now runs unconditionally, on the rejected path too. Updating it only on success double-counts the elapsed time of every rejected request on the next call, which inflates the effective rate under exactly the overload conditions the limiter exists for.
• Two mutable floats and no allocation: this fits in a Redis hash of two fields, or in 16 bytes of a packed struct.

What the numbers say

Output:

  rate = 5/s, burst = 5
  adversarial pattern: 5 allowed (fixed window 10, sliding log 5)
        t  tokens before  allowed
      0.0           5.00     True
      0.1           4.50     True
      0.2           4.00     True
      0.4           4.00     True
      1.0           5.00     True
      2.0           5.00     True
  No timer, no background thread, no per-request state cleanup: tokens
  are computed LAZILY from elapsed time on each call. Two floats per
  client, O(1) time, and burst is an explicit parameter rather than an
  accident. This is the answer.

Five allowed on the adversarial pattern — matching the sliding log's exact answer — from two floats instead of a list. The trace table is the part to internalise: tokens are never recomputed except when someone asks, and the value at any instant is a pure function of (last, tokens, now). That purity is what makes the distributed version in block 5 a single compare-and-set rather than a read-modify-write conversation.

Try it yourself

The lazy refill is the part worth seeing rather than reading. Watch tokens accumulate with no timer anywhere:

from c03_rate_limiter import parts
TokenBucket = parts()["TokenBucket"]

tb = TokenBucket(rate=5.0, burst=5)
print("  drain the bucket, then idle and watch it refill from elapsed time alone")
for t in (0.0, 0.0, 0.0, 0.0, 0.0):
    tb.allow(t)                                # spend all 5
print(f"  t=0.0  tokens={tb.tokens:.2f}  allow -> {tb.allow(0.0)}")
for t in (0.2, 0.5, 1.0, 3.0):
    ok = tb.allow(t)
    print(f"  t={t:.1f}  tokens after={tb.tokens:.2f}  allow -> {ok}")

  drain the bucket, then idle and watch it refill from elapsed time alone
  t=0.0  tokens=0.00  allow -> False
  t=0.2  tokens after=0.00  allow -> True
  t=0.5  tokens after=0.50  allow -> True
  t=1.0  tokens after=2.00  allow -> True
  t=3.0  tokens after=4.00  allow -> True

Nothing ran between those calls. No thread woke up, no timer fired, no cron touched a million idle buckets. The state is two floats and the value at any instant is a pure function of (last, tokens, now) — which is exactly what makes the distributed version a single compare-and-set instead of a conversation.

Beyond the toy

Burst becomes an explicit parameter rather than an emergent property of the window length. That is the actual argument for this algorithm and it is a product argument, not a performance one: you can now sell "100 requests per second, bursts to 500" and implement exactly that, which no window-based algorithm can express without lying.

Three things production adds:

• Cost-weighted consumption. allow(now, cost) already takes it. An LLM completion is not one unit of anything; charging tokens by estimated cost and refunding the difference on completion is what m01 does, and it is the same estimate-then-reconcile split as billing.
• A hierarchy of buckets. Per-key AND per-org AND per-endpoint, all of which must admit. The subtlety is that a request rejected by the third bucket must refund the two it already debited, or a client burning its org quota silently loses its per-key quota too.
• GCRA (the leaky-bucket-as-virtual-scheduling formulation from ATM networking) computes the identical decision from one float instead of two — see the deep dive, where it is measured against this implementation over 5,000 Poisson arrivals.

Block 4 — Sliding window counter

Teaches: the memory/accuracy compromise everyone ships

The problem. The sliding log is exact and unaffordable; the fixed window is free and wrong. The standard compromise estimates the trailing window by blending two fixed-window counters, and it is what Cloudflare published and what most systems ship. This block was written to demonstrate a bounded error. The measurement did not cooperate, and the block now shows what it actually found.

@block(4, "Sliding window counter", "the memory/accuracy compromise everyone ships")
def b4(s, show):
    class SlidingCounter:
        """Weighted blend of the previous and current fixed windows."""
        def __init__(self, limit, window):
            self.limit, self.w = limit, window
            self.cur_key, self.cur, self.prev = 0, 0, 0
        def allow(self, now):
            k = int(now // self.w)
            if k != self.cur_key:
                self.prev = self.cur if k == self.cur_key + 1 else 0
                self.cur, self.cur_key = 0, k
            frac = 1.0 - (now % self.w) / self.w
            est = self.prev * frac + self.cur
            if est < self.limit:
                self.cur += 1; return True
            return False
    def worst_case(limit, eps):
        """Fill the previous window at its very END, then hammer at 1+eps."""
        sc = SlidingCounter(limit, 1.0)
        for j in range(limit):
            sc.allow(1.0 - 1e-9 * (limit - j))
        admitted = sum(sc.allow(1.0 + eps) for _ in range(limit * 5))
        # The old `limit` requests sit at t~1.0, still inside the trailing
        # window [eps, 1+eps] for any eps < 1. So true occupancy is the sum.
        return admitted, (limit + admitted) / limit

    def over_admission(limit, mult, n=40_000, seed=5):
        """Run ONLY the counter; check each admit against the TRUE trailing count.

        No second limiter, so there is no state-divergence confound: `bad` is
        exactly the count of requests a sliding log would have refused.
        """
        rng = random.Random(seed)
        sc, hist = SlidingCounter(limit, 1.0), deque()
        t, bad, adm = 0.0, 0, 0
        for _ in range(n):
            t += rng.expovariate(limit * mult)
            if sc.allow(t):
                while hist and hist[0] <= t - 1.0: hist.popleft()
                if len(hist) + 1 > limit: bad += 1
                hist.append(t); adm += 1
        return adm, bad, n

    if show:
        times = [0.98, 0.98, 0.99, 0.99, 0.999] + [1.001, 1.001, 1.002, 1.002, 1.003]
        sc = SlidingCounter(limit=5, window=1.0)
        got = [sc.allow(t) for t in times]
        print(f"  adversarial pattern: {sum(got)} allowed (fixed 10, log 5, bucket 5)")
        print(f"  memory: 2 integers per client vs {5*8} B for the log at limit=5")
        print()
        print("  I expected 'bounded error'. Measuring the worst case says otherwise:")
        print(f"  {'gap after boundary':>20}{'admitted':>10}{'true/limit':>12}")
        for eps in (0.1, 0.3, 0.5, 0.9, 0.99):
            adm, ratio = worst_case(100, eps)
            print(f"  {eps:>19.2f}s{adm:>10}{ratio:>11.2f}x")
        print("  The worst case tends to 2x -- the SAME bound as the fixed window")
        print("  this algorithm exists to fix. It does not remove the 2x; it makes")
        print("  the 2x require a specific arrival pattern instead of any burst.")
        print()
        print("  And the published '0.003% wrongly allowed' does not survive either.")
        print("  Measured, limit=100, Poisson arrivals, 40k requests each:")
        print(f"  {'offered load':>14}{'admitted':>10}{'over-limit':>12}{'% of all':>10}")
        for mult in (0.5, 0.9, 1.0, 1.5, 3.0):
            adm, bad, n = over_admission(100, mult)
            print(f"  {mult:>13.1f}x{adm:>10}{bad:>12}{bad/n*100:>9.2f}%")
        print("  Zero error while traffic is under the limit; 15-23% once it is at")
        print("  or above it. Cloudflare's figure is real and is measured in the")
        print("  regime where the limiter is not limiting. In the regime a limiter")
        print("  exists for, the error is four orders of magnitude larger.")
    return {"SlidingCounter": SlidingCounter}

Reading the implementation

• self.prev = self.cur if k == self.cur_key + 1 else 0 — the else 0 handles a gap. If more than one window has elapsed, the previous window is genuinely empty and reusing a stale count would reject traffic for a burst that finished minutes ago. Getting this wrong produces a limiter that is too strict after an idle period, which reads as a random outage.
• est = self.prev * frac + self.cur — the whole algorithm. frac is how much of the previous window is still inside the trailing window, and multiplying by it assumes the previous window's requests were spread uniformly. They were not; a burst is by definition non-uniform, and the burst is the case you are limiting.
• worst_case() constructs the adversarial arrival pattern directly: fill the previous window at its very end, then arrive eps into the next one. Because the old requests sit at t≈1.0, they are still inside the trailing window [eps, 1+eps] for any eps < 1, so true occupancy is just the sum — no simulation needed to score it.
• over_admission() runs only the counter and scores each admit against the true trailing count built from the counter's own history. Running two limiters side by side and diffing them would be wrong: after the first disagreement their internal states differ, and everything downstream measures divergence rather than error.

What the numbers say

Output:

  adversarial pattern: 6 allowed (fixed 10, log 5, bucket 5)
  memory: 2 integers per client vs 40 B for the log at limit=5

  I expected 'bounded error'. Measuring the worst case says otherwise:
    gap after boundary  admitted  true/limit
                 0.10s        11       1.11x
                 0.30s        30       1.30x
                 0.50s        50       1.50x
                 0.90s        90       1.90x
                 0.99s        99       1.99x
  The worst case tends to 2x -- the SAME bound as the fixed window
  this algorithm exists to fix. It does not remove the 2x; it makes
  the 2x require a specific arrival pattern instead of any burst.

  And the published '0.003% wrongly allowed' does not survive either.
  Measured, limit=100, Poisson arrivals, 40k requests each:
    offered load  admitted  over-limit  % of all
            0.5x     40000           0     0.00%
            0.9x     39463        2140     5.35%
            1.0x     37837        6235    15.59%
            1.5x     26703        9314    23.29%
            3.0x     13423        6258    15.65%
  Zero error while traffic is under the limit; 15-23% once it is at
  or above it. Cloudflare's figure is real and is measured in the
  regime where the limiter is not limiting. In the regime a limiter
  exists for, the error is four orders of magnitude larger.

Two results, and both contradict what this block was written to show.

The worst case tends to 2×, which is the fixed window's bound. At a gap of 0.99 s the estimate has decayed to 100 × 0.01 = 1, so 99 more are admitted while all 100 originals are still inside the trailing second: 199 against a limit of 100. The sliding window counter does not remove the fixed window's 2×. It makes the 2× require a specific arrival pattern — fill the window late, then wait most of a window — instead of any burst that happens to straddle a boundary. That is a real improvement and it is not the improvement it is usually sold as.

The published 0.003% is measured in the regime where the limiter is idle. At 0.5× offered load the measured error is exactly zero, because a limiter under its limit rejects nothing and therefore mis-rejects nothing. At 1.0–1.5× it is 15–23% of all requests. Both numbers are true; they describe different regimes, and the regime a rate limiter exists for is the second one.

Try it yourself

Reproduce the worst case yourself, and watch it converge on 2× as the gap grows:

from c03_rate_limiter import parts
SlidingCounter = parts()["SlidingCounter"]

LIMIT = 100
for gap in (0.1, 0.25, 0.5, 0.75, 0.95, 0.999):
    sc = SlidingCounter(limit=LIMIT, window=1.0)
    for j in range(LIMIT):                     # fill window 0 at its very END
        sc.allow(1.0 - 1e-9 * (LIMIT - j))
    admitted = sum(sc.allow(1.0 + gap) for _ in range(LIMIT * 3))
    print(f"  gap {gap:>5.3f}s after the boundary -> {admitted:>3} more admitted, "
          f"true occupancy {(LIMIT + admitted) / LIMIT:.2f}x the limit")

  gap 0.100s after the boundary ->  11 more admitted, true occupancy 1.11x the limit
  gap 0.250s after the boundary ->  25 more admitted, true occupancy 1.25x the limit
  gap 0.500s after the boundary ->  50 more admitted, true occupancy 1.50x the limit
  gap 0.750s after the boundary ->  75 more admitted, true occupancy 1.75x the limit
  gap 0.950s after the boundary ->  95 more admitted, true occupancy 1.95x the limit
  gap 0.999s after the boundary -> 100 more admitted, true occupancy 2.00x the limit

The estimate decays linearly while the real requests stay inside the trailing window the whole time. As the gap approaches a full window the estimate reaches zero and the limiter admits a second full limit — which is the fixed window's failure, arrived at by a different route.

Beyond the toy

What this changes in the interview: do not say "the sliding window counter fixes the boundary problem". Say "it trades the fixed window's easily-triggered 2× for a hard-to-trigger 2×, at the same O(1) state" — and if you have this measurement, say that the accuracy claim is load-dependent and quote the condition. Naming the regime a benchmark was taken in is the single most transferable habit on this page.

What production does when that is not good enough:

• More, smaller buckets (block 2's Beyond the toy). Ten 100 ms buckets bound the error at one bucket rather than one window, for ten integers.
• Token bucket instead, which has no windows and therefore no boundary at any scale.
• Accept it and price it. Cloudflare's choice is defensible precisely because their traffic mostly sits under the limit — the regime where the measurement above says the error is zero.

Block 5 — Two servers

Teaches: every single-node algorithm is wrong the moment you scale out

The problem. Every algorithm above is exactly correct on one machine, and you do not have one machine. This block is the moment the problem stops being an algorithms question and becomes a distributed systems question, and the transition is the thing being tested.

@block(5, "Two servers", "every single-node algorithm is wrong the moment you scale out")
def b5(s, show):
    if show:
        print("  Run the token bucket independently on N servers, limit 5/s each")
        print(f"  {'servers':>9}{'per-server limit':>18}{'effective limit':>17}")
        for n in (1, 2, 4, 16):
            print(f"  {n:>9}{5:>18}{5*n:>17}")
        print("  Sharding the LIMIT instead (5/n per server) is worse: a client whose")
        print("  requests land unevenly gets throttled far below its quota.")
        print()
        print("  Three real options, and the trade each makes:")
        print(f"  {'design':<26}{'accuracy':>10}{'latency':>10}  {'blast radius':<20}")
        for name, acc, lat, blast in (
                ("central store (Redis)", "exact", "+1 RTT", "hard dependency"),
                ("local + async sync", "approx", "0", "drift on partition"),
                ("consistent-hash owner", "exact", "+1 RTT", "one shard per key")):
            print(f"  {name:<26}{acc:>10}{lat:>10}  {blast:<20}")
        print("  The follow-up is always 'what if Redis is down'. The answer that")
        print("  scores is fail-OPEN with a local fallback limiter, because a rate")
        print("  limiter that fails closed converts a cache outage into a full outage.")
    return {}

Reading the implementation

There is no implementation here on purpose — the block prints a decision table rather than simulating, because the failure is arithmetic and does not need code to demonstrate. N independent limiters at limit L enforce N×L. That is the whole finding, and a candidate who says it in the first ten seconds of this follow-up has effectively answered it.

What the numbers say

Output:

  Run the token bucket independently on N servers, limit 5/s each
    servers  per-server limit  effective limit
          1                 5                5
          2                 5               10
          4                 5               20
         16                 5               80
  Sharding the LIMIT instead (5/n per server) is worse: a client whose
  requests land unevenly gets throttled far below its quota.

  Three real options, and the trade each makes:
  design                      accuracy   latency  blast radius        
  central store (Redis)          exact    +1 RTT  hard dependency     
  local + async sync            approx         0  drift on partition  
  consistent-hash owner          exact    +1 RTT  one shard per key   
  The follow-up is always 'what if Redis is down'. The answer that
  scores is fail-OPEN with a local fallback limiter, because a rate
  limiter that fails closed converts a cache outage into a full outage.

The effective-limit column is linear in server count, which means your limit is a function of your deployment topology — it changes when autoscaling adds a replica, silently, with no config change and no deploy. That is the property that makes this a correctness bug rather than a tuning issue.

The obvious repair, dividing the limit by N, is worse and the reason is worth stating precisely: request routing is not uniform at short timescales. A client with 5 open connections landing on 3 of 16 replicas gets 3/16 of its quota while the other 13 replicas hold unusable credit. You have converted a system that over-admits by N× into one that under-admits by up to N×, and under-admitting a paying customer generates a support ticket where over-admitting generates a slightly larger bill.

Try it yourself

The arithmetic is the argument, so do it for your own fleet size:

LIMIT = 1000                     # what you sold the customer, per minute
for servers in (1, 3, 10, 50, 200):
    independent = LIMIT * servers
    sharded = LIMIT / servers
    print(f"  {servers:>3} servers | independent limiters -> {independent:>7,}/min "
          f"({independent / LIMIT:>4.0f}x sold) | sharded -> {sharded:>6.1f}/min each")
print()
print("  A customer whose traffic lands on 3 of 50 shards gets "
      f"{3 * LIMIT / 50:.0f}/min of a {LIMIT}/min plan.")

    1 servers | independent limiters ->   1,000/min (   1x sold) | sharded -> 1000.0/min each
    3 servers | independent limiters ->   3,000/min (   3x sold) | sharded ->  333.3/min each
   10 servers | independent limiters ->  10,000/min (  10x sold) | sharded ->  100.0/min each
   50 servers | independent limiters ->  50,000/min (  50x sold) | sharded ->   20.0/min each
  200 servers | independent limiters -> 200,000/min ( 200x sold) | sharded ->    5.0/min each

  A customer whose traffic lands on 3 of 50 shards gets 60/min of a 1000/min plan.

Both failure directions are bad and they are bad in different currencies: over-admitting costs money and is recoverable through billing; under-admitting throttles a paying customer to 6% of their plan and generates a support ticket. Neither is a tuning problem — both are consequences of choosing the wrong place to keep the state.

Beyond the toy

The three-row table is the real answer, and the choice is decided by one question: is the limit a contract or a safety device?

• A contract (billed, published in a pricing page) wants exactness, so it wants the central store, and it must fail closed — failing open during your own incident is free unlimited usage.
• A safety device (protecting a backend from overload) wants availability, so it wants local enforcement with async reconciliation, and it must fail open — a limiter that fails closed converts a Redis blip into a total outage.

Most real systems have both and the mistake is applying one policy to both. d03 develops the lease-based middle ground, where each process leases a block of tokens and enforces locally: a lease factor of 20 cuts store traffic 20× and bounds the error at lease_size × process_count, which is a number you can put in a contract.

Block 6 — Atomicity

Teaches: check-then-set across a network is a race, not an implementation detail

The problem. Block 5 says "use a shared store". This block is why that sentence is not an answer. The obvious way to use a shared store is read, decide, write — three operations, two of which are races, and the race only fires under concurrency, which is the only condition a rate limiter is deployed under.

@block(6, "Atomicity", "check-then-set across a network is a race, not an implementation detail")
def b6(s, show):
    class RedisLike:
        def __init__(self): self.d = {}
        def get(self, k): return self.d.get(k, 0)
        def set(self, k, v): self.d[k] = v
        def incr(self, k):                      # atomic
            self.d[k] = self.d.get(k, 0) + 1; return self.d[k]
    def racy(store, key, limit, n_workers):
        allowed = 0
        for _ in range(n_workers):
            v = store.get(key)                  # every worker reads the same value
            if v < limit:
                allowed += 1
        for _ in range(allowed): store.incr(key)
        return allowed
    def atomic(store, key, limit, n_workers):
        allowed = 0
        for _ in range(n_workers):
            if store.incr(key) <= limit: allowed += 1
        return allowed
    if show:
        print(f"  limit = 5, {10} concurrent workers hitting the same key")
        r1 = RedisLike(); r2 = RedisLike()
        print(f"  GET-then-SET (read all, then write): {racy(r1, 'k', 5, 10):>2} allowed  "
              f"<- WRONG")
        print(f"  INCR and compare (single round trip): {atomic(r2, 'k', 5, 10):>2} allowed  "
              f"<- correct")
        print("  The racy version is what you write first. It is correct under no")
        print("  concurrency and wrong under exactly the load a rate limiter exists")
        print("  for. The fix is one atomic operation -- INCR, or a Lua script for")
        print("  the token bucket, since 'read tokens, compute, write tokens' is")
        print("  three round trips and two races.")
    return {"RedisLike": RedisLike}

Reading the implementation

• racy() reads the counter for every worker before any of them writes. That is a deliberately extreme interleaving — real concurrency produces something in between — and it is extreme in the direction that shows the bug clearly: every worker sees the pre-request value, so every worker is admitted.
• atomic() uses incr and compares the returned value. One round trip, and the decision is made from a value that no other worker can have seen. The comparison is <= limit rather than < limit because INCR returns the count after incrementing.
• RedisLike.incr is a single method to make the point that atomicity is a property the store provides, not one the client can construct from non-atomic pieces.

What the numbers say

Output:

  limit = 5, 10 concurrent workers hitting the same key
  GET-then-SET (read all, then write): 10 allowed  <- WRONG
  INCR and compare (single round trip):  5 allowed  <- correct
  The racy version is what you write first. It is correct under no
  concurrency and wrong under exactly the load a rate limiter exists
  for. The fix is one atomic operation -- INCR, or a Lua script for
  the token bucket, since 'read tokens, compute, write tokens' is
  three round trips and two races.

Ten allowed against a limit of five, versus five. The failure is exactly 2× again here, but that is an artifact of the worker count — with 100 concurrent workers the racy version admits 100. The over-admission of a check-then-act race is bounded by concurrency, not by the limit, which is what makes it strictly worse than block 1's boundary bug.

Try it yourself

Interleave the reads and writes explicitly and watch the admitted count track the concurrency rather than the limit:

from c03_rate_limiter import parts
RedisLike = parts()["RedisLike"]

def racy(workers, limit=5):
    store = RedisLike()
    seen = [store.get("k") for _ in range(workers)]      # all read before any write
    admitted = sum(1 for v in seen if v < limit)
    for _ in range(admitted): store.incr("k")
    return admitted

def atomic(workers, limit=5):
    store = RedisLike()
    return sum(1 for _ in range(workers) if store.incr("k") <= limit)

print(f"  {'concurrency':>12}{'GET-then-SET':>14}{'atomic INCR':>13}")
for w in (2, 5, 10, 100, 1000):
    print(f"  {w:>12}{racy(w):>14}{atomic(w):>13}")

   concurrency  GET-then-SET  atomic INCR
             2             2            2
             5             5            5
            10            10            5
           100           100            5
          1000          1000            5

The over-admission of a check-then-act race is bounded by concurrency, not by the limit. That is what makes it strictly worse than block 1's boundary bug: the fixed window's error is capped at 2×, and this one grows without limit exactly as load grows.

Beyond the toy

INCR solves the fixed-window case in one round trip. The token bucket does not fit in one primitive — "read tokens and timestamp, compute refill, compare, write both" is a read-modify-write over two fields — so the production answer is a Lua script, which Redis executes atomically because it is single-threaded. That is a real cost worth naming: the script is now a deployment artifact that must be versioned, and EVALSHA cache misses after a failover cause a latency spike that looks like a network problem.

Two further failure modes this block does not simulate, both worth a sentence if the interview goes there:

• The round trip is on the hot path. At 1M decisions/s, one RTT per decision is 1M RTTs/s; by Little's law at 0.5 ms that is 500 requests permanently in flight just for rate limiting. This is the arithmetic that motivates leasing.
• A rejected request still costs a round trip. Under a volumetric attack the limiter's own store becomes the bottleneck, which means the thing protecting you is the thing that falls over. The mitigation is a cheap local pre-filter — a per-process token bucket at a generous multiple of the real limit — so that obvious floods never reach the store.

The assembly

Every block above, wired together into one working system:

def assembly(s):
    print("\nSix blocks = a production limiter. One traffic pattern, four algorithms.\n")
    times = boundary_burst()
    algos = [
        ("fixed window",     s["FixedWindow"](5, 1.0)),
        ("sliding log",      s["SlidingLog"](5, 1.0)),
        ("token bucket",     s["TokenBucket"](5.0, 5)),
        ("sliding counter",  s["SlidingCounter"](5, 1.0)),
    ]
    print(f"  {'algorithm':<20}{'allowed':>9}{'burst allowed':>15}"
          f"{'state/client':>14}{'exact':>7}")
    for name, lim in algos:
        got = [lim.allow(t) for t in times]
        burst = sum(got[:20])
        state = {"fixed window": "1 int", "sliding log": "N floats",
                 "token bucket": "2 floats", "sliding counter": "2 ints"}[name]
        exact = "yes" if name == "sliding log" else "no"
        print(f"  {name:<20}{sum(got):>9}{burst:>15}{state:>14}{exact:>7}")
    print("\n  60 requests: a 20-request burst STRADDLING the window boundary at")
    print("  t=1.0, then 40 spread over 20s at the configured rate. Straddling is")
    print("  the whole point -- a burst wholly inside one window is handled")
    print("  identically by all four, so it discriminates nothing. Put the burst on")
    print("  the boundary and the fixed window's 2x failure appears immediately.")
    print("\n  What to say, in order: fixed window is O(1) state and allows 2x at the")
    print("  boundary; sliding log is exact and O(limit) memory per client; token")
    print("  bucket is O(1) state, lazy, and makes burst an explicit parameter;")
    print("  sliding counter is O(1) state and -- per block 4 -- has the SAME 2x")
    print("  worst case as the fixed window, just harder to trigger. Then: none of")
    print("  them survive two servers without a shared store, and the shared store")
    print("  needs ONE atomic operation, and it must fail open.")
    print("\n  Note the burst column: the counter allowed 6, one MORE than the token")
    print("  bucket's 5, on a pattern chosen to embarrass the fixed window. That one")
    print("  request is the whole difference between 'bounded error' as a slogan and")
    print("  as a measurement -- and it is why the token bucket is the answer.")
    print("\n  Built: fixed window -> sliding log -> token bucket -> sliding counter")
    print("  -> distribution -> atomicity.")
    print("  Not built, and worth an extra 10 minutes if the interview goes there:")
    print("  hierarchical limits (per-user AND per-org), cost-weighted requests")
    print("  (an LLM call is not one unit), and the 429 + Retry-After contract.")

def parts():
    """Every mechanism this page builds, ready to import.

        >>> from c03_rate_limiter import parts
        >>> p = parts()
        >>> sorted(p)                      # doctest: +ELLIPSIS
        [...]
    """
    return collect()


def verify():
    """Re-derive every headline claim on this page from scratch."""
    # Rebuild the algorithms independently of the blocks, so a bug in a block
    # cannot make its own claim pass.
    class FW:
        def __init__(s, lim, w): s.lim, s.w, s.c = lim, w, {}
        def allow(s, t):
            k = int(t // s.w); s.c = {k: s.c.get(k, 0)}
            if s.c[k] < s.lim: s.c[k] += 1; return True
            return False
    class SL:
        def __init__(s, lim, w): s.lim, s.w, s.q = lim, w, deque()
        def allow(s, t):
            while s.q and s.q[0] <= t - s.w: s.q.popleft()
            if len(s.q) < s.lim: s.q.append(t); return True
            return False
    class TB:
        def __init__(s, r, b): s.r, s.b, s.tok, s.last = r, b, float(b), 0.0
        def allow(s, t, cost=1.0):
            s.tok = min(s.b, s.tok + (t - s.last) * s.r); s.last = t
            if s.tok >= cost: s.tok -= cost; return True
            return False
    class SC:
        def __init__(s, lim, w): s.lim, s.w, s.k, s.cur, s.prev = lim, w, 0, 0, 0
        def allow(s, t):
            k = int(t // s.w)
            if k != s.k:
                s.prev = s.cur if k == s.k + 1 else 0
                s.cur, s.k = 0, k
            if s.prev * (1.0 - (t % s.w) / s.w) + s.cur < s.lim:
                s.cur += 1; return True
            return False

    adv = [0.98, 0.98, 0.99, 0.99, 0.999, 1.001, 1.001, 1.002, 1.002, 1.003]

    # B1 -- the fixed window admits 2x the limit across a boundary.
    got_fw = sum(FW(5, 1.0).allow(t) for t in adv)
    check("B1  fixed window admits 2x the limit at a boundary",
          got_fw == 10, f"admitted {got_fw} against a limit of 5")

    # B2 -- the sliding log is exact on the same pattern.
    l = SL(5, 1.0); got_sl = sum(l.allow(t) for t in adv)
    check("B2  sliding log is exact on the same pattern",
          got_sl == 5, f"admitted {got_sl}, the correct answer")

    # B2 -- and its state is O(limit) per client, not O(1).
    big = SL(10_000, 60.0)
    for i in range(10_000): big.allow(i * 1e-4)
    check("B2  sliding log state is O(limit) per client",
          len(big.q) == 10_000, f"{len(big.q)*8:,} B for one client at limit=10k")

    # B3 -- the token bucket matches the log's exact answer from two floats.
    t = TB(5.0, 5); got_tb = sum(t.allow(x) for x in adv)
    check("B3  token bucket matches the log's answer",
          got_tb == got_sl, f"admitted {got_tb}, same as the sliding log")

    # B4 -- the sliding counter's worst case tends to 2x, NOT to a small bound.
    worst = 0.0
    for eps in (0.5, 0.9, 0.99):
        sc = SC(100, 1.0)
        for j in range(100): sc.allow(1.0 - 1e-9 * (100 - j))
        adm = sum(sc.allow(1.0 + eps) for _ in range(500))
        worst = max(worst, (100 + adm) / 100)
    check("B4  sliding counter's worst case approaches 2x, like the fixed window",
          1.95 <= worst < 2.0, f"measured {worst:.2f}x at a 0.99s gap")

    # B4 -- and its error is ~0 below the limit but large at/above it.
    def over(mult, n=40_000, seed=5):
        rng = random.Random(seed); sc, hist = SC(100, 1.0), deque()
        tt, bad = 0.0, 0
        for _ in range(n):
            tt += rng.expovariate(100 * mult)
            if sc.allow(tt):
                while hist and hist[0] <= tt - 1.0: hist.popleft()
                if len(hist) + 1 > 100: bad += 1
                hist.append(tt)
        return bad / n
    under, overld = over(0.5), over(1.5)
    check("B4  counter error is zero under the limit",
          under == 0.0, f"{under*100:.2f}% at 0.5x offered load")
    check("B4  ...and 15-25% at or above it",
          0.15 <= overld <= 0.25, f"{overld*100:.2f}% at 1.5x offered load")

    # B6 -- check-then-act admits `workers`, atomic INCR admits `limit`.
    store = {}
    reads = [store.get("k", 0) for _ in range(10)]
    racy = sum(1 for v in reads if v < 5)
    atomic = 0
    store["k"] = 0
    for _ in range(10):
        store["k"] += 1
        if store["k"] <= 5: atomic += 1
    check("B6  GET-then-SET admits one per concurrent worker",
          racy == 10, f"{racy} admitted against a limit of 5")
    check("B6  atomic INCR admits exactly the limit",
          atomic == 5, f"{atomic} admitted")

    # Assembly -- the four algorithms rank as the page claims on the burst.
    times = boundary_burst()
    burst = {name: sum([a.allow(x) for x in times][:20]) for name, a in
             (("fixed", FW(5, 1.0)), ("log", SL(5, 1.0)),
              ("bucket", TB(5.0, 5)), ("counter", SC(5, 1.0)))}
    check("ASM fixed window is the worst on a boundary-straddling burst",
          burst["fixed"] > burst["counter"] >= burst["log"] == burst["bucket"],
          f"fixed {burst['fixed']}, counter {burst['counter']}, "
          f"log {burst['log']}, bucket {burst['bucket']}")

Output:

Six blocks = a production limiter. One traffic pattern, four algorithms.

  algorithm             allowed  burst allowed  state/client  exact
  fixed window               50             10         1 int     no
  sliding log                45              5      N floats    yes
  token bucket               45              5      2 floats     no
  sliding counter            46              6        2 ints     no

  60 requests: a 20-request burst STRADDLING the window boundary at
  t=1.0, then 40 spread over 20s at the configured rate. Straddling is
  the whole point -- a burst wholly inside one window is handled
  identically by all four, so it discriminates nothing. Put the burst on
  the boundary and the fixed window's 2x failure appears immediately.

  What to say, in order: fixed window is O(1) state and allows 2x at the
  boundary; sliding log is exact and O(limit) memory per client; token
  bucket is O(1) state, lazy, and makes burst an explicit parameter;
  sliding counter is O(1) state and -- per block 4 -- has the SAME 2x
  worst case as the fixed window, just harder to trigger. Then: none of
  them survive two servers without a shared store, and the shared store
  needs ONE atomic operation, and it must fail open.

  Note the burst column: the counter allowed 6, one MORE than the token
  bucket's 5, on a pattern chosen to embarrass the fixed window. That one
  request is the whole difference between 'bounded error' as a slogan and
  as a measurement -- and it is why the token bucket is the answer.

  Built: fixed window -> sliding log -> token bucket -> sliding counter
  -> distribution -> atomicity.
  Not built, and worth an extra 10 minutes if the interview goes there:
  hierarchical limits (per-user AND per-org), cost-weighted requests
  (an LLM call is not one unit), and the 429 + Retry-After contract.

Verify the claims

Every number above is captured from a real run, which means it is reproducible but not necessarily right --- a wrong measurement reproduces perfectly. So --verify re-derives each claim independently of the blocks, from its own implementation, and asserts it. A block with a bug cannot make its own claim pass.

$ python3 c03_rate_limiter.py --verify

  [PASS] B1  fixed window admits 2x the limit at a boundary                     admitted 10 against a limit of 5
  [PASS] B2  sliding log is exact on the same pattern                           admitted 5, the correct answer
  [PASS] B2  sliding log state is O(limit) per client                           80,000 B for one client at limit=10k
  [PASS] B3  token bucket matches the log's answer                              admitted 5, same as the sliding log
  [PASS] B4  sliding counter's worst case approaches 2x, like the fixed window  measured 1.99x at a 0.99s gap
  [PASS] B4  counter error is zero under the limit                              0.00% at 0.5x offered load
  [PASS] B4  ...and 15-25% at or above it                                       23.29% at 1.5x offered load
  [PASS] B6  GET-then-SET admits one per concurrent worker                      10 admitted against a limit of 5
  [PASS] B6  atomic INCR admits exactly the limit                               5 admitted
  [PASS] ASM fixed window is the worst on a boundary-straddling burst           fixed 10, counter 6, log 5, bucket 5
  10/10 claims verified

It exits non-zero on any failure, so it runs in CI alongside test_handson.py --- which means a claim on this page cannot silently rot.

The design space

Every rate limiter picks a point on a three-way tradeoff, and the algorithms above are points on that surface rather than competitors:

The row that matters is the last column. The window-based algorithms all express burst implicitly, as a consequence of window length, which means you cannot sell "100/s, bursts to 500" and implement it. The token bucket and GCRA make it a parameter. That, not the boundary bug, is the reason the token bucket is the answer — and it is a product argument that most candidates never reach because they stop at correctness.

What the measurements actually rank

Blocks 2 and 4 measure two of these rows. Extending the same harness across the family, at limit 100 with Poisson arrivals at 1.5× the limit, scoring peak true occupancy rather than how often the estimate was wrong:

On random traffic the sliding window counter is an excellent deal: a 1.11× peak from two integers, matching a ten-bucket log that costs five times the state. Block 4's finding is not that the counter is bad — it is that its adversarial worst case is 2× while the bucketed log's is bounded at \(1 + 1/B\) by construction. Those are different claims about different threat models, and conflating them is how "bounded error" became a slogan.

The practical reading: if your traffic is adversarial, bucket it; if it is merely bursty, the counter is fine and cheaper. An interviewer who asks "how accurate is it" is usually asking which of those two you understand.

Cost model: why distribution dominates everything

The single-node algorithms differ by a few bytes and a few nanoseconds. That difference is irrelevant next to the cost of the shared store, so the cost model that matters is the distributed one.

At 1M decisions/s with one round trip each, Little's law says the in-flight count is

\[ L = \lambda W = 10^6 \times 0.5 \times 10^{-3} = 500 \]

concurrent requests permanently outstanding just for rate limiting, and the store needs 5–10 shards to absorb the ops. That is a real fleet with real failure modes, sitting in front of every request, to enforce a limit.

Leasing is what makes the arithmetic go away. Each process leases a block of \(k\) tokens and enforces locally:

with \(P\) processes. At 50 processes and lease 20 the bound is 1,000 requests of over-admission against whatever the limit is — a number you can write into a contract, which is the property that makes leasing sellable rather than merely cheaper. The full treatment is in d03; the point here is that a 20× infrastructure reduction comes from one design decision, and you can state its exact cost.

Advanced algorithms

• GCRA (Generic Cell Rate Algorithm), from ATM traffic shaping, computes the token bucket's decision from a single theoretical arrival time instead of a token count plus a timestamp. Measured against the block-3 implementation over 5,000 Poisson arrivals, it produced identical decisions on every request (3,984 allowed by both) from one float instead of two. It is what Cloudflare and Envoy's local limiter actually use, and it is the answer to "can you do better than the token bucket" — which is otherwise a question with no good answer.

  \[ \text{allow} \iff \text{now} \geq \text{TAT} - \tau, \qquad \text{TAT} \leftarrow \max(\text{now}, \text{TAT}) + T \]

  with \(T = 1/\text{rate}\) the emission interval and \(\tau = (\text{burst}-1)T\) the burst tolerance. Halving the state matters when the state is a Redis hash field per client per endpoint across a million clients.

• Hierarchical token bucket (HTB), from Linux tc: a tree of buckets where a child may borrow unused capacity from its parent. This is the correct structure for "per-key limit inside per-org limit", and it solves the refund problem noted in block 3 — a request checks the leaf, borrows upward, and there is one debit rather than three that may need unwinding.

• Weighted fair queueing / deficit round robin. The distinction block 5 gestures at: a limiter enforces a contract and a scheduler allocates a scarce resource. When clients contend for capacity rather than each having an independent quota, no limiter is the right tool — you want DRR or a reserved floor per class. This is exactly the split between d03 and d05.

• Sketch-based limiting for unbounded key spaces. Per-client state is affordable for a million known clients and not for an open internet where the key is a source IP. Count-min sketch with a fixed memory budget gives an over-estimate (never under), which is the safe direction: you may throttle an innocent client, you will never miss an abuser. Cloudflare and Fastly both do this at the edge.

Hardware and placement

Where the limiter runs decides what it can be:

• In-process library. Nanoseconds, no failure mode, wrong by \(N\)× across \(N\) processes. Correct for safety limits — protecting a thread pool or a connection pool — where the per-process bound is the thing you actually want.
• Sidecar / service mesh (Envoy's local + global split). Envoy ships exactly the two-tier design block 5 argues for: a local token bucket per proxy for cheap enforcement, plus an optional global service for accuracy. That split is not a compromise, it is the correct architecture, and naming it as prior art is stronger than deriving it.
• Edge / CDN. The only placement where a volumetric attack is stopped before it costs you bandwidth. It is also the placement with the weakest consistency, because edge PoPs are far apart — so edge limits are necessarily approximate and necessarily generous.
• API gateway. Where per-customer contract limits belong, because it is the layer that already knows the customer.

The recurring principle: enforce approximately where it is cheap, account exactly where it is slow. Every mature system in this space converges on it.

How this connects to the rest of the program

• d03 is this page's full design round: leasing, degraded mode weighted by observed traffic share, the reconciliation path, and six hostile critiques.
• d05 is the other kind of limiting — protecting capacity rather than enforcing a contract — and it reaches reserved floors rather than per-client quotas.
• m01 is what happens when the unit is wrong: for LLM serving, requests-per-minute is off by 735× against the resource that actually binds, and the correct unit is KV·seconds. That is the same "what are you actually limiting" question this page opens with, one substrate down.
• The follow-up bank Q53–Q64 is the spoken version of every block here, including the clock choice, the estimate-then-reconcile refund, and why remaining must not lie.
• The diff bank D3 is block 6's race as a code review: an agent removing the lock around a check-then-act, with the measured-GIL argument for why "CPython makes it safe" is not a defence.

Failure modes at scale

• The limiter becomes the outage. A store that fails closed converts a Redis blip into a total outage. Fail open for safety limits; fail closed only for billed contracts, and then only with a local degraded limit so it is not a binary.
• The hot key. One customer's traffic concentrates on one Redis shard. Consistent hashing does not help — the key is the customer. The mitigation is local leasing for exactly the top-N keys, which is the opposite of the usual "shard harder" instinct.
• Retry amplification. A rejected request that retries immediately costs a second round trip, so under overload the limiter's own store load grows with rejection rate. Retry-After with full jitter is the mechanism; an unjittered value synchronises every rejected client and creates the herd it was meant to prevent.
• Clock skew across processes. Every algorithm here uses now. With leasing, two processes disagreeing by 100 ms disagree about which window a request falls in. Use monotonic clocks locally and let the store's clock define window boundaries, fetched on the lease round trip that is already happening.
• Limit changes are not atomic. Raising a customer's limit mid-window with a fixed-window implementation grants the full new limit immediately, on top of what they already spent. The token bucket degrades gracefully here — capacity changes, credit does not — which is one more argument for it.
• The unbounded key space. Per-IP limiting on the open internet is a memory exhaustion attack: the attacker picks the keys. Bound it with a sketch or an LRU, and understand that both mean an abuser can evict an honest client's state.

Primary sources

• Cloudflare, How we built rate limiting capable of scaling to millions of domains (2017) — the sliding window counter and the 0.003% figure that block 4 measures the conditions of.
• Stripe, Scaling your API with rate limiters — the four-limiter taxonomy and the case for separating request-rate from concurrency limits.
• ATM Forum, Traffic Management Specification 4.0 — GCRA, the original virtual scheduling formulation.
• Envoy Proxy documentation, Global rate limiting and Local rate limiting — the two-tier architecture block 5 argues for, in production.
• Devanbu & Shieber, and later Cormode & Muthukrishnan, An Improved Data Stream Summary: The Count-Min Sketch (2005) — bounded-memory limiting over an unbounded key space.
• Amazon Builders' Library, Timeouts, retries, and backoff with jitter — the full-jitter result behind the Retry-After failure mode above.
• Floyd & Jacobson, Random Early Detection (1993) — the intellectual ancestor of probabilistic admission, and the bridge to d05.

What to do with this

Time yourself implementing the sliding-window counter from memory in 15 minutes, then answer the three follow-ups the interviewer always asks: what happens at the boundary, what happens when Redis is down, and how you would test it. Those are in the follow-up bank.

Milestones, experiments, readings and exit criteria for this project: d03 — Distributed Rate Limiter.