URL Shortening Service

Six courses built a design language piece by piece. This course’s job is not to teach new mechanics; it is to use the established patterns together, on a single problem and defend each choice with a reason. Every case walks the same six steps: constraints turn into numbers, assumptions collect in their own table, a back-of-the-envelope estimate follows from that table, the design assembles from patterns by name, at least one alternative is eliminated with a number, and the design’s behavior under failure and what it gives up are written down.

The first case is the URL shortening service: given a long link, it generates a short key, and requesting that key redirects to the original target. The design looks at a single decision — how the short key is generated — and this lesson measures that decision.

Constraints

Functional requirements. F1: a short key is generated and returned for a long link. F2: requesting the short key redirects to the target. F3: a link has an expiration time; an expired link does not redirect. F4: the owner deletes the link. F5: a short key is never assigned to two different targets.

Scope reduction. Click counting, requests for a custom key, malware scanning of the target link, and account management are outside this design; each brings its own write path and does not move the decisions below.

Non-functional requirements. The threshold’s source is written, not its class; the format follows the Introduction to System Design course’s Functional and Non-Functional Requirements lesson.

Code	Threshold	Threshold’s source
G1	the median redirect response does not exceed 50 ms	the redirect is an extra round trip inserted between the click and the destination page
G2	the shortening call does not exceed 300 ms	the result is awaited on screen
G3	the redirect path’s service availability is 99.95 percent	the shortened link is embedded in written text and cannot be taken back
G4	the hit probability of a random key guess is below 1/1000	the link is not secret, but it should not be listable either

Assumptions

This table is this lesson’s alone; later cases build their own and do not inherit numbers from it.

Code	Assumption	Value	Rationale
BK1	shortenings created per day	500,000	shortening depends on a sharing action, it is infrequent
BK2	daily redirects per shortening	100	a link is opened many times on the day it is shared
BK3	peak factor	3	the ratio of the peak-hour rate to the daily average
BK4	link record	500 bytes	target link, owner, creation and expiration time
BK5	retention period	1825 days	an unrenewed link drops after five years
BK6	the key share receiving 0.80 of requests	0.01	access concentrates in a small number of new links
BK7	alphabet size	62	digits and both letter cases; no separators, can be typed by hand
BK8	cache record	300 bytes	key and target link
BK9	redirect response	300 bytes	bodiless response and its headers

Back-of-the-Envelope Estimate

// shortening/estimate.mjs — the back-of-the-envelope estimate from BK1-BK9 and the key-length scan
const BK = {
  dailyShortenings: 500_000,   // BK1
  redirectsPerShortening: 100,     // BK2
  peakFactor: 3,            // BK3
  recordBytes: 500,            // BK4
  retentionDays: 1825,            // BK5
  hotShare: 0.01,      // BK6: the key share receiving 0.80 of requests
  hotRequestShare: 0.80,      // BK6
  alphabet: 62,                // BK7
  cacheRecordBytes: 300,            // BK8
  responseBytes: 300,            // BK9
};
const DAY = 86_400, MONTH_MIN = 43_800, TARGET = 0.9995;   // TARGET: G3 threshold, not an assumption

function compute(v) {
  const readPeak = ((v.dailyShortenings * v.redirectsPerShortening) / DAY) * v.peakFactor;
  const total = v.dailyShortenings * v.retentionDays;
  return {
    total,
    readPeak,
    writePeak: (v.dailyShortenings / DAY) * v.peakFactor,
    storeReads: readPeak * (1 - v.hotRequestShare),
    egressMbit: (readPeak * v.responseBytes * 8) / 1e6,
    storeGB: (total * v.recordBytes) / 1e9,
    cacheGB: (total * v.hotShare * v.cacheRecordBytes) / 1e9,
  };
}

