Rate Limiting Algorithms: Token Bucket, Leaky Bucket, and Sliding Window, Compared

Every rate limiter trades three things against each other: burst tolerance, memory per client, and how precisely it holds the limit.

“Limit each client to 100 requests per minute” is a one-sentence requirement that hides an entire design space. The moment you try to implement it, you have to answer questions the sentence never asked. Does a client that was quiet for ten minutes get to spend a backlog? What happens at the stroke of the minute? Where does the counter live when you have forty API servers? Do you reject the request, or make it wait?

There are five algorithms worth knowing. Each answers those questions differently, and each is right somewhere.

Fixed window counter

Keep a counter per client per time bucket. user:123:minute:9184 increments on each request, resets when the minute rolls over, rejects above the limit.

It is the cheapest thing that works: one integer per client per window, O(1) to check, trivially implemented with Redis INCR and an EXPIRE. It is also the one with a real flaw, and the flaw is worth internalising because it shows up in production as “our rate limiter doesn’t work.”

The boundary problem. With a limit of 100/minute, a client sends 100 requests at 11:00:59 and another 100 at 11:01:00. Both windows are perfectly within limit. The service just absorbed 200 requests in one second — twice the intended rate, and no rule was broken. Worse, because clients tend to align to clock boundaries (cron jobs, scheduled syncs, retry timers), this is not a theoretical edge case. It is what your traffic actually looks like at :00.

Fixed windows are fine when the limit is a rough quota and a 2× burst is survivable. They are not fine when the limit exists to protect something that will fall over at 2×.

Sliding window log

Store a timestamp for every request. To check a new one, drop every timestamp older than the window and count what remains.

This is exact. There is no boundary artifact, because the window genuinely slides with the current instant — at any moment you are enforcing “at most 100 requests in the trailing 60 seconds,” which is precisely what was asked for.

The cost is memory, and it is not a small cost. You store one entry per request per client for the window duration. A limit of 10,000/hour means up to 10,000 timestamps held per client, and you are paying that for every client simultaneously. Redis sorted sets (ZADD, then ZREMRANGEBYSCORE to trim, then ZCARD) implement this cleanly, which is exactly why so many teams reach for it and then discover their Redis memory graph climbing with traffic.

Use it when precision genuinely matters and the limit is small — per-user login attempts, expensive privileged operations, anything where you will later need to show the exact sequence.

Sliding window counter

The pragmatic middle. Keep two fixed-window counters — current and previous — and interpolate between them weighted by how far into the current window you are:

def allowed(prev_count, curr_count, elapsed_fraction, limit):
    """elapsed_fraction: 0.0 at the start of the current window, 1.0 at the end."""
    estimate = prev_count * (1 - elapsed_fraction) + curr_count
    return estimate < limit

Twenty-five percent into the current minute, you count 75% of the previous minute’s requests plus all of this minute’s. The boundary burst is smoothed away, because those 100 requests at 11:00:59 keep almost all their weight through 11:01:00.

It is an approximation — it assumes requests were spread evenly across the previous window, which they were not — but the error is small and bounded, and the cost is two integers per client instead of thousands of timestamps. For most public APIs this is the correct default, and it is what a lot of production limiters actually run.

Token bucket

A bucket holds up to capacity tokens and refills at rate tokens per second. Each request removes a token; an empty bucket means rejection.

The elegant part is that you never run a refill timer. You store two numbers — the token count and the timestamp of the last update — and compute the refill lazily when a request arrives:

import time
from dataclasses import dataclass

@dataclass
class TokenBucket:
    capacity: float      # burst size
    rate: float          # tokens per second, the sustained limit
    tokens: float
    updated: float

    def allow(self, cost: float = 1.0) -> bool:
        now = time.monotonic()
        # Lazy refill: no background timer, no per-client goroutine.
        self.tokens = min(self.capacity, self.tokens + (now - self.updated) * self.rate)
        self.updated = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True
        return False

Two numbers per client, O(1), no boundary artifact. And it gives you something the window algorithms cannot: two independent dials. rate sets the sustained throughput; capacity sets how large a burst you tolerate. Those are genuinely different policy questions, and a single “100 per minute” number conflates them.

The burst behaviour is usually what you want. A client that has been idle accumulates tokens and can fire a batch immediately — which is exactly how real clients behave, and punishing it achieves nothing. A client that sustains traffic settles into the refill rate.

Note the cost parameter. Because a request can consume more than one token, a token bucket naturally expresses weighted limits: a cheap read costs 1, an expensive aggregation costs 20. Window counters cannot do this without contortions. Hold onto that — it is the whole story for AI APIs.

Leaky bucket

Requests enter a queue; the queue drains at a fixed rate. Overflow is rejected.

The output is perfectly smooth — constant rate, no burst, ever. That is the point, and it is a different guarantee from the token bucket’s. A token bucket smooths the average while permitting spikes. A leaky bucket eliminates spikes entirely.

The cost is latency and queuing. A request that arrives when the queue is deep waits, and waiting requests hold resources. Under sustained overload a leaky bucket adds delay to everything before it starts rejecting anything, which can be worse than rejecting early.

Reach for it when the thing you are protecting genuinely cannot absorb a burst — a legacy system with a hard connection ceiling, a third-party API that bills on peak, a physical device. For most HTTP APIs, a token bucket is the better fit.

The comparison, in one table

