These are the notes for System Design episode 28, our second full design problem. A spammer's script has found the URL shortener from episode 27, and ChaiNow now has free users, paying partners and its own internal tools, all needing different limits. In episode 19 you learned the rate limiting algorithms (fixed window, token bucket, sliding log, 429 Too Many Requests, backoff with jitter). Today you design the rate limiter as a real service, the way an interviewer expects: you'll write the requirements, put the limiter in the API gateway (episode 20), keep the limits as rules in data, not code, watch the obvious shared counter let 50 requests through a limit of 10 (a race condition), fix it with one atomic step (Redis INCR, MULTI/EXEC, or a Lua script), cut the memory from 80 GB to 0.16 GB with a sliding window counter, decide what happens when the limiter's own store dies (fail open or fail closed, per endpoint), and finish with 429 + Retry-After and the full design on one page. Every demo is plain Python and runs as-is; outputs are real (Python 3.13). ChaiNow and its partner ChaiStats are made up, and so are their limits.
Rate limiting means capping how many requests one client may make in a period of time. Example: "a free user may shorten at most 10 links per minute; the 11th gets refused". A rate limiter is the piece of software that does the counting and says yes or no to every request. A rate limiter service is a rate limiter built to work for a whole system: many servers, many kinds of users, many endpoints, and failures.
The problems
| Problem | What it teaches |
|---|---|
| The shortener under attack | Requirements; limit by user, API key or IP, per endpoint; plans; where the limiter lives (API gateway, middleware) |
| Limits change every week | Rules as data: plan, path, limit, period; first match wins; a default; a config store cached in every gateway |
| 50 got through a limit of 10 | The read-check-write race condition, threads, why it only fails under attack |
| Count safely | Atomic operations: a lock, Redis INCR, MULTI/EXEC, Lua scripts with EVAL; count first, then decide |
| 80 GB of timestamps | Sliding log vs sliding window counter: memory and accuracy; the window-edge trick blocked |
| The limiter's store dies | Fail open vs fail closed, decided per endpoint, plus an alert |
| Tell the client | 429 Too Many Requests, Retry-After, backoff with jitter |
| Put it all together | The full design: gateway + rules cache + Redis cluster, keys that expire, sharding |
Problem 1: the shortener under attack (requirements)
Last episode we built a free URL shortener for ChaiNow. A spammer's script found it and is making a million short links an hour. Every one of those requests uses the same servers and database as real users, so real users get slow responses.
The first instinct is "block anyone who sends too much". But not everyone is equal:
| Who | What they need | Limit on /shorten |
|---|---|---|
| Free user | Shorten a few links | 10 per minute |
| ChaiStats (a partner who pays) | Shorten links for all their customers | 1,000 per minute |
| ChaiNow's own internal tools | Bulk jobs, tests | No limit |
And some limits protect money, not servers. Logging in with an OTP (one-time password: a code sent by SMS, like 482913) costs ChaiNow a few paise for every SMS sent. A script hammering /send-otp would burn the SMS budget, so that endpoint gets 3 per minute for everyone, partners included.
A few words before we go on:
- An endpoint is one address of an API that does one job, written as its path. Example:
/shortenmakes a short link,/send-otpsends an OTP,/menureturns ChaiNow's menu. - A plan is the kind of account a client has, which decides its limits. Example:
free,partner,internal. - An API key is a secret string a program sends with every request to say who it is, like a membership card. Example: ChaiStats' servers send
X-API-Key: cs_live_7f3a...(made up). It's how we know a request is from a partner when no person logged in. - An IP address is the network address a request comes from. Example:
10.0.0.7. When there's no login and no API key, it's the only thing we can limit by.
The requirements
In a design interview, requirements come first: what must the system do (functional requirements) and how well (non-functional requirements: speed, correctness, availability).
| Requirement | Kind | Why |
|---|---|---|
| Limit by user (or by API key or IP when there's no login), separately per endpoint | Functional | /send-otp and /menu need very different limits |
| Different limits per plan, changeable without a deploy | Functional | The business changes limits; a deploy (releasing new code to the servers) is slow and risky |
| Correct across many servers | Non-functional | ChaiNow runs many gateway servers; the bot's requests land on all of them (episode 19) |
| Fast: adds only a millisecond or two | Non-functional | Every request passes through it |
| Tell clients clearly: 429 + Retry-After | Functional | Good clients can slow down instead of retrying blindly |
| Keep working, or fail safely, when its own store breaks | Non-functional | The limiter must not become the outage (Problem 4) |
Where does it live?
Every request already passes through one front door: the API gateway from episode 20, the server that sits in front of all ChaiNow's services and handles shared jobs like checking who you are and routing the request. So the limiter goes there, as middleware: code that runs on every request before it reaches the real service, and can stop it. Example: the gateway receives POST /shorten, the limiter middleware says "over the limit", and the shortener service never even sees the request.
| Where | Good | Bad |
|---|---|---|
| Inside every service | Close to the code | Every team writes it again; easy to forget one service |
| In the API gateway (middleware) | One place, every request, bad traffic stopped early | The gateway must be fast and reliable (it already must) |
| In the client (the app) | Saves wasted calls | Can't be trusted: a spammer simply skips it |
The counters themselves can't live inside one gateway server, because the gateways are many (episode 19, problem 5). They live in one shared store that every gateway asks. That's Problem 2.
Problem 1, part 2: rules as data, not code
"Changeable without a deploy" means the limits must be data, not code: a list of rules, where each rule says which plan, which path, how many requests, and per what period. A star (*) means "any plan".
# Limits live in a config file, not in the code
RULES = [
{"plan": "free", "path": "/shorten", "limit": 10, "per": "minute"},
{"plan": "partner", "path": "/shorten", "limit": 1000, "per": "minute"},
{"plan": "*", "path": "/send-otp", "limit": 3, "per": "minute"},
]
DEFAULT = {"limit": 100, "per": "minute"}
def rule_for(plan, path):
for r in RULES: # first matching rule wins
if r["path"] == path and r["plan"] in (plan, "*"):
return r
return DEFAULT
for plan, path in [("free", "/shorten"), ("partner", "/shorten"),
("partner", "/send-otp"), ("free", "/menu")]:
r = rule_for(plan, path)
print(f"{plan:<8}{path:<10} -> {r['limit']} per {r['per']}")
Output:
free /shorten -> 10 per minute
partner /shorten -> 1000 per minute
partner /send-otp -> 3 per minute
free /menu -> 100 per minute
How it works:
RULESis a plain list of dictionaries. Nothing in it is logic; it could come from a JSON file or a database table.rule_forwalks the list and returns the first matching rule: the path must be equal, and the plan must be equal or*. If nothing matches, it returnsDEFAULT.- Free
/shorten: 10 per minute. Partner/shorten: 1,000. - Partner
/send-otp: only 3, because the*rule matches every plan, partners included. - Free
/menu: no rule mentions/menu, so it falls back to the default 100 per minute.
Because the first match wins, order matters: put specific rules (one plan) before general ones (*). The common-mistakes table shows what happens otherwise.
In production, the rules sit in a config store: a small database or file service that holds settings for the whole system. Every gateway keeps a copy of the rules in memory (a cache, episode 7) and refreshes it every few seconds. Reading rules from memory costs nothing per request, and changing a limit is editing one line in the config store; within seconds every gateway uses it, with no deploy.
Problem 2: 50 got through a limit of 10 (the race condition)
Real life: the last cinema seat
A cinema has one seat left, F12. Two clerks at two counters both look at their screens: "1 free". Both sell F12. Two people turn up for one seat.
| A cinema | A shared counter |
|---|---|
| Two clerks look: "1 seat free" | Two servers read the counter: both see 9 |
| Both sell seat F12 | Both write back 10: two requests counted once |
| One booking system checks and books in one step | One atomic step: read, add and write together |
When the result depends on who gets there first, and two get there at the same time, it's called a race condition. Episode 19 showed it with two servers by hand. Now let's attack the counter for real.
The obvious code, under attack
A thread is one line of work inside a program; a program can run many threads at the same time. Example: a web server handles each incoming request in its own thread. Here, 50 threads are 50 requests landing on many gateway servers at once.
The obvious limiter: read the counter from the shared store, check it, write it back plus one. Between the read and the write there's a network trip to the store, which we fake with a short time.sleep.
import threading, time
store = {} # pretend this is the shared Redis
LIMIT = 10 # 10 requests per minute
def allow(user):
count = store.get(user, 0) # 1. read the counter
time.sleep(0.3) # (network trip to the store)
if count >= LIMIT:
return False
store[user] = count + 1 # 2. write it back
return True
allowed = []
def request():
if allow("bot"): allowed.append(1)
threads = [threading.Thread(target=request) for _ in range(50)]
for t in threads: t.start()
for t in threads: t.join()
print("limit:", LIMIT, " allowed:", len(allowed), "of 50")
print("counter says:", store["bot"])
Output:
limit: 10 allowed: 50 of 50
counter says: 1
Allowed: 50 of 50, with a limit of 10. And the counter says 1. (This demo depends on timing: on a busy machine a thread can start late, after others have written, so you may occasionally see counter says: 2, or a few fewer than 50 allowed. The failure is the same.) What happened:
- All 50 threads called
store.get("bot", 0)and read 0 before any of them reachedstore[user] = count + 1. - Every one of them checked
0 >= 10(false), so every one was allowed. - Every one wrote
0 + 1. Fifty writes of the same value1. The counter "lost" 49 requests.
The cruel part: this limiter works perfectly when requests come one at a time, and fails completely in exactly the attack it exists for, a burst of requests at once. Tests that send requests one by one will never catch it.
Read, check, then write back is never safe when many workers share one value.
Problem 2, fixed: one atomic step
An atomic operation is a step that happens completely or not at all, with nothing able to happen in the middle. Example: "add 1 and tell me the new value" as one step; no other request can read the counter between the add and the answer.
In Python, a lock makes a block of code atomic among threads: only one thread at a time can hold it, the others wait. Example: with lock: around the add. In Redis, the command INCR does exactly this job by itself.
import threading, time
store, lock = {}, threading.Lock()
LIMIT = 10
def incr(key): # like Redis INCR: one step, atomic
with lock:
store[key] = store.get(key, 0) + 1
return store[key]
def allow(user):
time.sleep(0.3) # (network trip to the store)
return incr(user) <= LIMIT # count first, then decide
allowed = []
def request():
if allow("bot"): allowed.append(1)
threads = [threading.Thread(target=request) for _ in range(50)]
for t in threads: t.start()
for t in threads: t.join()
print("limit:", LIMIT, " allowed:", len(allowed), "of 50")
print("counter says:", store["bot"])
Output:
limit: 10 allowed: 10 of 50
counter says: 50
incradds one and returns the new value, all insidewith lock:. Each of the 50 threads gets a different number: 1, 2, 3, ..., 50.- The order flipped: count first, then decide. If the new count is over the limit, refuse. The threads that got 1 to 10 are allowed; 11 to 50 are refused.
- Allowed: 10 of 50, exactly the limit. And the counter says 50: every request was counted, even the refused ones. (That's a design choice: counting refused requests too means a client that keeps hammering stays blocked. The mini project counts only allowed requests instead; both are fine as long as you choose on purpose.)
How Redis does it
Redis is an in-memory data store (episode 19): it keeps keys and values in RAM, so reading and writing take very little time, and many servers can share it over the network. Example: the key bot:/shorten:28333 holds the number 7.
From the redis.io documentation:
INCR keyadds 1 to the number stored atkey(starting from 0 if the key doesn't exist) and returns the new value. Its time complexity is O(1) (constant time: it takes the same short time however many keys Redis holds). The docs' counter pattern is built on "Redis atomic increment operations".EXPIRE key secondstells Redis to delete the key by itself after that many seconds. That's how an old minute's counter cleans itself up.- The docs' rate limiter pattern uses a key per IP address per second, and sends
INCRandEXPIREtogether insideMULTI/EXEC"to make sure that we'll both increment and set the expire at every API call".MULTIstarts a transaction (a group of commands), Redis queues the commands that follow, andEXECruns them all together, with no other client's command in between. - The docs also show a version that first reads the counter and then increments it, and warn: "In the above code there is a race condition". Their fix turns
INCRand the optionalEXPIRE(only needed when the key was just created) into a Lua script sent withEVAL.
Lua is a small programming language; Redis can run a short Lua script sent with the EVAL command, and it runs the whole script in one go, so the script's steps are atomic together. Example: a script that does "INCR the key; if the result is 1, EXPIRE it in 60 seconds; return the result" is one round trip and one atomic step.
| Need | Redis tool | Atomic? |
|---|---|---|
| Add one, get the new value | INCR |
Yes, one command |
| Add one and set an expiry | INCR + EXPIRE inside MULTI/EXEC |
Yes, run together |
| Add one, set an expiry only if new, or any small logic (like a sliding window estimate) | A Lua script with EVAL |
Yes, the whole script |
Read with GET, decide, then INCR |
Two separate round trips | No: the race condition |
Note that an atomic INCR alone is not enough if you check before you increment; the check must use the value that the atomic step returned (see the common mistakes). You just invented an atomic rate limiter!
Problem 3: 80 GB of timestamps (sliding window counter)
Episode 19 showed the fixed window counter (one counter per user per minute, reset when the minute changes) and its weakness: a bot sends 10 requests at 0:59 and 10 more at 1:00, and gets 20 in two seconds through a limit of 10 per minute. It also listed two cures, the sliding log and the sliding window counter. At ChaiNow's scale, which one?
Real life: counting visitors at a temple
| A temple gate | Rate limit windows |
|---|---|
| Write every visitor's entry time in a book | Sliding log: one timestamp per request. Exact, but the book never ends |
| Keep just two tallies: this hour and last hour | Sliding window counter: two numbers per user. Tiny, nearly exact |
| Halfway through this hour, count half of last hour's visitors | The weighted estimate: smooths the edge |
- A timestamp is the time something happened, stored as a number. Example:
1793263259seconds. - A sliding log keeps the timestamp of every request and counts the ones in the last 60 seconds. Exact, and a window that "slides" with the clock, but it stores one number per request.
- A sliding window counter keeps only two counts per user: this minute's and the previous minute's. If we are a fraction
passedof the way into this minute, it assumes the previous minute's requests were spread evenly, so the part(1 - passed)of them still falls inside the last 60 seconds:
estimate = now + before × (1 - passed)
Example: 15 seconds into this minute (passed = 0.25), with 8 requests last minute and 3 so far this minute, the estimate is 3 + 8 × 0.75 = 9.
LIMIT, WINDOW = 10, 60 # 10 requests per 60 seconds
counts = {} # (user, minute number) -> count
def allow(user, t):
minute = t // WINDOW
now = counts.get((user, minute), 0)
before = counts.get((user, minute - 1), 0)
passed = (t % WINDOW) / WINDOW # how far into this minute we are
estimate = now + before * (1 - passed)
if estimate >= LIMIT:
return False
counts[(user, minute)] = now + 1
return True
# the edge trick from episode 19: 10 at t=59 s, 10 more at t=60 s
first = sum(allow("bot", 59) for _ in range(10))
second = sum(allow("bot", 60) for _ in range(10))
later = sum(allow("bot", 90) for _ in range(10))
print("t=59:", first, " t=60:", second, " t=90:", later)
users, limit = 10_000_000, 1000
print(f"log of timestamps: {users * limit * 8 / 1e9:,.0f} GB")
print(f"two counters each: {users * 2 * 8 / 1e9:,.2f} GB")
Output:
t=59: 10 t=60: 0 t=90: 5
log of timestamps: 80 GB
two counters each: 0.16 GB
The edge trick:
| Time | Minute | now |
before |
passed |
Estimate before each request | Allowed |
|---|---|---|---|---|---|---|
| t = 59 | 0 | 0 → 9 | 0 | 59/60 | 0, 1, ..., 9 | 10 |
| t = 60 | 1 | 0 | 10 | 0 | 10 + 0 = 10 (≥ 10) | 0 |
| t = 90 | 1 | 0 → 4 | 10 | 0.5 | 0 + 5, ..., 4 + 5 = 9, then 5 + 5 = 10 | 5 |
- t = 59: nothing before, 10 allowed.
- t = 60: a new minute, but the whole previous minute still counts (
passed = 0), so the estimate is 10: the edge trick is blocked. A fixed window would have allowed 10 more here. - t = 90: halfway through, half of last minute's 10 still counts (5), so 5 more get in. Smooth, not a cliff.
The memory, for 10 million users with a limit of 1,000 per minute, assuming 8 bytes per timestamp or counter (our assumptions; the arithmetic is in the code):
| Algorithm | Per user | 10 million users |
|---|---|---|
| Sliding log | up to 1,000 timestamps × 8 bytes = 8,000 bytes | 10,000,000 × 1,000 × 8 = 80 GB |
| Sliding window counter | 2 counters × 8 bytes = 16 bytes | 10,000,000 × 2 × 8 = 0.16 GB |
Five hundred times less memory (80 / 0.16 = 500), for a small approximation: the counter assumes last minute's requests were spread evenly, which a bot that sent them all at :59 breaks a little. That's why big rate limiters use counters or token buckets (episode 19), not full logs. You just invented the sliding window counter!
| Algorithm (episode 19 + today) | Stores per user | Edge trick? | Good for |
|---|---|---|---|
| Fixed window | 1 counter | Up to 2× at the edge | Simplest; INCR + EXPIRE |
| Sliding log | 1 timestamp per request | No, exact | Small limits where exactness matters |
| Sliding window counter | 2 counters | Blocked, nearly exact | Large scale, our choice today |
| Token bucket | 2 numbers (tokens, last refill time) | No; allows bursts up to the bucket size | When short bursts are fine |
Problem 4: the limiter's store dies (fail open vs fail closed)
Real life: the guard's register is lost
A building's guard writes every visitor in a register to enforce "10 visitors per flat per day". One day the register is lost. What does the guard do with the next visitor?
| The guard | The rate limiter |
|---|---|
| The register is lost | The counter store (Redis) is unreachable: Connection refused |
| Let everyone in | Fail open: allow requests without a limit. The app stays up, but spammers get a free window |
| Lock the gate | Fail closed: refuse requests. Safe, but now the limiter itself has taken the app down |
There's no single right answer, so we decide per endpoint, in the rules. Browsing the menu should keep working; sending OTPs (which cost money) should stop while we're blind.
Here incr really tries to connect to the counter store at 127.0.0.1 port 6399, where nothing is listening, so the connection really fails:
import socket
def incr(key): # ask the shared counter store
conn = socket.create_connection(("127.0.0.1", 6399), timeout=0.2)
conn.close() # (nobody is listening there today)
return 1
RULES = {"/menu": {"limit": 100, "if_store_down": "open"},
"/send-otp": {"limit": 3, "if_store_down": "closed"}}
def allow(user, path):
rule = RULES[path]
try:
return incr(f"{user}:{path}") <= rule["limit"]
except OSError as e: # the limiter's store is down
print(" store error:", repr(e))
return rule["if_store_down"] == "open"
for path in RULES:
print(f"{path:<10} allowed: {allow('priya', path)}")
Output:
store error: ConnectionRefusedError(111, 'Connection refused')
/menu allowed: True
store error: ConnectionRefusedError(111, 'Connection refused')
/send-otp allowed: False
socket.create_connectionopens a network connection (a socket) to an address and port;timeout=0.2means give up after 0.2 seconds.- Nothing listens on port 6399, so the operating system answers at once with
ConnectionRefusedError, error number 111, "Connection refused". It's a kind ofOSError, Python's family of errors from the operating system (network, files), soexcept OSErrorcatches it, and also timeouts and other network failures. - Each rule carries
if_store_down./menusays"open": allowed: True, browsing keeps working./send-otpsays"closed": allowed: False, nobody can burn the SMS budget while the limiter can't count. print(..., repr(e))logs the error. In production, log it loudly and alert on it (episode 25): a limiter quietly failing open is exactly what an attacker hopes for.
| Fail open | Fail closed |
|---|---|
| Choose when the endpoint is cheap and must stay up | Choose when abuse costs money or safety |
/menu, /search, reading pages |
/send-otp, /login attempts, payments |
| Risk: abuse while the store is down | Risk: real users refused while the store is down |
Without the try/except, the store's failure becomes the app's failure; see the common mistakes. You just invented fail open and fail closed!
Problem 5: tell the client (429 and Retry-After)
A refused request needs a clear answer, so good clients slow down instead of retrying in a tight loop. From MDN, 429 Too Many Requests means "the client has sent too many requests in a given amount of time", and "A Retry-After header may be included to this response to indicate how long a client should wait before making the request again". The status code is specified in RFC 6585, section 4 (an RFC is a numbered document that defines an internet standard).
- An HTTP status code is the three-digit number at the start of every response that says how it went. Example:
200 OK,429 Too Many Requests. - A header is a named piece of extra information sent with a request or response. Example:
Retry-After: 31, meaning "wait 31 seconds".
How long should Retry-After be? With a fixed window, simple: until the next window starts.
import math
WINDOW = 60
def retry_after_fixed(t): # fixed window: wait for the next one
return WINDOW - t % WINDOW
for t in [42, 59, 60, 61.5]:
print(f"limit hit at t={t}: Retry-After: {math.ceil(retry_after_fixed(t))}")
Output:
limit hit at t=42: Retry-After: 18
limit hit at t=59: Retry-After: 1
limit hit at t=60: Retry-After: 60
limit hit at t=61.5: Retry-After: 59
math.ceil rounds up, so the client never comes back a fraction of a second too early. With a sliding window counter it's less obvious, because the estimate falls gradually; the mini project steps forward one second at a time until the estimate drops below the limit (for a bot that used all 10 of its requests at t = 30, it answers Retry-After: 31, and indeed t = 60 is still refused while t = 61 is allowed).
On the client side, episode 19 already gave the rule: if the server sent Retry-After, wait at least that long; otherwise use exponential backoff (double the wait after each failure: 1, 2, 4, 8 seconds) with jitter (pick a random wait up to that number, so clients that were refused together don't all come back together).
The full design
The path of one request:
- A client (a user, or a partner's server with an API key) sends
POST /shorten. - The API gateway receives it; its rate limiter middleware finds the client, plan and path, and looks up the rule in its in-memory copy of the rules (refreshed from the config store every few seconds).
- The middleware sends one small atomic script to the Redis cluster: update the sliding window counter for
user:path:minute, set its expiry, and answer allow or refuse. - Allowed: the request goes on to the service (
/shorten,/menu,/send-otp). Refused: the gateway answers429 Too Many RequestswithRetry-After, and the service never sees it. - Redis unreachable: the middleware follows the rule's fail mode (open or closed) and raises an alert.
| Piece | What it does | Detail |
|---|---|---|
| API gateway + limiter middleware | Runs on every request, before any service | Finds the client (user id, API key or IP), plan and path |
| Rules | Plan, path, limit, period, fail mode | Live in a config store; cached in memory in every gateway; refreshed every few seconds |
| Counter store | A Redis cluster (several Redis servers working as one) holding the counters | One small atomic script per request: update the sliding window counter for user:path:minute, set its expiry |
| Keys that expire | Old minutes delete themselves | A sliding counter needs the previous minute, so keep each key for two windows |
| Over the limit | 429 Too Many Requests + Retry-After |
The client backs off with jitter (episode 19) |
| Store down | Follow the rule's fail mode | Fail open or closed per endpoint, and alert (episode 25) |
| Speed | Keep Redis close to the gateways, in the same data centre | We budget about a millisecond extra per request |
| Scale | Shard the counters by key across Redis servers (episode 12) | All of one key's counters live on one server, so each script stays on one server and stays atomic |
Sharding (episode 12) means splitting data across several servers, each holding a part. Example: keys starting a-m on Redis server 1, n-z on server 2 (real systems hash the key instead, episode 13). For the limiter, the key priya:/shorten:28333 always goes to the same server, so every gateway asks the same place about Priya's /shorten counter.
The whole chain
- Different users, different limits → requirements, and rules as data: free 10, partner 1,000, OTP 3, default 100.
- Read, check, write with 50 requests at once → allowed 50 of 50, counter says 1: a race condition.
- One atomic step (a lock; Redis
INCR,MULTI/EXEC, a Lua script) → allowed exactly 10 of 50. - A log of timestamps for 10 million users → 80 GB; a sliding window counter → 0.16 GB, and the t = 59 / t = 60 edge trick is blocked (10, 0, then 5 at t = 90).
- The store goes down →
ConnectionRefusedError(111, 'Connection refused')→ fail open for/menu, fail closed for/send-otp, and alert. - The full design: gateway middleware + rules cache + Redis cluster + 429 with Retry-After.
Common mistakes (and the real outputs)
| Mistake | Code | Output | Fix |
|---|---|---|---|
| Read, check, write back | count = store.get(u) ... store[u] = count + 1 |
limit: 10 allowed: 50 of 50 / counter says: 1 |
One atomic INCR, compare its result |
Atomic INCR, but checked before it |
GET, compare, then INCR |
allowed: 50 of 50 / counter says: 50 (one line) |
INCR first, then compare the value it returned |
INCR and EXPIRE as two separate calls |
incr(k), crash, expire(k) never runs |
an hour later, expiry set? False / allowed now? False (locked out forever) |
MULTI/EXEC or one Lua script |
| No plan for the store going down | no try/except around the store call |
ConnectionRefusedError: [Errno 111] Connection refused (the request crashes) |
Fail open / closed per rule, and alert |
| General rule before a specific one | "*" rule listed before "partner" |
partner /shorten -> 10 per minute |
Specific rules first (first match wins) |
> instead of >= |
if estimate > LIMIT: |
allowed between t=59 and t=60: 11 / limit: 10 (one line) |
if estimate >= LIMIT: |
| Testing with one request at a time | a loop of single requests | always looks correct | Test with many threads at once |
The second mistake, run for real. INCR is atomic here, but the decision used the value read earlier:
import threading, time
store, lock = {}, threading.Lock()
LIMIT = 10
def incr(key): # atomic, like Redis INCR
with lock:
store[key] = store.get(key, 0) + 1
return store[key]
def allow(user): # GET first, INCR later
count = store.get(user, 0) # 1. read (GET)
time.sleep(0.3) # network trip
if count >= LIMIT:
return False
incr(user) # 2. atomic INCR, but too late
return True
allowed = []
threads = [threading.Thread(target=lambda: allowed.append(allow("bot")))
for _ in range(50)]
for t in threads: t.start()
for t in threads: t.join()
print("allowed:", sum(allowed), "of 50 | counter says:", store["bot"])
Output:
allowed: 50 of 50 | counter says: 50
Every request was counted (50), but all 50 were allowed (timing-dependent like the RACE demo: on a busy machine a few late threads may see 10 and be refused), because all of them read 0 and decided before anyone incremented. This is the version the Redis docs warn about: "In the above code there is a race condition".
The third mistake: a tiny pretend Redis (TinyRedis, with a fake clock now) where the gateway crashes between INCR and EXPIRE:
import threading
class TinyRedis: # a pretend Redis with a fake clock
def __init__(self):
self.data, self.expiry = {}, {}
self.lock, self.now = threading.Lock(), 0
def _drop_if_expired(self, key):
if key in self.expiry and self.now >= self.expiry[key]:
del self.data[key], self.expiry[key]
def incr(self, key): # INCR: add 1, return the new value
with self.lock:
self._drop_if_expired(key)
self.data[key] = self.data.get(key, 0) + 1
return self.data[key]
def expire(self, key, seconds): # EXPIRE: delete the key after N s
with self.lock:
self.expiry[key] = self.now + seconds
def eval(self, script, *args): # like EVAL: a script runs as one step
with self.lock:
return script(self, *args)
LIMIT = 10
# --- mistake: INCR, then EXPIRE as a separate call
r = TinyRedis()
def allow_two_calls(key):
n = r.incr(key)
if n == 1:
raise ConnectionResetError("gateway crashed before EXPIRE")
return n <= LIMIT
try:
allow_two_calls("priya:/shorten")
except ConnectionResetError as e:
print("crash:", e)
r.now = 3600 # one hour later...
print("an hour later, expiry set?", "priya:/shorten" in r.expiry,
"| count:", r.data["priya:/shorten"])
for _ in range(9): r.incr("priya:/shorten")
print("allowed now?", r.incr("priya:/shorten") <= LIMIT, "(locked out forever)")
# --- fix: INCR and EXPIRE together, in one script
def incr_and_expire(redis, key, seconds):
redis._drop_if_expired(key)
redis.data[key] = redis.data.get(key, 0) + 1
if redis.data[key] == 1: # first request in this window
redis.expiry[key] = redis.now + seconds
return redis.data[key]
r = TinyRedis()
print("\nscript ->", r.eval(incr_and_expire, "priya:/shorten", 60))
r.now = 60
print("60 s later ->", r.eval(incr_and_expire, "priya:/shorten", 60),
"(a fresh window)")
Output:
crash: gateway crashed before EXPIRE
an hour later, expiry set? False | count: 1
allowed now? False (locked out forever)
script -> 1
60 s later -> 1 (a fresh window)
- With two calls, the crash came after
INCRand beforeEXPIRE, so the key has no expiry. An hour later it still exists; Priya's count keeps growing and she is refused forever. (With a time in the key, likepriya:/shorten:28333, she wouldn't be locked out, but those keys would never be deleted and memory would slowly fill.) - With one script (
eval), the increment and the expiry happen together or not at all; 60 seconds later the key is gone and a fresh window starts at 1. That's the job ofMULTI/EXECor a Lua script in real Redis.
The fourth mistake: the same store call as the FAILMODE demo, without try/except:
import socket
def incr(key):
conn = socket.create_connection(("127.0.0.1", 6399), timeout=0.2)
conn.close()
return 1
def allow(user, path): # no try/except
return incr(f"{user}:{path}") <= 100
print("/menu allowed:", allow("priya", "/menu"))
Output:
Traceback (most recent call last):
File "nohandle.py", line 11, in <module>
print("/menu allowed:", allow("priya", "/menu"))
~~~~~^^^^^^^^^^^^^^^^^^
File "nohandle.py", line 9, in allow
return incr(f"{user}:{path}") <= 100
~~~~^^^^^^^^^^^^^^^^^^
File "nohandle.py", line 4, in incr
conn = socket.create_connection(("127.0.0.1", 6399), timeout=0.2)
File "socket.py", line 868, in create_connection
raise exceptions[0]
File "socket.py", line 853, in create_connection
sock.connect(sa)
~~~~~~~~~~~~^^^^
ConnectionRefusedError: [Errno 111] Connection refused
(File paths in the tracebacks are shortened to the file name.) The menu, which never needed protecting from a store outage, now crashes on every request: the safety feature became the outage.
The fifth mistake:
RULES = [
{"plan": "*", "path": "/shorten", "limit": 10}, # general first
{"plan": "partner", "path": "/shorten", "limit": 1000}, # never reached
]
def rule_for(plan, path):
for r in RULES:
if r["path"] == path and r["plan"] in (plan, "*"):
return r
print("partner /shorten ->", rule_for("partner", "/shorten")["limit"], "per minute")
Output:
partner /shorten -> 10 per minute
ChaiStats paid for 1,000 a minute and gets 10, because the general * rule matched first.
The sixth mistake, an off-by-one in the sliding window:
LIMIT, WINDOW = 10, 60
counts = {}
def allow(user, t):
minute = t // WINDOW
now = counts.get((user, minute), 0)
before = counts.get((user, minute - 1), 0)
estimate = now + before * (1 - (t % WINDOW) / WINDOW)
if estimate > LIMIT: # BUG: should be >=
return False
counts[(user, minute)] = now + 1
return True
got = sum(allow("bot", 59) for _ in range(10)) + \
sum(allow("bot", 60) for _ in range(10))
print("allowed between t=59 and t=60:", got, "| limit:", LIMIT)
Output:
allowed between t=59 and t=60: 11 | limit: 10
At t = 60 the estimate is exactly 10, and 10 > 10 is false, so an 11th request gets in. "At the limit" must already mean "refuse": >=.
Mini project: a rate limiter service in about 120 lines
Everything from today in one program, stdlib only: rules as data (with an unlimited internal plan, a default, and a fail mode per rule), a counter store standing in for Redis whose run_script runs a whole function atomically (like a Lua script with EVAL), sliding window counters with keys that expire after two windows, a RateLimiter that the gateway middleware would call, returning 200, 429 with Retry-After, or, when the store is down and the rule says closed, 503 Service Unavailable (the HTTP status for "I can't serve this right now"). Then it proves with threads that bursts never get past the limit. Time t is simulated in seconds, so the output never changes.
# Mini project: a rate limiter service (rules as data, sliding window
# counters, atomic scripts, fail open / closed, 429 + Retry-After)
import threading, time
WINDOW = 60 # every rule here is per minute
# ---- 1. rules as data (in production: a config store, cached in memory)
RULES = [
{"plan": "internal", "path": "*", "limit": None, "if_down": "open"},
{"plan": "free", "path": "/shorten", "limit": 10, "if_down": "open"},
{"plan": "partner", "path": "/shorten", "limit": 1000, "if_down": "open"},
{"plan": "*", "path": "/send-otp", "limit": 3, "if_down": "closed"},
]
DEFAULT = {"plan": "*", "path": "*", "limit": 100, "if_down": "open"}
def rule_for(plan, path):
for r in RULES: # first matching rule wins
if r["path"] in (path, "*") and r["plan"] in (plan, "*"):
return r
return DEFAULT
# ---- 2. the counter store (stands in for Redis)
class CounterStore:
def __init__(self):
self.counts, self.expiry = {}, {}
self.lock = threading.Lock()
self.down = False # flip to True to "crash" it
def run_script(self, script, *args): # like EVAL: one step, atomic
if self.down:
raise ConnectionRefusedError(111, "Connection refused")
with self.lock:
return script(self, *args)
def count(self, key, t): # an expired key counts as 0
if key in self.expiry and t >= self.expiry[key]:
return 0 # (Redis deletes it by itself)
return self.counts.get(key, 0)
def estimate(store, name, t, minute): # sliding window counter
now = store.count(f"{name}:{minute}", t)
before = store.count(f"{name}:{minute - 1}", t)
passed = (t % WINDOW) / WINDOW
return now + before * (1 - passed)
def sliding_script(store, name, t, limit): # runs inside the lock
minute = t // WINDOW
if estimate(store, name, t, minute) >= limit:
wait = 1 # Retry-After: first second when
while estimate(store, name, t + wait, (t + wait) // WINDOW) >= limit:
wait += 1 # the estimate drops below limit
return False, wait
key = f"{name}:{minute}"
store.counts[key] = store.count(key, t) + 1
if store.counts[key] == 1: # INCR + EXPIRE, together:
store.expiry[key] = (minute + 2) * WINDOW # kept for 2 windows
return True, 0
# ---- 3. the limiter: what the API gateway's middleware calls
class RateLimiter:
def __init__(self, store):
self.store, self.store_errors = store, 0
def check(self, user, plan, path, t):
rule = rule_for(plan, path)
if rule["limit"] is None:
return 200, {}
try:
ok, wait = self.store.run_script(
sliding_script, f"{user}:{path}", t, rule["limit"])
except OSError as e: # the store is down
self.store_errors += 1 # count it: this feeds an alert
if rule["if_down"] == "open":
return 200, {"note": f"fail open ({e.strerror})"}
return 503, {"note": f"fail closed ({e.strerror})"}
if ok:
return 200, {}
return 429, {"Retry-After": str(wait)}
store = CounterStore()
limiter = RateLimiter(store)
# ---- 4. proof with threads: many requests at the same moment
def burst(user, plan, path, n, t):
results, lock = [], threading.Lock()
def one():
time.sleep(0.001) # (network trip to the gateway)
status, _ = limiter.check(user, plan, path, t)
with lock: results.append(status)
threads = [threading.Thread(target=one) for _ in range(n)]
for th in threads: th.start()
for th in threads: th.join()
return results.count(200), results.count(429)
for user, plan, n in [("bot1", "free", 200), ("bot2", "free", 200),
("chaistats", "partner", 1500)]:
ok, refused = burst(user, plan, "/shorten", n, t=30)
print(f"{user:<10}{plan:<8} {n:>5} at once -> {ok:>4} allowed, "
f"{refused:>4} got 429")
print("otp, 10 at once ->", burst("asha", "free", "/send-otp", 10, t=30))
# ---- 5. a 429 with Retry-After, and keeping to it
status, headers = limiter.check("bot1", "free", "/shorten", t=30)
print("\nHTTP/1.1", status, "Too Many Requests")
print("Retry-After:", headers["Retry-After"])
wait = int(headers["Retry-After"])
print(f"retry at t={30 + wait - 1}:", limiter.check("bot1", "free", "/shorten", 30 + wait - 1)[0])
print(f"retry at t={30 + wait}:", limiter.check("bot1", "free", "/shorten", 30 + wait)[0])
# ---- 6. the edge trick from episode 19 is blocked
print("\nt=119:", sum(limiter.check("ravi", "free", "/shorten", 119)[0] == 200
for _ in range(10)), "allowed",
"| t=120:", sum(limiter.check("ravi", "free", "/shorten", 120)[0] == 200
for _ in range(10)), "allowed")
# ---- 7. internal tools have no limit
print("internal, 5,000 requests:",
sum(limiter.check("ops", "internal", "/shorten", 30)[0] == 200
for _ in range(5000)), "allowed")
# ---- 8. the store goes down: fail open or closed, per rule
store.down = True
for path in ["/menu", "/shorten", "/send-otp"]:
print(f"store down, {path:<10}->", *limiter.check("priya", "free", path, 200))
if limiter.store_errors:
print(f"ALERT: rate limiter store unreachable ({limiter.store_errors} errors)")
Output (identical on every run):
bot1 free 200 at once -> 10 allowed, 190 got 429
bot2 free 200 at once -> 10 allowed, 190 got 429
chaistats partner 1500 at once -> 1000 allowed, 500 got 429
otp, 10 at once -> (3, 7)
HTTP/1.1 429 Too Many Requests
Retry-After: 31
retry at t=60: 429
retry at t=61: 200
t=119: 10 allowed | t=120: 0 allowed
internal, 5,000 requests: 5000 allowed
store down, /menu -> 200 {'note': 'fail open (Connection refused)'}
store down, /shorten -> 200 {'note': 'fail open (Connection refused)'}
store down, /send-otp -> 503 {'note': 'fail closed (Connection refused)'}
ALERT: rate limiter store unreachable (3 errors)
What to notice:
- Race-free under threads: 200 requests at once for
bot1and forbot2→ exactly 10 allowed each; 1,500 at once for ChaiStats → exactly 1,000; 10 OTP requests → exactly 3. The whole read-estimate-increment happens insiderun_script's lock, so no two requests can interleave, like a Lua script in Redis. - Only allowed requests are counted here (
sliding_scriptchecks before it increments, both inside the same atomic script). That's safe because the check and the increment are in one step; it's theGETthenINCRin two steps that races. - Retry-After: 31: at t = 30 the minute already holds 10. At t = 60 the estimate is 0 + 10 × 1 = 10, still refused; at t = 61 it's 10 × 59/60 ≈ 9.83, allowed. The client that obeys
Retry-Aftergets in on its first retry. - The edge trick is blocked: 10 at t = 119, 0 at t = 120.
- Internal tools are unlimited (
limit: None), and never even touch the store. - Store down:
/menuand/shortenfail open (200, with a note for the logs),/send-otpfails closed (503), and the error counter raises an ALERT./menuhas no rule of its own, so it usesDEFAULT, which fails open. - Keys expire after two windows (
(minute + 2) * WINDOW): minute 0's counter is still needed asbeforeduring minute 1, and useless after that.
Extend it: add per-rule window values (per second, per hour); add a reload_rules method that swaps in a new rules list while threads are running; make count delete expired keys; replace the sliding window with a token bucket script and compare Retry-After; return a remaining number with every 200.
Practice
- Homework: in the RACE demo, remove the
time.sleepline and run it a few times. Is it still broken? - Homework: in the SLIDING demo, change the last burst from t = 90 to t = 119. How many get in, and why?
- Homework: in the RULES demo, add an
internalplan with no limit on any path. - Homework: should
/loginfail open or closed? Why? - ChaiNow grows to 50 million users with a limit of 100 per minute. How much memory for a sliding log vs a sliding window counter (8 bytes each)?
- Limit 10 per minute. Last minute had 8 requests, this minute 3 so far, and it's t = 75. Is the next request allowed? And the one after it?
- Why does the mini project keep each counter for two windows instead of one?
- A fixed-window limiter (60 s windows) refuses a request at t = 42. What
Retry-Aftershould it send? At t = 61.5?
Solutions and hints
1. Without the sleep, it usually looks fine. Five runs in a row:
limit: 10 allowed: 10 of 50
counter says: 10
limit: 10 allowed: 10 of 50
counter says: 10
limit: 10 allowed: 10 of 50
counter says: 10
limit: 10 allowed: 10 of 50
counter says: 10
limit: 10 allowed: 10 of 50
counter says: 10
Still broken. The read and the write are now so close together that the threads rarely switch between them (in the standard Python build, only one thread runs Python code at a time, and it switches between threads only every so often), but the race is still there. Change the demo's sleep line to time.sleep(0), the shortest possible pause, which only lets other threads run. Five runs in a row:
limit: 10 allowed: 18 of 50
counter says: 10
limit: 10 allowed: 16 of 50
counter says: 10
limit: 10 allowed: 14 of 50
counter says: 10
limit: 10 allowed: 15 of 50
counter says: 10
limit: 10 allowed: 20 of 50
counter says: 10
18, 16, 14, 15, 20 allowed through a limit of 10: different on every run (yours will differ too), and a real network trip is far longer than sleep(0). A bug that passes most tests and fails under load is the worst kind; only an atomic step removes it.
2.
t=59: 10 t=60: 0 t=119: 10
log of timestamps: 80 GB
two counters each: 0.16 GB
At t = 119 we are 59/60 of the way through minute 1, so only 1/60 of minute 0's 10 requests still counts: 10 × 1/60 ≈ 0.17. Minute 1 has 0 so far (the t = 60 burst was all refused, and refused requests aren't counted). The estimate goes 0.17, 1.17, ..., 9.17: all 10 allowed. Correct: the 10 requests at t = 59 are 60 seconds old, almost out of the window.
3. Add a rule with path: "*" and limit: None, put it first, and let rule_for match * paths:
RULES = [
{"plan": "internal", "path": "*", "limit": None, "per": "minute"}, # no limit
{"plan": "free", "path": "/shorten", "limit": 10, "per": "minute"},
{"plan": "partner", "path": "/shorten", "limit": 1000, "per": "minute"},
{"plan": "*", "path": "/send-otp", "limit": 3, "per": "minute"},
]
DEFAULT = {"limit": 100, "per": "minute"}
def rule_for(plan, path):
for r in RULES: # first matching rule wins
if r["path"] in (path, "*") and r["plan"] in (plan, "*"):
return r
return DEFAULT
def describe(r):
return "no limit" if r["limit"] is None else f"{r['limit']} per {r['per']}"
for plan, path in [("internal", "/shorten"), ("internal", "/send-otp"),
("free", "/shorten"), ("partner", "/send-otp")]:
print(f"{plan:<9}{path:<10} -> {describe(rule_for(plan, path))}")
Output:
internal /shorten -> no limit
internal /send-otp -> no limit
free /shorten -> 10 per minute
partner /send-otp -> 3 per minute
Because it's first and matches any path, internal tools skip even the OTP rule. In the real limiter, None means "don't call the store at all".
4. Usually closed. While the limiter is blind, a fail-open /login lets an attacker try passwords without any limit (and if login sends an OTP, burn the SMS budget). The cost of failing closed, real users can't log in for a few minutes, is visible and alerted; the cost of failing open is silent. A middle path: fall back to a small limit counted in each gateway's own memory (not shared, so not exact, but not unlimited either). Whatever you choose, write it in the rule and alert on store errors.
5.
users, limit = 50_000_000, 100
print(f"log of timestamps: {users * limit * 8 / 1e9:,.0f} GB")
print(f"two counters each: {users * 2 * 8 / 1e9:,.2f} GB")
print(f"ratio: {limit / 2:.0f}x less")
Output:
log of timestamps: 40 GB
two counters each: 0.80 GB
ratio: 50x less
The saving is limit / 2: a log stores up to limit timestamps per user, the counter stores 2 numbers. With a limit of 1,000 it was 500 times; with 100 it's 50 times.
6.
LIMIT, WINDOW = 10, 60
before, now, t = 8, 3, 75 # 15 seconds into minute 1
passed = (t % WINDOW) / WINDOW
estimate = now + before * (1 - passed)
print("passed:", passed, "| estimate:", estimate, "| allowed:", estimate < LIMIT)
now += 1 # that request was counted
print("next one:", now + before * (1 - passed), "| allowed:",
now + before * (1 - passed) < LIMIT)
Output:
passed: 0.25 | estimate: 9.0 | allowed: True
next one: 10.0 | allowed: False
passed = 15/60 = 0.25, estimate = 3 + 8 × 0.75 = 9 < 10: allowed. After it, 4 + 6 = 10: the next one is refused.
7. The sliding window counter at any moment in minute m reads minute m's counter and minute m - 1's. So minute m's counter is needed during minute m and all of minute m + 1; it can go only when minute m + 2 starts, which is exactly (m + 2) × 60. Expire it after one window and the estimate would forget the previous minute: the edge trick would be back.
8. Until the next window starts: 60 − 42 = 18 seconds; at t = 61.5 it's 60 − 1.5 = 58.5, rounded up to 59 (see the retry_after_fixed demo in Problem 5). Rounding down would send the client back half a second early, into another 429.
Quick quiz
class Store(dict): # just enough to run the quiz code
def set(self, key, value): self[key] = value
store, LIMIT, user = Store(bot=0), 10, "bot"
def allow(): print("allowed, count is now", store["bot"])
# This runs on twenty gateway servers at once. What's the bug?
count = store.get(user)
if count < LIMIT:
store.set(user, count + 1)
allow()
Output (run alone, it looks fine):
allowed, count is now 1
The code runs on twenty gateway servers at once. What's the bug?
- A.
LIMITis too small - B. A race: the read and the write are separate
- C. It should use a list
- D. Nothing, it's fine
Answer
B. A race condition. Many servers can read the same count before any of them writes it back, so all of them pass the check (the RACE demo: 50 of 50 allowed). Use one atomic increment (Redis INCR) and compare the value it returns, or put the whole check in one Lua script.
Interview questions: "Design a rate limiter"
A design interview is a conversation. Here is the walkthrough, in the order an interviewer expects, with what to say at each step.
1. Clarify the requirements (2-3 minutes). Ask: who is limited (users, API keys, IPs)? Per endpoint? Different plans? How many users and requests? Must limits change without deploys? What should happen when the limiter itself fails? Then state them: limit per client per endpoint, plan-based rules changeable at runtime, correct across many gateway servers, adds about a millisecond, returns 429 with Retry-After, fails safely.
2. Estimate (1-2 minutes). "10 million active users, limit 1,000 per minute. A sliding log is 10M × 1,000 × 8 bytes = 80 GB; a sliding window counter is 10M × 2 × 8 bytes = 0.16 GB." This number justifies the algorithm choice.
3. Where it lives. In the API gateway, as middleware, before any service. Not in the client (can be skipped), not copied into every service. Counters in a shared store, because a per-server counter lets a client get servers × limit (episode 19).
4. Rules. Data, not code: {plan, path, limit, period, fail mode}, first match wins, specific before general, a default. Stored in a config store, cached in each gateway, refreshed every few seconds.
5. Algorithm. Sliding window counter (two counters per key, nearly exact, blocks the window-edge burst). Mention the alternatives and when you'd pick them: fixed window (simplest), token bucket (allows bursts), sliding log (exact but memory-hungry).
6. Data model and atomicity. Key user:path:minute, value a count, expiry two windows. The update must be one atomic step: never GET then SET; use INCR, MULTI/EXEC, or one Lua script that reads both windows, decides, increments and sets the expiry.
7. Scale. A Redis cluster near the gateways; shard by key so each client's counters live on one node and the script stays atomic on that node. Rules are cached, so the only network call per request is the one script.
8. Failure. Per-rule fail mode: open for cheap reads, closed for costly or security-sensitive endpoints; log and alert on store errors; short timeouts so a slow store doesn't make every request slow.
9. Client contract. 429 Too Many Requests with Retry-After; clients wait at least that long, then back off exponentially with jitter.
Common follow-up questions:
- What is a race condition, and where is it in a rate limiter? (Two requests read the same count before either writes; both pass. Our demo: 50 of 50 through a limit of 10.)
- Why isn't
INCRalone always enough? (If youGETand decide first, the decision uses an old value. Decide on the value the atomic step returns, or do the whole decision in one script.) - Why
MULTI/EXECor Lua forINCR+EXPIRE? (If the process dies between the two, the key never expires: the client is stuck, or memory leaks.) - How would you limit by IP when many users share one IP? (Prefer user id or API key when available; give IP-based rules higher limits; IP is the fallback when nothing else identifies the client.)
- What's the trade-off between fail open and fail closed? (Availability vs protection; decide per endpoint.)
- How does the client know when to retry? (Retry-After; for a sliding window, compute the first second when the estimate falls below the limit.)
- How do you change a limit for one partner right now? (Edit its rule in the config store; gateways pick it up on their next refresh, no deploy.)
- How do you test it? (Bursts with many threads at once, not one request at a time; inject store failures; check the window edge.)
Glossary
| Term | Meaning |
|---|---|
| Rate limiting | Capping how many requests one client may make in a period of time, e.g. 10 links per minute |
| Rate limiter | The software that counts requests and allows or refuses each one |
| Rate limiter service | A rate limiter built for a whole system: many servers, plans, endpoints, and failures |
| Client | Whoever sends requests: a person's app, a partner's server, a script |
| Spammer / bot | A script sending huge numbers of requests, e.g. a million short links an hour |
| Endpoint / path | One address of an API that does one job, e.g. /shorten, /send-otp, /menu |
| API key | A secret string a program sends with every request to say who it is, e.g. a partner's key |
| IP address | The network address a request comes from, e.g. 10.0.0.7; the fallback way to identify a client |
| User id | The id of a logged-in user, e.g. priya |
| OTP | One-time password: a code sent by SMS to log in; every SMS costs money |
| Plan | The kind of account, which decides the limits: free, partner, internal |
| Partner | A business that pays for higher limits, e.g. ChaiStats (made up) |
| Functional requirement | What the system must do, e.g. "limit per plan and endpoint" |
| Non-functional requirement | How well it must do it: fast, correct across servers, available |
| Deploy | Releasing new code to the servers |
| API gateway | The front-door server all requests pass through before reaching services (episode 20) |
| Middleware | Code that runs on every request before the real service, and can stop it, e.g. the limiter |
| Rule | One line of limits as data: plan, path, limit, period, fail mode |
| Rules as data | Keeping limits in a list or table instead of in code, so they change without a deploy |
* (wildcard) |
In a rule, "any plan" (or "any path") |
| First match wins | rule_for returns the first rule that matches, so specific rules go before general ones |
| Default rule | The limit used when no rule matches, e.g. 100 per minute |
| Config store | A small database or file service holding settings (like rules) for the whole system |
| Cache | A copy of data kept close by for fast reads, e.g. the rules in every gateway's memory (episode 7) |
| Shared store | One place every server reads and writes the counters, e.g. Redis |
| Race condition | A bug where the result depends on who gets there first, and two get there at once, e.g. two clerks selling one seat |
| Read-check-write | Reading a value, deciding, then writing it back in separate steps; races when shared |
| Thread | One line of work inside a program; many can run at once, e.g. one per request |
threading.Thread |
Python's way to start a thread: Thread(target=fn).start(), then .join() to wait for it |
time.sleep |
Pauses the current thread, e.g. to fake a network trip; sleep(0) just lets other threads run |
| Atomic operation | A step that happens completely or not at all, with nothing in the middle, e.g. INCR |
| Lock | Lets only one thread at a time run a block of code: with lock: |
| Redis | An in-memory data store that many servers share over the network; fast because data is in RAM |
| Key / value | In Redis, a name and the data stored under it, e.g. bot:/shorten:28333 → 7 |
| INCR | The Redis command that adds 1 to a key and returns the new value, atomically, in O(1) time |
| O(1) | Constant time: the same short time however much data there is |
| EXPIRE | The Redis command that deletes a key by itself after N seconds |
| Expiry / TTL | How long until a key is deleted; TTL = time to live |
| MULTI / EXEC | Redis commands that start a transaction and run its queued commands together |
| Transaction | A group of commands run together, with no other client's command in between |
| Lua | A small programming language; Redis can run a Lua script atomically |
| Lua script | A short program sent to Redis with EVAL and run in one go, e.g. INCR + EXPIRE + a decision |
| EVAL | The Redis command that runs a Lua script |
| GET | The Redis command that reads a key's value; GET then INCR is the documented race |
| Count first, then decide | Use the value the atomic increment returned to allow or refuse |
| Window | A block of time limits are counted in, e.g. one minute |
| Fixed window | One counter per client per window, reset when the window changes (episode 19) |
| Window-edge trick | Sending a burst just before and just after a fixed window's edge to get twice the limit |
| Timestamp | The time something happened, stored as a number, e.g. 1793263259 seconds |
| Sliding log | Keeping the timestamp of every request and counting those in the last window: exact, memory-hungry |
| Sliding window counter | Two counters (this window, previous window) and the estimate now + before × (1 - passed) |
| Weighted estimate | Counting only the part of the previous window that still overlaps the last 60 seconds |
| Token bucket | Tokens refill at a fixed rate; each request spends one; allows bursts up to the bucket size (episode 19) |
| Byte / GB | A byte is 8 bits; a GB here is 10^9 bytes, e.g. 80 GB for the sliding log |
| Fail open | When the limiter can't count, allow requests, e.g. /menu |
| Fail closed | When the limiter can't count, refuse requests, e.g. /send-otp |
| Fail mode | The rule's choice of fail open or fail closed |
| Socket | A network connection between two programs, opened with socket.create_connection |
| Port | A number that picks one program on a machine, e.g. 6399 in our demo |
ConnectionRefusedError |
Python's error when nothing is listening at the address: [Errno 111] Connection refused |
OSError |
Python's family of operating-system errors (network, files); ConnectionRefusedError is one |
| Timeout | Giving up after a time limit, e.g. timeout=0.2 seconds |
| Traceback | Python's report of an uncaught error and where it happened |
| Alert | A rule that notifies a person when something is wrong, e.g. store errors (episode 25) |
| HTTP status code | The three-digit number at the start of a response, e.g. 200, 429, 503 |
| 200 OK | The request succeeded |
| 429 Too Many Requests | "The client has sent too many requests in a given amount of time" (MDN; RFC 6585 section 4) |
| 503 Service Unavailable | "I can't serve this right now"; used by our mini project when failing closed |
| Header | Named extra information with a request or response, e.g. Retry-After: 31 |
| Retry-After | A header telling the client how long to wait before trying again |
| RFC | A numbered document defining an internet standard, e.g. RFC 6585 |
math.ceil |
Rounds a number up, e.g. 58.5 → 59 |
| Backoff (exponential) | Waiting longer after each failure: 1, 2, 4, 8 seconds (episode 19) |
| Jitter | A random part added to the wait so clients don't all retry together (episode 19) |
| Redis cluster | Several Redis servers working as one, each holding part of the keys |
| Sharding | Splitting data across several servers by key, e.g. each client's counters on one server (episode 12) |
| Data centre | A building full of servers; keeping Redis in the same one as the gateways keeps the check fast |
Summary
- A rate limiter service limits each client (user, API key or IP) per endpoint, with different limits per plan, correctly across many servers, in about a millisecond.
- It lives in the API gateway as middleware; its counters live in a shared store (Redis).
- Rules are data: plan, path, limit, period, fail mode; first match wins; kept in a config store and cached in every gateway, so limits change without a deploy.
- Read, check, write on a shared counter is a race condition: 50 of 50 got through a limit of 10. Count in one atomic step (Redis
INCR;INCR+EXPIREinMULTI/EXEC; or a Lua script withEVAL) and decide on the value it returns: exactly 10 of 50. - A sliding window counter needs two numbers per client (0.16 GB for 10 million users vs 80 GB for a sliding log) and blocks the window-edge trick.
- When the store dies, fail open for cheap endpoints and fail closed for costly or sensitive ones, decided per rule, and alert.
- Refused requests get 429 Too Many Requests with Retry-After; clients wait, then back off with jitter.
- The full design: gateway middleware + rules cache + Redis cluster, keys
user:path:minutethat expire after two windows, sharded by key.
Next episode: a system you use every day. How does a message from Priya reach Rahul in under a second, with one tick, two ticks and blue ticks? Design WhatsApp chat.
Sources: redis.io, INCR command page (O(1) time complexity; the counter pattern using "Redis atomic increment operations"; the rate limiter pattern with a key per IP per second, INCR + EXPIRE inside MULTI/EXEC "to make sure that we'll both increment and set the expire at every API call"; the GET-then-INCR version, "In the above code there is a race condition"; the fix as a Lua script sent with EVAL); MDN, "429 Too Many Requests" ("the client has sent too many requests in a given amount of time"; "A Retry-After header may be included to this response to indicate how long a client should wait before making the request again"; specification RFC 6585, section 4). The memory numbers are our own arithmetic on stated assumptions (10 million users, limit 1,000, 8 bytes per timestamp or counter).