URL shortener codes: an interactive birthday problem for random, hashed and counter IDs

A URL shortener needs a short, unique code for every link. There are three common ways to make one: draw random characters, hash the URL and keep the first few characters, or take the next number from a counter and write it in base62. Random and hashed codes can collide, and the birthday problem says they collide far sooner than intuition suggests. Counters never collide but need coordination and produce guessable codes.

The playground draws random two-character codes into a grid of all 3,844 possibilities, then applies the same arithmetic to real code lengths and volumes.

The birthday problem, in codes

With 3,844 possible codes, drawing just 73 at random gives even odds that two match, and in the playground the first collision comes at the 40th code. The same holds at scale: 7 base62 characters give 3.5 trillion codes, but collisions become more likely than not after only 2.2 million links, and a billion links produce about 142,000 of them. That sounds alarming until you look at the other number: when a billion codes are taken, a new random code collides with probability 0.028%. So random codes work, provided every insert checks for a clash and retries, which a unique index does atomically.

Three ways to make codes

• Random codes with a unique index and a retry are simple and unguessable. The database does the collision check, and retries stay rare as long as the space is far larger than the number of links.
• Hashing the URL, for example the first 7 characters of a base62-encoded SHA-256, gives the same code for the same URL, which deduplicates for free. Different URLs still collide at the same birthday rate, so a clash needs a fallback such as rehashing with a salt.
• A counter in base62 cannot collide: a billion links need only 6 characters. But the counter must be shared, through a ticket server, ranges of ids handed to each server, or Snowflake-style ids, and sequential codes let anyone enumerate every link. Scrambling the number with a reversible permutation keeps uniqueness while hiding the order.

A key generation service combines the ideas: it pre-generates unused random codes in bulk and hands batches to application servers, so creating a link needs no collision check at all.

Random codes with a retry, and base62

import secrets, string

ALPHABET = string.digits + string.ascii_lowercase + string.ascii_uppercase   # base62

def random_code(length=7):
    return "".join(secrets.choice(ALPHABET) for _ in range(length))

def shorten(db, url, tries=5):
    for _ in range(tries):
        code = random_code()
        # the unique index on code makes the collision check atomic
        inserted = db.execute(
            "INSERT INTO links (code, url) VALUES (%s, %s) ON CONFLICT (code) DO NOTHING",
            (code, url)).rowcount
        if inserted:
            return code
    raise RuntimeError("no free code after retries")

def base62(n):
    """For counter-based ids: unique by construction, no check needed."""
    s = ""
    while True:
        n, r = divmod(n, 62)
        s = ALPHABET[r] + s
        if n == 0:
            return s

In a system design interview

Do the arithmetic out loud: “100 million new links a month is about 6 billion over five years. Seven base62 characters give 3.5 trillion codes, so a random code collides with an existing one less than 0.2% of the time even at the end. We generate randomly, insert under a unique index, and retry on conflict. Codes are unguessable, which matters because some links are private.” Expect the follow-ups: custom aliases, the same long URL shortened twice, and how the check works when the table is sharded by code.

Read the guide to hashing and encoding or unique ids, or watch a strong candidate design a URL shortener.

Questions people ask