Rate Limiting Algorithms Compared

Rate limiting protects services from abuse, overload, and cascading failures. The algorithm choice determines whether you block legitimate traffic, allow bursts, or create unfairness — so it is worth knowing what each one actually guarantees before shipping it into the path of every request.

The mechanism every limiter shares

Whatever the algorithm, the decision is the same five steps:

1. identify the key     : API key, user id, IP — the unit you limit
2. locate the state     : counter/window/bucket for that key
3. apply the clock      : refill, expire, or roll the window
4. decide allow/deny    : state vs limit
5. respond              : 200 + headers, or 429 + Retry-After
 
headers (RFC 6585 / draft-ietf-httpapi-ratelimit-headers):
  Retry-After: 30            ← seconds until a new attempt may succeed
  X-RateLimit-Remaining: 0
  X-RateLimit-Reset: 1790002200

Two properties matter in production and are independent of the algorithm. Latency: the limiter sits on every request, so the decision must cost well under a millisecond — a Redis round trip at ~0.5 ms in-region is acceptable, a cross-region call is not. Failure mode: when the limiter's store is down, do you fail open (allow traffic, lose protection) or fail closed (deny traffic, lose availability)? For abuse prevention, fail open; for a per-tenant billing limit, fail closed. Choose deliberately — the default will be discovered during the incident that takes the limiter down.

State must also be updated atomically. A check-then-increment in two steps races: two concurrent requests both read "99 of 100 used" and both allow the 101st. In Redis this is why the whole decision runs inside one Lua script — atomic, single-threaded, no gap between read and write.

Fixed window: simplest, with a boundary burst

Count requests in fixed time windows:

