Token Bucket vs. Sliding Window: Building Rate Limiters That Actually Hold Under Load

Rate limiting sounds like a solved problem until you actually implement one and watch it fail in a way your load test didn't predict: legitimate bursts getting rejected, or a limiter that lets through 2x its stated limit at window boundaries. The failure modes are specific enough that it's worth working through the two dominant algorithms — token bucket and sliding window — with actual code, not just the diagrams.

The problem with fixed windows

The naive approach almost everyone reaches for first is a fixed window counter: pick a window size (say, 60 seconds), count requests in that window, reset the counter when the window rolls over.

import time

class FixedWindowLimiter:
    def __init__(self, limit: int, window_seconds: int):
        self.limit = limit
        self.window_seconds = window_seconds
        self.count = 0
        self.window_start = time.time()

    def allow(self) -> bool:
        now = time.time()
        if now - self.window_start >= self.window_seconds:
            self.window_start = now
            self.count = 0
        if self.count < self.limit:
            self.count += 1
            return True
        return False

This is simple and cheap, and it's also broken in a specific, exploitable way. Say the limit is 100 requests/minute. A client can send 100 requests in the last second of window N, then another 100 in the first second of window N+1. That's 200 requests in roughly two seconds, well within the letter of "100/minute" as the code enforces it, but nowhere near the spirit of it. This is the classic boundary-burst problem, and it's the reason fixed windows get replaced once traffic is adversarial or bursty enough to find the seam.

Sliding window: smoothing the boundary

A sliding window log fixes this by tracking actual timestamps instead of a single counter, and counting how many fall within the trailing window at the moment of the request:

from collections import deque
import time

class SlidingWindowLogLimiter:
    def __init__(self, limit: int, window_seconds: float):
        self.limit = limit
        self.window_seconds = window_seconds
        self.timestamps = deque()

    def allow(self) -> bool:
        now = time.time()
        cutoff = now - self.window_seconds
        while self.timestamps and self.timestamps[0] < cutoff:
            self.timestamps.popleft()
        if len(self.timestamps) < self.limit:
            self.timestamps.append(now)
            return True
        return False

This is exact — no boundary exploit — but it costs memory proportional to the request rate, since you're storing a timestamp per request within the window. For a single client that's fine. For a service rate-limiting thousands of distinct API keys, storing an unbounded deque per key is a real cost, and it's the reason production systems usually use an approximation instead of the exact log.

Sliding window counter: the practical middle ground

The approximation that shows up in most real infrastructure (this is roughly what Cloudflare and several API gateways describe publicly) is the sliding window counter: keep two fixed-window counters, the current one and the previous one, and weight the previous window's count by how much of it still overlaps the trailing window.

import time

