08 — Design A URL Shortener

This chapter designs a link shortener from the numbers up. It covers four things:

• Deriving the length of the short code from the ten-year link volume.
• Why hashing the URL and truncating the result cannot avoid duplicate codes.
• Sizing the memory cache that carries the read traffic.
• Why the choice between two HTTP redirect status codes determines how much analytics data the product can collect.

What goes in and what comes out

The input is one long web address:

https://example.com/2026/q3/annual-report?utm_source=email&utm_campaign=q3

The output is a short one:

https://sho.rt/8Kq2mZ1

Those last seven characters — 8Kq2mZ1 — are a code the service generated and stored next to the long URL.

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 instead. The browser follows it to the original URL.

The core logic is small; most of the design is in the parts around it. Two numbers decide it: the total number of links ever created, which fixes the code length, and the number of clicks per link, which fixes everything else.

Where candidates lose this round

There are three common failures, and all three appear later in this chapter with the arithmetic that settles them:

1. Picking “6 or 7 characters” with no arithmetic behind it (3b how long is the code).
2. Claiming a hash-based scheme will not produce duplicate codes (7a hash the url and truncate).
3. Treating the choice between HTTP status codes 301 and 302 as trivia rather than as the decision that determines how much analytics data the product can collect (Deep dive 3 301 vs 302 is an analytics decision).

What you do not need to have read

Three other chapters go deeper on machinery this one only uses:

• Chapter 02 — estimation technique.
• Chapter 07 — the ever-increasing integer this design turns into codes.
• Chapter 04 — the limit on how fast one caller may create links.

You do not need any of them to follow this chapter. Each idea is restated here where it is used.

1. Framing: what decision, and what breaks

A shortener is mechanically 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.

Three product properties pull in different directions, and every later trade-off is a move between them. In the table below, the middle column is what the product wants and the right column is what it costs to build.

Three words that carry the rest of the chapter

Keyspace is the count of distinct codes the format can express. Seven characters drawn from a 62-symbol alphabet gives 62 multiplied by itself seven times, written 62^7. 3b how long is the code works out what that equals.

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 website. The arithmetic below quantifies it.

Density is the fraction of the keyspace you actually use. A scheme that spreads 365 billion links thinly across 3.5 trillion possible codes is sparse. Sparseness is what makes a code expensive to guess, because most codes an attacker tries will be dead.

A short code is obscure, never secret. The arithmetic below gives the exact number of guesses it costs an attacker to find a live link.

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

2. Requirements

This section lists what the service must do, what it will not do, and the performance targets the later sections are built to satisfy. Beneath these sit six assumptions, separated into the ones that would change the architecture if they were wrong and the ones that would only change how many machines you buy.

Functional

