High Level Design
Designing a URL Shortener
End-to-end design of a URL shortening service — estimations, API design, 301 vs 302 redirects, hash functions with collision resolution, base62 encoding, and the deep-dive read/write paths.
A URL shortener takes a long URL and converts it to a short, manageable alias. When a user clicks the alias, they are redirected to the original URL.
Example: https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long → https://tinyurl.com/y7keocwj
Step 1: Requirements and Scope#
| Question | Answer |
|---|---|
| Traffic volume | 100 million URLs generated per day |
| Shortened URL length | As short as possible |
| Characters allowed | 0–9, a–z, A–Z (62 characters) |
| Delete or update? | No — simplified: URLs are immutable |
Functional Requirements#
- URL shortening — given a long URL, return a much shorter URL.
- URL redirecting — given a short URL, redirect to the original.
- High availability, scalability, and fault tolerance.
Estimations#
| Metric | Calculation | Value |
|---|---|---|
| Write operations | 100M / 86,400s | ~1,160 writes/sec |
| Read operations | 10× writes | ~11,600 reads/sec |
| URLs stored over 10 years | 100M × 365 × 10 | ~365 billion URLs |
| Storage per URL | 100 bytes long + 100 bytes short | ~200 bytes |
| Total storage | 365B × 200 bytes | ~73 TB |
Step 2: High Level Design#
API Endpoints#
URL Shortening:
POST /api/v1/shorten
Body: { "longUrl": "https://www.example.com/very/long/url" }
Response: { "shortUrl": "https://tinyurl.com/abc123" }
URL Redirecting:
GET /api/v1/{shortUrl}
Response: HTTP 301/302 redirect to the original long URL
URL Redirecting#
When a user clicks a short URL, the server resolves it and redirects.
Detailed communication flow#
301 vs 302 Redirect#
| 301 Moved Permanently | 302 Found (Temporary) | |
|---|---|---|
| Cached by browser? | ✅ Yes | ❌ No |
| Subsequent requests | Sent directly to long URL (bypasses shortener) | Always sent to shortener first |
| Server load | Lower — client caches | Higher — every click goes through shortener |
| Analytics | ❌ Loses click tracking | ✅ Full click tracking via shortener |
| Use case | Performance-focused, URL won't change | Analytics, A/B testing, changeable targets |
Data Model#
Most intuitive representation: hash table mapping <shortURL, longURL>.
GET longURL: longURL = hashTable.get(shortURL)
Redirect user to longURL
For production, use a relational database with columns: id, shortURL, longURL.
URL Shortening#
Short URL format: www.tinyurl.com/{hashValue}
We need a hash function f(longURL) → hashValue where:
- Each long URL maps to exactly one hash value.
- Each hash value can be mapped back to the long URL.
Step 3: Deep Dive#
Data Model#
Hash tables don't scale — memory is expensive and limited. Use a relational DB instead.
Hash Function#
Character set: [0–9, a–z, A–Z] = 62 characters.
Length of hashValue: find smallest n such that 62ⁿ ≥ 365 billion.
| n | 62ⁿ |
|---|---|
| 6 | ~56 billion — too small |
| 7 | ~3.5 trillion ✅ |
Two options: Hash + collision resolution or Base62 encoding.
Option 1: Hash + Collision Resolution#
Use MD5 or SHA-1, truncated to 7 characters.
| Hash | Output size | Suitability |
|---|---|---|
| CRC32 | 8 hex chars | ❌ Too small, high collision risk at scale |
| MD5 | 32 hex chars | ✅ Medium scale (millions of URLs) |
| SHA-1 | 40 hex chars | ✅ Large scale (billions of URLs) |
Collision handling: recursively append a predefined string until no collision is found.
Problem: repeated DB queries are expensive.
Solution: use a Bloom filter to check membership probabilistically before hitting the DB.
- Returns "definitely not present" or "possibly present" (with small false-positive rate).
- Avoids expensive DB lookups for the common case (URL not yet stored).
Option 2: Base62 Conversion#
Convert a unique numeric ID to a 7-character alphanumeric string using base62.
- Digits 0–9, A–Z (26), a–z (26) = 62 symbols.
- Example: ID = 11157 → base62 → 2TX
Result: https://tinyurl.com/2TX
Comparison: Hash vs Base62#
| Aspect | Hash + Collision Resolution | Base62 Conversion |
|---|---|---|
| Short URL length | Fixed (7 chars) | Grows with ID value |
| Unique ID required? | No | Yes |
| Collision possible? | Yes — must be resolved | No — ID is unique |
| Predictability | Not predictable | Next URL guessable if ID increments by 1 → security risk |
| Best for | Public-facing shorteners (bit.ly, TinyURL) | Enterprise/internal tools, low-security use cases |
URL Shortening: Deep Dive#
Using Base62 with a unique ID generator:
- longURL received as input.
- Check DB — if longURL already has a short URL, return it (idempotent).
- If new, generate a unique ID from the distributed ID generator.
- Convert ID to shortURL via base62.
- Store (id, shortURL, longURL) in DB.
- Return shortURL to client.
Canonicalization — before storing, normalize the URL to avoid duplicates from different representations of the same page:
- Parse the URL.
- Lowercase scheme and host.
- Remove default ports, trailing slashes, fragments.
- Sort query parameters.
- Compute a hash of the canonical form for idempotency checks.
URL Redirecting: Deep Dive#
Reads greatly outnumber writes (10:1) — cache the shortURL → longURL mapping in Redis.
- User clicks short URL.
- Load balancer forwards request to a web server.
- Web server checks Redis cache for the shortURL.
- Cache hit → return longURL immediately.
- Cache miss → query DB; return longURL (and populate cache for next time).
- If not in DB → invalid short URL.
Follow-Ups#
- Rate Limiting — prevent abuse from malicious clients flooding with shortening requests. Rate-limit by IP.
- Web server scaling — stateless tier; add/remove servers freely.
- Database scaling — replication for reads; sharding for write scale.
- Availability — CDN to cache mappings close to users globally.
- Analytics — track clicks, time of click, geography. Use 302 redirects so all requests flow through the shortener.
- Custom aliases — let users specify their own short URL; validate uniqueness and update schema.