Designing a URL shortener

• Designing a URL shortener
  • 1. Requirements first
  • 2. The API
  • 3. Making the short code
  • 4. Storage
  • 5. Making redirects fast
  • 6. Growing
  • What interviewers look for

§Designing a URL shortener

This is one of the most common system design interview questions. Here is a simple way to walk through it.

§1. Requirements first

Ask before you draw anything:

• Functional: make a short link for a long URL; redirect a short link to the long URL.
• Non-functional: redirects must be fast; links must not collide; the service must stay up.
• Scale: how many new links a day, and how many redirects? Redirects are usually far more common than new links, so this is a read-heavy system.

§2. The API

• POST /links with the long URL returns the short code.
• GET /{code} answers with a redirect (HTTP 301 or 302) to the long URL.

§3. Making the short code

Give every link a unique number (an ID from the database or an ID service), then write that number in base 62 (0-9, a-z, A-Z). Seven base-62 characters give about 3.5 trillion codes.

const string chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
long id = 125;
var code = "";
do { code = chars[(int)(id % 62)] + code; id /= 62; } while (id > 0);
Console.WriteLine(code);

It prints 21, because 125 = 2 × 62 + 1. Using unique IDs means two links can never get the same code.

§4. Storage

A simple table: code → long URL, plus creation time. Reads by code must be fast, so the code is the key. A key-value store fits well.

§5. Making redirects fast

Put a cache in front of the database: most traffic goes to a small number of popular links. Links rarely change, so cached copies stay correct for a long time.

§6. Growing

• More app servers behind a load balancer; the servers keep no state.
• Shard the storage by code when one database is not enough.
• Replicate data so a failed server doesn’t lose links.

§What interviewers look for

Clear requirements, a simple design first, then the bottlenecks: the read load, the ID generation, and what happens when a part fails.

#tip · TIP-022