The System Design Interview

FUNCTIONAL
  1. 1:1 and group chats (groups up to 500 members)
  2. Send and receive text messages in real time
  3. Delivery and read receipts
  4. Message history on all my devices
OUT OF SCOPE: voice/video calls, media, end-to-end encryption details

NON-FUNCTIONAL
  Scale        100 M DAU, ~40 messages sent per user per day
  Latency      message delivered to an online recipient in < 500 ms
  Ordering     messages appear in the same order for everyone in a chat
  Delivery     no message lost; duplicates hidden from the user
  Availability 99.99% for sending; history can lag briefly
  Retention    keep history forever

// Powers of two against the decimal round numbers you use at the whiteboard.
const units = ["KiB vs KB", "MiB vs MB", "GiB vs GB", "TiB vs TB", "PiB vs PB"];
const fmt = (n) => n.toLocaleString("en-US", { maximumFractionDigits: 1 });
units.forEach((unit, i) => {
  const binary = 2 ** (10 * (i + 1));
  const decimal = 10 ** (3 * (i + 1));
  const off = ((binary / decimal - 1) * 100).toFixed(1);
  console.log(`${unit}  2^${10 * (i + 1)} = ${fmt(binary).padStart(25)}  is ${off.padStart(4)}% more than 10^${3 * (i + 1)}`);
});

// Time shortcuts: the exact numbers and the round ones people use.
const day = 24 * 60 * 60;
console.log();
for (const [label, exact, round, roundLabel] of [
  ["seconds per day", day, 1e5, "100,000"],
  ["seconds per month (30 d)", 30 * day, 2.5e6, "2.5 million"],
  ["seconds per year", 365 * day, Math.PI * 1e7, "π × 10^7"],
]) {
  const err = ((round / exact - 1) * 100).toFixed(1);
  console.log(`${label.padEnd(25)}${fmt(exact).padStart(11)}  ≈ ${roundLabel.padEnd(11)} (${err > 0 ? "+" : ""}${err}%)`);
}

// Requests per day → average requests per second.
console.log();
for (const perDay of [1e6, 10e6, 100e6, 1e9]) {
  console.log(`${fmt(perDay).padStart(13)} a day = ${fmt(perDay / day).padStart(8)} a second on average`);
}

KiB vs KB  2^10 =                     1,024  is  2.4% more than 10^3
MiB vs MB  2^20 =                 1,048,576  is  4.9% more than 10^6
GiB vs GB  2^30 =             1,073,741,824  is  7.4% more than 10^9
TiB vs TB  2^40 =         1,099,511,627,776  is 10.0% more than 10^12
PiB vs PB  2^50 =     1,125,899,906,842,624  is 12.6% more than 10^15

seconds per day               86,400  ≈ 100,000     (+15.7%)
seconds per month (30 d)   2,592,000  ≈ 2.5 million (-3.5%)
seconds per year          31,536,000  ≈ π × 10^7    (-0.4%)

    1,000,000 a day =     11.6 a second on average
   10,000,000 a day =    115.7 a second on average
  100,000,000 a day =  1,157.4 a second on average
1,000,000,000 a day = 11,574.1 a second on average

// From the photo-app estimates to hardware: servers, CDN offload and cache memory.
const DAY = 86_400;
const dau = 50e6;
const peakFactor = 3;

// 1. Feed API servers. ASSUMPTION: one server handles 1,000 feed requests/s (measure yours with a load test).
const feedPeak = ((dau * 10) / DAY) * peakFactor;
const perServer = 1000;
const targetUtilisation = 0.6; // leave headroom for spikes, GC pauses, deploys
const needed = Math.ceil(feedPeak / (perServer * targetUtilisation));
const zones = 3;
// Survive losing a whole zone: the remaining zones must carry the full peak.
const withZoneLoss = Math.ceil(needed / (zones - 1)) * zones;
console.log(`feed peak ${Math.round(feedPeak).toLocaleString("en-US")} QPS → ${needed} servers at 60% → ${withZoneLoss} across ${zones} zones (survives losing one)`);

