Design a URL Shortener

A URL shortener takes https://example.com/very/long/path?with=params and hands back something like bit.ly/2dt1pnm. Two operations: shorten (write a mapping) and redirect (read it and forward the browser). The whole design is shaped by one fact — redirects vastly outnumber shortens, so this is a read-heavy system.

Requirements and back-of-envelope math

Suppose we shorten 100M new URLs/day and serve reads at a 100:1 read/write ratio — so ~10B redirects/day, or roughly 115K redirects/sec on average. Storage per mapping is small: a 7-char code, the long URL (~500 bytes), plus a little metadata ≈ 500 bytes. So 100M/day is about 50 GB/day, ~18 TB/year. For scale, Bitly's real system serves on the order of 360M redirects/day.

How short can the code be? base62 keyspace math

Short codes use base62 — the characters [a-z A-Z 0-9], 62 of them. A code of length L gives 62^L possibilities. Work it out: 62^6 ≈ 56.8 billion, and 62^7 ≈ 3.5 trillion. At 100M new URLs/day, 7 characters lasts 3.5e12 / 1e8 ≈ 35,000 days (~95 years). That is why 7 characters is the standard target — short enough to type, huge enough to never run out.

62^7 = 62 * 62 * 62 * 62 * 62 * 62 * 62 ≈ 3.52 x 10^12  (3.5 trillion)
3.5 trillion / 100 million per day ≈ 35,000 days ≈ 95 years of keys

Generating the code — KGS vs hashing

There are two textbook ways to mint a unique code, and the difference is all about collisions:

1. 1Hash the URL — take md5(longUrl) and keep the first 7 base62 chars. Simple, but two different URLs can hash to the same code (a collision). You must check the DB on every write and retry with a tweak — extra reads, and it gets slower as the table fills.
2. 2Key Generation Service (KGS) — pre-generate unique keys offline (e.g. count 1, 2, 3… and encode each in base62) and hand them out on demand. No collision check at write time because keys are unique by construction. The KGS just needs to mark a key 'used' and be replicated so it is not a single point of failure.
3. 3A base62-encoded counter guarantees uniqueness but makes codes sequential and guessable; hashing or a randomized KGS pool avoids that.

The redirect path — and 301 vs 302

A redirect looks up the code and returns an HTTP redirect. The status code is a real trade-off: 301 (permanent) is cacheable by browsers and CDNs, so repeat clicks may never touch your servers — fast and cheap, but you lose per-click analytics. 302 (temporary/found) forces every click back through you, so you can count it, at the cost of more load. A shortener that sells click analytics leans toward not caching redirects permanently.

POST /shorten   { "url": "https://example.com/long..." }  ->  201 { "code": "2dt1pnm" }
GET  /2dt1pnm                                             ->  301/302 Location: https://example.com/long...

-- link store (single-keyed, read-mostly) --
code  VARCHAR(7)  PRIMARY KEY
long_url  TEXT
created_at  TIMESTAMP
creator_id  BIGINT

That single-keyed, read-mostly, ever-growing shape is exactly what a wide-column store is built for. Bitly ran this on hand-sharded MySQL for years, then in 2023 migrated ~80B rows into Google Cloud Bigtable. Shortening stays synchronous (the same code must never be given to two people); click analytics is asynchronous — every click is published to a queue (Bitly's own NSQ) and processed later, so a user never waits on analytics.