• shorten(long_url) -> short_url, optionally with a custom alias — a code the customer chooses rather than one the service invents — and an expiry date.
• GET /{key} redirects to the original URL. GET is the ordinary HTTP verb a browser uses to fetch a page, and {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, which the browser reports in a request header.
• Delete or disable a link; a disabled link must stop redirecting everywhere, promptly.

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

Non-functional — these decide the design

Six targets, each with the reason it is set where it is. The right column gives the justification for each number.

Three of those rows use terms of art.

p99 is the 99th percentile. Sort every request of the day by how long it took; the p99 is the time the slowest 1% exceeded. It is the number a user notices, because a mean hides the bad tail entirely — a service where 99 requests take 5 ms and one takes 5 seconds has a mean of 55 ms and a p99 of 5 seconds.

Availability is the fraction of the year the service answers. Multiply the shortfall by the minutes in a year:

minutes in a year
  365 x 24 x 60                         =  525,600
99.99% allows a shortfall of 0.01%
  525,600 x 0.0001                      =  52.6 minutes/year
99.9% allows a shortfall of 0.1%
  525,600 x 0.001                       =  525.6 minutes/year  =  8.8 hours

One extra nine is a factor of ten in permitted downtime. That is the whole reason 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. It becomes a real problem the moment reads are served from copies of the database that lag behind 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 building two different paths: a cached, edge-served read path and a coordinated, validated write path.

The assumptions this design rests on

Every number below flows from six stated assumptions. The right column marks whether being wrong about an assumption changes the shape of the system or only its size.

A load-bearing assumption is one where being wrong changes the shape of the system, not the size of the fleet. Four qualify here, and each is examined below.

The read:write ratio is load-bearing because it decides which path gets the engineering. At 10:1 the write path can be slow and coordinated; at 2:1 you have a write-heavy system pretending to be a read-heavy one and the code allocator becomes the bottleneck; at 100:1 the write path stops mattering at all and the design is entirely cache and edge.

The popularity skew is the most load-bearing assumption here, and it produces the cache result in Deep dive 2 the read path and the 11 h leverage. The claim that 10 GB of memory absorbs 96% of reads is not a property of caching in general; it is a property of traffic where a small number of links take most of the clicks. If clicks were spread evenly across the day’s 100 million distinct links, a cache holding 50 million of them would serve exactly 50% of reads, and no amount of extra memory would change that. The non-linear payoff of the last few gigabytes exists only because the distribution is skewed.

The latency budget is load-bearing because 50 ms at p99 forbids a cross-continent round trip on the common path, which is what forces content to be served from edge locations near the user rather than from one region.

The failure-tolerance asymmetry is load-bearing because it allows clicks to be counted asynchronously. If a lost click were as unacceptable as a lost link, the redirect would have to wait for a durable write to the analytics store, and Deep dive 3 301 vs 302 is an analytics decision would have a very different answer.

The two that are not load-bearing are the peak multiplier and the data size. Doubling the peak factor buys more machines; getting the row size wrong by 50% moves a storage figure that was never the constraint. Getting a non-load-bearing assumption wrong costs money. Getting a load-bearing one wrong costs a rewrite.

3. Back of the envelope

The assumptions now become the four numbers the rest of the chapter uses: the request rate, the code length, the storage footprint, and the bandwidth.

Technique and rounding discipline come from chapter 02.

One convention runs through every figure below: a day has 86,400 seconds, and this chapter rounds that to 100,000 to simplify the division. Dividing by 100,000 moves a decimal point five places; dividing by 86,400 does not.

That shortcut introduces a known error. Two percentages are involved, and only one applies to the answers:

how far the divisor is off
  100,000 / 86,400                      =  1.157      the divisor is 15.7% too big

how far the answer is off, per second
  86,400 / 100,000                      =  0.864      the quotient is 13.6% too small

The figures below carry the 13.6%, not the 15.7%. Dividing by a number that is too big gives an answer that is too small, and the two percentages differ because they are reciprocals of each other, not the same fraction seen twice. So every per-second figure in this chapter is about 14% under the true rate. That is a deliberate and consistent bias, not a mistake — and if it ever matters, multiply by 1.16 to recover the true number.

3a. Volume

Start from the two assumed volumes and derive how many requests per second the service handles — the quantity usually written QPS, for queries per second.

The block below has four steps. It converts links per day into reads per day, then divides both by the seconds in a day to get per-second rates, then multiplies by 3 for the busy hour. The write line and read line keep a 10:1 ratio throughout; that ratio is the output that matters, not the absolute numbers.

assume  100 M new links/day, and 10 clicks per link over its lifetime

writes per day
  100,000,000
reads per day
  100,000,000 x 10                      =  1,000,000,000

write QPS
  100,000,000 / 100,000                 =  1,000
read QPS
  1,000,000,000 / 100,000               =  10,000

peak, at 3x
  1,000 x 3                             =  3,000
  10,000 x 3                            =  30,000

The read:write ratio is 10:1 and it is the most important number in the chapter.

It says two things. First, the write path is allowed to be slow, coordinated, and expensive per operation — there are ten times fewer writes, and no human is blocked on the millisecond when creating a link. Second, a cache is not an optimization here, it is the architecture (Deep dive 2 the read path and the 11 h leverage).

Sensitivity to this number:

• At 100:1 (a marketing-heavy corpus) the write path stops mattering, and the design is entirely the cache and the edge.
• At 2:1 the system is write-heavy, and the allocator becomes the bottleneck.

3b. How long is the code?

This derives the code length from the ten-year volume.

What base 62 means

Codes are written in base 62: a positional numbering system whose 62 symbols are the digits 0-9 (10 of them), the uppercase letters A-Z (26), and the lowercase letters a-z (26). That is 10 + 26 + 26 = 62.

It is the same idea as decimal, which uses 10 symbols, or binary, which uses 2. In decimal, three digits express 10 x 10 x 10 = 1,000 distinct values. In base 62, three characters express 62 x 62 x 62 = 238,328. Each extra character multiplies the count of expressible values by 62.

So a code of L base-62 characters expresses 62^L distinct values, and the question “how many characters?” is really “how many distinct links must the format hold over its lifetime?”

Sizing the ten-year demand

First, the demand. How many codes must ever exist?

links created in ten years
  100,000,000 links/day x 365 days/year x 10 years  =  365,000,000,000

365 billion codes. Now the supply. Multiply 62 by itself and see where the running total crosses 365 billion:

62^5 = 62 x 62 x 62 x 62 x 62          =  916,132,832           0.92 billion
62^6 = 62^5 x 62                       =  56,800,235,584        56.8 billion
62^7 = 62^6 x 62                       =  3,521,614,606,208     3,522 billion

Five characters gives 0.92 billion codes — not close. Six gives 56.8 billion, still short of 365 billion. Seven gives 3,522 billion, which clears it with room to spare.

Now convert each space into the thing a product manager understands: how many years it lasts before it runs out, at 100 million new links per day.

62^5, in days
  916,132,832 / 100,000,000                        =  9.2 days

62^6, in years
  56,800,235,584 / 100,000,000 = 568 days
  568 / 365                                        =  1.56 years

62^7, in years
  3,521,614,606,208 / 100,000,000 = 35,216 days
  35,216 / 365                                     =  96.5 years

And the headroom of the seven-character space over what the ten-year requirement actually needs:

  3,521,614,606,208 / 365,000,000,000              =  9.65x

Six characters buys 1.56 years and seven buys 96.5, so the answer is seven. Five, at nine days, is not viable.

The 9.65x headroom is not spare slack. It is budget spent later: on waste in the code allocator (Bottlenecks and scaling), and on the sparseness that makes guessing expensive (7b base 62 of a counter).

Why base 62 and not base 64, 58, or 36

The alphabet is a separate choice from the length. The block below gives the size of each candidate space at 7 characters, plus base 36 at 8, to compare against the 365,000,000,000 requirement.

64^7                                    =  4,398,046,511,104     above  -> 7 chars is enough
58^7                                    =  2,207,984,167,552     above  -> 7 chars is enough
36^7                                    =     78,364,164,096     BELOW  -> 7 chars is not enough
36^8                                    =  2,821,109,907,456     above  -> 8 chars needed

• Base 64 is the encoding normally used to carry binary data through text channels; it adds two symbols to the same alphabet. It is still 7 characters for 365 billion links, so it shortens nothing — and it costs real usability. Standard base 64 uses + and /, and / is the path separator and + decodes to a space in a query string (RFC 3986, the specification that defines what characters mean inside a URL), so a raw base-64 code is not a valid path segment. The base64url variant swaps in - and _, which are URL-safe, but _ vanishes under an underline in a mail client, and both read as noise when a code is dictated over a phone.
• Base 58 drops the four glyphs that get misread (0 against O, and 1 against l and I). It still covers 365 billion in 7 characters: 2,207,984,167,552 / 365,000,000,000 = 6.0x headroom instead of 9.65x. Losing headroom you were never going to spend, in exchange for fewer mistyped links, is free.
• Base 36 treats upper and lower case as the same symbol, so it needs 8 characters. 36^7 is 78 billion, well under the 365 billion required, and only 36^8 at 2,821 billion clears it. Case-insensitivity costs exactly one character — a product call, and the right one if links get read aloud in radio ads or typed off packaging.

3c. Storage over ten years

Pricing the data establishes that storage is not the constraint, with one exception that is easy to miss.

A row is not just its visible columns. A database also stores index entries that let it find the row quickly, plus per-row bookkeeping. Those overheads are counted here using the page-layout arithmetic from sql/03.

Read the block in two halves. The top half is data you can see in the schema; the bottom half is the overhead the storage engine adds, which is 52% as large again as the data itself.

long_url, average                        100
short_key, 7 chars at 1 B                  7
user_id                                    8
created_at                                 8
expires_at                                 8
                                         ---
row payload                              131
primary-key index entry (8 + 8 + 4)       20
unique index on short_key (8 + 8 + 4)     20
row header + line pointer                 28
                                         ---
per link, all-in                         199

The three overhead lines, spelled out:

• Each index entry is 8 + 8 + 4 = 20 bytes: 8 for the indexed value, 8 for the pointer to the row it refers to, and 4 of per-entry bookkeeping. There are two indexes here — one on the primary key id, one enforcing UNIQUE on short_key — so that is 20 twice.
• row header + line pointer is 28 bytes. In Postgres, the reference engine for this repo’s storage arithmetic, every row carries a 23-byte header padded to 24 (it holds transaction visibility information), and the page’s slot directory adds a 4-byte line pointer so the engine can find the row inside its page.

Adding the halves: 131 + 20 + 20 + 28 = 199. Call it 200 B.

Now multiply that 200 B by the volume, and follow it out to ten years of replicated storage.

bytes per day
  100,000,000 x 200                     =  20,000,000,000
GB per day
  20,000,000,000 / 1,000,000,000        =  20
ten years, one copy, in TB
  20 x 365 x 10 / 1,000                 =  73
at replication factor 3, in TB
  73 x 3                                =  219

Replication factor 3 (RF 3) means every row is stored on three separate machines, so that losing two of them loses no data. It is the standard price of durability, and it is why 73 TB of logical data becomes 219 TB of disk you actually buy.

73 TB of primary data is not a hard problem; it is 8 to 20 commodity boxes. Storage is not the binding constraint, with one exception.

The click log is a second dataset. Compare its daily growth against the URL table’s daily growth from the block above:

click events per day at 50 B each
  1,000,000,000 x 50                    =  50,000,000,000
ratio to the URL table's daily growth
  50,000,000,000 / 20,000,000,000       =  2.5
one year of raw click rows, in TB
  50 x 365 / 1,000                      =  18.25

The analytics log grows 2.5x faster than the thing it measures: 50 GB a day of click rows against 20 GB a day of link rows.

This dictates four moves. Raw click rows do not belong in the same store, do not get an index, and mostly should not exist for long:

1. Write them to a queue — a buffer that accepts events instantly and lets a separate process consume them at its own pace — so the redirect never waits on the analytics store.
2. Roll them up into per-link, per-hour counters, which is the only granularity anyone queries.
3. Keep raw events for 30 days for the fraud and abuse pipeline (Deep dive 4 abuse which most answers skip), then drop them.
4. Put the rest in columnar cold storage, which stores each field contiguously and so compresses far better for the scan-heavy queries analytics actually runs.

Bandwidth

The last quantity to price is network throughput, which turns out to be a non-issue. Multiply the read rate by the size of one redirect response, then convert bytes per second to bits per second by multiplying by 8:

redirect response, ~500 B of status line + Location + headers
  10,000 responses/s x 500 B            =  5,000,000 B/s
the same in Mbps
  5,000,000 x 8 / 1,000,000             =  40 Mbps

A redirect carries no page body, only a status line, a Location header and a few others — which is why 500 B covers it.

40 megabits per second runs against the 1 gigabit per second a standard server network card sustains: 40 / 1,000 = 4%. Bandwidth is 4% of one network card, so this is a request-rate and latency problem, never a bytes problem — the opposite of the video and photo estimates in chapter 02, where the bytes are the whole difficulty.

4. API sketch

The request and response shapes are worth pinning down, because three of the choices in them matter.

Four endpoints. Note the status codes under GET /{key}: there are four of them, and which one comes back for a dead link is one of the three key choices below.

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 section 9)
  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

