Design: a URL shortener

Start with numbers, not boxes

The mistake in every interview is drawing boxes first. Boxes are free; you can justify any of them. Numbers are not - they tell you which boxes you are allowed to skip.

So estimate out loud. Say 100 million new links a year. That's about 3 writes a second - nothing at all. But links are read far more than written, at maybe 100:1, so that's 300 reads a second, and reads arrive in spikes when something goes viral.

Now storage. A row is roughly 500 bytes: the short code, the long URL, an owner, a timestamp. 100 million rows is 50 GB a year. That fits on one machine with room to spare, for years.

That paragraph just eliminated sharding, and it eliminated it with arithmetic rather than opinion. Say that in an interview and you have already outperformed the candidate who opened with 'I'd shard by hash of the URL'.

links_per_year = 100_000_000
reads_per_write = 100
bytes_per_row = 500

writes_per_sec = links_per_year / (365 * 24 * 3600)
reads_per_sec = writes_per_sec * reads_per_write
storage_gb = links_per_year * bytes_per_row / 1e9

print(f"writes/sec  {writes_per_sec:.1f}")
print(f"reads/sec   {reads_per_sec:.0f}")
print(f"storage/yr  {storage_gb:.0f} GB")

writes/sec  3.2
reads/sec   317
storage/yr  50 GB

Generating the short code

You need a short, unique, URL-safe string. There are two honest approaches and one trap.

Hash the URL and take the first seven characters. Simple, and identical URLs collapse to one code - but hashes collide, so you must check for and handle collisions, and the check is a database read on every write.

Encode a counter in base62. The database's auto-incrementing id is already unique, so encode it in [0-9a-zA-Z] and you get a short code with no collision possible, ever. 62^7 is 3.5 trillion codes. This is the better default.

The trap is that sequential ids are guessable - anyone can walk your entire link database by counting. If links are private, that's a breach, and the fix is to encode a scrambled id rather than the raw one.

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encode(n):
    if n == 0:
        return ALPHABET[0]
    out = []
    while n:
        n, rem = divmod(n, 62)
        out.append(ALPHABET[rem])
    return "".join(reversed(out))

for db_id in (1, 1000, 100_000_000, 3_521_614_606_207):
    print(f"{db_id:>15,}  ->  {encode(db_id)}")

1  ->  1
          1,000  ->  g8
    100,000,000  ->  6LAze
3,521,614,606,207  ->  ZZZZZZZ

The redirect is the whole product

317 reads a second, each one a lookup by primary key, each one returning a row you could cache forever - because a short code's target never changes. This is the friendliest caching problem in existence.

So: cache-aside on the short code, with a long TTL. A hit is a memory read and a 301. Expect a hit rate well above 95%, because link traffic is brutally skewed - a handful of viral links carry most of the requests, which is exactly the shape caches love.

One decision has teeth. A 301 is a permanent redirect and browsers cache it, so repeat visits never reach you at all - the cheapest possible outcome, and you lose the ability to count those clicks or ever change the target. A 302 is temporary: every visit comes to you, so analytics work and links stay editable, at the cost of real traffic. Analytics usually wins, and that is why most shorteners use 302.

def redirect(code):
    url = cache.get(f"link:{code}")          # ~0.2 ms
    if url is None:
        url = db.query(                       # ~2 ms, by primary key
            "SELECT long_url FROM links WHERE code = %s", code
        )
        if url is None:
            return 404
        cache.set(f"link:{code}", url, ttl=86400)

    queue.push("record_click", code)          # analytics NEVER blocks (module 3)
    return 302, url

cache hit    0.2 ms   ~96% of requests
cache miss   2.2 ms   ~4%
click count  0 ms on the request path - a queued job