How to design a URL shortener

In this lesson, we’ll design a URL shortener: a service that turns a long web address into a short code and redirects visitors from the code back to the original. https://example.com/2026/q3/annual-report?utm_source=email becomes https://sho.rt/8Kq2mZ1, and the last seven characters are the code the service generated and stored next to the long URL.

The whole design falls out of two numbers. How many links the service will ever create fixes the code length, and how many times each link is clicked fixes everything else. We’ll work through four things that follow from them:

• Deriving the code length from the ten-year link volume.
• Why hashing the URL to make codes cannot avoid duplicates, and how a permuted counter does.
• Sizing the memory cache that carries the read traffic.
• Why the choice between two HTTP redirect status codes decides how much analytics data the product can collect.

By the end you’ll be able to size each tier from the workload, name the single number that forces each design move, and defend the whole ladder in an interview.

When a browser requests the short address, the service answers with an HTTP redirect: a response that carries no page of its own, only the instruction to go to another address. The browser follows it to the original URL. The core logic is small, and most of the design lives in the parts around it.

Three other topics come up in passing but are not prerequisites, and each idea is restated where it is used. They are the estimation chapter, the unique ID generator chapter, and the rate limiter chapter.

The core problem is a giant lookup table pulled three ways

Mechanically, a shortener is a very large lookup table: one short code in, one long URL out, exposed on a public API to a user base that includes people trying to abuse it. That much is easy. The design is hard because three product properties pull against each other, and every later trade-off is a move between them.

Three terms carry the rest of the lesson:

• Keyspace is the count of distinct codes the format can express. Seven characters from a 62-symbol alphabet gives 62 multiplied by itself seven times, written 62^7.
• A collision is when the scheme hands the same code to two different long URLs. It is not cosmetic; it silently sends one customer’s traffic to another customer’s site.
• Density is the fraction of the keyspace actually used. A scheme that spreads 365 billion links thinly across 3.5 trillion possible codes is sparse, and sparseness is what makes a code expensive to guess, because most codes an attacker tries land on nothing.

A short code is obscure, never secret. Three things break in production, in order of frequency: the click counter under-reports because someone shipped a cacheable redirect; a phisher discovers that your domain gets his malware URL past a corporate email filter; a viral link concentrates a fifth of global traffic onto one machine in the cache tier.

Requirements

Functional

• shorten(long_url) -> short_url, optionally with a custom alias (a code the customer chooses instead of one the service invents) and an expiry date.
• GET /{key} redirects to the original URL, where {key} is the seven-character code.
• Per-link click analytics: total, over time, by referrer and country. The referrer is the page the click came from, reported by the browser in a request header.
• Delete or disable a link; a disabled link must stop redirecting everywhere, promptly.

Out of scope: user accounts, billing, and vanity domains. Each is real work but none of it changes the architecture.

Non-functional

Three terms of art:

• p99 is the 99th percentile: sort every request of the day by how long it took, and the p99 is the time the slowest 1% exceeded. A mean hides the bad tail, so p99 is the number a user notices.
• Availability is the fraction of the year the service answers. 99.99% permits about 53 minutes of downtime a year; 99.9% permits about 8.8 hours. One extra nine is a factor of ten in permitted downtime, which is why the read and write targets are stated separately.
• Read-your-writes is the guarantee that whoever just created something can immediately see it. It is free on one machine, and becomes a real problem the moment reads are served from database copies that lag the original, because the creator’s own read can land on a copy that has not received the row yet.

The read and write targets differ by an order of magnitude, which justifies two different paths: a cached, edge-served read path and a coordinated, validated write path.

The assumptions the design rests on

An assumption is load-bearing when being wrong about it changes the shape of the system, not just the number of machines.

Getting a non-load-bearing assumption wrong costs money. Getting a load-bearing one wrong costs a rewrite.

Four numbers size the whole system

Before we design anything, we size it. Four numbers drive the rest of the work: the request rate, the code length, the storage footprint, and the bandwidth. Throughout, we round a day to 100,000 seconds (the true figure is 86,400), which makes every division a decimal shift and leaves every per-second rate about 14% under the true value, a consistent and deliberate bias.

Volume

At 100 M new links/day and 10 clicks/link:

• Writes: 100 M/day ≈ 1,000 QPS, peaking near 3,000.
• Reads: 1 B/day ≈ 10,000 QPS, peaking near 30,000.

The 10:1 read:write ratio is the most important number here. It says two things. The write path is allowed to be slow, coordinated, and expensive per operation, because there are ten times fewer writes and no human is blocked on the millisecond. And a cache is not an optimization, it is the architecture. At 100:1 the write path stops mattering entirely; at 2:1 the system is write-heavy and the code allocator becomes the bottleneck.

