24 — A URL shortener

A URL shortener maps a short code to a long URL, and redirects anyone who follows the code. It is small enough to design completely, and it still has real decisions in it: how to generate codes without collisions, which redirect status to send, how much a cache helps, and how to stop the service being used to spread malicious links. It follows the process from chapter 23.

Requirements

Functional.

1. Create a short link for a long URL, optionally with a custom alias and an expiry time.
2. Redirect a short link to its long URL.
3. Disable a link, by its owner or by an abuse team.
4. Report click counts per link, a few minutes behind.

Non-functional.

Out of scope: editing the target of an existing link, link-in-bio pages, and per-user dashboards beyond counts.

Estimates

Every input here is an assumption (chapter 4).

redirects_per_day = 100_000_000   # assumption
creates_per_day = 1_000_000       # assumption
peak_factor = 3                   # assumption: peak hour is 3x the daily average
bytes_per_link = 500              # assumption: code, URL, owner, timestamps, index overhead
years = 5

avg_reads = redirects_per_day / 86_400
avg_writes = creates_per_day / 86_400
print(f"average redirects/s: {avg_reads:,.0f}, peak: {avg_reads*peak_factor:,.0f}")
print(f"average creates/s:   {avg_writes:,.1f}, peak: {avg_writes*peak_factor:,.1f}")
links = creates_per_day * 365 * years
print(f"links after {years} years: {links:,}")
print(f"storage after {years} years: {links*bytes_per_link/1e9:,.0f} GB")
print(f"read:write ratio: {redirects_per_day/creates_per_day:.0f}:1")

average redirects/s: 1,157, peak: 3,472
average creates/s:   11.6, peak: 34.7
links after 5 years: 1,825,000,000
storage after 5 years: 912 GB
read:write ratio: 100:1

Three things follow from these numbers.

• Writes are tiny. 35 inserts a second at peak is a small fraction of the 2,000 queries a second that chapter 6 works out for one modest connection pool. Write scaling isn’t the problem.
• Reads dominate, 100 to 1. The design is mostly about the redirect path, and caching is the main tool.
• Storage grows to under a terabyte in five years. That fits one database server with room to spare, with read replicas for availability (chapter 12). Partitioning by code (chapter 11) is a later option, not a starting requirement.

API

POST   /links                 {"url": "...", "alias": "...", "expires_at": "..."}
       Idempotency-Key: <client-generated UUID>
       -> 201 {"code": "TIr20PI", "short_url": "https://sho.rt/TIr20PI"}

GET    /{code}                -> 302, Location: <long URL>
                              -> 404 if unknown, 410 if disabled or expired

DELETE /links/{code}          -> 204 (marks the link disabled)

GET    /links/{code}/stats    -> {"clicks": 1234, "as_of": "..."}

The Idempotency-Key makes a retried create return the same code instead of making a second link (chapter 15). Creation also passes through a rate limiter keyed by account (chapter 22).

Data model

There are two access patterns that matter: look up a link by code (very often), and insert a link (rarely). The source of truth is one PostgreSQL table:

CREATE TABLE links (
    code         text        PRIMARY KEY,
    target_url   text        NOT NULL,
    owner_id     bigint,
    created_at   timestamptz NOT NULL DEFAULT now(),
    expires_at   timestamptz,
    disabled_at  timestamptz
);

CREATE TABLE create_requests (                 -- idempotency keys
    owner_id         bigint NOT NULL,
    idempotency_key  uuid   NOT NULL,
    code             text   NOT NULL REFERENCES links(code),
    PRIMARY KEY (owner_id, idempotency_key)
);

CREATE INDEX links_owner ON links (owner_id, created_at DESC);

The redirect path reads only links by primary key. The owner index serves “my links” pages. Click counts don’t live in this table: updating a counter row on every click would put a hot row under the most popular links, and it would add a write to every redirect. Counts are aggregated elsewhere, as described below.

Topology

                 +-----+     +-----------------+     +-------+     +------------+
 browser ------> | CDN | --> | redirect service| --> | Redis | --> | PostgreSQL |
                 +-----+     +-----------------+     +-------+     |  primary + |
                                    |                              |  replicas  |
                                    v  click events                +------------+
                              [log stream] --> [aggregator] --> click counts
 API client --> [create service] --> rate limit, URL checks --> PostgreSQL primary

