Art of Codeartofcode
Lesson 7 of 15

31. Design a URL Shortener

1
The interview prompt
2
31.1 What do you ask first?
3
31.2 How big is this, really?
4
31.3 What are the doors?
5
31.4 What do we store?
6
31.5 What does the whole system look like?
7
31.6 How do you generate the short code?
8
31.7 301 or 302?
9
31.8 How do you keep redirects fast at 12,000 a second?
10
31.9 How do you count clicks without slowing redirects?
11
31.10 What would you say in the last five minutes?
12
Score yourself
13
Variations to practise
14
Sources
15
Code lab
31. Design a URL Shortener

31.6 How do you generate the short code?

3 min read+10 XP

Step 5: Deep dives (10 minutes)

Three options, each with real trade-offs.

counter with ID blocks vs hash of the URL vs random code.

Figure: three ways to make a code. Only the counter never collides; only random codes are unguessable without extra work.

31.6.1 Counter with ID blocks

Every new link gets the next number, written in base62 (Chapter 10). The problem is that one shared counter means every create goes to one place. The fix: a ticket server hands each app server a block of, say, 1,000 IDs at a time. The app server uses them up locally, then asks for the next block.

  • Never collides, by construction.
  • One call to the ticket server per 1,000 links, so it's never a bottleneck at 40 writes a second.
  • If an app server crashes with 600 unused IDs, those IDs are simply skipped. Gaps are fine; duplicates aren't.
  • Guessable: codes 1000, 1001, 1002 are neighbours, so anyone can walk through all links. Fix: scramble the number before encoding with a one-to-one mapping, for example (a × id + b) mod 62⁷ where a shares no factor with 62⁷. Every ID still maps to a different code, but neighbours no longer look alike. This hides the order. It is not encryption, so private links still need real access control.

31.6.2 Hash of the long URL

Hash the URL (for example SHA-256), write it in base62, keep the first 7 characters.

  • The same URL always gives the same code, so duplicates are free.
  • Cutting a hash short creates collisions. Two different URLs can share the same 7 characters. You must check on insert and, on a clash, add a salt and hash again.
  • If two users shorten the same URL, they share one code and one click count, which may not be what the product wants.

31.6.3 Random code

Pick 7 random base62 characters, insert, and let the primary key reject duplicates; on rejection, try again.

  • Unguessable, which matters if links can be private.
  • Clashes grow as the table fills, but at 6 billion links out of 3.5 trillion possible 7-character codes, the chance a new code clashes is under 0.2%, so retries are rare.

Our pick: counter with ID blocks, scrambled. It never collides, needs no read-before-write, and the ticket server is called once per 1,000 links. If the interviewer says "links may be private", switch to random codes with a primary-key check.

Interviewer pushback:

  • "What if the ticket server goes down?" → App servers still have the rest of their current block, so creates continue for a while. Run the ticket server as a single row in the primary database, updated with an atomic increment, or as two servers handing out odd and even blocks, so there's no single point of failure.
  • "Can't you just use the database's auto-increment?" → With one primary, yes, and it's a fine first version. Blocks matter once creates come from many servers or regions, or if we shard later (Chapter 10).

Memory code: "Count in blocks, scramble the order, never reuse a number."