How long is the code?

Codes are written in base 62: the digits 0-9, the uppercase A-Z, and the lowercase a-z, which is 10 + 26 + 26 = 62 symbols. Like any positional system, L characters express 62^L distinct values, so “how many characters?” is really “how many links must the format hold over its lifetime?”

The ten-year demand is 100 M/day x 365 x 10 = 365 billion codes. Comparing that against the supply at each length:

Seven characters is the answer. The 9.65x headroom is not spare slack; it is budget spent later on waste in the code allocator and on the sparseness that makes guessing expensive.

Why base 62 and not 64, 58, or 36

The alphabet is a separate choice from the length.

• Base 64 is the encoding used to carry binary data through text channels. At 64^7 = 4.4 trillion it is still 7 characters for this volume, so it shortens nothing, and it costs usability: standard base 64 uses + and /, but / is the URL path separator and + decodes to a space in a query string (RFC 3986), so a raw base-64 code is not a valid path segment. The URL-safe base64url variant swaps in - and _, but _ vanishes under an underline in a mail client.
• Base 58 drops the four glyphs that get misread (0/O, and 1/l/I). It still covers 365 billion in 7 characters, with 6x headroom instead of 9.65x. Trading headroom you were never going to spend for fewer mistyped links is free.
• Base 36 treats upper and lower case as the same symbol, so 36^7 = 78 billion falls short and it needs 8 characters. Case-insensitivity costs exactly one character: the right call if links get read aloud in radio ads or typed off packaging.

Storage over ten years

A stored row is not just its visible columns. Using the page-layout arithmetic from the database internals chapter, a link is about 131 B of payload (the URL, key, user id, timestamps) plus about 68 B of engine overhead: two index entries at 20 B each (one on the primary key, one enforcing UNIQUE on short_key), and a 28 B row header plus line pointer. That totals about 200 B per link.

At that size:

• 20 GB/day, so 73 TB of primary data over ten years, or 219 TB at replication factor 3 (every row on three machines so losing two loses nothing).
• 73 TB is roughly 8 to 20 commodity boxes. Storage is not the binding constraint, with one exception.

That exception is the click log. At 1 B clicks/day and 50 B per event, it grows 50 GB/day, 2.5x faster than the link table it measures. So raw click rows do not belong in the main store. Instead: write them to a queue (a buffer that accepts events instantly so the redirect never waits on analytics), roll them up into per-link, per-hour counters, keep raw events 30 days for the fraud pipeline and then drop them, and put the rest in columnar cold storage that compresses well for scan-heavy analytics queries.

Bandwidth

A redirect carries no page body, only a status line, a Location header, and a few others: about 500 B. At 10,000 responses/s that is 5 MB/s, or 40 Mbps, about 4% of one 1 Gbps network card. This is a request-rate and latency problem, never a bytes problem.

API sketch

POST /v1/urls
  {"long_url": "https://...", "custom_alias": null,
   "expires_at": null, "idempotency_key": "..."}
  201 {"short_url": "https://sho.rt/8Kq2mZ1", "key": "8Kq2mZ1"}
  409 if custom_alias is taken
  422 if the URL fails validation or reputation screening

GET  /{key}
  302 Location: https://...            (the default; see 301 vs 302 below)
  200 the interstitial, if the link is flagged
  410 if the link was deleted or has expired
  404 if the key was never issued

DELETE /v1/urls/{key}
GET    /v1/urls/{key}/stats?from=&to=&group_by=day|country|referrer

An interstitial is a warning page shown instead of the redirect, telling the visitor where the link goes and making them click again to proceed.

Three choices in this API carry weight:

• Use 410 Gone, not 404, for a deleted link. 404 means “never existed,” which is inaccurate and costs a support ticket every time an expired campaign link is reported as a bug. 410 means “existed and is now withdrawn.” Never redirect a dead link to your homepage; that invites treating your domain as a generic redirector.

• Use an idempotency_key, not automatic dedupe by URL. An idempotency key is a client-generated identifier on a create request, so a retry after a timeout produces the same link instead of a second one. That is not the same as globally deduplicating by destination: two different users shortening the same URL want two links, two click counters, and two expiries. Global dedupe at a 30% duplicate rate would save only about 22 TB over ten years, a few thousand dollars a year against the per-user analytics customers are paying for. Do not trade the product for it.

• Rate limit creation per API key and per source IP, using the token-bucket scheme from the rate limiter chapter. As the abuse section explains, this is a correctness control, not a cost control.

