System Design Interview · Classic

Design a URL Shortener (bit.ly)

Given 30-45 minutes in an interview, this is the most common system design question. Here is the full answer with every layer explained.

1. Requirements Clarification

Functional Requirements

· Given a long URL, generate a short URL (alias)
· Redirect short URL to original URL
· Custom aliases (optional)
· Expiry / TTL for links (optional)
· Analytics: click count, geo, device (nice to have)

Non-Functional Requirements

· High availability — redirect must be available 24/7
· Low latency — redirection in <10ms (with cache)
· Scale — 100M new URLs/day write; 10B reads/day
· Short URL must be unique
· URL cannot be predictable/guessable

2. Capacity Estimation

Write QPS: 100M URLs/day ÷ 86,400 sec/day ≈ 1,200 QPS Read QPS: 10B reads/day ÷ 86,400 ≈ 116,000 QPS (100:1 read/write ratio) Read:Write Ratio = 100:1 → This is a READ-HEAVY system → Cache aggressively Storage (5 years): 100M URLs/day × 365 × 5 = 182.5 Billion URLs Per record: short_url(8B) + long_url(100B) + metadata(100B) ≈ 500 bytes Total storage: 182.5B × 500B ≈ 91 TB (manageable with sharding) Bandwidth: Read: 116,000 QPS × 500 bytes ≈ 58 MB/s ← modest Cache requirement (assuming 80/20 rule): 20% of URLs serve 80% reads → cache top 20M URLs Memory: 20M × 500 bytes ≈ 10 GB → fits in Redis comfortably

3. API Design

POST /api/v1/shorten

Request: { "longUrl": "https://...", "alias": "optional", "expiry": "2025-01-01" }

Response: { "shortUrl": "https://bit.ly/xK9dP2" }

GET /{shortCode}

Request: —

Response: HTTP 301/302 redirect to longUrl

GET /api/v1/{shortCode}/stats

Request: —

Response: { "clicks": 12345, "geo": {...} }

DELETE /api/v1/{shortCode}

Request: —

Response: 204 No Content

301 vs 302 Redirect — Interview Question

301 (Permanent): Browser caches the redirect. Next time, browser goes directly to long URL — our server gets less traffic. Better for reduced load but we lose click analytics.
302 (Temporary): No caching. Every redirect hits our server — we can track analytics. Use 302 for analytics-heavy systems.

4. Short Code Generation — Trade-offs

MD5 Hash (truncate)

How: MD5(longUrl) → take first 7 chars → Base62

✓ Pros

· Deterministic (same URL = same short)

· No DB lookup to generate

✗ Cons

· Hash collision possible

· If same URL submitted twice, collision detection needed

· MD5 is weak for security

→ Acceptable for small scale. Need collision handling.

Auto-increment ID + Base62 ✓

How: DB auto-increment ID (e.g. 12345) → Base62 encode → 'dnh'

✓ Pros

· Guaranteed unique

· Simple

· Predictable length growth

✗ Cons

· IDs are sequential (guessable)

· Central ID generator = bottleneck

→ Best approach. Use distributed ID generator (Twitter Snowflake).

Base62 Capacity

Characters: a-z (26) + A-Z (26) + 0-9 (10) = 62 chars.
7 characters: 62⁷ ≈ 3.5 trillion unique codes → enough for 182B URLs with room to spare.

5. High-Level Architecture

┌─────────┐ │ DNS │ └────┬────┘ │ ┌────▼────┐ ┌─────┤ CDN ├─────┐ │ └─────────┘ │ (static assets, popular short URLs) │ │ ┌────▼─────┐ ┌────▼─────┐ │ Mobile │ │ Browser │ └────┬─────┘ └────┬─────┘ │ │ └──────────┬──────────┘ │ ┌──────▼──────┐ │ Load Balancer│ └──────┬───────┘ │ ┌─────────────┼─────────────┐ │ │ │ ┌──────▼──────┐ ┌───▼────┐ ┌──────▼──────┐ │ Web Server 1│ │ ... │ │ Web Server N│ (stateless) └──────┬──────┘ └────────┘ └──────┬──────┘ │ │ └──────────┬───────────────┘ │ ┌───────▼────────┐ │ Redis Cache │ ← shortCode → longUrl (10 GB, ~95% cache hits) └───────┬────────┘ │ miss ┌───────▼────────┐ │ MySQL / Cass. │ ← source of truth │ (Read Replicas)│ └────────────────┘

6. Database Schema

TABLE urls ( id BIGINT PRIMARY KEY AUTO_INCREMENT, short_code VARCHAR(8) NOT NULL UNIQUE, long_url TEXT NOT NULL, user_id BIGINT, -- NULL for anonymous created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP, expires_at TIMESTAMP, -- NULL = no expiry click_count BIGINT DEFAULT 0 ); INDEX idx_short_code ON urls(short_code); -- most read path TABLE users ( id BIGINT PRIMARY KEY, email VARCHAR(255) NOT NULL UNIQUE, api_key VARCHAR(64) NOT NULL UNIQUE );

Why not just the short_code as PK? Auto-increment integer ID is used as the input to Base62 encoding. The short_code is a derived column, not the primary key.

7. Scaling Bottlenecks & Solutions

Low

⚠️ Database write bottleneck (1,200 QPS)

Single primary is fine for this write load (MySQL handles ~5K write QPS). Add connection pooling. Only shard when reaching 10K+ QPS.

Solved by Cache

⚠️ Database read bottleneck (116,000 QPS)

95% of reads served from Redis cache. Only 5,800 QPS hits DB. Add read replicas to handle remaining. Cache key: shortCode → longUrl with TTL.

Medium

⚠️ Hot URLs (viral short links causing thundering herd)

Pre-populate cache for popular URLs. Add jitter to TTL to prevent simultaneous expiry. Use pub-sub to invalidate cache on URL deletion.

High

⚠️ Single Redis instance failure

Redis Cluster with replication. Master-replica with sentinel for automatic failover. Redis persistence (RDB + AOF) for durability.

Low

⚠️ URL expiry cleanup

Background job runs every hour. Lazy deletion: check expiry on read and return 404. Redis TTL handles cache expiry automatically.

8. Likely Follow-up Questions

Q: How would you handle custom aliases?

A: User provides their preferred alias → check if it exists in DB (shortCode lookup) → if taken, return error → if free, insert with user's alias as short_code instead of auto-generated one. Limit custom aliases to premium users to prevent abuse.

Q: How would you prevent abuse (spam short URLs)?

A: Rate limiting per API key (e.g., 1000 URL creations per day). Use URL reputation service to check if long URL is malicious. Require email verification before allowing URL creation.

Q: How would you implement analytics?

A: Don't block redirect with analytics writes. Use fire-and-forget: push click event to Kafka on redirect, then redirect immediately. Consumer processes events asynchronously and writes to a time-series DB (ClickHouse, InfluxDB) for analysis.

Q: How do you scale to 1 trillion URLs?

A: Shard by shortCode hash (consistent hashing). Each shard has its own auto-increment range (or use distributed ID gen like Twitter Snowflake). Cache layer remains the same. CDN can directly serve redirect for very popular URLs.

← Fundamentals Twitter →