Problem Statement
Design a URL shortening service like bit.ly that:- Converts long URLs to short URLs
- Redirects short URLs to original URLs
- Tracks click analytics (optional)
Step 1: Requirements Clarification
Functional Requirements
Core Features
- Given a long URL → generate short URL
- Given a short URL → redirect to original
- Custom short URLs (optional)
- URL expiration (optional)
Analytics (Optional)
- Click count
- Geographic data
- Referrer tracking
- Time-based analytics
Non-Functional Requirements
- High Availability: Service should be always accessible
- Low Latency: Redirects should be fast (<100ms)
- Scalability: Handle billions of URLs
- Durability: URLs should never be lost
Capacity Estimation
Copy
Assumptions:
• 100M new URLs per month
• 10:1 read-to-write ratio
• 5-year data retention
• Average URL length: 500 bytes
Calculations:
─────────────────────────────────────────────────────────────
Write QPS:
= 100M / (30 × 24 × 3600)
= 100M / 2.6M
≈ 40 QPS (peak: 120 QPS)
Read QPS:
= 40 × 10 = 400 QPS (peak: 1,200 QPS)
Storage (5 years):
= 100M × 12 × 5 × 600 bytes
= 6B × 600 bytes
= 3.6 TB
Short URL length:
• 6 chars (base62): 62^6 = 56 billion (OK)
• 7 chars (base62): 62^7 = 3.5 trillion (OK)
→ 7 characters gives us plenty of room
Step 2: High-Level Design
Copy
┌─────────────────────────────────────────────────────────────────┐
│ URL Shortener Architecture │
├─────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────┐ │
│ │ Client │ │
│ └──────┬──────┘ │
│ │ │
│ ┌──────▼──────┐ │
│ │ Load Balancer│ │
│ └──────┬──────┘ │
│ │ │
│ ┌──────────────┼──────────────┐ │
│ │ │ │ │
│ ┌──────▼──────┐ ┌─────▼─────┐ ┌─────▼─────┐ │
│ │ API Server │ │API Server │ │API Server │ │
│ └──────┬──────┘ └─────┬─────┘ └─────┬─────┘ │
│ │ │ │ │
│ └──────────────┼──────────────┘ │
│ │ │
│ ┌─────────────────────┼─────────────────────┐ │
│ │ │ │ │
│ ┌──────▼──────┐ ┌──────▼──────┐ ┌──────▼──────┐ │
│ │ Cache │ │ Database │ │ Counter │ │
│ │ (Redis) │ │ (Cassandra) │ │ Service │ │
│ └─────────────┘ └─────────────┘ └─────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
API Design
Copy
POST /api/v1/shorten
─────────────────────────────────────────────────────────────
Request:
{
"long_url": "https://example.com/very/long/path?with=params",
"custom_alias": "my-link", // optional
"expires_at": "2025-12-31" // optional
}
Response:
{
"short_url": "https://short.ly/abc123",
"long_url": "https://example.com/very/long/path?with=params",
"created_at": "2024-01-15T10:30:00Z",
"expires_at": "2025-12-31T00:00:00Z"
}
─────────────────────────────────────────────────────────────
GET /{short_code}
─────────────────────────────────────────────────────────────
Response: 301 Redirect to original URL
HTTP/1.1 301 Moved Permanently
Location: https://example.com/very/long/path?with=params
─────────────────────────────────────────────────────────────
GET /api/v1/stats/{short_code}
─────────────────────────────────────────────────────────────
Response:
{
"short_url": "https://short.ly/abc123",
"total_clicks": 15234,
"clicks_by_country": {...},
"clicks_by_date": {...}
}
Step 3: Key Design Decisions
Short URL Generation
- Base62 Encoding
- Counter + Encoding
- Hash-Based
Copy
import string
ALPHABET = string.ascii_letters + string.digits # 62 chars
def encode_base62(num):
"""Convert number to base62 string"""
if num == 0:
return ALPHABET[0]
result = []
while num:
num, remainder = divmod(num, 62)
result.append(ALPHABET[remainder])
return ''.join(reversed(result))
def decode_base62(s):
"""Convert base62 string to number"""
num = 0
for char in s:
num = num * 62 + ALPHABET.index(char)
return num
# Example:
# encode_base62(123456789) → "8M0kX"
Copy
class ShortURLGenerator:
def __init__(self, counter_service):
self.counter = counter_service
def generate(self):
# Get next unique ID from distributed counter
unique_id = self.counter.get_next_id()
# Convert to base62
short_code = encode_base62(unique_id)
# Pad to 7 characters if needed
return short_code.zfill(7)
# Counter options:
# 1. Database auto-increment (bottleneck)
# 2. Twitter Snowflake (distributed)
# 3. Redis INCR (simple, fast)
# 4. UUID → take first 7 chars (collision risk)
Copy
import hashlib
def generate_short_url(long_url, attempt=0):
"""Generate short URL using MD5 hash"""
# Add attempt number to handle collisions
input_string = f"{long_url}{attempt}"
# MD5 hash → take first 7 characters
hash_object = hashlib.md5(input_string.encode())
hash_hex = hash_object.hexdigest()
# Convert hex to base62 for shorter result
hash_int = int(hash_hex[:12], 16)
short_code = encode_base62(hash_int)[:7]
return short_code
# Handle collisions:
def create_short_url(long_url):
for attempt in range(10):
short_code = generate_short_url(long_url, attempt)
if not exists_in_db(short_code):
save_to_db(short_code, long_url)
return short_code
raise Exception("Could not generate unique short URL")
Database Schema
Copy
-- Main URL mapping table
CREATE TABLE urls (
id BIGINT PRIMARY KEY,
short_code VARCHAR(10) UNIQUE NOT NULL,
original_url TEXT NOT NULL,
user_id BIGINT,
created_at TIMESTAMP DEFAULT NOW(),
expires_at TIMESTAMP,
click_count BIGINT DEFAULT 0
);
-- Index for fast lookups
CREATE INDEX idx_short_code ON urls(short_code);
-- Analytics table (separate for write performance)
CREATE TABLE click_events (
id BIGINT PRIMARY KEY,
short_code VARCHAR(10),
clicked_at TIMESTAMP,
ip_address INET,
user_agent TEXT,
referrer TEXT,
country VARCHAR(2)
);
-- Partition by time for easy cleanup
CREATE TABLE click_events_2024_01 PARTITION OF click_events
FOR VALUES FROM ('2024-01-01') TO ('2024-02-01');
Database Choice
| Option | Pros | Cons |
|---|---|---|
| PostgreSQL | ACID, mature, good for analytics | Harder to scale writes |
| Cassandra | High write throughput, easy scaling | No transactions, eventual consistency |
| DynamoDB | Managed, auto-scaling | Cost at scale, vendor lock-in |
Step 4: Detailed Component Design
Caching Strategy
Copy
┌─────────────────────────────────────────────────────────────────┐
│ Cache Layer Design │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Read Flow: │
│ ────────── │
│ 1. Client requests short.ly/abc123 │
│ 2. Check Redis cache for "abc123" │
│ 3. Cache hit → return original URL (99% of cases) │
│ 4. Cache miss → query database │
│ 5. Store in cache with TTL (24 hours) │
│ 6. Return 301 redirect │
│ │
│ Cache sizing: │
│ ──────────── │
│ • 80/20 rule: 20% URLs = 80% traffic │
│ • Hot URLs: ~100 million │
│ • Size: 100M × 600 bytes = 60 GB │
│ • Redis cluster: 3 nodes × 32 GB each │
│ │
│ Cache key format: │
│ url:{short_code} → {original_url} │
│ │
└─────────────────────────────────────────────────────────────────┘
Copy
class URLService:
def __init__(self, cache, db):
self.cache = cache
self.db = db
def get_original_url(self, short_code):
# 1. Check cache
cached = self.cache.get(f"url:{short_code}")
if cached:
# Async: increment click count
self.increment_clicks_async(short_code)
return cached
# 2. Query database
url_record = self.db.get_by_short_code(short_code)
if not url_record:
raise NotFoundException()
# 3. Check expiration
if url_record.expires_at and url_record.expires_at < now():
raise ExpiredException()
# 4. Cache for future requests
self.cache.set(
f"url:{short_code}",
url_record.original_url,
ex=86400 # 24 hour TTL
)
# 5. Track click
self.increment_clicks_async(short_code)
return url_record.original_url
URL Shortening Service
Copy
class URLShortener:
def __init__(self, id_generator, db, cache):
self.id_generator = id_generator
self.db = db
self.cache = cache
def shorten(self, long_url, custom_alias=None, expires_at=None):
# 1. Validate URL
if not self.is_valid_url(long_url):
raise InvalidURLException()
# 2. Check for duplicate (optional - return existing)
existing = self.db.get_by_original_url(long_url)
if existing:
return existing.short_code
# 3. Handle custom alias
if custom_alias:
if self.db.exists(custom_alias):
raise AliasAlreadyExistsException()
short_code = custom_alias
else:
# Generate unique ID and convert to base62
unique_id = self.id_generator.get_next_id()
short_code = encode_base62(unique_id)
# 4. Store in database
url_record = URLRecord(
short_code=short_code,
original_url=long_url,
expires_at=expires_at
)
self.db.save(url_record)
# 5. Pre-warm cache (optional)
self.cache.set(f"url:{short_code}", long_url, ex=86400)
return short_code
Distributed ID Generation
Copy
┌─────────────────────────────────────────────────────────────────┐
│ ID Generation Options │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Option 1: Database Auto-Increment │
│ ───────────────────────────────── │
│ + Simple, guaranteed unique │
│ - Single point of failure, bottleneck │
│ │
│ Option 2: UUID (take first 7 chars) │
│ ────────────────────────────────── │
│ + Distributed, no coordination │
│ - Collision risk, not sequential │
│ │
│ Option 3: Redis Counter │
│ ──────────────────────── │
│ + Fast, atomic INCR │
│ - Single point of failure (mitigate with replication) │
│ │
│ Option 4: Snowflake ID (Recommended) │
│ ──────────────────────────────────── │
│ 64 bits: timestamp(41) + datacenter(5) + machine(5) + seq(12) │
│ + Distributed, time-sortable, no coordination │
│ - Clock sync required │
│ │
└─────────────────────────────────────────────────────────────────┘
Step 5: Scaling Considerations
Read Path Optimization
Copy
┌─────────────────────────────────────────────────────────────────┐
│ Optimized Read Path │
├─────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────┐ │
│ │ CDN │ ← Cache 301 redirects │
│ │ (CloudFlare) │ for popular URLs │
│ └────────┬────────┘ │
│ │ Cache miss │
│ ┌────────▼────────┐ │
│ │ Load Balancer │ │
│ └────────┬────────┘ │
│ │ │
│ ┌────────▼────────┐ │
│ │ API Servers │ │
│ │ (stateless) │ │
│ └────────┬────────┘ │
│ │ │
│ ┌────────▼────────┐ │
│ │ Redis │ ← 99% cache hit rate │
│ │ Cluster │ │
│ └────────┬────────┘ │
│ │ Cache miss (1%) │
│ ┌────────▼────────┐ │
│ │ Database │ │
│ └─────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
Database Sharding
Copy
Shard by short_code hash:
short_code = "abc123"
shard_id = hash(short_code) % num_shards
┌─────────────────────────────────────────────────────────────────┐
│ Shard 0 Shard 1 Shard 2 Shard 3 │
│ (a-g)* (h-n)* (o-u)* (v-z0-9)* │
├─────────────────────────────────────────────────────────────────┤
│ abc123 hxK9mP qR5tYu zA3bC7 │
│ def456 jLm2nO sTu8vW 2Df5Gh │
│ ... ... ... ... │
└─────────────────────────────────────────────────────────────────┘
* Simplified - actual sharding uses consistent hashing
Step 6: Additional Features
Analytics Pipeline
Copy
┌─────────────────────────────────────────────────────────────────┐
│ Analytics Architecture │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Click Event │
│ │ │
│ ▼ │
│ ┌──────────┐ │
│ │ Kafka │ ← High-throughput event streaming │
│ │ Topic │ │
│ └────┬─────┘ │
│ │ │
│ ┌────┴────────────────────┐ │
│ │ │ │
│ ▼ ▼ │
│ ┌──────────────┐ ┌──────────────┐ │
│ │ Real-time │ │ Batch │ │
│ │ (Flink) │ │ (Spark) │ │
│ └──────┬───────┘ └──────┬───────┘ │
│ │ │ │
│ ▼ ▼ │
│ ┌──────────────┐ ┌──────────────┐ │
│ │ Redis │ │ Data Lake │ │
│ │ (counters) │ │ (S3) │ │
│ └──────────────┘ └──────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
301 vs 302 Redirect
| Code | Type | SEO | Caching | Use Case |
|---|---|---|---|---|
| 301 | Permanent | Passes link juice | Cached by browser | Default choice |
| 302 | Temporary | Less SEO value | Not cached | Analytics, A/B testing |
Interview Tip: Mention that 301 redirects are cached by browsers, which means subsequent clicks may not hit your servers. This is great for performance but bad for accurate analytics. Some services use 302 for this reason.
Final Architecture
Copy
┌─────────────────────────────────────────────────────────────────┐
│ Complete URL Shortener System │
├─────────────────────────────────────────────────────────────────┤
│ │
│ ┌──────────────┐ │
│ │ Clients │ │
│ └──────┬───────┘ │
│ │ │
│ ┌──────▼───────┐ │
│ │ CDN │ │
│ └──────┬───────┘ │
│ │ │
│ ┌──────▼───────┐ │
│ │ LB │ │
│ └──────┬───────┘ │
│ │ │
│ ┌────────────────────┼────────────────────┐ │
│ │ │ │ │
│ ┌──────▼──────┐ ┌───────▼───────┐ ┌──────▼──────┐ │
│ │ Write API │ │ Read API │ │ Analytics │ │
│ │ Servers │ │ Servers │ │ API │ │
│ └──────┬──────┘ └───────┬───────┘ └──────┬──────┘ │
│ │ │ │ │
│ ┌──────▼──────┐ ┌───────▼───────┐ ┌──────▼──────┐ │
│ │ ID │ │ Redis │ │ Kafka │ │
│ │ Generator │ │ Cluster │ │ │ │
│ │ (Redis) │ └───────┬───────┘ └──────┬──────┘ │
│ └──────┬──────┘ │ │ │
│ │ │ │ │
│ └─────────┬──────────┘ │ │
│ │ │ │
│ ┌───────▼────────┐ ┌─────────▼────────┐ │
│ │ Cassandra │ │ ClickHouse │ │
│ │ (URL data) │ │ (Analytics) │ │
│ └────────────────┘ └──────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
Key Takeaways
| Aspect | Decision | Reason |
|---|---|---|
| Short code | 7 chars, base62 | 3.5 trillion URLs, no special chars |
| ID generation | Snowflake | Distributed, no coordination |
| Database | Cassandra | High write throughput, easy scaling |
| Cache | Redis cluster | Fast reads, 99% hit rate |
| Redirect | 301 | Browser caching, SEO friendly |
| Analytics | Kafka + ClickHouse | Async processing, OLAP queries |