The redirect service and the create service are separate deployments of stateless code, so a flood of creates can’t slow redirects. Redirect reads go to Redis first, then to a replica. Creates go to the primary.

Generating codes

How long a code needs to be

Codes use 62 characters (0-9, A-Z, a-z).

6 chars: 56,800,235,584 codes, 35.7 bits
7 chars: 3,521,614,606,208 codes, 41.7 bits
8 chars: 218,340,105,584,896 codes, 47.6 bits

Seven characters give about 3.5 trillion codes. The five-year estimate of 1.8 billion links uses 0.05% of that space.

Three ways to choose a code

Hashing the URL looks attractive because it removes duplicates, but truncating a hash to 42 bits gives exactly the same collision behavior as random codes, so it still needs the check. It also gives every user who shortens the same URL the same link, which mixes their click counts and lets one user’s disable affect another’s link. If deduplication is wanted, it’s better done with a separate unique index on (owner_id, target_url).

Random codes and the birthday paradox

With random codes, the chance that some two codes collide grows much faster than intuition suggests. For a space of $N$ codes, a 50% chance of at least one collision arrives after about

$\sqrt{2N \ln 2}$

codes. A program checked this against simulation:

import math, random, statistics

N = 62**7
print(f"formula, 50% chance of a collision after {math.sqrt(2*N*math.log(2)):,.0f} codes")

def draws_until_collision(rng):
    seen = set()
    while True:
        c = rng.randrange(N)
        if c in seen:
            return len(seen) + 1
        seen.add(c)

rng = random.Random(7)
runs = [draws_until_collision(rng) for _ in range(200)]
print(f"simulated, median of 200 runs: {statistics.median(runs):,.0f} codes "
      f"(min {min(runs):,}, max {max(runs):,})")

for K in (10**6, 10**8, 365 * 10**6, 1_825 * 10**6):
    p = K / N
    print(f"stored {K:>13,}: P(new code collides) = {p:.6%}, "
          f"expected collisions so far = {K*K/(2*N):,.1f}")

formula, 50% chance of a collision after 2,209,524 codes
simulated, median of 200 runs: 2,372,306 codes (min 189,412, max 6,422,487)
stored     1,000,000: P(new code collides) = 0.000028%, expected collisions so far = 0.1
stored   100,000,000: P(new code collides) = 0.002840%, expected collisions so far = 1,419.8
stored   365,000,000: P(new code collides) = 0.010365%, expected collisions so far = 18,915.3
stored 1,825,000,000: P(new code collides) = 0.051823%, expected collisions so far = 472,883.2

The 200 runs vary widely, from 0.19 million to 6.4 million, so their median is a noisy estimate. The same simulation on a smaller space ($62^4$, 14.8 million codes) with 20,000 runs gave a median of 4,538 against a formula value of 4,526, and 49.8% of runs had collided by the formula’s count. The formula holds.

So a first collision is likely after only about 2.2 million links, a few days of traffic at the assumed rate. That is why random codes need a uniqueness check. But the second half of the output matters more for running the service: even after five years, a new random code collides with an existing one 0.05% of the time. Collisions are certain overall (about 470,000 of them in five years) but each insert rarely needs more than one try.

The check has to be atomic. Reading first and inserting second has the same race as the rate limiter in chapter 22: two servers can both see a code as free. The primary key does the check inside the insert:

INSERT INTO links (code, target_url, owner_id, expires_at)
VALUES ($1, $2, $3, $4)
ON CONFLICT (code) DO NOTHING
RETURNING code;

If no row comes back, the code was taken, and the service picks another and tries again. PostgreSQL’s INSERT documentation describes ON CONFLICT DO NOTHING as skipping the insert instead of raising a unique violation.

Counters, and shuffling them

A counter can’t collide, and needs no retry. PostgreSQL’s sequences (nextval) supply one, and to avoid a round trip per link, each create server can reserve a block of values at a time, as in chapter 11. The problem is that consecutive codes (0000001, 0000002, …) reveal how many links exist and let anyone walk through all of them.