The three-digit numbers are HTTP status codes, the standard vocabulary a server uses to say what happened. The ones used above:

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

The three graded choices

1. 410 Gone, not 404, for a deleted link. 404 means “never existed,” which is inaccurate. It costs a support ticket every time a customer’s expired campaign link gets reported as a bug. 410 means “existed and is now withdrawn,” which is accurate and self-explaining.

Never redirect a dead link to your homepage; that invites treating your domain as a generic redirector.

2. idempotency_key, not automatic dedupe by URL. An idempotency key is a client-generated identifier attached to a create request, so that a retry after a timeout produces the same link rather than a second one. It makes the operation idempotent: doing it twice has the same effect as doing it once.

That is not the same as globally deduplicating by destination, and the difference is the one to state. Two different users shortening the same destination want two links, two click counters, and two expiries. Merging them destroys the product.

The alternative was considered and priced. Global dedupe at an assumed 30% duplicate rate saves 30% of the ten-year storage:

  73 TB x 0.30                          =  21.9 TB

Do not trade the product for 22 TB. That is a few thousand dollars a year against per-user analytics that customers are paying for.

3. Create is rate limited per API key and per source IP. Each caller is capped at some number of creates per interval, using the token-bucket scheme derived in chapter 04. Deep dive 4 abuse which most answers skip explains why this is a correctness control and not a cost control.

5. Data model

The access pattern, more than the schema, is what matters here: this is a key-value workload rather than a relational one.

Two tables. Note what is in the second one: rolled-up counters keyed by (short_key, hour, country, referrer_hash), not one row per click.

urls
  id           BIGINT   PRIMARY KEY   -- dense counter, section 7b
  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

Why this is a key-value workload

The access pattern is a single-key point lookup with no joins, no range scans, and no cross-key transactions.

Each term describes something this workload does not do:

• A point lookup fetches exactly one row by its exact key. GET /8Kq2mZ1 is a point lookup and nothing else.
• A join combines rows from two tables. Nothing here joins.
• A range scan walks a span of consecutive keys, like “every link created last Tuesday.” Nothing here scans.

A store that only has to serve point lookups is a key-value store: it does nothing but map one key to one value (chapter 06). That is the argument for using one instead of a general-purpose relational database (an RDBMS, relational database management system), whose joins, transactions and ordered indexes would all go unused while still costing you something.

Partition it by hash. Hash-partitioned means the store computes a hash of short_key and uses that number to pick which machine holds the row, so a lookup touches exactly one machine and never has to ask around.

Do the partitioning with the hash ring from chapter 05, which places both keys and servers on a circle of hash values. The alternative — the obvious “hash modulo server count” — reassigns almost every key when the server count changes. Growing from 16 machines to 17 with modulo moves about 94% of the corpus; the ring moves 1/(N+1), which here is 1/17 = 5.9%.

The consistency requirement is unusually weak

A link is written once and never updated. This has one consequence: two copies of the data can only ever disagree about whether a row exists, never about what it says. There is no such thing as a stale destination.

So the write must be durable before the API returns — the user is about to paste that link — but the reads can be served from anywhere. In the language of quorums, which are schemes where a write is acknowledged by W copies and a read consults R of them, this is a high W and an R of 1.

Two things the schema deliberately omits

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 it indexes.

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 those writes to one row on one machine.

That is a hot key: a single key receiving a wildly disproportionate share of traffic. It is the fastest way to melt a shard, which is one of the machines the data is split across, each holding a disjoint slice of the rows.

Here the slice is chosen by the hash of short_key, so a hot key is by construction a hot shard — and adding shards does not help, because the key hashes to the same place every time. Deep dive 2 the read path and the 11 h leverage puts a number on it: 6,000 QPS onto one machine.

6. High-level architecture

All the pieces fit together below, and each box is an assertion a later section justifies.

The diagram has two independent halves. The top half, starting at the first Client, is the read path a browser takes when someone clicks a short link. The bottom half, starting at Client again, is the write path when someone creates one. They meet only at the store, DB. The write path is longer than the read path; that asymmetry drives the design.

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

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

    style EDGE fill:#2d6a4f,color:#fff
    style C fill:#2d6a4f,color:#fff
    style DB fill:#1d3557,color:#fff
    style TS fill:#bc6c25,color:#fff
    style SAFE fill:#9d0208,color:#fff

The colour key

This chapter uses the same four hex colours for two different jobs, so it says which is which each time.

Here the colours mark component roles:

Both caches are green for the same reason: an edge PoP is not a different kind of thing from the shared cache, only a closer one.

The Deep dive 4 abuse which most answers skip diagram reuses the same four hexes as verdicts instead — green created, orange interstitial, red rejected. Different key, stated there.

Walking the read path

A client — a browser following a short link — issues GET /8Kq2mZ1 to the nearest edge PoP. A PoP is a point of presence: a small rack of servers the company operates in a city close to users. This one holds a key-value copy of the hottest million codes.

A miss is a request whose key is not in that copy. Misses fall through to a load balancer, a machine that spreads requests evenly across a pool of identical servers, and from there to the redirect service.

That service is stateless: it keeps nothing between requests. Any instance can serve any request, so instances can be added or killed freely, which is what makes the read tier cheap to scale.

It consults the shared cache, which maps a hot key to its long URL and also holds the blocklist bloom filter of Deep dive 4 abuse which most answers skip. Only on a second miss does it read the KV store. That store is hash-partitioned on short_key at RF 3: it picks the machine from a hash of the code, and keeps three replicas of every row.

Separately, the service drops a click event onto the click queue. The arrow is labelled async, fire and forget, meaning the redirect goes back to the browser without waiting for the queue to accept the event. Rollup jobs later aggregate those raw events into the hourly counters of Data model.

Walking the write path

A client posts to the write service, which does four things in order:

1. Consults the rate limiter of chapter 04, capping how fast one caller may create links.
2. Draws a number from the counter allocator — a single row handing out contiguous blocks of integers (7b base 62 of a counter).
3. Runs the destination past a reputation check against Google Safe Browsing and internal blocklists (Deep dive 4 abuse which most answers skip).
4. Writes the row to the same KV store.

The four assertions, and the arrow people leave out

Four claims are drawn in that picture and argued later:

