SyntaxPilot
Courses/System Design/Lesson 27

System Design · Lesson 27 of 40 · 11 min

Design a URL shortener

queued

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

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**7 is 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, :,.0f means "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.
  • links is a dictionary from code to URL. If a code is already there for a different URL, that's a collision.
  • Notice links[code] = url then 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_shared multiplies 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 from ALPHABET, 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 True with the check at the end makes encode(0) return "0" instead of an empty string.

Reading the output:

  • 1 is 1, 61 is Z (the last symbol), and 62 is 10, 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 (c is 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:

  • encode is the same base62 as before, written recursively (the function calls itself for the higher digits): encode(n // 62) writes everything but the last digit, and ALPHABET[n % 62] adds the last one. % is modulo: the remainder after dividing.
  • next_block stands for the one shared counter in a database. take_block moves it forward by 1,000 and hands that whole range to one server. global next_block tells 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 call next() on it, and remembers where it stopped.
  • Each AppServer takes a block when it starts. Server a gets ids 0-999, server b gets 1,000-1,999.
  • + 100_000 just 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). Server b's first id, 1,000, becomes 101,000 = qh2.
  • links is 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 encode always writes exactly 7 characters (width=7), padding with 0 at the front: 0000q0U. All codes are now the same length.
  • M = 62^7, the number of 7-character codes. scramble multiplies 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). So unscramble(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

  1. 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).
  2. Hash and cut to 6 hex characters → 292 collisions in 100,000 links (birthday paradox: about n²/2N).
  3. Count + base62 → unique by design; 7 characters = 3,521,614,606,208 codes, 0.17% used.
  4. One counter, many servers → bottleneck and single point of failure → id blocks of 1,000 (q0U, qh2, q0V), gaps are fine.
  5. 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.
  6. 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. OrderedDict keeps items in order, move_to_end marks one as just used, and popitem(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 to oJfTb2w, the same as the SHUFFLE demo. Server b took the next block (101,000-101,999), so its first code qPUlD3a can never clash with a's.
  • Aliases and generated codes share one key space. An alias is checked before saving (alias taken: diwali), and _next_code skips 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 unknown zzzzzzz); 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 answers 404, '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: diwali has 501 (500 + the one printed). The redirect only appended an event; it never waited for counting.
  • Round trip: decoding oJfTb2w and unscrambling with P_INV gives 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

  1. Homework: in the HASHCUT demo, keep 8 characters instead of 6. How many collisions now?
  2. Homework: in the ESTIMATE demo, make it 1 billion new links a month. What changes?
  3. Homework: in the BASE62 demo, what is encode(3844)? Work it out by hand first.
  4. Homework: how would you add custom aliases (chai.nw/diwali)? What can go wrong?
  5. At our assumed 100 million links a month, how many years until 6-, 7- and 8-character codes run out?
  6. 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?
  7. Why must P be odd and not a multiple of 31? Would P = 31 × 1,000,001 work?
  8. 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.
  9. 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.

  1. 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."
  2. 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.
  3. API. POST /shorten {url, alias?, ttl?} → {short_url}; GET /{code} → 302 with Location, or 404. (An API, application programming interface, is the set of requests a service accepts.)
  4. 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.
  5. 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.
  6. 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.
  7. Analytics. Don't count synchronously in the redirect; put a click event on a queue and let workers aggregate counts.
  8. Abuse and edge cases. Rate limit shorten per 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.
  9. 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.