CS Fundamentals Trainer · Guides

Design a URL shortener

Short codes, 301 vs 302, collisions, caching, abuse, and counting clicks without slowing the redirect.

23 min read

A URL shortener turns https://example.com/some/very/long/path?with=parameters into https://sho.rt/Xk3b9Qa and sends visitors who open the short link to the long one. It is a favourite system design question because the idea fits in one sentence, and yet it touches almost everything: ID generation, the choice of database, caching, HTTP semantics, abuse, and analytics.

1. Pin down the problem

Start by agreeing on what the service must do, and what it may leave out.

Then the qualities that decide the design:

The write path can be slow and careful. The read path must be fast and almost always up. Design them separately.

2. Back-of-the-envelope numbers

Assume 100 million new links a month and 100 redirects for every link created. These are round numbers, so we can check each step.

QuantityCalculationResult
New links per second100 million / (30 × 86 400 s)about 39 per second
Redirects per second39 × 100about 3 900 per second on average
Peak redirectsassume 10 × the averageabout 39 000 per second
Links in 5 years100 million × 12 × 56 billion
Storage6 billion × about 500 bytes (URL, code, dates, owner)about 3 TB

What these numbers say:

How long must the code be?

A code made of the 62 characters 0-9, A-Z and a-z ("base62") has 62^n possibilities for n characters:

LengthPossible codes
662^6 = 56 800 235 584 (about 57 billion)
762^7 = 3 521 614 606 208 (about 3.5 trillion)

Six billion links fit in 6 characters, with room to spare. Seven characters give a safety margin of almost 600 times, so 7 is the usual choice. It is short enough to type, and long enough that guessing a valid code is hopeless.

3. The two operations

A small API is enough:

POST /api/links      { "url": "https://example.com/a/very/long/path", "alias": "optional", "expires_at": "optional" }
                  →  201 { "code": "Xk3b9Qa", "short_url": "https://sho.rt/Xk3b9Qa" }

GET  /Xk3b9Qa     →  redirect to the long URL (or 404 if unknown)

Diagram: Creating a link and following it

301 or 302?

The redirect status code is a real design decision, not a detail. Both are defined in RFC 9110, section 15.4 [1].

There is also a search engine side. A 301 tells crawlers that the destination is the real address, so links that point at your short URL are credited to it, and it is a common reason marketing teams ask for a 301. A 302 may leave the short URL in the index for a while. Google says that redirects do not lose ranking signals [7], so this is a point in favour of 301 and not a disaster for 302.

If you offer statistics, editing, or expiry, use a temporary redirect. Choose 301 only for links that really are permanent and where you do not count clicks. Even then, remember that a cached 301 is very hard to take back.

4. Making the code

This is the part interviewers like to dig into. There are four common ways, each with a catch.

ApproachHow it worksCatch
Hash and cutHash the long URL (MD5, SHA-256), keep the first 7 characters in base62Different URLs can collide after cutting, so you must check and retry. The same URL always gives the same code, which is nice for deduplication and bad when two users want separate statistics
Random codeDraw 7 random base62 charactersCollisions are rare but real. You need a uniqueness check, which the database does for free
Counter, then base62Take the next number from a counter and write it in base62No collisions at all, but codes are guessable and enumerable (1, 2, 3...), and the counter is a shared resource
Snowflake-style idsA 64-bit number made of a timestamp, a machine number and a per-millisecond sequence, then written in base62No coordination and no collisions, but the code is 10 or 11 characters and roughly time-ordered, so it is neither short nor secret
Pre-made key rangesA key service hands each app server a block of numbers (say 1 000 000 at a time) to use up locallyFast and collision-free, but still sequential unless you scramble the numbers. A server crash wastes the rest of its block, which is fine: we have trillions

A simple, solid choice for a first version is random codes with a unique key in the database. Let the database be the judge of uniqueness.

How often will random codes collide?

If there are already N codes stored out of 62^7 possible ones, a new random code hits an existing one with probability N / 62^7. With 6 billion links stored:

6 000 000 000 / 3 521 614 606 208 ≈ 0.0017  (about 0.17 %)

About one insert in 600 needs a second attempt at the very end of the five years, and almost none at the start. So the rule is simple: try the insert, and if the code already exists, draw another. After a few failed attempts, give up with an error (or switch to a longer code). This is the birthday problem in a friendly form: it only bites when you compare many codes with each other, not when each new code meets a table that already exists [2].

import secrets

ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"


def random_code(length=7):
    # secrets (not random) so that codes cannot be predicted
    return "".join(secrets.choice(ALPHABET) for _ in range(length))


def create_link(db, long_url):
    for _ in range(5):
        code = random_code()
        row = db.execute(
            "INSERT INTO links (code, long_url) VALUES (%s, %s) "
            "ON CONFLICT (code) DO NOTHING RETURNING code",
            (code, long_url),
        ).fetchone()
        if row:                      # the code was free and is now ours
            return code
    raise RuntimeError("could not find a free code")