class SlidingWindowCounterLimiter:
    def __init__(self, limit: int, window_seconds: float):
        self.limit = limit
        self.window_seconds = window_seconds
        self.curr_window = 0
        self.curr_count = 0
        self.prev_count = 0

    def _window_id(self, now: float) -> int:
        return int(now // self.window_seconds)

    def allow(self) -> bool:
        now = time.time()
        window = self._window_id(now)

        if window != self.curr_window:
            if window == self.curr_window + 1:
                self.prev_count = self.curr_count
            else:
                self.prev_count = 0
            self.curr_count = 0
            self.curr_window = window

        elapsed_in_curr = now - (window * self.window_seconds)
        weight = max(0.0, (self.window_seconds - elapsed_in_curr) / self.window_seconds)
        estimated = self.curr_count + self.prev_count * weight

        if estimated < self.limit:
            self.curr_count += 1
            return True
        return False

This trades exactness for O(1) memory per client, and the error it introduces is bounded and well understood: it assumes requests are uniformly distributed within the previous window, which is an approximation, not a guarantee. In practice the deviation from the true sliding-window-log count is small enough to be irrelevant for the rate limits most APIs actually enforce.

Token bucket: allowing controlled bursts on purpose

Both algorithms above treat any burst as something to suppress. Token bucket takes a different stance: it explicitly allows bursts up to a configured size, while still enforcing a long-run average rate. This matches how a lot of real traffic actually behaves — a client that's been idle for a while and then needs to catch up shouldn't be penalized as harshly as one hammering the endpoint continuously.

The mechanism: a bucket holds up to capacity tokens. Tokens refill continuously at rate tokens/second. Each request consumes one token; if the bucket is empty, the request is rejected.

import time
import threading

class TokenBucketLimiter:
    def __init__(self, rate: float, capacity: float):
        self.rate = rate
        self.capacity = capacity
        self.tokens = capacity
        self.last_refill = time.monotonic()
        self.lock = threading.Lock()

    def allow(self, cost: float = 1.0) -> bool:
        with self.lock:
            now = time.monotonic()
            elapsed = now - self.last_refill
            self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
            self.last_refill = now

            if self.tokens >= cost:
                self.tokens -= cost
                return True
            return False

Two details here matter more than they look:

1. time.monotonic(), not time.time(). Wall-clock time can jump backward (NTP adjustment, manual clock change) and a backward jump would let elapsed go negative, which either refills nothing or, worse, corrupts the token count depending on how you guard it. Monotonic clocks never go backward within a process's lifetime, which is exactly the guarantee a refill calculation needs.
2. The lock. A rate limiter is almost always shared across concurrent request handlers. Without the lock, two threads can both read self.tokens as sufficient, both decrement, and let through one more request than the bucket should have allowed — a classic check-then-act race. The lock has to wrap the read-modify-write of tokens, not just the final comparison.

The cost parameter is worth calling out too: not all requests are equal. A bulk export endpoint might reasonably cost 10 tokens while a status check costs 1. Token bucket handles variable cost naturally; fixed and sliding window counters do not, without extra bookkeeping.

Distributed rate limiting: why single-process code isn't enough

Everything above lives in one process's memory. The moment you run more than one instance of a service behind a load balancer, a per-process limiter is enforcing the limit per instance, not per client — five instances each independently allowing 100 req/min gives a client 500 req/min in aggregate, not 100.

The standard fix is to move the state into something shared, usually Redis, and to make the check-and-decrement atomic so concurrent requests across instances don't race the same way threads did above. A minimal token bucket in Redis using a Lua script (so the read-refill-check-decrement sequence is atomic on the Redis side):

-- KEYS[1] = bucket key, ARGV[1] = rate, ARGV[2] = capacity, ARGV[3] = now, ARGV[4] = cost
local bucket = redis.call("HMGET", KEYS[1], "tokens", "ts")
local tokens = tonumber(bucket[1]) or tonumber(ARGV[2])
local ts = tonumber(bucket[2]) or tonumber(ARGV[3])
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])

local elapsed = math.max(0, now - ts)
tokens = math.min(capacity, tokens + elapsed * rate)

local allowed = 0
if tokens >= cost then
    tokens = tokens - cost
    allowed = 1
end

redis.call("HMSET", KEYS[1], "tokens", tokens, "ts", now)
redis.call("EXPIRE", KEYS[1], math.ceil(capacity / rate) + 1)
return allowed

Running this as a Lua script means Redis executes it atomically — no other client's script can interleave between the read and the write, which is exactly the race the in-process lock was preventing, now solved across processes instead of across threads. The EXPIRE call matters for a different reason: without it, every client that ever made one request leaves a key in Redis forever. Setting the TTL to roughly the time it takes the bucket to fully refill means idle clients' keys disappear on their own.

Picking one

None of these is strictly better; they answer different questions:

• Fixed window: only when the boundary-burst issue is genuinely acceptable for your traffic (e.g., you're limiting something coarse like daily export quota, where a burst around midnight doesn't matter).
• Sliding window log: when you need exact enforcement and can afford the memory — typically low-cardinality cases like a handful of high-value API keys, not millions of anonymous IPs.
• Sliding window counter: the default choice for most API gateways — bounded memory, small and well-understood approximation error, no burst exploit.
• Token bucket: when controlled bursts are a feature, not a bug — a client that saved up quota by being idle should be able to spend it faster than the steady-state rate, up to the bucket's capacity.

The thing worth internalizing is that "rate limiting" isn't one algorithm with configuration knobs — the four approaches above encode genuinely different policies about what a burst means, and picking the wrong one shows up as either angry users hitting a limit that shouldn't have triggered, or an abuse vector that technically respects the stated rate while defeating its purpose.