Data model

urls
  id           BIGINT   PRIMARY KEY   -- dense counter (see code generation)
  short_key    CHAR(7)  UNIQUE        -- base-62 of a permutation of id
  long_url     VARCHAR(2048)
  user_id      BIGINT
  created_at   TIMESTAMP
  expires_at   TIMESTAMP NULL
  status       SMALLINT               -- active | flagged | disabled

click_counters                        -- rolled up, not raw
  short_key, hour, country, referrer_hash, count

This is a key-value workload, not a relational one. The access pattern is a single-key point lookup: GET /8Kq2mZ1 fetches exactly one row by its exact key, with no joins (combining rows from two tables), no range scans (walking a span of consecutive keys), and no cross-key transactions. A store that only serves point lookups is a key-value store (key-value store chapter); a relational database’s joins, transactions, and ordered indexes would all go unused while still costing you something.

Partition the store by hash: it computes a hash of short_key and uses that to pick which machine holds the row, so a lookup touches exactly one machine. Do the partitioning with the hash ring from the consistent hashing chapter instead of plain “hash modulo server count,” because modulo reassigns almost every key when the server count changes (growing 16 machines to 17 moves about 94% of the corpus; the ring moves 1/17, about 6%).

The consistency requirement is unusually weak. A link is written once and never updated, so two copies can only ever disagree about whether a row exists, never about what it says: there is no such thing as a stale destination. The write must be durable before the API returns (the user is about to paste that link), but reads can be served from anywhere. In quorum terms, this is a high W and an R of 1.

Two deliberate omissions:

• No index on long_url. Nothing queries by destination, and an index on a column up to 2 KB wide would cost more than the table.
• No click_count column on urls. If the count lived on the row, every redirect would become a write to that row, and a viral link would send all of them to one row on one machine. That is a hot key: a single key taking a wildly disproportionate share of traffic, which is the fastest way to melt one shard (one of the machines the data is split across). Because the shard is chosen by the hash of short_key, a hot key is by construction a hot shard, and adding shards does not help: the key hashes to the same place every time.

High-level architecture

The read path (top) is what a browser takes when someone clicks a short link. The write path (bottom) is what happens when someone creates one. They meet only at the store. The write path is longer, and that asymmetry drives the design.

flowchart TD
    U["Client GET /8Kq2mZ1"] --> EDGE["Edge PoP: KV copy of the hot 1 M keys"]
    EDGE -->|"miss"| LB["Load balancer"]
    LB --> RD["Redirect service (stateless)"]
    RD --> C["Shared cache: hot key to long_url, plus blocklist bloom"]
    C -->|"miss"| DB["KV store of record: hash-partitioned on short_key, RF 3"]
    RD -.->|"async, fire and forget"| Q["Click queue"]
    Q --> AGG["Rollup jobs: hourly counters"]

    U2["Client POST /v1/urls"] --> WR["Write service"]
    WR --> RL["Rate limiter"]
    WR --> TS["Counter allocator: hands out blocks (single writer)"]
    WR --> SAFE["Reputation check: Safe Browsing, blocklists"]
    WR --> DB
    WR -->|"write-through"| C

Read path. A browser issues GET /8Kq2mZ1 to the nearest edge PoP (point of presence: a small rack of servers in a city close to users), which holds a copy of the hottest million codes. A miss falls through a load balancer to the redirect service, which is stateless: it keeps nothing between requests, so any instance can serve any request and the tier is cheap to scale. It consults the shared cache; only on a second miss does it read the KV store. Separately it drops a click event onto the click queue without waiting for it (fire and forget), and rollup jobs aggregate those events into the hourly counters later.

Write path. The write service in order: consults the rate limiter, draws a number from the counter allocator (a single row handing out contiguous blocks of integers), runs the destination past a reputation check, and writes the row.

The arrow people leave out is the write-through from the write service into the cache: it populates the cache at creation time instead of waiting for the first read. The creator tests the link within seconds, so a lazily-populated cache guarantees that first read misses, and it may also miss a database replica that has not caught up, which is exactly read-your-writes failing. Populating on create makes read-your-writes free.

Code generation: hash vs. counter

There are two ways to produce the code, and they fail in opposite directions.

flowchart TD
    START["Need a 7-char code"] --> Q{"How is it derived?"}
    Q -->|"Hash the URL, truncate"| H["Stateless, free dedupe"]
    H --> HBAD["But collides: first duplicate ~32 min after launch"]
    Q -->|"Encode a counter"| CTR["Zero collisions, dense"]
    CTR --> CBAD["But ordered: enumerable, leaks daily volume"]
    CBAD --> FIX["Permute the counter with a keyed cipher"]
    FIX --> GOOD["Zero collisions AND unordered: the chosen design"]