A shuffled counter keeps the no-collision property and hides the order. The counter goes through a keyed permutation of the code space before encoding. A Feistel network is a standard way to build a permutation of a range of a chosen size: it is reversible by construction, whatever its round function. This one works on 42 bits, which is slightly more than $62^7$, and uses cycle walking: if the result is outside the code space, it applies the permutation again until it lands inside.

import hashlib, hmac

ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
N = 62**7          # size of the code space
HALF_BITS = 21     # a Feistel network over 42 bits; 2**42 > 62**7

def base62(n, width=7):
    out = []
    for _ in range(width):
        n, r = divmod(n, 62)
        out.append(ALPHABET[r])
    return "".join(reversed(out))

def _round(key, i, half):
    mac = hmac.new(key, f"{i}:{half}".encode(), hashlib.sha256).digest()
    return int.from_bytes(mac[:4], "big") & ((1 << HALF_BITS) - 1)

def feistel(key, x, rounds=4):
    mask = (1 << HALF_BITS) - 1
    left, right = x >> HALF_BITS, x & mask
    for i in range(rounds):
        left, right = right, left ^ _round(key, i, right)
    return (left << HALF_BITS) | right

def shuffle(key, counter):
    x = feistel(key, counter)
    while x >= N:              # cycle walking
        x = feistel(key, x)
    return x

key = b"keep-this-secret"
print("counter  plain     shuffled")
for c in range(1, 6):
    print(f"{c:>7}  {base62(c)}  {base62(shuffle(key, c))}")

sample = range(1_000_000)
codes = {shuffle(key, c) for c in sample}
print(f"distinct codes for {len(sample):,} counters: {len(codes):,}")
print(f"all inside the code space: {all(c < N for c in codes)}")

counter  plain     shuffled
      1  0000001  TIr20PI
      2  0000002  NpigzrE
      3  0000003  aTxmpI1
      4  0000004  GiXUwQK
      5  0000005  3kQ6bA8
distinct codes for 1,000,000 counters: 1,000,000
all inside the code space: True

A million counters gave a million distinct codes, all in range. Since $2^{42} / 62^7 \approx 1.25$, cycle walking applies the permutation 1.25 times on average. The key has to stay secret and fixed: changing it would change the code for every future counter value, and could reissue a code already in use.

Which to choose

At 35 creates a second, all three work. Random codes with ON CONFLICT are the simplest: no sequence, no key to manage, and the retry rate stays under 0.1% for years. A shuffled counter suits a system that wants no retries at all, or that generates codes somewhere without access to the unique index. A plain counter is only reasonable when codes being sequential doesn’t matter.

Custom aliases go through the same insert, and a conflict is reported to the user rather than retried. Aliases also need a reserved list (api, login, admin and similar) so that they don’t shadow the service’s own paths.

Redirect status: 301 or 302

The redirect is an HTTP response with a Location header. The status code decides who may cache it. RFC 9110 defines the codes, and lists 301 and 308 among the status codes that are “heuristically cacheable”: a cache may reuse them even without explicit freshness information. 302 and 307 aren’t on that list.

For a shortener, the trade-off is this:

• 301 lets browsers and intermediaries cache the redirect. Repeat clicks may never reach the service, which saves load, but those clicks aren’t counted, and a link disabled for abuse keeps working for anyone who has it cached.
• 302 sends every click to the service (or to the CDN), which keeps counts accurate and makes disabling immediate.

Leaving caching to the status code is fragile. Explicit Cache-Control headers (RFC 9111) say exactly what is wanted, whichever code is used. A reasonable choice is a 302 with Cache-Control: private, max-age=0 for links that are counted, which keeps browsers from caching. If the CDN should cache redirects for a short time, s-maxage sets a lifetime for shared caches only. The CDN’s own logs then carry the click counts for those requests, and disabling a link needs a CDN purge.

Caching the redirect path

Redirects are a cache’s best case: keys are immutable (a code’s target never changes in this design), values are small, and popularity is very uneven. How much a cache helps depends on how uneven. A simulation with one million links, Zipf-distributed requests with three different exponents, and an LRU cache, measured after a warm-up:

import bisect, itertools, random
from collections import OrderedDict

LINKS = 1_000_000      # links in the working set
REQUESTS = 2_000_000   # the first half warms the cache, the second half is measured

