Designing a URL Shortener, Properly

The URL shortener is the "hello world" of system design interviews, which is unfortunate, because the interview version skips everything that makes it interesting. A redirect service is small enough to hold in your head and still touches ID generation, caching, hot keys, abuse, and the difference between a 301 and a 302. This post designs one from requirements to architecture, doing the arithmetic out loud.

Requirements

Functional:

POST /links with a long URL returns a short code; optionally a custom alias and an expiry.
GET /{code} redirects to the long URL. This is the product. Everything else is secondary.
Links can be disabled (abuse, takedown) and expire.
Click counts per link, approximately, with a delay measured in seconds.

Non-functional, with the assumptions that drive the numbers:

100 million new links per month; reads outnumber writes 100 to 1.
Redirect latency well under 100 ms at the 99th percentile, excluding the client's network.
Redirects must keep working if the write path is down: availability over consistency for reads.
Keep links for five years by default.

Capacity estimation

Writes per second, averaged over a month:

λ_{w} = \frac{10^{8}}{30 \times 86,400 s} \approx 38.6 writes/s, λ_{r} = 100 λ_{w} \approx 3,860 reads/s .

Traffic is not flat; a peak-to-average ratio of 3 gives roughly 12,000 redirects per second at the busiest time. That is a comfortable load for a few stateless web processes in front of a cache, and nowhere near the territory where exotic infrastructure is needed.

Storage over five years, assuming an average row of about 500 bytes (a 7-character code, a URL of a few hundred bytes, timestamps, owner, flags, and index overhead):

10^{8} \times 12 \times 5 = 6 \times 10^{9} rows, 6 \times 10^{9} \times 500 B \approx 3 TB .

Three terabytes is a single large PostgreSQL instance with a replica, or a few shards if you prefer smaller boxes. It is not a "distributed database" problem on its own.

Code length: with a 62-character alphabet (0-9a-zA-Z),

62^{6} \approx 5.7 \times 10^{10}, 62^{7} \approx 3.5 \times 10^{12} .

Six characters would cover six billion links with a factor of nine to spare; seven gives six hundred times headroom and room for a sparse keyspace. Use seven.

Bandwidth: a redirect response is around 500 bytes of headers; at 12,000/s that is 6 MB/s outbound, which is small. Cache size: holding the hottest million links at roughly 300 bytes each (key, URL, flags) is about 300 MB of memory, which fits on one cache node. Whether a million entries is enough depends on how skewed the traffic is, which is the subject of the caching section.

Data model

CREATE TABLE links (
  code        text        PRIMARY KEY,                 -- 7 base62 chars, or a custom alias
  target      text        NOT NULL CHECK (length(target) <= 2048),
  owner_id    bigint,
  created_at  timestamptz NOT NULL DEFAULT now(),
  expires_at  timestamptz,
  disabled    boolean     NOT NULL DEFAULT false
);

-- Append-only click log, partitioned by day so old partitions can be dropped
-- or rolled into a daily aggregate.
CREATE TABLE clicks (
  code        text        NOT NULL,
  at          timestamptz NOT NULL,
  referrer    text,
  ua_hash     bytea,
  country     char(2)
) PARTITION BY RANGE (at);

CREATE TABLE clicks_2025_01_21 PARTITION OF clicks
  FOR VALUES FROM ('2025-01-21') TO ('2025-01-22');

CREATE MATERIALIZED VIEW link_click_counts AS
  SELECT code, count(*) AS clicks FROM clicks GROUP BY code;

Two decisions are hiding here. The code is the primary key, not a surrogate integer, because the redirect path has a code and nothing else; one index lookup should be the whole query. And clicks are never written on the request path: the redirect service emits an event and moves on, and a consumer writes the partitioned table in batches.

Why not store the long URL's hash for de-duplication?

It is tempting to add UNIQUE (sha256(target)) so that two people shortening the same URL get the same code. It also makes the short link a reverse lookup table: anyone can test whether a given long URL has been shortened by anyone. If de-duplication is wanted, scope it per owner (UNIQUE (owner_id, target_hash)), which keeps the convenience and removes the oracle.

Generating codes

There are three families of approach. The table summarises them; the paragraphs explain the trade-offs that matter.

Approach	Collisions	Predictable?	Needs coordination?	Length for 6B links
counter, base62-encoded	none	yes, sequential	yes, a counter or range allocator	6 chars
hash of the URL, truncated	yes, must detect and retry	no	no	7 chars + retries
random 7-char string	rare, must detect and retry	no	no	7 chars

Counter plus base62. A 64-bit counter encoded in base62 never collides and is the simplest to reason about. The cost is coordination: every writer needs a unique next number. The standard trick is a range allocator: a tiny service (or a single UPDATE ... RETURNING on a one-row table) hands each API process a block of 1,000 ids; processes burn through their block locally and come back for another. Losing a block on a crash wastes at most 1,000 codes out of 3.5 trillion.

The other cost is predictability. Sequential codes let anyone enumerate every link ever created by incrementing. If links are public anyway this is harmless; if people shorten private documents, it is a disclosure. Mitigations are a secret per-deployment permutation of the alphabet, or a bijective mix (multiply by a large constant coprime to 62, modulo $62^{7}$ ), both of which keep the no-collision property.