A hash-based scheme feeds the long URL through a hash function (a fixed procedure turning any input into a fixed-size scrambled number) and uses part of the output as the code. Identical inputs give identical codes and there is no shared state, but two different URLs can hash to the same code. A counter-based scheme keeps one ever-increasing integer, hands the next value to each new link, and encodes it. Codes are guaranteed distinct, but every writer must coordinate on whose turn it is. Hashing trades duplicate codes for statelessness; counting trades coordination for a guarantee.

Why hashing collides

Take SHA-256(long_url), keep the leading 42 bits (a 7-character base-62 code needs 7 x log2(62) ≈ 41.7 bits, and you cannot keep a fraction of a bit), reduce that value mod 62^7 so it lands inside the code space, and encode it. On a duplicate, re-hash with a salt (an extra value mixed in to get a different answer).

The mod step is not optional. 42 bits spans 4.40 trillion values but 62^7 is only 3.52 trillion, so about one 42-bit value in five is too large for a 7-character code; skip the reduction and those inputs overflow the encoder. The reduction is slightly non-uniform (values in the low end are twice as likely), which nudges collisions up about 12% and changes nothing about the argument.

The collision rate is governed by the birthday bound. In a room of 23 people two share a birthday more often than not, because what matters is the number of pairs (23 x 22 / 2 = 253), which grows as the square. Applied to codes drawn from a space of size M, the first duplicate appears after roughly sqrt(M) draws, not after M.

For M = 62^7 and 365 billion links over the decade:

• The keyspace is 10.4% full by year ten. A random draw lands on an occupied code with that probability.
• The first collision arrives about 32 minutes after launch (1.177 x sqrt(M) ≈ 2.2 million links). Any claim that collisions are negligible is wrong by six orders of magnitude.
• Expected collisions over the decade are n^2 / 2M ≈ 18.9 billion: about 5.2% of writes on average and 10.4% on the last insert of the decade. The retry path is one write in twenty, not an edge case, and must be tested.
• Every create needs a read-before-write or a unique-index conflict check. That is affordable at 3,000 peak writes/s, but you can never insert blindly.

To reach a fill ratio a counter gets for free, hashing needs an eighth character (62^8 drops the collision rate to about 1 in 599). So the honest hash design is 8 characters: hashing costs a character for the same volume. What it buys in return is free deduplication: the same URL always produces the same code.

Why a counter, and how to hide its order

Encoding a dense counter (one that increases by exactly one each time) gives zero collisions by construction, no read-before-write, and the full 62^7 space usable.

The allocator is a ticket server: one row holding the next unissued value, handing out contiguous blocks to write nodes, which serve individual links from their block without talking to anyone. That makes the single coordinated component nearly idle: at a block size of 10,000 and 1,000 writes/s, it is contacted about once every ten seconds across the whole fleet.

The unique ID generator chapter rejects this design in favor of a Snowflake ID (a 64-bit id from a timestamp, machine number, and per-millisecond sequence, so any machine mints unique ids without coordinating). That is the right answer for general id generation, but it makes values sparse: 22 bits go to machine and sequence, so every passing millisecond jumps the value by 2^22 ≈ 4.2 million whether or not any ids were minted. Code length is set by the largest value, not the count used, so after ten years a Snowflake reaches about 1.32e18 and needs an 11-character code for the same 365 billion links a counter encodes in 7. Uniqueness is what an id generator sells; density is what a shortener needs, and those are different products.

A counter’s one problem is that its output is ordered, which leaks three things:

• An attacker walks 0, 1, 2, … and enumerates every link at one request per link found, instead of the ~9.6 requests a random probe of a 10.4%-full space costs.
• Two codes minted a day apart subtract to reveal the day’s exact link volume.
• The code reveals a link’s relative age, enough to isolate “everything created during the incident.”

Enumeration is the real failure, because the industry treats an unlisted short link as private: shared documents, invoices, unlisted videos, password-reset pages a support agent shortened.

The fix: permute the counter, do not randomize it

Encrypt the counter with a small keyed block cipher whose input and output are both codes in the same space. This keeps the counter’s guarantee and destroys its order.

A Feistel network builds a cipher from any scrambling function. Split the number into a left and right half, then repeat four times:

(left, right)  ->  (right, left XOR f(right))

