Design a URL Shortener

Step 1 of 4: Understand the problem and establish design scope #

Goal: lock in requirements and the back-of-the-envelope numbers.

Requirements:

1. Given a long URL, return a much shorter URL; clicking the short URL redirects to the original
2. 100 million URLs generated per day
3. Short URL uses [0-9, a-z, A-Z] characters: 62 possible chars
4. No deletion or update of shortened URLs
5. High availability, scalability, fault tolerance

Back of the envelope estimation:

1. Write QPS: 100M / 24 / 3600 = 1,160 writes/s
2. Read QPS (10:1 ratio): 11,600 reads/s
3. 10-year records: 100M × 365 × 10 = 365 billion URLs
4. Storage (avg URL length 100 bytes): 365B × 100 bytes × 10 years = 365 TB

Step 2 of 4: Propose high-level design and get buy-in #

Goal: agree on the API, redirect type, and shortening flow.

API endpoints:

• POST api/v1/data/shorten: body {longUrl: longURLString}, returns shortURL
• GET api/v1/shortUrl: returns longURL for HTTP redirection

URL redirecting:

1. 301 redirect: permanent. Browser caches the response; subsequent requests skip the shortener → reduces server load, but loses analytics
2. 302 redirect: temporary. All requests hit the shortener → enables click tracking and analytics

URL shortening flow:

• www.tinyurl.com/{hashValue}: a hash function maps long URL → hashValue
• Requirements: each longURL maps to one hashValue; hashValue must map back to longURL

Step 3 of 4: Design deep dive #

Goal: pick the hash function, then detail shorten + redirect paths.

Data model #

Store <shortURL, longURL> mapping in a relational database (hash tables in memory aren't feasible at scale). Simplified schema: id, shortURL, longURL.

Hash function #

Hash value length: 62^n ≥ 365B. At n=7, 62^7 = ~3.5 trillion → 7-character hash values.

Option A: Hash + collision resolution

1. Use CRC32, MD5, or SHA-1, then take the first 7 characters
2. On collision, recursively append a predefined string until unique
3. Expensive: DB lookup on every request. Bloom filters can speed up collision checking

Option B: Base 62 conversion

1. Convert a unique numeric ID to base 62 (0-9 → 0-9, 10-35 → a-z, 36-61 → A-Z)
2. Example: 11157₁₀ = 2×62² + 55×62¹ + 59×62⁰ = [2, T, X] → https://tinyurl.com/2TX

Comparison:

URL shortening deep dive (Base 62 approach) #

1. longURL input → check if already in DB → return existing shortURL if found
2. If new: generate a unique ID (from a distributed ID generator, see Ch.7) → convert to base 62 → store (id, shortURL, longURL) in DB
3. Example: ID 2009215674938 → base 62 → "zn9edcu"

URL redirecting deep dive #

1. User clicks https://tinyurl.com/zn9edcu
2. Load balancer → web servers → check cache for shortURL
3. Cache hit: return longURL. Cache miss: fetch from DB → cache it → return
4. Invalid shortURL if not in DB

<shortURL, longURL> mapping is cached since reads >> writes.

Step 4 of 4: Wrap up #

Additional talking points:

1. Rate limiter (Ch.4): protect against malicious bulk URL creation
2. Web server scaling: stateless tier, easy horizontal scaling
3. Database scaling: replication and sharding
4. Analytics: track click rates, sources, timing
5. Availability, consistency, reliability (Ch.1)