# Commentary: rate-limiter The study guide for [`rate_limiter.py`](rate_limiter.py), and the only documentation this toy has. Read it with the source open beside you. ``` cd rate-limiter python3 demo.py # the aha (§6) python3 test_rate_limiter.py # pins the trace this page describes ``` Stdlib only, no dependencies, no setup. **Environment for every transcript below:** macOS (Darwin 25.5.0, arm64), `Python 3.15.0a8 (main, Apr 14 2026, 14:20:41) [Clang 22.1.3]`. **The files:** [`rate_limiter.py`](rate_limiter.py) is the toy (52 lines, two classes); [`demo.py`](demo.py) drives both with one trace; [`test_rate_limiter.py`](test_rate_limiter.py) locks that trace in. --- ## Contents 1. [Orientation](#1-orientation) 2. [The problem this mechanism exists to solve](#2-the-problem-this-mechanism-exists-to-solve) 3. [Background you need](#3-background-you-need) 4. [The mental model](#4-the-mental-model) 5. [Reading the source](#5-reading-the-source) 6. [The demo, and what it proves](#6-the-demo-and-what-it-proves) 7. [Design decisions and roads not taken](#7-design-decisions-and-roads-not-taken) 8. [What's simplified vs. the real thing](#8-whats-simplified-vs-the-real-thing) 9. [Check yourself](#9-check-yourself) 10. [Further reading](#10-further-reading) --- ## 1. Orientation This toy implements two rate limiters — a **token bucket** and a **sliding window log** — and tunes them to the *same* average rate: five requests per five seconds. If a rate limit were a single well-defined idea, two correct implementations of "5 per 5s" would agree on every request. They don't. Fed one identical trace, they disagree twice, in opposite directions. By the end you should be able to: - state what each algorithm actually stores, and why that storage choice determines its entire personality; - predict, by arithmetic rather than intuition, which limiter admits a given request; - explain why the phrase "5 requests per 5 seconds" is *underspecified*, and what question you have to answer to make it precise; - recognise which of the two a system you're using has picked, from its observable behaviour alone. The last one is the real payoff. "Rate limited" is a thing you will read in someone else's API docs, and the docs will usually not tell you which algorithm is behind it. --- ## 2. The problem this mechanism exists to solve A shared resource — an API, a database, a mail relay — has finite capacity. Demand for it does not politely stay under that capacity. A rate limiter is the component that decides, per request, whether serving it is affordable, and it exists for at least four distinct reasons that often get conflated: - **Protecting capacity.** Beyond some arrival rate the service degrades for everyone. Shedding load early is better than collapsing late. - **Fairness between clients.** Without a limit, one aggressive caller consumes the capacity that the other thousand were relying on. This is the reason most public APIs give. - **Cost control.** When a request costs real money downstream (an LLM token, an SMS, a third-party call), the limiter is a budget. - **Abuse and brute-force resistance.** Ten password attempts per hour is a rate limit whose purpose is security, not capacity. These pull in different directions, which is why there is no single correct algorithm. A capacity-protection limiter wants to *smooth* traffic — the thing that hurts the server is the instantaneous spike. A fairness limiter wants to *count exactly* — the thing that matters is the total each client consumed. Those two goals produce the two algorithms in this toy. The crucial observation, and the one this toy is built to force: **"5 requests per 5 seconds" does not specify a behaviour.** It leaves open the question *which five seconds?* Every rate-limiting algorithm is an answer to that question, and the answers are not equivalent. --- ## 3. Background you need None of this is deep, but the commentary below leans on it. | Concept | Where it's used here | One source | |---|---|---| | **Burst vs. sustained rate** | The entire point of the toy — two limiters with identical sustained rates and different burst behaviour | [Token bucket § Burst size](https://en.wikipedia.org/wiki/Token_bucket) | | **Amortized analysis** | Why the eviction `while` loop in `SlidingWindowLog.allow` is O(1) per call despite being a loop | [Amortized analysis](https://en.wikipedia.org/wiki/Amortized_analysis) | | **`deque` vs. `list`** | Why the log is a `deque`: `popleft()` is O(1), `list.pop(0)` is O(n) | [`collections.deque`](https://docs.python.org/3/library/collections.html#collections.deque) | | **Monotonic vs. wall-clock time** | Why `allow()` takes `now` as a parameter instead of calling a clock | [`time.monotonic`](https://docs.python.org/3/library/time.html#time.monotonic) | **The two that carry the result** are the first and the last. Burst-vs- sustained is the whole aha; if you only internalise one row, take that one. Dependency injection of `now` is what makes the aha *checkable* — without it this toy would need `sleep()` calls and would be untestable and non-reproducible. --- ## 4. The mental model Before any code. Both limiters answer "may this request proceed?", but they hold completely different things in memory. ``` TOKEN BUCKET — holds one number. refill: +1 token/sec, continuously │ ▼ ┌───────────┐ capacity = 5 (overflow is discarded) │ ▓ ▓ ▓ ░ ░ │ └───────────┘ │ request takes 1 token; no token, no service SLIDING WINDOW LOG — holds a timestamp per request. log: [ 0.0 0.0 0.0 0.0 0.0 ] 5 entries → full ▲ ├─────── window = 5s ──────┤ └─ anything older than this is dropped on the next call request admitted iff fewer than 5 entries remain after dropping ``` The difference in *storage* is the difference in *personality*, and it is worth stating as a slogan before you read a line of code: - The bucket remembers **how much credit you have**. Credit accrues continuously and is capped. It has no idea when your past requests happened; that information was folded into a single number and thrown away. - The log remembers **exactly when each request happened**. It can answer "how many in the last 5 seconds?" precisely, because it kept the receipts. Everything that follows is a consequence of that one distinction. --- ## 5. Reading the source The file is 52 lines. Read it in this order. ### 5.1 The interface decision, made in the docstring ```python """Two rate-limiting algorithms, side by side: token bucket and sliding window log. Both expose the same interface: allow(now) -> bool, where `now` is a caller-supplied timestamp (seconds), so behavior is deterministic and testable without real clocks or sleeps. """ ``` `rate_limiter.py:1-5` The single most consequential design decision in the toy is in this docstring, not in any class: **`now` is a parameter, not something the code fetches.** Had `allow()` called `time.monotonic()` internally, the demo would need real `sleep()` calls, would take five seconds to run, and — worse — would produce *slightly different output on every run*, because the burst at "t=5.0" would really land at 5.0003. The boundary behaviour that is half the aha would become a coin flip. Injecting the clock makes the toy a pure function of its trace: same input, same output, forever. This is not just a testing trick; it is what production limiters do too, for a different reason. A limiter running on many machines must agree on what time it is, and the wall clock is *not* a safe source: NTP can step it backwards, and a backwards jump makes `elapsed` negative and quietly *removes* tokens. Real implementations use a monotonic source, or the storage layer's own clock (Redis's `TIME`), precisely so no client's skewed clock can corrupt the shared state. ### 5.2 `TokenBucket.__init__` — the whole state is one float ```python def __init__(self, capacity, refill_rate): self.capacity = capacity self.refill_rate = refill_rate self.tokens = capacity self.last_refill = 0.0 ``` `rate_limiter.py:15-19` Two config values and two state values. Note `self.tokens = capacity` — a fresh bucket starts **full**, so a brand-new client may immediately burst. That is a deliberate and near-universal choice (it means a client who has never been seen isn't punished), but it has a real consequence: if your limiter's state is evicted from cache and recreated, the client silently gets a fresh full burst. Cache eviction becomes a rate-limit bypass. `last_refill` is the interesting field. It exists so that refill can be computed *lazily*. ### 5.3 `TokenBucket.allow` — continuous refill without a timer ```python def allow(self, now): elapsed = now - self.last_refill self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate) self.last_refill = now if self.tokens >= 1: self.tokens -= 1 return True return False ``` `rate_limiter.py:21-29` Nine lines containing three ideas worth slowing down for. **Lazy refill.** The mental model says tokens arrive continuously. A naive implementation would need a background thread ticking `tokens += 1` every second — per client, forever, for millions of idle clients. Instead the bucket computes what *would* have accumulated since it was last touched, at the moment it's next touched. Work happens only on request, and the answer is identical to the continuous model. This lazy-evaluation-of-elapsed-time trick is the standard implementation of every token bucket you will meet. **`min(self.capacity, ...)` is the entire burst policy.** Delete the `min` and an idle client accrues unbounded credit; come back after a day and fire 86,400 requests at once. The cap is what makes the bucket a *rate* limiter rather than a *quota*. `capacity` and `refill_rate` are therefore two genuinely independent knobs: the rate sets what you may sustain, the capacity sets how much you may spend at once. This toy sets `refill_rate = capacity / window`, which ties them together and is what makes the comparison against the window fair — but they need not be tied. **Tokens are fractional; admission is integral.** `self.tokens` is a float that happily sits at 2.5, but the test is `>= 1`. Partial credit accumulates and is never lost to rounding. This is why the bucket can be *precisely* fair over time while still making yes/no decisions — and, as you'll see in §6, that stored fraction is exactly what makes the second divergence happen. ### 5.4 `SlidingWindowLog.__init__` — keeping the receipts ```python def __init__(self, max_requests, window): self.max_requests = max_requests self.window = window self.log = deque() ``` `rate_limiter.py:38-41` A `deque`, not a `list`, and that is load-bearing. Eviction always removes from the *front* (oldest first). `list.pop(0)` is O(n) — it shifts every remaining element down one slot — so a list-backed log would degrade quadratically exactly when it's busiest. `deque.popleft()` is O(1). ### 5.5 `SlidingWindowLog.allow` — evict, then count ```python def allow(self, now): cutoff = now - self.window while self.log and self.log[0] <= cutoff: self.log.popleft() if len(self.log) < self.max_requests: self.log.append(now) return True return False ``` `rate_limiter.py:43-51` **The `while` loop is O(1) amortized, not O(n).** It looks like a scan, and a single call can indeed pop many entries — but every entry is appended exactly once and popped at most once, so the total popping across N calls is bounded by N. The cost per call *averages* to a constant. A worst-case single call can still be slow, which matters if you're chasing tail latency, but the throughput is linear. **The `<=` is not a detail.** `cutoff = now - window`, and an entry is evicted when it is `<= cutoff` — that is, an entry exactly `window` seconds old is considered expired. At `t=5.0` with a 5-second window, `cutoff = 0.0`, and the entries recorded at `0.0` satisfy `0.0 <= 0.0`. All five are dropped and the window is empty. Change that one character to `<` and the entries survive, because `0.0 < 0.0` is false. I ran both against the demo trace rather than reasoning about it: ``` === Claim 2: is the `<=` in the eviction cutoff load-bearing? === <= (as written) burst #2 at t=5.0: [True, True, True, True, True] < (counterfactual) burst #2 at t=5.0: [False, False, False, False, False] ``` One character flips the result from *all five admitted* to *all five rejected*. Half this toy's headline aha rests on it. This is also a fair warning about the algorithm in general: its behaviour at the exact boundary is a judgement call, and the two defensible answers are maximally different. Note also the ordering: eviction happens **before** the length check, and the append happens **only on success**. A denied request leaves no trace, so being rejected does not extend your penalty — a client hammering a limiter it has already saturated doesn't dig itself deeper. (Some production limiters deliberately choose the opposite, recording denials too, to punish hammering.) --- ## 6. The demo, and what it proves `demo.py` drives both limiters with one trace: a burst of 5 at `t=0`, a single request at `t=2.5`, then another burst of 5 at exactly `t=5.0`. ```python TRACE = ( [(0.0, "burst #1") for _ in range(5)] + [(2.5, "lone request")] + [(5.0, "burst #2") for _ in range(5)] ) ``` `demo.py:12-16` Both are configured for the same average rate — `refill_rate = CAPACITY / WINDOW` = 1.0 tokens/sec, versus 5 requests per 5s window: ```python bucket = TokenBucket(capacity=CAPACITY, refill_rate=CAPACITY / WINDOW) window = SlidingWindowLog(max_requests=CAPACITY, window=WINDOW) ``` `demo.py:20-21` Running it: ``` $ python3 demo.py t event token bucket sliding window 0.0 burst #1 allow allow 0.0 burst #1 allow allow 0.0 burst #1 allow allow 0.0 burst #1 allow allow 0.0 burst #1 allow allow 2.5 lone request allow DENY <-- differ! 5.0 burst #2 allow allow 5.0 burst #2 allow allow 5.0 burst #2 allow allow 5.0 burst #2 allow allow 5.0 burst #2 DENY allow <-- differ! ``` ### 6.1 Divergence one, at t=2.5: the bucket allows, the log denies **Bucket.** After burst #1 it holds 0 tokens, `last_refill = 0.0`. At `t=2.5`: `elapsed = 2.5`, so `tokens = min(5, 0 + 2.5 × 1.0) = 2.5`. Since `2.5 >= 1`, admit, leaving **1.5**. The bucket has been quietly refilling and has credit to spend. **Log.** `cutoff = 2.5 - 5.0 = -2.5`. Every entry sits at `0.0`, and `0.0 <= -2.5` is false, so nothing is evicted. `len(log) == 5`, which is not `< 5`. Deny. All five original requests are still inside the trailing five-second window, so by an exact count the client has already spent its allowance. Both are *correct* readings of "5 per 5 seconds." They disagree because they answer *which five seconds?* differently: the log means "the last five seconds, right now"; the bucket means "amortised, continuously." ### 6.2 Divergence two, at t=5.0: the log allows all five, the bucket denies the last **Log.** `cutoff = 0.0`. The five entries at `0.0` satisfy `0.0 <= 0.0` and are all evicted (§5.5). The log is empty; five appends all succeed. The window rolled over and the allowance reset **completely and instantly**. **Bucket.** It carried 1.5 tokens out of `t=2.5`, and gains `2.5 × 1.0 = 2.5` more, for `4.0`. Four requests are admitted, draining it to `0.0`; the fifth finds `0.0 >= 1` false and is denied. Recovery is *gradual*: the bucket never hands back a full allowance at an instant. ### 6.3 The two divergences are the same event Here is the part the summary tables miss. The bucket denies the fifth request at `t=5.0` **because** it allowed the lone request at `t=2.5`. That earlier `allow` spent a token that never came back. Remove it from the trace and the bucket arrives at `t=5.0` with a full 5.0 tokens and admits all five. Rather than assert that, I ran it: ``` === Claim 1: does the lone t=2.5 request cause the t=5.0 denial? === with the lone request: [True, True, True, True, False] without it: [True, True, True, True, True] ``` So this isn't two unrelated quirks. It's one property — **the bucket has memory that decays smoothly, the log has memory that expires in a cliff** — observed from two sides. The bucket's generosity at 2.5 *is* its stinginess at 5.0. The log's stinginess at 2.5 *is* its generosity at 5.0. ### 6.4 The trace is pinned by a test ``` $ python3 test_rate_limiter.py PASS test_demo_trace_divergence PASS test_bucket_never_exceeds_capacity_after_long_idle PASS test_bucket_steady_state_rate PASS test_window_evicts_entries_older_than_window All 4 tests PASSED ``` `test_demo_trace_divergence` (`test_rate_limiter.py:12-33`) asserts the exact divergence above, so the claim in this commentary can't rot silently. The other three are unit checks: the cap holds after a long idle, the drained bucket admits one request per `1/refill_rate` seconds, and eviction drops entries at the boundary. ### 6.5 The boundary condition — when none of this matters Worth naming so you can place your own system. The two algorithms converge to identical behaviour when **no burst ever exceeds the limit** — a client sending one request per second against "5 per 5s" is admitted by both, always, and the choice is irrelevant. The divergence only appears when traffic is *clumpy* relative to the window. If your traffic is smooth, pick either and spend your attention elsewhere. --- ## 7. Design decisions and roads not taken ### 7.1 Why these two, and not the fixed-window counter? The obvious third algorithm — bump a counter, reset it every 5 seconds — is absent on purpose. It's cheap (one integer per client) and it's what people reach for first, but it has a notorious flaw: a client can fire the full allowance at the very end of one window and again at the start of the next, achieving **twice** the intended rate across the boundary. The sliding window log exists precisely to fix that. Including the broken version would have made the toy a survey of three algorithms rather than a sharp comparison of the two real trade-offs. If you want to feel it, it's a five-line class — write it and run the demo trace through it. ### 7.2 Why the log, given that it's the expensive one? This is the honest tension, and it is worth being precise about, because the obvious version of the criticism is wrong. Per client, the bucket stores **two floats, forever**, whatever the traffic. It's tempting to say the log stores one timestamp per request — but read §5.5 again: `append` happens only inside the `len(self.log) < self.max_requests` branch, so the log *cannot* grow past `max_requests`. I checked: ``` === Q2 / memory: how large does SlidingWindowLog.log actually get? === 1000 requests, max_requests=5 -> len(log) = 5 ``` A thousand requests, five entries. So memory is **O(max_requests) per client** — proportional to the *limit you configured*, not to the traffic you receive. That's a much better property than the naive reading suggests, and it means a client hammering you does not cost you extra memory. It's still meaningfully worse than the bucket, though, because limits are often large. "10,000 requests per hour" means up to 10,000 timestamps resident per active client, against the bucket's two floats — a ~40,000× difference in state for the same policy, multiplied by every client you're tracking. The log is here because it's the *exact* answer, and the exact answer is the right thing to compare an approximation against. In production the usual choice is a third option that this toy deliberately doesn't implement: the **sliding window counter**, which keeps two fixed-window counters and blends them by how far into the current window you are. Cloudflare's formula: > `rate = 42 * ((60-15)/60) + 18 = 42 * 0.75 + 18 = 49.5 requests` That's O(1) memory, no boundary doubling, and a small approximation error — it assumes the previous window's requests were spread evenly, which they weren't. For nearly all real workloads that error is irrelevant and the memory saving is not. ### 7.3 Why `allow(now)` rather than `allow()` Covered in §5.1, but to state the trade-off plainly: pushing the clock to the caller makes the library deterministic and testable at the cost of a slightly awkward API. A production version would wrap it — `allow()` calling `allow_at(time.monotonic())` — to get both. This toy skips the wrapper because the whole point is that you supply the trace. ### 7.4 Why two classes and no shared base class They implement the same interface and share zero code, which is a fair description of the algorithms themselves. An `ABC` with an abstract `allow` would add a file's worth of ceremony and hide the thing worth seeing: that these two have almost nothing in common beyond their signature. --- ## 8. What's simplified vs. the real thing - **One client.** Both classes are a single limiter instance. Real systems key state per API key or IP, which turns "two floats" into "two floats × millions" and makes eviction policy a design problem of its own. - **One process.** State is in memory. The moment you have two servers, each enforces the limit independently and a client gets 2× the intended rate. Real deployments push state into a shared store (usually Redis) — and then inherit a distributed-systems problem: the read-modify-write must be atomic (a Lua script or `INCR`-based trick), and every check now costs a network round trip. - **No concurrency control.** `allow()` is not thread-safe. Two threads can both read `self.tokens == 1`, both decrement, and admit two requests on one token. A real implementation needs a lock, or an atomic operation in the backing store. - **Rejection is binary.** These return `False`. Real limiters usually *queue and delay* rather than reject (nginx's `limit_req` does this by default, rejecting only once the queue exceeds `burst`), and return `429` with a `Retry-After` telling the client when to come back — which the bucket can compute exactly and the log can too. - **No cost weighting.** Every request costs one token. Real APIs charge variable cost per endpoint — a bulk export costs more than a health check — which the bucket supports naturally (`tokens -= cost`) and the log does not. - **Eviction is lazy, and only the log's own client triggers it.** Entries leave `self.log` only when `allow()` is next called. A client that goes silent leaves up to `max_requests` timestamps resident indefinitely — the memory is bounded (§7.2) but not *reclaimed*. Multiply by every client you have ever seen and you need a real eviction policy for the limiters themselves, which is a second, separate cache-expiry problem this toy doesn't have because it holds exactly one limiter. --- ## 9. Check yourself Answer before expanding. Each answer is derivable from the source. **Q1.** A client is idle for an hour, then fires 10 requests at once. How many does `TokenBucket(capacity=5, refill_rate=1.0)` admit?
Answer Five. `elapsed` is 3600, so `3600 × 1.0 = 3600` tokens *would* accrue, but `min(self.capacity, ...)` clamps to 5. Five requests drain it; the sixth finds `0.0 >= 1` false. This is `test_bucket_never_exceeds_capacity_after_long_idle` (`test_rate_limiter.py:36-42`), which uses `t=1000.0` and asserts exactly `[True, True, True, True, True, False]`.
**Q2.** The sliding window log resets as a cliff (§6.2). Can you exploit that the way you'd exploit a fixed-window counter — 5 requests at `t=4.999`, then 5 more at `t=5.0`, for 10 in a millisecond?
Answer No, and this is the log's whole reason for existing. I tried both timings: ``` 5 at t=4.999 then 5 at t=5.000 -> second burst: [False, False, False, False, False] 5 at t=0.000 then 5 at t=5.000 -> second burst: [True, True, True, True, True] ``` The cliff is measured **per entry**, not against a shared clock. At `t=5.0` the cutoff is `0.0`, and entries stamped `4.999` are nowhere near expiring — so the second burst is denied outright. Only entries genuinely `window` seconds old drop out, which is why the two bursts in the working case are a full 5 seconds apart. That's the difference between a *sliding* window and a *fixed* one. A fixed window counter shares one reset instant across all clients, so straddling it gives 2× the limit. The log gives each request its own expiry, so it admits at most `max_requests` in any window-length interval — exactly what it says on the tin. It's the fixed-window counter that has the boundary bug, not this.
**Q3.** You swap `self.tokens >= 1` for `self.tokens > 0`. What breaks?
Answer The bucket starts admitting on *partial* credit, letting the balance go negative. Sending three requests at `t=2.5` (where the bucket holds 2.5 tokens) shows it: ``` t=2.5 allow -> True, tokens now 1.5 t=2.5 again -> True, tokens now 0.5 t=2.5 again -> True, tokens now -0.5 ``` The third is admitted on half a token. The real code denies it (`0.5 >= 1` is false), so this variant admits one extra request in every drain. It is *not* an unlimited overdraft, though — a fourth request finds `-0.5 > 0` false and is denied, and since `min(capacity, tokens + elapsed × rate)` never floors at zero, the debt is real and must be waited off before anything is admitted again. So the long-run average rate is still honoured. What changes is the shape at the margin: you've traded a clean "no token, no service" rule for a borrow-then-repay one, and made the state able to represent a debt you now have to reason about.
**Q4.** Why does `SlidingWindowLog.allow` append `now` only when returning `True`?
Answer So denials don't count against the client. If rejected requests were logged, a client that keeps retrying while limited would keep its own window permanently full and never recover — the limiter would punish retrying rather than just throttling it. Some production limiters deliberately do log denials to discourage hammering, but that's a policy choice, not the default reading of "5 requests per 5 seconds."
**Q5.** Your API is behind three load-balanced servers, each running this `TokenBucket` in memory. A client's effective rate limit is what?
Answer Up to 3× the intended limit — each server enforces 5-per-5s against the share of traffic it happens to see, and the shares are independent. Worse, it's *non-deterministic*: it depends on how the balancer distributes that client's requests. This is the single biggest gap between the toy and production, and it's why real limiters keep state in a shared store rather than in process memory. See §8.
--- ## 10. Further reading Every link below was fetched and confirmed live when this was written. - **[Stripe: Scaling your API with rate limiters](https://stripe.com/blog/rate-limiters)** — the best practitioner's account of *why* you'd run several different limiters at once (request-rate, concurrency, fleet-usage, worker-utilisation) rather than one. Stripe uses the token bucket. Start here. - **[Cloudflare: How we built rate limiting capable of scaling to millions of domains](https://blog.cloudflare.com/counting-things-a-lot-of-different-things/)** — the sliding window *counter* from §7.2, including the blending formula and the memory argument that makes it worth the approximation error. - **[Brandur Leach: Rate Limiting, Cells, and GCRA](https://brandur.org/rate-limiting)** — the Generic Cell Rate Algorithm, which tracks a single "theoretical arrival time" instead of tokens or timestamps. A genuinely different third answer to "which five seconds?", and O(1) like the bucket but with the log's exactness. - **[Wikipedia: Token bucket](https://en.wikipedia.org/wiki/Token_bucket)** — the formal treatment, the maximum-burst-size arithmetic, and the relationship to the leaky bucket (each is the other's mirror image). - **[nginx `ngx_http_limit_req_module`](https://nginx.org/en/docs/http/ngx_http_limit_req_module.html)** — a production limiter you can read the config language of. Note it *delays* excess requests rather than rejecting them, and that `burst` is a separate knob from `rate` — exactly the `capacity`-vs-`refill_rate` split from §5.3.