LESSON 11.2
Rate-limiting algorithms
Fixed window, sliding log, sliding window counter, token bucket and leaky bucket, worked through with numbers.
6 min read
All rate limiters answer the same question, "has this key made too many requests recently?", but they define "recently" differently. The differences show up at window edges and during bursts.
Step across a window boundary, then compare the same traffic with a sliding window or a bucket.
Fixed window counter
Keep one counter per key per window, such as ratelimit:user7:12:01. Increment it; reject when it exceeds the limit. Let the key expire after the window.
It's the cheapest possible: one counter, one atomic increment. Its flaw is the edge burst: a client can spend a full limit at the end of one window and another at the start of the next, briefly doubling the rate.
Sliding log
Store a timestamp for every request in the last window (a sorted set in Redis). On each request, drop timestamps older than the window, count what's left, and allow if under the limit.
It's exact, with no edge bursts. But it stores one entry per request: a limit of 10,000 per hour means up to 10,000 entries per key. Good for low limits on sensitive operations, such as login attempts.
Sliding window counter
A cheap approximation of the sliding log. Keep counters for the current and previous fixed windows, and weight the previous one by how much of it still falls inside the sliding window.
- Previous minute
- 90 requests
- Overlap with the last 60 s
- 20 of 60 s = 1/3
- Current minute so far
- 30 requests
- Estimate
- 90 × 1/3 + 30 = 60 → allowed
Two counters per key, smooth behavior, and accurate enough in practice. It assumes requests in the previous window were spread evenly, which is usually fine.
Token bucket
Each key has a bucket holding up to capacity tokens, refilled at rate tokens per second. A request takes a token; no token, no entry. Store just two numbers per key: tokens left and the last refill time, and compute the refill lazily on each request.
- Capacity 10, rate 1 per second. The bucket starts full.
- A burst of 10 requests at once: all allowed, bucket empty.
- Half a second later, one more: the bucket holds 0.5 tokens, rejected. Retry-After is about 0.5 s.
- Over any long period, the client averages 1 request a second, with bursts of up to 10.
Token buckets express two separate things, sustained rate and allowed burst, which matches how real clients behave. They're what most API gateways and cloud providers use.
Leaky bucket
Requests enter a queue that drains at a constant rate; if the queue is full, new requests are rejected. Output is perfectly smooth. It's the right tool for shaping traffic to a downstream that can't handle bursts, such as a partner API with a strict rate.
Fixed window
- Cheapest: one counter
- Edge bursts up to 2× the limit
Pick it when: Coarse limits where precision doesn't matter.
Sliding log
- Exact
- Memory grows with the limit
Pick it when: Low limits on sensitive actions like logins.
Sliding window counter
- Two counters
- Smooth
- Approximate
Pick it when: A good general default for per-minute limits.
Token bucket
- Separate burst and rate
- Two numbers per key
- Needs an atomic read-modify-write
Pick it when: API limits, the most common choice.
Try it
Distributed API Rate Limiter HLD
Choose an algorithm and its parameters for a public API.