• The code comes from a permuted counter (Deep dive 1 where the seven characters come from).
• The read path is a cache with a database as the fallback (Deep dive 2 the read path and the 11 h leverage).
• Clicks are counted asynchronously and never block the redirect (Deep dive 3 301 vs 302 is an analytics decision).
• Every write goes through reputation screening (Deep dive 4 abuse which most answers skip).

The arrow often omitted is the write-through from WR into C: the write service populates the cache at creation time, rather than waiting for the first read to do it.

The reason: the creator tests the link within seconds of making it. Against a lazily-populated cache that first read is a guaranteed miss, and it may also miss a database replica that has not caught up yet, which is exactly the read-your-writes requirement from Requirements failing. Populating on create makes read-your-writes free, instead of forcing you to route reads to the primary copy.

7. Deep dive 1: where the seven characters come from

There are two ways to produce the code, and they fail in opposite directions. The two families, before the arithmetic: 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 always give identical codes, and there is no shared state anywhere. A counter-based scheme instead keeps one ever-increasing integer, hands the next value to each new link, and encodes that integer as the code; codes are guaranteed distinct, but every writer must agree on whose turn it is. Hashing trades duplicate codes for statelessness; counting trades coordination for a guarantee.

7a. Hash the URL and truncate

The scheme, in four steps

1. Take SHA-256(long_url). SHA-256 is a standard hash function that turns any input into 256 scrambled bits.
2. Keep the leading 42 bits. Why 42? A 7-character base-62 code needs 7 x log2(62) = 7 x 5.954 = 41.68 bits of information, and you cannot keep a fraction of a bit, so 42 is the smallest whole number that covers it.
3. Reduce that value mod 62^7 so it lands inside the space the codes actually live in.
4. Encode the result in base 62. If that code is already taken, hash again with a salt — an extra value mixed into the input to get a different answer out of the same URL.

Step 3 is not a detail

Leaving out the mod is a bug that this chapter’s own encoder catches.

42 bits is the smallest width that covers 62^7. “Covers” means it is at least as big — which necessarily means it overshoots:

2^42                                    =  4,398,046,511,104
62^7                                    =  3,521,614,606,208
                                           ---------------
the gap                                 =    876,431,904,896

fraction of 42-bit values that do not fit in 7 characters
  876,431,904,896 / 4,398,046,511,104   =  0.199

One 42-bit value in five is too large for a 7-character code. That is not hypothetical: encode(4_000_000_000_000) in 7d working python raises OverflowError for exactly this reason, because 4 trillion sits above 62^7.

There is a second reason the reduction matters. The collision arithmetic below is computed against M = 62^7. Skip the reduction and you are analysing the scheme in a space it does not actually draw from, so every number in the next block would be wrong.

This is the same range problem that 7c the fix permute the counter do not randomize it solves for the Feistel construction using cycle-walking. A hash can take the cheaper fix — plain mod — because unlike the permutation it has no bijection to preserve.

One caveat, for accuracy rather than for the conclusion: mod is not perfectly uniform. Codes below 2^42 - 62^7 (24.9% of the space) have two 42-bit values mapping onto them and are therefore twice as likely as the rest. That raises expected collisions about 12% above the uniform figure below and changes nothing about the argument. Cycle-walk instead of reducing if you want it exactly uniform.

What this scheme genuinely buys: the same long URL always produces the same code, so deduplication is free. What it does not buy is freedom from collisions.

The birthday bound, and why the intuition fails

The relevant tool is the birthday bound. In a room of 23 people, two share a birthday more often than not — even though there are 365 days in a year, which feels like it should require far more people.

The reason is that the thing being counted is pairs, not people, and pairs grow as the square. Twenty-three people make 23 x 22 / 2 = 253 pairs, and 253 chances against 365 days is a coin flip.

Apply that to codes drawn at random from a space of size M: the first duplicate appears after roughly the square root of M draws, not after M of them. Square roots are much smaller than people expect, which is where the six-orders-of-magnitude error comes from.

Running the numbers on 62^7

The block below computes five quantities. Read it top to bottom: the fill ratio in line 2 is the input to everything under it.

the space, M
  62^7                                  =  3,521,614,606,208

fill after ten years, n / M
  365,000,000,000 / 3,521,614,606,208   =  0.1036          (10.36%)

expected collisions over the decade, n^2 / 2M
  365,000,000,000^2                     =  1.33225e23
  1.33225e23 / (2 x 3,521,614,606,208)  =  18,900,000,000

average collision probability per insert, n / 2M
  0.1036 / 2                            =  0.0518          (5.18%)

collision probability on the last insert of the decade, n / M
                                        =  0.1036          (10.36%)

the point where a first collision is more likely than not, 1.177 x sqrt(M)
  sqrt(3,521,614,606,208)               =  1,876,596
  1.177 x 1,876,596                     =  2,208,754 links

and how long that takes at 100 M/day, in minutes
  2,208,754 / 100,000,000               =  0.0221 days
  0.0221 x 24 x 60                      =  31.8 minutes

Two of those lines need their formula explained rather than just applied.

The fill ratio, n / M, is the fraction of the keyspace occupied — 10.36% after ten years. It drives everything else, because a random draw lands on an already-occupied code with exactly that probability.

Expected collisions is n^2 / 2M because there are about n^2 / 2 pairs of links, and each pair has a 1 / M chance of sharing a code. Multiply the two: (n^2 / 2) x (1 / M) = n^2 / 2M. The 1.177 x sqrt(M) in the last line is the standard birthday-bound constant for a 50% chance of at least one collision.

The three things to say

1. The first collision arrives about 32 minutes after launch. Any claim that “collisions are so rare we can ignore them” is wrong by six orders of magnitude.
2. By year ten, one insert in ten collides (10.4%). Averaged over the decade that is 5.2% of all writes, so the retry path is not an edge case — it is one write in twenty, and it must be tested.
3. It forces a read-before-write, or at minimum a unique-index conflict, on every create. That is affordable at 3,000 peak writes/s, but it means you can never simply insert blindly.

What it would take to make hashing honest

To reach the fill ratio a counter gets for free, you need one more character:

62^8                                    =  218,340,105,584,896
fill after ten years
  365,000,000,000 / 218,340,105,584,896 =  0.00167          (0.167%)
one collision every
  1 / 0.00167                           =  599 inserts

Compare 1-in-599 against 1-in-10 at seven characters. So the honest hash-based design is 8 characters, not 7. Truncated hashing costs a character, which is 14% of the code length.

7b. Base-62 of a counter

The alternative is to get a dense, monotonically increasing integer — one that goes up by exactly one each time, leaving no gaps — and encode it in base 62. That yields zero collisions by construction, no read before the write, and the full 62^7 space actually usable.

The allocator is a ticket server: one row in one database holding the next unissued value, handing out contiguous blocks of numbers to write nodes, which then serve individual links out of their block without talking to anyone. Chapter 07 rejects exactly this design for general-purpose ID generation, and it is worth naming why it wins here and loses there.

The competing scheme there is a Snowflake ID: a 64-bit identifier assembled from a timestamp, a machine number, and a per-millisecond sequence counter, so that every machine can mint unique IDs without ever coordinating with another machine.

That works, and it is the right answer for general ID generation. But it makes the numbers sparse. Twenty-two of the 64 bits are spent on machine number and sequence, which means the timestamp sits in the high bits and every millisecond that passes jumps the value forward by 2^22 = 4,194,304 whether or not any IDs were minted. The values skip most of the number line.

