Rate limiting: five algorithms, same traffic

Rate limiting is one of the few topics where the algorithms are short enough to implement in full, compare on identical input, and see the differences directly. So rather than describing five approaches, let us build them and run the same traffic through each. The numbers below all come from actually executing the code.

The reason to care is not punishment. It is that one misbehaving client can take down a service for everybody else. A retry loop with no backoff, deployed by a customer who has not noticed, will open connections as fast as your server accepts them until the pool is exhausted. Nobody chose to attack you; a limiter is what stops an accident from becoming an outage.

The setup for every comparison

All limiters implement one method — given a timestamp, allow this request or not — and all are configured identically: ten requests per sixty seconds. Then three traffic patterns:

• Pattern A — ten requests at t=59, ten more at t=61. Twenty requests inside a two-second span, straddling a minute boundary.
• Pattern B — one request per second for two minutes. Sustained, and six times the configured rate.
• Pattern C — a burst of ten at once, then one per second.

Pattern A is the interesting one, and it is where the first algorithm falls over.

Fixed window: simple, and broken at the boundary

Keep a counter and the time the current window started. Reset when the window rolls over.

class FixedWindow:    def __init__(self, limit, window):        self.limit, self.window = limit, window        self.count, self.start = 0, 0.0    def allow(self, now):        if now - self.start >= self.window:            self.start = now - (now % self.window)   # align to window            self.count = 0        if self.count < self.limit:            self.count += 1            return True        return False

Two fields per key and no allocation per request. It is also the cheapest to get wrong in production, because of this:

Pattern A: 10 requests at t=59, then 10 at t=61  fixed window     allowed 20 of 20  (in a 2-second span)

A limit advertised as ten per minute permitted twenty requests in two seconds. The counter reset at the boundary and the client got a fresh allowance immediately after spending the last one. In the worst case a fixed window allows twice its stated limit in an instant, and the burst lands at a predictable moment — the top of the minute — which is exactly when everyone else's scheduled jobs fire too.

If your limit exists to stop abuse, this is a real hole. If it exists to catch a runaway loop eventually, it is adequate and very cheap.

Sliding log: exact, and it charges you for it

Store a timestamp per request; drop the ones that have aged out; count what remains.

class SlidingLog:    def __init__(self, limit, window):        self.limit, self.window = limit, window        self.hits = deque()    def allow(self, now):        while self.hits and self.hits[0] <= now - self.window:            self.hits.popleft()                  # expire old entries        if len(self.hits) < self.limit:            self.hits.append(now)            return True        return False

This is the definitionally correct answer — the window truly slides, so there is no boundary to exploit:

  sliding log      allowed 10 of 20

The cost is memory, and it scales with the limit rather than being constant. At ten requests per minute you store ten timestamps per key, which is nothing. At ten thousand requests per minute across a million API keys you are storing ten billion timestamps, and the limiter has become the largest data structure in your infrastructure. Sliding log is the right choice for expensive endpoints with low limits, and the wrong one for a general-purpose gateway.

Sliding counter: most of the accuracy, a fraction of the memory

The compromise. Keep counts for the current and previous windows, and estimate by weighting the previous one by how much of it still overlaps the sliding period.

class SlidingCounter:    def __init__(self, limit, window):        self.limit, self.window = limit, window        self.cur_start, self.cur, self.prev = 0.0, 0, 0    def allow(self, now):        w = math.floor(now / self.window) * self.window        if w > self.cur_start:            # only carry the count forward if it is the adjacent window            self.prev = self.cur if w - self.cur_start == self.window else 0            self.cur, self.cur_start = 0, w        overlap = 1.0 - (now - self.cur_start) / self.window        est = self.prev * overlap + self.cur        if est < self.limit:            self.cur += 1            return True        return False

At t=61 the current window is one second old, so 59/60 of the previous window still counts. Ten previous requests weighted at 0.983 gives an estimate of 9.83, leaving room for exactly one more:

  sliding counter  allowed 11 of 20

Eleven rather than the exact ten, and eleven rather than the fixed window's twenty. Three integers per key, constant regardless of the limit. The inaccuracy comes from assuming the previous window's requests were spread evenly through it, which they were not — they were clustered at the end. For almost every real use, being within ten percent for constant memory is the correct trade.

Token bucket: the one most APIs actually use

A bucket holds tokens up to some capacity and refills at a steady rate. Each request spends one. Refill lazily on read, so there is no timer to run.

class TokenBucket:    def __init__(self, capacity, refill_per_sec):        self.capacity, self.rate = capacity, refill_per_sec        self.tokens, self.last = float(capacity), 0.0    def allow(self, now):        # Refill for the elapsed time, capped at capacity.        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)        self.last = now        if self.tokens >= 1:            self.tokens -= 1            return True        return False

The two parameters separate concerns that every other algorithm conflates. Capacity is how large a burst you tolerate; rate is the sustained throughput you are willing to serve. They are genuinely different questions, and being able to answer them independently is why this algorithm dominates in practice.

It holds the boundary correctly, and it handles a burst the way real clients behave — an idle client accumulates tokens and may spend them at once, which is usually exactly what you want:

