Rate limiting algorithms: token bucket vs sliding window

A rate limiter decides whether a request is allowed based on how many requests the same client has made recently. The four common rate limiting algorithms are fixed window, sliding window log, sliding window counter and token bucket. Fixed window is the simplest but lets through double the limit at window edges; token bucket allows controlled bursts; the sliding window counter is the usual choice when you want a smooth limit at low memory cost.

They all answer the same question with different trade-offs in accuracy, memory and burst behavior. Picking the wrong one rarely causes an outage on its own, but it does decide whether your limit means what your documentation says it means.

What is rate limiting?

Rate limiting caps how many requests a client can make in a period of time, such as 100 requests per minute per API key. The key is whatever identifies the client: a user ID, an API token, an IP address, or a combination. When a client goes over the limit, the server rejects the request, usually with HTTP status 429 Too Many Requests and a Retry-After header saying how long to wait.

You add one for three reasons. It protects shared resources from a single noisy client. It gives paying tiers something concrete to differ on. And it turns runaway clients, like a retry loop with no backoff, into rejected requests instead of database load.

Fixed window: simple, with a gap at the edges

A fixed window counter splits time into buckets aligned to the clock, for example one per minute, and keeps one counter per key per bucket. Each request increments the counter; once it hits the limit, everything else in that minute is rejected.

def allow(key, now, limit=100, window=60):
    bucket = (key, int(now // window))
    if counts.get(bucket, 0) >= limit:
        return False
    counts[bucket] = counts.get(bucket, 0) + 1
    return True

It costs one integer per key and one increment per request. In Redis it is an INCR on a key named after the window, with an expiry so old windows clean themselves up.

The problem is the boundary. A client can send 100 requests at 0:59.9 and another 100 at 1:00.1. Both windows see exactly 100, so all 200 pass. Running that pattern through the code above confirms it: 200 requests accepted in 0.2 seconds against a limit of 100 per minute. If the limit exists to protect a fragile downstream service, that doubled burst is exactly what you were trying to prevent.

Fixed windows also synchronize clients. Everyone who was blocked gets unblocked at the top of the minute, so traffic arrives in a wave.

How does a sliding window fix the boundary problem?

A sliding window measures the last 60 seconds from the current moment instead of from the start of a clock minute. There are two ways to build it.

The sliding window log stores a timestamp for every accepted request. On each new request, drop timestamps older than the window and count what is left.

def allow(log, now, limit=100, window=60):
    while log and log[0] <= now - window:
        log.popleft()           # log is a collections.deque
    if len(log) >= limit:
        return False
    log.append(now)
    return True

This is exact. The same edge burst now gets 100 accepted and 100 rejected. The cost is memory: one entry per accepted request per key. At 100 requests per minute that is fine. At 10,000 per second across a million keys, it is not. In Redis this is typically a sorted set scored by timestamp, trimmed on every request.

The sliding window counter gets close to the same result with two integers. Keep fixed-window counts for the current and previous windows, then weight the previous count by how much of it still overlaps the sliding window:

def allow(key, now, limit=100, window=60):
    w = int(now // window)
    prev = counts.get((key, w - 1), 0)
    cur = counts.get((key, w), 0)
    elapsed = (now - w * window) / window   # 0.0 to 1.0
    estimate = prev * (1 - elapsed) + cur
    if estimate >= limit:
        return False
    counts[(key, w)] = cur + 1
    return True

If the previous minute had 100 requests and you are 25% into the current minute with 20 so far, the estimate is 100 * 0.75 + 20 = 95. Five more are allowed. On the edge burst, this version accepted 101 of 200, one more than the exact log, because it assumes the previous window's requests were spread evenly. That assumption is the whole trade: a small error in exchange for constant memory per key.

How does the token bucket allow bursts?

A token bucket holds up to capacity tokens and refills at a steady rate. Each request takes one token. If the bucket is empty, the request is rejected. You do not need a timer to refill it; store the token count and the last update time, and top up based on elapsed time when the next request arrives.

class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity, self.rate = capacity, rate
        self.tokens, self.last = capacity, 0.0

    def allow(self, now):
        self.tokens = min(self.capacity,
                          self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

Two numbers describe the behavior, which is why this algorithm shows up in so many API gateways. With a capacity of 10 and a rate of 1 per second, a client that has been idle can fire 10 requests at once, and they all pass. Fire 15 and exactly 10 pass. Three seconds later, three more tokens are back. A client flooding at 100 requests per second for a full minute gets 69 through: the initial 10 plus roughly one per second after that.

That is the point of the design. The long-run rate is capped by rate, but short bursts up to capacity are allowed, which fits real clients: a page load that fires eight API calls at once, then goes quiet.

The leaky bucket is the close relative. Instead of allowing bursts, it queues requests and drains them at a fixed rate, smoothing output. Use it when the downstream system needs a steady flow, not when you want to reject quickly.

When should you use which algorithm?

Daily or monthly quotas are fine as fixed windows, since nobody cares about a burst at midnight. Per-second protection for a database is where the sliding counter or token bucket earns its place.

Running a rate limiter across many servers

On one server, any of these is a dictionary. With 30 instances behind a load balancer, each one sees only part of a client's traffic, so per-instance limits let through up to 30 times the intended rate. You need shared state, which usually means Redis or the rate limiting feature of your gateway or edge platform.

Three details decide whether the shared version holds up:

• Make the check-and-update atomic. Reading the count, comparing, and writing back as separate commands lets two servers both read 99 and both allow. Run the logic as one Lua script in Redis, or use a single atomic command where the algorithm allows it.
• Decide what happens when the store is down. Failing open keeps your API up but removes protection; failing closed protects the backend but turns a cache outage into an API outage. Most public APIs fail open with a local fallback limit.
• Limit before expensive work. The check should run at the edge or early in middleware, before authentication lookups or database calls, or the limiter protects nothing.

Rate limits also pair with capacity planning. A limiter sheds excess load per client; it does not replace sizing for the aggregate peak, which is covered in designing for the spike, not the average.

Key takeaways

• Fixed window is cheap but can accept twice the limit across a window boundary.
• The sliding window log is exact but stores one entry per request.
• The sliding window counter approximates the log with two counters and is a strong default.
• Token bucket caps the average rate while allowing bursts up to its capacity.
• In a cluster, keep limiter state shared and update it atomically.

FAQ

What HTTP status code should a rate limiter return?

Return 429 Too Many Requests. Include a Retry-After header with the number of seconds to wait so well-behaved clients can back off instead of retrying immediately.

Is token bucket the same as leaky bucket?

No. A token bucket rejects requests when empty and allows bursts up to its capacity. A leaky bucket queues requests and releases them at a fixed rate, so output is smooth but requests may wait.

Should I rate limit by IP address?

Only as a fallback for unauthenticated traffic. Many users can share one IP behind a NAT or corporate proxy, so limits keyed on an API token or user ID are fairer and harder to dodge.