where f is any keyed function. Every round is reversible whatever f does: to undo it you still have right, so you can recompute f(right) and XOR it back out. That makes the whole thing a bijection (a one-to-one mapping, every input to exactly one output and vice versa), and a bijection cannot collide. The permuted counter inherits the raw counter’s zero-collision guarantee with no storage, no uniqueness check, and no retry loop.

A Feistel network works on a power-of-two domain, so use 42 bits (two halves of 21), the same 42 bits hashing needed, overshooting 62^7 by the same ~25%. Handle the overshoot with cycle-walking: if the encrypted value lands above 62^7, encrypt it again until it lands inside. Because a permutation maps out-of-range values only among themselves, this stays a bijection. The cost is the ratio of the two spaces, about 1.25 encryptions per code.

Being a bijection, it is invertible, so GET /{key} can decrypt the code straight back into the primary key instead of consulting a secondary index. Two caveats: custom aliases still need a real lookup table, and the cipher key can never be rotated without orphaning every code ever issued.

The permutation removes the ordering and volume leaks and raises the attacker’s enumeration cost from 1 request per hit to about 9.6 (a random guess now hits an occupied code only at the 10.4% fill rate). It does not make links secret: at 10.4% fill a random guess still finds a live link about once every ten tries; even at 8 characters it is 1 in 599. A short code is obscurity, not security. The controls that actually protect confidential links are rate limiting GET by IP and a real authorization check on anything genuinely private.

Working Python

The codec and the permutation in runnable form. encode repeatedly divides by 62 and collects remainders (the standard way to write a number in any base); decode reverses it with Horner’s rule. The permutation wraps four Feistel rounds in the cycle-walking loop, and the final assertions prove on a small domain that the output is a permutation of the input, which is the proof of zero collisions.

"""Base-62 codec plus the keyed permutation that hides the counter."""
import hashlib

ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
BASE = len(ALPHABET)                     # 62
KEY_LEN = 7                              # 62^7 = 3,521,614,606,208
INDEX = {c: i for i, c in enumerate(ALPHABET)}

def encode(n, width=KEY_LEN):
    """Base-62 numeral for n, left-padded with '0' to a fixed width."""
    if n < 0:
        raise ValueError("counter values are non-negative")
    out = []
    while n:
        n, r = divmod(n, BASE)
        out.append(ALPHABET[r])
    s = "".join(reversed(out)) or "0"
    if len(s) > width:
        raise OverflowError(f"{s} does not fit in {width} characters")
    return s.rjust(width, "0")

def decode(s):
    n = 0
    for c in s:
        n = n * BASE + INDEX[c]          # KeyError on a glyph outside the alphabet
    return n


assert encode(0) == "0000000"
assert encode(61) == "000000z"
assert encode(62) == "0000010"
assert encode(62 ** 7 - 1) == "zzzzzzz"
assert decode("zzzzzzz") == 3_521_614_606_207
assert all(decode(encode(n)) == n for n in range(0, 200_000))


def _round_fn(key, rnd, x, half_bits):
    h = hashlib.sha256(f"{key}:{rnd}:{x}".encode()).digest()
    return int.from_bytes(h[:8], "big") & ((1 << half_bits) - 1)

def feistel(n, key, half_bits, rounds=4):
    mask = (1 << half_bits) - 1
    left, right = (n >> half_bits) & mask, n & mask
    for r in range(rounds):
        left, right = right, left ^ _round_fn(key, r, right, half_bits)
    return (left << half_bits) | right

def feistel_inv(n, key, half_bits, rounds=4):
    mask = (1 << half_bits) - 1
    left, right = (n >> half_bits) & mask, n & mask
    for r in reversed(range(rounds)):
        left, right = right ^ _round_fn(key, r, left, half_bits), left
    return (left << half_bits) | right

def permute(n, key, half_bits, limit, rounds=4):
    """Cycle-walking: re-encrypt until the image lands inside [0, limit)."""
    x = n
    while True:
        x = feistel(x, key, half_bits, rounds)
        if x < limit:
            return x

def permute_inv(n, key, half_bits, limit, rounds=4):
    x = n
    while True:
        x = feistel_inv(x, key, half_bits, rounds)
        if x < limit:
            return x


HALF, LIMIT = 21, 62 ** KEY_LEN          # 2 x 21 = 42 bits, and 2^42 > 62^7

def short_key(counter, key="server-secret"):
    return encode(permute(counter, key, HALF, LIMIT))

def counter_of(code, key="server-secret"):
    return permute_inv(decode(code), key, HALF, LIMIT)


