Designing a URL Shortener

Time to put everything together. A URL shortener (like TinyURL or bit.ly) sounds easy — "save a link and send people to it" — and that is exactly why interviewers love it. The hard part is making it work at huge scale, and every scaling choice uses an idea from an earlier chapter.

Step 1: Ask questions and estimate the size

Before you design anything, figure out what the system must do. A URL shortener might need to:

• Shorten a URL → return a short link
• Redirect: GET /abc123 → send the user to the original URL (301 or 302)
• Custom links (for example, /my-brand)
• Analytics (how many clicks, who clicked, from where)
• Expiry dates on links

Rough math (back-of-the-envelope)

Write side (100M URLs/day):

• Writes per second = 100M / 24 / 3600 = ~1,160 writes/sec
• 10 years of URLs = 100M × 365 × 10 = 365 billion records
• Each URL is about 100 bytes → total storage = 365 TB over 10 years

Read side (10 reads for every write):

• Reads per second = 1,160 × 10 = ~11,600 redirects/sec
• Cache memory: the most popular 20% of URLs cause 80% of the traffic → caching 20% of a day's URLs × 100 bytes ≈ 170 GB (fine for a Redis cluster)

Key length: We need short keys for 365 billion records using base62. Find the smallest n where 62ⁿ ≥ 365B. At n=7, 62⁷ ≈ 3.5 trillion — far more than enough. 7 characters is the answer.

What these numbers tell us: reads are far more common than writes (so a cache is a must), storage is 365 TB (so we must split the database), and 1,160 writes/sec is moderate (so one main database is fine to start).

Step 2: The two API calls

1. Write — POST /api/v1/data/shorten

   { "longUrl": "https://example.com/very/long/path", "expireAt": "2025-12-31" }

   Response: { "shortUrl": "https://tinyurl.com/abc123" }

2. Read — GET /abc123 Returns HTTP 301 Moved Permanently (the browser remembers the redirect) or 302 Found (the browser checks with us every time, which we need for analytics).

Step 3: Making the key — how to create abc123

Option A: Hash, then cut it short

Run the long URL through a hash (MD5 or SHA-256), take the first 7 characters, check that no one is using them, and if they are, try the next 7 characters.

Problem: when writes are heavy, checking for a clash means reading the database on every single write. At 40 writes/sec that is fine; at 10,000 writes/sec it becomes a traffic jam.

Bloom filter trick: Instead of asking the database on every write whether a key is taken, use a bloom filter — a small, memory-light structure that answers "has this key been used?" A bloom filter can be wrong in one direction only: it may say "used" when it actually was not (a false positive), but it will never say "free" when the key is taken. A false positive just makes you try the next 7 characters. The result is far fewer database reads while checking for clashes.

Option B: Counter that goes up by one + base62

Use a database counter that goes 1, 2, 3, … and encode that number in base62 → 1 → "1", 62 → "Z", 63 → "10". 7 characters covers up to 3.5 trillion URLs.

Problem: the keys are easy to guess in order — a competitor can walk through your whole database one number at a time.

Option C: Key Generation Service (KGS)

A dedicated service makes millions of random 7-character keys ahead of time and stores them in a "not used yet" table. When an API server needs a key, it asks the KGS, which hands one over and marks it used, all in one safe step.

Why it is good: no clash check needed when writing; it works across many servers (any API server can ask the KGS); and keys are random, so they cannot be guessed in order. If the table is small enough, the KGS can keep it in memory.

Generating IDs across many machines (Snowflake)

For really large scale, use a Snowflake ID: a 64-bit number built from a timestamp + a datacenter ID + a machine ID + a counter. Twitter invented this for tweet IDs, and it is guaranteed unique across machines without any of them having to coordinate. Because the shortener's base62 encoder needs a number to work on, where that number comes from is its own big question — important enough that Alex Xu gives it a whole chapter. The next section is that deep dive.

Generating the unique number

Base62 only changes a number into text — it does not invent the number. So the real question behind base62(id) → "zn9edcu" is: where does a unique, 64-bit number come from when you have many servers in many datacenters? A plain database auto_increment works on one machine but breaks when spread out: a single database is not big enough, and sharing one counter across machines adds delay on the busy path. Four common approaches come up — the first three have flaws, and one is the answer you want.

The usual rules an interviewer gives for this sub-problem: IDs must be unique, numbers only, fit in 64 bits, be sorted by time (so newer IDs are bigger), and the generator must keep up 10,000+ IDs/sec.

Multi-master replication

Use each database's auto_increment, but instead of going up by 1, go up by k = the number of databases. With two databases, one gives 1, 3, 5, … and the other gives 2, 4, 6, … — no clashes, and you get more throughput by adding more databases.

Why it loses: the IDs do not go up over time across servers (server-2's "4" might be made after server-1's "5"), so you cannot sort by time. It is awkward across datacenters, and adding or removing a server breaks the step math — you have to redo the whole counter setup.

UUID

A UUID is a 128-bit value (like 09c93e62-50b4-468d-bf8a-c07e1040bfb2) that each server makes on its own, with no coordination — so there are no syncing problems and it scales easily with the web tier. The chance of two being the same is tiny: per Wikipedia, you would need to make 1 billion UUIDs a second for about 100 years to have a 50% chance of a single duplicate.

Why it loses for this problem: it is 128 bits, not 64; it is not sorted by time; and it is not a plain number, so base62-encoding it would make a short URL far longer than 7 characters.

