Design a URL shortener

A URL shortener turns a long link into a short one, like sho.rt/aB3x9Kp.

Requirements and numbers

It makes short links and sends visitors on to the long URL. Clicks far outnumber new links, say 100 reads per write. A day has about 86,400 seconds, so 1 million new links a day is about 12 writes and 1,200 reads a second.

Short codes

Codes use base62: a-z, A-Z and 0-9, 62 characters. 7 characters give 62 to the power of 7, about 3.5 trillion codes. Two ways to pick one:

• Counter: turn the next number into base62. Codes never clash, but they come in order, so others are easy to guess.
• Random: pick 7 random characters and check the database. If the code is taken (a collision), pick again.

Data model

Each row maps a short code to a long URL, plus extras like the created time. Every click is one lookup by code, with no joins, so a key-value store fits well. The code is a unique key, so two links can never share one. To split the data across machines, split it by code.

The redirect

The server looks up the code and replies with a redirect. The long URL goes in the Location header.

• 301 means moved for good. The browser remembers it and may skip your server next time.
• 302 means moved for now. The browser asks you every time, so you can count every click.

An unknown code gets 404.

Scaling reads

A link almost never changes, so it is safe to cache. Keep popular codes in an in-memory cache. With a 95% hit rate, only 1 in 20 clicks reaches the database. A CDN can cache the redirect for very popular links at edges near users. Those clicks skip your servers, so count them from the CDN's logs.

Remember

• Clicks far outnumber new links; design for fast reads.
• 7 base62 characters give about 3.5 trillion codes.
• Each click is one lookup: code to long URL.
• Use 302 if you want to count every click.
• Cache popular links; they rarely change.