System design at scale

01 · ONE SERVER

One server, and why it falls over suddenly

Start with the simplest design that works: one computer runs your program and its database. A user's phone sends a request over the internet, the server does some work, reads or writes the database, and sends a response. For a new product this is the right design: cheap, easy to understand, easy to debug.

Push the slider up. Nothing much happens, and nothing much happens, and then everything happens at once. That is not a quirk of the model; it is how queues work. Requests arrive at random, so sometimes three arrive together and two have to wait. The busier the server, the less slack it has to catch up, and waiting time grows like 1 / (1 − utilisation).

// One server. Requests arrive at random, lambda per second;
// the server can finish mu per second. Queueing theory
// (the M/M/1 queue) says how long each request spends inside.
const mu = 600;                       // what the box can do, requests/s
​
function report(lambda) {
  const rho = lambda / mu;            // utilisation: the share of time it's busy
  if (rho >= 1) {
    console.log(lambda, "req/s: overloaded, the queue grows without end");
    return;
  }
  const meanMs = 1000 / (mu - lambda);   // average time in the system
  const p99Ms = meanMs * Math.log(100);  // response time is exponential
  console.log(lambda + " req/s", "busy " + Math.round(rho * 100) + "%",
    "mean " + meanMs.toFixed(1) + " ms", "p99 " + p99Ms.toFixed(1) + " ms");
}
​
for (const lambda of [100, 300, 450, 540, 580, 594, 600]) report(lambda);

p99 means the 99th percentile: 99 requests in 100 are faster than this, 1 is slower. It is the number engineers watch, because the average hides the unlucky users.

02 · LATENCY NUMBERS

Latency numbers: what is fast, what is far

Before you can design for speed you need a feel for how long things take. The ladder in the 3D is on a log scale: each line is ten times the one below. Reading a value from the CPU's L1 cache takes about half a nanosecond; a packet from California to the Netherlands and back takes about 150 milliseconds. That is three hundred million times longer.

// Jeff Dean's "numbers everyone should know" (2009), with the SSD
// figure from Colin Scott's 2020 update. Orders of magnitude, not specs.
const ns = {
  "L1 cache reference": 0.5,
  "main memory reference": 100,
  "SSD random read": 16000,
  "round trip inside one datacentre": 500000,
  "disk seek": 10000000,
  "packet California-Netherlands-California": 150000000,
};
​
// Stretch time so 1 nanosecond lasts 1 second.
function human(s) {
  const units = [["years", 31557600], ["days", 86400], ["hours", 3600], ["minutes", 60], ["seconds", 1]];
  for (const [name, size] of units) if (s >= size) return (s / size).toFixed(1) + " " + name;
  return s + " seconds";
}
​
for (const [what, n] of Object.entries(ns)) {
  console.log(what.padEnd(42), String(n).padStart(10), "ns  =", human(n));
}

Three rules fall out of this table. Memory beats disk, so keep hot data in RAM (that is what a cache is). A network hop inside a datacentre costs about as much as thousands of memory reads, so avoid chatty designs that make many small calls. And distance is physics: light in glass fibre travels at about two thirds of its speed in a vacuum, so nothing you build will get a London user to a New York server and back in under about 55 ms.

// Physics sets a floor no engineering can lower.
const c = 299792;                // km/s in a vacuum
const fibre = c / 1.47;          // glass slows light by its refractive index
const londonToNewYork = 5570;    // km, great-circle distance
​
const oneWayMs = londonToNewYork / fibre * 1000;
console.log("one way, at least", oneWayMs.toFixed(1), "ms");
console.log("round trip, at least", (2 * oneWayMs).toFixed(1), "ms");
console.log("a page needing 5 sequential round trips:", (10 * oneWayMs).toFixed(0), "ms");

The real figures drift (spinning disks gave way to SSDs, networks got faster), so learn the orders of magnitude, not the digits. For what a memory reference actually is, see Memory; for the buildings these round trips happen in, see the Datacentre.

03 · UP OR OUT

Scale up, or scale out

When one server is too slow you have two moves. Vertical scaling (scaling up) means a bigger machine: more cores, more RAM. It needs no code changes, which is why it is the right first move. But big machines cost more per unit of work, there is a largest machine you can buy, and one machine is still one point of failure.