// 2. Image egress and the CDN. Views: 100 per user per day at 300 KB.
const viewGbps = ((dau * 100) / DAY) * 300e3 * 8 / 1e9;
for (const hitRatio of [0.9, 0.95, 0.99]) {
  const origin = viewGbps * (1 - hitRatio);
  console.log(`CDN hit ratio ${(hitRatio * 100).toFixed(0)}%: origin serves ${origin.toFixed(1).padStart(4)} Gbit/s of ${viewGbps.toFixed(0)} (avg), ${(origin * peakFactor).toFixed(1).padStart(4)} at peak`);
}

// 3. Cache memory for recent post metadata (feeds mostly show the last few days).
const postsPerDay = dau * 0.1;
const bytesPerPost = 1e3;
for (const days of [1, 7, 30]) {
  const gb = (postsPerDay * bytesPerPost * days) / 1e9;
  console.log(`metadata for the last ${String(days).padStart(2)} ${days === 1 ? "day: " : "days:"} ${gb.toFixed(0).padStart(3)} GB in cache`);
}

feed peak 17,361 QPS → 29 servers at 60% → 45 across 3 zones (survives losing one)
CDN hit ratio 90%: origin serves 13.9 Gbit/s of 139 (avg), 41.7 at peak
CDN hit ratio 95%: origin serves  6.9 Gbit/s of 139 (avg), 20.8 at peak
CDN hit ratio 99%: origin serves  1.4 Gbit/s of 139 (avg),  4.2 at peak
metadata for the last  1 day:    5 GB in cache
metadata for the last  7 days:  35 GB in cache
metadata for the last 30 days: 150 GB in cache

// The physics floor under cross-region latency: light in glass fibre covers about 1 km every 4.9 µs.
const US_PER_KM = 4.9; // one way, refractive index ≈ 1.47

const places = {
  Virginia: [37.54, -77.44], // Azure East US (approximate city coordinates)
  California: [37.77, -122.42], // West US
  London: [51.51, -0.13], // UK South
  Singapore: [1.35, 103.82], // Southeast Asia
  Sydney: [-33.87, 151.21], // Australia East
};

// Great-circle distance: the shortest path over the Earth's surface (haversine formula).
function km([lat1, lon1], [lat2, lon2]) {
  const rad = Math.PI / 180;
  const a = Math.sin(((lat2 - lat1) * rad) / 2) ** 2 +
    Math.cos(lat1 * rad) * Math.cos(lat2 * rad) * Math.sin(((lon2 - lon1) * rad) / 2) ** 2;
  return 2 * 6371 * Math.asin(Math.sqrt(a));
}

// Measured P50 round trips between those Azure regions (30 days to July 30, 2026).
const measured = [
  ["Virginia", "California", 69],
  ["Virginia", "London", 78],
  ["Virginia", "Singapore", 224],
  ["London", "Sydney", 261],
];

for (const [a, b, ms] of measured) {
  const d = km(places[a], places[b]);
  const floor = (2 * d * US_PER_KM) / 1000; // there and back, in ms
  console.log(`${`${a} ↔ ${b}`.padEnd(22)}${Math.round(d).toLocaleString("en-US").padStart(7)} km  ` +
    `floor ${floor.toFixed(0).padStart(3)} ms  measured ${String(ms).padStart(3)} ms  (${(ms / floor).toFixed(2)}× the floor)`);
}

Virginia ↔ California   3,920 km  floor  38 ms  measured  69 ms  (1.80× the floor)
Virginia ↔ London       6,024 km  floor  59 ms  measured  78 ms  (1.32× the floor)
Virginia ↔ Singapore   15,689 km  floor 154 ms  measured 224 ms  (1.46× the floor)
London ↔ Sydney        16,994 km  floor 167 ms  measured 261 ms  (1.57× the floor)

// Adding up a request's latency from its hops. Network times are the round trips from the ladder;
// the work done at each hop (a cache GET, a DB query) is an ASSUMPTION written next to it.
const SAME_ZONE = 0.3, CROSS_ZONE = 1.5, US_TO_UK = 78; // ms, round trips