The unique key makes the check and the insert one step: the primary key guarantees that only one of two inserts of the same code can succeed, and ON CONFLICT DO NOTHING turns the loser into an empty result instead of an error. RETURNING gives back only the rows that were really inserted [3], so an empty result means "try another code". Checking with a SELECT first and inserting afterwards would leave a gap between the two statements that two requests can slip through.

Counters and base62

If you prefer numbers, you need to write them in base62. This is the conversion in four languages (pick a language on the tabs; your choice is remembered):

ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"


def encode(n):
    if n == 0:
        return ALPHABET[0]
    digits = []
    while n:
        n, rest = divmod(n, 62)
        digits.append(ALPHABET[rest])
    return "".join(reversed(digits))
const alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

func Encode(n uint64) string {
	if n == 0 {
		return string(alphabet[0])
	}
	var buf [11]byte // the largest uint64 needs 11 base62 digits
	i := len(buf)
	for n > 0 {
		i--
		buf[i] = alphabet[n%62]
		n /= 62
	}
	return string(buf[i:])
}
const ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

// n is a BigInt, so ids above 2^53 stay exact
function encode(n) {
  if (n === 0n) return ALPHABET[0];
  let out = "";
  while (n > 0n) {
    out = ALPHABET[Number(n % 62n)] + out;
    n /= 62n;
  }
  return out;
}
public static string Encode(ulong n)
{
    const string alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    if (n == 0) return alphabet[0].ToString();
    var chars = new char[11];            // the largest ulong needs 11 base62 digits
    int i = chars.Length;
    while (n > 0)
    {
        chars[--i] = alphabet[(int)(n % 62)];
        n /= 62;
    }
    return new string(chars, i, chars.Length - i);
}

Some values to check an implementation against: encode(0) is 0, encode(61) is z, encode(62) is 10, and encode(62^7 - 1) is zzzzzzz.

A plain counter gives 1, 2, 3: anyone can walk through all your links. If links must not be guessable, either use random codes, or scramble the number first with a reversible mix (multiply by a large odd number that shares no factor with 62^7, modulo 62^7). Do not use "security by obscurity" for truly private content: a shortener is not an access control system. Put real secrets behind a login.

Snowflake-style ids

Systems that must hand out unique ids from many machines without a shared counter often use the Snowflake layout, which Twitter made popular [6]. A 64-bit number is cut into three parts: 41 bits of milliseconds since a start date of your choice (about 69 years), 10 bits for the machine (1 024 machines), and 12 bits for a sequence number (4 096 ids per millisecond per machine). Every machine can make ids on its own, the ids rise with time, and they never collide as long as no two machines share a number and no clock goes backwards.

import threading
import time

EPOCH_MS = 1_700_000_000_000          # your own start date, so the 41 bits last longer


class Snowflake:
    def __init__(self, machine_id):
        assert 0 <= machine_id < 1024
        self.machine_id = machine_id
        self.last_ms = -1
        self.seq = 0
        self.lock = threading.Lock()

    def next(self):
        with self.lock:
            now = int(time.time() * 1000)
            if now < self.last_ms:
                raise RuntimeError("the clock went backwards")   # refuse rather than risk a duplicate
            if now == self.last_ms:
                self.seq = (self.seq + 1) & 4095
                if self.seq == 0:                                # 4 096 ids this millisecond: wait
                    while now <= self.last_ms:
                        now = int(time.time() * 1000)
            else:
                self.seq = 0
            self.last_ms = now
            return ((now - EPOCH_MS) << 22) | (self.machine_id << 12) | self.seq

For a shortener this is the wrong tool, for two reasons. The number is large, so its base62 form has 10 or 11 characters instead of 7, which is long for a "short" link. And it starts with a timestamp, so anyone can tell when a link was made and guess its neighbours. Use it where unique ids matter more than short or secret ones (for example, the internal primary key of a link or a click), and keep the public code separate. The same goes for UUIDs and ULIDs: unique, but too long.

Custom aliases

For sho.rt/summer-sale, accept the user's text but treat it like any other code: same unique key, same atomic insert, and a clear "that name is taken" answer on conflict. Restrict the allowed characters and length, and keep a list of reserved words (api, admin, login, static...) so a user cannot shadow your own routes.

5. Where the data lives

One table is enough:

CREATE TABLE links (
  code        text PRIMARY KEY,                  -- the unique key is also the index we read by
  long_url    text NOT NULL,
  owner_id    bigint,                            -- null for anonymous links
  created_at  timestamptz NOT NULL DEFAULT now(),
  expires_at  timestamptz                        -- null means never
);

The only query on the hot path is "give me the row for this code", a lookup by primary key. That fits any relational database, and it fits key-value stores (DynamoDB, Cassandra, Redis) just as well, because there are no joins and no range queries. Both are fine answers. The honest reasons to choose:

Codes are case-sensitive: check the collation

Xk3b9Qa and xk3b9qa are different codes in base62, and the database must agree. PostgreSQL compares text exactly by default, so the table above is correct there. MySQL and SQL Server use case-insensitive collations by default, so the two codes would count as the same key: lookups would find the wrong row, and the unique key would reject codes that are really free. In MySQL, declare the column with a binary collation (code VARCHAR(11) CHARACTER SET ascii COLLATE ascii_bin). In any database, write a test that stores aB and Ab and expects two rows.

