Rate limiting: the four algorithms and when each is wrong

Rate limiting looks like a solved problem until you have to pick an algorithm, at which point the choice determines your failure mode.

fixed window#

Count requests per fixed interval. Reset the counter at the boundary.

key: user:1234:minute:2026-04-06T14:23
incr, expire 60s, reject if > limit

Pros: trivial to implement, one counter, minimal memory.

Cons: the boundary problem. A client can send the full limit at 14:23:59 and the full limit again at 14:24:00 — double the intended rate, in one second, legally.

Use when: the limit is generous relative to the burst you can absorb, and simplicity matters more than precision. Most internal services.

sliding window log#

Store a timestamp per request. Count the ones inside the window.

Pros: exactly correct. No boundary artifacts.

Cons: memory proportional to the limit times the number of clients. A limit of 10,000 per hour per user across a million users is a lot of timestamps.

Use when: limits are small, precision matters, and client count is bounded. API keys with strict quotas.

sliding window counter#

The practical compromise. Keep counters for the current and previous window, interpolate based on how far into the current window you are.

def allowed(now, limit, window):
    cur_start = now - (now % window)
    elapsed = (now - cur_start) / window
    estimate = prev_count * (1 - elapsed) + cur_count
    return estimate < limit

Pros: two counters per client, no boundary problem in practice, cheap.

Cons: an approximation. Can be slightly wrong at the edges under a very uneven request distribution.

Use when: this is the default. It is what most production rate limiters actually do and it is almost always the right choice.

token bucket#

A bucket holds tokens, refilled at a constant rate up to a maximum. Each request consumes one. Empty bucket, request rejected.

def allowed(bucket, now, rate, capacity):
    bucket.tokens = min(capacity, bucket.tokens + (now - bucket.last) * rate)
    bucket.last = now
    if bucket.tokens >= 1:
        bucket.tokens -= 1
        return True
    return False

Pros: allows bursts up to the bucket capacity while enforcing a long-run average. This matches how real clients behave — idle, then a burst of activity — much better than a strict window.

Cons: two parameters instead of one, and people set them without thinking about what the burst allowance means.

Use when: you want to allow legitimate bursts. Most user-facing APIs. This is the second-best default after sliding window counter and is better when burstiness is expected.

leaky bucket#

A queue drained at a constant rate. Requests enter the queue; overflow is rejected.

Pros: output rate is perfectly smooth, which is what you want when you are protecting a downstream system that cannot handle bursts at all.

Cons: adds latency — requests wait in the queue. Not appropriate for interactive traffic.

Use when: you are shaping traffic to a fixed-capacity downstream, like a third-party API with a hard rate limit, or a legacy system that falls over above a threshold.

the parts everyone gets wrong#

Rate limiting the wrong key. Limiting by IP breaks for users behind NAT and does nothing against a distributed attacker. Limit by authenticated identity where you have one, and by IP only as a coarse pre-auth defense.

Not telling the client anything useful. A 429 with no information is hostile. Send the standard headers:

RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 42
Retry-After: 42

A client that knows when to retry will retry then. A client that does not will hammer you.

No jitter on the client side. If a thousand clients are told to retry in 42 seconds, they all retry at exactly the same moment. Always jitter, and say so in your API documentation.

Rate limiting at the wrong layer. Limiting at the application means the request already consumed a connection, a thread, and possibly a database query. For abuse protection, limit at the edge. For fairness between legitimate users, limit in the application where you know who they are.

Ignoring cost variance. Not all requests are equal. A search that scans a million rows and a health check are both "one request." Weight by cost, or rate-limit expensive endpoints separately, or you will limit the wrong thing.

Global counters in a distributed system. Exact global rate limiting requires coordination on every request, which is a latency and availability problem. The usual answer is per-node limits with the total divided across nodes, accepting some imprecision, or a shared store with local caching and periodic reconciliation.

Decide which imprecision you can live with, deliberately, rather than discovering it during an incident.

the one-line recommendation#

Sliding window counter for fairness, token bucket where bursts are legitimate, limit by authenticated identity, always send Retry-After, always jitter.