Design a URL Shortener
2 min read
Design a URL Shortener (TinyURL / bit.ly)
The classic warm-up. It looks trivial but touches encoding, scale and caching.
1. Requirements
- Functional: shorten a long URL; redirect a short URL to the original; optional custom alias and expiry.
- Non-functional: highly available, low-latency redirects, short codes. Read-heavy (~100:1 reads:writes).
2. Estimation
- Assume 100M new URLs/month → ~40 writes/sec.
- Reads at 100:1 → ~4,000 redirects/sec.
- Storage: 100M/mo × 5 yr × ~500 bytes ≈ 3 TB. Trivial for modern DBs.
3. The core problem: generating short codes
Use a base62 alphabet [a-z A-Z 0-9]. With 7 characters: 62⁷ ≈ 3.5 trillion URLs — plenty.
Two approaches:
| Approach | How | Trade-off |
|---|---|---|
| Counter + base62 | Encode an auto-increment ID | Sequential, guessable, needs coordination |
| Hash (MD5/SHA) | Hash the URL, take first 7 chars | Collisions possible — check & retry |
A robust pattern: a distributed ID generator (e.g. a range-allocation service or Snowflake IDs) hands each app server a block of unique IDs, which are base62-encoded. No coordination on the hot path.
4. High-level design
Write: Client ─▶ LB ─▶ App ─▶ ID gen ─▶ DB (id → longURL)
Read: Client ─▶ LB ─▶ App ─▶ Cache ─▶ DB ─▶ 301 redirect
5. Data model
urls: id (PK) | short_code (unique) | long_url | user_id | created_at | expires_at
Key-value stores (DynamoDB, Cassandra) fit perfectly: look up by short_code.
6. Deep dives
- Caching: redirects are read-heavy and immutable — cache
short_code → long_urlin Redis with a long TTL. Huge hit rate. - Redirect type:
301(permanent) caches in browsers (fewer hits, but no analytics);302(temporary) lets you count every click. - Analytics: fire a click event to a queue → process asynchronously so redirects stay fast.
- Custom aliases: check uniqueness on write; reserve a separate keyspace.
Takeaway: the "hard" part isn't storage — it's generating unique short codes at scale without coordination, and serving reads from cache.