Design a URL Shortener

Description

A URL shortener turns a long link into a short one - sedu.ly/aZ3kQ9 - and sends anyone who clicks it on to the original page. It's one of the most popular first system design questions because it's small enough to finish in 45 minutes, yet it touches almost every core idea: estimating load, generating unique IDs, caching a read-heavy path, partitioning data, and choosing between HTTP redirect codes.

It also looks like a one-table app: store code -> longUrl, redirect on lookup. In this lesson you'll see why that first version breaks at scale, and build the real design step by step:

1. Start from the numbers - and let them decide where the effort goes.
2. Encode a unique number instead of guessing codes.
3. Generate IDs at scale (leased ranges, and Snowflake).
4. Hashing the long URL instead, and what it costs.
5. The read path: caching, unknown codes, 301 versus 302.
6. Partitioning the data, and where the design breaks.

The first version, and why it breaks

The first version most people write is:

String shorten(String longUrl) {
    String code;
    do {
        code = randomCode(6);                  // 62^6 ≈ 56.8 billion possible codes
    } while (db.exists(code));                 // an extra read before every write
    db.insert(code, longUrl);                  // two servers can both pass exists() with the same code
    return code;
}

String resolve(String code) {
    return db.find(code);                      // every click is a database read
}

It works on a laptop. At production scale, each part fails in its own way:

• The collision check gets worse as the service succeeds. With 1 billion links stored, a fresh random 6-character code clashes with an existing one about 1.8% of the time; at 6 billion, about 10.6%. Retries become routine, and each costs another read.
• Check-then-insert races. Two app servers can both see exists(code) == false and both insert - one link silently overwrites the other, or an insert fails with an error nobody handles.
• Every click reads the database. Redirects outnumber new links by 100 to 1 or more, and they all land on one table.

A system design answer is the set of decisions that fix these, made in the order the numbers force them.

Start from the numbers

Assume 100 million new links a month, each clicked about 100 times:

Two conclusions fall straight out. Writes are modest, so the design effort goes into the read path. And 3 TB and growing won't stay on one database node, so the data will eventually be partitioned.

Here is where the lesson ends up - each box is explained below:

The pattern: encode a unique number

Instead of guessing a code and checking it, give every link a unique integer ID and write that ID in base 62 - digits, uppercase and lowercase letters, all safe in a URL. Uniqueness comes from the ID, so there is nothing to check:

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

    static String encode(long id) {                          // id >= 0
        StringBuilder sb = new StringBuilder();
        do {
            sb.append(ALPHABET.charAt((int) (id % 62)));     // least significant digit first...
            id /= 62;
        } while (id > 0);                                    // do-while: 0 encodes as "0", not ""
        return sb.reverse().toString();                      // ...so reverse at the end
    }

    static long decode(String code) {
        long id = 0;
        for (int i = 0; i < code.length(); i++) {
            id = id * 62 + ALPHABET.indexOf(code.charAt(i));
        }
        return id;
    }
}

encode(125) is "21" (2 × 62 + 1), and decode(encode(id)) == id for every non-negative long - distinct IDs always give distinct codes. The two classic bugs: dropping the reverse() (codes stay unique, but decode("12") returns 64, not 125), and a plain while loop that encodes 0 as the empty string.

Where the ID comes from is the real design question.

Generating IDs at scale

A database sequence is the simplest source, but one counter serializes every write and is a single point of failure. The usual fix is range leasing: each app server claims a block of IDs with one atomic increment and hands them out from memory.

interface SharedCounter { long addAndGet(long delta); }   // e.g. UPDATE id_counter SET value = value + 1000 RETURNING value

class IdRangeAllocator {
    private static final long BLOCK = 1_000;
    private final SharedCounter counter;
    private long next = 0, end = 0;                       // this server's current block: [next, end)

    IdRangeAllocator(SharedCounter counter) { this.counter = counter; }

    synchronized long nextId() {
        if (next == end) {                                // block used up (or first call): lease the next one
            end = counter.addAndGet(BLOCK);
            next = end - BLOCK;
        }
        return next++;
    }
}

