Skip to content
Velloreth
Technology 4 min read

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

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

AlgorithmBurstAccuracyState
Fixed windowat the edgelowone counter
Sliding windownohigha log or a weighted count
Token bucketyeshigha token count
Leaky bucketnohigha 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.

KeyUse
The user ida per-user limit
The IPan anonymous limit
The API keya per-client limit
The endpointa per-route limit
A combinationa 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

TierLimit
Anonymous10 per minute
Free100 per hour
Paid10,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.

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.

Frequently asked questions

What is rate limiting?
A control that caps the number of requests a client may make in a period, so one client cannot consume the whole capacity. It protects against an abuse, a bug and a denial of service. It is applied per user, per IP, per API key or per endpoint.
What is a token bucket?
An algorithm where a bucket holds tokens that refill at a fixed rate, and each request consumes one. It allows a burst up to the bucket size and then limits to the refill rate. It is the common choice for an API, because a short burst is usually legitimate.
What is the difference between a fixed window and a sliding window?
A fixed window counts the requests in a fixed period, such as a minute, and resets at the boundary, which allows a double burst at the edge. A sliding window looks back over the last period from the current time, which is more accurate and needs more state.
What is a leaky bucket?
An algorithm where the requests enter a queue and are processed at a fixed rate, so 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.
How do I rate limit across several servers?
Use a shared store such as Redis and an atomic operation, such as an increment with an expiry or a Lua script. A per-server limit is not a global limit, because each server has its own counter. The shared store is a dependency, so a fallback is needed when it is unavailable.
What should the response be?
A 429 Too Many Requests with a Retry-After header, and the rate limit headers so the client can adapt. A 429 is not a 403, because the request is not forbidden, it is too frequent. The client should back off and retry after the indicated time.