Horizontal scaling (scaling out) means more machines running the same program. It has no ceiling, and losing one machine is survivable. It has one requirement: the app servers must be stateless. If a user's login session lives in one server's memory, their next request must reach that same server. Move session state into a shared store (a database or a cache) and any server can answer any request.

Drag the slider and watch the box grow (2×, 4×) and then multiply. Notice what breaks next: around 3,400 requests a second it is not the app servers but the database, which is still one machine. This is the pattern of the whole chapter. You never remove the bottleneck; you move it.

// How many app servers for the busiest minute of the day?
const peakRps = 12000;      // measured or estimated
const perServer = 1000;     // from a load test of ONE server
const target = 0.7;         // stay below 70% busy: latency climbs fast above it
​
const needed = Math.ceil(peakRps / (perServer * target));
const total = needed + 2;   // N+2: survive one failure during a deploy
​
console.log("needed at peak:", needed);
console.log("to run, with spares:", total);
console.log("busy at peak with all up:", Math.round(peakRps / (total * perServer) * 100) + "%");

04 · LOAD BALANCER

The load balancer

With several app servers, something has to decide which one gets each request. That is a load balancer: one address the world talks to, which forwards each request to a healthy server behind it. It can work at the transport level (layer 4: it sees TCP connections) or at the HTTP level (layer 7: it can route by URL, add headers and end TLS).

It also does health checks: every few seconds it asks each server "are you OK?", and stops sending traffic to one that doesn't answer. Kill a server below and watch the wires: the balancer routes around it, and the others get hotter.

How it chooses matters. Random is simple but uneven. Round robin takes turns. Least connections asks every server how busy it is, which is costly with many balancers. A beautiful trick sits in between: pick two servers at random and send to the less busy one.

// 100 servers, 20,000 requests of uneven cost (1 to 10 units).
// Which way of choosing a server spreads the work most evenly?
let seed = 42;
const rand = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
const N = 100, M = 20000;
const costs = Array.from({ length: M }, () => 1 + Math.floor(rand() * 10));
​
function run(choose) {
  const load = new Array(N).fill(0);
  costs.forEach((c, i) => { load[choose(load, i)] += c; });
  const avg = load.reduce((a, b) => a + b) / N;
  return "busiest server is " + (Math.max(...load) / avg * 100 - 100).toFixed(1) + "% above average";
}
​
console.log("random:        ", run(() => Math.floor(rand() * N)));
console.log("round robin:   ", run((load, i) => i % N));
console.log("two choices:   ", run((load) => {
  const a = Math.floor(rand() * N), b = Math.floor(rand() * N);
  return load[a] <= load[b] ? a : b;     // ask two, pick the less busy
}));

The load balancer is itself a single point of failure, so in practice it runs as a pair (or a fleet) sharing an address. To see a rack of real machines behind a balancer, open the Cluster.

05 · CACHES

Caches: CDN, app cache, and invalidation

The fastest request is one that never reaches you. A cache keeps a copy of an answer close to whoever needs it, so the slow path runs once instead of every time. Two caches appear in the 3D:

A CDN (content delivery network) is a set of servers in hundreds of cities. Images, scripts and any page that is the same for everyone are served from the one nearest the user, and never touch your servers. HTTP itself says what may be cached and for how long, with headers like Cache-Control: max-age=3600. An app cache (Redis or Memcached) sits beside the app servers and holds hot database results in RAM.

With half the traffic answered at the edge and 90% of the rest from the cache, the database sees a fraction of the reads, and the first break jumps from about 3,400 to about 22,000 requests a second. Look at what breaks now: writes. Caches only help reads.

// Cache-aside: look in the cache; on a miss, read the database
// and remember the answer for a while (its time to live, TTL).
const db = new Map([["user:1", "Ada"]]);
const cache = new Map();             // key -> { value, expires }
let now = 0, hits = 0, misses = 0;
​
function get(key) {
  const e = cache.get(key);
  if (e && e.expires > now) { hits++; return e.value; }
  misses++;
  const value = db.get(key);         // the slow trip
  cache.set(key, { value, expires: now + 60 });
  return value;
}
​
function renameWrong(key, value) { db.set(key, value); }
function renameRight(key, value) { db.set(key, value); cache.delete(key); }
​
get("user:1"); get("user:1");
renameWrong("user:1", "Ada Lovelace");
now = 10;
console.log("after renameWrong:", get("user:1"), "(stale for up to 60 s)");
renameRight("user:1", "Countess Lovelace");
console.log("after renameRight:", get("user:1"));
console.log("hits", hits, "misses", misses);

