Modelling API Rate Limiting: Token Buckets, Sliding Windows, and Request Queues

Why rate limiting exists as a control system

An API rate limiter is a small feedback control system sitting in front of a backend, deciding in real time whether to admit or reject each incoming request based on how many requests a client (or the system as a whole) has already made in some recent interval. Its job is to protect shared resources — database connections, compute capacity, downstream third-party APIs with their own limits — from being overwhelmed by any single caller, while still allowing legitimate bursts of traffic to pass through when the system has spare capacity. The interesting engineering detail is that "how many requests in some recent interval" can be measured in several genuinely different ways, and each measurement method produces a different admission pattern for the exact same underlying traffic, which is why the choice of algorithm is worth understanding rather than treating rate limiting as an interchangeable commodity feature.

Fixed window: simple counting with an edge-burst problem

The simplest approach divides time into fixed intervals — for example, non-overlapping 60-second windows starting on the minute — and keeps a counter per client per window. Each request increments the counter; once the counter exceeds the limit, further requests in that window are rejected (typically with an HTTP 429 status and a Retry-After header) until the window resets and the counter returns to zero. This is cheap to implement and cheap to store, since it only requires one counter and one timestamp per client.

Its well-known flaw is the boundary burst problem: because windows are independent, a client can send its full quota of requests in the last moment of one window and its full quota again in the first moment of the next window, producing up to twice the intended limit within a short span that straddles the boundary. For a limit of 100 requests per minute, a client could in principle send 100 requests at 0:59 and another 100 at 1:01 — 200 requests in two seconds — while never technically exceeding the stated per-window limit. Systems that need tighter guarantees against bursting avoid fixed windows for exactly this reason.

Sliding window: smoothing the boundary by weighting two windows

A sliding window log or sliding window counter algorithm fixes the boundary burst problem by not treating windows as fully independent. The sliding window counter approach, for instance, keeps counts for the current and previous fixed windows and computes an estimated count for the trailing N-second window as a weighted combination: (fraction of the previous window still 'inside' the trailing interval) × (previous window's count) + (current window's count). If a client is 40% of the way through the current window, the estimate uses 60% of the previous window's count plus 100% of the current window's count. This produces a much closer approximation to a true rolling count without the cost of storing a timestamp for every individual request, which is what a fully precise sliding window log would require.

The sliding window log variant is the exact version: it stores a timestamp for every request in a per-client structure (often a Redis sorted set), and on each new request it discards timestamps older than the window and counts what remains. This is precise but memory-proportional to request volume during high-traffic periods, which is why most large-scale API gateways use the weighted-counter approximation rather than the full log unless perfect accuracy is required.

Token bucket: separating burst allowance from sustained rate

The token bucket algorithm models each client as having a bucket that holds up to a maximum number of tokens (the burst capacity). Tokens are added to the bucket at a steady refill rate (the sustained rate limit, e.g., 10 tokens per second) up to the bucket's capacity, and each incoming request consumes one token to be admitted; a request arriving when the bucket is empty is rejected or queued. This is a meaningfully different shape of control than a window-based approach: it explicitly separates "how fast can you sustain requests indefinitely" (the refill rate) from "how much can you burst all at once" (the bucket capacity), which maps naturally onto how real client behavior actually looks — mostly steady low-rate polling, punctuated by occasional bursts, such as a mobile app syncing a backlog of offline actions the moment connectivity returns.

The related leaky bucket algorithm inverts the framing: instead of tokens accumulating to allow bursts, requests fill a queue (the bucket) that drains at a constant rate, which smooths bursty input into a perfectly steady output stream but adds queueing latency for any request beyond the leak rate rather than rejecting it outright. Token bucket favors admitting bursts up to a cap and rejecting or delaying only what's left over; leaky bucket favors a constant, predictable output rate regardless of input burstiness, at the cost of added latency during bursts.

What the algorithm choice does to a real traffic trace

These differences are easiest to see by imagining the same synthetic traffic trace — say, a client that sends 5 requests per second steadily, then bursts to 40 requests in one second, then returns to 5 per second — run through each algorithm with roughly equivalent average limits. A fixed window counting 300 requests per minute would likely admit the entire burst if it happens to land inside a single window with unused quota, then potentially throttle unrelated legitimate traffic later in that same window once the quota is exhausted. A sliding window counter would partially smooth this, admitting less of the burst depending on exactly when it falls relative to the window boundary. A token bucket sized with a burst capacity of, say, 40 tokens and a 5-per-second refill rate would admit the entire burst by design (that's exactly the scenario burst capacity exists for) and then correctly throttle back to the sustained rate afterward, with the bucket needing 8 seconds to refill from empty. A leaky bucket would admit the burst into its queue and drain it at a constant 5 per second, meaning the last of the 40 burst requests would be processed roughly 8 seconds after it arrived rather than being rejected — trading rejection for latency.

This is why production API gateways (AWS API Gateway, Kong, Envoy, Cloudflare) commonly expose token bucket as the default, since it maps most intuitively onto "how much can you burst" and "what's your steady rate" as two independently tunable numbers that map onto realistic client behavior, while still being simple enough to implement per-client with a single counter and last-refill timestamp — no need for the timestamp log or weighted-window arithmetic that sliding window approaches require.