Why limit requests at all
A server has a finite amount of work it can do. Without a limit, one client can use all of it: a script stuck in a loop, a scraper, or an attacker guessing passwords. Everyone else gets slow answers or none.
A rate limiter sits in front of the server and enforces a rule such as "100 requests per minute per user". Requests over the limit are turned away at once, usually with the status code 429 Too Many Requests, before they cost the server anything.
A request arrives
The limiter works out who it belongs to: a user, an API key, or an IP address.
The limiter checks that client's recent history
How it remembers that history is the whole difference between the four algorithms on this page.
Under the limit: let it through. Over: reject it
A rejection is cheap. The client is told to slow down and try again later.
Every animation on this page uses the same small limit so the numbers are easy to follow: 4 requests per 8 ticks.
Try it first
Pick a limiter and a kind of traffic. Above the line is what arrived: green was let through, red was rejected. Below the line is what actually reached the server.
Arrived
Reached the server
- let through
- rejected
- reached the server
The rule: Count requests in fixed blocks of time. The count resets at the start of each block. Eight requests in four ticks, right where one window ends and the next begins.
- Let through
- 0
- Rejected
- 0
- Most in any 8 ticks
- 0 (limit 4)
Fixed window
The rule: cut time into fixed blocks and count the requests in each block. When a new block starts, the count goes back to zero.
Example
100 requests per minute
From 12:00:00 to 12:00:59 the limiter counts. Request number 101 in that minute is rejected. At 12:01:00 the count resets and the client has a fresh 100.
import time
def allow(user):
block = int(time.time() // 60) # which minute are we in?
key = f"{user}:{block}"
if counters.get(key, 0) >= LIMIT:
return False
counters[key] = counters.get(key, 0) + 1
return TrueIt is one counter per client, which makes it the cheapest limiter to run. It also has a famous hole. Watch what happens when a burst arrives right where one block ends and the next begins:
Arrived
Reached the server
- let through
- rejected
- reached the server
The rule: Count requests in fixed blocks of time. The count resets at the start of each block. Eight requests in four ticks, right where one window ends and the next begins.
- Let through
- 0
- Rejected
- 0
- Most in any 8 ticks
- 0 (limit 4)
Four requests at the end of block 1 are allowed. The count resets. Four more at the start of block 2 are allowed. Eight requests reached the server in four ticks, twice the limit, and the limiter never noticed, because it only ever looks at one block at a time.
Good at
- One counter per client: tiny and fast
- Easy to explain: the limit resets on the minute
Where it bites
- A burst across a block boundary can reach twice the limit
- Clients learn to send everything the moment the count resets
Sliding window
The rule: count the requests let through in the last 8 ticks, measured from right now. There are no blocks and no reset. The window moves forward with time.
The simplest way to do it is to keep a list of the times of recent requests. On each new request, drop the times that are too old, then count what is left.
Example
No boundary to hide behind
The limit is 4 per 8 ticks. Four requests are let through at ticks 7 and 8. At tick 9 another arrives. Looking back 8 ticks from tick 9, there are already 4. It is rejected. It stays that way until tick 15, when the oldest ones fall out of the window.
The same burst that fooled the fixed window:
Arrived
Reached the server
- let through
- rejected
- reached the server
The rule: Count the requests let through in the last 8 ticks, measured from right now. Eight requests in four ticks, right where one window ends and the next begins.
- Let through
- 0
- Rejected
- 0
- Most in any 8 ticks
- 0 (limit 4)
Good at
- Accurate: the limit holds over every stretch of time, not just inside blocks
Where it bites
- Stores a time for every recent request, which adds up with large limits
- After a burst the client is blocked until the window has moved past it
Token bucket
The rule: each request spends a token. Tokens drip back in at a steady rate, up to a full bucket.
Picture a bucket that holds 4 tokens. One new token is added every 2 ticks. A full bucket stays full: extra tokens are thrown away. A request that finds a token takes it and goes through. A request that finds the bucket empty is rejected.
Example
Saving up for a burst
A client is quiet for a while, so its bucket fills to 4. Then it sends 4 requests at once. All four go through, because four tokens were waiting. The fifth is rejected. After that the client can send one request every 2 ticks, as tokens arrive.
import time
class TokenBucket:
def __init__(self, capacity, tokens_per_second):
self.capacity = capacity
self.tokens_per_second = tokens_per_second
self.tokens = capacity
self.updated = time.monotonic()
def allow(self):
now = time.monotonic()
earned = (now - self.updated) * self.tokens_per_second
self.tokens = min(self.capacity, self.tokens + earned) # never above a full bucket
self.updated = now
if self.tokens >= 1:
self.tokens -= 1
return True
return FalseArrived
Reached the server
- let through
- rejected
- reached the server
The rule: Each request spends a token. Tokens drip back in at a steady rate, up to a full bucket. Ten requests in a single tick, then one per tick for a while.
- Let through
- 0
- Rejected
- 0
- Most in any 8 ticks
- 0 (limit 4)
The token bucket makes a different promise from the window limiters. It says: over time you get the steady rate, and at any moment you may burst by at most one bucketful. That matches how real clients behave. A page load fires ten requests at once and then goes quiet.
Good at
- Allows short bursts while holding the long-term rate
- Two numbers per client: the token count and the time it was last updated
- Two settings to tune separately: bucket size (burst) and drip rate (average)
Where it bites
- A burst plus the drip can pass more than the bucket size in a short stretch
Leaky bucket
The rule: requests wait in a small queue, and the queue is emptied at a steady rate. If the queue is full when a request arrives, it is rejected.
The name comes from a bucket with a small hole in the bottom. Water can be poured in as fast as you like, but it only leaves through the hole at one speed. Pour in too much and it overflows.
Example
A burst goes in, a trickle comes out
The queue holds 4 and releases one request every 2 ticks. Six requests arrive together. Four join the queue and two are rejected. The server receives the four one at a time, 2 ticks apart, as if the burst had never happened.
Look below the line. Whatever shape arrives above it, the server sees the same steady drip.
Arrived
Reached the server
- let through
- rejected
- reached the server
The rule: Requests wait in a small queue that is emptied at a steady rate. A full queue rejects. Ten requests in a single tick, then one per tick for a while.
- Let through
- 0
- Rejected
- 0
- Most in any 8 ticks
- 0 (limit 4)
Good at
- The server gets perfectly even traffic
- Protects something fragile behind it, such as an old system or a paid third-party service
Where it bites
- Accepted requests wait in the queue, so they are slower
- A burst of urgent requests cannot jump ahead: the drip rate is the drip rate
One burst, four limiters
All four at once, facing the burst on the block boundary.
Tick 0 of 40. Eight requests in four ticks, right where one window ends and the next begins. Above each line: what arrived. Below: what reached the server.
And facing a single large spike:
Tick 0 of 40. Ten requests in a single tick, then one per tick for a while. Above each line: what arrived. Below: what reached the server.
What to notice:
- Fixed window is the only one that hands the whole burst to the server.
- Sliding window is the strictest. It never passes more than 4 in any 8 ticks.
- Token bucket lets the first part of a burst through at once, then settles into the steady rate.
- Leaky bucket turns any shape of traffic into the same even line.
Which one should you use?
| What you need | A good first choice |
|---|---|
| The simplest thing that mostly works | Fixed window |
| A limit that is exact, for example on login attempts | Sliding window |
| A public API where short bursts are normal | Token bucket |
| Even traffic into something that cannot take spikes | Leaky bucket |
Key takeaways
- A rate limiter rejects requests over a limit before they cost the server anything.
- Fixed window counts in blocks. It is cheap, and a burst across a boundary can reach twice the limit.
- Sliding window measures back from right now, so the limit holds over every stretch of time.
- Token bucket allows a burst up to the bucket size, then the steady drip rate.
- Leaky bucket queues requests and releases them at one even speed.