That bug is the hard part. Invalidation is deciding when a cached copy is no longer true. The usual tools: a TTL (every entry expires, so staleness is bounded), delete on write (the code that changes the database deletes the cache key), and versioned keys (user:1:v7). Watch for the thundering herd: a popular key expires and a thousand requests miss at once and all hit the database. Facebook's answer was to give one request a lease to refill it while the rest wait or take the stale copy.

06 · READ REPLICAS

Replication and read replicas

Replication keeps a copy of the same data on several machines. The common form is leader-follower: one primary takes all writes and streams a log of changes to replicas, which apply them in the same order. Reads can go to any replica. If the primary dies, a replica is promoted.

Add replicas below and look at the first break: it barely moves, from about 22,000 to 27,000. Every replica must apply every write, so replicas multiply read capacity and do nothing for write capacity. The database is still bound by one primary's writes.

Replication is usually asynchronous: the primary says "saved" before the replicas have the change. That is fast, but it means a replica can be behind. That gap is replication lag, normally milliseconds, sometimes seconds or minutes under load.

// A primary ships its changes to a replica asynchronously.
// The replica applies each change LAG ticks later.
const LAG = 3;
const primary = new Map(), replica = new Map();
const inFlight = [];
​
function write(t, key, value) {
  primary.set(key, value);
  inFlight.push({ key, value, at: t + LAG });
}
function tick(t) {
  while (inFlight.length && inFlight[0].at <= t) {
    const e = inFlight.shift();
    replica.set(e.key, e.value);
  }
}
​
write(0, "bio", "old"); tick(5);
write(10, "bio", "new");             // the user saves their profile...
for (let t = 10; t <= 14; t++) {
  tick(t);
  console.log("t=" + t, "primary:", primary.get("bio"), " replica:", replica.get("bio"));
}
// ...and reloads at t=11 from a replica: their edit seems lost.

Kleppmann names the guarantees you may want: read-your-writes (you always see your own changes), monotonic reads (you never see time go backwards by hitting a staler replica next), and consistent prefix (you never see an answer before its question). Each one is a promise that has to be engineered, not a default.

07 · SHARDING

Sharding: splitting the data

To scale writes, split the data itself. Sharding (or partitioning) gives each database server a slice of the keys: users 0 to 1 million on shard 1, the next million on shard 2, and so on, or a hash of the key decides. Now each shard takes a quarter of the writes, and each can have its own replicas. In the 3D the sparks take the colour of the shard their key belongs to.

The first break jumps to about 100,000 requests a second. The price is real, though. A query that needs data from every shard ("top 10 posts overall") must ask all of them. A transaction across two shards needs a protocol like two-phase commit. And one celebrity key can make one shard a hot spot while the others idle.

The biggest cost comes when you add a shard. With hash(key) % N, changing N moves nearly every key. Consistent hashing places shards and keys on a ring, and a key belongs to the next shard clockwise; adding a shard only takes keys from its neighbours.

// Spread 100,000 keys over 4 shards, then add a 5th.
// How many keys have to move?
function fnv1a(s) {                  // a small, well-mixed string hash
  let h = 2166136261;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 16777619); }
  return h >>> 0;
}
const keys = Array.from({ length: 100000 }, (_, i) => "user:" + i);
​
// 1) hash mod N
const modN = (k, n) => fnv1a(k) % n;
let moved = keys.filter((k) => modN(k, 4) !== modN(k, 5)).length;
console.log("mod N:              ", (moved / 1000).toFixed(1) + "% moved");
​
// 2) consistent hashing: shards own arcs of a ring (100 points each)
function ring(n) {
  const pts = [];
  for (let s = 0; s < n; s++) for (let v = 0; v < 100; v++) pts.push([fnv1a("shard" + s + "#" + v), s]);
  return pts.sort((a, b) => a[0] - b[0]);
}
function owner(pts, k) {
  const h = fnv1a(k);
  let lo = 0, hi = pts.length;       // first point clockwise of the key
  while (lo < hi) { const m = (lo + hi) >> 1; if (pts[m][0] < h) lo = m + 1; else hi = m; }
  return pts[lo % pts.length][1];
}
const r4 = ring(4), r5 = ring(5);
moved = keys.filter((k) => owner(r4, k) !== owner(r5, k)).length;
console.log("consistent hashing: ", (moved / 1000).toFixed(1) + "% moved (a fair share for shard 5: 20%)");

