Glossary

Not definitions — explanations. Every entry answers five questions: what it is from first principles, why it exists (what problem forced its invention), how it works internally, what it connects to, and where it shows up in production.

An entry you can read and still not implement the thing is a failed entry. Where a mechanism has a number attached, the number is here too.

Table of Contents

• Measurement and Performance
• Memory and Hardware
• Storage
• Distributed Systems
• Streaming
• Retrieval
• Machine-Learning Systems
• Recommendation and Experimentation
• Languages and Runtimes
• Operating Systems
• References

Measurement and Performance

Amplification (read / write / space)

What. The ratio between work the system actually does and work the user asked for. Write amplification = bytes written to the device ÷ bytes the user wrote. Read amplification = blocks read ÷ blocks logically needed. Space amplification = bytes on disk ÷ bytes of live data.

Why. Without these three numbers, "my storage engine is fast" is unfalsifiable. They turn a vague performance discussion into an accounting identity, and they make the trade-offs impossible to hide: you cannot improve all three, so any design decision must say which one it is spending.

How. You instrument them with counters inside the code, not by watching iostat. The OS can tell you bytes went to the device; it cannot attribute them to a memtable flush versus an L2→L3 compaction. Retrofitting these counters after the fact always misses paths, which is why P04 puts them in milestone 2.

Connects to. The RUM conjecture is the formal statement that you must choose. Compaction is the knob. Bloom filters buy read amplification with memory.

Production. Leveled compaction at fanout 10 gives W/R/S ≈ 31/4/1.10; size-tiered gives 4/30/2.11 (numbers). RocksDB exposes both and makes you choose; the choice is the single biggest performance lever in an LSM deployment.

Try it — the trade, computed:

import math
T, base = 10, 64e6
for data in (8e9, 512e9):
    L = max(1, math.ceil(math.log(data/base, T)))
    print(f"{data/1e9:>5.0f} GB, {L} levels:  "
          f"leveled W/R/S = {T*L+1:>3}/{L+1}/{1+1/T:.2f}   "
          f"tiered = {L+1:>3}/{T*L}/2.00")
print("no strategy wins all three -- that is the RUM conjecture")

    8 GB, 3 levels:  leveled W/R/S =  31/4/1.10   tiered =   4/30/2.00
  512 GB, 4 levels:  leveled W/R/S =  41/5/1.10   tiered =   5/40/2.00
no strategy wins all three -- that is the RUM conjecture

Arithmetic intensity

What. FLOPs performed per byte moved from DRAM: \(I = W/Q\). Units are FLOP/byte.

Why. Because compute got cheap and memory did not. A modern accelerator can do hundreds of FLOPs in the time it takes to fetch one byte from HBM, so the question "is this kernel fast?" is really "does it do enough arithmetic per byte to keep the multipliers fed?"

How. \(Q\) is DRAM traffic, not total loads — a value served from L2 costs no DRAM traffic. This is why tiling works: it does not change \(W\), it shrinks \(Q\) by making each fetched byte serve more arithmetic, sliding the kernel rightward along the roofline until it hits the compute ceiling.

Connects to. Roofline, ridge point, operator fusion, systolic array.

Production. A 4096³ bf16 GEMM has \(I = 1365\) with perfect reuse and \(I = 1.0\) with none — a 295× runtime difference on identical arithmetic (numbers). In transformer decode, \(I = 2b/\text{bytes}\), i.e. arithmetic intensity equals batch size and nothing else, which is the whole reason continuous batching exists.

Try it — the same GEMM, 295× apart:

def gemm_intensity(m,n,k,bytes_per=2):
    W = 2*m*n*k
    Q_best = (m*k + k*n + m*n)*bytes_per   # each matrix streamed once
    Q_none = (m*k + m*k*n + m*n)*bytes_per # B re-read per row of A
    return W/Q_best, W/Q_none
b,w = gemm_intensity(4096,4096,4096)
print(f"perfect reuse I={b:8.1f} FLOP/byte  -> compute-bound on an H100 (ridge 295)")
print(f"no reuse      I={w:8.1f} FLOP/byte  -> memory-bound; same arithmetic, 295x slower")

perfect reuse I=  1365.3 FLOP/byte  -> compute-bound on an H100 (ridge 295)
no reuse      I=     1.0 FLOP/byte  -> memory-bound; same arithmetic, 295x slower

Bootstrap (confidence interval)

What. A non-parametric way to put an uncertainty interval on any statistic: resample your observed data with replacement many times, recompute the statistic on each resample, and take the empirical quantiles of those values.

Why. Latency distributions are right-skewed, often multi-modal, and never normal. A t-interval on the mean assumes normality and is simply wrong for them. The bootstrap assumes only that your sample is representative.

How. Fifteen lines: draw \(n\) samples with replacement from your \(n\) observations, compute the median, repeat 2,000×, sort, take the 2.5th and 97.5th percentiles. Implemented in tools/bench.py.

Connects to. Tail latency — you bootstrap the median and the percentiles, not the mean. Common random numbers reduces the variance the bootstrap then measures.

Production. The reason to bother: it lets you say "no measurable difference" honestly when two intervals overlap. Reporting "3% faster" from overlapping intervals is the most common benchmarking lie, and a harness that cannot produce that verdict will manufacture wins for you.

Try it — the honest verdict, in eight lines:

import random, statistics
def ci_median(s, iters=2000, conf=95, seed=0):
    rng=random.Random(seed); n=len(s)
    meds=sorted(statistics.median([s[rng.randrange(n)] for _ in range(n)]) for _ in range(iters))
    lo=(100-conf)/2/100; return meds[int(lo*iters)], meds[int((1-lo)*iters)-1]
rng=random.Random(1)
a=[rng.gauss(100,10) for _ in range(300)]
b=[rng.gauss(101,10) for _ in range(300)]
print("A median 95% CI:", tuple(round(x,2) for x in ci_median(a)))
print("B median 95% CI:", tuple(round(x,2) for x in ci_median(b)))
print("overlap -> report NO MEASURABLE DIFFERENCE, not a 1% win")

A median 95% CI: (99.98, 102.03)
B median 95% CI: (99.27, 101.64)
overlap -> report NO MEASURABLE DIFFERENCE, not a 1% win

Coordinated omission

What. A measurement bug in which a load generator that waits for a response stops issuing requests during a stall, and therefore never records the latencies its own stall caused.

Why it matters. It makes the tail look far better than it is. If your system freezes for 1 second at 1,000 req/s, ~1,000 requests should have been recorded at latencies from 1 ms to 1,000 ms. A closed-loop generator records one slow request and then resumes, so your p99 barely moves.

How to avoid. Issue requests on a schedule (open-loop) rather than after the previous response, and record latency from the request's intended send time.

Connects to. Tail latency, Little's Law.

Production. Almost every naive benchmark of a server has this bug. It is the main reason internally-measured p99s look much better than user-observed ones.

Little's Law

What. \(L = \lambda W\): the average number of items in a stable system equals arrival rate × average time in system. No assumptions about the arrival or service distribution.

Why. It converts between three things you can each measure and lets you check them against each other. Any two give you the third.

How. Applied to memory: to sustain 57.5 GB/s at 121 ns latency you need \(57.5\times10^9 \times 121\times10^{-9} = 6{,}958\) bytes — ~109 cache lines in flight at all times (numbers). A single dependent-load chain keeps exactly one in flight, achieving 0.53 GB/s — 108× below peak on the same hardware.

Connects to. Memory-level parallelism, backpressure, and the utilisation law in math.md.

Production. The cleanest way to sanity-check a capacity claim. If someone says "10,000 QPS at 50 ms latency with 100 threads", Little's Law says you need \(10{,}000 \times 0.05 = 500\) concurrent requests. With 100 threads, it is impossible.

Try it — two applications of one identity:

lam, W = 10_000, 0.050        # 10k req/s at 50 ms
print(f"requests in flight = {lam*W:.0f}")
print(f"with 100 threads: {'impossible' if lam*W > 100 else 'fine'}")
bw, lat = 57.5e9, 121e-9
print(f"bytes in flight to sustain {bw/1e9:.1f} GB/s at {lat*1e9:.0f} ns = "
      f"{bw*lat:.0f} ({bw*lat/64:.0f} cache lines)")

requests in flight = 500
with 100 threads: impossible
bytes in flight to sustain 57.5 GB/s at 121 ns = 6958 (109 cache lines)

Relative contrast

What. \(\mathrm{RC} = d_{\text{mean}} / d_1\) — the mean distance from a query to the whole dataset divided by the distance to its true nearest neighbour.

Why. Because ambient dimension \(d\) does not predict nearest-neighbour difficulty and everyone uses it as if it does. Real embeddings live near a low-dimensional manifold and are far easier than their \(d\) suggests.

How. As RC → 1, every point is about as far as every other, greedy descent has no gradient to follow, and any distance-based method degenerates toward random. Measured on uniform data at \(n{=}10\)k: RC = 2.22 at d=16, 1.36 at d=64, 1.10 at d=512 (numbers).

Connects to. Curse of dimensionality, HNSW, greedy graph search.

Production. Report RC with every recall number. An ANN benchmark on uniform high-dimensional data measures the dataset, not the index, and its conclusions do not transfer to your corpus.

Roofline model

What. Achievable performance is \(\min(P,\; I\times B)\), where \(P\) is peak compute, \(B\) is peak bandwidth, and \(I\) is arithmetic intensity. Plotted on log-log axes it looks like a slanted roof meeting a flat ceiling.

Why. It answers "am I doing badly, and in which direction?" with two measurements instead of a profiler session. Below the roof you have headroom; on the slanted part you are bandwidth-limited and more FLOP/s buys nothing.

How. Compute \(I\) for your kernel, look up the ridge point, and compare. Implemented in tools/roofline.py.

Connects to. Tiling and fusion move you right; quantisation moves you right by shrinking \(Q\).

Production. The standard first question about any GPU kernel. Also the reason "we upgraded to a faster GPU and nothing improved" happens: if you were bandwidth-bound, you bought FLOP/s you cannot use.

Ridge point

What. \(I_{\text{ridge}} = P/B\), the arithmetic intensity at which a kernel stops being memory-bound and becomes compute-bound.

Why. It is the single number that tells you what "efficient" means on a given machine, and it varies enormously: 295 FLOP/byte on an H100, 153 on an A100, ~17 on a server CPU (numbers).

How. Note what the spread means: a kernel with \(I = 50\) is compute-bound on a CPU and badly memory-bound on an H100. The same code changes regime when you change hardware, which is why porting a kernel and keeping the same optimisation strategy so often disappoints.

