CS Fundamentals Trainer · Guides

Design a URL shortener

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

16 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.

• Create: given a long URL, return a short one. Optionally let the user choose the alias (sho.rt/summer-sale) and an expiry date.
• Redirect: given a short code, send the visitor to the long URL, fast.
• Maybe: click statistics, accounts, editing or deleting links, QR codes.

Then the qualities that decide the design:

• Reads dwarf writes. A link is created once and followed many times. Ratios of 100 reads to 1 write are a common assumption.
• Redirects must be fast and available. A slow redirect is felt by every visitor on every click. It is better to serve an old destination than to show an error.
• Codes must be short, unique, and hard to guess if links are meant to be private-ish.
• Links live a long time. Printed on paper or buried in old emails, they must keep working for years.

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.

What these numbers say:

• 39 writes per second is tiny. Any database handles it. The write path is not the hard part.
• 3 900 reads per second is modest, 39 000 at peak is not. That is where a cache and a good read path pay off.
• 3 TB fits on one machine's disk, but not comfortably in memory. The data is small enough that sharding is an option you plan, not a day-one need.

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:

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].

• 301 Moved Permanently tells browsers and caches that the short link will always lead there. They may remember it and skip your server on later visits. That saves you traffic, but you lose the click count (the request never arrives), and you cannot change the destination for people who already cached it.
• 302 Found (or 307, which also forbids changing the request method) says "for now". The visitor asks you every time, so you can count clicks, change the destination, expire the link, and block it if it turns out to be malicious.

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.

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")

ON CONFLICT DO NOTHING [3] makes the check and the insert one atomic step. Two requests that draw the same code at the same moment cannot both win. Checking with a SELECT first and inserting afterwards would leave exactly that gap.

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.

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:

• Relational (PostgreSQL, MySQL): you probably have one already, you get transactions and constraints, and 3 TB with a primary key index is routine. Choose this unless you have a reason not to.
• Key-value store: easier to spread over many machines when you outgrow one, and built for exactly this access pattern. The price is giving up the flexible queries you will want later for reports and abuse handling.

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

• Cache code → long URL in Redis (or Memcached). A small number of links gets most of the clicks, so a cache holding a fraction of all links can answer the large majority of requests. Evict with least-recently-used [5]. See caching strategies for patterns and failure modes.
• Cache misses for unknown codes too, briefly (a few seconds to a minute). Bots love to probe random codes; without this every probe goes to the database.
• A CDN can serve redirects if you use a cacheable status and a short Cache-Control. The price is the same as with 301: the edge answers without telling you, so your click counts are missing. Many services choose to keep clicks counted and skip the CDN for redirects.
• Keep the handler tiny. Look up, set the Location header, return. No sessions, no templates, no extra queries.

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

• Expiry: on lookup, compare expires_at with the current time and answer 410 Gone (or 404) if the link is over. Put the same time limit on the cache entry, so a cache cannot keep an expired link alive. A nightly job can delete old rows in batches to keep the table small.
• Deleting: remove the row and delete the cache key. A visitor with an old cached 301 still gets through, which is one more reason to avoid 301 for links that can be deleted.
• Re-using codes: do not give an expired code to someone else too soon. Old emails and printed pages still point to it, and the new owner would receive visitors meant for somebody else. With trillions of codes there is no need to recycle.

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.

• Accept only http and https URLs. A stored javascript: or data: URL turns your redirect into an attack. Parse the URL properly, do not just check the start of the string.
• Do not redirect to yourself, or to other shorteners, which creates loops and chains.
• Check destinations against a list of known bad sites (for example Google Safe Browsing) when a link is created, and again later, because a harmless page can be swapped for a harmful one. Keep the ability to disable a code at once.
• Rate-limit creation per account and per IP, or your service becomes a free spam relay. See design a rate limiter.
• Mind open redirect rules. Your whole product is an open redirect by design, so the usual advice (never redirect to a user-supplied URL) cannot apply as is. The protections above, plus an interstitial "you are leaving..." page for flagged links, are the substitute [4].

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.

10. 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.

"How do you handle a viral link?"

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".

11. Things to mention in an interview

• Start with requirements and numbers, and say that the read path matters more than the write path.
• Call out 301 versus 302, and tie it to analytics.
• Compare the ID options and say why you pick one; mention the collision probability and the atomic insert.
• Show the cache in front of a key-value style lookup, and talk about hot keys.
• Bring up abuse before you are asked.
• Keep analytics off the redirect path.

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. Atomic insert-or-skip.
4. OWASP, Unvalidated Redirects and Forwards Cheat Sheet.
5. Redis documentation, Key eviction. Least-recently-used and other policies for the redirect cache.

Practise this topic: System Design Resilience & Scalability Data scaling

More guides