Rate-limiting algorithms compared

A rate limiter answers one question for every request: has this client used up its allowance? If it has not, the request goes on; if it has, the request is refused at once with 429 Too Many Requests, or held back until it fits. Five algorithms do almost all of this work. A token bucket allows bursts up to a set size and a steady rate after that. A leaky bucket queues requests and lets them out at an even pace. A fixed window counts requests per clock second or minute, which is cheap, but lets up to twice the limit through at a window’s edge. A sliding log keeps a timestamp for every request and is exact. A sliding window counter estimates a sliding window from two counts. This lesson builds all five, runs them on the same traffic, measures how far each strays from its limit and what it stores, and ends with how to choose one and how to tell clients they were limited.

What a rate limiter decides

Every limiter works from the same inputs. The key says whose allowance a request uses: an API key, a user, an account, a tenant or a network address. The cost says how much of it the request uses, usually 1, though an expensive search may cost more than a cheap read. The limit is a rate, often with a burst size, and the time is when the request arrives. The answer is allow or refuse, or, for a leaky bucket, a later moment at which the request may go on.

Limits exist for four reasons, and the reason decides which algorithm fits. They protect capacity, so that one client’s surge cannot use up servers that everyone shares. They share capacity fairly between clients who pay for the same service. They cap costs that grow with every request, such as a text message sent for every one-time code or a call to a paid service. And they slow abuse: password guessing, scraping and spam.

Each layer limits by what it knows. An edge proxy sees only network addresses, so it can stop a flood but cannot tell one customer from another. The API gateway knows the API key and can enforce what each customer bought. The service knows which endpoints are expensive and how busy it is. Limits near the client are cheap and coarse; limits near the work are precise.

A rate limit is also only one kind of limit. Stripe’s engineering blog describes four that run together on its API: a request rate limiter per user, a limiter on how many requests each user has in progress at once, and two load shedders that look at the whole system instead of one user. One of them keeps capacity back for critical requests, and the other drops the least important traffic when workers run short (Stripe). The first two decide by a client’s allowance, the shedders by the state of the servers. A limit on requests in progress is a rate limit in another form: by Little’s law, 20 searches a second that take 3 seconds each keep 60 in progress.

Five algorithms and what each keeps

All five limit one key at a time; a real limiter keeps one copy of this state per key, in a table or a key-value store. The code is the version this lesson runs. Time comes in as an argument, in whole milliseconds, so the same requests always get the same decisions, and every comparison uses whole numbers, so rounding never changes a decision. A service would pass in a monotonic clock instead of the time of day: Python’s time.monotonic never runs backwards, and correcting the computer’s time does not move it (Python documentation).

Token bucket

A token bucket holds up to b tokens and gains r tokens a second. Every request takes a token, and a request that finds the bucket empty is refused. This one starts full, so a client that has been quiet can send a burst of b requests at once, and after that it gets r a second. Over any stretch of T seconds, a token bucket lets through at most

requests: what the bucket held at the start plus what T seconds earned. That bound is what you promise a client, and what the service behind the limiter must be sized for.

No timer adds the tokens. Each request first adds what the time since the previous request earned, up to b, then takes its token. So the state per key is two numbers: the tokens, and the time they were last brought up to date.

# Token bucket: a burst of up to `capacity` requests passes at once, then `rate` requests a second.
# Time is passed in as whole milliseconds from a clock that only moves forward, so a test or a simulation decides
# what "now" is. Tokens are counted in thousandths, so every number stays whole and no rounding error can let a
# request through or turn one away.