const hop = (name, network, work) => ({ name, ms: network + work });
const times = (n, h) => ({ name: `${n} × ${h.name}`, ms: n * h.ms }); // n calls, one after another
const seq = (name, steps) => ({ name, ms: steps.reduce((s, x) => s + x.ms, 0), steps, how: "total" });
const par = (name, steps) => ({ name, ms: Math.max(...steps.map((x) => x.ms)), steps, how: "(slowest wins)" });

const naive = seq("naive feed request", [
  hop("session from cache in another zone", CROSS_ZONE, 0.2),
  times(20, hop("post from the DB, one query each", CROSS_ZONE, 1)),
  hop("ranking service in the UK region", US_TO_UK, 10),
]);

const better = seq("better feed request", [
  hop("session from cache in the same zone", SAME_ZONE, 0.2),
  par("three independent calls at once", [
    hop("20 posts in one batched query", CROSS_ZONE, 4),
    hop("ranking service in this region", CROSS_ZONE, 10),
    hop("like counts from cache", SAME_ZONE, 0.5),
  ]),
]);

function show(node, depth = 0) {
  const label = "  ".repeat(depth) + node.name;
  console.log(`${label.padEnd(42)}${node.ms.toFixed(1).padStart(6)} ms ${node.how ?? ""}`.trimEnd());
  for (const step of node.steps ?? []) show(step, depth + 1);
}

show(naive);
show(better);
console.log(`speed-up: ${(naive.ms / better.ms).toFixed(1)}×`);

naive feed request                         139.7 ms total
  session from cache in another zone         1.7 ms
  20 × post from the DB, one query each     50.0 ms
  ranking service in the UK region          88.0 ms
better feed request                         12.0 ms total
  session from cache in the same zone        0.5 ms
  three independent calls at once           11.5 ms (slowest wins)
    20 posts in one batched query            5.5 ms
    ranking service in this region          11.5 ms
    like counts from cache                   0.8 ms
speed-up: 11.6×