const f = (x, n = 2) => x.toFixed(n);
const r = compute(BK);
console.log(`total links in the retention window = ${r.total.toLocaleString("en-US")}`);
console.log(`peak redirects/s = ${f(r.readPeak)}   peak shortenings/s = ${f(r.writePeak)}   ratio = ${f(r.readPeak / r.writePeak)}`);
console.log(`redirects/s behind the cache = ${f(r.storeReads)}   egress = ${f(r.egressMbit)} Mbit/s`);
console.log(`store = ${f(r.storeGB)} GB   cache = ${f(r.cacheGB)} GB   G3 downtime budget = ${f((1 - TARGET) * MONTH_MIN, 1)} min/month`);

console.log(`\n${"length".padEnd(9)}${"key space".padStart(19)}${"occupancy".padStart(11)}` +
  `${"extra tries/record".padStart(20)}${"extra hits/s at peak".padStart(24)}${"guesses per hit".padStart(22)}`);
const extraTries = {};
for (const L of [5, 6, 7, 8]) {
  const space = BK.alphabet ** L, d = r.total / space;
  // Retry expectation: with k keys already assigned, one attempt's miss probability is k/space.
  let extra = 0;
  for (let k = 0; k < r.total; k += r.total / 1e5) extra += (1 / (1 - k / space) - 1) / 1e5;
  extraTries[L] = extra;
  console.log(`${String(L).padEnd(9)}${space.toLocaleString("en-US").padStart(19)}${f(d, 6).padStart(11)}` +
    `${f(extra, 6).padStart(20)}${f(extra * r.writePeak, 4).padStart(24)}${f(1 / d, 1).padStart(22)}`);
}

const SHARD = 8, dropped = r.readPeak / SHARD * (1 - BK.hotRequestShare);
console.log(`\nsingle shard failure (${SHARD} shards): dropped redirects ${f(dropped)}/s = ` +
  `${f(dropped / r.readPeak, 4)} of requests, rejected shortenings ${f(r.writePeak / SHARD)}/s`);
console.log(`G3 budget against a single shard failure = ${f((1 - TARGET) * MONTH_MIN / (dropped / r.readPeak), 1)} min/month`);

const doubled = compute({ ...BK, dailyShortenings: BK.dailyShortenings * 2 });
console.log(`\nBK1 sensitivity: daily shortenings 500,000 -> 1,000,000 makes store ${f(r.storeGB)} -> ${f(doubled.storeGB)} GB, ` +
  `occupancy at 7 characters ${f(r.total / BK.alphabet ** 7, 6)} -> ${f(doubled.total / BK.alphabet ** 7, 6)}, ` +
  `guesses per hit ${f(BK.alphabet ** 7 / r.total, 1)} -> ${f(BK.alphabet ** 7 / doubled.total, 1)}`);

total links in the retention window = 912,500,000
peak redirects/s = 1736.11   peak shortenings/s = 17.36   ratio = 100.00
redirects/s behind the cache = 347.22   egress = 4.17 Mbit/s
store = 456.25 GB   cache = 2.74 GB   G3 downtime budget = 21.9 min/month

length             key space  occupancy  extra tries/record    extra hits/s at peak       guesses per hit
5                916,132,832   0.996035            4.550910                 79.0089                   1.0
6             56,800,235,584   0.016065            0.008120                  0.1410                  62.2
7          3,521,614,606,208   0.000259            0.000130                  0.0022                3859.3
8        218,340,105,584,896   0.000004            0.000002                  0.0000              239276.8

single shard failure (8 shards): dropped redirects 43.40/s = 0.0250 of requests, rejected shortenings 2.17/s
G3 budget against a single shard failure = 876.0 min/month

BK1 sensitivity: daily shortenings 500,000 -> 1,000,000 makes store 456.25 -> 912.50 GB, occupancy at 7 characters 0.000259 -> 0.000518, guesses per hit 3859.3 -> 1929.7

