Design Exercise: URL Shortener
Requirements
- Shorten long URLs → short URLs (e.g., bit.ly/abc123)
- Redirect short URL → original URL
- 100M URLs/month created, 10B redirects/month
- Redirect latency < 50ms
Estimation
Write: 100M/month ÷ 2.6M sec/month ≈ 40 writes/sec
Read: 10B/month ÷ 2.6M ≈ 4000 reads/sec (100:1 read-heavy)
Storage: 100M × 500B = 50GB/month, 5yr = 3TB
Short URL length: 62^7 = 3.5 trillion combinations (enough)High-Level Design
Client ──► Load Balancer ──► App Servers (stateless)
│
┌──────────────┼──────────────┐
▼ ▼ ▼
Redis Cache PostgreSQL Rate Limiter
(hot URLs) (all mappings) (per-user)
Key Decisions
- ID generation: Base62 encode an auto-increment ID or use hash (MD5 first 7 chars)
- Storage: PostgreSQL (simple KV: short_code → long_url)
- Caching: Redis for top 20% most-accessed URLs (Pareto principle)
- Redirect: 301 (permanent, cached by browser) or 302 (temporary, trackable)
Database Schema
CREATE TABLE urls (
id BIGSERIAL PRIMARY KEY,
short_code VARCHAR(7) UNIQUE NOT NULL,
long_url TEXT NOT NULL,
created_at TIMESTAMPTZ DEFAULT NOW(),
expires_at TIMESTAMPTZ,
click_count BIGINT DEFAULT 0
);
CREATE INDEX idx_short_code ON urls(short_code);