Connects to. Roofline. In decode, batch size is intensity, so \(b^{*} = I_{\text{ridge}}\times\text{bytes}/2\) — batch 295 on an H100 at bf16, 148 at fp8.

Production. Quantising weights to fp8 halves the batch needed to saturate the multipliers. The real win from low precision at inference is smaller operands, not faster arithmetic.

Tail latency

What. The high percentiles — p95, p99, p99.9 — of a latency distribution, as opposed to the mean or median.

Why. The mean is the number that hides the bug. A system with a 1 ms mean and a 2 s p99 is broken for 1% of requests, and if a user action touches 100 such services, the majority of user actions hit a p99 event: \(1 - 0.99^{100} = 63.4\%\) (numbers).

How. Use nearest-rank percentiles so the reported value is an observation that actually occurred, and keep the raw samples — you cannot recover a distribution from a summary. Watch coordinated omission.

Connects to. Stragglers are the batch-processing version of the same maximum-over-N problem — see P06; hedged requests are one mitigation.

Production. Report p50/p95/p99 with a bootstrap interval, always. A mean latency in a report is a scorecard deduction in this track for exactly this reason.

Try it — nearest-rank, and why the mean lies:

def pct(samples, q):
    import math
    s=sorted(samples); rank=max(1, math.ceil(q/100*len(s)))
    return s[rank-1]                       # a value that ACTUALLY OCCURRED
lat=[1,1,1,2,2,3,3,5,9,400]                # ms
print("mean", sum(lat)/len(lat), " p50", pct(lat,50), " p99", pct(lat,99))
print("the mean (42.7) describes no request that happened")

mean 42.7  p50 2  p99 400
the mean (42.7) describes no request that happened

Memory and Hardware

Cache line

What. The unit of transfer between memory levels — 64 bytes on nearly all current hardware. You never load a byte; you load the line containing it.

Why. Spatial locality: programs that touch address \(x\) usually touch \(x+1\) soon. Amortising the fixed cost of a DRAM transaction over 64 bytes is nearly free if the prediction holds, and pure waste if it does not.

How. Consequences follow directly. A struct that straddles a line costs two fetches. An array-of-structs walk that reads one field wastes the rest of every line — hence structure-of-arrays layouts. Two threads writing different variables in the same line serialise, because coherence operates at line granularity: false sharing.

Connects to. Prefetching, tiling, false sharing.

Production. Padding a per-thread counter to 64 bytes is a one-line change that can give near-linear scaling where there was none.

Curse of dimensionality

What. In high-dimensional spaces, distances between random points concentrate: the ratio of the farthest to the nearest neighbour tends to 1.

Why it happens. Sum \(d\) independent coordinate differences. The mean grows like \(d\) while the standard deviation grows like \(\sqrt{d}\), so the relative spread shrinks as \(1/\sqrt{d}\). Every point drifts toward the same distance from every other.

How it bites. Once distances are nearly equal, "nearest" stops carrying information, partitioning schemes cannot prune (every cell is a candidate), and greedy descent has no gradient. k-d trees degenerate to full scans by around \(d \approx 20\) — far lower than most people expect.

Connects to. Relative contrast is the quantitative version. Intrinsic vs ambient dimension is the escape hatch: real embeddings concentrate on a low-dimensional manifold and behave far better than their \(d\) implies.

Production. The reason ANN libraries exist at all, and the reason benchmarks on synthetic uniform data mislead.

False sharing

What. Two threads write to distinct variables that happen to occupy the same cache line. No logical conflict, but the coherence protocol ping-pongs the line between cores and both threads stall.

Why it exists. Coherence is maintained per line, not per byte, because per-byte tracking metadata would cost more than the data.

How to see it. A parallel program whose throughput decreases with more threads, with no lock in sight. Fix by padding each thread's data to a full line, or by accumulating in a thread-local and merging once at the end.

Connects to. Cache line, atomics.

Production. A classic cause of "our 32-core box performs like a 4-core box". Also why per-CPU counters in kernels are padded.

Memory-level parallelism

What. The number of independent memory requests a core can have outstanding at once.

Why. Latency is fixed by physics; throughput is not. The only way to hide a 121 ns DRAM latency is to have many fetches in flight simultaneously.

How. Independent loads overlap; dependent loads cannot. This is why a pointer chase measures latency and an array scan measures bandwidth, and why the same DRAM delivers 0.53 GB/s to one and 57.5 GB/s to the other — a 108× spread on identical hardware (numbers).

Connects to. Little's Law gives the required concurrency; prefetching supplies it automatically for predictable patterns; GPUs supply it with thousands of threads.

Production. The reason linked lists lose to arrays far beyond what complexity analysis suggests, and the reason batching a graph traversal (process 8 nodes at once) can be several times faster than the obvious loop.

Prefetcher

What. Hardware that observes the access stream, detects a pattern, and issues loads before the program asks.

Why. To create memory-level parallelism automatically for the common case of sequential or constant-stride access.

How. Typical units detect sequential lines, constant strides, and sometimes simple strided patterns across pages. They cannot follow pointers, because the address is not computable until the previous load returns.

Connects to. This is precisely why a latency benchmark must use a random cycle: a fixed-stride chase is the easiest possible pattern to prefetch, and my first attempt at measuring DRAM latency reported 1.30 ns at 512 MB because of it (numbers).

Production. The reason sequential scans over 100 GB can outrun index lookups over 1 GB. "Big-O ignores the constant" understates it: the constant here varies by 100× depending on whether the prefetcher can help.

Systolic array

What. A grid of multiply-accumulate cells where operands flow rhythmically between neighbours rather than being fetched from a register file per operation.

Why. A CPU core is limited by operand delivery: every MAC needs values read from a register file with few ports. Adding multipliers does not help because they starve.

How. In a weight-stationary \(k \times k\) array, each cell holds one weight, activations flow horizontally, partial sums flow vertically. Per cycle you fetch \(O(k)\) values and perform \(k^2\) MACs — operand reuse \(O(k)\), achieved by wiring rather than caching, with no tags, misses, or replacement policy. At \(k=256\) and 700 MHz that is \(2\times65{,}536\times7\times10^8 = 91.75\) TOPS, matching TPUv1's reported 92.

Connects to. Arithmetic intensity — the array is a hardware solution to the same problem tiling solves in software.

Production. TPUs, Apple's AMX, and the tensor cores in modern GPUs. The cost is total inflexibility: no branches, no gather, one operation. Restriction buys efficiency — the same trade as MapReduce's programming model, in silicon.

Try it — operand reuse, and TPUv1 from two integers:

for k in (8, 64, 256):
    print(f"k={k:>4}: {k*k:>6} MACs/cycle from {2*k:>4} operands = {k/2:>5.1f}x reuse")
k, clock = 256, 700e6
print(f"TPUv1: 2*{k}^2*{clock/1e6:.0f}MHz = {2*k*k*clock/1e12:.2f} TOPS (reported 92)")

k=   8:     64 MACs/cycle from   16 operands =   4.0x reuse
k=  64:   4096 MACs/cycle from  128 operands =  32.0x reuse
k= 256:  65536 MACs/cycle from  512 operands = 128.0x reuse
TPUv1: 2*256^2*700MHz = 91.75 TOPS (reported 92)

Tiling (blocking)

What. Restructuring a loop nest so it operates on sub-blocks that fit in a cache level, instead of streaming whole arrays.

Why. To raise arithmetic intensity without changing the arithmetic. A naive matmul re-reads matrix \(B\) once per row of \(A\); a tiled one loads a block of \(B\) once and uses it for a whole block of \(A\).

How. Choose block \(B\) so three \(B \times B\) fp32 tiles fit in L1: \(3B^2 \times 4 \le \text{L1}\). On a 128 KB L1 that gives \(B \le 103\) — but the measured optimum is 32, because vector-register pressure and loop overhead bind before cache capacity does (numbers). Derive the bound, then measure; the gap is the lesson.

Connects to. Cache line, roofline. Multi-level tiling (register/L1/L2) is what real BLAS does.

Production. Measured progression on one laptop: naive 1.91 → loop-reordered 27.33 → blocked+vectorised 58.30 GFLOP/s, against Accelerate's 1,679. Note that loop reordering alone was 14.3× and blocking only paid once vectorisation was enabled.

Storage

Bloom filter

What. A probabilistic set membership structure that answers "definitely not present" or "possibly present", never producing a false negative.

Why. A point read for an absent key in an LSM must consult every run on disk. With 40 runs that is 40 random reads to answer "no". A few bits per key in RAM turns most of those into an in-memory rejection.

How. \(m\) bits, \(n\) keys, \(k\) hash functions. Insert sets \(k\) bits; query checks them. \(P(\text{bit still }0) \approx e^{-kn/m}\), so \(\text{fpr} \approx (1-e^{-kn/m})^k\). Minimising over \(k\) gives \(k_{\text{opt}} = (m/n)\ln 2\) and \(\text{fpr} = 0.6185^{m/n}\). At the optimum each bit is 1 with probability exactly ½ — the filter is at maximum entropy, which is the information-theoretic reason that is the optimum. In practice you compute one 128-bit hash and derive all \(k\) probes by Kirsch–Mitzenmacher double hashing.

Connects to. Read amplification, LSM tree. Cannot support range queries — it hashes keys, destroying order.

Production. 10 bits/key gives ~0.82% fpr with \(k=7\), costs 125 KB per 100k keys, and turns 40 disk reads into 0.33 — a 122× reduction (numbers). This is why 10 is the default everywhere. Monkey shows uniform allocation across levels is not optimal.

Compaction

What. Background merging of immutable sorted files into fewer, larger, non-overlapping ones.

Why. An LSM tree makes writes cheap by never updating in place, which means obsolete versions and tombstones accumulate. Without compaction, reads must consult ever more files and space grows without bound.

How. Two families. Size-tiered merges runs of similar size: each byte is rewritten about once per level, so write amplification ≈ \(L\), but up to \(T\) runs coexist per level so read amplification ≈ \(TL\) and space ≈ 2×. Leveled keeps each level as non-overlapping runs, \(T\)× larger than the one above: merging rewrites ~\(T\) bytes of target per byte of source, so write amplification ≈ \(TL\) but reads touch ~\(L\) files and space ≈ 1.1×.

Connects to. Amplification, RUM conjecture, write stall.

Production. The p99 during compaction is the number that matters and the one nobody reports. A steady-state p99 measured with no compaction running is a number that does not exist in production.

Kirsch–Mitzenmacher double hashing

What. Deriving \(k\) hash values from two: \(g_i(x) = h_1(x) + i\cdot h_2(x) \bmod m\).

Why. Computing \(k\) independent hashes is wasteful when \(k = 7\) or more.