These numbers are in the estimate class, and four of them determine the design. The peak ratio is exactly 100: 1736.11 redirects per second against 17.36 shortenings. The retention window holds 912,500,000 links and 456.25 GB — more than a single node can carry. Behind the cache, 347.22 requests/s remain, and the entire hot set is 2.74 GB — it fits in memory. The most decisive is the key-length table: five characters is full for this volume (occupancy 0.996035), six characters does not satisfy G4 (62.2 guesses per hit, threshold 1000), seven characters satisfies both (3859.3 guesses, 0.000130 extra tries per record). Even if BK1 doubles, seven characters still leaves 1929.7 guesses per hit, and the threshold holds.

The Collision Rate of Key Generation

The extra tries/record column in the table is an expectation. This section measures whether random generation behaves this way, whether the collision rate depends only on the occupancy rate, and where the difference from a counter arises.

// shortening/key.mjs — collision rate of key generation: how random generation depends on
// occupancy, and a comparison with counter-based generation. The key space is modeled as an
// array of slots, the generator is hand-written, the seed is fixed; the numbers are not
// machine-dependent. IT IS A MODEL.
const SEED = 20260730;
const generator = (t) => { let s = t % 2147483647; return () => (s = (s * 48271) % 2147483647) / 2147483647; };

function fillRandomly(m, n, rand) {           // on a collision, a new key is drawn
  const full = new Uint8Array(m);
  let tries = 0;
  for (let i = 0; i < n; i += 1) {
    let y;
    do { y = Math.floor(rand() * m); tries += 1; } while (full[y]);
    full[y] = 1;
  }
  return { full, extra: tries - n };
}

function expectedExtra(m, n) {                  // with k slots full, one attempt's miss probability is k/m
  let t = 0;
  for (let k = 0; k < n; k += 1) t += 1 / (1 - k / m) - 1;
  return t;
}

const M = 2_000_000, OCCUPANCY = [0.016065, 0.1, 0.5, 0.9, 0.996035];
const f = (x, n = 6) => x.toFixed(n);
const c = (x) => x.toLocaleString("en-US");
console.log(`model: a ${c(M)}-slot key space, seed ${SEED}, hand-written generator`);
console.log(`\n${"occupancy".padEnd(10)}${"added".padStart(10)}${"extra tries".padStart(14)}` +
  `${"measured/record".padStart(17)}${"expected/record".padStart(17)}${"measured/expected".padStart(19)}`);
for (const d of OCCUPANCY) {
  const n = Math.round(d * M);
  const { extra } = fillRandomly(M, n, generator(SEED));
  const exp = expectedExtra(M, n);
  console.log(`${f(d).padEnd(10)}${c(n).padStart(10)}${c(extra).padStart(14)}` +
    `${f(extra / n).padStart(17)}${f(exp / n).padStart(17)}${f(extra / exp, 4).padStart(19)}`);
}

// Scale check: the collision rate depends on occupancy, not the size of the space.
console.log("");
for (const m of [250_000, 2_000_000, 8_000_000]) {
  const n = m / 2;
  const { extra } = fillRandomly(m, n, generator(SEED));
  console.log(`scale check: space ${c(m).padStart(9)}, occupancy 0.500000 -> extra tries/record ${f(extra / n)}`);
}

// Two generation modes at the same occupancy: the counter never collides, but its keys are adjacent.
const GUESSES = 20_000, BLOCK = 1000, d6 = 0.016065, n6 = Math.round(d6 * M);
const random = fillRandomly(M, n6, generator(SEED));
const counterFull = new Uint8Array(M);
for (let i = 0; i < n6; i += 1) counterFull[i] = 1;                // the counter distributes upward from 0
const guesser = generator(SEED + 1);
let randomHits = 0, counterHits = 0;
for (let g = 0; g < GUESSES; g += 1) {
  if (random.full[Math.floor(guesser() * M)]) randomHits += 1; // a random guess against random keys
  if (counterFull[g]) counterHits += 1;                             // a sequential guess against counter keys
}
const row = (name, extra, coord, hits) => console.log(`${name.padEnd(18)}${c(extra).padStart(14)}` +
  `${coord.padStart(21)}${c(hits).padStart(12)}${(GUESSES / hits).toFixed(1).padStart(22)}`);