Ticket server (Flickr)

A single database whose only job is to hold one shared counter — every app server asks the ticket server for the next number. Flickr made this popular. Good points: the IDs are plain numbers and it is very simple to build for small or medium scale.

Why it loses: the one ticket server is a single point of failure — if it dies, everything that depends on it stops. You can run more than one ticket server to fix that, but then you are back to syncing problems between them.

Twitter Snowflake (the answer)

Snowflake avoids every flaw above by dividing the problem: instead of sharing one counter, it splits a 64-bit number into sections that each machine can fill in on its own. So every machine makes IDs by itself, yet the result is still unique everywhere and sorted by time.

 0 | 41-bit timestamp (ms since epoch) | 5-bit DC | 5-bit machine | 12-bit seq
sign|<--------------------------------->|<------->|<----------->|<----------->|

What each part does:

• Timestamp (41 bits, at the top) sits at the front of the number, so a bigger timestamp means a bigger ID — that is what makes Snowflake IDs sortable by when they were made. 2⁴¹ − 1 ms ≈ 69 years; picking a start date near today pushes the "running out" point far into the future. Twitter's default start is 1288834974657 (Nov 04 2010 UTC).
• Datacenter + machine IDs (5 + 5 bits) are set once at startup and never change. They make every machine's IDs unique with no coordination at runtime — but changing these by accident can cause clashes, so they are treated as carefully-reviewed settings.
• Sequence number (12 bits) goes up by one for each ID made in the same millisecond on one machine, and resets to 0 when the millisecond changes — letting one machine make up to 4096 IDs per millisecond (about 4M/sec) before it has to wait for the next millisecond.

A common follow-up is tuning the sections: the field sizes are a budget, not a rule. A service with low traffic but a long life can take bits from sequence and give them to timestamp for more years of room; a high-traffic service does the opposite.

Bringing it back to the shortener

Now the full create flow is clear: make a Snowflake ID → base62-encode it → save the <id, shortURL, longURL> row. For example, the ID generator might return 2009215674938; base62 turns that into "zn9edcu", and the short URL becomes https://tinyurl.com/zn9edcu. (Before making anything, the write path first checks whether the longURL already exists, so the same input reuses its old short URL instead of making a duplicate.) Snowflake is the right default here because its IDs are 64-bit, plain numbers (base62 likes that), need no coordination across your write servers, and are sorted by time — which also means short keys keep trending upward, a free bonus for analytics.

Step 4: The high-level design

Client → CDN / Edge → Load Balancer → API Servers → Cache (Redis) → DB (Sharded)
                                                          ↓ miss
                                                    DB Primary (writes)
                                                    DB Replicas (reads)

Write path: POST /shorten → API server → make a key → write to the main database → return the short URL. We do not write to the cache when creating (the cache fills up later, on the first read).

Read path: GET /abc123 → API server → check the Redis cache → if found: redirect. If not found → read a database replica → put it in the cache → redirect.

Step 5: Looking closer at each choice

301 vs. 302 redirect

Use 301 if you want the least server load. Use 302 if you need to count clicks. TinyURL uses 301; bit.ly uses 302 (counting clicks is their business).

Caching the read path

• Lots of reads → cache hard. Reads dwarf writes, so a cache in front of the database (Chapter 4, cache-aside) serves popular links straight from memory and keeps the database relaxed.
• A small cache covers a big share of the traffic: 20% of URLs often cause 80% of the clicks.
• TTL (how long to keep a cached item): set it to match the URL's expiry date (or a long default like 24h if there is no expiry).

Storage and sharding

• Lots of data → sharding. Billions of mappings will not fit on one database, so split them by the short key (Chapter 5). Since reads look things up by the short key, split on hash(short_key) for an even spread.
• Use the short key (not the user ID) to decide the split — 100% of read queries use it.
• SQLite, MySQL, and PostgreSQL all work; DynamoDB is a good managed option (partition key = short key).

Users around the world

• Global users → CDN + many regions. The redirect should be fast everywhere (Chapter 7). Put your API behind CloudFront or Cloudflare so edge servers can serve cached redirects from the CDN itself — the fastest possible path for popular URLs.
• Stay up → load balancer + replicas. No single machine should be able to take the whole service down (Chapters 2, 3, 5).

Analytics

If you need to count clicks:

• Send it off to the side: the redirect handler drops a click event onto Kafka, and a separate analytics service reads it. The important redirect path stays fast; the counting catches up a moment later.
• Counting: use Redis sorted sets for live counters, then save them to the analytics database in batches every minute.

URL expiry

• Keep an expire_at column in the database.
• On read: check if it has expired before redirecting; if it has, return 410 Gone.
• Cleanup: a background job deletes expired rows now and then (do not clean up while serving a read — that would slow the read down).

Rate limiting

Without rate limiting, one bad actor can use up all your keys or run up your storage bill:

• Token bucket per IP: allow short bursts, refill at a steady rate. Easy to build in Redis.
• Reply with 429 Too Many Requests and a Retry-After header.
• Logged-in users get higher limits than anonymous ones.

The whole picture

Work through this chapter and you have not just learned a toy problem — you have rehearsed the exact path of a real system design interview, from a simple first design to a scaled, cached, replicated, worldwide system.

Every choice points back to an earlier chapter:

Practice

Try these to check that the write and read paths make sense.