Pattern A (boundary):  token bucket allowed 10 of 20Pattern C (burst of 10, then 1/sec):  token bucket     allowed  19 of 70  sliding log      allowed  11 of 70

Pattern C shows the philosophical difference. The sliding log allows eleven: the burst consumed the entire window and almost nothing else gets through. The token bucket allows nineteen, because it drains the initial ten and then keeps admitting requests as tokens trickle back. Both are correct implementations of different intentions. If a client legitimately idles and then submits a batch, the token bucket serves them and the sliding log does not.

Leaky bucket is the close relative, and the difference is what happens to excess. A token bucket rejects immediately when empty. A leaky bucket queues arrivals and drains them at a fixed rate, so output is perfectly smooth and requests wait rather than fail. That suits traffic shaping toward a downstream system with a hard throughput ceiling; it is wrong for a public API, where a caller would rather be told no than be held indefinitely.

Side by side

For a general-purpose API, token bucket. For an expensive endpoint with a small limit where exactness matters, sliding log. For a high-cardinality gateway where memory dominates, sliding counter. Fixed window only when you knowingly accept the boundary hole.

Where the naive version breaks: more than one server

Everything above assumes one process. Deploy four servers behind a load balancer with per-process counters and your ten-per-minute limit is now forty per minute, varying with how the balancer distributes traffic. The limit has become a number nobody can predict.

Moving the counter to a shared store introduces a second, subtler problem. This is wrong:

# BROKEN under concurrency: read and write are separate operations.count = store.get(key) or 0if count < limit:    store.set(key, count + 1)      # another server wrote here meanwhile    return Truereturn False

Two servers read 9, both conclude there is room, both write 10. Eleven requests pass a limit of ten. Widen the gap between read and write — network latency, a garbage collection pause — and the overshoot grows with the number of servers.

The fix is to make the whole check atomic rather than to make the window between the two steps smaller. An atomic increment that returns the new value is enough for the counter algorithms:

def allow(store, key, limit, window):    count = store.incr(key)            # atomic: increments and returns    if count == 1:        store.expire(key, window)      # first request starts the clock    return count <= limit

Note the ordering: increment first, then decide. You count every request including rejected ones, which is a deliberate choice — it means a client hammering you while blocked keeps the key alive rather than letting it expire into a fresh allowance.

Token bucket needs more than a single increment, because refilling requires reading the timestamp, computing tokens, and writing both back. That is a read-modify-write, so it needs a server-side script or a compare-and-swap loop to stay atomic. This is the practical reason many teams choose a counter algorithm for distributed limiting even when token bucket suits the traffic better.

There is a shortcut worth knowing: limit locally, approximately. Give each server one-Nth of the budget and skip coordination entirely. You lose exactness — an unlucky distribution gets a client throttled early — and you gain a limiter that adds no latency and cannot be taken down by the store being unavailable. For protecting against runaway clients rather than enforcing a contractual quota, that is often the right call.

What to limit by

The key you count against matters as much as the algorithm.

API key or account is the best choice when you have one. It is stable, it identifies the party you have an agreement with, and it survives the client changing network.

IP address is what you fall back to for unauthenticated traffic, and it is unreliable in both directions. An entire office, university, or mobile carrier can share one address, so a per-IP limit throttles thousands of unrelated users together — while an attacker with a pool of addresses evades it entirely. Use it for coarse protection on unauthenticated endpoints and never as a precise control.

Per endpoint matters because requests are not equally expensive. A cached read and a report that scans a large table should not draw on the same allowance. Weighting solves this cleanly: charge a request several tokens rather than one, in proportion to what it costs you. A token bucket handles this naturally, which is another point in its favour.

Layer them. A generous per-account limit to enforce the plan, a tighter per-endpoint limit on the expensive routes, and a coarse per-IP limit in front of anything unauthenticated.

Telling the client what happened

This is where an API is considerate or hostile, and it costs nothing to get right.

Return 429 Too Many Requests — not 400, which suggests the request was malformed and should not be retried, and not 503, which suggests your service is broken. Include Retry-After with the seconds until capacity returns. Include the limit, how much remains, and when the window resets, so a well-behaved client can pace itself instead of discovering the wall by hitting it.

The reason to bother: without these headers, a client's only strategy is to retry and see. Retrying immediately makes things worse for everyone, and it is the rational response to being given no information. Publish the numbers and clients can be well-behaved; withhold them and they cannot.

Distinguish rejection from failure in your own metrics too. A 429 is the system working as designed; a 500 is not. Graphing them together hides both.

Choosing the number, and watching it

Do not pick a round number. Measure what legitimate clients actually do — the median, the ninety-fifth and ninety-ninth percentiles of requests per minute per key — and set the limit above the ninety-ninth. A limit chosen because it sounded generous will either throttle real users or fail to constrain anyone.

Then roll it out in stages: log what would have been rejected without rejecting anything, look at whose traffic would have been cut and whether that seems right, and only then enforce. This step reliably finds a batch job you had forgotten about.

Afterwards, watch the rejection rate per key rather than in aggregate. A global rate of one percent looks fine and may be one important customer being blocked constantly while everyone else is unaffected. Alert on a key transitioning into sustained rejection, because either the limit is wrong for them or something on their side has broken — and both are worth knowing before they write in.