How. The result is that this gives the same asymptotic false-positive rate as \(k\) independent hashes. So a Bloom lookup is one hash plus \(k\) array probes. Take a 128-bit digest, split into two 64-bit halves, and make \(h_2\) odd so it generates the full residue ring.

Connects to. Bloom filter.

Production. What every production Bloom filter does. Implemented in tools/bloom.py.

LSM tree

What. Log-structured merge tree: writes go to an in-memory sorted structure backed by a log; when it fills, it is flushed as an immutable sorted file; files are periodically merged.

Why. Because sequential writes are dramatically cheaper than random ones on every storage medium, and because immutability makes concurrency and crash-safety far simpler than in-place update.

How. Write path: append to WAL → insert into memtable → on threshold, flush to an SSTable → compact. Read path: memtable → immutable memtable → each on-disk run, newest first, with a Bloom filter and a sparse index per run to avoid touching most of them.

Connects to. B-tree is the in-place alternative; amplification is how you compare them.

Production. RocksDB (inside Kafka Streams and Flink), LevelDB's descendants (Cassandra, DynamoDB), and the segment-and-merge structure of every Lucene index and therefore of OpenSearch. You have operated LSM trees for years.

B-tree

What. A balanced search tree with high fanout, updated in place, where each node is a disk page.

Why. To keep the number of page reads for a lookup logarithmic with a very large base — fanout of hundreds means a billion keys sit three or four levels deep.

How. Contrast with LSM: a B-tree does a random write per update (write amplification ≈ 1 page per modified key, but random) and one read path per lookup (low read amplification). LSM converts random writes into sequential ones at the cost of reading more files later.

Connects to. RUM conjecture — B-trees and LSMs sit at different corners of the same triangle.

Production. PostgreSQL, MySQL/InnoDB, SQLite. The rule of thumb: B-trees for read-heavy and update-in-place workloads, LSM for write-heavy and append-mostly.

RUM conjecture

What. You cannot simultaneously optimise Read overhead, Update overhead, and Memory (space) overhead; improving one degrades at least one other.

Why it matters. It converts a sprawling design space into a single question: which one am I spending? Reading it takes ninety seconds; feeling it takes nine weeks of building an LSM.

How it generalises. The same shape appears everywhere in this journey: recall vs latency in ANN, consistency vs availability under partition, precision vs throughput in quantisation, completeness vs latency in watermarks. Once you recognise the shape, new systems become legible quickly.

Connects to. Amplification, compaction, CAP.

Sparse index

What. An index with one entry per block rather than per key: the first key of each block and its offset.

Why. A dense index over a billion keys does not fit in memory. A sparse one over 4 KB blocks with ~100 keys each is 100× smaller and still narrows a lookup to a single block, which you then scan.

How. Binary search the sparse index to find the block that could contain the key, read that one block, scan it. One disk read instead of a tree walk.

Connects to. LSM tree, SSTable. Block size is the tunable: a larger block means a smaller index and more wasted read per lookup.

Production. Every SSTable format. Learned indexes propose replacing the binary search with a model.

SSTable

What. Sorted String Table: an immutable file of key-value pairs in sorted order, plus a Bloom filter, a sparse index, block checksums, and a footer giving their offsets.

Why. Immutability makes it safe to read concurrently with no locking, cheap to cache, and trivially crash-consistent (a partially written file is discarded, never repaired). Sortedness makes range scans a merge and lookups a binary search.

How. Write: buffer sorted entries into blocks, CRC each block, append the filter and index, write the footer, fsync, then atomically rename into place — the rename is what makes the file appear all-at-once.

Connects to. LSM tree, compaction, atomic rename.

Tombstone

What. A marker recording that a key was deleted, written like any other entry rather than removing data in place.

Why. In an immutable-file design you cannot delete from a file that is already written and may be being read. The delete must be a write.

How. A read that encounters a tombstone as the newest version for a key returns "not found". The tombstone can only be physically dropped during a compaction that includes the bottom level — otherwise an older version in a lower level would resurface.

Connects to. Compaction, space amplification.

Production. In HNSW, deletion also uses tombstones because a node is referenced by its neighbours' adjacency lists and patching every in-edge would require a reverse index. Consequence: recall drifts down with churn, because tombstoned nodes occupy beam slots without producing results — effective efSearch falls to roughly \(ef \times (1 - \text{tombstone fraction})\).

Try it — what churn does to effective efSearch:

for frac in (0.0, 0.1, 0.3, 0.5):
    print(f"tombstone fraction {frac:.0%}: effective efSearch of 128 -> {128*(1-frac):.0f}")
print("deleted nodes occupy beam slots without producing results")

tombstone fraction 0%: effective efSearch of 128 -> 128
tombstone fraction 10%: effective efSearch of 128 -> 115
tombstone fraction 30%: effective efSearch of 128 -> 90
tombstone fraction 50%: effective efSearch of 128 -> 64
deleted nodes occupy beam slots without producing results

Write-ahead logging

What. Append the intended change to a sequential log and fsync it before modifying the main structure.

Why. Crash atomicity. After a crash, the log tells you what was intended; replay makes the state consistent. Without it, a crash mid-update leaves a structure that is neither the old nor the new version.

How. The rule is log before data. Records carry a checksum so a torn tail — a partial record at the end, which is normal after a crash, not corruption — is detected and replay stops there. Group commit batches many logical writes into one fsync to amortise its cost.

Connects to. fsync, ARIES, LSM tree, checkpointing.

Production. The fsync is the bottleneck: ~90 µs per durable 4 KB write on the reference machine, capping a fsync-per-write engine at ~10,900 writes/s regardless of everything else (numbers). Group commit is not an optimisation, it is the difference between 10⁴ and 10⁶ writes/s.

fsync

What. A system call that forces previously written data for a file out of the OS page cache and onto durable media, returning only when the device says it is safe.

Why. write() returning successfully guarantees nothing about durability — it has merely copied bytes into the page cache. Without fsync, a power loss loses them.

How. The cost is ~90 µs on the reference machine — ~743 DRAM round trips, three orders of magnitude above anything else in a write path. Note also that a failed fsync is treacherous: on some systems the error is reported once and the dirty pages are dropped, so a naive retry sees success and loses data.

Connects to. Write-ahead logging, atomic rename.

Production. The single number that sets the ceiling of every durable-write system.

Atomic rename

What. Using rename() to publish a fully-written temporary file under its final name, relying on rename being atomic within a filesystem.

Why. It converts "a file that might be half written" into "a file that either exists completely or does not exist", which is the only crash-consistency primitive most applications need.

How. Write to foo.tmp, fsync the file, rename to foo, fsync the directory (the step everyone forgets — without it the rename itself may not be durable).

Connects to. SSTable publication, MapReduce output commit, checkpointing.

Production. Same pattern in three projects here: P03's segment flush, P04's SSTable publication, P06's reduce-output commit. Make the state transition and the position advance atomic is one idea wearing three costumes.

Learned index

What. Replacing a sparse index's binary search with a model that predicts a key's position, plus a bounded correction search.

Why. A sorted array's cumulative distribution function is an index; if the CDF is smooth, a small model approximates it in far less space than explicit entries.

Connects to. Sparse index.

Production. Real but narrower than the original excitement suggested: gains depend heavily on key distribution and updates are awkward. Worth measuring, worth being honest about — a good extension for P04.

Monkey allocation

What. Allocating more Bloom filter bits per key to smaller (higher) LSM levels rather than the same number everywhere.

Why. A level's contribution to false-positive cost is independent of its size — one wasted read either way — but its memory cost scales with the number of keys it holds. Uniform allocation therefore over-spends on the huge bottom level.

Connects to. Bloom filter, compaction.

Production. A genuinely surprising result and one of the best hypothesis sources in P04: same total memory, measurably lower read amplification.

Write stall

What. Deliberately blocking or throttling incoming writes because compaction cannot keep up.

Why. Without it, an LSM under sustained overload accumulates compaction debt: runs pile up, read amplification climbs, compaction gets slower, and the system collapses non-gracefully. A stall trades latency for stability.

Connects to. Compaction, backpressure — the same idea at a different layer.

Production. The failure mode people skip testing. Finding your engine's breaking point and characterising how it breaks is worth more than another 10% of throughput.

ARIES

What. The canonical crash-recovery algorithm: write-ahead logging with log sequence numbers, three recovery phases (analysis, redo, undo), and support for fine-grained locking and partial rollback.

Why. It establishes the vocabulary — LSN, redo, undo, checkpoint, dirty page table — that every subsequent recovery design reuses.

How. Redo everything first (including uncommitted work) to restore the exact state at crash time, then undo the losers. Repeating history before undoing is the counterintuitive step that makes fine-grained locking recoverable.

Connects to. WAL, checkpointing.

Production. Read §1–3 for the concepts; you will not implement full ARIES in this journey, and you will use its vocabulary constantly.

Distributed Systems

Asynchronous model

What. A system model with no bound on message delay or relative processing speed.

Why. Because real networks have no such bound. Any protocol proved correct only under a synchrony assumption will fail exactly when that assumption breaks, which is during the incident.

How. In this model you cannot distinguish a crashed node from a slow one — the single asymmetry from which nearly everything else in distributed systems follows.

Connects to. FLP, failure detector, CAP.

CAP theorem

What. During a network partition, a system must choose between consistency (linearizability) and availability.

Why the usual statement is wrong. "Pick two of three" is a slogan, not the theorem. Partition tolerance is not a choice — partitions happen. The theorem is a statement about what you do when one occurs.

How to think about it properly. PACELC extends it usefully: if Partition, choose A or C; Else, choose Latency or Consistency. The else-branch is where systems spend 99.9% of their time and CAP says nothing about it.

Connects to. Linearizability, quorum.

Production. Dynamo chose AP with vector clocks and read repair; Spanner chose CP with bounded clocks. Both are correct; they answer different questions.

PACELC

What. If Partition, choose Availability or Consistency; Else, choose Latency or Consistency.

Why. Because the partition-free case is the common case and CAP ignores it. Every synchronous replication scheme pays latency for consistency all the time, not just during partitions.

Connects to. CAP, quorum, read strategies.

Failure detector

What. A component that reports which nodes it suspects have failed.

Why. FLP says deterministic async consensus is impossible; practical systems escape by adding a timing assumption, encapsulated in a detector that is allowed to be wrong.

How. It tells you nothing about the remote node — only about your own observations. Three worlds are consistent with a missed heartbeat: crashed, network dropped it, or alive-but-slow (GC pause, disk stall, CPU starvation). The timeout \(T\) is a trade with no correct value: too small gives false positives, spurious elections, and a feedback loop where load causes elections that cause load; too large gives an availability gap of \(T\) on every real crash. Phi-accrual replaces the binary with a suspicion level.

