Commentary: rate-limiter

Two limiters tuned to the same average rate, fed one identical trace, disagreeing twice — in opposite directions. A study guide for rate_limiter.py.

cd rate-limiter
python3 demo.py              # the aha (§6)
python3 test_rate_limiter.py # pins the trace this page describes

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 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.

3. Background you need

None of this is deep, but the commentary below leans on it.

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.

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 admitted 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

"""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.
"""

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

    def __init__(self, capacity, refill_rate):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self.last_refill = 0.0

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 (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

    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

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

    def __init__(self, max_requests, window):
        self.max_requests = max_requests
        self.window = window
        self.log = deque()

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

    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

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:

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.

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.

TRACE = (
    [(0.0, "burst #1") for _ in range(5)]
    + [(2.5, "lone request")]
    + [(5.0, "burst #2") for _ in range(5)]
)

Both are configured for the same average rate — refill_rate = CAPACITY / WINDOW = 1.0 tokens/sec, versus 5 requests per 5s window:

    bucket = TokenBucket(capacity=CAPACITY, refill_rate=CAPACITY / WINDOW)
    window = SlidingWindowLog(max_requests=CAPACITY, window=WINDOW)

Running it:

python3 demo.py

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:

6.4 The trace is pinned by a test

python3 test_rate_limiter.py

test_demo_trace_divergence (test_rate_limiter.py lines 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

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:

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 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:

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 so can the log.
• 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, a second and 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.

10. Further reading

Every link below was fetched and confirmed live when this was written.

• Stripe: Scaling your API with 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 — 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 — 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 — 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 — 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.