One counter round trip now covers 1,000 links. If a server crashes halfway through its block, the rest of that block is never issued - the code space gets a gap, which is harmless: codes must be unique, not contiguous or ordered. (Flickr's "ticket servers" use a related trick: two MySQL servers hand out odd and even IDs respectively, so one can fail without stopping ID generation.)

class SnowflakeIds {
    private static final long EPOCH = 1_735_689_600_000L;   // 2025-01-01T00:00:00Z, a custom epoch
    private final long workerId;                             // 0..1023, unique per running generator
    private long lastMs = -1, sequence = 0;

    SnowflakeIds(long workerId) { this.workerId = workerId; }

    synchronized long nextId() {
        long now = System.currentTimeMillis();
        if (now < lastMs) throw new IllegalStateException("clock moved backwards");   // would reissue old IDs
        if (now == lastMs) {
            sequence = (sequence + 1) & 4095;                // 12 bits
            if (sequence == 0) {                             // 4,096 IDs already issued this millisecond
                while ((now = System.currentTimeMillis()) <= lastMs) { }   // spin to the next millisecond
            }
        } else {
            sequence = 0;
        }
        lastMs = now;
        return ((now - EPOCH) << 22) | (workerId << 12) | sequence;
    }
}

Second flavor: hashing the long URL

Some products want "the same long URL always gets the same code." Hashing does that naturally: MD5(longUrl) is a function of the URL. But its 128 bits don't fit in 6 characters, and 6 base62 characters keep only about 36 of them - so different URLs start colliding just as random codes do (a 50% chance of at least one clash after roughly 280,000 links, by the birthday bound). The hash design still needs clash handling: on a clash, re-hash with a salt (longUrl + "#1", and so on).

The counter design gets deduplication differently - an index on the long URL, looked up before issuing a new ID. That's an extra read per write, paid only if the product needs it.

Whichever generator you use, let the database enforce uniqueness. A UNIQUE (or primary-key) constraint on code turns check-then-insert into one atomic insert that either succeeds or reports a duplicate you can retry - no separate exists read, no race. The same constraint catches custom aliases such as /abc12 that happen to equal a code the generator produces later; many services also keep aliases out of the generator's space entirely, for example by requiring a -, which base62 never emits.

The read path

GET /aZ3kQ9
  -> load balancer -> any app server (stateless)
       -> cache: code -> longUrl             hit  -> 302, Location: longUrl
       -> miss: database lookup by code      -> put in cache -> redirect
       -> not in the database                -> 404

• Cache-aside fits unusually well. Reads dominate, clicks are heavily skewed toward a few hot links, and a code's destination rarely changes - so a cache far smaller than the dataset serves most requests, and invalidation is rare. An LRU cache keeps the hot set.
• Unknown codes are the blind spot. Cache-aside only stores what it found, so a code that doesn't exist misses every time and reaches the database. Caching "not found" for a short TTL handles repeated bad codes; a flood of distinct made-up codes needs a Bloom filter of existing codes (it has no false negatives, so "definitely absent" can skip the database) and per-client rate limits.
• App servers stay stateless. Any server can handle any request because shared state lives in the database, the cache and the ID counter, so scaling out means adding servers behind the load balancer. State that is disposable is fine - a leased ID block. State a request depends on is not - click counts kept in one server's memory are split across servers and lost on restart. Send click events to a shared store or a queue instead.

301 or 302?

A shortener that sells analytics, lets users edit links or must take down phishing links sends 302 (or 307). One that only wants the least load can send 301 - preferably with a bounded Cache-Control: max-age, so a cached redirect eventually expires.

Partitioning the data

At ~3 TB and growing, the table is split across shards. Nearly every query is a point lookup by code, so the shard key is the code (or its ID): hash(code) mod N sends each lookup to exactly one shard and spreads writes evenly. Sharding by ID range looks natural with a counter, but every new ID falls in the highest range, so the newest shard takes all the inserts. Sharding by the destination's domain puts every link to a popular site on one shard - and a lookup by code wouldn't know which shard to ask.

Where it breaks

• The cache goes down. With a 98% hit rate, the database serves 2% of reads. Lose the cache and it gets 50 times its usual load - a cache outage becomes a database outage. Replicate the cache, and plan a degraded mode: read replicas, request coalescing, shedding load rather than collapsing.
• Sequential codes are guessable. Base62 is an encoding, not encryption. Someone holding aZ3kQ9 can try aZ3kQA and walk through other people's links, including "unlisted" ones. Scramble the ID before encoding and rate-limit lookups - or use long random codes for links that must stay private.
• Abuse. Short links hide their destination, which makes them useful for phishing and spam. Check destinations against a blocklist when links are created, rate-limit creation, and keep takedowns effective - one more reason for 302.
• Clock trouble for timestamp-based IDs (see Snowflake above).

Tradeoffs

For redirects: 302 for analytics, edits and takedowns; 301 for the least load.

Going further. The deep dive (next tab) takes the design global: serving several regions and the replication-lag 404, redirects at the CDN edge, the click-analytics pipeline, viral links and request coalescing, choosing the store, deletion and code reuse, and private links.

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. The estimate says ~40 writes/s and ~4,000 reads/s. A teammate wants to shard the database on day one "for write throughput". What do you say?

2. Why doesn't the counter design need exists(code) before inserting, while random codes do?

3. A link was served with 301 and no Cache-Control header. Its owner changes the destination, and some users still reach the old page. Why, and what should the service have done?

Key takeaways

• Estimate first: ~40 writes/s against ~4,000 reads/s says optimize reads; 6 billion links × 500 bytes ≈ 3 TB says partition eventually; 62^6 ≈ 56.8 billion says 6 characters are enough for a dense counter.
• Base62-encode a unique ID: unique by construction, no clash-check read. Leased ID ranges take the counter off the hot path; Snowflake removes coordination but lengthens codes to 9-11 characters.
• Let a UNIQUE constraint on the code settle races, retries and custom-alias clashes.
• Cache-aside on the read path, with a plan for unknown codes (Bloom filter, negative caching, rate limits), and stateless app servers.
• Shard by a hash of the code; consistent hashing makes adding a node move about 1/N of the keys instead of most of them.
• 302 keeps analytics, edits and takedowns working; 301 saves load, but browsers remember it.
• Sequential codes are guessable - scramble them, or use long random codes for anything meant to stay private.