Rate Limiting Algorithms Compared: Token Bucket vs Sliding Window

"Ten requests per minute per user" sounds like one rule. It is at least four different rules, depending on what "per minute" means, and the four algorithms that implement them disagree about real traffic. The quickest way to understand them is to run all four on the same requests and look at where they disagree.

The problem it solves

A rate limiter decides, per request, whether a client is over its budget. If so, the request is rejected before it reaches anything expensive, normally with 429 Too Many Requests and a Retry-After header. It protects the service from abusive clients, from buggy retry loops, and from one tenant starving the others.

The design questions are always the same three: what exactly counts as "too many", how much memory per client that takes, and how bursty traffic is treated.

The intuition

• Fixed window. Cut time into minutes. Count requests in the current minute; reset at the boundary. One counter per client. The flaw lives at the boundary: a full budget at 0:59 and another full budget at 1:00 are both legal, so a client can land twice the limit inside two seconds.
• Sliding log. Keep the timestamp of every accepted request. On each new one, drop timestamps older than a minute and count the rest. Exact — "no more than ten in any sixty-second span" — but it stores up to limit timestamps per client.
• Sliding window counter. Keep only two counters: this window and the previous one. Estimate the rolling count as the current count plus the previous count weighted by how much of the previous window still overlaps the last sixty seconds. Constant memory, close to the log, but an estimate: it assumes last window's requests were spread evenly.
• Token bucket. A bucket holds up to limit tokens and refills at a steady rate. Each request spends one. An idle client banks tokens up to the cap, so it may burst — but never more than the bucket holds, then it settles to the refill rate. Two numbers per client.

Every algorithm answers "how many recently?" What differs is how precisely "recently" is measured, and whether saved-up quiet time can be spent later.

Watch it run

The animation is the token bucket, with five tokens banked. Watch the level as requests arrive: a burst drains it, the sixth request gets a 429 the instant the bucket is empty — not when some window ends — and then the refill trickles back one token per second, which is exactly the sustained rate the caller settles at.

The code

Four limiters, the same budget of ten requests per sixty seconds, and time passed in explicitly so the results are deterministic.

from collections import deque

LIMIT, WINDOW = 10, 60.0                  # 10 requests per 60 seconds

class FixedWindow:
    def __init__(self): self.win, self.count = None, 0
    def allow(self, now):
        win = int(now // WINDOW)
        if win != self.win:
            self.win, self.count = win, 0     # new window: counter resets
        if self.count < LIMIT:
            self.count += 1
            return True
        return False

class SlidingLog:
    def __init__(self): self.log = deque()
    def allow(self, now):
        while self.log and self.log[0] <= now - WINDOW:
            self.log.popleft()                # forget what aged out
        if len(self.log) < LIMIT:
            self.log.append(now)
            return True
        return False

class SlidingCounter:
    def __init__(self): self.win, self.cur, self.prev = 0, 0, 0
    def allow(self, now):
        win = int(now // WINDOW)
        if win != self.win:
            self.prev = self.cur if win == self.win + 1 else 0
            self.win, self.cur = win, 0
        overlap = 1 - (now % WINDOW) / WINDOW # share of last window still in view
        if self.prev * overlap + self.cur < LIMIT:
            self.cur += 1
            return True
        return False

class TokenBucket:
    def __init__(self):
        self.tokens, self.last = float(LIMIT), 0.0
    def allow(self, now):
        rate = LIMIT / WINDOW                 # tokens per second
        self.tokens = min(LIMIT, self.tokens + (now - self.last) * rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

def admitted(limiter_cls, times):
    lim = limiter_cls()
    return sum(lim.allow(t) for t in times)

edge = [59.0] * 10 + [60.0] * 10          # 20 requests in one second
early_then_later = [float(t) for t in range(10)] + [90.0] * 10

for cls in (FixedWindow, SlidingLog, SlidingCounter, TokenBucket):
    print(cls.__name__, admitted(cls, edge), admitted(cls, early_then_later))
# FixedWindow 20 20
# SlidingLog 10 20
# SlidingCounter 10 15
# TokenBucket 10 20

Two traffic patterns, and they expose different things.

The boundary burst — ten requests at second 59 and ten at second 60. The fixed window admits all twenty, because they fall in two different minutes. Everything else admits ten. This is the fixed window's one weakness, and it is exactly twice the limit, not "a bit more".

Early, then later — ten requests in the first ten seconds, then ten at second 90. By then the first ten are more than sixty seconds old, so the exact answer is: admit all ten again. The log does. The token bucket does, because eighty idle seconds refilled it. The sliding counter admits only five: at second 90 it is halfway through its second window, so it counts half of the previous window's ten — assuming they were spread evenly, when in fact they were all at the start. Its error is the price of keeping two numbers instead of a list.

The complexity

Every one of these is O(1) time per request, except the sliding log, whose cleanup is amortised O(1) — each timestamp is appended once and popped once. The real difference is memory per client:

• Fixed window: one counter and a window id.
• Sliding log: up to limit timestamps. Fine at ten per minute; expensive at ten thousand per hour across a million clients.
• Sliding counter: two counters and a window id.
• Token bucket: a token count and a timestamp.

Where it goes wrong

• Counting per server. With five servers behind a load balancer, a per-process limiter lets each client through five times over. The counter must live in a shared store, and each check becomes a network round trip — often the dominant cost of the whole feature.
• Read-then-write races. Two servers read "9", both allow, both write "10". The check-and-increment must be one atomic operation in the shared store.
• Wall-clock drift. Servers disagreeing about time shift window boundaries. Use the store's clock, or a monotonic one per process.
• Choosing the key. Per IP punishes everyone behind one office network; per API key or account is usually fairer. Many systems layer both.
• Silent rejections. Without Retry-After, well-behaved clients retry immediately and make the overload worse.

Which one to pick

• Token bucket when short bursts are legitimate — a page load that fires twelve calls at once — but the sustained rate must be capped. Two tunable numbers, capacity and refill rate, map directly to "burst" and "sustained".
• Sliding window counter when you want a smooth rolling limit with constant memory and can accept a small approximation.
• Sliding log when the limit must be exact and small, such as login attempts.
• Fixed window when simplicity matters more than the boundary case, such as a daily quota.

A leaky bucket is the token bucket's sibling: requests queue and drain at a fixed rate, which smooths output instead of permitting bursts.

How to say it in an interview

"I would use a token bucket per API key: capacity is the burst we tolerate, the refill rate is the sustained limit, and each client costs two numbers. The state lives in a shared store with an atomic check-and-decrement, so every server agrees. Rejected requests get 429 with Retry-After. If the requirement were a strict rolling limit I would switch to a sliding window counter — constant memory, close to exact — and I would avoid a plain fixed window because it lets twice the limit through at a boundary."