If your store is case-insensitive and you cannot change it, use an alphabet without upper case (36 characters: 0-9a-z). Then 36^7 is only 78 billion, which would make collisions common at 6 billion links (about 8 %), so move to 8 characters (2.8 trillion).

When one database is not enough

Reads are easy to scale: add replicas, and put a cache in front (next section). If writes or storage outgrow one machine, split the table by code. Because lookups always arrive with the full code, you can shard by a hash of the code, and every request goes to exactly one shard. Use consistent hashing so that adding a shard moves only a small share of the data.

6. Making redirects fast

A redirect is a read of one small value by key, repeated for the same popular links over and over. That is the ideal case for a cache.

Diagram: The redirect path, from fastest to slowest

Rough check: if the cache answers 95 % of the 39 000 peak requests per second, the database sees about 2 000 per second. A single primary-key lookup is cheap, so a modest database server (or a couple of replicas) copes.

7. Expiry, deletion, and codes that come back

8. Abuse and safety

A shortener is a perfect tool to hide a malicious link, so safety is part of the design, not an extra.

9. Counting clicks without slowing the redirect

If you want statistics, the redirect must not wait for them. Instead of updating a counter in the database for each click (a write on the hottest path), put a small event on a queue and answer the visitor immediately:

Diagram: Clicks are counted after the visitor has left

Workers add up the events in batches (counts per code per hour), and the dashboard reads the totals. If the queue is down for a moment, you lose a few counts and not a single redirect. That is the right trade for this feature. Count approximately and cheaply; do not make the product depend on your analytics.

Expect a lot of the traffic to be machines. Crawlers, security scanners, and the link-preview fetchers of chat and social apps (they open a link the moment someone pastes it) all follow short links, and a browser may prefetch one. Record the User-Agent and whether the request was a GET or HEAD, filter known bots in the worker, not on the hot path, and report "human clicks" separately from "all requests". Otherwise the first message you share looks like a viral link.

10. Testing, monitoring, and reliability

Tests worth writing

What to watch

SignalWhy
Redirect latency (p50, p99) and error rateThe product is the redirect. Alert on the p99, not the average
Cache hit ratioA fall means a deploy changed the keys, or a scan is in progress
Share of 404sA rise is a scanner or bot probing codes
Create retries (collisions) per 1 000 createsThe share is about N / 62^7, so a rise is a sign that the space is filling or the generator is biased
Click queue lagCounts are late, never the redirect
Disk used, per replicaGrowth is steady, so alert early
Flagged and disabled linksHow well the abuse process works

What happens when something fails

11. Questions interviewers like to add

"What if two users shorten the same URL?"

Both designs are valid. Give each user their own code (simple, and they get separate statistics), or deduplicate by hashing the URL and returning the existing code (saves space, but statistics and ownership get tangled). Say which one you chose and why.

One code receiving a huge share of traffic is a hot key. A CDN or an in-process cache on every app server absorbs it, because the value is tiny and changes rarely. No shard should be asked for the same row 50 000 times a second.

"What happens when the cache is empty after a restart?"

All traffic hits the database at once. Warm the cache from the most-clicked links first, or let the first request for each code fill it, and make sure only one request per code goes to the database at a time (see the stampede section of the caching guide).

"How would you make it work in several regions?"

Reads are easy to replicate: put read replicas and caches near the visitors. Writes can go to one region, since there are only about 39 per second. Newly created links need a moment to appear in other regions, so it is common to serve the creator from the write region, or to fall back to the primary when a replica says "not found".

12. Things to mention in an interview

Quick recap

  1. Reads are about 100 times more common than writes, so optimise the redirect path.
  2. A 7-character base62 code gives 3.5 trillion possibilities: enough for years.
  3. Use a temporary redirect (302 or 307) if you count clicks or allow edits.
  4. Random codes with a unique key and an atomic INSERT ... ON CONFLICT are simple and safe; counters are collision-free but guessable.
  5. One table keyed by code is enough. Cache it, replicate it, and shard by code only when you must.
  6. Validate URLs, rate-limit creation, and keep a kill switch.
  7. Count clicks asynchronously.

Sources

  1. IETF, RFC 9110, section 15.4: Redirection 3xx. The meaning of 301, 302, 307 and 308, and which may be cached.
  2. Wikipedia, Birthday problem. Why collisions appear sooner than intuition says when codes are compared with each other.
  3. PostgreSQL documentation, INSERT: the ON CONFLICT clause. DO NOTHING, and RETURNING giving only the rows actually inserted.
  4. OWASP, Unvalidated Redirects and Forwards Cheat Sheet.
  5. Redis documentation, Key eviction. Least-recently-used and other policies for the redirect cache.
  6. Wikipedia, Snowflake ID. The 41/10/12 bit layout.
  7. Google Search Central, Redirects and Google Search. How crawlers treat permanent and temporary redirects.

Practise this topic: System Design System Design › Case studies

More guides