class TokenBucket:
    def __init__(self, rate, capacity, now_ms=0):
        self.rate = rate                  # tokens added every second (a whole number)
        self.capacity = capacity          # the most tokens the bucket holds: the largest burst
        self.milli = capacity * 1000      # tokens now, in thousandths; a new bucket starts full
        self.at = now_ms                  # when `milli` was last brought up to date

    def _refill(self, now_ms):
        # No timer runs. Each call adds what the time since the last call earned, up to the capacity.
        if now_ms > self.at:
            earned = (now_ms - self.at) * self.rate     # 1 ms earns `rate` thousandths of a token
            self.milli = min(self.capacity * 1000, self.milli + earned)
            self.at = now_ms

    def allow(self, now_ms, cost=1):
        """Take `cost` tokens and return True, or take nothing and return False."""
        self._refill(now_ms)
        if self.milli >= cost * 1000:
            self.milli -= cost * 1000
            return True
        return False

    def retry_after_ms(self, now_ms, cost=1):
        """How long until a request of `cost` tokens would pass: 0 if it would pass now."""
        if cost > self.capacity:
            raise ValueError("the request needs more tokens than the bucket can ever hold")
        self._refill(now_ms)
        missing = cost * 1000 - self.milli
        return max(0, -(-missing // self.rate))         # rounded up to a whole millisecond

    def tokens(self):
        return self.milli / 1000


if __name__ == "__main__":
    bucket = TokenBucket(rate=5, capacity=10)
    print("A bucket of 10 tokens that gains 5 a second")
    burst = [bucket.allow(0) for _ in range(14)]
    print(f"     0 ms  a burst of 14: {burst.count(True)} allowed, {burst.count(False)} refused,"
          f" retry after {bucket.retry_after_ms(0)} ms")
    allowed = burst.count(True)
    for now in range(100, 1100, 100):
        if bucket.allow(now):
            allowed += 1
            print(f"{now:>6} ms  allowed, {bucket.tokens():.1f} tokens left")
        else:
            print(f"{now:>6} ms  refused, retry after {bucket.retry_after_ms(now)} ms")
    print(f"Allowed from 0 to 1,000 ms: {allowed} = 10 for the burst + 5 earned in one second")

A bucket of 10 tokens that gains 5 a second
     0 ms  a burst of 14: 10 allowed, 4 refused, retry after 200 ms
   100 ms  refused, retry after 100 ms
   200 ms  allowed, 0.0 tokens left
   300 ms  refused, retry after 100 ms
   400 ms  allowed, 0.0 tokens left
   500 ms  refused, retry after 100 ms
   600 ms  allowed, 0.0 tokens left
   700 ms  refused, retry after 100 ms
   800 ms  allowed, 0.0 tokens left
   900 ms  refused, retry after 100 ms
  1000 ms  allowed, 0.0 tokens left
Allowed from 0 to 1,000 ms: 15 = 10 for the burst + 5 earned in one second

The output shows both halves of the behaviour. Ten requests of the burst pass at once and four are refused; then one request in two passes, because a token takes 200 ms to earn. Fifteen passed in the first second, the 10 the bucket held and the 5 the second earned: b + r × T exactly. Every refusal also knows how long the client must wait, which a server sends as Retry-After.

Widely used systems limit this way. Amazon API Gateway throttles requests with a token bucket in which a token counts for a request, configured by a rate (the tokens added each second) and a burst (the bucket’s capacity), and it describes these limits as targets applied on a best-effort basis rather than guaranteed ceilings (API Gateway documentation). Envoy’s local rate limit filter applies a token bucket too, and answers 429 when it runs out (Envoy documentation). Stripe’s request rate limiter is a token bucket per user, kept in Redis (Stripe).

Leaky bucket

A leaky bucket turns the idea around: the requests themselves go into the bucket and leave it at a steady rate, one every 1/r seconds. If b requests are already waiting, a new one is refused. The service behind a leaky bucket never sees a burst; it sees an even stream, and the price is the time requests spend waiting.

# Leaky bucket as a queue: requests wait in the bucket and leave it at a steady `rate` a second, one every
# 1000 / rate ms. At most `size` requests are in the bucket at once; a request that finds it full is refused.
# The service behind it never sees a burst, and the price is the time requests spend waiting.
from collections import deque


class LeakyBucket:
    def __init__(self, rate, size):
        self.gap = 1000 // rate          # ms between two requests leaving (rate must divide 1000)
        self.size = size                 # how many requests may be in the bucket at once
        self.inside = deque()            # when each request still in the bucket leaves it, in order
        self.last_leave = -self.gap      # when the latest request left or will leave

    def offer(self, now_ms):
        """When the request leaves the bucket for the service (ms), or None if the bucket is full."""
        while self.inside and self.inside[0] < now_ms:
            self.inside.popleft()        # it has left already
        if len(self.inside) >= self.size:
            return None
        leave = max(now_ms, self.last_leave + self.gap)
        self.last_leave = leave
        self.inside.append(leave)
        return leave


if __name__ == "__main__":
    bucket = LeakyBucket(rate=5, size=10)
    print("A bucket that lets 5 requests a second out and holds 10")
    leaves = [bucket.offer(0) for _ in range(14)]
    sent = [t for t in leaves if t is not None]
    print(f"A burst of 14 at 0 ms: {len(sent)} accepted, {leaves.count(None)} refused")
    print("They leave at (ms):", ", ".join(str(t) for t in sent))
    print(f"The last accepted request waits {sent[-1]} ms; the service never sees two within 200 ms")
    print(f"At 1,000 ms another arrives and leaves at {bucket.offer(1000)} ms")

A bucket that lets 5 requests a second out and holds 10
A burst of 14 at 0 ms: 10 accepted, 4 refused
They leave at (ms): 0, 200, 400, 600, 800, 1000, 1200, 1400, 1600, 1800
The last accepted request waits 1800 ms; the service never sees two within 200 ms
At 1,000 ms another arrives and leaves at 2000 ms

The same burst of 14 is treated differently. Ten requests are accepted, but only the first goes on at once; the others leave 200 ms apart, so the tenth waits 1.8 seconds. Four are refused, because the bucket is full. A leaky bucket suits work that can wait but must not arrive in bursts, such as calls to a partner whose contract allows a fixed number a second. It suits interactive requests badly, because a waiting request holds a connection open and keeps a person waiting.

NGINX’s limit_req module describes its method as a leaky bucket. Its documentation says that requests above the configured rate are delayed until their number exceeds the burst size, and then refused with an error; the burst size is zero unless you set one, the nodelay parameter passes the requests within the burst at once instead of delaying them, and refused requests get status 503 unless limit_req_status sets another code (NGINX documentation). For a limit on clients, set it to 429, so that a client can tell its own excess from an overloaded server.

GCRA: a token bucket in one number

A leaky bucket can also work without a queue, as a meter that only decides whether a request conforms and never delays anything. Used that way, it makes the same decisions as a token bucket. ITU-T Recommendation I.371, written for ATM networks, defines this as the generic cell rate algorithm (GCRA) and gives two equivalent versions of it: a continuous-state leaky bucket, and a virtual scheduling algorithm that keeps a single number, the theoretical arrival time (ITU-T I.371, Annex A).

The theoretical arrival time is when the next request would be due if requests came exactly at the steady rate. A request may arrive early by up to a tolerance; one that comes earlier still is refused. A tolerance of b − 1 intervals behaves like a bucket of b tokens, and the script checks that on 5,000 bursty requests:

# GCRA, the generic cell rate algorithm of ITU-T I.371 (Annex A), in its "virtual scheduling" form: a token
# bucket kept as one number per key, the theoretical arrival time (TAT), the moment the next request would be due
# if requests came exactly at the steady rate. A request may come early by up to `tolerance`, which is what lets a
# burst through.
import random

from token_bucket import TokenBucket


class GCRA:
    def __init__(self, rate, burst):
        self.interval = 1000 // rate                     # T: ms between requests at the steady rate
        self.tolerance = (burst - 1) * self.interval     # tau: how early a request may arrive
        self.tat = None                                  # theoretical arrival time of the next request

    def allow(self, now_ms):
        tat = now_ms if self.tat is None else max(self.tat, now_ms)
        if now_ms < tat - self.tolerance:                # too early: the burst allowance is used up
            return False
        self.tat = tat + self.interval
        return True


if __name__ == "__main__":
    rng = random.Random(7)
    times, t = [], 0
    for _ in range(5000):                                # bursty traffic: gaps from 0 to 300 ms
        t += rng.choice([0, 0, 0, 1, 5, 20, 50, 100, 300])
        times.append(t)
    gcra, bucket = GCRA(rate=10, burst=10), TokenBucket(rate=10, capacity=10)
    a = [gcra.allow(x) for x in times]
    b = [bucket.allow(x) for x in times]
    same = sum(x == y for x, y in zip(a, b))
    print(f"{len(times)} requests over {times[-1] / 1000:.1f} s; GCRA allowed {sum(a)}, the token bucket {sum(b)}")
    print(f"Same decision for {same} of {len(times)} requests")
    print(f"State per key: GCRA keeps 1 number (TAT = {gcra.tat} ms), the token bucket 2"
          f" ({bucket.milli / 1000:g} tokens at {bucket.at} ms)")

5000 requests over 253.2 s; GCRA allowed 2535, the token bucket 2535
Same decision for 5000 of 5000 requests
State per key: GCRA keeps 1 number (TAT = 253937 ms), the token bucket 2 (2.69 tokens at 253206 ms)

Every decision agrees, and GCRA stores half as much: one timestamp per key instead of a count and a timestamp. With millions of keys, half the state is worth having.

Fixed window

A fixed window counts the requests of the current window, such as the current clock second or minute, refuses once the count reaches the limit, and starts again at zero when the next window begins. It is the cheapest algorithm to run on a shared store: one counter per key and window, increased once per request and thrown away with its window.

# Fixed window: one counter per window of `window_ms` (each starts at a multiple of window_ms, the way
# "per minute" usually means "per clock minute"). Up to `limit` requests pass in each window.


class FixedWindow:
    def __init__(self, limit, window_ms):
        self.limit = limit
        self.window = window_ms
        self.current = None              # which window the count belongs to
        self.count = 0                   # requests allowed in it

    def allow(self, now_ms):
        w = now_ms // self.window
        if w != self.current:            # a new window: start counting again
            self.current, self.count = w, 0
        if self.count < self.limit:
            self.count += 1
            return True
        return False


if __name__ == "__main__":
    limiter = FixedWindow(limit=10, window_ms=1000)
    times = list(range(900, 1000, 10)) + list(range(1000, 1100, 10))   # 10 just before 1 s, 10 just after
    allowed = [t for t in times if limiter.allow(t)]
    print("A limit of 10 a second, counted in fixed windows of 1,000 ms")
    print(f"{len(times)} requests from {times[0]} to {times[-1]} ms: {len(allowed)} allowed")
    print(f"So {len(allowed)} requests passed within {allowed[-1] - allowed[0]} ms, twice the limit")

A limit of 10 a second, counted in fixed windows of 1,000 ms
20 requests from 900 to 1090 ms: 20 allowed
So 20 requests passed within 190 ms, twice the limit

Its weakness is the edge. A client that spends its whole allowance at the end of one window and again at the start of the next gets twice the limit through in a moment: here, 20 requests within 190 ms against a limit of 10 a second. A second weakness affects every client at once. All windows start again at the same instant, so clients that were refused, and jobs scheduled for the start of a minute, all come back together.

Sliding log

A sliding log keeps the time of every request it allowed during the last window. Before it decides, it drops the times that are older than one window; then it allows the request if fewer than the limit remain. No span of one window ever holds more than the limit, wherever the span starts, so the edge problem cannot happen.

# Sliding log: keep the time of every request allowed in the last `window_ms`. A request passes while fewer than
# `limit` are in the log, so no span of `window_ms` ever holds more than `limit` allowed requests. Exact, and the
# memory grows with the limit: one timestamp for every request it allows.
from collections import deque


class SlidingLog:
    def __init__(self, limit, window_ms):
        self.limit = limit
        self.window = window_ms
        self.log = deque()               # times of the allowed requests still inside the window, oldest first

    def allow(self, now_ms):
        while self.log and self.log[0] <= now_ms - self.window:
            self.log.popleft()           # older than the window: it no longer counts
        if len(self.log) < self.limit:
            self.log.append(now_ms)
            return True
        return False


if __name__ == "__main__":
    limiter = SlidingLog(limit=10, window_ms=1000)
    times = list(range(900, 1000, 10)) + list(range(1000, 1100, 10))   # the same 20 requests
    allowed = [t for t in times if limiter.allow(t)]
    print("A limit of 10 in any 1,000 ms, kept as a log of timestamps")
    print(f"{len(times)} requests from {times[0]} to {times[-1]} ms: {len(allowed)} allowed")
    print(f"The log holds {len(limiter.log)} timestamps; the oldest, {limiter.log[0]} ms, leaves the window"
          f" at {limiter.log[0] + 1000} ms")
    print(f"A request at 1,899 ms: {'allowed' if limiter.allow(1899) else 'refused'};"
          f" at 1,900 ms: {'allowed' if limiter.allow(1900) else 'refused'}")

A limit of 10 in any 1,000 ms, kept as a log of timestamps
20 requests from 900 to 1090 ms: 10 allowed
The log holds 10 timestamps; the oldest, 900 ms, leaves the window at 1900 ms
A request at 1,899 ms: refused; at 1,900 ms: allowed

The same 20 requests now get 10 through, and the next request must wait until the oldest time leaves the window: it is refused at 1,899 ms and allowed at 1,900 ms. The price is memory. The log holds a timestamp for every request in the window, so a limit of 1,000 an hour means up to 1,000 timestamps for each busy key. A double-ended queue keeps the work per request small, because a deque appends and pops at either end in roughly constant time (Python documentation), but it does not make the log any smaller.

Sliding window counter

A sliding window counter keeps the counts of only two fixed windows, the current one and the one before. To estimate how many requests the last full window held, it assumes that the previous window’s requests were spread evenly across it, and counts the share of that window that still overlaps:

Here W is the window’s length and e is how far into the current window the request arrives. A request passes while the estimate stays below the limit, so half-way through the current window, half of the previous window still counts.

That weight changes every millisecond, which surprises people who test the limiter. Suppose the limit is 10 in 10 seconds, the previous window allowed 10, and a burst of 10 starts half-way through the next window. Half of 10 still counts, so it looks as if 5 should pass:

# Sliding window counter: two counters, this fixed window's and the previous one's. It estimates the requests in
# the last `window_ms` as if the previous window's requests had been spread evenly over it:
#     estimate = previous × (window − elapsed) / window + current
# and lets a request pass while the estimate is below `limit`. The comparison is done in whole numbers
# (both sides multiplied by the window), so no rounding error can change a decision.


class SlidingWindowCounter:
    def __init__(self, limit, window_ms):
        self.limit = limit
        self.window = window_ms
        self.current = 0                 # index of the current fixed window
        self.count = 0                   # requests allowed in it
        self.previous = 0                # requests allowed in the window before it

    def allow(self, now_ms):
        w = now_ms // self.window
        if w != self.current:
            # The old count becomes "previous" only if that window is the one just before this one.
            self.previous = self.count if w == self.current + 1 else 0
            self.current, self.count = w, 0
        elapsed = now_ms - w * self.window
        if self.previous * (self.window - elapsed) + self.count * self.window < self.limit * self.window:
            self.count += 1
            return True
        return False


def burst_after_full_window(spacing_ms):
    """10 requests fill the window 0-10 s; then 10 more start half-way through the next window."""
    limiter = SlidingWindowCounter(limit=10, window_ms=10_000)
    for t in range(0, 10_000, 1000):
        limiter.allow(t)
    return sum(limiter.allow(15_000 + i * spacing_ms) for i in range(10))


if __name__ == "__main__":
    print("A limit of 10 in 10 s; the previous window allowed 10; a burst of 10 starts at 15.000 s")
    print("Half the previous window still counts, so you might expect 10 - 5 = 5 to pass.")
    print(f"Burst sent in the same millisecond: {burst_after_full_window(0)} allowed")
    print(f"Burst sent 1 ms apart:              {burst_after_full_window(1)} allowed")
    print("At 15.005 s the previous window counts 10 × 4,995 / 10,000 = 4.995, and 4.995 + 5 is below 10.")

A limit of 10 in 10 s; the previous window allowed 10; a burst of 10 starts at 15.000 s
Half the previous window still counts, so you might expect 10 - 5 = 5 to pass.
Burst sent in the same millisecond: 5 allowed
Burst sent 1 ms apart:              6 allowed
At 15.005 s the previous window counts 10 × 4,995 / 10,000 = 4.995, and 4.995 + 5 is below 10.

Five pass when the whole burst arrives within one millisecond, and six when its requests come 1 ms apart, because by the sixth request the previous window counts for only 4.995. Neither answer is a bug. A test that expects one number has to fix the time of every request, which is what an injected clock is for.

The five on the same traffic

Each algorithm looks reasonable on its own; the differences show when they all see the same requests. The traffic is 20 seconds of one client: random requests at about 4 a second, a burst of 30 at 3 seconds, ten requests on each side of the window edge at 8 seconds, and four seconds at 15 a second from 12 seconds on. Its random part is seeded, so it is the same on every run (Python documentation). Every limiter is set to about 10 a second: the token bucket holds 10 and gains 10 a second, the leaky bucket lets 10 a second out and holds 10, and the three window limiters allow 10 in 1,000 ms.

# The traffic every limiter in the playground sees: 20 seconds of one client's requests, as whole milliseconds.
# The random part is seeded, so every run (and every Python) builds the same trace.
import random


def bursty_trace(seed=7):
    rng = random.Random(seed)
    times, t = [], 0
    while True:                                          # background: random gaps of 1-499 ms, about 4 a second
        t += rng.randrange(1, 500)
        if t >= 20_000:
            break
        times.append(t)
    times += [3000 + 2 * i for i in range(30)]           # 3 s: a burst of 30 within 60 ms
    times += [7900 + 10 * i for i in range(10)]          # 7.9 s: 10 just before a window edge ...
    times += [8000 + 10 * i for i in range(10)]          # ... and 10 just after it
    times += [12_000 + 1000 * i // 15 for i in range(60)]  # 12-16 s: 15 a second, more than the limit
    return sorted(times)

# The rate-limiter playground: five limiters, each set to about 10 requests a second, on the same 20 seconds of
# traffic (traffic.py). Each column counts the requests that reached the service in that second; for the leaky
# bucket that is when a request left the bucket, which can be later than when it arrived.
from fixed_window import FixedWindow
from leaky_bucket import LeakyBucket
from sliding_counter import SlidingWindowCounter
from sliding_log import SlidingLog
from token_bucket import TokenBucket
from traffic import bursty_trace


def busiest_second(times):
    """The most requests in any span of 1,000 ms (times sorted)."""
    best, start = 0, 0
    for end, t in enumerate(times):
        while t - times[start] >= 1000:
            start += 1
        best = max(best, end - start + 1)
    return best


trace = bursty_trace()
limiters = {
    "token": TokenBucket(rate=10, capacity=10),
    "fixed": FixedWindow(limit=10, window_ms=1000),
    "log": SlidingLog(limit=10, window_ms=1000),
    "counter": SlidingWindowCounter(limit=10, window_ms=1000),
}
served = {name: [t for t in trace if limiter.allow(t)] for name, limiter in limiters.items()}
leaky = LeakyBucket(rate=10, size=10)
offers = [(t, leaky.offer(t)) for t in trace]
served["leaky"] = sorted(leave for _, leave in offers if leave is not None)
waits = [leave - t for t, leave in offers if leave is not None]

columns = ["token", "leaky", "fixed", "log", "counter"]
print("second  sent " + "".join(f"{c:>8}" for c in columns))
for s in range(20):
    def in_second(times):
        return sum(s * 1000 <= t < (s + 1) * 1000 for t in times)
    print(f"{s:>6}{in_second(trace):>6} " + "".join(f"{in_second(served[c]):>8}" for c in columns))

print()
print(f"{'':<22}" + "".join(f"{c:>8}" for c in columns))
print(f"{'served':<22}" + "".join(f"{len(served[c]):>8}" for c in columns))
print(f"{'refused':<22}" + "".join(f"{len(trace) - len(served[c]):>8}" for c in columns))
print(f"{'busiest 1,000 ms':<22}" + "".join(f"{busiest_second(served[c]):>8}" for c in columns))
print(f"{'longest wait (ms)':<22}" + "".join(f"{(max(waits) if c == 'leaky' else 0):>8}" for c in columns))
print(f"{len(trace)} requests in 20 s; every limiter is set to 10 a second")

second  sent    token   leaky   fixed     log counter
     0     4        4       4       4       4       4
     1     4        4       4       4       4       4
     2     5        5       5       5       5       5
     3    38       17      10      10      10      10
     4     5        5      10       5       5       5
     5     4        4       7       4       4       4
     6     4        4       4       4       4       4
     7    13       13       4      10       9      10
     8    16        6      10      10       2       6
     9     6        6      10       6       6       6
    10     4        4       6       4       4       4
    11     5        5       5       5       5       5
    12    20       18      10      10       9      10
    13    20       10      10      10      10      10
    14    19       10      10      10      10      10
    15    18       10      10      10      10      10
    16     3        3      10       3       3       3
    17     5        5       7       5       5       5
    18     3        3       3       3       3       3
    19     6        6       6       6       6       6

                         token   leaky   fixed     log counter
served                     142     145     128     118     124
refused                     60      57      74      84      78
busiest 1,000 ms            19      10      20      10      15
longest wait (ms)            0     997       0       0       0
202 requests in 20 s; every limiter is set to 10 a second

Read the row “busiest 1,000 ms” first, because it is what the service behind the limiter must survive. The sliding log and the leaky bucket held to 10. The token bucket let 19 through within a second when the heavy traffic began at 12 seconds: the 10 tokens it had saved and the 9 it earned in the next 0.9 seconds, its b + r × T bound at work. The fixed window let 20 through around the edge at 8 seconds, and the sliding window counter 15 in the same place.

The row “served” shows what the client got. The leaky bucket served the most, 145, because it delays requests instead of refusing them; its longest wait was 997 ms. The sliding log served the fewest, 118, because being exact means refusing everything over the line. From 12 to 16 seconds every limiter settles at 10 a second, but the token bucket first spends its saved tokens (18 in the first of those seconds), and the leaky bucket goes on sending 10 a second after the heavy traffic has stopped, until its queue is empty (second 16).

The five side by side, with what each lets through and what it keeps for every key:

How close the window counters come

One trace proves little. The next script gives the three window limiters an hour of traffic in three shapes, with a limit of 100 requests in any 60 seconds, and measures two things: the most requests each one let through in any 60 seconds, and how many it served in the hour.

# How close do the window limiters come to the exact rule "at most 100 requests in any 60 seconds"? Each one gets
# an hour of the same traffic, in three shapes: steady single requests, bursts at random moments, and a pattern
# built to fool them (a burst at the end of one window, then requests spread evenly over the next).
import random

from fixed_window import FixedWindow
from sliding_counter import SlidingWindowCounter
from sliding_log import SlidingLog

LIMIT, WINDOW, HOUR = 100, 60_000, 3_600_000


def steady(load, rng):
    times, t, mean_gap = [], 0, WINDOW // (LIMIT * load)
    while (t := t + rng.randrange(1, 2 * mean_gap)) < HOUR:
        times.append(t)
    return times


def bursty(load, rng):
    """Single requests and bursts of 2-29 (about 7 requests an event on average), 0-9 ms apart in a burst."""
    times, t, mean_gap = [], 0, WINDOW * 7 // (LIMIT * load)
    while (t := t + rng.randrange(1, 2 * mean_gap)) < HOUR:
        for _ in range(1 if rng.random() < 0.6 else rng.randrange(2, 30)):
            times.append(t)
            t += rng.randrange(10)
    return times


def edge_pattern(load, rng):
    """Even windows: 100 requests in their last 100 ms. Odd windows: 100 requests spread evenly."""
    times = []
    for w in range(0, HOUR // WINDOW, 2):
        start = w * WINDOW
        times += [start + WINDOW - 100 + i for i in range(LIMIT)]
        times += [start + WINDOW + i * (WINDOW // LIMIT) for i in range(LIMIT)]
    return times


def busiest(times):
    """The most requests in any span of 60 s (times sorted)."""
    best, start = 0, 0
    for end, t in enumerate(times):
        while t - times[start] >= WINDOW:
            start += 1
        best = max(best, end - start + 1)
    return best


rows = []
for shape, load in [(steady, 1), (steady, 2), (bursty, 1), (bursty, 2), (edge_pattern, 1)]:
    times = shape(load, random.Random(load))
    limiters = [FixedWindow(LIMIT, WINDOW), SlidingWindowCounter(LIMIT, WINDOW), SlidingLog(LIMIT, WINDOW)]
    served = [[t for t in times if limiter.allow(t)] for limiter in limiters]
    label = "edge pattern" if shape is edge_pattern else f"{shape.__name__} {load}x"
    rows.append((label, len(times), [busiest(s) for s in served], [len(s) for s in served]))

print(f"Limit: {LIMIT} requests in any {WINDOW // 1000} s; each row is one hour of traffic")
print("fixed: fixed window; counter: sliding window counter; log: sliding log")
for title, column in [("Busiest 60 s", 2), ("Served", 3)]:
    print()
    print(f"{title:<14}{'sent':>7}{'fixed':>8}{'counter':>9}{'log':>7}")
    for label, sent, *values in rows:
        v = values[column - 2]
        print(f"{label:<14}{sent:>7}{v[0]:>8}{v[1]:>9}{v[2]:>7}")

Limit: 100 requests in any 60 s; each row is one hour of traffic
fixed: fixed window; counter: sliding window counter; log: sliding log

Busiest 60 s     sent   fixed  counter    log
steady 1x        5964     118      108    100
steady 2x       12036     120      101    100
bursty 1x        5589     150      129    100
bursty 2x       11629     169      124    100
edge pattern     6000     200      199    100

Served           sent   fixed  counter    log
steady 1x        5964    5854     5778   5709
steady 2x       12036    6000     6000   5996
bursty 1x        5589    4989     4656   4449
bursty 2x       11629    5959     5569   5457
edge pattern     6000    6000     5970   3000

On steady traffic the counter is close: its busiest minute held 108 requests when the traffic came at the limit’s own rate and 101 at twice that rate, against 118 and 120 for the fixed window. Bursts make it worse, 129 and 124, because a burst breaks the assumption that the previous window’s requests were spread evenly. The last row is traffic built to defeat it: 100 requests in the last 100 ms of one window, then 100 spread evenly over the next. The fixed window let 200 through within a minute and the counter 199, and over the hour the counter served 5,970 requests where the exact log served 3,000. The estimate treats the burst as if it had been spread across its window, so as time moves on it counts less and less of a burst that is still inside the last 60 seconds.

The error runs the other way too. When the previous window’s requests came early in it, they have already left the real window, but the estimate still counts part of them, so the counter can refuse a request that an exact limiter would have allowed. So the sliding window counter is an estimate: close on ordinary traffic, and wrong by up to about a factor of two on traffic shaped against it. That is good enough for sharing capacity fairly, and not for limits whose number is a promise, such as how many password guesses an attacker gets or how many text messages, each one charged for, a client can trigger.

What each one costs in memory

# What each algorithm keeps per key, and what that costs for 10 million keys with a limit of 1,000 requests an hour.
# Counted at 8 bytes a number (a 64-bit count or timestamp) and nothing else: a real store adds its own overhead
# per key, about the same for every algorithm, so compare the rows rather than read the totals as exact.
KEYS = 10_000_000
LIMIT = 1_000
NUMBER = 8

STATE = [
    ("GCRA", "the theoretical arrival time", 1),
    ("token bucket", "tokens and the last refill time", 2),
    ("fixed window", "the window and its count", 2),
    ("sliding window counter", "the window and two counts", 3),
    ("sliding log", "one timestamp per request in the window", LIMIT),
]


def size(n_bytes):
    for unit, scale in [("GB", 10**9), ("MB", 10**6), ("KB", 10**3)]:
        if n_bytes >= scale:
            return f"{n_bytes / scale:,.1f} {unit}"
    return f"{n_bytes} B"


print(f"{KEYS:,} keys, a limit of {LIMIT:,} requests an hour, {NUMBER} bytes a number")
print(f"{'algorithm':<24}{'per key':>10}{'all keys':>12}  what it keeps")
for name, what, numbers in STATE:
    print(f"{name:<24}{size(numbers * NUMBER):>10}{size(numbers * NUMBER * KEYS):>12}  {what}")

busy = 0.01
log_bytes = KEYS * busy * LIMIT * NUMBER + KEYS * (1 - busy) * 50 * NUMBER
print(f"\nThe log's total is its worst case: every key at its limit. If 1% of keys are at the limit and the rest"
      f"\nsend 50 requests an hour, the log holds {size(log_bytes)}.")

10,000,000 keys, a limit of 1,000 requests an hour, 8 bytes a number
algorithm                  per key    all keys  what it keeps
GCRA                           8 B     80.0 MB  the theoretical arrival time
token bucket                  16 B    160.0 MB  tokens and the last refill time
fixed window                  16 B    160.0 MB  the window and its count
sliding window counter        24 B    240.0 MB  the window and two counts
sliding log                 8.0 KB     80.0 GB  one timestamp per request in the window

The log's total is its worst case: every key at its limit. If 1% of keys are at the limit and the rest
send 50 requests an hour, the log holds 4.8 GB.

Counting only the numbers themselves, GCRA needs 80 MB for 10 million keys and the sliding window counter 240 MB, small enough for one cache server. The sliding log needs up to 80 GB, five hundred times the token bucket, when every key is at its limit; even with only 1 % of keys busy it holds 4.8 GB. A real store adds an overhead per key that is much the same for every algorithm, so the comparison holds even where the totals do not.

Choosing one for an API

Start from what the limit protects, then choose the key, the algorithm and the numbers.

• A public API sold by plan. Use a token bucket per API key. The rate is what the plan promises, and the bucket size is the largest burst you are willing to absorb, such as the requests one page load or one batch makes at once. A daily or monthly quota on top can be a fixed window, because a burst at the edge matters little against a day’s total.
• Logins, one-time codes and password resets. The limits are small, and they are promises about an attacker: five guesses must mean five. Use a sliding log of failed attempts, which is a handful of timestamps per key, keyed by the account and by the account and address together. Keep any limit on the address alone generous: RFC 6269 notes that when many subscribers share one address, an address shut out after failed logins shuts out everyone behind it (RFC 6269, section 13.1).
• Calls to a partner with a hard limit. Pace them, with a leaky bucket in front of the partner or pacing in the caller. Microsoft’s Rate Limiting pattern gives the example of releasing 20 operations every 200 ms instead of 100 at once, so that the partner sees an even flow (Azure Architecture Center).
• Expensive endpoints. Searches and reports that take seconds need a limit on how many run at once, as well as on how many start each second: at 3 seconds each, 20 a second keep 60 running. Stripe’s limiter on requests in progress is this kind of limit (Stripe).
• Millions of keys where a close answer is enough, such as limits per address at the edge: a sliding window counter, at three numbers a key, or a fixed window when even that is too much.

Two habits help, whichever you choose. Give each request a cost, so that an expensive call takes several tokens and a cheap one takes one. And run a new limiter in a watching mode first: Stripe’s post advises dark launching each limiter, watching the traffic it would have blocked and adjusting it before it refuses anything (Stripe).

Telling the client it was limited

A refused request should get an answer that the client can act on. The status code for it is 429 Too Many Requests, defined in RFC 6585: the response should explain the condition, it may include a Retry-After field that says how long to wait, and a cache must not store it (RFC 6585). Retry-After carries either a number of seconds or an HTTP date (RFC 9110). Round the wait up to a whole second, so that a client which waits exactly that long is not refused again for the same reason.

Many APIs also describe the limit on every response, so that well-behaved clients slow down before they are refused. The IETF’s HTTPAPI working group is standardising two fields for this: RateLimit-Policy for the quota and its window, and RateLimit for what is left and within how many seconds. It is still an Internet-Draft, so the details may change. The draft does not mandate any algorithm, tells clients not to treat the numbers as a guarantee, and gives Retry-After precedence when both are present (draft-ietf-httpapi-ratelimit-headers).

// What a client sees from a limited API: at most 5 requests in any 10 seconds per key (a sliding log), and the
// response to each request with Retry-After (RFC 9110) and the RateLimit-Policy and RateLimit fields of the IETF
// draft. Time is passed in as whole milliseconds, so every run prints the same.
const LIMIT = 5;
const WINDOW_MS = 10_000;

class SlidingLog {
  constructor(limit, windowMs) {
    this.limit = limit;
    this.windowMs = windowMs;
    this.log = []; // times of the requests allowed in the last window, oldest first
  }

  allow(nowMs) {
    while (this.log.length && this.log[0] <= nowMs - this.windowMs) this.log.shift();
    if (this.log.length >= this.limit) return false;
    this.log.push(nowMs);
    return true;
  }

  /** Whole seconds, rounded up, until the oldest request leaves the window and one more unit is available. */
  secondsUntilOldestLeaves(nowMs) {
    if (!this.log.length) return this.windowMs / 1000;
    return Math.ceil((this.log[0] + this.windowMs - nowMs) / 1000);
  }
}

function respond(limiter, nowMs) {
  const allowed = limiter.allow(nowMs);
  const remaining = limiter.limit - limiter.log.length;
  const t = limiter.secondsUntilOldestLeaves(nowMs);
  const lines = [`${String(nowMs).padStart(6)} ms  ${allowed ? '200 OK' : '429 Too Many Requests'}`];
  if (!allowed) lines.push(`Retry-After: ${t}`);
  lines.push(`RateLimit: "per-key";r=${remaining};t=${t}`);
  return lines.join(`\n${' '.repeat(11)}`);
}

const limiter = new SlidingLog(LIMIT, WINDOW_MS);
console.log(`Every response carries\n           RateLimit-Policy: "per-key";q=${LIMIT};w=${WINDOW_MS / 1000}`);
for (const nowMs of [0, 1000, 2000, 2500, 3000, 3100, 9000, 10_500, 10_600]) console.log(respond(limiter, nowMs));

Every response carries
           RateLimit-Policy: "per-key";q=5;w=10
     0 ms  200 OK
           RateLimit: "per-key";r=4;t=10
  1000 ms  200 OK
           RateLimit: "per-key";r=3;t=9
  2000 ms  200 OK
           RateLimit: "per-key";r=2;t=8
  2500 ms  200 OK
           RateLimit: "per-key";r=1;t=8
  3000 ms  200 OK
           RateLimit: "per-key";r=0;t=7
  3100 ms  429 Too Many Requests
           Retry-After: 7
           RateLimit: "per-key";r=0;t=7
  9000 ms  429 Too Many Requests
           Retry-After: 1
           RateLimit: "per-key";r=0;t=1
 10500 ms  200 OK
           RateLimit: "per-key";r=0;t=1
 10600 ms  429 Too Many Requests
           Retry-After: 1
           RateLimit: "per-key";r=0;t=1

Read the responses from the top. Each success says how much quota is left (r) and the seconds (t) within which no more than that is available, here the time until the oldest request leaves the 10-second window. The sixth request, at 3.1 seconds, is refused with Retry-After: 7, because the first request leaves the window at 10 seconds. At 10.5 seconds a request passes, and the one 100 ms later is refused again: a sliding window gives back one unit at a time, not the whole quota at once.

Two more choices matter for the rest of the system. Answer 429 when a client is over its own allowance, and 503 Service Unavailable when the server is overloaded whatever the client did: clients should react differently to the two, and so should your monitoring. And expect retries. A client that honours Retry-After and adds a small random delay spreads its retries out, while one that retries at once, in a loop, turns a limit into extra load.

Running a limiter safely

• Inject the clock, and make it monotonic. Passing the time in, as every example here does, makes tests exact, and lets production pass a clock that never jumps backwards when the system time is corrected.
• Choose the key with care. Use the authenticated identity whenever there is one. A network address is the only key for anonymous traffic, but many people can share one address, so limits on it must be loose.
• Decide where the state lives. In one process it is a dictionary. Envoy’s local rate limit applies its limits per Envoy process by default (Envoy documentation), so ten proxies let through ten times the limit. One limit across a whole fleet needs a shared store, or a way to divide the limit between servers, which is the subject of the next lesson.
• Decide what a broken limiter does. If the limiter itself fails, most APIs should let traffic through and raise an alarm rather than refuse everything; Stripe’s post describes catching every error in the limiter so that it fails open (Stripe). A limit that guards against abuse or cost may justify the opposite choice.

Interview questions

What is the difference between a token bucket and a leaky bucket? In a token bucket, tokens drip in at a steady rate up to a capacity, and each request takes one: requests pass at once while tokens last, so bursts up to the capacity go through and the long-run rate is the refill rate. In a leaky bucket used as a queue, the requests themselves wait and leave at a steady rate: the service sees an even stream, a burst turns into waiting time, and requests that find the bucket full are refused. So a token bucket limits how much passes and adds no delay, while a leaky bucket decides when work reaches the service. Used as a meter without a queue, a leaky bucket makes the same decisions as a token bucket; ITU-T I.371 defines that meter, the generic cell rate algorithm, in two equivalent forms.

How does an HTTP API tell a client that it is being rate limited, and when it may try again? With status 429 Too Many Requests, defined in RFC 6585, which should explain the condition and may carry a Retry-After field. Retry-After, defined in RFC 9110, gives a number of seconds or an HTTP date; the client should wait at least that long and add a small random delay, so that many clients do not return at the same instant. Many APIs also describe the quota on every response; the RateLimit-Policy and RateLimit fields of an IETF Internet-Draft do this in a standard form, but they are not a standard yet. Caches must not store a 429 response, and an overload that has nothing to do with one client’s allowance is better reported as 503 Service Unavailable.

Key takeaways

• A token bucket allows bursts up to its size b and r a second after that, so any T seconds carry at most b + r × T requests; GCRA makes the same decisions with one number per key.
• A leaky bucket queues requests and releases them at an even rate: no burst reaches the service, and requests wait instead.
• A fixed window is the cheapest and lets twice the limit through at a window’s edge, and every client starts again at the same instant.
• A sliding log is exact and stores a timestamp per request: use it for small limits that must hold.
• A sliding window counter estimates from two counts: close on steady traffic, but up to about twice the limit on traffic shaped against it.
• Refuse with 429 and a Retry-After rounded up to a whole second, describe limits with the RateLimit fields (still a draft), and keep 503 for overload.