def zipf_sampler(n, s, rng):
    cum = list(itertools.accumulate(1 / (k ** s) for k in range(1, n + 1)))
    total = cum[-1]
    return lambda: bisect.bisect_left(cum, rng.random() * total)

def lru_hit_rate(sample, capacity):
    cache, hits = OrderedDict(), 0
    for i in range(REQUESTS):
        key = sample()
        if key in cache:
            cache.move_to_end(key)
            hit = True
        else:
            cache[key] = True
            if len(cache) > capacity:
                cache.popitem(last=False)
            hit = False
        if i >= REQUESTS // 2:
            hits += hit
    return hits / (REQUESTS // 2)

print("exponent  cache 0.1%  cache 1%  cache 10%")
for s in (0.8, 1.0, 1.2):
    row = []
    for share in (0.001, 0.01, 0.1):
        sample = zipf_sampler(LINKS, s, random.Random(42))
        row.append(lru_hit_rate(sample, int(LINKS * share)))
    print(f"{s:>8}  " + "  ".join(f"{r:>9.1%}" for r in row))

exponent  cache 0.1%  cache 1%  cache 10%
     0.8      10.0%      23.2%      48.7%
     1.0      40.3%      58.5%      77.9%
     1.2      75.9%      87.5%      94.8%

The exponent matters more than the cache size. With an exponent of 1.2, caching 0.1% of links serves three quarters of redirects. With 0.8, a cache a hundred times larger does worse. The exponent isn’t something to assume. It can be measured from a day of redirect logs by plotting request count against popularity rank on log-log axes, where the slope is the exponent.

The cache is cheap either way. Caching the hottest 1% of 1.8 billion links is 18.25 million entries. At an assumed 200 bytes per entry, that is about 3.6 GB, which fits in one Redis instance’s memory, with a replica for failover.

Two details matter on this path:

• Negative caching. Requests for codes that don’t exist (typos, and scanners trying random codes) miss the cache and hit the database every time. Caching “not found” for a short time stops a scanner from turning into database load.
• Disabling. When a link is disabled, its cache entry is deleted as part of the same operation. Because the cache holds immutable mappings, this is the only invalidation the design needs (chapter 7).

Analytics

Counting clicks must never slow a redirect. The redirect service emits one small event per click (code, time, referrer, coarse location) to a log stream such as Kafka, without waiting for anything beyond a local buffer (chapter 8). A stream processor aggregates them into per-link, per-minute counts (chapter 9) and writes those to a separate table.

CREATE TABLE link_clicks_by_minute (
    code    text        NOT NULL,
    minute  timestamptz NOT NULL,
    clicks  bigint      NOT NULL,
    PRIMARY KEY (code, minute)
);

The aggregator writes one row per link per minute, however many clicks there were, so a viral link costs the database no more than a quiet one. If the event pipeline loses a few events under failure, counts are slightly low. That trade is acceptable for this requirement, and it’s stated as such.

Abuse

A shortener hides the destination of a link, which makes it useful for phishing and malware. Abuse handling is part of the design, not an add-on (chapter 19).

Short codes aren’t secrets, even when random. Seven characters are only 41.7 bits, and once the service has 1.8 billion live links, one random guess in about 1,900 hits a real one. A million guesses would find about 518 links. Anything sensitive needs authentication at the destination, not an unlisted URL.

Disabling has to reach every layer: the database row, the Redis entry, the CDN (with a purge), and, if 301s were ever sent without explicit cache headers, browsers that can’t be reached at all. This is the strongest argument for 302s with explicit headers.

Failure modes

The last row is worth a note. A user who creates a link and clicks it a second later is the most likely person to see replication lag. Writing the new link into the cache at creation time means the first redirect never depends on a replica having caught up.

The takeaway

The numbers make this a read problem: writes are tiny, storage fits one machine, and the redirect path is where the design work goes. Random codes collide sooner than intuition says (about 2.2 million for seven characters), so they need an atomic uniqueness check, which a primary key and ON CONFLICT provide. A shuffled counter avoids collisions without making codes guessable. Caching works well, but how well depends on the measured skew of traffic, and the redirect status and cache headers decide whether clicks can be counted and links can be disabled.