Connects to. Asynchronous model, Raft, split-brain.

Production. Tuning this is most of the operational work in a consensus deployment.

Phi-accrual failure detector

What. A detector that outputs a continuous suspicion level \(\varphi\) derived from the observed distribution of heartbeat inter-arrival times, rather than a boolean.

Why. A fixed timeout must be set for the worst case, so it over-waits in the common case. Modelling the distribution lets each consumer pick its own threshold.

How. Track inter-arrival times, fit a distribution (typically normal), and define \(\varphi = -\log_{10} P(\text{arrival later than now})\). A fast-failover component can act at \(\varphi = 3\); a conservative one waits for 8.

Connects to. Failure detector.

Production. Cassandra and Akka use it. The measurable win is a better false-positive/detection-time frontier under heavy-tailed delay.

FLP impossibility

What. In an asynchronous system with even one crash failure, no deterministic algorithm can guarantee consensus terminates.

Why it matters. It is not an engineering limitation to be out-engineered. It says that any consensus protocol must give up something: determinism (randomised protocols), termination guarantees (Paxos/Raft guarantee safety always, liveness only under partial synchrony), or the async model itself.

How practical systems escape. Raft is always safe and is live only when the network behaves well enough for a leader to hold an election. That distinction — safety unconditional, liveness conditional — is the design pattern.

Connects to. Asynchronous model, Raft, failure detector.

Quorum intersection

What. With \(N\) replicas and quorum size \(Q\), any two quorums intersect iff \(2Q > N\), i.e. \(Q \ge \lfloor N/2\rfloor + 1\).

Why. So a decision made by one quorum is visible to the next. If \(2Q \le N\), two disjoint quorums can each decide without seeing the other.

How this reframes split-brain. Split-brain is not an implementation bug; it is this inequality being violated — most often by an operator changing the replica count without thinking about the arithmetic.

Connects to. Raft, split-brain, CAP.

Production. With \(N=3\) and \(p=0.01\) independent failure, availability goes from 99.00% to 99.9702% — 3.65 days of downtime a year to 2.6 hours. The assumption doing all the work is independence, and correlated failure (same rack, same deploy, same poisoned request) collapses it.

Try it — the smallest safe quorum, brute-forced:

from itertools import combinations
for N in (3,5,6):
    for Q in range(1, N+1):
        disjoint = any(not (set(a)&set(b)) for a in combinations(range(N),Q)
                                            for b in combinations(range(N),Q))
        if not disjoint:
            print(f"N={N}: smallest safe quorum = {Q}  (2Q={2*Q} > N={N})"); break

N=3: smallest safe quorum = 2  (2Q=4 > N=3)
N=5: smallest safe quorum = 3  (2Q=6 > N=5)
N=6: smallest safe quorum = 4  (2Q=8 > N=6)

Linearizability

What. The strongest single-object consistency condition: every operation appears to take effect instantaneously at some point between its invocation and its response, and that order is consistent with real time.

Why. It is the model that matches intuition — a read sees the most recent write — and therefore the one whose absence surprises people.

How you check it. Record a history of invoke/return events with values, then search for a sequential ordering consistent with real-time constraints that satisfies the object spec (Wing–Gong, with pruning). The search is exponential in the worst case, so keep histories to a few thousand operations.

Connects to. Not the same as serializability (a multi-object transaction property with no real-time requirement) or sequential consistency (program order preserved, no real-time requirement). These three are routinely conflated; being precise about which one you provide is a distinguishing mark.

Production. P05's checker must report zero violations across ≥1,000 seeded fault runs, and finding one real bug in your own code with it is an exit criterion.

Raft

What. A leader-based consensus algorithm designed for understandability: a replicated log where one elected leader accepts writes and replicates them to followers.

Why. Paxos is correct and famously hard to implement correctly. Raft decomposes the problem into leader election, log replication, and safety, with an explicit strong-leader constraint that removes most of the concurrency.

How. Time is divided into terms, each with at most one leader. A candidate wins by receiving votes from a majority; a voter grants at most one vote per term and only to a candidate whose log is at least as up to date as its own. Entries commit once replicated to a majority. The subtle part — §5.4.2 — is that a leader may not commit an entry from a previous term by counting replicas; it must first commit an entry from its own term. The bug this prevents appears in roughly one in 10⁵ runs and destroys linearizability.

Connects to. FLP, quorum, failure detector, split-brain.

Production. etcd, Consul, CockroachDB, TiKV. Write a test that constructs the §5.4.2 interleaving deliberately — it will not appear by chance.

Split-brain

What. Two nodes simultaneously believing they are the authoritative leader, each accepting writes.

Why it happens. A partition, or a leader that was paused (GC, SIGSTOP) long enough to be replaced and then resumed still believing it leads.

How to prevent it. Quorum intersection plus fencing tokens: a monotonically increasing number issued with leadership, which downstream systems use to reject writes from a stale leader. Without fencing, a delayed write from an old leader can arrive after the new leader's and win.

Connects to. Quorum, Raft, asymmetric partition.

Asymmetric partition

What. A network fault where A can reach B but B cannot reach A.

Why it deserves its own entry. Symmetric partitions are easy to reason about and easy to test. Asymmetric ones break designs that symmetric tests pass: a leader that can send heartbeats but not receive votes keeps believing it leads while the cluster elects a successor.

Connects to. Split-brain, fault injection.

Production. Your fault injector must support it, and it is the injection most likely to find a real bug in your Raft.

Fault injection

What. Deliberately introducing failures — drops, delays, duplicates, reordering, partitions, pauses, corruption, clock skew — under test.

Why. Distributed bugs do not reproduce. Waiting for them in production is not a testing strategy.

How — and this is the part that matters. The injector must be deterministic and replayable: seeded, with a recorded schedule that reproduces the exact interleaving. A distributed bug you cannot replay is a distributed bug you cannot fix. This is why P05 builds the injector in milestones 1–2, before any distributed feature.

Connects to. Linearizability checking — injection finds the schedule, the checker recognises the violation.

Production. Jepsen is the public standard for this. The injector is also the most reusable artifact in Stage 3.

Idempotency

What. An operation that produces the same effect whether applied once or many times.

Why. Because exactly-once delivery is impossible and retries are therefore mandatory. If retries are safe, at-least-once delivery is sufficient.

How. For a KV store: client id + monotonic sequence number, with a server-side dedup table recording the last sequence and its response per client. The awkward part is that the table grows without bound and needs a session-expiry policy.

Connects to. Exactly-once, atomic rename.

ReadIndex

What. A way to serve a linearizable read from a Raft leader without appending an entry to the log: record the current commit index, confirm leadership with a heartbeat round to a majority, wait until the state machine has applied that index, then read.

Why. Reads are usually the majority of traffic and writing a log entry per read is wasteful. But reading from a leader that has silently been deposed returns stale data, so some confirmation is required.

How the three options compare. Read-from-leader-without-check is fastest and can be stale; ReadIndex costs one round trip and is linearizable; lease reads are local (no round trip) and linearizable only under a bounded clock-drift assumption.

Connects to. Linearizability, Raft.

Production. The latency/staleness/assumption frontier is a real design choice; state which point you chose and what it costs you.

Consistent hashing

What. Mapping keys and nodes onto the same ring so that adding or removing a node relocates only \(O(K/N)\) keys instead of nearly all of them.

Why. With plain hash(key) % N, changing \(N\) remaps almost every key — a full data reshuffle on every membership change.

How. Naive consistent hashing balances badly (random points on a ring produce uneven arcs), so each physical node is represented by many virtual nodes. More virtual nodes means better balance and a bigger routing table.

Connects to. Partitioning, rebalancing, and the AP design point of CAP.

Streaming

Event time vs processing time

What. Event time is when the thing happened, carried in the record. Processing time is when your system saw it.

Why it is the central distinction in streaming. They differ by an unbounded and variable amount, and choosing the wrong one produces silently wrong answers.

A concrete failure. A user reads an article at 23:58 on an offline phone that syncs at 00:07. Keyed on processing time, your "reads per day" attributes it to the wrong day — and over a month every daily number is wrong by the size of the offline-sync population. That is a systematic bias correlated with a user segment, not noise. Keyed on event time, it lands correctly — but now the 23:00–00:00 window cannot close at 00:00, because more events may arrive. You have traded a wrong answer for a late answer.

Connects to. Watermark is the dial that governs that trade.

Watermark

What. An assertion emitted at processing time \(t\): no event with event time ≤ \(W(t)\) will arrive after this point.

Why. Because with an unbounded input you must decide when to stop waiting before you can emit any result at all. A watermark is a formal admission that you are giving up on completeness in exchange for an answer.

How, and the three consequences. (1) The assertion can be wrong — an event below the current watermark is late, and you must have a policy: drop, fire again with a correction, or route to a side output. There is no free option. (2) It is a heuristic: perfect watermarks need a known maximum delay, which you do not have, so real systems use \(W(t) = \max(\text{observed event time}) - \delta\) with \(\delta\) a completeness/latency dial. (3) It must be the minimum across all inputs — and one idle partition therefore holds it back forever, stalling every window. That last failure is the most common operational problem in streaming, and its standard fix (idle-partition detection with a timeout) weakens the guarantee.

Connects to. Event time, windowing, late event.

Production. Sweep \(\delta\) and plot completeness against emission latency. That curve is the streaming analogue of ANN's recall/QPS curve, and it makes the same point: you choose a point on a frontier, and the only sin is not stating which.

Try it — the min rule, and the idle-partition stall:

partitions = {"p0": 1000, "p1": 995, "p2": 1002}   # max event time seen per partition
delay = 30
wm = min(partitions.values()) - delay
print(f"watermark = min({list(partitions.values())}) - {delay} = {wm}")
partitions["p1"] = None                              # p1 goes idle
alive = [v for v in partitions.values() if v is not None]
print(f"if p1 idles and you take min of the rest: {min(alive)-delay} (windows advance)")
print("if you keep waiting on p1: watermark frozen, EVERY window stalls")

watermark = min([1000, 995, 1002]) - 30 = 965
if p1 idles and you take min of the rest: 970 (windows advance)
if you keep waiting on p1: watermark frozen, EVERY window stalls

Windowing

What. Grouping unbounded events into bounded sets for aggregation.

Types and why they differ. Tumbling: fixed, non-overlapping — each event in one window. Sliding: fixed size, smaller step — each event in several windows, so state grows proportionally to size/step. Session: dynamic, closed by a gap of inactivity — and therefore the hardest, because a late event can bridge two existing sessions and force a merge plus a retraction of already-emitted results.

