Design a URL Shortener
TinyURL / Bit.ly — turn long URLs into short, unique, redirectable keys at read-heavy scale.
Overview
A URL shortener maps a long URL to a short alias and redirects users on lookup. It looks trivial but is the canonical warm-up: it forces you to reason about unique key generation, a read-heavy access pattern (100:1), caching, and storage growth — the building blocks of every larger design.
Requirements
Functional
- Given a long URL, return a unique short URL (7-character alias).
- Redirect a short URL to its original long URL (HTTP 301/302).
- Support optional custom aliases and expiration times.
- Track basic analytics (click counts) per short URL.
Non-functional
- Redirects must be low latency (< 100 ms) — this is the hot path.
- Highly available: a broken redirect breaks every link ever shared.
- Short URLs are not predictable/guessable.
- Read-heavy: ~100 reads for every write.
Back-of-the-envelope
The numbers that justify the architecture.
| New URLs / month | 100M | ≈ 40 writes/sec |
| Reads / month | 10B | 100:1 read:write ≈ 4,000 reads/sec |
| Storage / 5 years | ~1.5 TB | 100M/mo × 60 mo × 500 bytes/record |
| Keyspace | 62^7 ≈ 3.5T | base62 [a-zA-Z0-9]; enforce uniqueness with check-and-retry |
Reference architecture
A stateless redirect service fronted by a CDN/cache, a key-generation strategy, and a KV store optimized for point lookups.
Deep dives
Generating unique short keys
Two viable approaches. (1) Hash + encode: hash the long URL with a per-attempt salt, map the digest into the 62^7 keyspace, then base62-encode and left-pad to exactly 7 characters. Collisions are possible — use an atomic uniqueness check and retry with a new salt. (2) Key Generation Service (KGS): pre-generate random unique keys offline into a database and hand them out. KGS avoids collision checks on the hot path and guarantees uniqueness, at the cost of a new stateful service that must be highly available and must not hand out the same key twice (use two tables: available vs used, and load keys in memory batches).
Read path and caching
Redirects dominate. Put the short→long mapping behind Redis with an LRU policy; a cache hit is a memory lookup and a 301. Cache the 20% of links that get 80% of traffic. On a miss, read from the KV store and backfill. Because mappings are immutable once created, cache invalidation is trivial — the entry only leaves on expiry or eviction.
Use a 301 (permanent) redirect to let browsers cache and shed load, or a 302 (temporary) if you need every click to hit your server for analytics. That single choice is a real trade-off interviewers probe.
Storage choice
The access pattern is a pure point lookup by key with no joins — a wide-column or KV store (Cassandra, DynamoDB) is a natural fit and scales horizontally by partitioning on the short key. A relational DB works at the start but a single primary becomes the bottleneck; you'd shard by hash of the key anyway.
Key trade-offs
For each decision: the two options, and when to pick which.
Bottlenecks & follow-ups
Where it breaks under load — and what an interviewer will probe.
- ▲Single-DB write throughput → shard by key hash or use a horizontally scalable KV store.
- ▲Cache stampede on a viral link → request coalescing and a warm cache.
- ▲KGS as a single point of failure → replicate and pre-load key batches.
What a strong answer sounds like
- ✓Lead with the read:write ratio — it justifies caching and your storage choice.
- ✓Compute the keyspace out loud (62^7) to prove 7 chars is enough for years.
- ✓Name the 301-vs-302 trade-off; it signals you think about second-order effects.