Requirements

Functional Requirements:

1. Generate short URLs for original long URLs
2. Given a valid short URL, redirect it to the original long URL
3. URLs expire after 2 weeks

Non-Functional Requirements:

1. Low redirect latency (< 100 ms p99)
2. High availability: 99.9% uptime (less than 10 hours of downtime)
3. Assume 100m DAU

Capacity Estimation

Assume 100m DAU, 1 link creation per user per day, 100 redirects per user

Compute

100 x 10^6 users x (100 redirects) x = 100 x 10^8 redirects per day. 10^5 seconds per day. So 100 x 10^3 QPS == 100,000

Assume standard 32 GB, 16 vCPU node can handle ~2k QPS, so want 500 servers behind load balancer. Want to ensure headroom of ~30% so maybe 700-800 servers.

Storage

100 x 10^6 users x 1 create = 10^8 POSTS per day. Per year that's ~400 x 10^8 = 4 x 10^10 POSTS -> assume storage per URL/short URL is 1 KB = 10^3 B.

So 4 x 10^13 Bytes annually, assuming each POST only expires after a year (extra safe assumption). That is 40 TB. That is just past the cusp of storing on a single database/managed DB -- need explore sharding strategy.

API Design

GET /api/url/

POST /api/url -> BODY {url: }

High-Level Design

URL shortening algorithm: use some kind of hashing algorithm

Assume 100:1 read:write ratio

Load balancer fronting stateless servers.

POST endpoint flow:

• Hash algorithm to determine short URL
• Persist to database

GET endpoint flow:

• Given short url, fetch record from database. Return 404 if not found, otherwise 301 permanent to original URL

Database Design

Relational Database (MySQL)

url_table

id, original, short, created

index on short url

Detailed Component Design

To scale writes:

• Shard database to horizontally scale writes. Compute is already behind a load balancer.

To scale reads:

• leverage content-delivery network to cache redirect responses.
• Use cache (e.g. redis) to avoid database lookups.