Design a URL shortener
Turn a long URL into a tiny one - base-62 encoding, hash collisions, and the read-heavy cache that makes the redirect instant.
9 min read
A URL shortener is mostly a giant lookup table from a short code to a long URL. The only real puzzles are how you invent the code, and what you send back when someone clicks it.
Hash the URL and keep the first seven characters?
The obvious approach is to hash the long URL and keep the first few characters. It is deterministic, it needs no shared state, and the same URL always gets the same code. It also collides, far sooner than intuition suggests.
This is the birthday problem. The question is not whether a new URL hits one particular code, but whether any two of a billion URLs share one, and there are about 5 × 1017 pairs to compare against 3.5 × 1012 codes. Collisions are the normal operating condition, so every write needs a lookup and a retry. You need about eleven characters before they stop mattering, and by then the short URL is not short.
Take a number nobody else will get, and write it in base 62
The alternative is to start from a number that is unique by construction, from a counter or an ID generator like the one in the previous lab, and write it in base 62: the digits 0-9, then a-z, then A-Z. Seven base-62 characters cover about 3.5 trillion URLs, and since each ID maps to exactly one code, collisions cannot happen at all.
The price is predictability. Consecutive IDs give consecutive codes, so anyone can walk the space and harvest every link people have shortened, which matters for a service people paste private documents into. The fix keeps the counter but scrambles it with a bijection, a reversible shuffle of the ID space, so codes stay collision-free but stop being neighbours. Old links never break: the code space only grows to the left.
Which redirect you return decides whether you hear from them again
The read path is one lookup and one HTTP status code, and the status code is not a detail. It decides whether the browser comes back to you on the next click, or goes straight to the destination from its own cache.
A 301 is the browser's licence to skip you next time, which is wonderful for your servers and fatal for the click counter that is usually the business. A 302 keeps every click coming through you, at the cost of serving all of them. Most shorteners choose 302, then make that lookup extremely cheap: a cache in front of the table, because the read-to-write ratio is enormous and a small set of popular links takes most of the traffic.
The short version
- Truncated hashes collide by the birthday problem long before the code space looks full.
- Base 62 of a unique ID gives seven-character codes for trillions of URLs with no collisions.
- Scramble the ID with a bijection so codes cannot be enumerated.
- 302 keeps analytics; 301 saves load. Cache the lookup either way.