Sparseness costs characters, because the code length is set by the largest value, not by how many values you used. Work out how large a Snowflake ID gets after ten years, then find which base-62 space contains it:

milliseconds in ten years
  10 years x 365 days x 86,400 s x 1,000       =  315,360,000,000 ms
each millisecond advances the ID by 2^22
  315,360,000,000 x 4,194,304                  =  1,322,715,709,440,000,000

the base-62 spaces that bracket it
  62^10                                        =    839,299,365,868,340,224
  62^11                                        =  52,036,560,683,837,093,888

The largest ID, 1.32e18, exceeds 62^10 (0.84e18) but fits inside 62^11. So base-62 of a Snowflake ID is an 11-character code for the same 365 billion links the counter encodes in 7.

Uniqueness is what an ID generator sells; density is what a shortener needs, and those are different products.

The four extra characters are the price of never talking to a coordinator. Here you can afford to talk to one, because handing out blocks makes the coordinator almost idle:

allocator calls per second = write QPS / block size
  1,000 / 1,000                                =  1 call/s
  1,000 / 10,000                               =  0.1 call/s   (one every 10 s)

At the block size of 10,000 chosen in Bottlenecks and scaling, the single coordinated component in this system is contacted once every ten seconds across the entire fleet.

A counter has one problem: its output is ordered. Codes come out in creation order, which leaks three things:

• An attacker walks 0, 1, 2, ... and enumerates every link ever created, at one request per link found instead of the roughly 9.6 requests a random probe of a 10.4%-full space would cost.
• Two codes minted a day apart subtract to give the day’s exact link volume, the same business-metric leak Snowflake has (chapter 07).
• The code tells you a link’s relative age, which is enough to isolate “everything created during the incident.”

Enumeration is the real privacy failure here, because the entire industry treats an unlisted short link as a private one — shared documents, invoices, unlisted video links, password-reset pages that were shortened by a well-meaning support agent.

7c. The fix: permute the counter, do not randomize it

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

What a Feistel network is

A Feistel network is a standard way to build a cipher out of any scrambling function. Split the number into a left half and a right half, then four times over, replace the pair with:

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

where f is any keyed function — here, a SHA-256 of the key, the round number and the value.

Every round is reversible, whatever f does. To undo a round you already have right (it became the new left), so you can recompute f(right) and XOR it back out. That makes the whole construction a bijection: a one-to-one mapping where every input has exactly one output, and every output exactly one input.

A bijection cannot collide. The permuted counter inherits the raw counter’s zero-collision guarantee exactly: no storage, no uniqueness check, no retry loop.

Fitting a power-of-two cipher into a base-62 space

A Feistel network works on a domain that is a power of two, because it splits the number into equal bit-halves. So use 42 bits — two halves of 21 — which is the same 42 bits 7a hash the url and truncate needed, and it overshoots 62^7 by the same 20%.

Handle the overshoot with cycle-walking: if the encrypted value lands above 62^7, encrypt it again, and repeat until it lands inside. Because a permutation maps the out-of-range values only among themselves, cycle-walking is still a bijection on the range you keep — nothing in range can be produced twice.

The cost is the number of encryptions you expect to run before landing in range, which is just the ratio of the two spaces:

  2^42                                  =  4,398,046,511,104
  62^7                                  =  3,521,614,606,208
expected encryptions per code
  4,398,046,511,104 / 3,521,614,606,208 =  1.25

1.25 hash operations per code, and in exchange the external code is uncorrelated with the internal counter.

Being a bijection, it is also invertible, which has a useful consequence: 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, because they were never encrypted from anything. And the cipher key can never be rotated without orphaning every code ever issued.

What the permutation does and does not buy

It removes the ordering leak, removes the volume leak, and raises the attacker’s enumeration cost from 1 request per hit to 9.6 — because a random guess now hits an occupied code only at the 10.4% fill rate:

requests per live link found, random guessing at 10.4% fill
  1 / 0.1036                            =  9.6

It does not make links secret. At 10.4% fill, an attacker guessing 7-character codes finds a live link roughly every 10 tries. Even at 8 characters it is 1 in 599.

A short code is obscurity. The mitigations that actually work are rate limiting GET by IP (chapter 04) plus a real authorization check on anything genuinely confidential.

The cheap alternative was considered: a dense counter followed by two random characters. It multiplies an attacker’s work by 62^2 = 3,844 per known code, but it leaves the ordering and volume leaks fully intact, because the counter part is still in the open. The permutation fixes all three leaks in the same 7 characters, so it wins outright.

7d. Working Python

The code below is the whole scheme in runnable form: a base-62 encoder and decoder, then the keyed permutation, with assertions that check the round trip and prove on a small domain that the permutation never collides.

Start with the codec. encode repeatedly divides by 62 and collects the remainders — that is the standard way to write a number in any base, the same procedure you would use by hand to convert to binary. decode runs it backwards with Horner’s rule, multiplying the running total by 62 and adding each digit.

The assertions after the two functions pin the boundaries: 0 is all zeros, 61 is the last single symbol z, 62 rolls over into a second place, and 62^7 - 1 is zzzzzzz, the largest code that fits, whose decimal value is one less than the 3,521,614,606,208 derived in 3b how long is the code.

