Rate limiting algorithms: bursts, windows and shared quotas

TL;DR: Choose a limiter from the resource you need to protect: request rate, burst size or concurrent work. Define the accounting key and coordination boundary, because a correct local algorithm can still exceed a service-wide quota.

Write the admission contract first

“Allow 60 requests per minute” leaves several questions unanswered. Is that per user, tenant, API key or source address? May all 60 arrive at once? Does a rejected request consume quota? Does a retried request count again? State those decisions before naming an algorithm.

A tenant key is often more meaningful than an IP address for an authenticated API. Many users can share a corporate egress address, while one abusive client can use multiple addresses. Protect the unauthenticated path separately and avoid trusting a caller-supplied tenant header without authentication.

Microsoft's rate-limiting middleware guide describes fixed and sliding windows, token buckets and concurrency limiting. The mechanisms are useful beyond that framework; the enforcement details still depend on the implementation.

Compare the behavior at a boundary

A fixed limit of 60 requests per clock minute can admit 60 just before the minute changes and another 60 just after. That is 120 requests in a short interval without violating either individual window. If the downstream cannot tolerate the burst, the stated fixed-window contract is the wrong protection.

For a token bucket with capacity 20 and refill rate five tokens per second, a full bucket admits an immediate burst of 20 one-token requests. Over the next five seconds, at most 25 additional tokens become available. Admission over that period is bounded by the initial balance plus refill, assuming the bucket is used efficiently and no other limits apply.

Inspect a small token-bucket model

This Python exercise uses explicit timestamps so the result is deterministic. A real concurrent service needs a monotonic clock and atomic updates; this single-threaded model demonstrates the accounting only.

capacity, refill = 20.0, 5.0
tokens, last = capacity, 0.0

def admit(now, cost=1.0):
    global tokens, last
    if now < last or cost <= 0:
        raise ValueError("invalid time or cost")
    tokens = min(capacity, tokens + (now - last) * refill)
    last = now
    if tokens < cost:
        return False
    tokens -= cost
    return True

assert sum(admit(0.0) for _ in range(21)) == 20
assert sum(admit(1.0) for _ in range(6)) == 5
assert not admit(1.0, cost=2.0)

The rejected request does not consume tokens in this model. A different billing or abuse policy may choose different accounting, but it must say so. Costs can represent units other than requests when work varies, such as an estimated token budget for inference.

The atomic step includes reading, refilling and deducting. Separate operations permit concurrent requests to spend the same balance.

Decide whether the limit is local or shared

With four replicas each holding an independent bucket that refills at five requests per second, the fleet can admit up to roughly 20 requests per second in aggregate, plus its combined burst allowance. A load balancer does not transform four local buckets into one global bucket.

For a strict tenant-wide limit, coordinate admission through a shared atomic store or a design that assigns bounded quota portions to workers. Shared coordination introduces availability and latency tradeoffs. Quota leasing can reduce per-request coordination but needs an explicit bound on overshoot and treatment of failed workers.

Choose failure behavior by operation. An unavailable quota store might justify temporarily limited local admission for a low-risk read endpoint. A costly provisioning endpoint may instead reject requests until its shared budget can be checked. Record the fallback rather than allowing the client library's exception behavior to choose it accidentally.

Keep waiting and retrying from defeating the limit

An unbounded waiting queue converts immediate overload into delayed overload and memory consumption. Bound queue length and wait time, and cancel requests whose caller deadline has expired. A rate limit also does not cap work duration; combine it with a concurrency bound when slow operations can accumulate.

Return useful retry guidance where the API contract supports it. Clients must still use bounded retries and jitter; retrying rejected requests immediately can consume frontend capacity even when the protected backend is safe.

Self-check: after changing from one replica to four, tenant traffic admitted by a “100 per minute” limiter grows fourfold. Is the token-bucket calculation necessarily wrong?

No. Each replica may be enforcing its own valid local allowance. Inspect where quota state lives and how requests are assigned. If the requirement is one tenant-wide allowance, change the coordination design and test aggregate admission across replicas.