Designing a URL Shortener
A worked system design: requirements, back-of-the-envelope capacity numbers, base62 short codes with working code, how to avoid collisions, redirect status codes, caching and scaling.
A URL shortener maps a short code to a long URL and redirects visitors with an HTTP 301 or 302. The core design is a key-value store keyed by the code, codes made by encoding a unique counter in base62, and a cache in front because redirects vastly outnumber writes. Interviewers expect the 301 versus 302 trade-off.
A URL shortener maps a short code to a long URL and redirects visitors. The core design is a key-value store keyed by a short code, codes generated from a unique counter encoded in base62, a cache in front for the very read-heavy redirects, and a 301 or 302 response to send the user on.
- 100 million new short URLs per month is about 39 writes per second, and at a 100:1 read ratio about 3,900 redirects per second on average.
- Storing 6 billion URL records at about 500 bytes each, 100 million a month for 5 years, takes about 3 TB.
- A base62 short code of 6 characters has about 56.8 billion possibilities and a 7-character code has about 3.5 trillion.
- With a billion random 7-character base62 codes, the birthday problem gives about 140,000 expected colliding pairs, while a counter-based code has no collisions by construction.
- A 301 redirect is cached by browsers and cuts server load but loses click counts, while a 302 redirect sends every click back to the server for analytics and link changes.
01Requirements first
Functional requirements: given a long URL, return a short one. Visiting the short URL redirects to the original. Optionally, custom aliases, expiry and click analytics.
Non-functional requirements: redirects must be fast (tens of milliseconds) and highly available, because a dead redirect breaks every link ever shared. Short codes must be unpredictable enough not to be guessed in order, and must never collide.
In an interview, say these out loud and agree numbers before drawing boxes. Here the working assumption is 100 million new URLs per month, with 100 reads for every write.
02Back-of-the-envelope numbers
100 million writes per month is 100,000,000 / (30 x 86,400 seconds), about 39 writes per second. At a 100:1 read ratio that is about 3,900 redirects per second on average, and peaks might be several times higher.
Storage: if each record (code, long URL, timestamps, owner) takes about 500 bytes, then 100 million a month for 5 years is 6 billion records, about 3 TB. That fits on a modest cluster, but not on a single small disk.
These numbers show what matters. Writes are trivial. Reads are the load, and they are very cacheable, since a small fraction of links gets most of the clicks.
03Short codes: base62
Using 62 symbols (digits, lowercase, uppercase), a code of length L has 62^L possibilities. L=6 gives about 56.8 billion. L=7 gives about 3.5 trillion. Six characters would technically hold the 6 billion records we expect, but with random codes, collisions become frequent at that fill level (about 10% of the space), so seven is the safer choice.
To make a code from a number, write the number in base 62:
import string
alpha = string.digits + string.ascii_lowercase + string.ascii_uppercase
def encode(n):
if n == 0:
return alpha[0]
s = ''
while n:
n, r = divmod(n, 62)
s = alpha[r] + s
return s
def decode(s):
n = 0
for ch in s:
n = n * 62 + alpha.index(ch)
return n
print(encode(62)) # 10
print(encode(1_000_000)) # 4c92
print(encode(62**7 - 1)) # ZZZZZZZ
print(decode('4c92')) # 1000000The round trip works for every value I tested, including the largest 7-character code. This is the same idea as converting to hexadecimal, only with more symbols.
04Generating unique numbers
Option 1: random 7-character codes. It looks simple, but the birthday problem bites. With a billion codes stored in a space of 3.5 trillion, the expected number of colliding pairs is about n squared over 2N, roughly 140,000. You must check the database on every insert and retry on a clash, and the clash rate keeps rising as the table fills.
Option 2: a counter. Every new URL takes the next number and encodes it. No collisions by construction. The challenge is a counter shared by many servers. Common answers: a database sequence, a service such as ZooKeeper handing each app server a range of numbers (say 1 million at a time) so servers only coordinate once per range, or a Snowflake-style ID made from a timestamp, machine ID and sequence.
Counters produce predictable, sequential codes, so someone can walk through them and enumerate every link. If that matters, scramble the number with a keyed permutation or a block cipher before encoding, which keeps uniqueness and hides the order.
Option 3: hash the long URL and keep the first 7 characters. It gives the same code for the same URL (useful for deduplication) but needs collision handling again.
05Redirects: 301 or 302
The server answers a short URL with an HTTP redirect and a Location header.
301 Moved Permanently tells browsers and proxies the mapping is permanent, so they cache it and may never ask your server again. That cuts load, but you lose click counts and cannot change or expire the link for those clients.
302 Found (or 307) is temporary, so every click comes back to your server. That costs more traffic but gives accurate analytics and the ability to disable a link. Most shorteners that offer statistics use 302.
If an unknown code arrives, return 404. If a link has expired, return 410 Gone.
06Architecture and scaling
Write path: client sends POST /shorten with a long URL. The service validates it (scheme, length, optionally a safe-browsing check), takes the next ID, encodes it, stores code -> long URL, and returns the short URL.
Read path: GET /4c92. Look in a cache such as Redis first. On a miss, read from the database, store in the cache, and redirect. Since the same popular links are hit repeatedly, a cache with a modest size can serve most traffic, and an LRU eviction policy suits it.
Storage: the access pattern is a lookup by key, so a key-value or wide-column store (DynamoDB, Cassandra) or a sharded relational database all work. Shard by the code, with consistent hashing so adding nodes moves little data (see the load balancing topic).
Put a load balancer in front of stateless app servers, replicate the database for availability, and push the redirect closer to users with a CDN or edge nodes if latency matters globally. Count clicks asynchronously through a queue so analytics never slows a redirect.
Abuse is a real concern: rate limit creation per client, block known malicious domains, and let users report links.
07Common interview questions and trade-offs
Q: How many characters do you need?
A: Work back from the number of URLs. 6 billion over five years is about a tenth of 62^6 (56.8 billion), so 6 characters would fit, but a table that full makes random codes collide constantly. 7 characters (3.5 trillion) leaves plenty of room.
Q: Random codes or a counter?
A: A counter has no collisions but needs a coordinated ID source and produces guessable order. Random codes need collision checks. Many systems use a counter plus a reversible scramble.
Q: Why not just hash the URL?
A: Truncating a hash causes collisions, so you still need a check and a retry. It does help with deduplicating identical URLs.
Q: 301 or 302?
A: 301 for less load, 302 when you need analytics or the ability to change the link.
Q: How do you handle a viral link?
A: Cache it, and if needed replicate hot keys across cache nodes or serve from a CDN so one key does not overload one node.
Q: How do you support custom aliases?
A: Treat them as keys in the same table, check availability with a conditional insert, and reserve a separate namespace or length so they never clash with generated codes.