Concept · Reliability
Rate-limiting algorithms
Fixed window, sliding log, sliding counter and token bucket, compared on the same traffic.
A rate limiter caps how many requests a client may make per unit of time. Four algorithms dominate; all allow limit requests per window in the long run, but behave differently in the short run.
| Algorithm | State per key | Behaviour | Watch out for |
|---|---|---|---|
| Fixed window | One counter per aligned window | Count requests in 12:00:00–12:00:59, reset at the boundary | Up to 2× the limit across a boundary |
| Sliding log | A timestamp per accepted request | Count requests in the last window seconds — exact | Memory grows with the limit |
| Sliding window counter | Two counters | previous × overlap + current — a close approximation | Slight over-admission right after a boundary |
| Token bucket | Tokens and a timestamp | Bucket of capacity tokens refilled at rate; each request takes one | Allows bursts up to capacity (by design) |
A leaky bucket queues requests and releases them at a constant rate — it smooths output rather than rejecting bursts, and is common in traffic shaping.
Run the same traffic through all four and compare what each lets through:
The token bucket admits a full bucket at once and then follows its refill rate. Switch to window-edge traffic and look at the last column: the fixed window lets twice its limit through around the boundary.
Choosing
- Token bucket for API rate limits: tolerate short bursts, cap the sustained rate. Two numbers of state.
- Sliding window counter for high-volume limits where you want close-to-exact windows cheaply.
- Sliding log for low limits that must be exact, such as login attempts.
- Fixed window for daily and monthly quotas, where boundary bursts don't matter.
In a distributed system
Counters must be shared (usually in Redis) and updated atomically — a Lua script for read-decide-write logic — or each server must enforce a share of the limit locally. Decide whether to fail open or closed when the store is unreachable, and return 429 with Retry-After. The System Design roadmap's rate-limiting lesson builds a Redis token bucket; see also load shedding.