console.log(`\noccupancy ${f(d6)}, ${c(n6)} keys assigned, ${c(GUESSES)} guesses`);
console.log(`${"generation mode".padEnd(18)}${"extra tries".padStart(14)}${"coordination calls".padStart(21)}` +
  `${"hits".padStart(12)}${"guesses per hit".padStart(22)}`);
row("random", random.extra, "0", randomHits);
row(`counter (block ${BLOCK})`, 0, (n6 / BLOCK).toFixed(1), counterHits);

model: a 2,000,000-slot key space, seed 20260730, hand-written generator

occupancy      added   extra tries  measured/record  expected/record  measured/expected
0.016065      32,130           256         0.007968         0.008119             0.9813
0.100000     200,000        10,771         0.053855         0.053605             1.0047
0.500000   1,000,000       385,317         0.385317         0.386294             0.9975
0.900000   1,800,000     2,802,181         1.556767         1.558425             0.9989
0.996035   1,992,070     9,053,122         4.544580         4.552201             0.9983

scale check: space   250,000, occupancy 0.500000 -> extra tries/record 0.386128
scale check: space 2,000,000, occupancy 0.500000 -> extra tries/record 0.385317
scale check: space 8,000,000, occupancy 0.500000 -> extra tries/record 0.384476

occupancy 0.016065, 32,130 keys assigned, 20,000 guesses
generation mode      extra tries   coordination calls        hits       guesses per hit
random                       256                    0         344                  58.1
counter (block 1000)             0                 32.1      20,000                   1.0

The measurement gives three things. The ratio of measured to expected sits between 0.98 and 1.01 at every occupancy; the closed form represents random generation faithfully, and the 0.000130 in the table is reliable. The scale check shows the collision rate depends on occupancy, not on the size of the space: when the space grows thirty-two-fold, the ratio moves from 0.386128 to 0.384476, landing on the same third digit — which is why a two-million-slot model can speak for a 3.5-trillion space. Third, the ratio is not linear in occupancy: at 0.10 there are 0.05 extra tries per record, while at 0.996035 there are 4.54.

The last table places the two generation modes side by side. The counter never collides; its cost has two line items. The first is coordination: the counter is handed out from one place, and in blocks of a thousand keys it makes 32.1 calls for 32,130 keys — 0.017 calls per second at peak, negligible. The second is predictability, and it is not negligible: a client guessing sequentially hits on 20,000 of 20,000 tries, against 344 of 20,000 for random.

Design

No component is re-explained; each one is tied back to the lesson that established it, and this case’s parameter for it is written down.

• Edge caching (Traffic Layer, Content Delivery Networks). The parameter is the redirect response’s lifetime at the edge: 300 seconds. This is the staleness window from the Scaling the Data Layer course’s Consistency and Stale Data lesson, meaning F3 and F4 take effect at the edge with a delay.
• The redirect service is stateless (Application Layer, Stateless Services); since the state carried per request is zero, session stickiness (Traffic Layer, Session Stickiness) is off.
• Key–value store (Scaling the Data Layer, Store Types), sharded (Data Distribution, Sharding) into eight shards. The shard key is the short key itself: both redirect and delete already know it, both access patterns touch a single node, and no scatter–gather occurs.
• Cache-aside (Scaling the Data Layer, Cache-Aside). The parameter comes from BK6: the 2.74 GB hot set serves 0.80 of requests, leaving 347.22 requests/s behind it.
• API gateway and rate limiting (Traffic Layer, API Gateway), on the shortening path only. The parameter is 20 shortenings per minute per account: peak writes run at 17.36/s, and no single client should be able to fill it.
• Eventual consistency (Introduction to System Design, Consistency Models). Propagating a new key to the replicas takes time; the parameter is that the first redirect immediately after shortening goes to the primary replica, so the creator can open their own link.