Algorithm	Memory/client	Burst	Precision	Best for
Fixed window	1 counter	Up to 2× at boundary	Poor	Rough quotas, cheapest possible
Sliding window log	1 entry per request	None	Exact	Small limits, audit trails, security
Sliding window counter	2 counters	Slight	Good	Sensible default for public APIs
Token bucket	2 numbers	Tunable via capacity	Good	Bursty clients, weighted costs
Leaky bucket	queue	None, by design	Good	Protecting a fragile downstream

Making it work across many nodes

Everything above assumes one counter. You have forty API servers, so the counter has to be shared — and the sharing is where the bugs are.

The race. This is broken:

count = redis.get(key)          # two requests both read 99
if int(count or 0) < limit:
    redis.incr(key)             # both increment
    return ALLOW                # both allowed. Limit exceeded.

Read-modify-write across a network is not atomic, and under exactly the concurrency a rate limiter exists to handle, it fails. The fix is to make the whole decision atomic — a Lua script evaluated server-side in Redis, or a single atomic primitive like INCR (which returns the post-increment value, so you can decide from the result alone) paired with an EXPIRE. Redis Lua scripts execute atomically, which is why nearly every production Redis limiter is a short Lua script rather than application-side logic.

The latency. A network round trip on every request is real overhead, and it puts Redis on the critical path of every single call — including a shared failure mode where your rate limiter takes down the API it was protecting. Decide up front whether an unavailable limiter fails open (allow, protect availability) or fails closed (deny, protect the backend). Both are defensible; the wrong answer is not having decided.

Sharded budgets. The alternative to a shared counter is no shared counter: give each of N nodes limit/N and enforce locally with zero network hops. It is approximate — a client whose traffic lands unevenly gets throttled early — but it is fast and it has no shared failure mode. Some systems reconcile periodically in the background, trading a little staleness for most of the accuracy.

GCRA — the Generic Cell Rate Algorithm, borrowed from ATM networking — deserves a mention as the distributed-friendly option. It stores a single value per client (a “theoretical arrival time”) rather than a counter, which makes it cheap to hold in a shared store and gives leaky-bucket smoothness with token-bucket bookkeeping.

Tell the client what happened

A rate limiter that returns a bare 429 has done half the job. The client now knows it was throttled and has no idea what to do next, so it will guess — usually by retrying immediately, which is the behaviour you were trying to stop.

Return 429 Too Many Requests with a Retry-After header. The status code is defined in RFC 6585 §4 and the header in RFC 9110. A well-behaved client honours it, and — importantly — Retry-After should override the client’s own backoff calculation, because you know your recovery window and the client does not.

Beyond that, publish the budget itself. The IETF’s RateLimit header fields work standardises what many APIs already ship informally: how much quota remains and when it resets. That turns rate limiting from a wall the client discovers by hitting it into a budget the client can pace itself against — which is strictly better for both sides.

And a practical note: rate limit responses should be cheap. If producing a 429 costs a database lookup, an attacker sending 10,000 requests a second still gets 10,000 database lookups a second. Check the limit as early in the request path as you can, ideally at the edge before any expensive work.

Why AI platforms limit tokens, not requests

Here is where the fundamentals stop being generic.

Every algorithm above counts requests, on the implicit assumption that requests cost roughly the same. For an LLM API that assumption is completely false. One call with a 200,000-token context and a long generation can consume hundreds of times the GPU-seconds of a short classification call. A requests-per-minute limit would let a handful of enormous requests saturate a cluster while every client’s dashboard shows them comfortably under quota.

So providers publish two limits: requests per minute and tokens per minute — and in practice the token limit is the one you actually hit. This is the token bucket’s cost parameter doing real work: the bucket is denominated in tokens, and a request withdraws as many as it consumes.

That creates a problem unique to this domain, and it is worth stating plainly: you don’t know a request’s true cost until after it runs. Output tokens are not known in advance. So a token-based limiter has to estimate on admission — input tokens are countable, output can be bounded by max_tokens — and then reconcile against actuals when the response completes. The estimate keeps you from admitting work you cannot afford; the reconciliation keeps the bucket honest over time. Skip the reconciliation and your limiter drifts, usually in the permissive direction.

Three consequences that follow directly, and that I see missed often:

Streaming breaks the accounting. A streamed response occupies capacity for its entire duration, but the token count only finalises at the end. Reserve against your estimate at admission, hold it for the life of the stream, and settle when it closes. A limiter that only debits at completion will happily admit a hundred concurrent long generations it has no capacity for.

Queue, don’t reject, for batch work. The leaky bucket earns its place here. Interactive agent traffic wants fast rejection so it can fail over to another model tier. A nightly batch evaluation job wants to be queued and drained at whatever rate the cluster sustains. Those are different policies on the same resource, and the inference gateway is where you distinguish them.

Per-agent limits, not per-user limits. This is the one that catches teams moving from a chat product to an agentic one. A human generates a few requests per minute. An agent loop running on that human’s behalf generates dozens, sometimes hundreds — and it does so in a tight, correlated burst. A limit sized for human behaviour will throttle your own agents into uselessness, and a limit sized for agents gives a compromised credential enormous room. The unit of limiting has to be the agent session, with its own budget, its own ceiling, and its own identity.

The one thing to take away

Pick the algorithm by asking one question: what does a burst do to the thing I am protecting?

If a burst is harmless and clients are naturally spiky, use a token bucket and size the capacity to the burst you can absorb. If a burst is fatal, use a leaky bucket and pay the latency. If you just need a defensible quota with modest cost, use a sliding window counter. If you need to prove exactly what happened, pay for the log.

Then make the decision atomic, decide whether you fail open or closed, and tell the client what you did. Those three are where the outages come from — not the algorithm.