# round trip: the code decrypts back to the primary key, so no index lookup
assert all(counter_of(short_key(n)) == n for n in range(0, 5000))

# consecutive counters produce unrelated codes -- the enumeration fix
assert len({short_key(n)[:3] for n in range(1000, 1010)}) >= 9

# exhaustive bijection check on a toy domain: a permutation cannot collide
TOY_HALF, TOY_LIMIT = 8, 50_000          # 2^16 = 65,536 > 50,000
image = [permute(n, "k", TOY_HALF, TOY_LIMIT) for n in range(TOY_LIMIT)]
assert sorted(image) == list(range(TOY_LIMIT))

The read path and the cache

Sizing the cache produces the key result of this design: the last few gigabytes of memory are worth far more than the first. That result is entirely a consequence of the popularity-skew assumption.

The workload is the friendliest a cache can face: 10,000 reads/s against 73 TB, where each value is immutable once written: a code’s destination never changes. A cache is a small, fast copy of the most useful part of a large, slow store; its hit rate h is the fraction of requests it answers itself, and 1 - h is the miss rate that falls through to the database. Immutability means there is no invalidation problem except deletion, which is rare and handled with a short time-to-live (TTL, an expiry stamped on each entry) plus an explicit purge.

Assume the day’s 1 billion clicks land on 100 million distinct links and that popularity is Zipfian: the n-th most popular item gets roughly 1/n of the traffic of the most popular one. For a Zipf exponent of 1, the top m of K items cover ln(m)/ln(K) of all accesses. With K = 100 million, that simplifies to a rule you can do in your head:

h = log10(m) / 8

Cache a million entries and h = 6/8 = 0.75; cache ten million and h = 7/8 = 0.875. Every factor of ten in memory buys one eighth of hit rate. A cache entry is not a database row (it carries none of the storage-engine overhead), but by a different route (key, URL, expiry, in-memory bookkeeping) it also comes to roughly 200 B.

10 GB of RAM takes the database from 3,750 QPS to 376. The reason is a mismatch between two curves: hit rate rises with the logarithm of memory, but database load falls as the reciprocal of the miss rate. A logarithm flattens; a reciprocal blows up. So the first 20 MB buys 62 points of hit rate and a 2.7x reduction, while the last 8 GB buys only 9 more points but takes the reduction from 8x to 26.6x.

This result depends entirely on the Zipf assumption. Under uniform popularity, caching 50 M of 100 M equally-clicked links would answer exactly 50% of requests, for 2.0x leverage, and no amount of memory would ever reach 26.6x because the curve is a straight line. So real traffic’s skew is the first thing to verify. As a sanity check, the cruder “20% of items take 80% of traffic” rule gives 2,000 DB QPS where Zipf gives about 874; provision on the pessimistic 2,000, because over-provisioning wastes a little capacity while under-provisioning causes an outage.

Two extensions fall out of the same table:

• Push it to the edge. The value is 100 bytes and never changes, so an edge PoP can answer outright without contacting the core. The 1,000,000-entry row is 200 MB at 75% hit rate: put that in every PoP and three quarters of clicks never make the ~150 ms cross-continent round trip. This is the single largest latency win available, and it costs 200 MB.
• Keep a small in-process cache in front of the shared one. A viral link can take 20% of global traffic: at 30,000 peak QPS, 6,000 QPS onto one machine. Consistent hashing explicitly does not fix this, because the key hashes to one place no matter how many machines you add. What fixes it is a small (say 10,000-entry) map inside each application process evicting on a least-recently-used (LRU) policy: a hot key is by definition never the least recently used, so every node answers it locally.

301 vs. 302: an analytics decision

A one-line choice of HTTP status code silently decides how much of the product’s data you keep, and the resulting undercount cannot be corrected afterward.

Both codes send the browser to the destination. The difference is one line in the spec: 301 Moved Permanently is cacheable by default; 302 Found is not. Cacheable means the browser may remember the answer and, on the next click of the same link, jump straight to the destination without asking your service, so your service never learns the click happened.

If 30% of clicks are repeat visits, a 301 means 30% fewer requests reaching the service (a discount on the read fleet, the edge bill, and repeat-click latency) and 30% of clicks the counter never sees, a hole in the only data the product sells.

That hole cannot be calibrated away. The clicks a 301 hides are exactly the repeat clicks, so the undercount concentrates on your most engaged users and most-clicked links, the two things the customer is paying to measure. To correct it you would need the per-link repeat rate, which is precisely what you stopped measuring.