Two deliberately unused patterns. Command and query responsibility separation (Scaling the Data Layer, Command and Query Separation) is not used: the read model is the same as the write model, there is no projection to derive. A message queue (Application Layer, Message Queues) is not used on the shortening path: the caller waits for the key inside the response.

Eliminated Alternative: Counter-Based Generation

The alternative design does not draw the key at random; it generates it by converting an incrementing counter to base 62. Collision is zero by definition, F5 is guaranteed arithmetically, and the store’s existence check never runs.

The number that eliminates it is in G4. Because counter keys are contiguous, a client guessing sequentially hits on every try (20,000/20,000 in the measurement, 1.0 guesses per hit); random generation at seven characters needs 3859.3 guesses per hit. The difference is 3859-fold, and the threshold is 1000; the counter cannot satisfy this at any key length, because the problem is not the size of the space but contiguity. What it wins was measured, and small — at seven characters, the extra store touches random generation adds at peak is 0.0022/s, less than one ten-thousandth of the 17.36 writes.

The alternative wins if a different constraint changes: had the key length been fixed at five characters, occupancy would be 0.996035, and random generation would produce 4.55 extra tries per record and 79.01 extra store touches per second at peak — four and a half times the write load. In that case the counter would be the only working mode, and G4 could not be satisfied by any mode at all.

Failure Behavior and What Is Given Up

If a store shard drops (Resilience and Reliability, Failure Modes), that shard’s keys are served only from the cache: 0.0250 of redirects, 43.40 requests/s, are dropped, and 2.17 shortenings/s are rejected. G3’s monthly 21.9-minute downtime budget, measured against this partial failure, corresponds to 876.0 minutes of a single-shard outage.

If the store drops entirely, redirects continue from the cache through graceful degradation (Resilience and Reliability, Graceful Degradation), and 0.80 of requests are answered; the shortening path is closed, because returning an unwritten key would break F5.

What is given up is freshness. A deleted or expired link keeps working for the 300-second window at the edge. The design bought this window deliberately: in exchange, most redirects never reach the origin at all.

Summary

• The constraints reduced to five functional requirements and four thresholds; four out-of-scope items were written down, and each threshold carries a source, not a class.
• The estimate from nine assumptions gave a peak ratio of 100 (1736.11 redirects/s, 17.36 shortenings/s), and set the retention window at 456.25 GB and the hot set at 2.74 GB.
• Key length was set by two thresholds at once: five characters is full (0.996035), six characters does not satisfy G4 (62.2 guesses), seven characters satisfies both (0.000130 extra tries, 3859.3 guesses).
• The collision rate depends on occupancy, not the size of the space: at 0.50 occupancy, three different spaces gave 0.386128 / 0.385317 / 0.384476, and measured/expected fell between 0.98 and 1.01 on every row.
• Counter-based generation zeroes out collisions but leaves 1.0 guesses per hit under sequential guessing; what it wins is 0.0022 store touches per second at peak, so it was eliminated.
• A single-shard failure drops 0.0250 of requests; G3’s 21.9-minute budget corresponds to 876.0 minutes of a shard outage; what is given up is the edge’s 300-second staleness window.

Next Step

In this case, reads outnumbered writes a hundred to one, and the read’s response was a single record: give the key, get back the target. The caching decision therefore stayed simple, and no merging happened on the redirect path. In the next case, the read ratio stays similar but the response changes: instead of a single record, an ordered list compiled from many sources is requested. The question then stops being “where do I cache the record” and becomes: when is the list compiled — fanned out to everyone’s box the moment it is written, or gathered at read time? The two options’ work volume differs sharply for the same stream, and the difference is set not per user but by the tail of the follower distribution.