Design a URL Shortener

Read-heavy key-value lookups

Requirements: create short codes, redirect quickly, optional custom aliases and expiry. Design: a write service obtains a unique numeric ID (from a range allocator or Snowflake-style generator) and base62-encodes it, avoiding collisions without checking; the code-to-URL mapping lives in a key-value store or partitioned relational table; redirects go through a cache and return 301 (cacheable by browsers) or 302 (when every click must be counted). Click analytics are sent asynchronously to a queue.

Apply the framework

Classic problems combine the building blocks in different ways.

Base62 codes and capacity, run

I ran this with Python 3.12.3 using only the standard library; inputs are fixed or seeded, so the output is reproducible. The 18.25 billion links estimated for five years fit in six characters (jV58GI); seven characters give about 3.5 trillion codes.

# Short codes for a URL shortener: base62-encode a unique numeric ID
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encode(n):
    s = ""
    while True:
        n, r = divmod(n, 62)
        s = ALPHABET[r] + s
        if n == 0:
            return s

def decode(s):
    n = 0
    for ch in s:
        n = n * 62 + ALPHABET.index(ch)
    return n

for i in (0, 61, 62, 125, 18_250_000_000):
    code = encode(i)
    print(f"{i:>14,} -> {code:8} -> {decode(code):,}")
for length in (6, 7, 8):
    print(f"{length} chars: {62 ** length:,} codes")

Output:

             0 -> 0        -> 0
            61 -> Z        -> 61
            62 -> 10       -> 62
           125 -> 21       -> 125
18,250,000,000 -> jV58GI   -> 18,250,000,000
6 chars: 56,800,235,584 codes
7 chars: 3,521,614,606,208 codes
8 chars: 218,340,105,584,896 codes

Avoid guessable codes if needed

Sequential IDs give sequential codes; shuffle or encrypt IDs if links must not be enumerable.

Quick check: Why prefer 302 over 301 in some shorteners?

• 301 is not supported by browsers
• 302 is faster
• Browsers do not cache 302 permanently, so every click reaches the service for analytics
• 302 needs no server