Specialty · System designLesson 4 of 5Free to read

Rate limiting · System Design

How do you stop one client from flooding your API?

Why you need it

A buggy script in a loop, a scraper or an attack can send thousands of requests a second and slow the service down for everyone else. A rate limiter caps how fast each client may call you and answers the rest with HTTP 429 Too Many Requests (defined in RFC 6585). The algorithm you pick decides whether short bursts are allowed and how fair the limit is.

The intuition

Fixed window: count requests per client in each minute (or any window); reject once the count passes the limit. Simple, but a client can send a full allowance at the end of one window and another at the start of the next: twice the limit in a moment.

Token bucket: each client has a bucket that holds up to capacity tokens and refills at rate tokens per second. A request takes one token; no token, no service.

after a quiet spell the bucket is full, so a burst of up to capacity requests is fine
over time the average can't exceed rate
the bucket never holds more than capacity, however long it sat idle

You don't need a timer to refill: when a request arrives, add (now − last) × rate tokens for the time that passed, capped at the capacity.

Definition

Rate limiting

Capping how many requests a client may make in a period of time.

Token bucket

A limiter that allows bursts up to a capacity and an average rate set by the refill speed.

HTTP 429

The status code for "Too Many Requests". It can include a Retry-After header saying when to try again.

Examples

Fixed window

Try it yourself

A limit of 3 per 60 seconds, and the burst at the boundary.

def fixed_window(times, limit, window):
    counts = {}
    result = []
    for t in times:
        w = t // window
        counts[w] = counts.get(w, 0) + 1
        result.append(counts[w] <= limit)
    return result

print(fixed_window([1, 2, 3, 4, 61], 3, 60))
print(fixed_window([58, 59, 59, 60, 60, 61], 3, 60))

Output

[True, True, True, False, True]
[True, True, True, True, True, True]

Step by step

L5Which window the request falls in: 0 for seconds 0–59, 1 for 60–119.
L10The 4th request in window 0 is rejected; 61 starts a fresh window.
L11Six requests within 4 seconds, all allowed: 3 just before the boundary, 3 just after.

Token bucket

Try it yourself

Capacity 3, refilling 1 token per second.

class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity = capacity
        self.rate = rate
        self.tokens = capacity
        self.last = 0

    def allow(self, now):
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

bucket = TokenBucket(capacity=3, rate=1)
for t in [0, 0, 0, 0, 0.5, 1.0, 5.0, 5.0, 5.0, 5.0]:
    print(t, bucket.allow(t))

Output

0 True
0 True
0 True
0 False
0.5 False
1.0 True
5.0 True
5.0 True
5.0 True
5.0 False

Step by step

L9Refill for the time that passed, but never above capacity.
L11A whole token is needed for one request.
L17A burst of 3 at t = 0, then one per second. After a long gap, at most 3 again.

Common mistakes

A limit per server instead of per client

With 10 servers each allowing 100 per minute, a client really gets 1,000. Keep the counters in a shared store such as Redis.

Rejecting without telling when to retry

Clients retry immediately and make it worse. Send 429 with a Retry-After header.

Unbounded refill

If tokens keep piling up while a client is idle, it can send a giant burst later. Cap the bucket at its capacity.

Quick quiz

1. What does this print?

class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity = capacity
        self.rate = rate
        self.tokens = capacity
        self.last = 0

    def allow(self, now):
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

b = TokenBucket(capacity=2, rate=0.5)
print([b.allow(t) for t in [0, 0, 0, 2]])

A
```
[True, True, False, True]
```
B
```
[True, True, True, True]
```
C
```
[True, False, False, True]
```

Show the answer

Answer: A

Two tokens to start; the third request finds none. After 2 seconds at 0.5 per second, one token is back.

2. What's the weakness of a fixed-window limit?

AA client can get about twice the limit around a window boundary
BIt can't count more than 60 requests
CIt needs a timer for every client

Show the answer

Answer: A

The full allowance at the end of one window plus the full allowance at the start of the next.

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictWhich window?
Type exactly what this prints.
ModifyThe bottomless bucket
This token bucket keeps adding tokens while a client is idle, so after a long pause it allows a huge burst. Cap the tokens at capacity when refilling.
WriteA token bucket function
Write token_bucket(times, capacity, rate). times are request times in seconds, in order. The bucket starts full at time 0. Return a list with True (allowed) or False (rejected) for each request.
```
token_bucket([0, 0, 0, 0, 0.5, 1.0], 3, 1)
# [True, True, True, False, False, True]
```

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

Term	Chinese	Definition
Rate limiting	限流	Capping how fast a client may send requests.
Token bucket	令牌桶	Allows bursts up to a capacity and an average rate.
429 Too Many Requests	429 请求过多	The HTTP status for a rate-limited request.