Complexity

A rate limiter runs in front of every request, so the cost of one decision and the memory each key consumes translate directly into the cost of running your service. This chapter compares the five algorithms on time, space, accuracy and burst behavior. Below, L is the limit per window and K is the number of active keys.

Time per decision

• Fixed window: compute the window number and bump one counter. O(1).
• Sliding window log: drop expired entries from the front, then count. With a deque each timestamp is appended once and removed once, so the cost is amortized O(1), although a single call may drop up to O(L) entries. Implemented with a Redis sorted set, adds and range deletes cost O(log n).
• Sliding window counter: one multiplication and one addition. O(1).
• Token bucket: add elapsed time × rate and compare. O(1).
• Leaky bucket (queue): enqueue and dequeue are each O(1).

Memory per key

Multiply by K for the total. With a limit of 10,000 per hour and 100,000 active users, a sliding log may have to hold a billion timestamps in the worst case, while token buckets need just 200,000 numbers. That gap is why large services rarely use the log approach.

def worst_case_bytes(keys: int, limit: int, bytes_per_number: int = 8) -> dict[str, int]:
    return {
        "fixed_window": keys * 2 * bytes_per_number,
        "sliding_log": keys * limit * bytes_per_number,
        "sliding_counter": keys * 3 * bytes_per_number,
        "token_bucket": keys * 2 * bytes_per_number,
    }


for name, size in worst_case_bytes(keys=100_000, limit=10_000).items():
    print(f"{name:16} {size / 2**20:10.1f} MiB")
# sliding_log needs about 7,629 MiB; the others need a few MiB

Real usage is higher because of language and storage overhead, but the orders of magnitude hold.

Accuracy and bursts

The token bucket bound is a simple formula: starting from a full bucket, at most capacity + rate × T requests pass during a span of length T. That is why it is configured with two numbers, such as "10 per second on average, bursts of up to 20".

def max_admitted(rate: float, capacity: float, seconds: float) -> int:
    # Most requests that can pass in `seconds`, starting from a full bucket
    return int(capacity + rate * seconds)


print(max_admitted(rate=10, capacity=20, seconds=1))    # 30
print(max_admitted(rate=10, capacity=20, seconds=60))   # 620

Measuring the boundary problem

This snippet sends requests just before and just after a boundary and counts how many each approach admits.

from collections import deque


def fixed_window(times, limit, window):
    counts = {}
    ok = 0
    for t in times:
        w = int(t // window)
        counts[w] = counts.get(w, 0) + 1
        ok += counts[w] <= limit
    return ok


def sliding_log(times, limit, window):
    log, ok = deque(), 0
    for t in times:
        while log and log[0] <= t - window:
            log.popleft()
        if len(log) < limit:
            log.append(t)
            ok += 1
    return ok


burst = [59.5] * 5 + [60.5] * 5        # five on each side of the boundary
print(fixed_window(burst, 5, 60))      # 10
print(sliding_log(burst, 5, 60))       # 5

The cost of going distributed

When several servers share one limit, every decision needs a round trip to a shared store such as Redis. At that point the network round trip, typically hundreds of microseconds to a few milliseconds, dominates the algorithm's O(1). Bundling several commands into one Lua script keeps it to a single round trip. At very high volume, some systems keep a local bucket on each server and only sync with the shared store periodically, trading a little accuracy for lower latency.

Summary

• Fixed window, sliding window counter and token bucket are O(1) in time and in space per key.
• A sliding window log is exact but needs O(L) memory per key, which hurts at scale.
• A token bucket admits at most capacity + rate × T requests over a span T.
• Once distributed, network round trips, not the algorithm, set the cost.