These are the notes for System Design episode 19. ChaiNow's public API (episode 18) is flooded by one partner's buggy script, and real customers can't order. You'll invent rate limiting, count requests with a fixed window and watch a bot get double the limit at the window's edge, fix it with the token bucket, answer politely with 429 Too Many Requests and Retry-After, make the limit hold across several servers with one shared, atomic counter, and stop blocked clients from stampeding back with exponential backoff and jitter. Every demo is plain Python and runs as-is; outputs are real (Python 3.13). Capacities, limits and traffic are made-up numbers; time is simulated (t in seconds), so the outputs never change.
The problems
| Problem | What it teaches |
|---|---|
| One script floods the API | Noisy clients, capacity, rate limiting per user |
| Counting per minute | Fixed window counter |
| The bot waits for the edge | The window-edge burst; token bucket; sliding log and sliding window |
| Tell the client politely | 429 Too Many Requests, Retry-After, x-ratelimit-* headers |
| Three servers, three counters | A shared counter (Redis), race conditions, atomic INCR |
| Everyone retries at once | Exponential backoff, jitter, the thundering herd |
Problem 1: one script floods the API
The servers handle 10 requests a second. A partner's script retries in a tight loop: 95 requests a second. Five real customers order in the same second.
import random
random.seed(4)
CAPACITY = 10 # the server can handle 10 requests a second
# one second of traffic: a buggy script + five real customers
arrivals = ["bot"] * 95 + ["asha", "ravi", "meena", "john", "priya"]
random.shuffle(arrivals) # they arrive mixed up
served = arrivals[:CAPACITY]
print("no limit: ", served.count("bot"), "bot,", [u for u in served if u != "bot"])
seen = {}
def under_limit(user, limit=2): # at most 2 requests per user per second
seen[user] = seen.get(user, 0) + 1
return seen[user] <= limit
fair = [u for u in arrivals if under_limit(u)]
served = fair[:CAPACITY]
print("with limit:", served.count("bot"), "bot,", [u for u in served if u != "bot"])
Output:
no limit: 10 bot, []
with limit: 2 bot, ['asha', 'john', 'priya', 'ravi', 'meena']
Rate limiting caps how many requests each client may make in a period of time. It protects the servers and keeps things fair. A client is identified by something like an API key, a user id or an IP address.
Problem 2: counting per minute (fixed window)
A ration shop keeps a fresh register page each month and ticks each visit. A fixed window counter does the same: the window is a block of time (this minute), and the counter's key is (user, current minute).
LIMIT, WINDOW = 5, 60 # 5 requests per user per minute
counts = {}
def allow(user, t): # t = time in seconds
key = (user, t // WINDOW) # which minute are we in?
counts[key] = counts.get(key, 0) + 1
return counts[key] <= LIMIT
print("ravi, 7 requests at t=10:",
["ok" if allow("ravi", 10) else "429" for _ in range(7)])
times = [59] * 5 + [60] * 5 # the bot waits for the edge
got = [t for t in times if allow("bot", t)]
print(f"bot: {len(got)} allowed between t=59 and t=60, limit is {LIMIT}/min")
Output:
ravi, 7 requests at t=10: ['ok', 'ok', 'ok', 'ok', 'ok', '429', '429']
bot: 10 allowed between t=59 and t=60, limit is 5/min
t // 60 is integer division: seconds 0-59 are minute 0, second 60 starts minute 1 with a fresh count. At the edge of two windows a client can get double the limit in a moment. Fixed windows are simple and cheap (one counter per user) but leaky at the edges.
Problem 3: the token bucket
A jar holds at most 5 tokens (the bucket size, the biggest burst). A machine drops in a token every 12 seconds (the refill rate, 5 a minute); when the jar is full, new tokens are lost. Every request takes a token; no token, no entry. Because tokens arrive at a known rate, you can say exactly how long to wait.
RATE, SIZE = 5 / 60, 5 # 5 tokens a minute; the bucket holds 5
bucket = {"tokens": SIZE, "t": 0}
def allow(t):
passed = t - bucket["t"] # refill for the time passed
bucket["tokens"] = min(SIZE, bucket["tokens"] + passed * RATE)
bucket["t"] = t
if bucket["tokens"] >= 1:
bucket["tokens"] -= 1 # spend one token
return "ok"
wait = (1 - bucket["tokens"]) / RATE # until one token is back
return f"429(retry after {wait:.0f}s)"
print("ravi, 7 at t=0: ", *[allow(0) for _ in range(7)])
print("ravi, 3 at t=30:", *[allow(30) for _ in range(3)])
bucket.update(tokens=SIZE, t=0)
got = [t for t in [59] * 5 + [60] * 5 if allow(t) == "ok"]
print(f"bot: {len(got)} allowed between t=59 and t=60")
Output:
ravi, 7 at t=0: ok ok ok ok ok 429(retry after 12s) 429(retry after 12s)
ravi, 3 at t=30: ok ok 429(retry after 6s)
bot: 5 allowed between t=59 and t=60
- At t = 0 the full bucket allows a burst of 5; the next token is 12 s away.
- By t = 30, 30 × 5/60 = 2.5 tokens are back: 2 requests pass, and the half token needs 6 more seconds.
- The edge attack gets only 5: there is no window edge, tokens just drip in.
The bucket stores only two numbers per user (tokens, last time), and it allows short bursts while enforcing the average. Stripe's docs suggest that clients too use "a client-side token bucket rate-limiting algorithm" to pace their own calls. (A close cousin, the leaky bucket, queues requests and lets them out at a fixed rate.)
Other ways to count
| Algorithm | Stores per user | Edge burst? | Notes |
|---|---|---|---|
| Fixed window | 1 counter | Yes (up to 2x) | Simplest |
| Sliding log | One timestamp per request | No | Exact, uses more memory |
| Sliding window counter | 2 counters | Mostly no | Weights the previous window's count by how much of it overlaps; cheap approximation |
| Token bucket | 2 numbers | No | Bursts up to the size, average = refill rate |
Problem 4: tell the client
RFC 6585 (2012), section 4: "The 429 status code indicates that the user has sent too many requests in a given amount of time ("rate limiting")." The response "MAY include a Retry-After header indicating how long to wait before making a new request." Its example reply is HTTP/1.1 429 Too Many Requests with Retry-After: 3600, and "Responses with the 429 status code MUST NOT be stored by a cache."
HTTP/1.1 429 Too Many Requests
Retry-After: 12
x-ratelimit-limit: 5
x-ratelimit-remaining: 0
x-ratelimit-reset: 1793263260
{"error": "rate limit: 5 requests per minute"}
Real APIs:
| API | Limit (from its docs) | Over the limit |
|---|---|---|
| GitHub REST API | 60 requests/hour unauthenticated; 5,000/hour for an authenticated user | 403 or 429; headers x-ratelimit-limit, -remaining, -used, -reset (UTC epoch seconds) |
| Stripe API | 100 requests/second in live mode, 25 in a sandbox (global, per account) | 429 Too Many Requests with a Stripe-Rate-Limited-Reason header |
GitHub's guidance: if retry-after is present, "you should not retry your request until after that many seconds has elapsed"; if x-ratelimit-remaining is 0, wait until x-ratelimit-reset.
Problem 5: three servers, three counters
Since episode 6 ChaiNow runs three API servers behind a load balancer that takes turns.
LIMIT = 5 # 5 requests per user per minute
servers = [{}, {}, {}] # each server's own counter
shared = {} # one counter all servers use
def allow(counter, user):
counter[user] = counter.get(user, 0) + 1 # Redis: INCR, one atomic step
return counter[user] <= LIMIT
local_ok = shared_ok = 0
for i in range(15): # the bot sends 15 in one minute
server = servers[i % 3] # the load balancer takes turns
local_ok += allow(server, "bot")
shared_ok += allow(shared, "bot")
print(f"own counter per server: {local_ok} of 15 allowed")
print(f"one shared counter: {shared_ok} of 15 allowed")
Output:
own counter per server: 15 of 15 allowed
one shared counter: 5 of 15 allowed
Each server saw only 5 of the bot's requests, so each thought it was fine. The fix is one shared counter in a fast in-memory store like Redis that every server checks.
The race condition
If two servers read the count at the same moment, both can allow:
LIMIT = 5
count = {"bot": 4} # 4 requests already this minute
# servers A and B each get a request at the same moment
a_saw = count["bot"] # A reads 4
b_saw = count["bot"] # B reads 4 (A hasn't written yet)
count["bot"] = a_saw + 1 # A writes 5
a_ok = a_saw + 1 <= LIMIT
count["bot"] = b_saw + 1 # B writes 5 too
b_ok = b_saw + 1 <= LIMIT
print("A allowed:", a_ok, "| B allowed:", b_ok, "| counter:", count["bot"])
print("requests allowed this minute:", 4 + a_ok + b_ok, "limit:", LIMIT)
Output:
A allowed: True | B allowed: True | counter: 5
requests allowed this minute: 6 limit: 5
The read and the add must be one atomic step (nothing can happen in between). Redis's INCR adds one to a key and returns the new value in one step, so every server sees a different number; an expiry on the key (e.g. 60 seconds) resets the window.
Problem 6: everyone retries at once
import random
random.seed(7)
def waits(jitter, tries=4): # seconds to wait before each retry
out = []
for n in range(tries):
base = 2 ** n # 1, 2, 4, 8: exponential backoff
out.append(round(random.uniform(0, base), 1) if jitter else base)
return out
for jitter in [False, True]:
print("jitter" if jitter else "no jitter")
for client in ["A", "B", "C"]:
print(f" client {client} waits", waits(jitter))
Output:
no jitter
client A waits [1, 2, 4, 8]
client B waits [1, 2, 4, 8]
client C waits [1, 2, 4, 8]
jitter
client A waits [0.3, 0.3, 2.6, 0.6]
client B waits [0.5, 0.7, 0.2, 4.1]
client C waits [0.0, 0.9, 0.3, 0.7]
Exponential backoff doubles the wait after each failure. Jitter picks a random wait between 0 and that number, so clients spread out. Stripe: "Follow an exponential backoff schedule to reduce request volume when necessary, and add randomness to the backoff schedule to avoid a thundering herd effect." And if the server sent Retry-After, wait at least that long.
The whole chain
- A bot floods the API → per-user limit: customers served 0 → 5.
- Fixed window: 5/min, but 10 slip through at the edge.
- Token bucket: bursts of 5, average 5/min, and it knows the wait.
- Reply 429 Too Many Requests + Retry-After (+
x-ratelimit-*). - 3 servers → 3 counters → 15 of 15; one shared counter, atomic INCR → 5 of 15.
- Clients: exponential backoff + jitter.
Common mistakes (and the real errors)
| Mistake | Code | Error / result | Fix |
|---|---|---|---|
| No limit at all | every request goes in | no limit: 10 bot, [] |
Per-client rate limit |
| Plain fixed window | key = (user, t // 60) |
bot: 10 allowed between t=59 and t=60, limit is 5/min |
Token bucket or sliding window |
| Counting in each server's memory | counts = {} per server |
own counter per server: 15 of 15 allowed |
One shared counter (Redis) |
| Read, then write the counter | n = get(); set(n + 1) |
requests allowed this minute: 6 limit: 5 |
Atomic INCR |
| Retrying on a fixed schedule | time.sleep(2 ** n) |
client A waits [1, 2, 4, 8] (B and C too) |
Jitter; honour Retry-After |
Rejecting with 500 or 200 |
return 200, {"error": "slow down"} |
clients can't tell to back off | 429 + Retry-After |
Mini project: a sliding-log limiter that answers like a real API
# Mini project: a sliding-log rate limiter that answers like a real API
from collections import deque
LIMIT, WINDOW = 3, 10 # 3 requests per 10 seconds, per user
log = {} # user -> times of allowed requests
def handle(user, t):
times = log.setdefault(user, deque())
while times and times[0] <= t - WINDOW:
times.popleft() # forget requests older than the window
if len(times) < LIMIT:
times.append(t)
return 200, {"x-ratelimit-remaining": LIMIT - len(times)}
retry = times[0] + WINDOW - t # when the oldest one leaves the window
return 429, {"Retry-After": retry, "x-ratelimit-remaining": 0}
for t in [0, 1, 2, 3, 9, 10, 11, 12]:
print(f"t={t:2}", *handle("ravi", t))
Output:
t= 0 200 {'x-ratelimit-remaining': 2}
t= 1 200 {'x-ratelimit-remaining': 1}
t= 2 200 {'x-ratelimit-remaining': 0}
t= 3 429 {'Retry-After': 7, 'x-ratelimit-remaining': 0}
t= 9 429 {'Retry-After': 1, 'x-ratelimit-remaining': 0}
t=10 200 {'x-ratelimit-remaining': 0}
t=11 200 {'x-ratelimit-remaining': 0}
t=12 200 {'x-ratelimit-remaining': 0}
The window slides with time: at t = 10 the request from t = 0 has left it, so one slot opens; at 11 and 12 the next ones open. Exact, but it keeps one timestamp per request. Extend it: add a second, per-IP limit, and send x-ratelimit-reset.
Practice
- Homework: in the token bucket demo, use a size of 2 and a rate of 1 token per second. What prints?
- Homework: in the fixed window demo, send 4 at t = 59 and 4 at t = 60. How many pass?
- Homework: in the shared counter demo, use 5 servers instead of 3. What does the per-server version allow?
- An OTP (one-time password) SMS API: what limit would you set per phone number, and why?
- A token bucket has size 100 and refills 10 per second. What is the biggest burst, and the long-run average?
- Why must a 429 response not be cached?
Solutions and hints
1. RATE, SIZE = 1, 2:
ravi, 7 at t=0: ok ok 429(retry after 1s) 429(retry after 1s) 429(retry after 1s) 429(retry after 1s) 429(retry after 1s)
ravi, 3 at t=30: ok ok 429(retry after 1s)
bot: 3 allowed between t=59 and t=60
The bucket never holds more than 2, so even after 30 quiet seconds only 2 pass. At the edge: 2 at t = 59 and 1 refilled token at t = 60.
2. bot: 8 allowed between t=59 and t=60, limit is 5/min: 4 in minute 0 and 4 in minute 1, both under 5, all within two seconds.
3. own counter per server: 15 of 15 allowed again (each server sees 3); the shared counter still allows 5. More servers make per-server counting even leakier: up to servers × limit.
4. Something like 1 per 30-60 seconds and 5 per hour per number (two limits together), because every SMS costs money and attackers use OTP endpoints to spam people. Also limit per IP and per account.
5. A burst of 100 (a full bucket); 10 per second on average.
6. The rejection is about this client at this moment; a cached 429 would block later requests (or other users) that should be allowed. RFC 6585 says it MUST NOT be stored by a cache.
Quick quiz
# token bucket: size 10,
# refill: 1 token per second
# the bucket is full at t = 0
# a client sends 15 requests at t = 0,
# then 15 more at t = 5
# how many are allowed in total?
- A. 10
- B. 15
- C. 20
- D. 30
Answer
B. At t = 0 the full bucket allows 10 (5 rejected). By t = 5, 5 tokens have dripped back, so 5 more pass: 15 in total.
Interview questions
- Why rate limit an API? (Protect capacity, fairness between clients, cost control, abuse and brute-force protection.)
- Fixed window vs sliding window vs token bucket? (Edge burst vs memory vs bursts plus average.)
- What does a token bucket's size control, and its rate? (Largest burst; long-run average.)
- What status code and headers do you return? (429,
Retry-After,x-ratelimit-*.) - How do you rate limit across many servers? (A shared store such as Redis, with atomic
INCRand an expiry, or a token bucket updated atomically.) - What if the shared store is down? (Decide: fail open (allow) to stay available, or fail closed (reject) to stay safe; often a local fallback limit.)
- Where should the limiter run? (At the edge: an API gateway or proxy, next episode; plus client-side pacing.)
- What is a thundering herd, and how do you avoid it? (Many clients retrying at once; exponential backoff with jitter.)
Glossary
| Term | Meaning |
|---|---|
| Rate limiting | Capping how many requests a client may make in a period of time |
| Rate limiter | The code or service that decides allow or reject |
| Capacity | How many requests a server can handle per second |
| Noisy client | One client using far more than its share |
| API key | A secret string identifying the calling client |
| Window | A block of time requests are counted in (e.g. one minute) |
| Fixed window counter | One counter per user per window; resets at each window's start |
| Edge burst | Up to 2x the limit at the boundary of two fixed windows |
| Sliding log | Keeping every request's time and counting the last N seconds exactly |
| Sliding window counter | Approximates a sliding window by weighting the previous window's count |
| Token bucket | Tokens refill at a steady rate up to a size; each request spends one |
| Bucket size | The most tokens the bucket holds: the biggest burst allowed |
| Refill rate | How fast tokens come back: the long-run average allowed |
| Burst | Many requests in a very short time |
| Leaky bucket | Requests queue and leave at a fixed rate |
| 429 Too Many Requests | The HTTP status code for rate limiting (RFC 6585) |
| Retry-After | A response header saying how long to wait before retrying |
x-ratelimit-* headers |
Headers telling the client its limit, what's left and when it resets (GitHub's names) |
| Epoch seconds | Seconds since 1 January 1970 UTC, a common way to send a time |
| RFC | "Request for Comments": the documents that define internet standards |
| Redis | A fast in-memory data store often used for shared counters |
| Race condition | A bug where the result depends on the timing of two things happening at once |
| Atomic operation | A step nothing else can interrupt or interleave with |
INCR |
Redis command: add one to a key and return the new value, atomically |
| Expiry (TTL) | A time after which a stored key is deleted automatically |
| Exponential backoff | Waiting longer after each failure, usually doubling |
| Jitter | Randomness added to wait times so clients spread out |
| Thundering herd | Many clients hitting a server at the same moment, e.g. all retrying together |
| Fail open / fail closed | When the limiter itself breaks: allow everything / reject everything |
Summary
- One noisy client can starve everyone; a per-client rate limit restores a fair share.
- A fixed window is simple but lets 2x the limit through at the edge.
- A token bucket (size + refill rate, two numbers per user) allows bursts, enforces the average, and knows the wait.
- Reject with 429 Too Many Requests and Retry-After; tell clients their budget with
x-ratelimit-*headers. - With many servers, count in one shared store with an atomic operation (Redis
INCR). - Clients retry with exponential backoff and jitter to avoid a thundering herd.
Next episode: where should the rate limiter live? In one front door for every service: proxies and API gateways.
Sources: RFC 6585, "Additional HTTP Status Codes" (2012), section 4; GitHub Docs, "Rate limits for the REST API"; Stripe Docs, "Rate limits"; Redis command reference, "INCR" ("Increments the integer value of a key by one"; its rate-limiter pattern pairs INCR with EXPIRE inside MULTI/EXEC).