Connects to. Watermark decides when a window fires; state backend holds it until then.

Production. Session windows with no timeout are the classic unbounded-state leak: state accumulates for every key ever seen. Plot state size over time in every experiment.

Late event

What. An event arriving with an event time below the current watermark.

Why unavoidable. The watermark is a heuristic. Setting \(\delta\) large enough to eliminate late events means never emitting anything promptly.

How to handle. Three policies, all of which must be counted: drop (fast, loses data), late firing (emit a correction, requires downstream to handle updates), or side output (route elsewhere for reconciliation).

Connects to. Watermark, retractions.

Production. Every event must land in a window, fire late, or be explicitly counted as dropped — and the three must sum to the input. If they do not, you are losing data silently.

Checkpointing

What. Periodically persisting operator state together with the input positions that produced it, atomically.

Why the "together" is the whole point. Recovering means restoring state and rewinding input to the checkpointed offsets. If you persist state and offsets separately, you get duplicates or gaps depending on the order — the classic bug, and one worth introducing deliberately once to see it.

How. Stop-the-world is simplest: pause, snapshot, resume. Chandy–Lamport barrier snapshots interleave markers with the data stream so operators snapshot without a global pause, at the cost of alignment delay under backpressure (which is why unaligned checkpoints exist).

Connects to. Exactly-once, WAL, atomic rename — three projects, one idea: make the state transition and the position advance atomic.

Production. Checkpoint interval is a real optimum: too frequent costs steady-state throughput, too rare costs recovery time.

Exactly-once

What. Three different claims that get conflated, only two of which are achievable.

Why precision matters. "Exactly-once semantics" on a marketing page is meaningless without saying with respect to what, and under which sink assumptions.

Connects to. Idempotency, checkpointing.

Backpressure

What. Propagating "slow down" upstream when a downstream stage cannot keep up.

Why. Without it, an unbounded queue absorbs the mismatch until memory is exhausted. Backpressure converts an availability failure into a latency degradation, which is almost always the better trade.

How to test it. Not by measuring throughput — by measuring memory. Slow the sink 10× and verify that lag grows while memory stays bounded. A system that "handles" backpressure by buffering is not handling it.

Connects to. Write stall is the same idea in a storage engine; Little's Law predicts the queue.

Consumer lag

What. How far behind the head of the log a consumer is, in records and in seconds.

Why it is the primary operational metric. It is the leading indicator: lag grows before latency SLOs break, and it is the only metric that distinguishes "slow" from "stopped".

Connects to. Distinguish it from watermark lag (wall clock minus watermark), which measures how far behind event time you are and is often more informative for correctness.

State backend

What. Where a stateful operator keeps its keyed state — in memory, or in an embedded store.

Why. State outgrows memory, and it must survive operator restart, which means it must be checkpointable.

How. Every production system uses an LSM (RocksDB in Flink and Kafka Streams) because the access pattern is write-heavy keyed updates with range scans for windows — exactly what an LSM is good at.

Connects to. LSM tree, checkpointing.

Retrieval

HNSW

What. Hierarchical Navigable Small World: a stack of proximity graphs with exponentially decaying layer membership, searched greedily from a sparse top layer down to a dense layer 0.

Why the hierarchy. A single-layer NSW relies on accidental long-range edges formed by early insertions. The hierarchy makes long-range navigation structural rather than lucky: upper layers are sparse, so a few hops cover large distances.

How. Each point joins layers \(0..\ell\) with \(\ell = \lfloor -\ln(U(0,1))\cdot m_L \rfloor\) — a geometric distribution, so layer \(i\) holds ~\(1/e^i\) of the points. Search descends greedily with beam width 1 until a local minimum at each layer, then runs a beam search of width efSearch at layer 0. It is, structurally, a skip list in a metric space, and seeing that makes the layer distribution obvious.

The part everyone skips. Algorithm 4, the neighbour-selection heuristic. It is not an optimisation; it is a connectivity guarantee.

Connects to. Greedy graph search, relative contrast, efSearch.

Production. OpenSearch, Elasticsearch, pgvector, Qdrant, Weaviate, FAISS.

Navigable small world

What. A graph with high clustering and short path lengths, in which greedy routing by distance works.

Why it works. Kleinberg's result: greedy routing achieves \(O(\log^2 n)\) hops only when long-range links follow a specific distance distribution. Too few long links and you crawl locally; too many and greedy descent has no gradient.

How it arises here. In NSW, insertion order supplies it accidentally — early insertions happen into a nearly-empty graph so their edges are necessarily long.

Connects to. HNSW replaces the accident with structure.

Greedy graph search

What. From an entry point, repeatedly move to the neighbour closest to the query, maintaining a beam of the best ef candidates found.

Why approximate. The stopping rule — halt when the closest unexplored candidate is farther than the worst held result — is only sound if the graph is locally metric. It is false near a local minimum, and that is exactly where the missing recall goes.

How the beam helps. A wider beam explores more paths out of local minima, trading latency for recall — the efSearch knob.

Connects to. Memory-level parallelism: a graph walk is a dependent-load chain (~121 ns per hop), while brute force is a prefetchable scan. This is a second, independent reason graph search loses at small \(n\).

efSearch / efConstruction

What. Beam widths. efSearch at query time; efConstruction during insertion.

Why two. Build quality and query quality are separable: a well-built graph can be searched cheaply, but a badly-built one cannot be rescued by a wide query beam.

How to choose. Recall is strongly concave in efSearch — the first units buy a lot, the last buy fractions of a percent at linear latency cost. Fix the recall you need first and read the latency off the curve; never pick a latency and report whatever recall falls out.

Connects to. HNSW. Measured curves in numbers.

Neighbour-selection heuristic

What. HNSW's Algorithm 4: when pruning a node's edges, keep a candidate only if it is closer to the base node than to any already-selected neighbour.