"""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 BASE == 62
assert encode(0) == "0000000"
assert encode(61) == "000000z"
assert encode(62) == "0000010"
assert encode(62 ** 6) == "1000000"
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))
assert all(decode(encode(n)) == n for n in
           (62 ** 6 - 1, 62 ** 6, 10 ** 9, 10 ** 11, 62 ** 7 - 1))

The permutation follows. feistel runs the four rounds forward and feistel_inv runs them backward; permute and permute_inv wrap each in the cycle-walking loop.

Four lines matter:

• In feistel, left, right = right, left ^ _round_fn(...) is the single round from the diagram above, and the loop runs it four times.
• In feistel_inv, the rounds run in reversed(range(rounds)) and the assignment is the mirror image. Nothing about _round_fn needs to be invertible for this to work — that is the property that makes Feistel networks useful.
• In permute, while True: ... if x < limit: return x is cycle-walking: keep re-encrypting until the value lands under 62^7.
• The three assertion blocks at the bottom check three different claims: that the round trip recovers the counter (so no index lookup is needed), that consecutive counters produce unrelated codes (the enumeration fix), and — on a toy domain small enough to enumerate exhaustively — that the output is a permutation of the input, which is the proof that it collides zero times.

The last assertion: sorted(image) == list(range(TOY_LIMIT)) says every value in [0, 50000) appears exactly once in the output. If any two inputs collided, some value would appear twice and another not at all, and the sort would not match.

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))
assert all(permute_inv(y, "k", TOY_HALF, TOY_LIMIT) == n
           for n, y in enumerate(image))

8. Deep dive 2: the read path, and the 1/(1-h) leverage

Sizing the cache produces a key result: the last few gigabytes of memory are worth far more than the first. That result is, as flagged in The assumptions this design rests on, entirely a consequence of one assumption about how clicks are distributed.

The workload, and why it is the friendliest cache in the book

Start with the shape: 10,000 reads/s against 73 TB, where the value is immutable once written — a short 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 can answer itself; 1 - h, the miss rate, is the fraction that fall through to the database.

Immutability is what makes this workload easy. There is no invalidation problem except deletion, which is rare and can be handled with a short time-to-live plus an explicit purge. A time-to-live (TTL) is an expiry stamped on a cache entry so stale copies age out on their own, without anyone having to remember to delete them.

The assumption that produces the result

Assume the day’s 1 billion clicks land on 100 million distinct links — that is the 10-clicks-per-link assumption from 3a volume — and that popularity is Zipfian.

A Zipf distribution is heavily skewed: the n-th most popular item gets roughly 1/n of the traffic the most popular one gets. The second-most-popular link gets half the clicks of the first, the tenth gets a tenth, the hundredth a hundredth. Word frequencies, city sizes and link clicks all behave this way empirically.

For the Zipf exponent s = 1, the top m items out of K cover ln(m) / ln(K) of all accesses. Substitute K = 100,000,000:

  ln(100,000,000)                       =  18.42
  h = ln(m) / 18.42

which, converting from natural log to base 10, is the same as
  h = log10(m) / log10(100,000,000)  =  log10(m) / 8

That second form is the one to carry into an interview, because it is mental arithmetic. Cache a million entries and log10(1,000,000) = 6, so 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.

Sizing the cache

Before the table, one column needs its unit justified.

A cache entry is not a database row. The 200 B row of 3c storage over ten years was 131 B of payload plus 68 B of storage-engine overhead — two index entries, a row header, a line pointer — and a cache carries none of that.

What a cache entry carries instead is the 7-byte key, the ~100-byte URL, the expiry, and the per-entry bookkeeping every in-memory store adds: object headers, a hash-table slot, a pointer or two, allocator size-class rounding. That also comes to roughly 200 B, by an entirely different route. The same figure appearing twice in this chapter is a coincidence, not a reused number.

Now the table. Each row is one choice of cache size. The first column is how many entries you hold, the second applies h = log10(m)/8, the third multiplies entries by 200 B, the fourth is the traffic that still reaches the database, and the last is the factor by which the database’s load was divided.

Work the last row by hand:

  log10(50,000,000)                     =  7.69897
  h = 7.69897 / 8                       =  0.96237      (the table prints 0.962)
  RAM = 50,000,000 x 200 B              =  10,000,000,000 B  =  10 GB
  DB QPS = 10,000 x (1 - 0.96237)       =  376
  leverage = 1 / (1 - 0.96237)          =  26.6

Carry the extra digits through that last row. The table prints h rounded to three places, but the two right-hand columns are computed from the unrounded 0.96237. Redo them from the printed 0.962 and you get 380 and 26.3 instead of 376 and 26.6 — the miss rate is such a small difference of large numbers that the fourth digit of h still moves the answer by about 1%.

10 GB of RAM takes the database from 3,750 QPS to 376.

The mechanism is a mismatch between two curves. The hit rate rises with the logarithm of the memory you buy, but database load falls as the reciprocal of the miss rate. A logarithm flattens out; a reciprocal blows up. So the two effects cross over, and the late gigabytes are worth more than the early ones:

• The first 20 MB buys 62 points of hit rate, and a 2.7x reduction in database load.
• The last 8 GB buys only 9 more points of hit rate — and takes the reduction from 8x to 26.6x.

That is the 1/(1-h) non-linearity from chapter 02 doing all the work.

Say plainly what that result depends on

It is the Zipf assumption, and nothing else.

Under uniform popularity — every link equally likely — caching half the links would answer half the requests, by definition:

uniform popularity, caching 50 M of 100 M equally-clicked links
  h = 50,000,000 / 100,000,000          =  0.50
  leverage = 1 / (1 - 0.50)             =  2.0

The same 10 GB gives 2.0x instead of 26.6x, and no purchase of memory would ever produce the 26.6x, because the curve is a straight line rather than a logarithm.

The whole read architecture — the shared cache, the edge tier, the in-process map — rests on this one assumption, so it is the first thing to check against real traffic.

Cross-check against 80/20

Sanity-check the Zipf law against the cruder rule of thumb that 20% of items take 80% of traffic. Caching 20% of the day’s distinct links is 20 million entries at 4 GB, and the two models disagree:

80/20 says
  h = 0.80        DB QPS = 10,000 x 0.20   =  2,000

Zipf s=1 says
  h = log10(20,000,000) / 8 = 7.301 / 8    =  0.913
                  DB QPS = 10,000 x 0.087  =    874

They disagree by more than 2x on database load. Provision on the pessimistic one — 2,000, not 874 — because over-provisioning wastes a little capacity while under-provisioning causes an outage.

Two extensions from the same table

Push it to the edge. The value is 100 bytes and never changes, so an edge PoP can answer the redirect outright without ever contacting the core.

Read the 1,000,000-entry row of the table: 200 MB, 75% hit rate. Put that in every PoP and three quarters of all clicks never make the 150 ms cross-continent round trip from chapter 02. 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, and at 30,000 peak QPS that is a lot of requests aimed at one key:

  30,000 x 0.20                         =  6,000 QPS onto one cache-tier machine

That is the hot-key problem from Data model, and consistent hashing explicitly does not fix it (chapter 05) — the key hashes to one place no matter how many machines you add.

What does fix it is a 10,000-entry map inside each application process, evicting on a least-recently-used (LRU) policy: when the map is full, throw out whatever has gone longest without being read. A hot key is by definition never the least recently used, so it never gets evicted, and every application node answers it locally. That is the same mechanism as the deny cache in chapter 04.

9. Deep dive 3: 301 vs 302 is an analytics decision

A one-line choice of HTTP status code silently decides how much of the product’s data you get to keep — and the resulting undercount cannot be corrected after the fact.

Both status codes send the browser to the destination. The difference is one line in the HTTP specification:

301 Moved Permanently is cacheable by default. 302 Found is not.

Cacheable here means the browser is entitled to remember the answer, and on the next click of the same short link, jump straight to the destination without asking your service at all. Your service never learns the click happened.

Price that. Assume 30% of clicks are repeat visits from a browser that has already resolved that link:

302: requests that reach the service
  10,000 QPS x 1.00                     =  10,000 QPS
301: requests that reach the service
  10,000 QPS x 0.70                     =   7,000 QPS

302: clicks the counter can see, per day
  1,000,000,000 x 1.00                  =  1,000,000,000
301: clicks the counter can see, per day
  1,000,000,000 x 0.70                  =    700,000,000

The same 30% appears in both halves, and that is the trade in one picture. 301 is a 30% discount on the read fleet, the edge bill, and the latency of a repeat click — and a 30% hole in the only data the product sells.

Why the hole cannot be calibrated away

An undercount of a known 30% sounds correctable: multiply everything by 1/0.7. That does not work here.

The clicks a 301 hides are exactly the repeat clicks. So the undercount is not spread evenly — it concentrates on your most engaged users and your most-clicked links, which are the two things the customer is paying to measure.

To correct it you would need the per-link repeat rate. That is precisely the number you stopped measuring when you shipped the 301.

Two consequences 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 (Deep dive 4 abuse which most answers skip), or a customer re-points a campaign, those clients never ask you again — and you have no way to reach them.

301 is therefore incompatible with takedown, which for a shortener is not optional. Expiry and destination rotation break in the same way, for exactly the population that clicked before.

Pick 302, and control caching explicitly with Cache-Control: no-store rather than relying on the status code’s default. The status code only sets a default; the header is the actual control, and a 301 with max-age=3600 is a real design point trading one hour of blindness for cache relief. 301 is right for a vanity-domain or domain-migration redirect, where nobody is paying for click data and permanence is the point. The question is whether analytics is the product or a nice-to-have — here it is the product, and a shortener that undercounts by 30% is selling a broken instrument.

10. Deep dive 4: abuse, which most answers skip

A large part of the design is the controls that stop your domain from becoming a phishing tool.

A shortener is an anonymizing redirector on a domain with reputation — precisely what a phisher wants. Your domain gets his malware URL past the corporate mail filter, and the recipient cannot see the destination before clicking.

The diagram below has two rows, and they are separate. The top row is what happens once, at create time. The bottom row is what happens at every read, forever after. Most designs draw only the top row; control 2 explains why that is a mistake.

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

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

    style REJ fill:#9d0208,color:#fff
    style INT fill:#bc6c25,color:#fff
    style OK fill:#2d6a4f,color:#fff

The colours here are verdicts, not roles — green created, orange shown an interstitial, red rejected — a different key from the one High level architecture uses for the same four hexes.

Follow the top row, which is create time. A POST /v1/urls first meets syntactic validation, which checks the URL’s scheme (the https: part), its host, and that it does not point back at your own service in a loop. It then checks the destination against the blocklist bloom filter; a hit means the domain is known-bad and the request is rejected with 422, while a miss falls through to the reputation verdict for that domain. If that verdict is cached and clean, fresh, the link is 201 created, status=active immediately. If it is unknown or stale, an async scan is queued and the link is created as active anyway, to be flagged later if the verdict comes back bad — a deliberate choice to keep creates fast, since holding a create for a scan would fail the write-availability target.

The bottom row is read time. Every GET /{key} asks whether the destination domain has been flagged since creation; if not it is a plain 302 to the destination, and if so the visitor gets a 200 interstitial that spells out the full destination URL and requires a second click.

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

The four controls

1. Screen at write time. Three checks before the row is written:

• Reject non-http(s) schemes outright. A javascript: or data: URL turns your redirect into a delivery service for stored cross-site scripting (XSS) — attacker-supplied code that runs in another user’s browser, under your domain, with your domain’s privileges.
• Reject your own domain, so a link cannot point at another link on your service and produce a redirect loop.
• Check the destination against a reputation service such as Google Safe Browsing.

There is a trap inside that third check, in your own scanner. The fetcher that renders the destination must refuse private and link-local addresses. Otherwise a user shortens http://169.254.169.254/ — the address cloud providers use to serve instance metadata, 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 on the attacker’s behalf, to somewhere the attacker cannot reach 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, get through screening, and then repoint the domain’s DNS record or swap the page content 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 remote procedure call (a request to another service over the network, usually 0.5 ms or more) 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 item in the set?” with either “definitely not” or “probably yes.”

The asymmetry is what makes it useful. It never misses a real member, so no bad domain slips through. In exchange it produces occasional false positives — clean domains it wrongly reports as possibly-bad — at a rate you choose by spending more bits per entry. Those you resolve against the real list, which is a network call, but only for the small fraction that trip the filter.

Price it at a 1% false-positive rate. The bits-per-entry formula for an optimally-sized bloom filter is -log2(p) / ln 2, so substitute p = 0.01:

bits per entry
  -log2(0.01)                           =  6.64
  6.64 / ln 2 = 6.64 / 0.693            =  9.59 bits

memory for 10 M bad domains, in MB
  10,000,000 x 9.59 bits                =  95,900,000 bits
  95,900,000 / 8                        =  11,987,500 B
  11,987,500 / 1,000,000                =  12 MB

false positives to resolve against the real list, at peak
  30,000 QPS x 0.01                     =  300 lookups/s

12 MB in every redirect process and 300 lookups/s of false-positive traffic is the whole cost of continuous re-checking, and it is the cheapest safety control in the system.

Compare it against the alternative it beat. A network call to a blocklist service on every redirect adds at least 0.5 ms to a 50 ms p99 budget, sends 30,000 requests per second to that service at peak, and — worst of all — makes a 99.99% read path depend on the availability of something else. The bloom filter is a memory reference with none of those properties.

3. An interstitial, not a hard block, for the suspicious band. Sort verdicts into three bands and treat each differently:

The interstitial costs a round trip and measurably kills conversion. That is exactly why it is reserved for the uncertain middle band rather than applied to everything — it is the response for “we do not know,” not the response for “this is bad.”

4. Rate limit creation, per API key and per source IP (chapter 04). Phishing campaigns need thousands of distinct links to outrun blocklists, because each link is burned once it is reported. So a per-account creation limit is not a cost control; it is the control that 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 being served by 200 MB of edge key-value data in every PoP and by every application node’s local LRU. Disabling the row changes nothing for any of them 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, it is the copy of your redirect sitting inside the user’s own browser, which you cannot purge at all.

11. Bottlenecks and scaling

Every limit the design runs into is collected below, with the number at which it binds and the move that relieves it, followed by the price of the one genuinely contended component.

Six limits. The middle column is the number at which each limit binds; the third is the move that buys headroom. Each was derived earlier in the chapter.

Pricing the allocator’s block size

The allocator is the only genuine single writer in the system, and its block size is a real trade with a cost on each side:

• Bigger blocks buy availability. Write nodes talk to the allocator less often, so they survive longer when it dies — they are still working through numbers they already hold.
• Bigger blocks burn keyspace. Every process that restarts abandons the unused remainder of its block. Those codes are gone forever, because the allocator never hands them out again.

Two fleet assumptions drive the table: 100 write nodes, and 1,000 process restarts a day across the fleet from deploys plus crashes, each abandoning half a block on average.

Both columns come from one-line formulas, so work the first row of each by hand:

runway = (write nodes x block size) / write rate
  (100 nodes x 1,000 codes) / 1,000 writes/s   =  100 seconds     at avg
  (100 nodes x 1,000 codes) / 3,000 writes/s   =   33 seconds     at peak

keyspace burned per day = (restarts x half a block) / codes used per day
  (1,000 restarts x 500 codes) / 100,000,000   =  0.005  =  0.5%

The runway column divides by the 1,000 writes/s average, not the 3,000/s peak (3a volume). If the allocator dies during the busy hour, the runway is a third of what a naive calculation shows, so read the third column, not the second.

Bigger blocks buy write availability with keyspace, and 3b how long is the code already told you the exchange rate: 9.65x headroom.

Check the middle row against that budget:

decade's consumption at 5% waste
  365,000,000,000 x 1.05                =  383,250,000,000
remaining headroom
  3,521,614,606,208 / 383,250,000,000   =  9.19x

So a block size of 10,000 costs you 9.65x headroom down to 9.19x — nothing you were going to spend — and buys 17 minutes to fix the allocator before creates start failing. Or 5.6 minutes if it dies at peak, which is the number to page on.

At 100,000 you burn half the keyspace every day to buy an afternoon of runway, which is the wrong side of the trade. At 1,000 you have 33 seconds at peak, which is not enough for a human to do anything. Take 10,000.

12. Failure modes

This section lists what breaks, with the signal that detects each failure and the mechanism that contains it.

In the Detection column, note that three rows fire the alarm on a component other than the one that failed, which is why they are missed in practice.

Two terms in that table deserve a definition. Request coalescing means that when many requests miss the cache on the same key at the same instant, only one of them is allowed to go to the database and the rest wait for its answer — without it, a cache eviction on a hot key produces thousands of simultaneous identical database reads. 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 detect that it is behind and refuse to reissue numbers.

13. Alternatives rejected

Each design below was seriously considered, was good at something, and was disqualified by a specific number.

Each entry gives Good: what the alternative wins at, then the number that ruled it out.

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 last insert of the decade has a one-in-ten collision probability and 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 product requirement, in which case pay the character.

Base-62 of a Snowflake ID from chapter 07. Good: no allocator, no coordination, no single writer. Rejected on density: Snowflake spends 22 bits on node and sequence, so after ten years the values reach 1.32e18 and the code is 11 characters instead of 7. The correct use of chapter 07 here is the internal primary key, not the public code — and if you use both, the dense counter is still what the code comes from.

A raw auto-increment as the public code. Good: shortest possible codes, trivially dense. Rejected because it is fully enumerable at one request per link and leaks daily volume by subtraction. The permutation in 7c the fix permute the counter do not randomize it 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 (identical fill ratio, identical birthday bound) with none of its dedupe benefit, and it needs a uniqueness check on every write forever. A permutation is a random-looking code with a proof of no collisions; randomness is the same code with a retry loop.

301 Moved Permanently. Good: 30% fewer requests, faster repeat clicks, cheaper edge. Rejected because the clicks it hides are exactly the repeat clicks, so the undercount cannot be corrected, and because a cached 301 makes takedown impossible — see Deep dive 3 301 vs 302 is an analytics decision and Deep dive 4 abuse which most answers skip. 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. A buffer pool is the slice of memory a database keeps recently-used pages in. 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 the buffer pool, so most reads become random reads off a solid-state disk at 100 microseconds each (chapter 02), and you need roughly one device’s full IOPS budget — its ceiling on input/output operations per second — per 10,000 QPS before replication. The relational features are used by custom aliases only, which are a rounding error of the traffic.

Synchronous click counting in the redirect path. Good: exact counts, no pipeline. Rejected because it converts a 100%-read path into a read-plus-write path at 10,000 writes/s onto the hottest rows in the system, and because it makes the redirect’s availability depend on the analytics store’s. Fire-and-forget onto a queue; analytics is allowed to be eventually consistent and a redirect is not allowed to be slow.

14. Interviewer pushback

The same material as answers to likely questions, with the point each question tests named up front.

“Why seven characters?” Testing: whether the length was derived or remembered. From the ten-year volume backwards. At 100 million links a day, ten years is 365 billion codes. 62^6 is 56.8 billion, which is 568 days of traffic, so six characters exhausts in a year and a half. 62^7 is 3.52 trillion, which is 96.5 years, or 9.65x the requirement. Seven it is, and the headroom is not spare — I spend some of it on allocator waste and I rely on the resulting 10.4% fill ratio being low enough that guessing costs about ten requests per hit. At 10x the volume the ten-year need is 3.65 trillion against a 3.52 trillion space, so it does not fit at all, and that is exactly where I would move to eight.

“Why not base 64? It is the standard encoding.” Testing: whether you have looked at the character set. Because it does not shorten anything and it breaks URLs. 64^7 is 4.4 trillion against 62^7 at 3.5 trillion, so both are seven characters for this volume; the extra two symbols are worth 64 / 62 - 1 = 3.2% more capacity per character, and that never crosses a boundary — 365 billion links needs 6.45 base-62 characters and 6.40 base-64 ones, and both round up to seven. And standard base 64 uses + and /, where / is the path separator and + decodes as a space in a query string, so I would have to use base64url with - and _ — and _ disappears under underlining in mail clients. The alphabet change I would actually consider is base 58, dropping the four glyphs that get misread; it is still seven characters with 6x headroom. Base 36 for case-insensitivity costs a full character, 36^7 being 78 billion, and that is a product call, not an engineering one.

“You use a counter. Can I guess other people’s links?” Testing: whether you know the difference between obscure and secret. With a raw counter, yes, trivially: I walk 0, 1, 2 and get every link in creation order at one request each, plus the daily creation volume by subtraction. So I do not expose the counter — I expose a keyed Feistel permutation of it, which is a bijection, so there are still zero collisions and no uniqueness check, and consecutive counters map to unrelated codes. That fixes ordering and volume. It does not make links private, and I would say so to the product team: at 365 billion links in a 3.5 trillion space the table is 10.4% full, so a random guess hits a live link about once every ten tries. The controls that actually matter are rate limiting GET by IP with attention to the 404 rate, and an authorization check on anything genuinely confidential. A short code is obscurity with a price tag, and I can quote the price.

“Walk me through the collision math for the hash approach.” Testing: whether “collisions are rare” is a real claim. At seven base-62 characters the space is 3.52 trillion. The chance of at least one collision passes 50% at about 1.177 * sqrt(M), which is 2.2 million inserts — 32 minutes at 100 million a day. Over the decade, expected collisions are n^2 / 2M with n at 365 billion, which is 18.9 billion. Per insert that averages 5.2% and reaches 10.4% on the last one. So collisions are the common case, not the edge case, and the retry path must be tested. To get the collision rate down to one in 599 I would need eight characters. That is why I prefer the counter: it uses the same space with no collisions and no read-before-write, and it costs me one coordinated allocation per second instead.

“301 or 302?” Testing: whether you know what the status code actually changes. 302, with Cache-Control: no-store, unless the product tells me analytics does not matter. 301 is cacheable by default, so a browser that has resolved a link never asks again. If 30% of clicks are repeats, that is 30% off my read fleet and 30% off my click counts — and the missing 30% is precisely the engaged users and the popular links, so the bias correlates with the thing being measured and I cannot calibrate it out. There are two harder problems than the counting. A cached 301 cannot be revoked, so when a link turns out to be malware I have no way to stop those browsers, and takedown is a requirement for a shortener. And expiry and destination editing stop working for anyone who already clicked. I would use 301 for a domain migration, where permanence is the goal and nobody is buying the click data.

“Your cache dies. What happens?” Testing: whether you sized for the failure or the steady state. At a 96% hit rate the database is doing 376 QPS and takes 10,000 the instant the cache goes, which is 26x — that is the 1/(1-h) reciprocal, and it is why a cache failure is a step function rather than a degradation. Three guards. Each application node keeps a small in-process LRU, so even a total shared-cache loss still absorbs the head of the Zipf distribution. Misses coalesce per key so a hot key produces one database read rather than 6,000. And I provision the database for a survivable multiple rather than for 376 QPS, because a store sized exactly for the cached load has effectively made the cache a hard dependency of a 99.99% read path. If the interviewer wants the number, this is a workload of pure point lookups, so a hash-partitioned store at RF 3 across 20 boxes handles 10,000 QPS without a cache at all; the cache is there for latency and cost.

“Someone reports that a link on your service is serving malware. What did you get wrong?” Testing: whether the design has a read-time control. Probably nothing at creation time — the standard attack is to shorten a clean page and repoint it a week later, so a write-time reputation check has a one-shot view of a destination that gets clicked for years. The read path therefore needs its own control, and it has to be a memory lookup because 30,000 QPS cannot afford a network call per redirect. A bloom filter of 10 million blocked domains at 1% false positives is about 12 MB per process, and the 1% resolves against the real list at 300 lookups a second at peak. Verdicts land in three bands: clean redirects, suspicious gets a full-page interstitial showing the destination, malicious returns 410. Then the part that actually goes wrong in the incident review: the purge has to reach the edge key-value tier and every node’s local cache, not just the primary store, which is the second reason I will not ship a 301.

Cheat sheet

Every result in the chapter, one line each, in the order you would use them at a whiteboard.

Related: 07 — Unique ID Generator supplies the counter and explains why a Snowflake ID is sparse; 04 — Rate Limiter is the control that makes bulk phishing uneconomic; 05 — Consistent Hashing is how the 219 TB is partitioned.