class FixedWindowRateLimiter:
    def __init__(self, max_requests: int, window_seconds: int):
        self.max_requests = max_requests
        self.window_seconds = window_seconds
        self.counters = {}  # window_key → count
 
    def allow(self, key: str) -> bool:
        window = int(time.time() // self.window_seconds)
        window_key = f"{key}:{window}"
        if self.counters.get(window_key, 0) >= self.max_requests:
            return False
        self.counters[window_key] = self.counters.get(window_key, 0) + 1
        return True

The boundary burst is structural, not a bug:

limit: 100 requests/minute, window [00:00, 01:00)
 
00:59:59  requests 1–100   all allowed   (window 1 at 100/100)
01:00:00  requests 1–100   all allowed   (window 2 resets to 0)
          → 200 requests inside 2 seconds against a "100/minute" limit

The worst case is a full 2× the limit across any boundary — fine for coarse throttling, unacceptable where the limit exists to protect a downstream budget (payment APIs, per-tenant quotas). Memory is O(1) per key (one counter), which is its real virtue.

Sliding window log: exact, but the memory math bites

Track every timestamp and count those inside the rolling window:

def allow(self, key: str) -> bool:
    now = time.time()
    cutoff = now - self.window_seconds
    self.requests[key] = [t for t in self.requests[key] if t > cutoff]
    if len(self.requests[key]) >= self.max_requests:
        return False
    self.requests[key].append(now)
    return True

Exact, no boundary burst, and it gives you Retry-After for free (oldest timestamp + window − now). The cost is O(n) memory per key, and it compounds:

limit 1,000 req/min per key, timestamp = 8 bytes (+ ~16 B list overhead)
  per key      ≈ 1,000 × 24 B ≈ 24 KB
  10,000 keys  ≈ 240 MB
  1,000,000 keys ≈ 24 GB        ← the log is no longer a data structure,
                                   it's your capacity plan

Plus the write cost: every request appends and the whole list is filtered on every check — a scan of up to n entries per request at the worst moment (right before the limit resets).

Sliding window counter: the practical hybrid

Combine the previous two — two integers plus an interpolation:

def allow(self, key: str) -> bool:
    now = time.time()
    curr = int(now // self.window_seconds)
    if self.curr_window.get(key) != curr:
        self.prev_count[key] = self.curr_count.get(key, 0)
        self.curr_count[key] = 0
        self.curr_window[key] = curr
    overlap = 1 - (now % self.window_seconds) / self.window_seconds
    weighted = self.prev_count[key] * overlap + self.curr_count[key]
    if weighted >= self.max_requests:
        return False
    self.curr_count[key] += 1
    return True

Worked example — limit 100/min, previous window had 100 requests, 15 seconds into the current window:

overlap = 1 − 15/60 = 0.75
weighted = 100 × 0.75 + 0 = 75        ← you may take 25 more right now
vs fixed window would allow a full 100 (the 2× burst)
vs exact log would also say 75         ← same answer, O(1) memory

Two counters per key (16 bytes), O(1) update, no boundary burst, ~99% agreement with the exact log. This is what most gateways run (Kong, AWS API Gateway, Cloudflare) and what Redis implementations reduce to two keys — accuracy sufficient for every abuse and quota case I have seen, at a rounding error of memory.

Token bucket and leaky bucket: shaping rather than counting

Token bucket refills tokens at a fixed rate up to a capacity — it is the algorithm that models what a rate limit is for: a sustained rate plus an allowed burst.

class TokenBucket:
    def __init__(self, capacity: int, refill_rate: float):
        self.capacity = capacity            # burst size
        self.refill_rate = refill_rate      # tokens per second
        self.tokens = capacity
        self.last_refill = time.time()
 
    def allow(self, tokens: int = 1) -> bool:
        now = time.time()
        self.tokens = min(self.capacity,
                          self.tokens + (now - self.last_refill) * self.refill_rate)
        self.last_refill = now
        if self.tokens >= tokens:
            self.tokens -= tokens
            return True
        return False

capacity=100, refill_rate=10/s allows a burst of 100, then sustains 10/s — exactly how you want a page load (20 assets at once) to behave while still capping the minute's total. Two fields per key; distributed version is one Lua script over a Redis hash, with the refill computed from elapsed time so the state stays correct across instances.

Leaky bucket is the inverse: a queue that drains at constant rate, so output is smooth regardless of input. That makes it a traffic shaper for networks and job schedulers — and a poor API limiter, because queued requests become added latency for the user rather than a clean rejection.

Where limiters fail in production

• Thundering herds at reset. A fixed window that denies 100% of requests until the boundary produces a synchronized spike the moment it opens. Jittered windows or token buckets (which refill continuously) remove the cliff.
• Distributed state races. Check-then-increment across instances over-admits by up to (instances − 1) per instant; Lua or an atomic INCR+EXPIRE closes the gap.
• Hot keys. One celebrity account hammering a single counter makes that Redis key a hotspot; local pre-allocation (each node keeps a small local bucket and periodically reconciles) trades a little accuracy for distribution.
• The limiter becoming the outage. Extra 0.5 ms per request is invisible; an extra cross-region hop or a synchronous dependency with no circuit breaker is not. Cache the decision briefly (50–100 ms) when the store is degraded, and document the fail-open policy.
• Counting the wrong unit. Limiting requests when your cost is downstream calls lets one request do 50× the damage; match the key and the unit to the resource you are protecting.

Key takeaways

• Fixed window is O(1) and simple, and permits a full 2× burst at every boundary — acceptable for throttling, wrong for hard quotas.
• Sliding window log is exact and gives precise Retry-After, but costs O(n) memory per key: 1M keys × 1,000 timestamps ≈ 24 GB.
• Sliding window counter gets log-quality accuracy with two integers — the default choice for most gateways.
• Token bucket expresses "sustained rate + burst" directly and shapes nothing — reject fast rather than queue; use leaky bucket only when smooth output is the requirement.
• Make the decision atomic and the failure mode explicit: Lua (or INCR) for the race, and a written answer for fail-open versus fail-closed before the limiter itself goes down.