Rate limiting with a token bucket

API design: REST, HTTP, GraphQL and gRPC Mid-level Python 3.13+ PostgreSQL 17+ Reviewed 31 Oct 2026 By Best Latest Apps

Predict the output

Capacity 5, refill 2 per tick. A client sends nothing for two ticks, then 8 requests in tick 3. How many are rejected in tick 3?

Python 3.13

cap, refill = 5, 2
tokens = cap
for arrive in (0, 0, 8):
    tokens = min(cap, tokens + refill)
    allowed = min(tokens, arrive)
    tokens -= allowed
print(arrive - allowed)

Options3018

Hint 1 of 1

Can tokens go above the capacity?

Choose an answer, then open Show answer below to check it.

Capacity 5, refill 2 per tick. A steady 2 requests per tick are all allowed. After two quiet ticks, a burst of 8 gets 5 through and 3 rejected; later ticks show the bucket refilling.

Run on Redis 7

Text version

Steady: rejected 0
Tick	Arrive	Tokens before	Allowed
T1	2	5	2
T2	2	5	2
T3	2	5	2
T4	2	5	2
T5	2	5	2
T6	2	5	2

Burst after quiet: rejected 6
Tick	Arrive	Tokens before	Allowed	Rejected
T1	0	5	0	0
T2	0	5	0	0
T3	8	5	5	3
T4	1	2	1	0
T5	6	3	3	3
T6	2	2	2	0

Show answer

Answer: A 3

Correct. The bucket is capped at 5, so 5 of 8 pass and 3 are rejected.

A token bucket refills over time but never above its capacity, which caps how big a burst can be. After the quiet ticks there are 5 tokens; 5 of the 8 requests take one each and the other 3 find it empty.

Why not the others?

B 0. Tokens never exceed the capacity, however long the client is quiet.
C 1. That assumes 7 tokens built up; the cap is 5.
D 8. The quiet ticks left a full bucket.

30-second answer

A token bucket holds up to N tokens and refills at a steady rate; each request takes a token or is rejected when none are left. Unused tokens build up to the capacity, so a client that was quiet can send a short burst, while the long-run rate stays capped by the refill. A fixed window counts requests per clock minute, which lets a client send double the limit across a window boundary and resets abruptly.

Practise saying it · 35 s. No recording, just a timer

Explain a token bucket.

Say your answer out loud, then check which of these points you covered:

Capacity and refill rate
Bursts up to capacity
Long-run rate capped
Fixed window boundary problem
Atomic in Redis

Deep dive

Sliding-window logs are exact but store every timestamp; sliding-window counters approximate cheaply.

Leaky bucket smooths output to a constant rate, often used for shaping rather than rejecting.

In a cluster, keep the bucket in Redis and update it atomically with a Lua script, or limit per instance and accept some slack.

Limit by API key or user, not only IP, so a whole office behind one NAT isn't punished.

A token bucket in Redis, ticks passed in for a repeatable run Ran on Python 3.13.5 · mypy --strict

Python 3.13

import redis

LUA = """
local cap = tonumber(ARGV[1])
local refill = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local want = tonumber(ARGV[4])
local s = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(s[1]) or cap
local ts = tonumber(s[2]) or now
tokens = math.min(cap, tokens + (now - ts) * refill)
local ok = math.min(tokens, want)
redis.call('HSET', KEYS[1], 'tokens', tokens - ok, 'ts', now)
return ok
"""

r = redis.Redis(decode_responses=True)
take = r.register_script(LUA)
scenarios = {
    "Steady": [2, 2, 2, 2, 2, 2],
    "Burst after quiet": [0, 0, 8, 1, 6, 2],
}
for name, arrivals in scenarios.items():
    rejected = 0
    for tick, want in enumerate(arrivals):
        args = [5, 2, tick, want]
        allowed = int(take(keys=[f"bucket:{name}"], args=args))
        rejected += want - allowed
    print(f"{name}: {rejected}")

Common mistakes

Fixed windows for strict limits.
Read-modify-write on Redis without a script or transaction, so concurrent requests overspend.
No Retry-After on 429.

Senior take & follow-ups

Describe capacity and refill, show the burst behaviour, and contrast with fixed windows.

Follow-up questions

Think of your answer first, then open the hint.

Why use Lua in Redis?
Show hint
The read, refill and decrement run atomically on the server.
Token bucket vs leaky bucket?
Show hint
Token bucket allows bursts up to capacity; leaky bucket smooths to a fixed rate.

Suggest a fix if something here is wrong or out of date.