📝 Problem Description
Design a URL shortening service like TinyURL or bit.ly that takes long URLs and creates much shorter aliases for them. When users access the short URL, they should be redirected to the original URL. This is a classic system design interview problem that tests fundamentals of distributed systems.
👤 Use Cases
1.
User wants to submit a long URL so that they receive a short, shareable link
2.
User wants to click on a short URL so that they are redirected to the original long URL
3.
User wants to create a custom short link so that they can use a memorable alias for their URL
4.
User wants to view analytics for their short URL so that they can see click counts, geographic data, and referrers
5.
User wants to set an expiration time so that the short URL becomes invalid after the specified time
✅ Functional Requirements
- •Given a URL, generate a shorter unique alias (short link)
- •When users access the short link, redirect to the original URL
- •Users should optionally be able to pick a custom short link
- •Links should expire after a configurable timespan
- •Track analytics: click count, location, device type
- •Users should be able to delete their short URLs
⚡ Non-Functional Requirements
- •System should be highly available (URL redirection should not fail)
- •URL redirection should happen in real-time with minimal latency (<100ms)
- •Shortened links should not be predictable (security)
- •System should handle 100M URL shortenings per month
- •The system should be scalable to handle billions of redirects
⚠️ Constraints & Assumptions
- •Short URLs should be 7 characters or less (excluding domain)
- •URLs must be unique - no collisions allowed
- •System must support 1000+ write requests per second
- •Read-to-write ratio is approximately 100:1
- •Short URLs cannot be reused after deletion (for security)
- •Maximum original URL length: 2048 characters
📊 Capacity Estimation
👥 Users
500M monthly active users
💾 Storage
~15TB for 5 years (100 bytes per URL × 500M URLs/month × 60 months)
⚡ QPS
Write: ~40 URLs/sec, Read: ~4000 redirects/sec
🌐 Bandwidth
Read: 50GB/day, Write: 5GB/day (10:1 read/write ratio)
📐 Assumptions
- • 100M new URLs shortened per month
- • 100:1 read to write ratio (more redirects than shortenings)
- • Each URL entry: ~500 bytes (URL + metadata)
- • 5 year data retention
- • Average original URL length: 200 characters
- • 7 characters for short key using Base62 = 62^7 = 3.5 trillion combinations
💡 Key Concepts
CRITICAL
Base62 Encoding
Use [a-zA-Z0-9] to encode numeric IDs into short strings. 62^7 = 3.5 trillion combinations is enough for our scale.
CRITICAL
Key Generation Service (KGS)
Pre-generate keys to avoid collisions and improve performance. KGS maintains a pool of unused keys.
CRITICAL
Read-Heavy Optimization
Use caching extensively since reads >> writes (100:1 ratio). Cache at multiple layers: CDN, Redis, application.
HIGH
301 vs 302 Redirects
301 (permanent) is cacheable by browsers - good for SEO but reduces analytics accuracy. 302 (temporary) allows tracking each click.
HIGH
Consistent Hashing
For database sharding, use consistent hashing on short key to distribute data and minimize redistribution on node changes.
MEDIUM
Cache-Aside Pattern
Application checks cache first, on miss queries DB and populates cache. Works well for read-heavy workloads.
💡 Interview Tips
- 💡Start with clarifying requirements - ask about scale, features, and constraints
- 💡Do back-of-envelope calculations early to understand scale (QPS, storage)
- 💡Discuss the key generation algorithm in detail - it's the core problem
- 💡Mention caching strategy - it's critical for read-heavy systems
- 💡Don't forget to discuss monitoring and rate limiting
- 💡Proactively mention security (malware detection, abuse prevention)
- 💡Draw diagrams - visual communication is important in interviews
- 💡Discuss trade-offs for each decision you make