08 · QUEUES

Queues and backpressure

Not every job has to finish before you answer. Sending an email, resizing a photo, updating a search index: put a message on a queue and reply "accepted" at once. Workers take messages off the other end at their own pace. Here the writes go through a queue, and the workers drain it no faster than the database can bear, so reads stay fast even in a write storm.

A queue doesn't add capacity. It adds time: a burst can be soaked up and worked off later. If writes arrive faster than workers drain them for long, the queue grows without end. So a good queue has a limit, and when it is full it pushes back: producers get "503, try later" instead of joining a line that will never move. That is backpressure, and it is far kinder than a server that accepts everything and answers nothing.

// A burst of 500 jobs/s for 20 s hits workers that do 300/s.
// The queue soaks up the burst, then drains. MAX is backpressure.
const MAX = 3000;
let depth = 0, rejected = 0, peak = 0;
for (let t = 0; t < 60; t++) {
  const arrive = t < 20 ? 500 : 100;
  const room = MAX - depth;
  const accepted = Math.min(arrive, room);
  rejected += arrive - accepted;            // told "503, try later"
  depth = Math.max(0, depth + accepted - 300);
  peak = Math.max(peak, depth);
  if (t % 5 === 4) console.log("t=" + (t + 1) + "s", "queue", depth, "rejected so far", rejected);
}
// Little's law: items waiting = arrival rate x time each waits
console.log("at the peak, a new job waits", (peak / 300).toFixed(1), "s");

Little's law ties it together: items in the system = arrival rate × time each spends there (L = λW). It holds for any stable queue, from a coffee shop to a Kafka topic. Most queues deliver at least once, so a worker can see the same message twice: workers must be idempotent, which is the next act but one.

09 · CONSISTENCY & CAP

Consistency models, CAP and PACELC

Once data lives on several machines, "what does a read return?" has more than one answer. These are consistency models, strongest first:

Linearizable: the system behaves as if there were one copy, and every read sees the latest completed write. Causal: if one write could have caused another, everyone sees them in that order. Read-your-writes and monotonic reads: guarantees for one user (act 6). Eventual: if writes stop, replicas end up the same, some time.

Below, shard 1's primary keeps writing a new value of x, and its replica copies it. Now cut the network between them. A user asks the replica for x. It has two honest options: refuse (it can't be sure it is up to date), or answer with what it has (which may be stale).

That is the CAP theorem, proved by Gilbert and Lynch in 2002: during a network Partition, a replicated system cannot be both Consistent (linearizable) and Available (every working node answers). Stated honestly, it is narrower than its fame:

You can't "choose" to give up P: networks fail whether you like it or not, so the choice is C or A while a partition lasts. When there is no partition, CAP says nothing. Its C means linearizability only, and its A means every node, which few real systems promise. That is why Kleppmann argues for not labelling databases "CP" or "AP" at all.

PACELC (Abadi, 2012) adds the part you live with every day: if Partitioned, choose A or C; Else, choose Latency or Consistency. Waiting for replicas in other buildings to confirm a write makes it consistent and slow; answering from the nearest copy makes it fast and possibly stale.

// N = 3 replicas. A write must reach W of them, a read asks R.
// Try every possible choice of replicas: can a read miss the latest write?
const N = 3;
function subsets(k) {
  const out = [];
  for (let m = 0; m < 1 << N; m++) {
    const s = [...Array(N).keys()].filter((i) => m & (1 << i));
    if (s.length === k) out.push(s);
  }
  return out;
}
for (const [W, R] of [[1, 1], [2, 1], [2, 2], [3, 1], [1, 3]]) {
  let stale = 0, total = 0;
  for (const w of subsets(W)) for (const r of subsets(R)) {
    total++;
    if (!r.some((i) => w.includes(i))) stale++;   // no overlap: old value
  }
  console.log("W=" + W, "R=" + R, R + W > N ? "R+W>N" : "R+W<=N", " stale reads possible:", stale + "/" + total);
}

