Design a URL shortener

1. 1Requirements
2. 2Estimates
3. 3API
4. 4Data model
5. 5High level design
6. 6Deep dives
7. 7Bottlenecks
8. 8Tradeoffs

Sample page

This page proves out the system design template and components. The numbers are worked examples; the full write-up comes later.

Requirements

Sends a long URL, gets back sho.rt/x7Kp2

Functional:

• Given a long URL, return a short code. Visiting the short URL redirects to the long one.
• Codes never change once issued. Custom aliases and expiry are out of scope for v1.

Non-functional:

• Redirects must be fast (p99 under 50 ms server time) and highly available.
• Reads far outnumber writes.

Estimates

Assume 100 million new URLs a month and a 100 to 1 read to write ratio.

• Writes: 100M / (30 × 86,400 s) ≈ 40 per second on average.
• Reads: about 4,000 per second on average; plan for a few times that at peak.
• Codes: 10 years × 1.2B a year = 12B codes. Seven base62 characters give 62⁷ ≈ 3.5 trillion, so 7 characters is plenty.

API

POST /api/urls        { "longUrl": "https://..." }  ->  201 { "code": "x7Kp2" }
GET  /{code}          ->  301 or 302, Location: https://...

Tradeoff: 301 vs. 302 redirect

We gain

301 lets browsers cache the redirect, so repeat visits never reach our servers.

We give up

Cached redirects are invisible to us, so click analytics undercount. Pick 302 if analytics matter.

Data model

One table keyed by code: code (PK), long_url, created_at. Lookups are always by code, which makes it a good fit for a key-value store or a relational table with a primary key. We start with PostgreSQL and revisit when a single primary can’t keep up.

High level design

Writes go through the app servers to the database. Redirects are answered from Redis whenever possible and fall back to the database on a miss.

Architecture: URL shortener (v1)+−ResetFullscreen

Scroll or pinch to zoom, drag to pan

Drawn in the Excalidraw style. Each app server takes a block of IDs from the ID service, so codes never collide.

Each short code comes from a counter range handed out by the ID service, then base62 encoded:

Java

Base62.java

public final class Base62 {
    private static final String ALPHABET =
            "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    /** Turns a unique counter value into a short code. 62^7 is about 3.5 trillion codes. */
    public static String encode(long id) {
        if (id < 0) throw new IllegalArgumentException("id must be non-negative");
        if (id == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (id > 0) {
            sb.append(ALPHABET.charAt((int) (id % 62)));
            id /= 62;
        }
        return sb.reverse().toString();
    }

    public static long decode(String code) {
        long id = 0;
        for (char c : code.toCharArray()) {
            int digit = ALPHABET.indexOf(c);
            if (digit < 0) throw new IllegalArgumentException("Bad character " + c);
            id = id * 62 + digit;
        }
        return id;
    }

    public static void main(String[] args) {
        String code = encode(125_000_000_000L);
        System.out.println(code + " " + decode(code)); // 2crtgcg 125000000000
    }
}

Python

base62.py

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"


def encode(id: int) -> str:
    """Turns a unique counter value into a short code. 62**7 is about 3.5 trillion codes."""
    if id < 0:
        raise ValueError("id must be non-negative")
    if id == 0:
        return "0"
    out = []
    while id > 0:
        id, rem = divmod(id, 62)
        out.append(ALPHABET[rem])
    return "".join(reversed(out))


def decode(code: str) -> int:
    id = 0
    for c in code:
        id = id * 62 + ALPHABET.index(c)
    return id


if __name__ == "__main__":
    code = encode(125_000_000_000)
    print(code, decode(code))  # 2crtgcg 125000000000

Tradeoff: Counter ranges vs. hashing the URL

We gain

No collisions and no read-before-write. Each server mints codes locally from its range.

We give up

Codes are guessable in sequence, and a crashed server wastes the rest of its range.

Deep dives

• What happens when one link goes viral and a single cache key takes 50,000 reads a second.
• Making the ID service highly available without handing out the same range twice.

Bottlenecks

• A single database primary for writes. At about 40 writes a second this is far off, but partitioning by code is the path when it isn’t.
• Cache memory: the hot set, not every URL, needs to fit.

Tradeoffs

A summary of every decision on this page and what it gave up. Filled in with the full write-up.