Explain the main rate-limiting algorithms — token bucket, leaky bucket, fixed window, sliding window log/counter

#The problem rate limiting solves

Every rate limiter answers the same underlying question — "has this client done too much, too recently?" — but "recently" is where all four algorithms diverge. A limiter has to compress an entire history of requests into a small, fast-to-check piece of state, and the compression method it picks determines exactly how bursty traffic is allowed to be, how much memory each tracked client costs, and how accurate the limiter is right at the edge of a time window. There is no universally correct choice; there is only the tradeoff your traffic pattern can tolerate.

Whichever algorithm sits behind it, a well-behaved rate limiter communicates its decision through standard HTTP: a rejected request gets 429 Too Many Requests, ideally with a Retry-After header telling the client how long to back off, and informational X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset headers on every response — allowed or not — so a well-written client can throttle itself before ever being rejected.

#Fixed window counter

The simplest approach: divide time into fixed-size windows (say, one per minute) and keep a counter per client per window. Increment on every request; reject once the counter exceeds the limit; the counter resets when the window rolls over.

def is_allowed_fixed_window(redis_client, user_id, limit, window_seconds):
    window = int(time.time() // window_seconds)
    key = f"rate:{user_id}:{window}"
    count = redis_client.incr(key)
    if count == 1:
        redis_client.expire(key, window_seconds)
    return count <= limit

This is one INCR and one conditional EXPIRE — cheap, O(1) memory per client, and trivial to reason about. Its flaw is the boundary: a client that sends its full limit in the last second of one window and its full limit again in the first second of the next window has effectively sent double the intended rate in about two seconds, and the counter never noticed because it reset in between.

#Sliding window log

The precise fix: record the timestamp of every individual request in a sorted set, drop everything older than the window on each check, and count what's left.

def is_allowed_sliding_log(redis_client, user_id, limit, window_seconds):
    now = time.time()
    key = f"rate:log:{user_id}"
    pipe = redis_client.pipeline()
    pipe.zremrangebyscore(key, 0, now - window_seconds)
    pipe.zadd(key, {str(now): now})
    pipe.zcard(key)
    pipe.expire(key, window_seconds)
    _, _, count, _ = pipe.execute()
    return count <= limit

This is exact — there is no boundary artifact, because the "window" is always the trailing N seconds relative to now, not an aligned clock interval. The cost is memory: a busy client under a generous limit means storing one entry per request, which is O(n) per key rather than O(1). At high volume, across millions of clients, this adds up fast.

#Sliding window counter

A cheaper approximation that most production systems actually reach for: keep two fixed-window counters (current and previous) and combine them with a weight based on how far into the current window you are.

estimated_count = previous_window_count * (1 - elapsed_fraction) + current_window_count

If you're 30% into the current window, you count 70% of the previous window's traffic plus 100% of the current window's — smoothing the hard edge of a fixed window into something close to the sliding log's accuracy, at the fixed window's O(1) memory cost. This is the algorithm behind most high-volume public API limiters, because it gets 95% of the accuracy of the sliding log for a tiny fraction of the memory.

#Leaky bucket

Leaky bucket models a queue with a constant drain rate: requests fill a bucket of finite capacity, and the bucket "leaks" — is processed — at a fixed rate regardless of how fast requests arrive. If the bucket is full, new requests are rejected.

import time
import threading
from collections import deque

class LeakyBucket:
    def __init__(self, capacity, leak_rate):
        self.capacity = capacity
        self.leak_rate = leak_rate  # processed per second
        self.queue = deque()
        self.last_leak = time.monotonic()
        self.lock = threading.Lock()

    def _leak(self):
        now = time.monotonic()
        elapsed = now - self.last_leak
        to_remove = int(elapsed * self.leak_rate)
        for _ in range(min(to_remove, len(self.queue))):
            self.queue.popleft()
        if to_remove > 0:
            self.last_leak = now

    def allow(self):
        with self.lock:
            self._leak()
            if len(self.queue) < self.capacity:
                self.queue.append(time.monotonic())
                return True
            return False

The defining feature is that leaky bucket smooths output to a strictly constant rate — it's traffic shaping, not just admission control. This is the right model when what you're protecting (a downstream database, a legacy system, a physical resource) genuinely cannot handle any burst at all, only a steady drip. Token bucket, by contrast, explicitly allows bursts.

#Token bucket

Token bucket flips leaky bucket's framing: instead of a queue that drains at a constant rate, it's a bucket that fills with tokens at a constant rate up to some capacity, and every request must spend one token to proceed.

import time
import threading

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity          # max burst size
        self.refill_rate = refill_rate    # tokens added per second
        self.tokens = capacity
        self.last_refill = time.monotonic()
        self.lock = threading.Lock()

    def _refill(self):
        now = time.monotonic()
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last_refill = now

    def allow(self, cost: float = 1.0) -> bool:
        with self.lock:
            self._refill()
            if self.tokens >= cost:
                self.tokens -= cost
                return True
            return False


# sustained: 100 requests/minute, burst: up to 20 at once
limiter = TokenBucket(capacity=20, refill_rate=100 / 60)

def handle_request() -> bool:
    return limiter.allow()

Because tokens accumulate while the client is idle, a client that hasn't called in a while can legitimately burst up to capacity requests instantly, then falls back to the steady refill_rate. That is precisely the behavior most public APIs want: don't punish someone for calling once a minute and then needing five calls in the same second to render one screen.

#Side by side

🧠 Check your understanding
0/3 · 0/3 answered
1. A fixed-window rate limiter allows 100 requests per minute. A client sends 100 requests in the last second of window A and 100 more in the first second of window B. What actually happened?
The client effectively sent 200 requests in about two seconds without ever exceeding the counter in either windowThe limiter correctly blocked the second batchThe limiter would have merged both windows automaticallyThis is impossible with a fixed window limiter
2. What is the key structural difference between token bucket and leaky bucket?
Leaky bucket allows unlimited bursts while token bucket does notToken bucket allows bursts up to its capacity because unused capacity accumulates as tokens; leaky bucket smooths output to a constant rate regardless of arrival burstsThey are mathematically identical, just named differentlyToken bucket has no capacity limit
3. Why does a naive in-memory token bucket break when a service is scaled to multiple instances behind a load balancer?
Token buckets cannot be implemented in memory at allEach instance tracks its own independent token count, so the effective rate limit becomes roughly the configured limit times the number of instancesLoad balancers reject requests with rate limiting headersToken buckets require a GPU to compute refill rates