Design a URL Shortener (e.g. bit.ly)
EasyAsked at: Google, Amazon, Bloomberg
A service that converts long URLs into short aliases and redirects visitors from the alias to the original URL. The canonical 'first system design question' — great for practicing capacity estimation, key generation, and read-heavy caching.
Request flow
Functional Requirements
- Given a long URL, generate a short unique alias (e.g. sho.rt/abc123).
- Given a short alias, redirect (HTTP 301/302) to the original long URL.
- Optionally allow custom aliases and expiration dates.
- Basic analytics: click counts per link.
Non-Functional Requirements
- Redirection must be extremely low latency (it's on the critical path of every click).
- High availability > strong consistency (a slightly stale click counter is fine; a broken redirect is not).
- System should be read-heavy (~100:1 read:write is typical for these services).
- URLs should be unguessable/unique enough to avoid collisions at scale.
Capacity Estimation
- Assume 100M new URLs/month written ≈ 40 writes/sec average (bursty, plan for ~10x peak).
- With 100:1 read:write ratio, that's ~4,000 redirects/sec average.
- Store URL, alias, created_at, expiry, user_id, click_count → ~500 bytes/record. 100M/month * 5 years ≈ 6B records ≈ 3TB — easily shardable, not enormous.
- A 7-character base62 alias gives 62^7 ≈ 3.5 trillion combinations — plenty of headroom before collisions become a real risk.
Design Walkthrough
1. High-level architecture
Client → CDN/Load Balancer → API service (stateless) → Cache (Redis) → Database.
Write path: POST /shorten { long_url } → API generates/reserves a short code → writes {code, long_url} to DB → returns short URL.
Read path: GET /{code} → check cache for code→long_url mapping → on hit, redirect immediately; on miss, read DB, populate cache, then redirect.
2. Short code generation — the core design decision
Option A — Hash the long URL (MD5/SHA256) and take the first 7 chars, base62-encode: simple, but collisions are possible and must be handled (check-and-retry with a salt, or append a counter).
Option B — Base62-encode an auto-incrementing counter (e.g. from a dedicated ID-generation service or a DB sequence): guarantees uniqueness with zero collision-handling, but a naive global counter is a single point of contention at very high write throughput.
Option C — Pre-generate a large pool of random unique codes offline (a 'key generation service' — KGS) and hand them out to API servers in batches: removes the generation step from the write's hot path and avoids counter contention entirely. This is the interview-favorite answer because it elegantly sidesteps both collision handling and hot-counter contention.
3. Data storage
A simple key-value model fits perfectly: {short_code (PK), long_url, user_id, created_at, expires_at, click_count}. Any KV store or relational table with an index on short_code works — DynamoDB/Cassandra are natural fits at scale, or plain Postgres/MySQL for moderate scale with a shard-by-short_code strategy once one machine is insufficient.
Shard by hash(short_code) once the dataset outgrows one machine — the access pattern is always a point lookup by short_code, so this shard key gives perfectly even load with no cross-shard queries needed on the read path.
4. Making redirects fast
Cache the code→URL mapping aggressively (Redis, cache-aside) since reads vastly outnumber writes and the mapping is immutable once created (aside from expiry/deletion) — a perfect caching use case with no invalidation headaches.
Push a CDN in front of the redirect endpoint where possible, or at minimum ensure the API/cache tier is geographically distributed close to users.
Use HTTP 302 (temporary) rather than 301 (permanent) if you need every click to still hit your servers for analytics — a pure 301 lets browsers cache the redirect and you lose click data on repeat visits. This is a common interviewer follow-up.
5. Analytics & click counting
Don't synchronously increment a counter in the hot redirect path (adds write latency and DB contention on hot links). Instead, fire an async event (to a message queue) on each click and let a separate consumer batch-aggregate counts into the DB or a dedicated analytics store.
Bottlenecks & Mitigations
- A single global counter for ID generation becomes a write bottleneck — solved via a pre-generated key pool (KGS) handed out in batches per API server.
- Extremely popular short links (e.g. viral tweets) become hot keys — mitigate with aggressive caching plus, if needed, replicating that one hot key across multiple cache nodes.
Likely Follow-Up Questions
- How would you support custom, user-chosen aliases without breaking the uniqueness guarantee? (Unique index / conditional write on short_code, reject on conflict.)
- How would you expire and reclaim old/unused short codes? (Background sweeper job checking expires_at, return reclaimed codes to the KGS pool.)
- How would you prevent someone from shortening a malicious/phishing URL? (Async check against a URL-reputation/blocklist service before or shortly after creation, disable the link if flagged.)