These are the notes for System Design episode 27, our first complete system built from the blocks of earlier episodes. ChaiNow's Diwali offer goes out by SMS, and a 90-character link eats the whole message. You'll write the requirements (functional and non-functional) and a back-of-the-envelope estimate (39 new links and about 3,900 clicks a second, 6 billion links and 3 TB in five years), try making the code by hashing the URL and cutting it short (292 collisions in 100,000 links, thanks to the birthday paradox), switch to a counter written in base62 (7 characters = 3.5 trillion codes), hand out id blocks so many servers never fight over one counter, shuffle the codes with a reversible multiply so nobody can guess the next one, choose between 301 and 302 redirects, and finish with the whole design: a cache in front, a key-value store behind, and a queue for click analytics. Every demo is plain Python (standard library only) and runs as-is; outputs are real (Python 3.13). ChaiNow, chainow.in and the short domain chai.nw are made up, and so are all the estimate's inputs: they are our assumptions, stated out loud, as you should do in an interview.
A URL shortener is a service that turns a long web address into a short one, and sends anyone who opens the short one to the long one. Example: chai.nw/q0U (11 characters) opens https://chainow.in/menu/masala-chai?ref=sms. A URL (Uniform Resource Locator) is a web address: the text you type or tap to open a page, such as https://chainow.in/menu.
The problems
| Problem | What it teaches |
|---|---|
| The link eats the SMS | Functional vs non-functional requirements, read-heavy systems, back-of-the-envelope estimates |
| Hash the URL and cut it? | Hashes, MD5, collisions, the birthday paradox |
| Count instead | A counter for uniqueness, base62 encoding and decoding |
| Many servers, one counter | Bottlenecks, single points of failure, id blocks, gaps in ids |
| The codes are guessable | Enumeration, a reversible shuffle with multiply and modulo, the modular inverse |
| Redirect, fast | 301 vs 302, the Location header, caching, key-value stores, sharding, an analytics queue |
Problem 1: the link eats the SMS
ChaiNow's marketing team wants to send a Diwali offer by SMS (a text message on a phone) to 2 crore customers (1 crore = 10 million, so 20 million people). In our story, one SMS holds 160 characters, and every character counts.
| Step | What we have | Length |
|---|---|---|
| The SMS | room for the whole message | 160 characters |
| The tracking link | chainow.in/offers/diwali-2026?... |
90 characters |
| What we want | chai.nw/q0U |
11 characters |
The link alone uses more than half the message; there's no room to say what the offer is. So we want a short code (the few characters after the domain, here q0U) that sends you to the long page when you tap it. Sending a browser from one URL to another is called a redirect.
Before writing any code, an interviewer wants two things: requirements (what exactly are we building?) and a size estimate (how big does it get?).
Requirements: what must it do, and how well?
A requirement is something the system must do or be. There are two kinds:
- A functional requirement says what the system does: a feature a user can see. Example: "give it a long URL, get back a short code".
- A non-functional requirement says how well it does it: speed, correctness, uptime, cost. Example: "a redirect takes a few milliseconds".
| Kind | Requirement | Why it matters for ChaiNow |
|---|---|---|
| Functional | Shorten: long URL → short code (7 characters) | The whole point: fit the link in the SMS |
| Functional | Redirect: short code → the long URL | A tap must open the offer page |
| Non-functional | Fast: a redirect in a few milliseconds | Nobody waits for a link to open |
| Non-functional | Never wrong: one code = one link, forever | A code must never open someone else's page |
| Non-functional | Always up | An SMS can't be unsent: if the shortener is down, every link in 2 crore messages is dead |
Later in an interview you'd add more functional requirements (custom aliases like chai.nw/diwali, links that expire, click counts; the mini project does all three) and more non-functional ones (cost, abuse protection). Start with the core two, then ask "what else?".
One observation shapes everything: a link is made once but clicked many, many times. A system that serves far more reads than writes is called read-heavy. A read here is a redirect (someone taps a link and we look up the code); a write is a new short link being saved. Read-heavy systems want a cache (episode 7): a small, fast copy of the most-used data kept close to the servers.
The back-of-the-envelope estimate
A back-of-the-envelope estimate is a rough calculation done quickly, with round numbers, to learn the size of a problem: is it 10 requests a second or 10,000? 1 GB or 1,000 TB? The name comes from doing it on the back of an envelope, not with exact data. The inputs are guesses you say out loud; the arithmetic is exact. If the interviewer gives different numbers, you change the inputs and run the same five lines again.
Our assumptions (made up for ChaiNow, not measured from any real service):
| Assumption | Value | Why it's a reasonable guess |
|---|---|---|
| New links per month | 100 million | A big public shortener, not just ChaiNow's own campaigns |
| Reads per write | 100 | Each link is clicked about 100 times on average |
| Bytes stored per link | 500 | Long URL + code + owner + dates |
| How long we keep links | 5 years | "Never wrong, forever" in practice means "for years" |
# Back-of-the-envelope estimate (our assumptions, say them out loud)
new_links_per_month = 100_000_000
reads_per_write = 100 # links are clicked far more than made
bytes_per_link = 500 # long URL + code + owner + dates
years = 5
seconds_per_month = 30 * 24 * 3600
writes = new_links_per_month / seconds_per_month
print(f"writes: {writes:,.0f} per second")
print(f"reads: {writes * reads_per_write:,.0f} per second")
total_links = new_links_per_month * 12 * years
print(f"links in {years} years: {total_links:,}")
print(f"storage: {total_links * bytes_per_link / 1e12:.0f} TB")
print(f"7-char codes used: {total_links / 62**7:.2%}")
Output:
writes: 39 per second
reads: 3,858 per second
links in 5 years: 6,000,000,000
storage: 3 TB
7-char codes used: 0.17%
How the numbers come out:
- A month is about 30 × 24 × 3,600 = 2,592,000 seconds. 100,000,000 / 2,592,000 = 38.6, printed as 39 writes a second.
- 100 reads per write → 3,858 reads a second (say "about 3,900" out loud).
- 100 million a month × 12 months × 5 years = 6,000,000,000 links (6 billion).
- 6 billion × 500 bytes (a byte is one character of plain text, roughly) = 3,000,000,000,000 bytes = 3 TB (a terabyte, TB, is 10^12 bytes, a million million).
62**7is the number of 7-character base62 codes (3.5 trillion, explained in Problem 3). Six billion links use only 0.17% of them. Hold on to that.- In the f-strings,
:,.0fmeans "comma-separated, no decimals", and:.2%means "as a percentage with 2 decimals".
What the estimate tells us:
- 39 writes a second is small. One database can take that.
- 3 TB is not huge either: one big database could hold it, though we'll plan to split it (sharding) as it grows.
- 3,900 reads a second, with some links going viral, is the real load. A viral link is one shared so widely that it gets a huge burst of clicks. That's why a cache sits in front.
- The read/write ratio (100:1) decides the design: optimise the redirect path first.
In an interview, these five lines of maths earn a lot of trust: they show you design for the real size, not a guess.
Problem 2: hash the URL and cut it?
Real-life example: gym lockers from your name
A gym decides to make your locker number from your name: the first three letters. Priya gets locker PRI. No list to keep, no counter to ask: the name alone gives the locker.
| Gym lockers | Short codes |
|---|---|
| Locker = first 3 letters of your name (Priya → PRI) | Hash + cut: md5(url)[:6] |
| Priya and Prince both get PRI | Collision: two links, one code |
| Hand out locker 1, 2, 3... | A counter: unique by design (Problem 3) |
Until Prince joins the gym. He also gets PRI. Two people, one locker: somebody opens the wrong locker. For us that's a collision: two different long URLs get the same short code, so a tap on one could open the other.
Hashes and MD5
A hash (or hash function) turns any input into a fixed-size jumble of characters. The same input always gives the same output, and a tiny change to the input gives a completely different output. Example: the MD5 hash of https://chainow.in/menu/masala-chai?ref=sms starts with e1251b.
MD5 is one well-known hash function. Its output is 128 bits, usually written as 32 hex characters (hex = base 16: the digits 0-9 and the letters a-f). Python has it in the standard library: hashlib.md5(data).hexdigest() gives the 32-character hex string.
Thirty-two characters is too long, so the idea is: hash the URL and keep the first six characters. Six hex characters give 16^6 = 16,777,216 possible codes, and we'll make only 100,000 links. Surely that's safe?
import hashlib, random
random.seed(42)
def short_code(url): # first 6 hex chars of the MD5 hash
return hashlib.md5(url.encode()).hexdigest()[:6]
print(short_code("https://chainow.in/menu/masala-chai?ref=sms"))
links, collisions = {}, 0
for i in range(100_000): # 100,000 different long links
url = f"https://chainow.in/order/{random.getrandbits(64)}"
code = short_code(url)
if code in links and links[code] != url:
collisions += 1 # two links, same short code!
links[code] = url
print("links:", 100_000, " collisions:", collisions)
print("possible codes:", f"{16**6:,}")
Output:
e1251b
links: 100000 collisions: 292
possible codes: 16,777,216
How it works:
url.encode()turns the text into bytes (hash functions work on bytes),.hexdigest()gives the hash as hex text, and[:6]keeps the first six characters.random.seed(42)makes the "random" numbers the same on every run, so you get exactly 292.random.getrandbits(64)is a random 64-bit number, so each URL is different.linksis a dictionary from code to URL. If a code is already there for a different URL, that's a collision.- Notice
links[code] = urlthen overwrites the old link. In a real service that means a customer who saved the old short link now lands on somebody else's order page.
292 collisions. 292 times, a customer would tap a Diwali offer and land on somebody else's page. And we used only 100,000 of 16.7 million codes (0.6%).
Why so many? The birthday paradox
In a room of just 23 people, there's about a 50% chance that two of them share a birthday, even though there are 365 days. That surprise is the birthday paradox. The trick: you're not asking "does someone share my birthday?" but "do any two people share one?", and 23 people make 23 × 22 / 2 = 253 pairs, each a chance to match.
# Birthday paradox: chance that at least two of k people share a birthday
def chance_shared(k, days=365):
p_all_different = 1.0
for i in range(k):
p_all_different *= (days - i) / days
return 1 - p_all_different
for k in (10, 23, 50):
print(f"{k} people: {chance_shared(k):.1%}")
# the same maths for short codes: expected clashing pairs ~ n^2 / (2N)
n, N = 100_000, 16**6
print(f"expected collisions: about {n * n / (2 * N):.0f}")
Output:
10 people: 11.7%
23 people: 50.7%
50 people: 97.0%
expected collisions: about 298
chance_sharedmultiplies the chance that each new person avoids every earlier birthday: 365/365, then 364/365, then 363/365, and so on. One minus that is the chance of at least one match.- For codes: each new link can collide with every link before it. With n links and N possible codes there are about n² / 2 pairs, each matching with chance 1/N, so about n² / (2N) collisions: 100,000² / (2 × 16,777,216) ≈ 298. Our real run gave 292. The formula works.
- So clashes start long before the codes run out: around the square root of N, not N. For 16.7 million codes, √N ≈ 4,096 links is already where the first clash becomes likely.
Hashing can be rescued: check the database before saving, and on a clash add something to the URL and hash again (check and retry). But every new link now needs an extra database read, and you must handle two servers racing for the same code. There's a simpler way.
Problem 3: don't derive the code, count
The gym's simple fix: hand out locker 1, 2, 3, ... A counter is a number that goes up by one every time it's used. Every new link gets the next number, so no two links can ever share one. Unique by design, no checking needed.
But numbers get long: link six billion is 6000000000, 10 digits. To make them short, write them in a bigger base. A base is how many different digit symbols a number system uses: base 10 uses 0-9; base 16 (hex) adds a-f. Base62 uses 62 symbols: 10 digits, 26 small letters and 26 capital letters, all safe to put in a URL.
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def encode(n): # number -> short code
code = ""
while True:
n, digit = divmod(n, 62)
code = ALPHABET[digit] + code
if n == 0:
return code
def decode(code): # short code -> number
n = 0
for ch in code:
n = n * 62 + ALPHABET.index(ch)
return n
for n in (1, 61, 62, 125, 1_000_000, 62**7 - 1):
print(f"{n:>17,} -> {encode(n):>7} -> {decode(encode(n)):,}")
print("7 characters give", f"{62**7:,}", "codes")
Output:
1 -> 1 -> 1
61 -> Z -> 61
62 -> 10 -> 62
125 -> 21 -> 125
1,000,000 -> 4c92 -> 1,000,000
3,521,614,606,207 -> ZZZZZZZ -> 3,521,614,606,207
7 characters give 3,521,614,606,208 codes
How it works:
- encode is how you write a number in any base.
divmod(n, 62)gives the quotient and the remainder (what's left over after dividing). The remainder picks one character fromALPHABET, and we put it at the front of the code. Repeat with the quotient until it reaches 0. It's the same as writing 125 in base 10: 125 → remainder 5, then 12 → remainder 2, then 1 → remainder 1: "125". - decode reverses it: for each character, multiply what you have by 62 and add the character's position in the alphabet.
ALPHABET.index(ch)gives that position. while Truewith the check at the end makesencode(0)return"0"instead of an empty string.
Reading the output:
- 1 is
1, 61 isZ(the last symbol), and 62 is10, just like 10 comes after 9 in base 10. - 125 is
21: 2 × 62 + 1 = 125. - 1,000,000 is
4c92: 4 × 62³ + 12 × 62² + 9 × 62 + 2 = 953,312 + 46,128 + 558 + 2 = 1,000,000 (cis position 12). - The biggest 7-character code is
ZZZZZZZ= 62^7 − 1. So 7 characters give 62^7 = 3,521,614,606,208 codes, about 3.5 trillion. Our six billion links use 0.17% of them (the spoiler from the estimate). - Every code decodes back to its number:
decode(encode(n)) == n, a round trip.
| Approach | Unique? | Extra database check per link? | Code length |
|---|---|---|---|
| Hash + cut to 6 hex | No: 292 collisions in 100,000 | Yes, to catch clashes | 6 |
| Counter + base62 | Yes, by design | No | 7 covers 3.5 trillion |
You just invented base62 short codes!
Problem 4: many servers, one counter
Real-life example: token rolls at a temple
ChaiNow runs many app servers (the machines running our shortener code, behind a load balancer from episode 6). Where does the counter live? If it's one number in one database, and every new link on every server must ask it for the next number:
- It becomes the bottleneck: the one part that limits the speed of the whole system, like the narrow neck of a bottle that limits how fast water pours.
- It becomes a single point of failure: one part that, if it stops, stops everything. Counter down = no new links anywhere.
A busy temple has the same problem with its token queue. One token counter for everyone means everyone waits for it. So the temple gives each gate a roll of 1,000 tokens: gate A gets 1 to 1,000, gate B gets 1,001 to 2,000. Each gate hands out tokens by itself and only goes back to the office when its roll runs out.
| A temple queue | Our servers |
|---|---|
| One token counter for all: everyone waits | One shared counter: every link waits on it (bottleneck) |
| Each gate gets a roll of 1,000 (A: 1-1000, B: 1001-2000) | Id blocks: ask once per 1,000 links (1,000× fewer trips) |
| A gate closes early: unused tokens wasted | Gaps in ids: fine, we have trillions |
An id block is a range of ids handed to one server at once. The server uses them one by one from its own memory and asks for a new block only when it runs out. In episode 23, two servers split ids into odd and even lanes; blocks work for any number of servers, and adding a server needs no change at all.
Code: two servers, no clashes
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def encode(n): # base62, as before
return (encode(n // 62) if n >= 62 else "") + ALPHABET[n % 62]
next_block = 0 # the ONE shared counter (database)
def take_block(size=1000): # a server grabs 1,000 ids at once
global next_block
start = next_block; next_block += size
return iter(range(start, start + size))
class AppServer:
def __init__(self): self.ids = take_block()
def shorten(self, url):
code = encode(next(self.ids) + 100_000)
links[code] = url
return "chai.nw/" + code
def redirect(code):
if code not in links: return 404, "Not Found"
return 302, "Location: " + links[code]
links = {}
a, b = AppServer(), AppServer() # two servers, no clashes
print(a.shorten("https://chainow.in/menu/masala-chai?ref=sms"))
print(b.shorten("https://chainow.in/offers/diwali-2026"))
print(a.shorten("https://chainow.in/order/5514/track"))
print(redirect("q0U"))
print(redirect("zzz"))
Output:
chai.nw/q0U
chai.nw/qh2
chai.nw/q0V
(302, 'Location: https://chainow.in/menu/masala-chai?ref=sms')
(404, 'Not Found')
How it works:
encodeis the same base62 as before, written recursively (the function calls itself for the higher digits):encode(n // 62)writes everything but the last digit, andALPHABET[n % 62]adds the last one.%is modulo: the remainder after dividing.next_blockstands for the one shared counter in a database.take_blockmoves it forward by 1,000 and hands that whole range to one server.global next_blocktells Python we mean the variable outside the function (forget it and you get an error; see the common mistakes).iter(range(...))makes an iterator: an object that hands out the next value each time you callnext()on it, and remembers where it stopped.- Each
AppServertakes a block when it starts. Serveragets ids 0-999, serverbgets 1,000-1,999. + 100_000just skips the tiny numbers so the codes look like codes: id 0 becomes 100,000 =q0U(q = 26, 0, U = 56: 26 × 3,844 + 0 × 62 + 56 = 100,000). Serverb's first id, 1,000, becomes 101,000 =qh2.linksis a dictionary from code to long URL: our stand-in for the database.
Reading the output: server A gives q0U and then q0V; server B, from its own block, gives qh2. No clashes, no waiting: each server talks to the counter once per 1,000 links.
The redirect: 302, Location and 404
The web runs on HTTP (HyperText Transfer Protocol), the rules a browser and a server use to talk. Every HTTP answer starts with a status code, a 3-digit number saying what happened:
| Code | Name | Meaning here |
|---|---|---|
| 302 | Found | "What you want is over there, for now": a temporary redirect |
| 301 | Moved Permanently | "It moved there for good": a permanent redirect (Problem 6) |
| 404 | Not Found | No such short code |
A redirect answer also carries a header (extra named information sent with an HTTP message) called Location: the URL the browser should go to next. So redirect("q0U") answers 302 with Location: https://chainow.in/menu/masala-chai?ref=sms, and the browser opens that page by itself. An unknown code like zzz gets 404.
The price: gaps
If a server crashes after using 250 ids of its block, the other 750 are never used: the temple gate that closed early.
next_block = 100_000
def take_block(size=1000):
global next_block
start = next_block; next_block += size
return iter(range(start, start + size))
ids = take_block()
for _ in range(250): next(ids) # server A makes 250 links...
ids = take_block() # ...crashes, restarts, new block
print("first id after restart:", next(ids))
print("ids lost in the gap:", 1000 - 250)
Output:
first id after restart: 101000
ids lost in the gap: 750
The restarted server can't know which ids it already used (they were only in its memory), so it must take a fresh block. With 3.5 trillion codes and 0.17% in use, a few hundred lost ids per crash is a cheap price. The counter itself still lives in one database, but it's touched once per 1,000 links, so it can be a small, carefully replicated database (copies on several machines, episode 11) without slowing anything.
But look again: q0U, q0V...
Counter codes come out in order. Next after q0V is obviously q0W. Anyone can walk through codes one by one and open other people's links: private documents, order pages, invite links. Trying every possible value one after another like this is called enumeration.
Problem 5: the codes are guessable
Real-life example: hotel room keys
| A hotel | Short codes |
|---|---|
| Rooms 101, 102, 103: easy to guess the next door | Counter codes: q0U, q0V, q0W, walk through them |
| Key cards with a scrambled id; the desk can map it back | Scrambled codes: oJfTb2w, 12YH3nB, still one per room |
| Private rooms need a real lock, not just an odd number | Private links: long random codes + a login. Hard to guess ≠ secret |
So we scramble the number before encoding it, in a way that (1) can be undone, and (2) can never give two numbers the same code. A rule that sends every input to a different output, so nothing collides and every output is used exactly once, is a permutation (a shuffle).
The reversible multiply
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def encode(n, width=7):
code = ""
for _ in range(width):
n, d = divmod(n, 62); code = ALPHABET[d] + code
return code
M = 62 ** 7 # all 7-character codes
P = 2_176_477_521_739 # odd, not a multiple of 31
P_INV = pow(P, -1, M) # undo the shuffle
def scramble(n): return (n * P) % M # one id -> one code, no clashes
def unscramble(c): return (c * P_INV) % M
for n in (100_000, 100_001, 100_002):
print(n, "->", encode(n), " shuffled ->", encode(scramble(n)))
codes = {scramble(n) for n in range(1_000_000)}
print("1,000,000 ids ->", f"{len(codes):,}", "different codes")
print("back:", unscramble(scramble(100_001)))
Output:
100000 -> 0000q0U shuffled -> oJfTb2w
100001 -> 0000q0V shuffled -> 12YH3nB
100002 -> 0000q0W shuffled -> DmHuVIG
1,000,000 ids -> 1,000,000 different codes
back: 100001
How it works:
- This
encodealways writes exactly 7 characters (width=7), padding with0at the front:0000q0U. All codes are now the same length. - M = 62^7, the number of 7-character codes.
scramblemultiplies the id by a big number P and keeps the remainder after dividing by M (% M). The result is always between 0 and M − 1, so it always fits in 7 characters. This "wrap around at M" arithmetic is modular arithmetic, like a clock that wraps at 12. - Why no clashes? M = 62^7 = 2^7 × 31^7. Because P is odd and not a multiple of 31, P and M share no common factor (their greatest common divisor is 1; such numbers are called coprime). For coprime P and M, multiplying by P modulo M is a permutation: every id from 0 to M − 1 lands on a different code.
- P_INV is the modular inverse of P: the number that "undoes" multiplying by P, because P × P_INV leaves remainder 1 when divided by M. Here P_INV = 2,496,727,397,347.
pow(P, -1, M)computes it (built into Python since 3.8). Sounscramble(scramble(n)) == n: the desk can map the key card back to the room. - The set comprehension
{scramble(n) for n in range(1_000_000)}keeps only distinct values. 1,000,000 ids → 1,000,000 different codes: no collisions.
Reading the output: neighbours q0U, q0V, q0W become oJfTb2w, 12YH3nB, DmHuVIG, which look unrelated. Unique like a counter, scattered like random, and reversible. You just invented non-guessable short codes!
Where it fits: the server takes the next id from its block, scrambles it, base62-encodes it to 7 characters, and saves code → URL. The store doesn't even need to keep the id: unscramble(decode(code)) gives it back.
One warning. This makes codes hard to guess by counting. It is not a secret lock: anyone who learns P (it's in your code) can unscramble too, and 3.5 trillion codes with 6 billion in use means a random guess still sometimes hits a real link. Truly private links need long random codes, or a login like episode 26.
Problem 6: redirect, fast
301 or 302?
Two status codes can send the browser on:
HTTP/1.1 301 Moved Permanently
Location: https://chainow.in/offers/diwali-2026
HTTP/1.1 302 Found
Location: https://chainow.in/offers/diwali-2026
- 301 Moved Permanently: MDN describes it as "the requested resource has been permanently moved to the URL in the Location header", and "a browser receiving this status will automatically request the resource at the URL in the Location header". Search engines (sites like web search that index pages) "attribute links to the original URL to the redirected resource". The catch, from http.dev: "Browsers cache 301 responses aggressively based on Cache-Control directives", and without explicit cache headers "the redirect persists in browser cache indefinitely". (Cache-Control is the HTTP header that tells browsers how long they may keep a copy.) So the next tap goes straight to the long URL without asking us.
- 302 Found is the temporary redirect; http.dev calls it "a detour". The browser asks us again every time.
Here's the difference in a few lines (a pretend browser that remembers 301s and not 302s, as described above):
# A browser that obeys caching: it remembers 301s, not 302s
def simulate(status, taps=5):
browser_cache, hits_on_server = {}, 0
for _ in range(taps):
if "q0U" in browser_cache: # remembered: no request sent
continue
hits_on_server += 1 # the tap reaches our server
if status == 301:
browser_cache["q0U"] = "https://chainow.in/offers/diwali-2026"
return hits_on_server
print("301: clicks counted:", simulate(301), "of 5")
print("302: clicks counted:", simulate(302), "of 5")
Output:
301: clicks counted: 1 of 5
302: clicks counted: 5 of 5
| 301 Moved Permanently | 302 Found | |
|---|---|---|
| Meaning | Moved for good | Temporary, ask me again |
| Browser caches it? | Yes, aggressively | No, by default |
| Later taps reach our servers? | No | Yes, every one |
| Load on us | Less | More |
| Can we count clicks? | Only the first per browser | Every click |
| Can we change or expire the link? | Browsers that cached it won't notice | Yes |
ChaiNow's marketing wants to know how many people tapped the Diwali offer, and some links must expire after the sale. So ChaiNow sends 302. A shortener that doesn't need analytics and wants the least load could choose 301. Either way, it's a trade-off you state out loud.
The whole design
phone taps chai.nw/q0U
|
load balancer (episode 6)
|
app servers -- each holds an id block, scrambles + base62-encodes new codes
|
cache (hot codes, episode 7) -- miss --> key-value store: code -> URL
| (sharded by code, episodes 9, 12)
click event --> queue (episode 16) --> analytics workers --> click counts
- Cache in front. 3,900 reads a second, and one viral link can mean millions of reads of the same code. Keeping hot codes in memory means most taps never touch the database (in the mini project, 551 successful redirects need only 4 database reads). Links almost never change, so the cache stays correct; when a link expires or is deleted, remove it from the cache too.
- Key-value store. The data is one simple lookup, code → URL, with no joins and no complex queries. A key-value store is a database that stores values under keys and finds a value by its exact key, like a giant dictionary. It fits perfectly.
- Sharded by code. When it grows past one machine, split the data across many machines by code: sharding (episode 12) means each machine (shard) holds part of the keys, for example by hashing the code to pick a shard. Because scrambled codes are spread evenly, the shards fill evenly.
- Clicks go to a queue. Each tap becomes an event (a small record: which code, when) put on a queue (episode 16), a waiting line of messages that other programs process later. Analytics (counting and studying clicks) workers read the queue and update counts. The redirect never waits for counting, so it stays fast even when analytics is slow.
- Rate limit the shorten API. Spammers love free short links that hide where they point. A rate limit caps how many requests one user may make in a time window. That's the next episode.
Notice the order we followed: requirements → estimate → design → trade-offs. That's the order for every design interview.
The whole chain
- 90-character link ate the SMS → requirements (shorten, redirect, fast, never wrong, always up) and an estimate: 39 writes/s, 3,858 reads/s, 6 billion links, 3 TB (from our assumptions).
- Hash and cut to 6 hex characters → 292 collisions in 100,000 links (birthday paradox: about n²/2N).
- Count + base62 → unique by design; 7 characters = 3,521,614,606,208 codes, 0.17% used.
- One counter, many servers → bottleneck and single point of failure → id blocks of 1,000 (
q0U,qh2,q0V), gaps are fine. - q0U, q0V, ... are guessable → reversible shuffle: multiply by P modulo 62^7, 1,000,000 ids → 1,000,000 codes, undone with the modular inverse.
- 302 to count every click (301 is cached by browsers) · cache · key-value store sharded by code · analytics queue.
Common mistakes (and the real outputs)
| Mistake | Code | Output | Fix |
|---|---|---|---|
| Cutting a hash short | code = md5(url)[:6] |
links: 100000 collisions: 292 |
Counter + base62, or check and retry |
| Codes straight from a counter | encode(next_id) |
next codes: ['q0V', 'q0W', 'q0X', 'q0Y', 'q0Z'] |
Reversible shuffle, or random codes |
| 301 for marketing links | return 301, ... |
301: clicks counted: 1 of 5 |
302 when you need every click |
| A multiplier that shares a factor with M | P = 2_176_477_521_738 (even) |
same code: True, then ValueError: base is not invertible for the given modulus |
P must be coprime with 62^7: odd and not a multiple of 31 |
Forgetting global for the shared counter |
next_block += size inside a function |
UnboundLocalError: cannot access local variable 'next_block' where it is not associated with a value |
global next_block (or keep the counter in an object) |
| Decoding user input without checking it | decode("q0-U") |
ValueError: substring not found |
Check every character is in the alphabet; answer 404 |
The second mistake, run for real (given one code, the next five are obvious):
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def encode(n):
return (encode(n // 62) if n >= 62 else "") + ALPHABET[n % 62]
def decode(code):
n = 0
for ch in code:
n = n * 62 + ALPHABET.index(ch)
return n
mine = "q0U" # the code I was given
start = decode(mine)
print("my id:", start)
print("next codes:", [encode(n) for n in range(start + 1, start + 6)])
Output:
my id: 100000
next codes: ['q0V', 'q0W', 'q0X', 'q0Y', 'q0Z']
The fourth mistake, an even multiplier:
M = 62 ** 7
P = 2_176_477_521_738 # even: shares the factor 2 with M
def scramble(n): return (n * P) % M
a, b = 5, 5 + M // 2 # two different ids
print(a, "->", scramble(a))
print(b, "->", scramble(b))
print("same code:", scramble(a) == scramble(b))
P_INV = pow(P, -1, M)
Output:
5 -> 317543790066
1760807303109 -> 317543790066
same code: True
Traceback (most recent call last):
File "m_even.py", line 9, in <module>
P_INV = pow(P, -1, M)
ValueError: base is not invertible for the given modulus
With an even P, ids n and n + M/2 differ by M/2, and (M/2) × P is a multiple of M (because P supplies the missing factor 2), so both land on the same code. Two links, one code, exactly what we were avoiding, and Python refuses to compute an inverse. (Within the first million ids this P happens not to clash, which is why such a bug can hide in testing.)
The fifth mistake:
next_block = 0
def take_block(size=1000): # forgot: global next_block
start = next_block; next_block += size
return iter(range(start, start + size))
take_block()
Output:
Traceback (most recent call last):
File "m_global.py", line 6, in <module>
take_block()
~~~~~~~~~~^^
File "m_global.py", line 3, in take_block
start = next_block; next_block += size
^^^^^^^^^^
UnboundLocalError: cannot access local variable 'next_block' where it is not associated with a value
Because the function assigns to next_block, Python treats it as a new local variable for the whole function, so reading it on the first line fails.
The sixth mistake:
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def decode(code):
n = 0
for ch in code:
n = n * 62 + ALPHABET.index(ch)
return n
print(decode("q0U"))
print(decode("q0-U")) # a user typed a dash
Output:
100000
Traceback (most recent call last):
File "m_decode.py", line 9, in <module>
print(decode("q0-U")) # a user typed a dash
~~~~~~^^^^^^^^
File "m_decode.py", line 5, in decode
n = n * 62 + ALPHABET.index(ch)
~~~~~~~~~~~~~~^^^^
ValueError: substring not found
str.index raises when the character isn't in the alphabet. A server that crashes on a mistyped link is worse than one that answers 404.
(File paths in the tracebacks are shortened to the file name.)
Mini project: a complete in-memory URL shortener
Everything from the episode in about 130 lines of standard-library Python: id blocks shared by two app servers, scrambled base62 codes, custom aliases (chai.nw/diwali), links that expire, 302 / 404 redirects, an LRU cache in front of a key-value store, and a click queue drained by an analytics worker. A fake clock makes expiry repeatable.
New terms used here:
- An alias (custom alias) is a short name the user picks instead of a generated code, like
diwali. - TTL (time to live) is how long a link stays valid, here in seconds; after that it expires and answers 404.
- LRU (least recently used) is a cache rule: when the cache is full, throw out the item that was used longest ago.
OrderedDictkeeps items in order,move_to_endmarks one as just used, andpopitem(last=False)removes the oldest. - A regular expression (
re) is a pattern for text:[A-Za-z0-9-]{3,30}means "3 to 30 letters, digits or dashes". - A deque (double-ended queue,
collections.deque) is a list that's fast to add to at one end and take from at the other: our stand-in for a message queue.
# Mini project: an in-memory URL shortener (stdlib only)
import re
from collections import OrderedDict, deque
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
M = 62 ** 7 # all 7-character codes
P = 2_176_477_521_739 # shares no factor with M
P_INV = pow(P, -1, M)
def encode(n, width=7):
code = ""
for _ in range(width):
n, d = divmod(n, 62); code = ALPHABET[d] + code
return code
def decode(code):
n = 0
for ch in code:
n = n * 62 + ALPHABET.index(ch)
return n
class Clock: # a fake clock, so runs repeat
def __init__(self): self.now = 0
def tick(self, seconds): self.now += seconds
class IdBlocks: # the one shared counter
def __init__(self, start=100_000, size=1000):
self.next, self.size = start, size
def take(self):
start = self.next; self.next += self.size
return iter(range(start, start + self.size))
class Store: # key-value store: code -> record
def __init__(self): self.data, self.reads = {}, 0
def get(self, code):
self.reads += 1
return self.data.get(code)
def put(self, code, record): self.data[code] = record
class Cache: # LRU cache for hot codes
def __init__(self, size): self.items, self.size = OrderedDict(), size
def get(self, code):
if code in self.items:
self.items.move_to_end(code) # most recently used
return self.items[code]
return None
def put(self, code, record):
self.items[code] = record; self.items.move_to_end(code)
if len(self.items) > self.size:
self.items.popitem(last=False) # drop the least recently used
def drop(self, code): self.items.pop(code, None)
ALIAS = re.compile(r"[A-Za-z0-9-]{3,30}")
class Shortener:
def __init__(self, blocks, store, cache, queue, clock):
self.blocks, self.store, self.cache = blocks, store, cache
self.queue, self.clock = queue, clock
self.ids = blocks.take()
def _next_code(self):
while True:
n = next(self.ids, None)
if n is None: # block used up: get another
self.ids = self.blocks.take(); continue
code = encode((n * P) % M) # scrambled, never repeats
if self.store.get(code) is None: # skip if an alias took it
return code
def shorten(self, url, alias=None, ttl=None):
if not url.startswith(("http://", "https://")):
raise ValueError("not a web address: " + url)
if alias is not None:
if not ALIAS.fullmatch(alias):
raise ValueError("bad alias: " + alias)
if self.store.get(alias) is not None:
raise ValueError("alias taken: " + alias)
code = alias
else:
code = self._next_code()
expires = None if ttl is None else self.clock.now + ttl
self.store.put(code, {"url": url, "expires": expires})
return "chai.nw/" + code
def redirect(self, code):
record = self.cache.get(code)
if record is None:
record = self.store.get(code)
if record is None:
return 404, "Not Found"
self.cache.put(code, record)
if record["expires"] is not None and self.clock.now >= record["expires"]:
self.cache.drop(code)
return 404, "Not Found (expired)"
self.queue.append((code, self.clock.now)) # click event, no waiting
return 302, "Location: " + record["url"]
def analytics_worker(queue, counts): # runs separately, drains the queue
while queue:
code, _when = queue.popleft()
counts[code] = counts.get(code, 0) + 1
# ---- wire it up: two app servers share one store, one cache, one queue
clock, store, queue, counts = Clock(), Store(), deque(), {}
blocks, cache = IdBlocks(), Cache(size=100)
a = Shortener(blocks, store, cache, queue, clock)
b = Shortener(blocks, store, cache, queue, clock)
diwali = a.shorten("https://chainow.in/offers/diwali-2026", alias="diwali")
menu = a.shorten("https://chainow.in/menu/masala-chai?ref=sms")
flash = b.shorten("https://chainow.in/offers/flash-sale", ttl=3600)
print(diwali, menu, flash)
for bad in [("https://chainow.in/x", "diwali"), ("ftp://old", None),
("https://chainow.in/y", "no spaces!")]:
try:
a.shorten(bad[0], alias=bad[1])
except ValueError as e:
print("refused:", e)
flash_code = flash.split("/")[1]
for _ in range(500): a.redirect("diwali") # a viral link
for _ in range(40): b.redirect(menu.split("/")[1])
for _ in range(10): a.redirect(flash_code)
print(a.redirect("diwali"))
print(b.redirect("zzzzzzz"))
clock.tick(3600) # one hour later
print(a.redirect(flash_code))
analytics_worker(queue, counts)
print("clicks:", counts)
print("redirects served:", sum(counts.values()), " store reads:", store.reads)
print("decode the code back to its id:", (decode(menu[-7:]) * P_INV) % M)
Output (identical on every run):
chai.nw/diwali chai.nw/oJfTb2w chai.nw/qPUlD3a
refused: alias taken: diwali
refused: not a web address: ftp://old
refused: bad alias: no spaces!
(302, 'Location: https://chainow.in/offers/diwali-2026')
(404, 'Not Found')
(404, 'Not Found (expired)')
clicks: {'diwali': 501, 'oJfTb2w': 40, 'qPUlD3a': 10}
redirects served: 551 store reads: 8
decode the code back to its id: 100000
What to notice:
- Generated codes are the episode's codes. Server
a's first id is 100,000, which scrambles tooJfTb2w, the same as the SHUFFLE demo. Serverbtook the next block (101,000-101,999), so its first codeqPUlD3acan never clash witha's. - Aliases and generated codes share one key space. An alias is checked before saving (
alias taken: diwali), and_next_codeskips a generated code if someone already took it as an alias (a 7-character alias could, in theory, equal a future scrambled code). - Input is checked at the door: non-web addresses and bad aliases are refused before touching the store.
- The cache absorbs the viral link. 551 successful redirects were served with only 4 store reads for redirects (the first lookup of each of
diwali,oJfTb2w,qPUlD3a, plus the unknownzzzzzzz); the other 4 of the 8 reads came from shortening (two alias checks and two "is this code free?" checks). - Expiry: after
clock.tick(3600), the flash-sale link answers404, 'Not Found (expired)'and is dropped from the cache. The expired tap isn't counted as a click. - Clicks are counted later, by
analytics_worker, from the queue:diwalihas 501 (500 + the one printed). The redirect only appended an event; it never waited for counting. - Round trip: decoding
oJfTb2wand unscrambling withP_INVgives back id 100,000.
Extend it: answer 301 for links created with a "permanent" flag; add a per-user rate limit to shorten (next episode); store created and owner in each record and add delete(code, user) that also drops the code from the cache; give Store several shards and pick one with hash(code) % shards.
Practice
- Homework: in the HASHCUT demo, keep 8 characters instead of 6. How many collisions now?
- Homework: in the ESTIMATE demo, make it 1 billion new links a month. What changes?
- Homework: in the BASE62 demo, what is
encode(3844)? Work it out by hand first. - Homework: how would you add custom aliases (
chai.nw/diwali)? What can go wrong? - At our assumed 100 million links a month, how many years until 6-, 7- and 8-character codes run out?
- You decide to cache the hottest 1 million links at 500 bytes each. How much memory? If 3,858 reads a second arrive and the cache answers 80%, 95% or 99% of them, how many reach the database?
- Why must P be odd and not a multiple of 31? Would P = 31 × 1,000,001 work?
- Pick 301 or 302 for: (a) a company moving its whole old domain to a new one, forever; (b) a printed poster QR code whose campaign page changes each month; (c) ChaiNow's Diwali SMS.
- With blocks of 1,000 and 50 app servers that each restart once a day, at most how many ids are wasted per day? Does it matter?
Solutions and hints
1. The same 100,000 URLs, cut to 6, 7 and 8 hex characters:
import hashlib, random
random.seed(42)
def short_code(url, length):
return hashlib.md5(url.encode()).hexdigest()[:length]
urls = [f"https://chainow.in/order/{random.getrandbits(64)}" for _ in range(100_000)]
for length in (6, 7, 8):
links, collisions = {}, 0
for url in urls:
code = short_code(url, length)
if code in links and links[code] != url:
collisions += 1
links[code] = url
print(f"{length} hex chars: {16**length:>14,} codes collisions: {collisions}")
Output:
6 hex chars: 16,777,216 codes collisions: 292
7 hex chars: 268,435,456 codes collisions: 15
8 hex chars: 4,294,967,296 codes collisions: 3
The 6-character row is the video's demo (same seed, same URLs). Each extra hex character multiplies the codes by 16 and divides the expected collisions by about 16 (n²/2N: 298 → 19 → 1.2; real runs vary around that). Still not zero. At 6 billion links even 8 hex characters would clash constantly: 6×10⁹ is far above √(4.3×10⁹) ≈ 65,536. Cut hashes need check-and-retry at any length; a counter needs nothing.
2. Change the first line to 1_000_000_000:
writes: 386 per second
reads: 38,580 per second
links in 5 years: 60,000,000,000
storage: 30 TB
7-char codes used: 1.70%
Everything scales by 10. 386 writes a second is still easy for id blocks (one counter trip every few seconds overall); 38,580 reads a second makes the cache and sharding essential; 30 TB definitely needs sharding. Seven characters are still plenty (1.7% used).
3. 3,844 = 62², so it's "1 followed by two zeros" in base62: encode(3844) = 100, just like 100 = 10² in base 10. And 3,843 = 61 × 62 + 61 = ZZ, the largest 2-character code.
4. Store the alias as the key, exactly like a generated code (the mini project does this). Things to handle: the alias may already be taken (refuse, or suggest another); it may collide with a future generated code (skip that generated code, or reserve a separate format, e.g. aliases must contain a dash, or generated codes are always exactly 7 characters and aliases may not be); validate characters and length; block offensive or brand-impersonating names; rate-limit alias creation so nobody grabs every good name.
5.
links_per_year = 100_000_000 * 12 # our assumption: 100 million a month
for length in (6, 7, 8):
codes = 62 ** length
print(f"{length} chars: {codes:>18,} codes, enough for {codes / links_per_year:,.0f} years")
Output:
6 chars: 56,800,235,584 codes, enough for 47 years
7 chars: 3,521,614,606,208 codes, enough for 2,935 years
8 chars: 218,340,105,584,896 codes, enough for 181,950 years
Six characters would actually be enough for 47 years at our assumed rate; seven gives a big safety margin if traffic grows 10× or 100×, and the scramble needs a fixed code space chosen up front.
6.
hot_links = 1_000_000 # assumption: cache the hottest million
bytes_per_link = 500 # same assumption as the estimate
print(f"cache memory: {hot_links * bytes_per_link / 1e6:,.0f} MB")
reads_per_second = 3_858
for hit_rate in (0.80, 0.95, 0.99):
print(f"hit rate {hit_rate:.0%}: database reads {reads_per_second * (1 - hit_rate):,.0f} per second")
Output:
cache memory: 500 MB
hit rate 80%: database reads 772 per second
hit rate 95%: database reads 193 per second
hit rate 99%: database reads 39 per second
Half a gigabyte fits in one server's memory. The hit rate (the share of reads the cache answers) is an assumption too; measure it in production. Every extra percent of hits takes load off the database.
7. M = 62^7 = 2^7 × 31^7, so P is coprime with M exactly when P has no factor 2 and no factor 31. If P shared a factor, two different ids would land on the same code (see the even-P mistake) and no inverse would exist. P = 31 × 1,000,001 would not work: it's a multiple of 31, so ids n and n + M/31 would collide, and pow(P, -1, M) raises ValueError: base is not invertible for the given modulus.
8. (a) 301: the move is forever, browsers caching it is good (less load), and per MDN search engines attribute links to the old URL to the new one. (b) 302: the target changes each month, and a cached 301 could keep sending browsers to last month's page. (c) 302: marketing needs every click counted, and the link should expire after the sale.
9. At most 999 per restart (a crash right after taking a fresh block), so at most 50 × 999 = 49,950 a day, about 18 million a year. Against 3.5 trillion codes that's about 0.0005% a year: it doesn't matter. Smaller blocks waste less but mean more trips to the counter; 1,000 is a comfortable middle.
Quick quiz
# Short codes use base62 (0-9, a-z, A-Z).
# How many different codes can
# 6 characters make?
- A. 62 × 6 = 372
- B. 6 ^ 62
- C. 62 ^ 6 ≈ 56.8 billion
- D. 16 ^ 6 ≈ 16.8 million
Answer
C. 62^6 ≈ 56.8 billion. Each of the 6 positions has 62 choices, so 62 × 62 × ... six times = 62^6 = 56,800,235,584 codes. A (62 × 6) adds the choices instead of multiplying them; B has base and exponent swapped; D, 16^6 = 16,777,216, is the number of 6-character hex codes, our cut MD5 hash: far fewer.
Interview questions: a design walkthrough
"Design a URL shortener" is a classic system design interview question. Here's how to walk through it in the order the episode followed, and what to say at each step.
- Clarify the requirements (2-3 minutes). Functional: shorten a long URL to a short code; redirect a code to its URL; optionally custom aliases, expiry, click analytics, user accounts. Non-functional: redirects in a few milliseconds, never return the wrong URL, highly available (links live in messages that can't be changed), and abuse-resistant. Say out loud: "This is read-heavy."
- Estimate (2-3 minutes). State assumptions, then compute: 100 million new links a month → ~39 writes/s; 100 reads per write → ~3,900 reads/s; 5 years → 6 billion links; 500 bytes each → 3 TB. Conclusion: writes are easy, reads need a cache, storage needs sharding eventually, 7 base62 characters (3.5 trillion) are plenty.
- API.
POST /shorten {url, alias?, ttl?}→{short_url};GET /{code}→ 302 withLocation, or 404. (An API, application programming interface, is the set of requests a service accepts.) - How to generate codes (the core question). Option 1: hash and cut, simple and stateless but collides (292 in 100,000 at 6 hex chars; birthday paradox), so it needs check-and-retry. Option 2: counter + base62, unique by design, no extra lookups. Option 3: random codes plus a uniqueness check, unguessable but needs the check. Choose the counter, then fix its two problems: - One counter is a bottleneck and single point of failure → id blocks per server; gaps are acceptable. - Sequential codes can be enumerated → reversible shuffle (multiply by a P coprime with 62^7, modulo 62^7; undo with the modular inverse), or random codes for private links.
- Data model and storage. One table/collection:
code → {long_url, created, expires, owner}. Access is only by exact code, so a key-value store; shard by code (scrambled codes spread evenly). Replicate for availability. - The redirect path. Load balancer → app server → cache → store. Cache hot codes (links rarely change; invalidate on delete/expire). 301 vs 302: 301 is cached by browsers (less load, but no click counts and no changes); 302 reaches us every time (analytics, expiry). Pick based on requirements: with analytics, 302.
- Analytics. Don't count synchronously in the redirect; put a click event on a queue and let workers aggregate counts.
- Abuse and edge cases. Rate limit
shortenper user/IP; validate URLs; same long URL twice → a new code each time is fine (or deduplicate per user by looking up the URL, which needs a second index); expired links → 404; reserved words that can't be aliases. - Trade-offs and follow-ups. What if the cache dies (the store must handle the burst; warm the cache)? How do you delete a link that a browser cached as a 301 (you can't, which is one more reason for 302)? How does the counter database stay available (replicate it; it's touched only once per block)?
Short questions you might also get:
- Why not just use the MD5 hash? (Cut short, it collides early: about n²/2N collisions; at full 32 characters it's too long.)
- Why base62 and not base64? (Base64 adds two symbols such as
+and/that have special meanings in URLs; base62 uses only letters and digits.) - How many characters do you need? (Enough that 62^k comfortably exceeds the links you'll ever store: 7 gives 3.5 trillion vs 6 billion estimated.)
- Is a scrambled counter code secure? (No, only hard to guess by counting; private links need long random codes or a login.)
- Why is this read-heavy and what does that change? (100 clicks per link: optimise redirects first, cache, replicate reads.)
Glossary
| Term | Meaning |
|---|---|
| URL | Uniform Resource Locator: a web address, e.g. https://chainow.in/menu |
| URL shortener | A service that maps a long URL to a short one and redirects to it, e.g. chai.nw/q0U |
| Short code | The few characters after the short domain that identify a link, e.g. q0U |
| Custom alias | A short name the user picks instead of a generated code, e.g. chai.nw/diwali |
| SMS | A short text message sent to a phone; in our story it holds 160 characters |
| Crore | An Indian number word: 1 crore = 10 million, so 2 crore = 20 million |
| Redirect | Sending a browser from one URL to another |
| HTTP | HyperText Transfer Protocol: the rules browsers and servers use to talk |
| Status code | The 3-digit number at the start of every HTTP answer, e.g. 302, 404 |
| Header | Extra named information sent with an HTTP message, e.g. Location: ... |
| Location header | The header that tells the browser which URL to go to after a redirect |
| 301 Moved Permanently | Permanent redirect; browsers cache it, so later taps skip our server |
| 302 Found | Temporary redirect ("a detour"); the browser asks us every time, so we can count clicks |
| 404 Not Found | The answer when a short code doesn't exist (or, in our design, has expired) |
| Cache-Control | The HTTP header that tells browsers how long they may keep a copy of a response |
| Search engine | A website that indexes pages so people can search them; follows 301s to the new URL |
| Requirement | Something the system must do or be |
| Functional requirement | What the system does, a feature, e.g. "shorten a URL" |
| Non-functional requirement | How well it does it, e.g. "redirect in a few milliseconds", "always up" |
| Read / write | Here: a redirect (looking up a code) / saving a new short link |
| Read-heavy | Serving far more reads than writes, e.g. 100 clicks per link |
| Back-of-the-envelope estimate | A quick rough calculation from stated assumptions, to learn the size of a problem |
| Assumption | An input you guess and say out loud, e.g. "100 million links a month" |
| Byte | One unit of storage, roughly one character of plain text |
| TB (terabyte) | 10^12 bytes; 6 billion links × 500 bytes = 3 TB |
| ms (millisecond) | One thousandth of a second |
| Viral link | A link shared so widely it gets a huge burst of clicks |
| Hash / hash function | Turns any input into a fixed-size jumble; same input, same output; e.g. MD5 |
| MD5 | A well-known hash function: 128 bits, written as 32 hex characters |
hexdigest() |
The hashlib method that returns the hash as hex text |
| Hex | Base 16: digits 0-9 and letters a-f |
| Collision | Two different inputs getting the same output, e.g. two URLs, one short code |
| Birthday paradox | With just 23 people, two probably share a birthday (50.7%); collisions come much sooner than you'd expect |
| n²/2N | Expected number of collisions for n items among N possible codes (298 for 100,000 in 16.7 million) |
| Check and retry | Fixing hash collisions by looking up each new code and re-hashing on a clash |
random.seed |
Fixes Python's random numbers so a program gives the same output every run |
| Counter | A number that goes up by one each time it's used; gives unique ids |
| Id | A number that identifies one item, e.g. link 100,000 |
| Base | How many digit symbols a number system uses: 10 for decimal, 16 for hex, 62 for base62 |
| Base62 | Writing numbers with 62 symbols (0-9, a-z, A-Z), e.g. 1,000,000 = 4c92 |
| Base64 | A 64-symbol encoding that adds characters like + and /, awkward in URLs |
| Encode / decode | Number → short code / short code → number |
| Round trip | Encoding then decoding gives back the original, e.g. decode(encode(n)) == n |
divmod(a, b) |
Python function giving the quotient and remainder at once |
Remainder / modulo (%) |
What's left after dividing, e.g. 125 % 62 = 1 |
| Recursion | A function calling itself, e.g. encode(n // 62) inside encode |
| App server | A machine running the service's code, behind a load balancer |
| Load balancer | Spreads incoming requests across many servers (episode 6) |
| Bottleneck | The one part that limits the speed of the whole system |
| Single point of failure | One part whose failure stops the whole system |
| Id block | A range of ids (e.g. 1,000) handed to one server at once, used from memory |
| Gap (in ids) | Ids that are never used, e.g. the rest of a block when a server crashes |
Iterator / next() |
An object that hands out the next value each time you call next() on it |
global |
Python keyword: inside a function, use the variable defined outside it |
| Replication | Keeping copies of data on several machines so one failure doesn't lose it (episode 11) |
| Enumeration | Trying every value in order, e.g. q0U, q0V, q0W, to find other people's links |
| Scramble / shuffle | Rearranging ids into codes that look unrelated, without repeats |
| Permutation | A rule that sends every input to a different output, using every output once |
| Modular arithmetic | Arithmetic that wraps around at a number M, like a clock at 12 |
| Coprime | Two numbers with no common factor except 1, e.g. P and 62^7 |
| Greatest common divisor (gcd) | The largest number that divides both; coprime means gcd = 1 |
| Modular inverse | The number that undoes multiplying by P modulo M: P × P_INV leaves remainder 1; pow(P, -1, M) |
| Cache | A small, fast copy of the most-used data, kept close to the servers (episode 7) |
| Hit rate | The share of reads the cache answers without the database |
| LRU | Least recently used: a cache rule that throws out the item used longest ago |
OrderedDict |
A Python dictionary that remembers order; used for LRU |
| Key-value store | A database that stores values under keys and finds them by exact key, like a big dictionary |
| Sharding / shard | Splitting data across machines by key; each machine is a shard (episode 12) |
| Queue | A waiting line of messages processed later by other programs (episode 16) |
deque |
Python's double-ended queue, fast at both ends; our stand-in for a message queue |
| Event | A small record of something that happened, e.g. (code, time) for a click |
| Analytics | Counting and studying events, e.g. clicks per link |
| TTL / expiry | Time to live: how long a link stays valid before it expires (404) |
| Rate limit | A cap on how many requests one user may make in a time window (next episode) |
| Regular expression | A text pattern, e.g. [A-Za-z0-9-]{3,30} |
| API | The set of requests a service accepts, e.g. POST /shorten, GET /{code} |
ValueError |
Python's error for a value with the wrong content, e.g. ALPHABET.index("-") |
UnboundLocalError |
Python's error for reading a local variable before it's assigned |
Summary
- Start every design with requirements: functional (shorten, redirect) and non-functional (fast, never wrong, always up), and notice it's read-heavy.
- Do a back-of-the-envelope estimate from stated assumptions: 39 writes/s, ~3,900 reads/s, 6 billion links, 3 TB in 5 years. Writes are easy; reads need a cache.
- Hashing and cutting collides early because of the birthday paradox (292 collisions in 100,000 links with 16.7 million codes; about n²/2N).
- A counter written in base62 is unique by design; 7 characters give 3.5 trillion codes.
- Id blocks remove the counter bottleneck: each server asks once per 1,000 links; gaps after crashes are fine.
- Counter codes are guessable; a reversible shuffle (multiply by P coprime with 62^7, modulo 62^7, undone by the modular inverse) keeps them unique and scattered. Hard to guess is not secret.
- 302 reaches us on every tap (click counts, expiry); 301 is cached by browsers (less load). ChaiNow uses 302.
- The design: load balancer → app servers → cache → key-value store (sharded by code), with clicks sent to a queue for analytics, and a rate limit on shortening.
- Follow the order requirements → estimate → design → trade-offs in every design interview.
Next episode: a spammer just found our free shortener and is making a million links an hour. We design a full rate limiter service: rules, race conditions, and what to do when its own database goes down.
Sources: MDN Web Docs, "301 Moved Permanently" ("the requested resource has been permanently moved to the URL in the Location header"; "A browser receiving this status will automatically request the resource at the URL in the Location header"; search engines "attribute links to the original URL to the redirected resource"; 302 Found is the temporary redirect); http.dev, "301 Moved Permanently" ("Browsers cache 301 responses aggressively based on Cache-Control directives"; without explicit cache headers "the redirect persists in browser cache indefinitely"; 302 is "a detour"). All estimate inputs are our own assumptions.