Pointer Walk

Rate Limiting

Fixed window, sliding window, token bucket and leaky bucket face the same burst, and one of them lets twice the limit through.

System DesignIntermediate11 min read

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.

  1. A request arrives

    The limiter works out who it belongs to: a user, an API key, or an IP address.

  2. The limiter checks that client's recent history

    How it remembers that history is the whole difference between the four algorithms on this page.

  3. 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.

Fixed window · limit 4 per 8 ticksInteractive
Limiter
Traffic
Block 1: requests counted0 / 4

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.

python
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 True

It 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:

Fixed window · limit 4 per 8 ticksInteractive
Block 1: requests counted0 / 4

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:

Sliding window · limit 4 per 8 ticksInteractive
Let through in the last 8 ticks0 / 4

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.

python
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 False
Token bucket · limit 4 per 8 ticksInteractive
Tokens in the bucket4 / 4

Arrived

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.

Leaky bucket · limit 4 per 8 ticksInteractive
Requests waiting in the queue0 / 4

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.

Same requests, four limiters · burst on the boundaryInteractive
Fixed window0 through · 0 rejected · busiest 8 ticks 0
Sliding window0 through · 0 rejected · busiest 8 ticks 0
Token bucket0 through · 0 rejected · busiest 8 ticks 0
Leaky bucket0 through · 0 rejected · busiest 8 ticks 0

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:

Same requests, four limiters · one big spikeInteractive
Fixed window0 through · 0 rejected · busiest 8 ticks 0
Sliding window0 through · 0 rejected · busiest 8 ticks 0
Token bucket0 through · 0 rejected · busiest 8 ticks 0
Leaky bucket0 through · 0 rejected · busiest 8 ticks 0

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 needA good first choice
The simplest thing that mostly worksFixed window
A limit that is exact, for example on login attemptsSliding window
A public API where short bursts are normalToken bucket
Even traffic into something that cannot take spikesLeaky 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    9 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress