Design a URL shortener

Interview 1: Design a URL shortener

We run the lesson 9-2 script, start to finish.

Step 1, requirements. Functional: given a long URL, return a short one, and redirect anyone who visits it. Non-functional: redirects must be fast (they sit in front of every click) and highly available. Out of scope after asking: custom aliases, analytics dashboards.

Step 2, estimation. Assume 100 million new URLs per month and a 100:1 read-to-write ratio.

• Writes: 10⁸ / month ≈ 40 per second average. Tiny
• Reads: 4,000 per second average, maybe 20,000 at peak. Read-heavy, exactly what unit 3 caches love
• Storage: 10⁸ URLs × 500 bytes ≈ 50 GB per year. One database easily holds a decade

Conclusion, said out loud: this is a small-write, huge-read system. One SQL leader with replicas plus an aggressive cache. No sharding needed for years.

Step 3, API and data model

Two endpoints:

POST /shorten   body: {"url": "https://long..."}   returns {"code": "xK9fQ2p"}
GET  /<code>    responds 301 redirect to the long URL

One table: links(code PRIMARY KEY, long_url, created_at). The interesting question is the code. Use base62: the 62 characters a-z, A-Z, 0-9. Each character multiplies the keyspace by 62, so length 7 gives 62⁷ possible codes.

To generate codes without collisions, keep a global counter (or ranges of IDs handed to each server) and convert each number to base62, the same way binary converts numbers to base 2. Every ID maps to a unique short string, no collision checking needed.

The keyspace calculator

How many codes each length allows, which is the step-3 math an interviewer expects on the spot.

for length in range(5, 9):
    print(length, "characters ->", 62 ** length, "possible codes")

Output

5 characters -> 916132832 possible codes
6 characters -> 56800235584 possible codes
7 characters -> 3521614606208 possible codes
8 characters -> 218340105584896 possible codes

62⁷ is about 3.5 trillion, which is comfortably more than any URL shortener will ever store. At the estimate's 100 million URLs a month, that is thousands of years of headroom.

Each extra character multiplies the total by 62, and reading down the column shows how fast that compounds. Five characters gives under a billion, which is genuinely too few, and two more characters gives 3,800 times more.

Six characters at 56 billion would also work for this product, and the choice between 6 and 7 is a judgment about growth versus link length. Picking 7 costs one character and removes the question permanently.

Note the assumption that makes sequential codes acceptable, which is that these links are not secret. Codes derived from a counter are guessable, so anyone can enumerate them, and a shortener used for private documents needs random codes instead.

That is a real tradeoff worth naming aloud. Counter-based codes are collision-free with no lookup, and random codes require a uniqueness check on insert, so the security requirement decides which cost you pay.

Steps 4 and 5, architecture and deep dive

The redirect path is the unit 1 anchor grown with everything you learned:

1. GET /xK9fQ2p hits the load balancer (unit 2), then any stateless app server (lesson 2-3)
2. The server checks Redis with cache-aside (lesson 3-2). Popular links are nearly always hits, and links never change, so staleness is a non-issue: cache forever with a long TTL
3. On a miss, read the database by primary key (indexed, lesson 4-1), from a read replica (lesson 4-3), and fill the cache
4. Respond with a 301 redirect, total time a few milliseconds

Writes take the boring path to the leader. Deep-dive favorite: a viral link is a hot key (lesson 5-2), and the cache is already the answer.

Notice what we did not use: no shards, no queues, no microservices. Matching the machinery to the numbers is the win.

The durability check

How long 62⁷ codes last at a thousand new URLs per second.

codes = 62 ** 7
new_urls_per_sec = 1000
seconds_per_year = 31_536_000
years = codes / new_urls_per_sec / seconds_per_year
print("Codes available:", codes)
print("Years until we run out:", round(years))

Output

Codes available: 3521614606208
Years until we run out: 112

A hundred and twelve years is the answer that closes the question. It is far enough out that no design decision depends on it, which is exactly what you want a capacity check to conclude.

Note how conservative the input is, and say so in an interview. A thousand per second is 25 times the estimated write rate from step 2, so the real figure is closer to 2,800 years, and the answer holds even if the product grows enormously.

seconds_per_year is 31,536,000, which is the 3.15 × 10⁷ constant from lesson 9-1 written out. Recognizing it saves recomputing 365 × 86,400 under pressure.

Chaining two divisions rather than multiplying the denominators first is deliberate, since each step is a quantity you can name. Codes divided by rate gives seconds of runway, and dividing by seconds per year converts it to a human unit.

The general habit here is worth more than the number. Any fixed-size identifier deserves this calculation, and it is the difference between choosing 7 characters for a reason and choosing it because another shortener did.

Why a shortener suits cache-aside with a very long TTL

Because a short link's target never changes, so cached entries cannot go stale.

The unit 3 invalidation problem exists only when data changes. A shortener's mapping is immutable, since once xK9fQ2p points somewhere it points there forever, so there is nothing to invalidate and no write path that has to remember to delete a key.

Immutable data is the perfect cache resident. No invalidation, no staleness, and hit rates near 100% for anything popular, which is the best possible version of the lesson 3-3 tradeoff because one side of it costs nothing.

The TTL exists for memory management rather than freshness, which is a useful reframing. Entries expire to make room for newer links rather than to stay correct, so the eviction policy from lesson 3-4 is doing the real work.

This is also why the hot key problem from lesson 5-2 is fully solved here. A viral link is one immutable value requested millions of times, which a cache and a CDN absorb entirely, so the database sees a single read.

Note that immutability is a design choice rather than a fact of the universe. Allowing users to edit a link's target would reintroduce invalidation, and declining that feature is what keeps this architecture as simple as it is.