Two consequences are worse than the counting. A 301 cannot be revoked (browsers cache it aggressively, sometimes for the life of the profile), so when a link turns out to be malware, or a customer re-points a campaign, those clients never ask you again. That makes 301 incompatible with takedown, which for a shortener is not optional; expiry and destination rotation break the same way.

So pick 302, and control caching explicitly with Cache-Control: no-store instead of relying on the status code’s default. 301 is right for a domain migration, where permanence is the point and nobody is buying the click data. Here analytics is the product, and a shortener that undercounts by 30% is selling a broken instrument.

Keeping your domain from becoming a phishing tool

A large part of the design is the set of controls that stop your domain from becoming a phishing tool. A shortener is an anonymizing redirector on a domain with reputation, which is exactly what a phisher wants: your domain gets his malware URL past the corporate mail filter, and the recipient cannot see the destination before clicking.

Safety is not a one-time check at creation. The top row below runs once at create time; the bottom row runs on every read, forever. Most designs draw only the top row.

flowchart LR
    W["POST /v1/urls"] --> V["Syntactic validation: scheme, host, no loops"]
    V --> B{"Destination on the blocklist bloom?"}
    B -->|"hit"| REJ["422 reject"]
    B -->|"miss"| REP{"Reputation verdict cached and fresh?"}
    REP -->|"clean, fresh"| OK["201 created, status=active"]
    REP -->|"unknown or stale"| SCAN["Async scan; create as active, flag on a bad verdict"]

    R["GET /{key}"] --> RB{"Destination flagged since creation?"}
    RB -->|"no"| RD["302 to the destination"]
    RB -->|"yes"| INT["200 interstitial: show the full URL, require a click"]

Four controls; the second is the one most often missed.

1. Screen at write time. Reject non-http(s) schemes outright: a javascript: or data: URL turns your redirect into a delivery service for stored cross-site scripting (attacker code running in another user’s browser under your domain). Reject your own domain, so a link cannot point at another link and loop. And check the destination against a reputation service such as Google Safe Browsing. There is a trap inside that check: the fetcher that renders the destination must refuse private and link-local addresses, or a user shortens http://169.254.169.254/ (the cloud instance-metadata address, reachable only from inside the network) and reads your cloud credentials out of the scan result. That class of bug is server-side request forgery (SSRF): tricking your server into making a request the attacker cannot make directly.

2. Re-check at read time, because a URL’s safety is not a property of the moment it was shortened. The standard attack is to shorten a clean page, pass screening, then repoint the domain’s DNS or swap the page a week later. A link is checked once and clicked for years, so the read path must consult a blocklist, and it must do that in memory: a network call per redirect at 30,000 peak QPS is not viable.

The structure that makes an in-memory blocklist affordable is a bloom filter: a compact bit array that answers “is this in the set?” with either “definitely not” or “probably yes.” It never misses a real member, so no bad domain slips through, but it produces occasional false positives (clean domains it wrongly flags) at a rate you choose by spending more bits. Those you resolve against the real list, a network call, but only for the small fraction that trip the filter. At a 1% false-positive rate, 10 million bad domains need about 12 MB per process (roughly 9.6 bits per entry) and produce about 300 false-positive lookups/s at peak, the cheapest safety control in the system. The alternative, a network call on every redirect, adds latency, sends 30,000 requests/s to that service, and makes a 99.99% read path depend on something else’s availability.

3. An interstitial, not a hard block, for the uncertain middle. Sort verdicts into three bands: clean redirects silently (302), flagged gets a full-page interstitial that spells out the destination and requires a confirm click, malicious returns 410 Gone. The interstitial costs a round trip and measurably kills conversion, which is exactly why it is reserved for “we do not know,” not “this is bad.”

4. Rate limit creation, per API key and per source IP (rate limiter chapter). Phishing campaigns need thousands of distinct links to outrun blocklists, because each link is burned once reported. So a per-account creation limit is not a cost control; it is what makes the abuse uneconomic. Pair it with a per-account reputation score: new accounts get interstitials by default and graduate out.

The control that gets missed in incident reviews: the takedown path must reach the caches and the edge, not just the database. A link disabled in the primary store is still served by 200 MB of edge data in every PoP and by every node’s local LRU until they are told, so the purge must fan out to all of them under a stated deadline. That is the second reason 301 is disqualified: after revocation, the copy of your redirect sitting in the user’s own browser cannot be purged at all.

Bottlenecks and scaling

Sizing the allocator’s block size

The allocator is the only genuine single writer, and its block size is a real trade. Bigger blocks buy availability: write nodes talk to the allocator less often, so they survive longer when it dies, still working through numbers they already hold. Bigger blocks also burn keyspace: every process that restarts abandons the unused remainder of its block forever.