10 · RETRIES

Timeouts, retries and idempotency

Networks drop packets and servers restart, so a call can fail for no lasting reason. The cure is simple: set a timeout, and if the call fails, try again. For rare, random failures it works wonders: if 10% of calls fail at random, four tries succeed 99.99% of the time.

Retries are poison when the failure is overload. Set the slider just past the break and compare the three policies. With three immediate retries, every failure comes back as more load, which causes more failures: a system a little past its limit ends up serving nothing that reaches its servers. Rejecting a request isn't free either, so the more it rejects the less real work it gets done. Backoff with a budget can't cure a steady overload (nothing can, except more capacity or less traffic), but it holds the extra load to about 10%, so the system stays up.

// Exponential backoff with "full jitter": wait a random time
// between 0 and base * 2^attempt (capped), so clients don't retry in sync.
let seed = 7;
const rand = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
const base = 100, cap = 5000;
​
for (let attempt = 0; attempt < 6; attempt++) {
  const ceiling = Math.min(cap, base * 2 ** attempt);
  const wait = Math.floor(rand() * ceiling);
  console.log("retry", attempt + 1, " window 0-" + ceiling + " ms", " waited", wait, "ms");
}
​
// Retries are for RARE, RANDOM failures. If 10% of calls fail at random:
const p = 0.1;
for (let tries = 1; tries <= 4; tries++) {
  console.log(tries, "tries: succeeds", ((1 - p ** tries) * 100).toFixed(2) + "% of the time");
}

The Google SRE book's rules: limit each request to three attempts; keep a retry budget so retries are at most 10% of a client's requests; use randomised exponential backoff; and retry at one layer only, because retries multiply: three layers that each try four times can send 64 attempts to the database for one click. Give each request a deadline and pass it down, so no one works on an answer nobody is waiting for.

import random, time
 
def call_with_retries(fn, attempts=4, base=0.1, cap=5.0):
    for attempt in range(attempts):
        try:
            return fn()
        except TimeoutError:
            if attempt == attempts - 1:
                raise                          # give up: let the caller decide
            time.sleep(random.uniform(0, min(cap, base * 2 ** attempt)))

Retries have a second trap. When a call times out, the client can't tell whether the request was lost or the reply was. Retrying a lost reply repeats the work: a second charge, a second order. The fix is idempotency: doing it twice has the same effect as once. GET, PUT and DELETE are idempotent by definition in HTTP; POST is not. For POST, the client sends an Idempotency-Key, and the server stores the reply under that key and returns it again on a repeat. Turn the keys off above and look at the ledger.

// The client sends "charge 30", the server does it, and the reply
// is lost. The client retries. Without a key, the card is charged twice.
const charges = [];
const seen = new Map();                 // idempotency key -> stored reply
​
function charge(amount, key) {
  if (key && seen.has(key)) return seen.get(key);   // same key: same answer
  charges.push(amount);
  const reply = { ok: true, id: charges.length };
  if (key) seen.set(key, reply);
  return reply;
}
​
charge(30);            // reply lost in the network...
charge(30);            // ...so the client tries again
console.log("no key:   ", charges.length, "charges");
​
charges.length = 0;
const key = "order-5521-attempt";       // made ONCE by the client, reused on retry
charge(30, key);
charge(30, key);
console.log("with key: ", charges.length, "charge");

11 · RATE LIMITING

Rate limiting and load shedding

When demand is more than you can serve, someone is going to be told no. The question is whether you choose who, and how fast. A rate limiter at the front door counts requests per client (or per API key, or overall) and refuses the excess at once with 429 Too Many Requests, often with a Retry-After header saying when to come back.

Push the slider far past the break. Without the limiter, everything behind the door overloads and everyone gets slow failures. With it, the system serves what it can at full speed and refuses the rest in a millisecond. Shedding load early and cheaply is what keeps an overload from becoming an outage.

The classic algorithm is the token bucket: tokens drip into a bucket at a steady rate, up to a maximum; each request takes one; an empty bucket means 429. It allows short bursts (up to the bucket size) but enforces the average. Others: fixed window (count per minute: simple, but allows double bursts at the edges), sliding window, and the leaky bucket, which smooths output to a constant rate.