Hashing the URL. Take the first 7 base62 characters of SHA-256 of the long URL. No coordination, and the same URL maps to the same code, which is sometimes a feature and sometimes a privacy leak (see the collapsed note above). Collisions are inevitable at scale: two different URLs can share a prefix, so the insert has to detect the unique violation and retry with a salt.

Random codes. Generate 7 random base62 characters and insert; on a unique violation, try again. With $n$ links in a space of $N = 62^{7}$ codes, the expected number of collisions over the lifetime of the system is about

\frac{n^{2}}{2 N} = \frac{(6 \times 10^{9})^{2}}{2 \times 3.5 \times 10^{12}} \approx 5 \times 10^{6},

five million retries spread across five years and six billion inserts, which is less than one in a thousand writes. Random codes are unpredictable, need no allocator, and the retry path is a few lines. For most shorteners this is the pragmatic choice; the counter wins when you want the shortest possible codes or a strict no-retry guarantee.

import secrets

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"


def encode_base62(n: int) -> str:
    """Counter style: 0 -> '0', 61 -> 'Z', 62 -> '10'."""
    if n == 0:
        return ALPHABET[0]
    out = []
    while n:
        n, rem = divmod(n, 62)
        out.append(ALPHABET[rem])
    return "".join(reversed(out))


def random_code(length: int = 7) -> str:
    """Random style: uniform over 62**length codes, from the OS CSPRNG."""
    return "".join(secrets.choice(ALPHABET) for _ in range(length))

The redirect itself

HTTP/1.1 302 Found
Location: https://example.com/very/long/path?with=query
Cache-Control: private, max-age=0
Content-Length: 0

301 Moved Permanently is cacheable by default, so a browser that has seen it once will skip your server entirely on the next click. That is fastest for the user and invisible to your analytics, and it makes "disable this link" impossible for anyone who already followed it. 302 Found (or 307 to preserve the method) keeps every click on your server. A shortener that needs to see every click, for analytics or for takedowns, should use 302; one that only cares about speed can use 301 with a long max-age and accept the loss of control.

DANGER

A shortener is an open redirect by design, which makes it a phishing tool by default. Validate the scheme (http/https only), refuse targets that resolve to private address ranges, rate-limit creation per account and per IP, keep a blocklist, and build the takedown switch (disabled = true) on day one. The disabled check happens on the read path, so a disabled link must also be evicted from the cache.

Architecture

Read and write paths are separate services sharing one database. The hot path (blue) touches the cache and, on a miss, a read replica; writes and analytics never block a redirect.

A redirect, step by step:

The load balancer terminates TLS and routes GET /{code} to any redirect replica.
The replica checks a small in-process LRU cache (a few thousand entries, 30-second TTL).
On a miss it asks Redis with GET link:{code}.
On a Redis miss it queries a PostgreSQL read replica by primary key, then writes the result back to Redis with a TTL, including a short-lived negative entry for "not found" so random probing cannot turn into database load.
It checks disabled and expires_at, emits a click event to a queue, and returns the 302.

Only steps 1, 2 and 5 are on the path for a cache hit, which is most requests.

Caching and the hot-key problem

How much the cache helps depends on how skewed popularity is. Link traffic is typically Zipf-like: a handful of links take a large share of clicks, and a long tail of links is clicked a few times each. With a Zipf exponent of 1 over one million links, the thousand most popular links receive about 52% of all redirects, the top ten thousand about 68%, and the top hundred thousand about 84%. A cache that holds 1% of the links serves two-thirds of the reads.

Cumulative share of redirect traffic against the k most popular links on a log axis, for Zipf exponents 1.0 and 0.8; the exponent-1 curve passes 52 percent at one thousand links and 68 percent at ten thousand — A Zipf popularity model over one million links. The steeper the skew, the smaller the cache that absorbs most reads; the same skew is what produces hot keys.

The same skew creates the problem. A single link that goes viral is one key, which lives on one Redis shard and one database row. At 12,000 requests per second for one key, that shard is doing all the work while the others idle, and if the key expires or is evicted, every replica misses at once and stampedes the database for the same row.

Four mitigations, cheapest first:

In-process cache. The LRU in step 2 means a viral key is served from memory in every replica after the first hit. Redis sees one request per replica per 30 seconds for that key, not 12,000 per second.
Request coalescing. When many concurrent requests in one process miss on the same key, let one of them fetch and have the others wait for that result (Go's singleflight, or a per-key promise). This turns a stampede of misses into a single fetch.
Key replication. For keys known to be hot, store link:{code}:0 through link:{code}:7 on different shards and have readers pick a random suffix. This spreads one key's load over eight shards at the cost of eight writes on update.
Edge caching. A Cache-Control: public, max-age=60 on the 302 lets a CDN serve the redirect from its edge nodes. You lose one minute of precision on disable and on click counts, which is usually a fine trade for a link that is currently being clicked by the whole internet.

TIP

Set Redis TTLs with a little jitter (EX 1800 + random(0, 300)) so that keys populated in the same burst do not all expire in the same second. Synchronized expiry is a common self-inflicted stampede.

What I would build first

A single PostgreSQL instance, a stateless HTTP service with random 7-character codes and the in-process LRU, and 302 redirects. No Redis until the database shows read pressure, no sharding until the table passes a terabyte, no range allocator unless codes must be short or sequential. The design above is the map of where to go when each of those happens; the arithmetic is what tells you that most shorteners never get there.