// Fan-out makes the tail the common case: a request that waits for N servers is slow if ANY of them is.
// Each server: usually 10 ms, but 1 request in 100 takes 1,000 ms (its p99), independently.
function mulberry32(seed) { // small seeded PRNG, so the simulation prints the same numbers every run
  return () => {
    let t = (seed = (seed + 0x6d2b79f5) | 0); // stay a 32-bit integer
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
const rand = mulberry32(2026);
const serverLatency = () => (rand() < 0.01 ? 1000 : 10);

const TRIALS = 100_000;
for (const fanOut of [1, 10, 100]) {
  let slow = 0;
  for (let t = 0; t < TRIALS; t++) {
    let worst = 0;
    for (let s = 0; s < fanOut; s++) worst = Math.max(worst, serverLatency());
    if (worst >= 1000) slow++;
  }
  const formula = 1 - 0.99 ** fanOut; // P(at least one slow) = 1 - P(none slow)
  console.log(`fan-out ${String(fanOut).padStart(3)}: ${(formula * 100).toFixed(1).padStart(4)}% slow by formula, ` +
    `${((slow / TRIALS) * 100).toFixed(1).padStart(4)}% in ${TRIALS.toLocaleString("en-US")} simulated requests`);
}

fan-out   1:  1.0% slow by formula,  1.0% in 100,000 simulated requests
fan-out  10:  9.6% slow by formula,  9.4% in 100,000 simulated requests
fan-out 100: 63.4% slow by formula, 63.4% in 100,000 simulated requests

// Measures the cost of one dependent memory load: each read's address comes from the previous read,
// so the CPU can't overlap them. Small arrays fit in cache; big ones force a trip to DRAM.
function chase(bytes, hops = 20_000_000) {
  const n = bytes / 4;
  const next = new Int32Array(n);
  // Sattolo's shuffle: one big random cycle through every slot (seeded, so runs are comparable).
  let seed = 42;
  const rand = () => ((seed = (seed * 1103515245 + 12345) >>> 0) / 2 ** 32);
  for (let i = 0; i < n; i++) next[i] = i;
  for (let i = n - 1; i > 0; i--) {
    const j = Math.floor(rand() * i);
    [next[i], next[j]] = [next[j], next[i]];
  }
  let p = 0;
  for (let i = 0; i < 1_000_000; i++) p = next[p]; // warm up
  const t0 = process.hrtime.bigint();
  for (let i = 0; i < hops; i++) p = next[p];
  const ns = Number(process.hrtime.bigint() - t0) / hops;
  return { ns, p };
}

for (const [label, bytes] of [["16 KiB (L1)", 16 << 10], ["1 MiB (L2)", 1 << 20], ["1 GiB (DRAM)", 1 << 30]]) {
  const { ns } = chase(bytes);
  console.log(`${label.padEnd(14)} ${ns.toFixed(1)} ns per dependent load`);
}

16 KiB (L1)    1.4 ns per dependent load
1 MiB (L2)     3.6 ns per dependent load
1 GiB (DRAM)   127.4 ns per dependent load

// Availability of a system from the availability of its parts (assuming parts fail independently).
const serial = (...parts) => parts.reduce((a, p) => a * p, 1); // every part must be up
const parallel = (...parts) => 1 - parts.reduce((a, p) => a * (1 - p), 1); // at least one must be up
const pct = (a) => `${(a * 100).toFixed(7).replace(/0+$/, "")}%`.padEnd(12);
const downPerYear = (a) => {
  const minutes = (1 - a) * 365 * 24 * 60;
  return minutes >= 1 ? `${minutes.toFixed(0)} min/year down` : `${(minutes * 60).toFixed(1)} s/year down`;
};

// Serial: a request passes through all three.
const lb = 0.9999, app = 0.999, db = 0.9995;
const chain = serial(lb, app, db);
console.log(`serial   LB × app × DB         ${pct(chain)}  ${downPerYear(chain)}`);

// Parallel: three copies, any one can serve. Each is a single instance at 99.5%.
const one = 0.995;
for (const n of [1, 2, 3]) {
  const copies = parallel(...Array(n).fill(one));
  console.log(`parallel ${n} × instance at 99.5% ${pct(copies)}  ${downPerYear(copies)}`);
}

// A whole design: LB → 3 app instances (any one will do) → DB primary with a standby.
const design = serial(lb, parallel(one, one, one), parallel(0.9995, 0.9995));
console.log(`design   LB → 3 apps → DB pair ${pct(design)}  ${downPerYear(design)}`);

// Ten dependencies in a chain, each a respectable 99.9%:
const ten = serial(...Array(10).fill(0.999));
console.log(`serial   10 × 99.9% deps       ${pct(ten)}  ${downPerYear(ten)}`);

serial   LB × app × DB         99.840065%    841 min/year down
parallel 1 × instance at 99.5% 99.5%         2628 min/year down
parallel 2 × instance at 99.5% 99.9975%      13 min/year down
parallel 3 × instance at 99.5% 99.9999875%   3.9 s/year down
design   LB → 3 apps → DB pair 99.9899625%   53 min/year down
serial   10 × 99.9% deps       99.004488%    5232 min/year down

// Checks the formulas by simulation: components fail and get repaired at random (seeded), minute by minute.
// Availability of one part = MTBF / (MTBF + MTTR): mean time between failures over the whole cycle.
function mulberry32(seed) {
  return () => {
    let t = (seed = (seed + 0x6d2b79f5) | 0); // stay a 32-bit integer
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
const rand = mulberry32(7);
const HOUR = 60, DAY = 24 * HOUR, MINUTES = 200 * 365 * DAY; // simulate 200 years

const part = (mtbf, mttr) => ({ mtbf, mttr, up: true, upMinutes: 0 });
const step = (p) => { // each minute: an up part may fail, a down part may come back
  if (p.up ? rand() < 1 / p.mtbf : rand() < 1 / p.mttr) p.up = !p.up;
  if (p.up) p.upMinutes++;
};

const appA = part(30 * DAY, 2 * HOUR), appB = part(30 * DAY, 2 * HOUR);
const db = part(90 * DAY, 1 * HOUR);
const zone = part(365 * DAY, 4 * HOUR); // a zone outage takes down everything in that zone
let pairUp = 0, systemUp = 0, sameZoneUp = 0;
for (let m = 0; m < MINUTES; m++) {
  [appA, appB, db, zone].forEach(step);
  const pair = appA.up || appB.up;
  if (pair) pairUp++;
  if (pair && db.up) systemUp++;
  if (pair && db.up && zone.up) sameZoneUp++; // both apps and the DB in ONE zone
}

const formula = (p) => p.mtbf / (p.mtbf + p.mttr);
const a = formula(appA), d = formula(db), z = formula(zone);
const show = (label, f, sim) =>
  console.log(`${label.padEnd(30)} formula ${(f * 100).toFixed(4)}%  simulated ${((sim / MINUTES) * 100).toFixed(4)}%`);
show("one app server", a, appA.upMinutes);
show("two app servers (parallel)", 1 - (1 - a) ** 2, pairUp);
show("app pair then DB (serial)", (1 - (1 - a) ** 2) * d, systemUp);
show("same, all in one zone", (1 - (1 - a) ** 2) * d * z, sameZoneUp);

one app server                 formula 99.7230%  simulated 99.7216%
two app servers (parallel)     formula 99.9992%  simulated 99.9993%
app pair then DB (serial)      formula 99.9530%  simulated 99.9533%
same, all in one zone          formula 99.9073%  simulated 99.9080%

// An error budget is the failure the SLO allows: (1 - SLO) of the requests in the window.
const SLO = 0.999; // 99.9% of requests succeed, measured over 30 days
const WINDOW_HOURS = 30 * 24;
const avgQps = 500;
const requests = avgQps * WINDOW_HOURS * 3600;
const budget = requests * (1 - SLO);
console.log(`window: ${requests.toLocaleString("en-US")} requests → budget ${Math.round(budget).toLocaleString("en-US")} failed requests`);

// Incidents spend the budget. Each: how long it lasted, the error rate, the traffic during it.
const incidents = [
  { what: "bad deploy, rolled back", minutes: 12, errorRate: 0.3, qps: 900 },
  { what: "DB failover", minutes: 2, errorRate: 1.0, qps: 500 },
  { what: "slow leak of 0.5% errors", minutes: 3 * 24 * 60, errorRate: 0.005, qps: 500 },
];
let spent = 0;
for (const i of incidents) {
  const failed = i.minutes * 60 * i.qps * i.errorRate;
  spent += failed;
  console.log(`${i.what.padEnd(26)} ${Math.round(failed).toLocaleString("en-US").padStart(9)} failed  ` +
    `(${((failed / budget) * 100).toFixed(1).padStart(4)}% of budget, ${((spent / budget) * 100).toFixed(1)}% used so far)`);
}

// Burn rate: how many times faster than "exactly on budget" errors are arriving.
// At burn rate 1 the budget lasts exactly the window; at 14.4 it's gone in 720 / 14.4 = 50 hours.
for (const errorRate of [0.001, 0.005, 0.0144, 0.1]) {
  const burn = errorRate / (1 - SLO);
  console.log(`error rate ${(errorRate * 100).toFixed(2).padStart(5)}%  burn rate ${burn.toFixed(1).padStart(5)}  ` +
    `a full budget lasts ${(WINDOW_HOURS / burn).toFixed(1).padStart(5)} hours`);
}

window: 1,296,000,000 requests → budget 1,296,000 failed requests
bad deploy, rolled back      194,400 failed  (15.0% of budget, 15.0% used so far)
DB failover                   60,000 failed  ( 4.6% of budget, 19.6% used so far)
slow leak of 0.5% errors     648,000 failed  (50.0% of budget, 69.6% used so far)
error rate  0.10%  burn rate   1.0  a full budget lasts 720.0 hours
error rate  0.50%  burn rate   5.0  a full budget lasts 144.0 hours
error rate  1.44%  burn rate  14.4  a full budget lasts  50.0 hours
error rate 10.00%  burn rate 100.0  a full budget lasts   7.2 hours