// Token bucket: tokens drip in at RATE per second, up to BURST.
// Each request spends one. No token: 429 Too Many Requests.
const RATE = 5, BURST = 10;
let tokens = BURST, last = 0;
​
function allow(now) {
  tokens = Math.min(BURST, tokens + (now - last) * RATE);   // refill
  last = now;
  if (tokens >= 1) { tokens -= 1; return true; }
  return false;
}
​
// a client fires 30 requests in 3 seconds (10/s, twice its limit)
let ok = 0, refused = 0;
for (let i = 0; i < 30; i++) {
  if (allow(i * 0.1)) ok++; else refused++;
}
console.log("allowed", ok, " refused with 429:", refused);
// 10 from the full bucket, then about 5 per second after that

12 · OBSERVABILITY

Observability: metrics, logs and traces

You can't fix what you can't see, and at scale you can't see anything by looking at one machine. Observability is building the system so it tells you what it is doing. Three kinds of signal, all on the panels above the system:

Metrics are numbers over time, cheap to keep: requests per second, error rate, p99 latency, CPU. The SRE book's four golden signals are latency, traffic, errors and saturation; if you measure only four things, measure those. Logs are a record per event; write them as structured data (JSON), not prose, so a machine can search them. Traces follow one request through every service it touches, as a tree of timed spans, joined by a trace ID passed along with each call. Google's Dapper paper made this practical; OpenTelemetry is today's open standard.

Push the load past the break and watch the panels: saturation hits the top first, then the latency bars, then the errors. Saturation is the early warning; alert on it before your users notice.

// 1,000 request times: most are quick, a few are very slow.
let seed = 3;
const rand = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
const ms = Array.from({ length: 1000 }, () => (rand() < 0.97 ? 20 + rand() * 30 : 400 + rand() * 1600));
​
const sorted = [...ms].sort((a, b) => a - b);
const pct = (p) => sorted[Math.ceil((p / 100) * sorted.length) - 1];
const mean = ms.reduce((a, b) => a + b) / ms.length;
​
console.log("mean", mean.toFixed(0), "ms");
console.log("p50 ", pct(50).toFixed(0), "ms   (the typical user)");
console.log("p95 ", pct(95).toFixed(0), "ms");
console.log("p99 ", pct(99).toFixed(0), "ms   (1 in 100 waits this long or more)");
​
// Fan-out: a page that needs answers from n servers waits for the slowest.
for (const n of [1, 10, 100]) {
  console.log(n, "servers: a slow reply in", ((1 - 0.99 ** n) * 100).toFixed(0) + "% of pages");
}

Teams turn this into promises: a service level objective such as "99.9% of requests under 300 ms over 30 days". The gap between 100% and the SLO is an error budget you are allowed to spend on risk, like shipping faster.

13 · ESTIMATION

Capacity estimation on the back of an envelope

Before you design, estimate. The goal is the right order of magnitude in five minutes, so you know whether you need one server or a thousand. Write your assumptions down, round boldly, and keep the units.

Say we're building a URL shortener. Assume 100 million new links a month and 100 clicks per link. Numbers worth knowing by heart: a day is 86,400 seconds (about 10⁵), a month about 2.6 million. So:

// A URL shortener, on the back of an envelope.
const newPerMonth = 100e6;          // assumption: 100 million new links a month
const readsPerWrite = 100;          // each link is clicked 100 times on average
const secondsPerMonth = 30 * 86400; // 2.6 million: worth remembering
const bytesPerLink = 500;           // long URL + short code + owner + dates
const years = 5;
​
const writes = newPerMonth / secondsPerMonth;
const reads = writes * readsPerWrite;
const peak = 3;                     // busiest hour vs the average: assumption
const storage = newPerMonth * 12 * years * bytesPerLink;
const links = newPerMonth * 12 * years;
const hotSet = reads * 86400 * 0.2 * bytesPerLink; // cache the hottest 20% of a day
​
console.log("writes:", writes.toFixed(0), "/s  peak", (writes * peak).toFixed(0), "/s");
console.log("reads: ", reads.toFixed(0), "/s  peak", (reads * peak).toFixed(0), "/s");
console.log("links after", years, "years:", (links / 1e9).toFixed(1), "billion");
console.log("storage:", (storage / 1e12).toFixed(1), "TB");
console.log("cache for the hot 20%:", (hotSet / 1e9).toFixed(0), "GB");
console.log("7 base-62 characters give", (62 ** 7 / 1e12).toFixed(2), "trillion codes");