Assuming 100 write nodes and about 1,000 restarts a day (deploys plus crashes), each abandoning half a block:

Read the peak column, not the average: if the allocator dies during the busy hour the runway is a third of what the average suggests. At 1,000 you have 33 seconds at peak, not enough for a human to act. At 100,000 you burn half the keyspace a day to buy an afternoon, the wrong side of the trade, since the 9.65x headroom is what you are spending. A block size of 10,000 costs the headroom only down to about 9.19x (nothing you were going to spend) and buys 5.6 minutes at peak to fix the allocator before creates fail.

Failure modes

Two terms: request coalescing means that when many requests miss the cache on the same key at once, only one goes to the database and the rest wait for its answer, so a hot-key eviction produces one read instead of thousands. A high-water mark is a durably stored record of the largest value ever handed out, so a component restored from an older backup can tell it is behind and refuse to reissue numbers.

Alternatives rejected

Each of these was good at something and disqualified by a specific number.

• Hash and truncate to 7 characters. Good: free deduplication, no shared state, no allocator. Rejected because the fill ratio at 365 billion links is 10.4%, so the first collision arrives 32 minutes after launch and getting to a safe fill ratio costs an eighth character. Revisit if global dedupe is a real product requirement.
• Base-62 of a Snowflake ID. Good: no allocator, no coordination. Rejected on density: Snowflake spends 22 bits on node and sequence, so the code is 11 characters instead of 7. The right use of a Snowflake here is the internal primary key, not the public code.
• A raw auto-increment as the public code. Good: shortest codes, trivially dense. Rejected because it is fully enumerable at one request per link and leaks daily volume by subtraction. The keyed permutation keeps every benefit and deletes both leaks for ~1.25 hash operations.
• Random 7-character codes with retry on conflict. Good: unguessable ordering, no allocator. Rejected because it has hash-truncation’s collision profile with none of its dedupe benefit and needs a uniqueness check on every write forever. A permutation is a random-looking code with a proof of no collisions.
• 301 Moved Permanently. Good: 30% fewer requests, faster repeat clicks. Rejected because the hidden clicks are exactly the repeat clicks (so the undercount cannot be corrected) and because a cached 301 makes takedown impossible. Right for a domain migration, wrong for a product whose output is click data.
• A relational database with a B-tree primary key and no cache. Good: one component, transactional custom aliases. Rejected on the read path: 10,000 QPS of point lookups against 73 TB means the working set does not fit in memory, so most reads become random disk reads and you need roughly one device’s full IOPS budget per 10,000 QPS before replication. The relational features are used only by custom aliases, a rounding error of the traffic.
• Synchronous click counting in the redirect path. Good: exact counts, no pipeline. Rejected because it converts a pure-read path into a read-plus-write at 10,000 writes/s onto the hottest rows, and makes the redirect’s availability depend on the analytics store’s. Fire-and-forget onto a queue instead: analytics may be eventually consistent, a redirect may not be slow.

Conclusion

• Two numbers set everything. Lifetime link volume (365 billion) fixes the code length at 7 base-62 characters; the 10:1 read:write ratio makes a cache the architecture, not an optimization.
• Generate codes from a keyed permutation of a dense counter. It has zero collisions by construction (unlike hashing, which collides within an hour and needs an eighth character to be honest), and the permutation removes the enumeration and volume leaks a raw counter would expose. A short code is obscurity, never security.
• The cache’s non-linear payoff is a property of skewed traffic, not of caching. Under Zipf popularity, 10 GB of RAM cuts database load 26x; under uniform popularity the same memory buys 2x. Verify the skew against real traffic.
• Serve 302, not 301. 301 is cacheable, which hides exactly the repeat clicks and makes takedown impossible.
• Safety is a read-time control, not a create-time one. A destination can turn malicious after screening, so the redirect path needs an in-memory bloom-filter blocklist and a purge that fans out to the edge and to in-process caches, not just the database.

One line to remember: a shortener is a read-mostly key-value store whose two hard problems are generating dense unguessable codes and carrying skewed read traffic in cache, and every other decision is downstream of those two numbers.

Further reading

• RFC 3986: Uniform Resource Identifier (URI): Generic Syntax: what characters are legal where in a URL, which is why the alphabet choice matters.
• Google Safe Browsing: the reputation API referenced in the write-time screening control.
• Related lessons on this site: the unique ID generator chapter (why a Snowflake id is sparse), the rate limiter chapter (the control that makes bulk phishing uneconomic), and the consistent hashing chapter (how the storage is partitioned).