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

Set a limit of five requests per ten seconds. Now send ten requests between second 8 and second 11. A naive limiter lets all ten through, and it is not buggy: it is doing exactly what "five per ten-second window" literally says. That surprising output, produced below, is the best argument for knowing more than one algorithm. To keep the results exact, every limiter takes the current time as an argument instead of reading a real clock, so each run is deterministic.

import math
from collections import deque


class FixedWindow:
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.current, self.count = None, 0

    def allow(self, now):
        slot = math.floor(now / self.window)      # which window are we in?
        if slot != self.current:
            self.current, self.count = slot, 0    # new window: counter resets
        if self.count < self.limit:
            self.count += 1
            return True
        return False


class SlidingWindowLog:
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.stamps = deque()

    def allow(self, now):
        while self.stamps and self.stamps[0] <= now - self.window:
            self.stamps.popleft()                 # forget requests that aged out
        if len(self.stamps) < self.limit:
            self.stamps.append(now)
            return True
        return False


class TokenBucket:
    def __init__(self, capacity, refill_per_sec):
        self.capacity, self.rate = capacity, refill_per_sec
        self.tokens, self.last = float(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


class LeakyBucketQueue:
    """Shaper: accepted requests wait in a queue served at a fixed rate."""
    def __init__(self, capacity, serve_per_sec):
        self.capacity, self.gap = capacity, 1.0 / serve_per_sec
        self.free_at = 0.0          # when the server finishes everything queued so far

    def schedule(self, now):
        backlog = max(0.0, self.free_at - now) / self.gap
        if backlog >= self.capacity:
            return None             # queue full: reject
        start = max(now, self.free_at)
        self.free_at = start + self.gap
        return start                # time this request will actually be served

The comparison harness below imports those classes and replays two traffic patterns against them. Save the classes above as limiters.py and this as compare.py in the same folder.

from limiters import FixedWindow, SlidingWindowLog, TokenBucket, LeakyBucketQueue


def verdicts(limiter, times):
    return " ".join("ok" if limiter.allow(t) else "--" for t in times)


# Test 1: ten requests straddling the boundary of the 10-second window.
t1 = [8.0, 8.5, 9.0, 9.2, 9.5, 10.0, 10.2, 10.4, 10.6, 10.8]
print("limit 5 per 10 s; request times:", t1)
print("fixed window :", verdicts(FixedWindow(5, 10), t1))
print("sliding log  :", verdicts(SlidingWindowLog(5, 10), t1))

# Test 2: one request, a quiet spell, then 9 at once and a slow trickle.
t2 = [0.0] + [20.0] * 9 + [20.5, 21.0, 21.5, 22.0]
print()
print("capacity 5, rate 2/s; request times:", t2)
print("token bucket :", verdicts(TokenBucket(5, 2), t2))

shaper = LeakyBucketQueue(capacity=5, serve_per_sec=2)
served = [shaper.schedule(t) for t in t2]
print("leaky queue  :", ["rej" if s is None else s for s in served])

limit 5 per 10 s; request times: [8.0, 8.5, 9.0, 9.2, 9.5, 10.0, 10.2, 10.4, 10.6, 10.8]
fixed window : ok ok ok ok ok ok ok ok ok ok
sliding log  : ok ok ok ok ok -- -- -- -- --

capacity 5, rate 2/s; request times: [0.0, 20.0, 20.0, 20.0, 20.0, 20.0, 20.0, 20.0, 20.0, 20.0, 20.5, 21.0, 21.5, 22.0]
token bucket : ok ok ok ok ok ok -- -- -- -- ok ok ok ok
leaky queue  : [0.0, 20.0, 20.5, 21.0, 21.5, 22.0, 'rej', 'rej', 'rej', 'rej', 22.5, 23.0, 23.5, 24.0]

Fixed window: simplest, with a seam

The fixed window keeps one counter per window (seconds 0 to 10, 10 to 20, and so on) and resets it at each boundary. It needs one integer per key and one increment per request, which makes it the easiest to implement in a database or cache. The output shows its flaw: five requests at the end of one window and five at the start of the next are all legal, so a caller can send up to twice the limit within a few seconds around the boundary. If that matters (a login endpoint, a costly downstream call), the plain fixed window is the wrong choice.

Sliding window: accurate, at a price

The sliding window log stores the timestamp of every accepted request and, on each new request, discards those older than the window before counting. It is exact: in the output, the sixth request at 10.0 is refused because five requests are still inside the last ten seconds. The cost is memory proportional to the limit, per key, which is painful for limits like "10,000 per hour". A common compromise is the sliding window counter: keep two fixed-window counters and estimate the rolling count as the current window's count plus the previous window's count weighted by how much of it still overlaps. It uses constant memory and is approximate: it assumes the previous window's requests were evenly spread.

Token bucket: allow bursts, enforce an average

Picture a bucket that holds up to capacity tokens and gains tokens at a steady rate. Each request takes one token; with none left, the request is rejected. The state is just two numbers, the token count and the time it was last updated, and refill is computed lazily on the next request instead of by a background timer. In the output, the caller was idle until time 20, so the bucket was full and five requests of the nine were let through at once (the sixth ok is the earlier request at time 0), after which only the refill rate of two per second applied. This is why token bucket is the most common choice for public APIs: it permits the short bursts that real clients produce while still bounding the long-run average. Burst size is the capacity; sustained rate is the refill rate.

Leaky bucket: smooth the output

The leaky bucket is usually described as a queue with a hole in the bottom. Requests enter the queue; the server drains it at a constant rate; if the queue is full, new requests are dropped. The simulation above implements it as a shaper: it returns the time at which each accepted request will actually be served, spaced 0.5 seconds apart, while the overflow is rejected. The key difference from the token bucket is that the leaky bucket changes the timing of the traffic leaving it, delivering an even stream to a fragile downstream, whereas a token bucket just says yes or no to bursts instantly. A variant of the leaky bucket used purely as a meter, with no queue, behaves nearly the same as a token bucket for admission decisions; the real distinction is whether you hold and pace requests (shaping) or only accept and reject (policing).

Common mistakes

• Using a fixed window for a security limit. Symptom: logs show ten login attempts in two seconds even though the limit is five per ten, because they straddled a boundary.
• Refilling tokens with a timer thread. It leaks resources per key and drifts under load. Compute the refill from elapsed time when a request arrives instead.
• Floating-point drift in tokens. Comparing tokens == 1.0 fails by a hair; compare with >= and cap at capacity, as the code above does.
• Storing a timestamp log for huge limits. Memory grows with the limit times the number of keys. Symptom: the limiter's own memory usage becomes the incident.
• Not capping the bucket. Forgetting min(capacity, ...) lets a caller idle for an hour and then burst thousands of requests.

How this shows up in real projects and interviews

In an interview you are expected to name at least token bucket and sliding window, state the trade-off (burst friendliness against memory and accuracy) and say which you would choose for the case at hand. In real services, token bucket is the usual default, a sliding window counter backs very large limits, and the leaky-bucket idea shows up as a queue in front of fragile dependencies. Most teams do not hand-write these: they configure a gateway or library. Knowing the algorithm still matters, because the documentation's phrase "burst" and "rate" only makes sense once you have seen a bucket fill.