Read the results the way an architect would. 39 writes a second is nothing; one database primary handles that easily. About 3,900 reads a second (12,000 at peak) is real but cacheable: links are written once and read many times, and a few links get most of the clicks. 3 TB fits on one disk but should be sharded for growth, and 33 GB of hot links fits in the RAM of one cache server. The tower in the 3D grows one slab a month for five years.

14 · A URL SHORTENER

A worked design: a URL shortener, worldwide

Put it all together. The process is the same for any system: requirements, estimates, API, data model, high-level design, then the bottlenecks and failures.

Requirements. Make a short link for a long URL; redirect anyone who opens it, fast; links last five years. Not in scope: editing links, analytics dashboards. Estimates: the last act, about 4,000 reads a second, 40 writes, 3 TB. API: two endpoints.

POST /api/links HTTP/1.1
Host: sho.rt
Content-Type: application/json
Idempotency-Key: 9b1d4c8e-6f0a-4a57-9a43-2f1e7c3d5b20
 
{"url": "https://example.com/a/very/long/path"}
 
HTTP/1.1 201 Created
{"short": "https://sho.rt/8tmGqb"}
 
GET /8tmGqb HTTP/1.1
Host: sho.rt
 
HTTP/1.1 302 Found
Location: https://example.com/a/very/long/path
Cache-Control: private, max-age=90

Notice 302 Found: a 301 Moved Permanently would let browsers cache the redirect forever, which is faster but means you never see the click again and can't change the target. And notice the idempotency key on the POST: a retried "create" returns the same short link instead of making two.

CREATE TABLE links (
  code        VARCHAR(10) PRIMARY KEY,
  long_url    TEXT        NOT NULL,
  owner_id    BIGINT,
  created_at  TIMESTAMP   NOT NULL DEFAULT now(),
  expires_at  TIMESTAMP
);
 
SELECT long_url FROM links WHERE code = 'xqH3a';

Making the code. Three options. Hash the long URL and take 7 characters: simple, but collisions must be checked. Random codes: also need a collision check. A counter turned into base 62: no collisions, and to avoid one counter becoming a bottleneck each server reserves a block of ids (say 10,000 at a time) from a central store. With 7 characters, base 62 gives 3.5 trillion codes, enough for 6 billion links many times over.

// The heart of a URL shortener: a counter, base 62, and a map.
const ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
​
function encode(n) {
  let s = "";
  do { s = ALPHABET[n % 62] + s; n = Math.floor(n / 62); } while (n > 0);
  return s;
}
​
const links = new Map();   // code -> long URL (the database)
const cache = new Map();   // the hot ones, in memory
let nextId = 125_000_000;  // in production: ranges handed out to each server
​
function shorten(url) {
  const code = encode(nextId++);
  links.set(code, url);
  return "https://sho.rt/" + code;
}
​
function visit(code) {
  let url = cache.get(code);
  if (!url) { url = links.get(code); if (url) cache.set(code, url); }
  return url ? { status: 302, location: url } : { status: 404 };
}
​
const short = shorten("https://en.wikipedia.org/wiki/Back-of-the-envelope_calculation");
console.log(short);
console.log(visit(short.split("/").pop()));
console.log(visit("nope"));

High-level design, as the 3D shows it: the CDN caches popular redirects at the edge (with a short max-age); a rate limiter stops one client from minting millions of links; stateless app servers behind a load balancer; a cache for hot codes; the links table sharded by code, each shard with a replica; a queue to update click counters without slowing redirects. Then the step most designs skip: three regions, so a user in Sydney isn't paying 150 ms per round trip to Europe, and so the service survives losing a whole datacentre. Reads are local; new links are written in one region and replicated, and because a code never changes once created, a few hundred milliseconds of lag is harmless. That is PACELC in practice: we chose latency, because this data allows it.

Where would it break next? Drag the slider. Then ask the questions that matter in a real review: what if one link goes viral (a hot key: it is served from the CDN and every cache, so fine)? What if a region goes dark (DNS sends its users to the next nearest)? What if someone uses it to spread malware links (a separate scanning queue and a block list)?