Why it exists. Keeping simply the \(M\) nearest neighbours destroys long-range connectivity on clustered data. Measured: intra-cluster distance 0.521, inter-cluster 1.413, so a distance-based cap deletes every bridge, deterministically, leaving well-connected islands with no paths between them. Recall then plateaus at 0.967 while uniform data reaches 0.993 — and raising efSearch does not help because the search cannot spend its budget (840 distance computations at ef=256 versus uniform's 4,059).

How the heuristic fixes it. By preferring candidates in directions not already covered, it preserves exactly the bridges the naive rule deletes.

Connects to. HNSW. Full analysis in the worked notebook entry.

Production. The best available example of "an optimisation that is actually a correctness property."

Pre-filtering vs post-filtering

What. Two ways to combine a metadata predicate with vector search. Post-filter: retrieve top-\(K\), then discard non-matches. Pre-filter: restrict the graph walk to matching nodes.

Why neither is always right. Post-filtering needs \(K \ge k/s\) for selectivity \(s\) — at \(s = 10^{-4}\) that is efSearch ≥ 100,000, i.e. brute force with a worse constant. This is the production p99 cliff on narrow filters. Pre-filtering has no over-fetch problem but walks an induced subgraph you did not build, which may be disconnected — the same failure as the clustered ceiling, now caused by a query rather than by the data.

The third option people forget. Brute force over the filtered set is \(O(sn)\) — at \(s=10^{-4}\) on 1M vectors, 100 distance computations, exact and faster than either alternative.

Connects to. Neighbour-selection heuristic, selectivity.

Production. A query planner needs all three strategies and empirical crossovers.

Try it — the over-fetch cliff:

import math
for s in (0.1, 0.01, 0.001, 0.0001):
    K = math.ceil(10/s)
    print(f"selectivity {s:<8} -> need K={K:>7,} candidates "
          f"({K/1e6:.1%} of a 1M corpus)")
print("at 1e-4 you are running brute force with a worse constant")

selectivity 0.1      -> need K=    100 candidates (0.0% of a 1M corpus)
selectivity 0.01     -> need K=  1,000 candidates (0.1% of a 1M corpus)
selectivity 0.001    -> need K= 10,000 candidates (1.0% of a 1M corpus)
selectivity 0.0001   -> need K=100,000 candidates (10.0% of a 1M corpus)
at 1e-4 you are running brute force with a worse constant

Selectivity

What. The fraction of the corpus satisfying a predicate.

Why it drives everything. It decides which filtering strategy wins, and a wrong estimate is worse than no plan at all.

Connects to. Pre/post-filtering.

Production. Log estimated vs actual selectivity on every query from day one; planner mispredictions otherwise look like unexplained performance bugs.

Product quantization

What. Splitting a vector into \(m\) sub-vectors, k-means clustering each subspace, and storing only the centroid ids — so a 512-dim fp32 vector (2 KB) becomes \(m\) bytes.

Why. Memory, at billion scale, is the binding constraint. PQ trades recall for a 32–64× size reduction.

How. Distances are computed asymmetrically: the query stays full-precision, and a small lookup table of query-to-centroid distances per subspace turns distance computation into \(m\) table lookups and adds.

Connects to. The other major ANN family alongside graphs; the two compose (IVF-PQ, HNSW-PQ).

Machine-Learning Systems

Attention

What. Each position produces a query, a key, and a value. Scores are query·key over all positions, softmaxed into weights, and used to take a weighted sum of values: \(\text{softmax}(QK^\top/\sqrt{d_k} + M)V\).

Why it exists. It gives each position a content-addressed, position-invariant lookup over all other positions, while remaining parallel across positions (unlike recurrence) and constant in parameters as sequence length grows (unlike a fixed-window MLP).

How, and the \(\sqrt{d_k}\). With unit-variance components, \(q\cdot k\) is a sum of \(d_k\) independent terms, so its variance is \(d_k\) and typical magnitude \(\sqrt{d_k}\). At \(d_k = 64\) scores are ±8, the softmax saturates to near-one-hot, and its gradient vanishes. Dividing by \(\sqrt{d_k}\) restores unit variance and keeps the layer learning. This is a variance calculation, not a heuristic.

Connects to. Multi-head, causal mask, KV cache, FlashAttention.

Production. At \(T=1024\), attention is only 18.2% of a GPT-2-small layer's FLOPs; the quadratic term does not dominate until ~4096 (numbers).

Multi-head attention

What. Splitting \(d\) into \(H\) heads of size \(d/H\), attending independently, concatenating, and projecting.

Why. One head produces one attention distribution — it can attend to one thing. \(H\) heads give \(H\) distributions at identical total parameter and FLOP cost, because the concatenate-then-project arithmetic is the same. Representational diversity, free.

The limit. Each head sees a \(d/H\)-dimensional subspace, so below some head size heads become too small to be useful. Finding that floor empirically is a P01 experiment.

Connects to. Grouped-query attention shares K/V across heads to shrink the KV cache.

Causal mask

What. Setting \(M_{ij} = -\infty\) for \(j > i\) so position \(i\) cannot attend to the future.

Why. Autoregressive training computes the loss at every position in parallel; without the mask, position \(i\) sees its own target.

How — and the bug. The mask must be applied before the softmax, so masked positions receive exactly zero weight. Applied after, they receive small nonzero weight and the model trains fine while quietly cheating.

How to test it. Perturb token \(t{+}1\) and assert the logits at positions \(\le t\) are bit-identical. This catches masking-after-softmax, off-by-one, and accidental bidirectionality in one property test.

Production. Label leakage shows up as a validation loss below the entropy floor. A model trained on shuffled targets should converge to exactly \(\ln V\) nats — memorise that number for your vocabulary and you can spot leakage instantly.

RoPE

What. Rotary position embedding: rotate query and key vectors by an angle proportional to position, in \(d/2\) independent 2-D planes, with \(\theta_i = m/\text{base}^{2i/d}\).

Why it differs in kind. Learned and sinusoidal encodings add a position vector to the token embedding. RoPE rotates, and because a rotation by \(m\) composed with the inverse of a rotation by \(n\) is a rotation by \(m-n\), the query·key dot product depends only on \(m-n\). Attention becomes relative-position-aware with no explicit relative term.

How to verify. Measured: the dot product for offset 2 is identical to nine decimals at positions (5,3), (105,103), (7,5) and (1000,998); norms are preserved exactly because rotations are orthogonal. Write both as tests before implementing.

Connects to. Two incompatible conventions exist (interleaved pairs vs split halves); either is fine if consistent, and mixing them produces a model that trains but extrapolates badly.

KV cache

What. Caching the key and value tensors for all previous positions during autoregressive generation.

Why. Without it, generating token \(n\) recomputes attention over all \(n-1\) previous positions — making generation quadratic in output length instead of linear.

How much it costs. \(2 \times L \times T \times d \times \text{bytes}\) per sequence (2 for K and V, \(L\) layers). Derive it, then measure it; they must agree within 5%, and a gap means you have misunderstood what is cached.

Connects to. The cache is why decode is memory-bound: arithmetic intensity in decode equals batch size. GQA and PagedAttention both exist to shrink or manage it.

Grouped-query attention

What. Sharing one K/V head across a group of Q heads.

Why. The KV cache is often the binding memory constraint at long context. GQA divides it by the group size at a small quality cost.

Connects to. Multi-query attention is the extreme case (one K/V head for all queries).

PagedAttention

What. Managing KV cache memory in fixed-size blocks with an indirection table, rather than as one contiguous per-sequence allocation.

Why. Contiguous allocation must reserve for the maximum sequence length, wasting most of it, and fragments badly across sequences of different lengths.

How. Exactly virtual memory applied to the KV cache — a page table per sequence, blocks allocated on demand, and sharing of common prefixes across sequences by reference-counting blocks.

Connects to. Paging. A good example of an OS idea transplanted into an ML runtime, which is the kind of connection this journey exists to make visible.

FlashAttention

What. Computing exact attention without ever materialising the \(T \times T\) score matrix, by tiling and using an online-softmax normalisation.

Why. Memory, not FLOPs, is the wall. At \(T=8192\) the score matrix is 3.2 GB for a single batch element in fp32 (numbers).

How. Process query/key blocks in tiles that fit in SRAM, maintaining a running max and running sum so the softmax can be normalised incrementally and correctly. The arithmetic is unchanged; the DRAM traffic is what is optimised.

Connects to. Arithmetic intensity, tiling. It is the same idea as blocked matmul, applied to a different kernel.

Reverse-mode automatic differentiation

What. Computing gradients by traversing the operation graph backwards, propagating adjoints (vector-Jacobian products).

Why reverse and not forward. For \(f:\mathbb{R}^n\to\mathbb{R}^m\), forward mode costs \(O(n)\) passes (one per input) and reverse costs \(O(m)\) (one per output). Training has \(n \approx 10^7\text{–}10^{11}\) parameters and \(m = 1\) scalar loss. Reverse mode is ~5×10⁶ times cheaper for a 10M-parameter model — 20 ms versus 28 hours. That ratio is the entire reason deep learning is computationally feasible.

How, mechanically. It is bookkeeping, not calculus. Per-op derivative rules are trivial; the engineering is recording the graph, traversing in reverse topological order, and accumulating contributions when a value is used more than once. The price is memory: every intermediate must stay alive until its adjoint is consumed.

Connects to. Gradient checkpointing trades that memory back for recompute. For \(C = AB\): \(\bar A = \bar C B^\top\), \(\bar B = A^\top \bar C\) — a backward pass is about 2× a forward pass, which is where \(C \approx 6ND\) comes from.

The bug to know. Missing gradient accumulation makes gradients too small by an exact integer factor, which looks like a learning-rate problem and gets "fixed" by raising the learning rate.

Gradient checkpointing

What. Discarding intermediate activations during the forward pass and recomputing them during the backward pass.

Why. Reverse-mode memory grows with graph depth, and memory is what stops a model fitting.

How. Storing every \(\sqrt{n}\)-th activation and recomputing the rest gives \(O(\sqrt{n})\) memory for roughly one extra forward pass.

Connects to. Reverse-mode AD. The canonical time-for-space trade.

Operator fusion

What. Combining a chain of elementwise operations into a single kernel.

Why — and it is not FLOPs. For d = relu(a*b + c) over \(N\) fp32 elements: unfused, three kernels move \(32N\) bytes for \(3N\) FLOPs (\(I = 0.094\)); fused, one kernel moves \(16N\) bytes for the same \(3N\) FLOPs (\(I = 0.188\)). Exactly 2× the arithmetic intensity, and half the DRAM traffic, with identical arithmetic.

Connects to. Arithmetic intensity, roofline. Both versions are far below any ridge point, so both are memory-bound and halving bytes should halve time. Predict 2×, measure, explain the gap — usually launch overhead at small \(N\).

Production. What torch.compile, XLA and TVM spend most of their effort on.

Try it — identical FLOPs, half the bytes:

N=1_000_000
unfused = (12+12+8)*N          # 3 kernels, each reading and writing DRAM
fused   = 16*N                 # read a,b,c once; write d once
flops   = 3*N
print(f"unfused: {unfused/N:>2.0f} bytes/elem, I={flops/unfused:.3f} FLOP/byte")
print(f"fused:   {fused/N:>2.0f} bytes/elem, I={flops/fused:.3f} FLOP/byte  "
      f"({(flops/fused)/(flops/unfused):.0f}x)")
print("identical FLOPs. Fusion is a DATA MOVEMENT optimisation.")

unfused: 32 bytes/elem, I=0.094 FLOP/byte
fused:   16 bytes/elem, I=0.188 FLOP/byte  (2x)
identical FLOPs. Fusion is a DATA MOVEMENT optimisation.

Dispatch overhead

What. The fixed per-operation cost a framework pays before any arithmetic: Python call, argument parsing, dtype/device/layout resolution, kernel selection, output allocation.

Why it dominates more often than expected. Measured: numpy array addition costs 254.56 ns of fixed overhead plus 0.2551 ns per element, so overhead equals element work at ~998 elements. Below ~1,000 elements a numpy op is more dispatch than arithmetic; at \(n=1\) the ratio is 998×.

Connects to. Operator fusion and graph mode amortise it. The same phenomenon as P02's constant factor and P11's bytecode result — three domains, one lesson.

Production. Why small-batch inference is often framework-bound rather than compute-bound, and why CUDA graphs exist.

Try it — the crossover, from two measured constants:

fixed, per_elem = 254.56, 0.2551      # ns, measured for numpy elementwise add
print(f"crossover: {fixed/per_elem:.0f} elements")
for n in (1, 100, 1000, 100000):
    tot = fixed + n*per_elem
    print(f"n={n:>7}: {fixed/tot:>5.1%} of the time is dispatch")

crossover: 998 elements
n=      1: 99.9% of the time is dispatch
n=    100: 90.9% of the time is dispatch
n=   1000: 49.9% of the time is dispatch
n= 100000:  1.0% of the time is dispatch

Quantization

What. Representing weights and/or activations in fewer bits — fp16, bf16, fp8, int8.

Why — and the reason is not faster arithmetic. It shrinks \(Q\), the bytes moved, while leaving \(W\) unchanged, raising arithmetic intensity. fp8 halves the batch size needed to leave the memory-bound regime (295 → 148 on an H100).

How it breaks. Per-tensor scaling assumes a single dynamic range. Transformer activations have outlier channels whose range destroys the scale for everything else — the LLM.int8() result. Per-channel scaling is the fix.

Connects to. bf16 vs fp16, roofline.

bf16 vs fp16

What. Two 16-bit floats that are not interchangeable. bf16 is 1/8/7 (sign/exponent/ mantissa); fp16 is 1/5/10.

Why bf16 won for training. It keeps fp32's 8-bit exponent, so its range is identical to fp32 (max 3.4e38, min normal 1.2e-38) and values simply truncate. fp16's 5-bit exponent bottoms out at 6.1e-5, and gradients routinely underflow it — which is exactly why fp16 training needs loss scaling and bf16 does not. Range matters more than precision when values span orders of magnitude.

Connects to. Floating point.

Recommendation and Experimentation

Implicit feedback

What. Behavioural signals — clicks, dwell, purchases — as opposed to explicit ratings.

Why it is hard. A click is not a rating, and the absence of a click is not a negative. It may mean disliked, unseen, or seen-and-deferred, and you cannot tell which.

Connects to. Position bias, off-policy evaluation.

Position bias

What. The strongest predictor of a click is where the item was shown, not how good it was.

Why it matters. Training on raw clicks teaches the model to reproduce your old ranker's ordering, not user preference. It is a feedback loop that looks like learning.

How it is modelled. The examination hypothesis factorises \(P(\text{click}) = P(\text{examine} \mid \text{rank}) \times P(\text{attract} \mid \text{examine})\), with examination decaying as \(r^{-\gamma}\), \(\gamma \approx 0.7\text{–}1.0\) from eye-tracking. The separation is what makes a skip at rank 9 weak evidence of dislike — the user probably never looked.

Connects to. Off-policy evaluation, simulator design.

Production. In a simulator this single parameter dominates every conclusion: with strong position bias, any algorithm that puts something plausible in slot 1 looks good. Sweep it, and report which conclusions survive.

Off-policy evaluation

What. Estimating how a new policy would perform using logs generated by a different policy.

Why you cannot avoid it. Your logs record what the old system showed. Items never shown have no positives and score as failures, so any new algorithm surfacing them is penalised for it. No metric fixes this — the information is not in the data.

How. Inverse propensity scoring reweights each logged event by \(1/P(\text{shown})\), which is unbiased but high-variance (hence capping) and requires knowing the logging policy's probabilities.

Connects to. This is the admission that motivates P09: a simulator generates the counterfactual, trading a biased measurement for a model-dependent one.

NDCG

What. Discounted cumulative gain normalised by the ideal ordering: \(\text{DCG} = \sum_i g_i / \log_2(i+2)\), divided by the DCG of the best possible ranking.

Why normalise. Raw DCG is not comparable across queries with different numbers of relevant items.

The assumption nobody states. The \(\log_2(i+2)\) discount is a model of user examination probability. If your product is an infinite-scroll feed rather than ten blue links, that model is wrong — and you should say so before quoting the number.

Connects to. Position bias is the same idea from the data side.

Try it — computed by hand:

import math
def dcg(g): return sum(v/math.log2(i+2) for i,v in enumerate(g))
gains={7:3.0, 3:2.0, 11:2.0}
ranked=[7,42,3,88,11]
got=[gains.get(d,0.0) for d in ranked]
ideal=sorted(gains.values(), reverse=True)
print(f"DCG {dcg(got):.4f}  IDCG {dcg(ideal):.4f}  NDCG@5 {dcg(got)/dcg(ideal):.4f}")
print("the log2(i+2) discount MODELS user examination -- state k, and state the model")

DCG 4.7737  IDCG 5.2619  NDCG@5 0.9072
the log2(i+2) discount MODELS user examination -- state k, and state the model

Coverage, novelty, Gini

What. Catalogue-level metrics. Coverage = fraction of the catalogue shown to anyone. Novelty = mean self-information \(-\log_2 p(\text{item})\), in bits. Gini = concentration of exposure.

Why they are mandatory. Almost every accuracy metric can be improved by recommending popular items, because popular items are popular. At Zipf \(\alpha = 1.0\), the top 1% of items captures 53% of engagement — so a bestseller list beats a mediocre personalised model on NDCG while covering 1% of the catalogue.

How they interact. Measured: a bestseller list has coverage 0.005 and Gini 0.000 — Gini alone misses the failure entirely because the five items share exposure evenly. You need coverage and concentration.

Connects to. Calibration, diversity.

Production. Report the full suite for every configuration. A table with only NDCG is a rejected result in this track.

Try it — why the bestseller list is hard to beat:

n=10000
for a in (0.5, 1.0, 1.2):
    w=[1/r**a for r in range(1,n+1)]; t=sum(w)
    print(f"Zipf({a}): top 1% of items carry {sum(w[:n//100])/t:>5.1%} of engagement")
print("a bestseller list is a strong ACCURACY baseline. Report coverage too.")

Zipf(0.5): top 1% of items carry  9.4% of engagement
Zipf(1.0): top 1% of items carry 53.0% of engagement
Zipf(1.2): top 1% of items carry 75.1% of engagement
a bestseller list is a strong ACCURACY baseline. Report coverage too.

Maximal marginal relevance

What. Greedy diversity re-ranking: \(\arg\max_i [\lambda\,\text{rel}(i) - (1-\lambda)\max_{j\in S}\text{sim}(i,j)]\).

Why. Accuracy metrics cannot see "ten articles about the same story" — all ten are genuinely relevant. Diversity is invisible to relevance.

How. One parameter, one line, and it traces the whole accuracy/diversity frontier as \(\lambda\) sweeps.

Connects to. Intra-list diversity is the metric; MMR is the mechanism.

Calibration

What. Whether the topic mix of recommendations matches the topic mix of a user's history.

Why. Accuracy-optimal recommendations are systematically miscalibrated: if a user reads 70% sport and 30% politics, the accuracy-maximising list is 100% sport, because that is the higher-probability category. The user experiences this as narrowing.

Connects to. Coverage/novelty, filter bubbles.

Sample-ratio mismatch

What. The observed traffic split differing from the intended one by more than chance.

Why it invalidates rather than warns. It means assignment, logging, or filtering differs between arms — so the two populations are not comparable and no analysis of the metric is valid.

How to detect. χ² with 1 d.f.; alarm at χ² > 10.83 (p < 0.001). A 0.5% imbalance on 400k users gives χ² = 40 — a five-sigma event.

Connects to. Peeking, statistical power.

Production. Make it a gate: the analysis pipeline should refuse to report the primary metric when SRM fires. Enforce in code, not in policy.

Try it — the gate:

def chi2(obs, ratio=(0.5,0.5)):
    n=sum(obs); exp=[n*r/sum(ratio) for r in ratio]
    return sum((o-e)**2/e for o,e in zip(obs,exp))
for obs in ([200000,200000],[201000,199000],[202000,198000]):
    c=chi2(obs)
    print(f"{obs} -> chi2 {c:7.2f}  {'ALARM: arms not comparable' if c>10.83 else 'ok'}")

[200000, 200000] -> chi2    0.00  ok
[201000, 199000] -> chi2   10.00  ok
[202000, 198000] -> chi2   40.00  ALARM: arms not comparable

Statistical power

What. The probability of detecting an effect of a given size if it exists.

Why it comes first. \(n = 2(z_{1-\alpha/2}+z_{\text{power}})^2\sigma^2/\delta^2\), so halving the minimum detectable effect quadruples the sample. At σ=0.5: MDE 0.05 needs 1,570/arm, 0.025 needs 6,280, 0.0125 needs 25,117.

Connects to. Peeking, CUPED.

Production. Do this before building the variant. If your realistic effect is 0.5% and you get 20,000 users/week, the experiment needs a year and should not be run. This calculation kills more proposals than any other number in the track.

Try it — the calculation that kills experiments:

import math
za, zb = 1.959963984540054, 0.8416212335729143
n = lambda sd, mde: math.ceil(2*(za+zb)**2*sd**2/mde**2)
for mde in (0.05, 0.025, 0.0125):
    print(f"MDE {mde:<7} -> {n(0.5,mde):>7,} per arm")
print("halving the effect quadruples the sample. Compute this BEFORE building.")

MDE 0.05    ->   1,570 per arm
MDE 0.025   ->   6,280 per arm
MDE 0.0125  ->  25,117 per arm
halving the effect quadruples the sample. Compute this BEFORE building.

Peeking

What. Repeatedly testing significance as data accumulates and stopping at the first significant result.

Why it is so damaging. Each look is another chance to cross the threshold by chance. Simulated A/A tests: 5.12% false positives at 1 look, 14.47% at 5, 19.30% at 10, 32.80% at 50. Checking a dashboard daily for a fortnight turns a 5% error rate into ~25%.

How to fix it properly. Either fix the sample size in advance (pre-registration), or use a method designed for continuous monitoring — always-valid p-values, mSPRT, or alpha-spending — and pay the sample-size premium those require.

Connects to. Statistical power.

Production. The largest single source of false results in industrial experimentation. Build tooling that makes peeking impossible, not merely discouraged.

CUPED

What. Using pre-experiment data as a covariate to reduce metric variance.

Why. Variance, not effect size, usually decides how long an experiment runs. Removing predictable variance shortens it without changing the treatment.

How. \(Y_{\text{adj}} = Y - \theta(X - \bar X)\) where \(X\) is the same metric measured before the experiment and \(\theta\) is chosen to minimise variance.

Connects to. Statistical power, common random numbers — same goal, different setting.

Production. Typically 20–50% variance reduction, which translates directly into experiment-days saved.

Common random numbers

What. Using identical random seeds across experimental arms, varying only the treatment.

Why. A difference between arms then cannot be caused by a different population or a different content sample — the noise is shared and cancels.

How. Use independent per-component Generator streams derived from one root seed, so that adding a parameter to one component does not shift every subsequent draw in the others.

Connects to. CUPED, bootstrap.

Production. Routinely an order-of-magnitude variance reduction in simulation — the difference between needing 1,000 and 100,000 simulated users.

Languages and Runtimes

Tree-walking interpreter

What. Executing a program by recursively traversing its AST, dispatching on node type.

Why start here. It is the most direct mapping from grammar to semantics: each node type has an eval and the structure of the interpreter mirrors the structure of the language.

How it costs. Per node: a type dispatch, a pointer chase to children (a dependent-load chain), and a recursive call. The AST is scattered across the heap, so locality is poor.

Connects to. Bytecode VM is the standard next step — but see the measurement below, because the improvement is not automatic.

Bytecode VM

What. Compiling the AST to a flat instruction sequence executed by a dispatch loop.

Why it should be faster. Instructions are contiguous (good locality), dispatch is a switch on a small integer rather than a type test, and operand access is stack- or register-indexed rather than a pointer chase.

The measurement that complicates it. Both interpreters written in Python, identical semantics, verified identical results to fifteen significant figures: tree-walk 543.6 ns/statement, bytecode 821.3 ns/statement — the bytecode VM is 1.5× slower.

Why. Each source statement compiles to ~7 bytecode instructions, and in a host-interpreted VM each one costs a full host dispatch. The tree-walk pays one type check per AST node — fewer, larger steps. Bytecode's advantage was never "fewer operations"; it is "cheaper operations", and that only materialises when the dispatch loop compiles to machine code, where a switch becomes a computed goto of a few nanoseconds.

Connects to. Dispatch overhead — the identical lesson in a tensor framework. Threaded dispatch is the next optimisation.

Production. This is why P11 Phase II is written in Rust, and the reason is a measurement rather than an assumption.

Threaded dispatch

What. Replacing a switch in the interpreter loop with a computed goto that jumps directly from the end of one instruction's handler to the next.

Why. A single switch is one indirect branch that the predictor sees for every opcode, so it is essentially unpredictable. With direct threading each handler has its own branch site, and the predictor can learn opcode-pair correlations.

Connects to. Bytecode VM, branch prediction.

Production. CPython uses computed gotos where the compiler supports them; it is worth several percent to tens of percent depending on workload.

Closure

What. A function together with the environment it captured.

Why it needs care. The captured variable must outlive the scope that created it, and two closures over the same variable must see each other's writes.

How to test it. The counter test: makeCounter() returning an incrementing function. Two independent counters must yield 1,2 and 1. If the second returns 3, they share an environment they should not; if the first returns 1 twice, you copied instead of captured. Eight lines that distinguish three different implementations.

How it is implemented. In a tree-walk interpreter, an environment chain with parent pointers — which in Rust means Rc<RefCell<Environment>>, and understanding why (shared mutable ownership with runtime-checked borrowing is exactly what a mutable scope chain is) is the highest-value day of Rust learning in this journey. In a VM, upvalues: pointers into the stack while the frame lives, "closed" onto the heap when it exits.

Try it — the counter test:

def make_counter():
    i = 0
    def count():
        nonlocal i
        i += 1
        return i
    return count
c1, c2 = make_counter(), make_counter()
print(c1(), c1(), c2())   # 1 2 1
print("1 2 1 = correct. '1 2 3' means they share an environment they should not.")
print("'1 1 1' means you copied the value instead of capturing the variable.")

1 2 1
1 2 1 = correct. '1 2 3' means they share an environment they should not.
'1 1 1' means you copied the value instead of capturing the variable.

Mark-sweep garbage collection

What. Tracing from a root set, marking reachable objects, then sweeping unmarked ones.

Why tracing rather than reference counting. Reference counting cannot collect cycles, and cycles are common (a parent holding children that hold the parent).

How, and where the bugs are. The root set is everything reachable without going through another object: the VM stack, call frames, upvalues, globals, and any temporary live during a native call. Miss one root and you free a live object — a memory-corruption bug that manifests arbitrarily far from its cause. The defence is a stress mode that collects at every allocation, which converts it into an immediate, reproducible failure.

Connects to. Generational GC. The root-set traversal is structurally the same problem as a kernel's page reclamation.

Production. Measure the pause distribution — p50/p99/max against heap size. That plot is why your JVM or Go service has a p99 problem, and generating it yourself makes a whole class of production mystery legible.

Generational hypothesis

What. Most objects die young.

Why it enables an optimisation. If true, collecting only recently-allocated objects reclaims most garbage for a small fraction of the tracing work.

How. A nursery collected frequently, with survivors promoted to an older generation collected rarely. The complication is a write barrier to record old→young pointers, since a minor collection cannot trace the whole old generation.

Connects to. Mark-sweep.

Production. The hypothesis is testable: measure your own object lifetime distribution before assuming it holds for your workload.

Inline caching

What. Caching, at each call or property-access site, the type seen last time and the resolved target — so a repeat with the same type skips the lookup.

Why it works. Sites are overwhelmingly monomorphic in practice: a given line of code usually sees one type.

Connects to. The foundation of every fast dynamic-language runtime, and the gateway to JIT compilation.

Production. From Smalltalk-80 through V8. The highest-value real optimisation in a dynamic-language interpreter.

Pratt parsing

What. Top-down operator-precedence parsing: each token has a binding power, and the parser consumes operators while their power exceeds the current level.

Why. It handles precedence and associativity without a separate grammar rule per level, and extends to new operators trivially.

Connects to. Recursive descent for statements plus Pratt for expressions is the standard pairing, and nine pages of Pratt's 1973 paper is all you need.

Operating Systems

System call

What. A controlled transition from user mode to kernel mode to request a privileged service.

Why it costs. Mode switch, register save, argument validation, dispatch, and the cache/TLB effects afterwards.

How much. Measured 127.59 ns for a real trap (close(-1)) — ~140 L1 hits. Beware the trap: getpid() measures 1.23 ns because libc caches the pid, and clock_gettime measures 18 ns because it is served from a shared page. Both are commonly and wrongly cited as syscall costs (numbers).

Connects to. Context switch, vDSO.

Production. ~140 L1 hits per call is why unbuffered I/O is catastrophic and why io_uring, sendmmsg and vectored I/O exist. Reading about io_uring before measuring a syscall is reading a solution to a problem you have not felt.

vDSO / commpage

What. A page of kernel-provided code and data mapped read-only into every process, so some "system calls" execute entirely in user mode.

Why. clock_gettime is called often enough that a 128 ns trap would be a visible cost; at 18 ns it is merely annoying.

Connects to. System call. Also the reason a naive syscall benchmark using clock_gettime measures nothing.

Context switch

What. Saving one execution context and restoring another.

Why it costs far more than the register save. The direct cost — registers, stack pointer, page-table base — is small. The dominant cost is cache and TLB pollution: the incoming process evicts the outgoing one's working set, and the refill is paid later, off the switch's books.

How much. Measured ~1,676 ns best case (derived from a pipe round trip: \((3864 - 4\times128)/2\)) — ~13 syscalls, ~1,842 L1 hits. But a switch that evicts a 1 MB working set costs \(16{,}384 \times 121\,\text{ns} \approx 2\,\text{ms}\) of refill in the worst case — three orders of magnitude more, and entirely invisible to a ping-pong benchmark.

Connects to. Cache line, thread-pool sizing, why goroutines beat threads.

Production. This gap is why P12 sweeps working-set size rather than quoting a single number.

Virtual memory

What. Per-process address spaces mapped to physical frames through page tables, translated by hardware and cached in the TLB.

Why, and it is three reasons not one. (1) Isolation — a process cannot name another's memory. (2) Relocation — programs need not know where they physically live, enabling demand paging, copy-on-write, and shared libraries. (3) Overcommit — using more address space than physical RAM. Most explanations give only the third.

How. Multi-level page tables; a miss triggers a page fault, which the kernel services by allocating, loading, or killing. The TLB caches translations; a miss costs a page-table walk.

Connects to. Page replacement, PagedAttention is the same idea applied to a KV cache.

Page replacement

What. Choosing which page to evict when memory is full.

Why the choice matters. FIFO, LRU, and clock differ substantially in fault rate, and one of them has a genuinely counterintuitive property.

Bélády's anomaly. With FIFO, giving the system more memory can increase the fault rate. It is fully reproducible with a hand-constructed reference string, and it is the clearest possible demonstration that "more resources is better" is an assumption rather than a law. LRU is a stack algorithm and provably cannot exhibit it — showing both in one harness makes the point twice.

Connects to. Working set.

Production. P12's best single experiment.

Try it — Bélády's anomaly, in fifteen lines:

def faults(refs, frames, policy):
    mem, q, n = set(), [], 0
    for r in refs:
        if r in mem: 
            if policy=="lru": q.remove(r); q.append(r)
            continue
        n += 1
        if len(mem) == frames:
            victim = q.pop(0); mem.discard(victim)
        mem.add(r); q.append(r)
    return n
refs = [1,2,3,4,1,2,5,1,2,3,4,5]
for policy in ("fifo","lru"):
    row = [faults(refs, f, policy) for f in (3,4)]
    tag = "  <-- ANOMALY: more memory, MORE faults" if row[1] > row[0] else ""
    print(f"{policy.upper():5} 3 frames: {row[0]} faults   4 frames: {row[1]} faults{tag}")

FIFO  3 frames: 9 faults   4 frames: 10 faults  <-- ANOMALY: more memory, MORE faults
LRU   3 frames: 10 faults   4 frames: 8 faults

Working set

What. The set of pages a process has referenced in a recent time window.

Why it is the useful abstraction. It explains the knee in the fault-rate curve: while the working set fits in memory, faults are rare; once it does not, they explode. Scheduling and admission control both depend on it.

Connects to. Page replacement, context switch cost, cache line.

Copy-on-write

What. Sharing pages between parent and child after fork, marking them read-only, and copying only on first write.

Why. fork followed by exec would otherwise copy an entire address space that is immediately discarded.

Connects to. Virtual memory, PagedAttention prefix sharing is the same trick.

Priority inversion

What. A high-priority task blocked on a lock held by a low-priority task, which is itself preempted by a medium-priority task — so the high-priority task waits on the medium one indefinitely.

Why it is not a rare curiosity. It is a structural consequence of combining priorities with blocking locks, and it famously nearly ended the Mars Pathfinder mission.

How to fix. Priority inheritance (the holder temporarily inherits the waiter's priority) or priority ceilings.

Connects to. Scheduling, atomics.

Atomic operation

What. A read-modify-write that cannot be interleaved with another core's access to the same location.

Why memory ordering is separate. Atomicity guarantees the operation happens as a unit; ordering guarantees how it is visible relative to other operations. They are independent, and conflating them costs performance.

How much. Measured: relaxed atomic add 2.01 ns, seq_cst 3.97 ns — exactly 2×. The difference is a barrier preventing lazy store-buffer draining. An uncontended mutex is 6.38 ns, only 3.2× a relaxed atomic.

Connects to. False sharing is what makes contended atomics catastrophic.

Production. "Locks are slow" is wrong as stated — contended locks are slow. Once a waiter sleeps you pay a context switch (~1,676 ns), 260× the uncontended lock. And a statistics counter should be relaxed: you want the count, not an ordering guarantee.

References

• Drepper, U. What Every Programmer Should Know About Memory. Red Hat, 2007.
• Hennessy, J. L., Patterson, D. A. Computer Architecture: A Quantitative Approach, 6th ed. Morgan Kaufmann, 2017.
• Kleppmann, M. Designing Data-Intensive Applications. O'Reilly, 2017.
• Arpaci-Dusseau, R. H. & A. C. Operating Systems: Three Easy Pieces. 2018.
• Nystrom, R. Crafting Interpreters. Genever Benning, 2021.
• Akidau, T. et al. The Dataflow Model. VLDB 8(12), 2015.
• Ongaro, D., Ousterhout, J. In Search of an Understandable Consensus Algorithm. USENIX ATC 2014.
• Herlihy, M. P., Wing, J. M. Linearizability. ACM TOPLAS 12(3), 1990.
• Malkov, Y. A., Yashunin, D. A. HNSW. IEEE TPAMI 42(4), 2020.
• O'Neil, P. et al. The Log-Structured Merge-Tree. Acta Informatica 33, 1996.
• Athanassoulis, M. et al. The RUM Conjecture. EDBT 2016.
• Dayan, N., Athanassoulis, M., Idreos, S. Monkey. SIGMOD 2017.
• Vaswani, A. et al. Attention Is All You Need. NeurIPS 2017.
• Su, J. et al. RoFormer. arXiv:2104.09864, 2021.
• Dao, T. et al. FlashAttention. NeurIPS 2022.
• Baydin, A. G. et al. Automatic Differentiation in Machine Learning: a Survey. JMLR 18, 2018.
• Jouppi, N. P. et al. In-Datacenter Performance Analysis of a TPU. ISCA 2017.
• Kwon, W. et al. Efficient Memory Management for Large Language Model Serving with PagedAttention. SOSP 2023.
• Kohavi, R., Tang, D., Xu, Y. Trustworthy Online Controlled Experiments. Cambridge, 2020.
• Chuklin, A., Markov, I., de Rijke, M. Click Models for Web Search. 2015.
• Jones, R., Hosking, A., Moss, E. The Garbage Collection Handbook, 2nd ed. CRC, 2023.
• Bélády, L. A., Nelson, R. A., Shedler, G. S. An anomaly in space-time characteristics of certain programs running in a paging machine. CACM 12(6), 1969.