Rate Limiting Algorithms: Token Bucket to Sliding Window
A rate limit protects a service from abuse. Learn the algorithms, the headers, the distributed case, and the client behaviour.
By Velloreth
The purpose
Cap the requests a client may make in a period.
Protect against:
- An abuse
- A bug that loops
- A denial of service
- A credential stuffing
It is applied per user, per IP, per key or per endpoint.
The algorithms
| Algorithm | Burst | Accuracy | State |
|---|---|---|---|
| Fixed window | at the edge | low | one counter |
| Sliding window | no | high | a log or a weighted count |
| Token bucket | yes | high | a token count |
| Leaky bucket | no | high | a queue |
The fixed window
Limit: 100 requests per minute
Window: 12:00:00 - 12:00:59
A counter per window.
The problem: a double burst at the edge.
12:00:59 -> 100 requests
12:01:00 -> 100 requests
= 200 requests in two seconds
The sliding window
Look back over the last period from the current time.
A log of the timestamps, or a weighted count of the current and the previous window.
It is more accurate and needs more state.
The token bucket
Bucket size: 100
Refill rate: 10 per second
Each request consumes a token.
The bucket refills at a fixed rate.
It allows a burst up to the bucket size, then limits to the refill rate.
It is the common choice for an API, because a short burst is usually legitimate.
function allow(bucket, now) {
const elapsed = now - bucket.lastRefill;
bucket.tokens = Math.min(bucket.size, bucket.tokens + elapsed * bucket.rate);
bucket.lastRefill = now;
if (bucket.tokens >= 1) {
bucket.tokens -= 1;
return true;
}
return false;
}
The leaky bucket
The requests enter a queue and are processed at a fixed rate.
The output is smooth.
It is the opposite of a token bucket, which allows a burst.
It is used when a steady rate matters more than a burst.
The distributed case
A per-server limit is not a global limit.
Each server has its own counter, so N servers allow N times the limit.
The fix: a shared store and an atomic operation.
-- Redis, atomic
local current = redis.call('INCR', KEYS[1])
if current == 1 then
redis.call('EXPIRE', KEYS[1], ARGV[1])
end
return current
The shared store is a dependency, so a fallback is needed when it is unavailable.
A fail-open allows the request when the store is down, and a fail-closed rejects it.
The headers
HTTP/1.1 429 Too Many Requests
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1730000000
Retry-After tells the client when to retry.
The limit headers let the client adapt before it is blocked.
A 429 is not a 403, because the request is not forbidden, it is too frequent.
The client
A client should:
- Read the headers
- Back off on a 429
- Retry after the indicated time
- Add a jitter
A client that retries immediately makes the problem worse.
An exponential backoff with a jitter is the pattern.
The key
The limit is applied to a key.
| Key | Use |
|---|---|
| The user id | a per-user limit |
| The IP | an anonymous limit |
| The API key | a per-client limit |
| The endpoint | a per-route limit |
| A combination | a finer limit |
An IP behind a proxy is the proxy’s address, so the X-Forwarded-For header is needed.
A shared IP such as a corporate NAT means one user can exhaust the limit for many.
The tiers
| Tier | Limit |
|---|---|
| Anonymous | 10 per minute |
| Free | 100 per hour |
| Paid | 10,000 per hour |
A tier is a business decision as much as a technical one.
Common mistakes
A per-server limit. N times the limit.
A fixed window with no edge handling. A double burst.
No Retry-After. A blind retry.
A 403 instead of a 429. A wrong signal.
A limit on the IP only. A shared IP problem.
No limit on the login. A brute force.
A fail-closed with no fallback. An outage when the store is down.
A limit that is too low. A false positive.
A limit that is too high. No protection.
No metric. The limit is a guess.
A quotable summary
A rate limit caps the requests a client may make in a period, and a token bucket allows a burst up to the bucket size and then limits to the refill rate, which is why it is the common choice for an API. A fixed window allows a double burst at the edge and a sliding window is more accurate and more expensive, and a distributed limit needs a shared store and an atomic operation. A 429 with a Retry-After tells the client what to do, and the client should back off with a jitter.
Related reading
For the related topics, see rest-api-rate-limiting and caching-strategies-guide. For the broader context, load-balancing-algorithms and owasp-top-ten-guide.