SyntaxPilot
Courses/System Design/Lesson 28

System Design · Lesson 28 of 40 · 10 min

Design a rate limiter service

queued

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: /shorten makes a short link, /send-otp sends an OTP, /menu returns 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:

  • RULES is a plain list of dictionaries. Nothing in it is logic; it could come from a JSON file or a database table.
  • rule_for walks the list and returns the first matching rule: the path must be equal, and the plan must be equal or *. If nothing matches, it returns DEFAULT.
  • 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 reached store[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 value 1. 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
  • incr adds one and returns the new value, all inside with 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 key adds 1 to the number stored at key (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 seconds tells 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 INCR and EXPIRE together inside MULTI/EXEC "to make sure that we'll both increment and set the expire at every API call". MULTI starts a transaction (a group of commands), Redis queues the commands that follow, and EXEC runs 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 INCR and the optional EXPIRE (only needed when the key was just created) into a Lua script sent with EVAL.

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: 1793263259 seconds.
  • 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 passed of 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_connection opens a network connection (a socket) to an address and port; timeout=0.2 means 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 of OSError, Python's family of errors from the operating system (network, files), so except OSError catches it, and also timeouts and other network failures.
  • Each rule carries if_store_down. /menu says "open": allowed: True, browsing keeps working. /send-otp says "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:

  1. A client (a user, or a partner's server with an API key) sends POST /shorten.
  2. 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).
  3. 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.
  4. Allowed: the request goes on to the service (/shorten, /menu, /send-otp). Refused: the gateway answers 429 Too Many Requests with Retry-After, and the service never sees it.
  5. 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

  1. Different users, different limits → requirements, and rules as data: free 10, partner 1,000, OTP 3, default 100.
  2. Read, check, write with 50 requests at once → allowed 50 of 50, counter says 1: a race condition.
  3. One atomic step (a lock; Redis INCR, MULTI/EXEC, a Lua script) → allowed exactly 10 of 50.
  4. 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).
  5. The store goes down → ConnectionRefusedError(111, 'Connection refused') → fail open for /menu, fail closed for /send-otp, and alert.
  6. 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 INCR and before EXPIRE, 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, like priya:/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 of MULTI/EXEC or 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 bot1 and for bot2 → exactly 10 allowed each; 1,500 at once for ChaiStats → exactly 1,000; 10 OTP requests → exactly 3. The whole read-estimate-increment happens inside run_script's lock, so no two requests can interleave, like a Lua script in Redis.
  • Only allowed requests are counted here (sliding_script checks before it increments, both inside the same atomic script). That's safe because the check and the increment are in one step; it's the GET then INCR in 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-After gets 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: /menu and /shorten fail open (200, with a note for the logs), /send-otp fails closed (503), and the error counter raises an ALERT. /menu has no rule of its own, so it uses DEFAULT, which fails open.
  • Keys expire after two windows ((minute + 2) * WINDOW): minute 0's counter is still needed as before during 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

  1. Homework: in the RACE demo, remove the time.sleep line and run it a few times. Is it still broken?
  2. Homework: in the SLIDING demo, change the last burst from t = 90 to t = 119. How many get in, and why?
  3. Homework: in the RULES demo, add an internal plan with no limit on any path.
  4. Homework: should /login fail open or closed? Why?
  5. 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)?
  6. 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?
  7. Why does the mini project keep each counter for two windows instead of one?
  8. A fixed-window limiter (60 s windows) refuses a request at t = 42. What Retry-After should 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. LIMIT is 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 INCR alone always enough? (If you GET and 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/EXEC or Lua for INCR + 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 + EXPIRE in MULTI/EXEC; or a Lua script with EVAL) 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:minute that 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).