Design a URL Shortener: A System Design Interview Walkthrough

The URL shortener is the warm-up question of system design interviews, and it is easy to answer badly by answering too much. The whole design follows from two facts: reads outnumber writes by a wide margin, and every read is a lookup by one exact key. Get those on the board first and the rest of the diagram draws itself.

The problem it solves

A user submits a long URL and gets back a short link like /7Ke3xR. Anyone who opens the short link is redirected to the long one. Optional extras — custom aliases, expiry dates, click counts — come later, and only if the interviewer asks.

Put numbers on it before drawing anything. Assume 100 million stored links and a steady 500 redirects a second against 5 new links a second. Five writes a second is 432,000 new links a day, about 158 million a year. If a row — key, long URL, owner, timestamps — averages 500 bytes, 100 million rows is 50 GB. Those numbers are assumptions, not measurements; the point of saying them is to show that the data fits comfortably on a small cluster, and that the read path is what needs care.

The intuition

Split the system into its two paths and design each for its own load.

The write path turns a long URL into a key, stores one row, and returns the link. At a handful of writes a second, its only real question is how to choose the key.

• A counter, encoded in base62. Each new link takes the next integer and writes it with the 62 characters 0-9a-zA-Z. Keys are as short as possible and never collide. The price: keys are sequential, so they reveal how many links exist and let anyone enumerate them, and every writer has to share one sequence. The usual fix for the shared sequence is to hand each server a block of numbers at a time.
• A random key. Seven random base62 characters hide the volume and need no coordination, but two writes can pick the same key, so every write must check for an existing row and retry on a clash.
• A hash of the long URL. Truncating a hash maps the same long URL to the same key, which deduplicates for free — and also means two users cannot have separate links, with separate click counts, for one URL. Truncation makes collisions possible, so it still needs the check.

The read path is one lookup by exact key, hundreds of times a second, with most traffic landing on a small set of popular links. That is the textbook case for a cache in front of a key-value store: nothing relational, no joins, one access pattern.

Watch it run

A write arrives, the key generator issues the next counter value as 7Ke3xR, one row is written, and the short link goes back. Then the reads start: the first misses the cache and is answered by the store, and later hits are answered from the cache. Watch the last frames, where a 301 would stop clicks reaching you at all and the counter's weakness is named.

The code

The key logic is small enough to write in the interview. The block below encodes and decodes counter values, draws a random key, and computes the numbers that decide the key length:

import secrets
import string

ALPHABET = string.digits + string.ascii_letters     # 62 symbols, URL-safe
BASE = len(ALPHABET)

def encode(n):                   # counter value -> short key
    if n == 0:
        return ALPHABET[0]
    out = []
    while n:
        n, r = divmod(n, BASE)
        out.append(ALPHABET[r])
    return "".join(reversed(out))

def decode(key):                 # short key -> counter value
    n = 0
    for ch in key:
        n = n * BASE + ALPHABET.index(ch)
    return n

def random_key(length=7):        # the other option: no order, no leak
    return "".join(secrets.choice(ALPHABET) for _ in range(length))

print(encode(125), decode("21"))              # 21 125
print(encode(100_000_000))                    # 6LAze
print(BASE ** 5, BASE ** 7)                   # 916132832 3521614606208
print(100_000_000 / BASE ** 7)                # 2.839606577724809e-05
print(len(random_key()))                      # 7

Read the last three lines as the key-length decision. With a counter, five characters already cover 916 million links, so the hundred-millionth link is the five-character 6LAze. With random keys, the question is instead how often a new key lands on a used one. With 100 million links in a seven-character space, that chance is about 0.003% per write — roughly one retry per 35,000 writes. The uniqueness check stays, but retries are rare.

Both claims are tested. encode is compared with a brute-force listing of every key in order, the round trip is checked on random numbers, and the collision estimate is measured in a deliberately tiny three-character space where clashes are common enough to count:

import itertools
import random

def keys_in_order():             # brute force: every key up to 3 characters
    yield ALPHABET[0]
    for length in (1, 2, 3):
        for first in ALPHABET[1:]:            # no leading "0", like numbers
            for rest in itertools.product(ALPHABET, repeat=length - 1):
                yield first + "".join(rest)

print(all(encode(i) == key for i, key in enumerate(keys_in_order())))  # True

random.seed(8)
print(all(decode(encode(n)) == n for n in
          (random.randrange(10 ** 15) for _ in range(20000))))       # True

space, links, trials, hits = BASE ** 3, 2000, 200, 0
for _ in range(trials):
    used = set()
    for _ in range(links):
        key = random.randrange(space)
        hits += key in used
        used.add(key)
print(round(hits / (trials * links), 5))      # 0.00431  measured
print(round((links - 1) / 2 / space, 5))      # 0.00419  predicted

The complexity

Both paths are constant work per request: encoding is proportional to the key length, and every read is one cache lookup plus, on a miss, one key-value lookup. The capacity questions are the ones worth talking about. The store holds tens of gigabytes under the assumptions above, and the cache only needs the popular fraction of keys. Writes are so rare that the counter's shared sequence is a design question rather than a throughput problem.

Where it goes wrong

• Answering with 301. A 301 is permanent, and browsers may cache it without asking you again. Later clicks then never reach your servers, so the click counts stop. A 302 is not cached by default, so each click comes back through you. Choose 301 only if you truly do not need to see the traffic.
• Counting clicks inline. Writing to a counter row on every redirect puts a write on the hot read path. Publish a click event and aggregate it elsewhere.
• Sequential keys in public. Anyone can walk /1, /2, /3 and read every link. If links can be private, use random keys.
• Custom aliases in a separate namespace. A user-chosen alias must be checked against the same table as generated keys, or a future counter value will collide with it.

How to say it in an interview

"It's read-heavy — I'll assume a hundred to one — and every read is a single lookup by key, so a key-value store with a cache in front is the natural fit. For keys I'd use base62: a counter gives the shortest keys but leaks volume and needs a shared sequence, random seven-character keys hide volume at the cost of a uniqueness check. I redirect with 302 so every click still reaches me, and I publish clicks asynchronously instead of writing on the read path."

Then stop and let the interviewer choose where to go deeper — key generation, caching or analytics. For the caching layer itself, see designing a distributed cache.