Case Study: Design a URL Shortener

A classic problem that exercises most building blocks.

1. Requirements​

Functional

• Create a short URL for a long URL.
• Redirect a short URL to the original.
• Optional: custom aliases, expiry, click analytics.

Non-functional

• Very high availability and low redirect latency.
• Read-heavy (for example 100 reads for every write).
• Short URLs should not be guessable in sequence if privacy matters.

2. Estimation​

New URLs: 100 million per month  -> about 40 writes/s
Reads (100:1)                    -> about 4,000 reads/s (peak 3x)
Storage: 500 bytes x 100M x 12 x 5 years = about 3 TB
Key space: 7 characters of base62 = 62^7 = about 3.5 trillion keys

3. API​

POST /v1/urls        { "long_url": "https://...", "alias": "optional" }  -> 201 { "short": "https://pv.io/aZ3k9Q" }
GET  /{short}        -> 301 or 302 redirect to the long URL

301 is cached by browsers (less load, no analytics); 302 is not cached (every click reaches you).

4. Generating the key​

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encode(n: int) -> str:
    if n == 0:
        return ALPHABET[0]
    out = []
    while n:
        n, r = divmod(n, 62)
        out.append(ALPHABET[r])
    return "".join(reversed(out))

print(encode(125))   # "21"

5. High-level design​

Client -> CDN / LB -> App servers -> Cache (Redis) -> Key-value DB (sharded)
                          |
                          +-> Key generation service
                          +-> Queue -> Analytics workers

• Data model: short_key (PK) -> long_url, created_at, expires_at, owner_id.
• Storage: a key-value or wide-column store (reads by primary key, simple access pattern), sharded by short_key.
• Cache: cache-aside with LRU for hot links; most traffic hits a small set of URLs.
• Redirect path: LB -> app -> cache lookup -> DB on miss -> 301/302.

6. Deep dives​

• Collisions: use a unique constraint on short_key and retry on conflict.
• Abuse: rate limit creation, scan targets for malware, expire unused links.
• Analytics: write click events to a queue and aggregate asynchronously so redirects stay fast.
• Availability: replicate across zones; the redirect path should not depend on analytics.
• Custom aliases: check availability atomically (conditional insert).