Session log

Newest first. One entry per topic, recording what was built, every number that was measured, and what was verified against which paper section. This is the detailed build record; PROGRESS.md has the status tables and PLAN.md has the curriculum.

Every performance figure quoted below is reproducible with ./verify.sh (see README.md); timings depend on hardware, everything else is seeded.

2026-08-08 — topics 34–43 — the last 40 guides, and the rules turned on for the whole book

Final batch of the rollout: topics 34 through 43, 40 guides, 9,163 lines of prose becoming 14,975. With these the ratchet reads 230 of 230, and .github/workflows/book.yml’s depth job is switched from --check (started files only) to --check --all, so a new guide that skips the rules now fails CI rather than being quietly exempt. Same contract and method as batches 1–3: one agent per topic on disjoint directories, tools/check-reading-depth.py printing N/N as the gate, two or three anchors per topic re-verified against the pin afterwards. Every spot-check confirmed the agent.

Three claims were the exact reverse of the source. Topic 43’s gray-failure guide sent readers to “§2 for the model, §1 and §3 for the examples”; §2 is the four case studies and §3 is the model (3.1 Terminology, 3.2 Differential observability, 3.3 Temporal evolution). The same guide collapsed §3.1’s observer and reactor into one entity — the observer gathers information, the reactor acts on it, and the gap between them is the whole paper. Topic 40’s bloodhound guide used Contains as its example of an edge kind excluded from pathfinding; at pin 1968388 it is element 60 of PathfindingRelationships (ad.go:1161), so the example is now GetChanges/GetChangesAll, which are in Relationships and ACLRelationships but genuinely not in pathfinding — because only their conjunction is dangerous, and post-processing synthesizes it into DCSync.

Two control laws were named after the wrong algorithm. CockroachDB’s KV slot adjuster is AIAD, not AIMD: total-- at kv_slot_adjuster.go:72, total++ at :91, and the code’s own comments say “additive decrease” and “additive increase”. Topic 35 carries genuine AIMD as well — DAGOR’s Algorithm 1, (1−α)·N down and +β·N up, §4.2.3 — which is precisely why the distinction had to be right. And topic 43’s Pivot Tracing 600 → 6 tuples/s headline belongs to process-level (intermediate) aggregation of emitted tuples (§4), not to the Table 3 rewrites, which reduce tuples packed into the baggage; four places in that topic’s README and two in its notes credited the wrong optimization, and one exercise went further and called it tuples crossing the join.

Three quotations did not survive being checked against the paper. Topic 35’s README quoted Bronson et al. as saying metastable failures “account for many of the largest outages at major web companies” — §1 says they “have caused widespread outages at large internet companies, lasting from minutes to hours”. Topic 39’s Fellegi-Sunter guide had the decision rule as “at or above T_μ → match, at or below T_λ → nonmatch”, which moves both thresholds into the automatic decisions; Eq. 2 is strict at both ends, and the clerical-review band includes its boundaries. Its controller definition dropped “(or in exceptional cases multiple entities)”, which is exactly the case where Heuristic 1 over-merges, and its safety argument said “private key” where the paper says “private signing key” — signing is what a multi-input spend requires and therefore what makes the heuristic sound.

Magnitudes. WeChat’s Chinese New Year peak is ≈10× the daily average, not 10× the daily peak (§2.3 gives both: peak hours ≈3× average). SLEUTH’s 250 bytes and 3 KB per edge belong to STINGER and NetworkX, the two main-memory-optimized stores, not to “a general graph database” — Neo4J and Titan are dismissed with no figure at all, so SLEUTH’s 10 bytes/edge is 25× better than the best main-memory store, which is the stronger claim. Pixie’s Algorithm 1 is eleven lines, not twenty. BloodHound’s PathfindingRelationships holds 64 kinds, not 63 (Relationships 88, ACLRelationships 30, PostProcessedRelationships 31, 104 graph.StringKind constants in total). And topic 43’s dapper guide asserted “113 dependency edges” twice, sourced from nothing — the README says 152 configured, and the claim the exercise rests on is edge recall = 1.000, which is count-agnostic.

Two papers contradict themselves, and the guides now say so rather than picking a side silently. Pixie prints C = max_{p∈P}|E(p)| in Eq. 1, which makes step allocation linear in degree, and then claims sub-linearity in the next sentence; sub-linearity needs C = max_p log|E(p)|, which is what this repo’s crate implements. The guide states both and works the example that settles it — degrees 1 and 10,000 with a 10,000-step budget give the low-degree pin 0 steps under the printed definition and ~5 under the intended one. Pixie also cites “lines 12-15 of Algorithm 2” where its printed algorithm has lines 9-14; the guide cites the printed lines and explains the discrepancy.

Anchors that had drifted. DataFusion retired EnforceDistribution into EnsureRequirements — the old top-level physical-optimizer/src/enforce_distribution.rs path does not resolve at the pin, the struct is at ensure_requirements/mod.rs:166 (:159 is inside its doc comment), and the hash RepartitionExec goes in at enforce_distribution.rs:1291 behind the should_add_hash_repartition guard at :1281. Four more repartition anchors pointed at doc comments rather than code: new_hash_partitioner is :679 not :667, new_round_robin_partitioner is :710 not :699, and the strength-reduced modulo is partition_reducer.partition_indices at :862 — :675 is prose. REPARTITION_RANDOM_STATE is SeededRandomState::with_seed(0) (mod.rs:592), not a plain RandomState, which is the difference between a reproducible partitioning and an irreproducible one. Splink’s expectation_maximisation.py:18 is an import line, not the E-step (:268); PostgresDialect is dialects.py:573 and the cited :674 is past the end of a 672-line file; graph_operations/connected_components.py does not exist. Six GraphRAG-SDK paths were missing a directory component, and vector_store.py:485 is fulltext_search — the query side — where the guide claimed index creation, which is :133. Topic 43’s three exercise stubs were missing the crate’s src/ component.

Numbers corrected in files outside the guides. FINDINGS.md row 42 read “35.3% hit-rate@50 with 92.2% overlap between users’ lists”; no run in this repo produced 35.3/92.2 — README’s lane-1 table, notes.md and this log all say 0.340 and 0.923 — and the ~0.92 figure is popularity_overlap, the overlap with the global bestseller list, not between users (that measure is personalization, 0.155). Corrected rather than annotated, on the same grounds as rows 23 and 32: it is not a stale measurement, it is a row that matches nothing. Topic 42’s README attributed the “classical random walks low degree nodes contribute less signal” quote to §3.1; it is §1. Topic 38’s 281-minute indexing figure is for the Podcast dataset at a 600-token chunk window — the 8k window is generation-side — and its notes cited /tmp/*.pdf as provenance. Topic 34’s PERF_TIMER_GUARD row and topic 36’s fabricated Twitter α=1.7 were fixed in batch 4’s earlier commits.

Arithmetic worked rather than asserted, per rule 3: DAGOR’s hidden capacity 300/(1+retries) = 150 QPS with the retry threshold at 280 QPS, 0.5^k shedding, and 30 s × 280 QPS = 8,400 queued; Fellegi-Sunter’s per-field weights giving 35.93 bits for the last/first/dob-agree, city-disagree, phone-agree pattern against 45.36 all-agree; the haircut’s 10× per-hop dilution reaching 0.1% in three hops, which is where topic 41’s 658 sub-0.1% UTXOs come from; BlockSci’s 8 B × 1.198e9 = 9.58 GB, i.e. 50.09 → 40.50 GB; Sherlock’s (2r)^k = ~80,000 states for r=200, k=2 against 3^200 ≈ 10^95; and dapper’s 40000/1024 = 39 traces with a rare path at ≈0.001.

Two provenance gaps are disclosed rather than papered over. Graefe’s SIGMOD-1990 Volcano paper is unreachable (ACM 403s; every mirror carries the TKDE-1994 edition, which has no §5 micro-benchmark table), so topic 37’s 25.73 µs/record and packet-size sweep are kept on the strength of a prior session’s verification, with every Volcano concept re-checked against TKDE and a note asking someone with ACM access to spot-check. Ammann/Wijesekera/Kaushik CCS’02 is not open-access anywhere reachable, so topic 40’s 5948/68364, 229 bits and O(|A|^2·|E|) are cross-corroborated against MulVAL CCS’06 §2 rather than re-read at source; no new Ammann number was introduced.

One rendering bug found by the final mdbook build, and it was corpus-wide. <details><summary>Answer</summary> opens a CommonMark HTML block that runs to the next blank line, so an answer starting on the very next line is raw HTML: backticks stay literal, and any bare <...> becomes a tag. Vec<u32> in topic 23’s roaring guide opened a <u32> element that swallowed the </details> after it. 118 blocks across 21 files were missing the blank line after </summary> and 58 more files were missing the one before </details>; both are normalised to the reference chapter’s shape. Four bare angle brackets in prose took backticks (Vec<u32>, and C<M>=A*B / C<!M>=A*B in topic 20’s GraphBLAS quotation, where <!M> was being read as the start of <!--).

Final verification, run with no agents live: 230 guide files present, check-reading-depth.py --check --all at 230/230 exit 0, mdbook build clean apart from the pre-existing search-index-size note, all 45 mermaid blocks in reading guides validated with @mermaid-js/mermaid-cli, all 317 SUMMARY links matching their file’s H1 byte-for-byte, and no broken relative .md link across 333 files.

2026-08-07 — topics 23–33 — the depth rules applied to 56 more guides, and four claims that were backwards

Third batch of the rollout: topics 23 through 33, 56 guides, 11,735 lines of prose becoming 19,282. Same contract and method as batches 1 and 2 — an > **In:** … **Out:** … on every ### Step N, a - [ ] self-test with collapsed answers under every ## Done when, a file-naming comment plus a real line gutter on every fenced block quoting source — with one agent per topic on disjoint directories, tools/check-reading-depth.py printing N/N as the gate, and two or three anchors per topic independently re-verified against the pin afterwards. Every spot-check confirmed the agent. Topics 31–33 also needed their prose ## Done when sections converted to checkbox form, which is why their growth factor is lower than batch 2’s. The ratchet moved 134 → 190 of 230.

Four guides taught the opposite of what their code does. gapbs’ PageRank was described as redistributing dangling-node rank; pr.cc divides by out_degree and moves on, and so does LAGr_PageRankGAP, whose stated purpose is bit-for-bit agreement with gapbs — only LAGr_PageRank redistributes. Delta-stepping’s relaxation was called race-free-by-design; sssp.cc:74-83 is a compare_and_swap retry loop that re-reads dist[wn.v] and loops. CockroachDB’s UpdateAndCheckMaxOffset was said to crash the node; it returns errUntrustworthyRemoteWallTimeErr and drops the message, while self-termination is a separate toleratedOffset field on the forward-clock-jump Fatalf path (hlc.go:49-51,396-404). And F1 Lightning was said to maintain its own version format so it cannot reuse a source engine’s; §3 says “every change committed to Lightning retains its original commit timestamp” — the timestamp is the shared currency, and what multi-engine support forces is the engine-neutral two-level schema of §4.6.

Three papers were being quoted with their own symbols swapped or fused. Paranjape’s motif definition is k-node, l-edge; topic 33’s guides had k and l reversed and then built an O(k²) complexity argument on top of the swap, where §4.1 says O(l²) contiguous subsequences for l = 3. Its triangle bound is O(TriEnum + m√τ) with τ the number of static triangles, not O(m√m). DBSP’s Theorem 3.4 reads (a×b)^Δ = a×b + z⁻¹(I(a))×b + a×z⁻¹(I(b)) — delayed integrals, which is what makes the cross-term vanish rather than appear — against the loose ΔA⋈I(B)+I(A)⋈ΔB+ΔA⋈ΔB the guides carried. Naiad’s progress protocol keeps two counts per pointstamp, an occurrence count and a precursor count, and the frontier is where the precursor count reaches zero (§2.3); the one-refcount story the guides told cannot explain why a notification is safe to deliver. Leiden’s abstract says “up to 25% of the communities are badly connected and up to 16% are disconnected”, which topic 24 had merged into a single 25%-disconnected figure in three places.

Nine section citations in one topic, and five declaration-instead-of-definition anchors in another. Naiad’s could-result-in and pointstamps are §2.3 not §3.2, loop timestamps §2.1, the distributed protocol §3.3 — whose formal proof is in the companion technical report, not the SOSP paper; Kafka’s sendfile path and 7-day retention are §3.1, coordination §3.2, at-least-once §3.3, throughput §5, and §4 is LinkedIn deployment rather than mechanics. In topic 26, bringetbitmap is brin.c:572 and :301 is the line in brinhandler that registers it; _bt_binsrch is nbtsearch.c:343 not :33; _bt_moveright :242 not :211; _bt_binsrch_posting :603 not :34; and BrinMemTuple is brin_tuple.h:44-56, where brin.c:157-170 is BrinBuildState, which merely holds one. Topic 23’s RediSearch walkthrough quoted a core.rs:229 add<E> calling E::delta and E::write that does not exist — the real path is add_record at core.rs:195-243 with E::encode at :243.

Numbers that came from the wrong table. Aurora’s 35× is Table 1’s transaction throughput ratio (27,378,000 against 780,000), not IOs per page change — a page write fans out as five log-record streams (Figure 2), and per-transaction IO goes the other way, 7.4 down to 0.95. BM25’s k1=1.2/b=0.75 are a Lucene convention, not the monograph’s defaults; §3.5 gives only ranges and §4.2 is “The Unified Model”. Block-Max WAND’s payload is §3 and its algorithm §5 — §4 is Related Work — and its speedups are Table 1’s 27.9 against 77.6 ms and Table 2’s 21,921 against 178,391 evaluated docIDs. HyPer’s 2 µs is the per-dirtied-page copy-on-write cost, not the cost of a snapshot regardless of database size, and the page-table trick is ICDE 2011 while HyPer’s version-chain MVCC is the 2015 paper. “Micro-partition, ~16 MB” is Snowflake product documentation; SIGMOD’16 says “large, immutable files” and states no size.

Three things were removed rather than softened, and one was kept after checking. Zobel & Moffat’s survey is paywalled and the only retrievable “PDF” is a student seminar deck, so topic 23’s reading map for it is now thematic with a note saying so. Shapiro’s catalog citations into the inaccessible RR-7506 tech report are re-anchored to the SSS’11 sections that carry the same constructions, and the two that exist only in the report or in related work are labelled. The “O’Rourke ’81” attribution for convex-hull segmentation appears in none of the learned-index papers in .cache/papers/ and is gone. Against that, AeonG’s “within one minute” — which looked like invented colour — is the paper’s own §1 Example 1 and stayed, attributed.

Rule 3 arithmetic that had to be worked rather than asserted. 15,645,988 / 5,428 is 2,882, not the 2,883 that appeared in topic 24’s guides, README and notes (5,428 × 2,883 = 15,648,924, which is not the count). Topic 26’s bloom rule-of-thumb in README had visibly given up mid-sentence — “every +4.8 bits/key HALVES… no — ×10 needs +4.8 bits?” — and is +1.44 bits/key to halve, +4.79 to cut tenfold, because log₁₀(1/FPR) = 0.209·b. Topic 23’s notes called the rare term’s idf 9.0, which is the adjacent column’s top-1 score; idf(83, 100000) under the repo’s own formula is ln(1197.6) = 7.09. Topic 25’s SpMM headline is 4.31 ms at 16.82 GFLOP/s against 5.65 ms dense, i.e. ~71% of dense throughput — 2·566,564·64 flops over 4.31 ms and 2·16384·64·64 over 5.65 ms — not the 81% derived from a superseded run.

Two FINDINGS.md rows were corrected against the only runs this repo records. Row 32 said writes fall from 10.5 M per 2 s to 94 with p99 334 ns → 2.7 s; README’s captured lane block, notes.md’s prediction table and this log’s own topic-32 entry all agree on 11,438,647 → 69 and 333 ns → 7.49 s, so no recorded run produces the row’s figures. Row 23 described “four two-term queries” when the first of the four is [t0 t1 t5], three terms. Where a topic’s notes.md baseline is simply an earlier run than its FINDINGS row — topics 23, 24, 25, 26 and 27 — the baseline heading is annotated to name FINDINGS as canonical, quote both sets, and tell the reader to re-run ./verify.sh NN rather than average two runs; the dated measurement itself is left intact.

Other out-of-scope fixes made while the guides were being rewritten. Topic 31’s README code map carried two stale anchors, yjsspan.rs:29 (which is id: DTRange; the states are :16-17) and local_writes/mod.rs:83-133 (a file 137 lines long that does not contain the trigger body; it is after_update.rs:65-123). Topic 28’s README used “micro-partition” twice. Topic 33’s notes claimed Q1–Q5 for two guides that have six questions. Topic 27’s README disagreed with itself thirty lines apart, carrying both the current lane (141.6 / 1111.0 / 31.2 ms) and a superseded one (97.2 / 894.3 / 24.7). Topic 26’s notes cited an ALEX §5.5 that does not exist; the robustness result is §6.2.6. Topic 25’s embed.rs doc comment asserted PyG’s Node2Vec.loss “is this exact expression” when node2vec.py:140,:142 share one embedding table where the exercise keeps two.

Gate: python3 tools/check-reading-depth.py topics/NN-*/ printed N/N for every one of the eleven topics before its commit, and one commit per topic keeps the batch reviewable in slices.

2026-08-06 — topics 13–22 — the depth rules applied to 60 more guides, and a benchmark that had been misreading itself

Second batch of the rollout: topics 13 through 22, 60 guides, 12,440 lines of prose becoming 40,955. Same contract as batch 1 — an > **In:** … **Out:** … on every step, a - [ ] self-test with collapsed answers under every ## Done when, a line gutter under a file-naming comment on every fenced block quoting source — and the same method: one agent per topic, ten to twelve at a time on disjoint directories, each forbidden from touching README.md, notes.md or experiments/, with tools/check-reading-depth.py printing N/N as the gate and two or three anchors per topic independently re-verified against the pin afterwards. Every spot-check confirmed the correction. The ratchet moves 74/230 → 134/230 and --check still exits 0. One measured headline changed — see below — and it changed because the old one was wrong, not because anything was re-run.

FINDINGS.md row 13 was misreading its own benchmark. The headline said supernode hops “reach fewer distinct nodes” than random hops. hop_bench.rs sets QUERIES = 10_000 random sources (:19) but takes exactly 100 supernodes (:61), and its report() (:21-27) divides elapsed time by the set size while printing the checksum raw. So 10,220,457 against 7,890,665 was comparing a sum over 10,000 queries with a sum over 100. Per query it is 1022 against 78,907 distinct nodes — 77× more, not fewer — and the real finding is the residual: 4.81 ns against 6.28 ns per distinct node, 1.31×, which is frontier cache pressure and re-walked overlap together. The lane counts distinct nodes, not edges traversed, so it cannot separate the two; the README gained an exercise that adds the edge counter and does. The row, both prose files and two guides were corrected, and “1000 sources” became 10,000 random plus 100 supernodes throughout.

Two claims were exactly backwards. raft-rs does not persist before it sends: raw_node.rs:555 reads rd.is_persisted_msg = raft.state != StateRole::Leader, with the comment above it citing Ongaro’s thesis §10.2.1 — “Leader can send messages immediately to make replication concurrently.” Only persisted_messages() waits. That makes the qdrant guide’s headline wrong too: it offered on_ready as “the fsync-before-send rule as real code”, when process_ready sends ready.messages() at consensus.rs:941 before appending entries (955-963) and HardState (965-973). It is legal because of the exemption, not an illustration of the rule. And Perceus does not build on borrow inference — Perceus §6 calls integrating selective borrowing future work that “would make certain programs no longer be garbage free”, while §5 says Perceus is “closely based on the reference counting algorithm in the Lean theorem prover”. Lean 4’s runtime is Counting Immutable Beans; the inheritance runs the other way.

Comments that no longer describe the code under them. SuiteSparse’s saxpy3 Gustavson/hash rule is not m/16 — that is a stale comment at GB_AxB_saxpy3.c:57-58; the shipped test is flmax >= cvlen/2 (slice_balanced.c:65) or hash_size >= cvlen/12 (:94), from which it follows that hash_size ≥ 2·flmax always and the resize path cannot execute. Gunrock’s BFS does not CAS: the CAS is commented out at bfs.hxx:116-122 and the live line is math::atomic::min(&distances[neighbor], iteration + 1) — and there is no parent[] array to CAS on. libcudf’s group-by does not spill to global atomics: compute_single_pass_aggs.cuh:95-122 sets a device atomic_flag, copies it to the host, synchronizes, and re-runs the whole aggregation in global memory. Z3 does not defer congruence repair the way egg does — merge fixes the table inline (euf_egraph.h:542, :551) and only queues the cascading merges. And rayon does not shatter work into thousands of deque pushes: it thief-splits (plumbing/mod.rs:246-284), so 8 threads produce 16 leaves, and with_min_len can only split less, because try_split is a conjunction (:331).

Tuning constants that were the wrong row of the right table. bitmap_switch is indexed by min(vlen, vdim) — GB_Global.c:181-189 defines eight thresholds and :486-497 selects by dimension — so every graph-sized matrix reads 0.40, and the “~4–8%, per-op” the guide taught was the row for dimensions 1 and 5–8. LAGraph’s direction-optimizing switch is not a disjunction: :248-251 disables the heuristic entirely while edges_unexplored < n, and the two remaining tests sit in mutually exclusive branches (:253-262, :263-278); its α=8, β1=8, β2=512 are not Beamer’s, whose SC’12 §VI-B reads “we select α = 14” and “We select β = 24”. SwissTable’s group is 8 control bytes on aarch64, not 16 — src/control/group/mod.rs:24-33 selects the NEON backend and neon.rs:16 is Group(uint8x8_t) — so every probe count derived from 16 is wrong on this host. CAGRA’s degree is not “fixed, e.g. 32”: cagra.hpp:151-153 defaults 64 with an intermediate of 128. PostgreSQL’s jit GUC boots to false (guc_parameters.dat:1451-1456), and the two thresholds the guides never mentioned are jit_inline_above_cost and jit_optimize_above_cost, both 500000. SQLite’s vdbe.c has 190 top-level case OP_ labels; the familiar 199 counts nine inner-switch cases and a comment. FoundationDB’s macro is now the function buggify() (flow/include/flow/Buggify.h:92-96), with 369 call sites under fdbserver/, 246 of them in ServerKnobs.cpp. qdrant’s ReplicaState has eleven variants (replica_set_state.rs:100-133), not three, and ActiveRead (:125) is readable but explicitly not a source of truth. libcudf’s join cooperative group is DEFAULT_JOIN_CG_SIZE = 2. And Faiss’s k limit is 1024 in §4.2 and 2048 in DeviceDefs.cuh:61-68.

Speedups quoted without the conditions that make them true. Crystal’s “~9× bandwidth (880 vs 100 GB/s)” is Table 2’s 880 against 53 GBps, i.e. 16.2×; its “PCIe ~16 GB/s” is §2.2’s “up to 16” against §5’s measured 12.8; “~16× on SSB” is §5.2’s 25×; “~9× on joins” is §4.3’s three regimes, 5.5× / 14.5× / 10.5×; and the guide taught that scan-plus-compact beats branch-per-thread when §4.2 found no measurable difference on the GPU. CAGRA’s “~10× build” is 2.2–27× against HNSW on a DGX A100 with the data already resident. egg’s 88× is a geometric mean over 32 tests of its own math and lambda suites, congruence closure only, against egg itself rebuilding after every merge — 21× end to end, with 8 of the 32 hitting the iteration limit. Beamer’s “3–8× fewer edge inspections” is unsourced; §VI-C measures 3.9× average, 2.4× minimum. Milvus’s DiskANN claim, Aurora’s and Socrates’ figures, and SIGMOD’15’s vpconflictd section (§5.1, not §5.2) were all re-pinned to the section that states them.

Numbers that were in no source at all, deleted. Faiss’s “~20× brute force over CPU”; the Mojo matmul GFLOPS ladder (~0.002 / 5 / 25 / 100 / 200+, “×2000”) whose four candidate URLs all 404; “~15 cycles per mispredict”; “~10–100× faster than LLVM” for cranelift; “~10–40 cycles contended” for atomic reference counting, replaced with Beans’s measured 52% geometric-mean and Perceus §4’s 5–59%; SuiteSparse’s “1000× skew means 7 cores idle”, replaced with the measured 8.5% imbalance at 4096-row slices against 23× at 16-row slices, reported as the negative result it is; and OLTP-Bench’s “~20 benchmarks”, which is 15 in §1 (BenchBase ships 19 sample configs, which is probably the source of the drift).

A clock speed was asserted and it was wrong. Two topic-17 guides said “~3.2 GHz”, from which they derived ~19 cycles per mispredict; the host is an Apple M5. They now derive a floor from this repo’s own naive dot rung — 10.89 GB/s at 8 bytes per pair with a 3-cycle FMA latency puts the core at ≥ 4.08 GHz, so a mispredict is ≲ 25 cycles — and all three guides cite the one derivation. In the same topic, nk_rsqrt_f32x4_neon_ (spatial/neon.h:56-60) does two Newton–Raphson rounds for ~23 bits; the three-round 8→16→32→~48 ladder the guide taught is the f64 helper at :105-115. And simsimd’s 39.7 GiB/s belongs to the manual-f32 variant the author measured and did not ship (dot/neon.h:159 says the shipped kernel upcasts to f64), on an M4, at n=4096, in GiB/s rather than the decimal GB/s notes.md uses.

Papers cited for things they do not say. Z3’s TACAS’08 names Nelson–Oppen only as the method Z3 avoids — “Z3 uses a new theory combination method that incrementally reconciles models maintained by each theory [5]” — and never uses the word “trigger” (that is Bjørner & de Moura, CADE 2007) or presents “CDCL”/“DPLL(T)” as its vocabulary. SuiteSparse’s TOMS’19 describes v2.3.3 and says it is “not yet multi-threaded” (§4.2.1, §7), so every parallel claim moved to Davis CSC’20. The AWS CACM’15 table was fabricated: the real figures are S3 804 + 645 lines of PlusCal, DynamoDB 939 of TLA+, EBS 102, the lock manager 223 + 318, against the old “~800 / ~1000 / ~450” — and the 35-step trace is DynamoDB’s, the author is Michael Deardeuff, and the small-scope hypothesis is Daniel Jackson’s, not in this paper. raft.tla asserts no properties at all: zero INVARIANT, PROPERTY or THEOREM, and Spec == Init /\ [][Next]_vars (:469) carries no fairness. TPC-C’s 45/43/4/4/4 is not a spec mandate — Clause 5.2.3 gives minimums and lists New-Order as “n/a”; the familiar split comes from the 23-card deck of 5.2.4.2, where New-Order is 43.478% — and the C-value rule constrains the delta, |C_load − C_run| ∈ [65..119] excluding 96 and 112. Boncz’s choke points were mislabelled: CP1.3 is Small Group-By Keys and it is Q1, CP1.4 is Q10, and CP3.3 exists precisely because dbgen’s date columns are correlated (L_RECEIPTDATE = L_SHIPDATE + [1..30]) — the guide had taught that they are independent. YCSB’s Table 2 has D as Latest, E as the only scan workload, and no F at all.

Rule 3 made the reader do the arithmetic. TPC-C’s 12.86 tpmC per warehouse derived from the 20.99 s cycle, matching Clause 4.1.3’s own Comment, and 10.75% of its transactions crossing a warehouse; Q1’s 98.593% selectivity against Q6’s 1.90%; ζ(10⁶, 0.99) = 15.39 giving a 6.50% hottest key and 50.2% in the top 1000, with Euler–Maclaurin reproducing go-ycsb’s hardcoded zetan = 26.46902820178302; Beans’s Figure 6 read as ratios — borrow inference is 2.4% (1.27 against a 1.24 base, and const_fold is 0.90, i.e. 10% faster without it) while reuse is 40% and atomics 52%, so reuse is worth roughly 16× borrow inference; TLA+ state spaces 6144 → 3072 → 1080 and raft.tla’s ≈1.9×10¹¹ from five of thirteen variables; AWS’s 303 lines of spec per bug on S3 against EBS’s 34; CAGRA’s 2324 B shared-memory footprint against an 8192 B budget; Faiss’s 1562:1 index-to-query traffic ratio; and Gunrock’s 410× thread-mapped imbalance on topic 13’s own graph.

Eleven defects outside the rollout’s remit, found by the guides and fixed separately. topics/14-vector-search/notes.md quoted a stale 185 QPS / 2.70 s against its own baseline’s 117 / 4.28. topics/16-testing-correctness/README.md had PQS’s pivot as one row per query (it is one per table), called PQS maintained (it is not), wrote TLP’s union as a set ∪ when it is a multiset ⊎, and dropped NoREC’s IS TRUE. topics/19-jit/README.md had the SQLite opcode count and the header path wrong and omitted that jit boots to false. topics/20-graphblas/README.md repeated four of the SuiteSparse corrections above; topics/17-simd/README.md had the 16-byte SwissTable group and pointed 8-byte compaction at simdjson’s 16-byte compress instead of compress_halves (arm64/simd.h:283-299); topics/18-gpu/README.md repeated the group-by spill claim. topics/15-replication-consensus/README.md’s mermaid state diagram used literal \n in two edge labels, which renders as text. topics/21-formal/README.md gave a distinct-state count in a total-state column and mis-attributed Lean’s runtime; its notes.md question worksheet still listed the superseded five-per-guide questions, two of which encoded the Nelson–Oppen and Perceus errors. And the Mojo type is struct SIMD[dtype: DType, size: Int] at 1.0.0b2, which needed a paired rename across the guide’s H1, its SUMMARY.md link, the topic README and PLAN.md:240.

Two tooling fixes fell out of the batch. The linter’s NAMED_FILE pattern omitted .hxx and .cxx, so Gunrock — which is entirely .hxx — could not be cited from a fenced block at all. And sixteen experiments/.gitignore files ignored Cargo.lock against this repo’s own rule that lockfiles are committed; fifteen of the sixteen lockfiles were force-added anyway, but topic 22’s was genuinely missing, so its measured lane could have resolved different dependency versions on a fresh clone than its notes were measured against.

Where a topic’s notes.md and FINDINGS.md disagree, that is now said out loud. Topics 17, 20 and 22 each have a notes.md baseline from an earlier run of the same lane than the row in FINDINGS.md — for topic 20, a 171× sweep and a 19.1 → 15.8 GB/s ladder against the row’s 175× and 20.7 → 12.3. No number was invented to reconcile them: each baseline heading now names FINDINGS.md as canonical and tells the reader to re-run ./verify.sh rather than average two runs.

Gate: tools/check-reading-depth.py prints N/N for every one of topics 13–22, the ratchet stands at 134/230, and --check exits 0. mdbook build and mermaid validation remain deferred to the end of the rollout, because concurrent agents race on book/.

2026-08-06 — topics 01–12 — the depth rules applied to 69 guides, and the claims that did not survive

The rules landed on 2026-08-05 with five guides implementing them and 225 not. This entry covers the first batch of the rollout: topics 1 through 12, 69 guides, 13,315 lines of prose becoming 48,139. Every step now carries an > **In:** … **Out:** … contract, every ## Done when is a - [ ] self-test with collapsed answers, and every fenced block quoting source carries a line gutter under a comment naming the file. No measurements were taken and no lane changed — FINDINGS.md and verify.sh are untouched throughout. The ratchet moves 5/230 → 74/230 and tools/check-reading-depth.py --check still exits 0.

Method, because it is the reason to trust the result. One agent per topic, twelve at a time on disjoint directories, each given the topic’s FINDINGS.md row and forbidden from touching README.md, notes.md, experiments/ or any other topic. Every file:line anchor was re-read through tools/pinned-source.py at the commit in resources/codebases.md; every paper claim was checked against the downloaded PDF and now cites the section, table or figure it came from. A claim that could not be located in its source was deleted rather than softened. The linter is the gate — a topic was not committed until it printed N/N — and two or three anchors per topic were independently re-verified afterwards against the pin. Every spot-check confirmed the correction.

The single most common defect was a section number. Topic 1’s four paper guides had them wrong in all four: Architecture of a Database System puts storage in §5 and transactions in §6, not the reverse, the parser is §4.1–4.2, and §2.1.3 describes a process pool rather than an event-driven server; Comer’s mechanics are §1, his cost analysis and Table I §2, and §4 is multiuser concurrency, not applications; the LSM paper’s multi-component design is §3.3; RUM’s triangle and Table 1 are §4. Topic 5’s ARIES guide put nested top actions at §10 (they are §9, and the example is file extension, Fig. 14 — index work is in ARIES/IM) and the catalog of recovery bugs at §3 (§10/§10.1). Topic 8’s SSI guide filed §4–§7 as engineering when §4 is the paper’s own new theory. Topic 9 cited “their §4.2 component breakdown” three times; it is §6.3 / Fig. 18, and §4.2 is garbage collection. Topic 10’s Join Order Benchmark map was off by one throughout, and topic 11’s Compiled and vectorized map was too.

The numbers that were not in the sources they were attributed to. Comer prints no millisecond figure anywhere, so “~30 ms per access, 600 ms per lookup” is gone, replaced by Table I’s access counts and Yao’s ln 2 ≈ 69% node utilisation. The LSM paper’s insert rate was overstated 10×: its own arithmetic is 50 arms at ~40 usable I/Os/s, i.e. ~20 index inserts per second per arm, not 200. X100’s interpretation overhead is 121×, not 45× — Table 1 reads 26.6 s against 0.22 s — and the same table’s hand-coded and X100 figures are 0.22 s and 0.50 s, not “~0.6 s for both”; “X100 runs at ~2 IPC” is not in the paper at all (§2’s IPC-2 is a scientific-computing reference point) and is replaced by Table 5’s 2.2 cycles per tuple against MySQL’s 49. Compiled and vectorized’s “TPC-H geometric mean within ~10–20%” does not exist; §4.1’s real range is Typer +74% on Q1 to Tectorwise +32% on Q9, with Q6 a tie. The Join Order Benchmark’s “median q-error reaches 10² to 10⁴ at 6 joins” inverts the paper’s finding — the medians stay near 1, the distribution widens, and §3.2’s actual numbers are 16%, 32% and 52% of PostgreSQL’s estimates wrong by 10× or more at 1, 2 and 3 joins. Aether’s 35× now carries its qualifiers (10 ms device, high skew, §3.2 Fig. 3), and the Bw-tree’s “1.5–4× with 10× less code” turned out to be two papers spliced: SIGMOD’18 §1 says 1.5–4.5×, §6.1 puts the 4× on ART, and the code-size claim is Leis et al. §3.2 with ICDE’13 §VI.A’s ~10,000 lines behind it.

Rule 6 — describe what the pinned code does, not what the technique usually does — caught the most interesting errors. LMDB does not fsync twice per commit: the meta file descriptor is opened O_WRONLY|MDB_DSYNC (mdb.c:5318), so the meta write is itself synchronous. SQLite’s “about 25% faster” comment is not a right-bias packing optimization leaving room for appends — btree.c:8730-8751 reassigns page numbers into ascending order for scan locality, the real packing bias is left-ward, and the block immediately after exists to undo it (“This adjustment is not optional”). Turso’s add_dirty() was described as the write-ahead rule visible in code; pager.rs:3418 writes a pre-image to the subjournal, for savepoint rollback — WAL frames are appended on the commit path. PostgreSQL’s XidInMVCCSnapshot does not binary-search xip[]; it calls pg_lfind32 (snapmgr.c:1902), a SIMD linear scan of 16 xids per iteration. RocksDB’s wait-for-graph deadlock detection is not the default — deadlock_detect defaults to false (transaction_db.h:304) and the real defence is a 1000 ms lock timeout. DataFusion’s optimizer fixpoint does not terminate on the Transformed flag (that is logging); termination is a HashSet<LogicalPlanSignature> (optimizer.rs:598-599). fjall does not fsync per policy — it does not fsync at all by default (PersistMode::Buffer, mod.rs:932). And LW_FLAG_RELEASE_OK does not exist at postgres 701f021: the flag at that bit is LW_FLAG_WAKE_IN_PROGRESS (lwlock.c:97) with inverted polarity.

Three claims were not just wrong but backwards. “Readers keep the cache line shared” — a shared LWLock acquire is a CAS on the state word (lwlock.c:807), so every reader writes the line too, which is exactly why topic 9’s counter table matters. “Waiters are served in arrival order” — postgres deliberately lets a new arrival barge past the queue (lwlock.c:1195-1205). And topic 5’s “the client was ACKed before any of this runs”: server.c:1958-1962 flushes the AOF before handleClientsWithPendingWrites, with a comment saying it is for appendfsync=always.

The unanchored fsync was topic 5’s worst defect — “an fsync costs ~1 ms” appeared at roughly eight sites across five guides, when this repo has measured that the phrase means nothing without a rung: write() 1.17 µs, macOS fsync 22.67 µs, F_FULLFSYNC 2.97 ms — 19.4× then 131×, 2542× end to end. The correction has teeth beyond wording: redis defines redis_fsync as fdatasync() on Linux and fcntl(fd, F_FULLFSYNC) on Apple (config.h:128-135), so appendfsync always on this machine pays the top rung. It is still not a throughput cap, because redis fsyncs once per event-loop iteration — 297 commands ride each 2.97 ms flush at an offered 100K/s — so it is a latency floor. everysec is a 1000 ms interval (aof.c:1348) with a 2000 ms write-postponement cap (:1196), not “~2 s”. The same rung question resolved topic 1’s db_bench claim: sync=true is write()+fdatasync() (options.h:2512-2515), the middle rung at 19.4×, not the 2542× of a full flush.

Folklore removed and replaced with measurement. “~100 cycles per coherence bounce” had no source; it is now this repo’s own 38.3 ns per transfer (the 40.54 − 2.28 ns difference in the false_sharing lane) alongside Leis et al. Table 4’s 5591 against 2187 cycles for the same ~370 instructions. Also deleted for want of a source: “PostgreSQL is ~1.5M lines of C”, “10,000 connections × 10 MB ≈ 100 GB”, a “1000× optimizer win” (now worked instead — 1M rows at 100 B in 8 KB pages is 12,346 pages scanned against 4, i.e. 3087×, with the division shown), DuckDB’s “a 20-way join is ~10^18 plans”, the mmap guide’s bare “~6 GB/s”, redis appendfsync no’s “typically ~30 s” (re-attributed to Linux’s vm.dirty_expire_centisecs = 3000), SSI’s “~7% overhead” (replaced by §8’s 10–20% CPU on SIBENCH, 5% on DBT-2++, RUBiS at 435/422/208 req/s), and “physiological logging”, ATT and DPT as ARIES vocabulary — none of the three appears in the paper.

Rule 3 turned assertions into arithmetic the reader runs. Comer’s fanout and height reproduced against topic 3’s own page-format table (which surfaced two byte figures wrong in the first pass: 83.1 MB is 87.2 MB, 20.6 GB is 22.14 GB); LSM write amplification K·(r+1) = 44× at T=10, K=4 and 87× total I/O; RUM’s Table 1 at N=1,080,000, B=40, T=10 giving LSM 4.2× worse reads and 3.6× better inserts; tidesdb’s bloom sizing from bloom_filter.c:207/223 — 9.59 bits per key, 7 hashes, 804 KB at p = 1%; turso’s table-interior fanout worked from real header constants to F = 453, height 3 at 1M rows, interiors 0.23% of the file; the clock-sweep hit rate for a 16 GB pool against 12 GB and 32 GB working sets with bgwriter’s 4 MB/s ceiling; the fraction of accesses that must fault to double topic 6’s mean given p50 42 ns against max 182 µs (2.88% / 0.95% / 0.023%); LeanStore’s 1/c ≈ 100 draws ≈ 22 µs and the coupon-collector count (14.5 M against 1.05 M); DuckDB’s 32,768-node purge floor and 6.3 MB (0.04%) queue; E[CAS attempts] = 1/(1−p) at ICDE’13’s p = 2e-4 (1.0002) against SIGMOD’18’s 10.79 aborts per insert (p = 0.915), a 5900× swing from workload alone; eight latch writes × 38.3 ns = 306 ns per lookup; and (1/p)·log_(1/p)(n) = 31.2 hops at both p = 1/2 and p = 1/4 — which is why RocksDB’s p = 1/4 with max height 12 (inlineskiplist.h:76-78) is chosen for memory, not hops.

Two long worked traces were added where a diagram had been doing the arguing. Topic 5’s ARIES guide gained a full recovery over an eight-record log: analysis rebuilding both tables row by row, redo showing all three of Fig. 11’s test levels and the RecLSN correction firing, undo as one interleaved backward sweep 80 → 70 → 50 → 30, then a second crash after CLR 100 demonstrating no double-undo, closing on §10.1’s LSN 10/20/30 selective-redo failure. Topic 8 gained a concrete visibility trace — snapshot xmin=100, xmax=110, xip=[103,107] against six tuple headers — and the two-doctors write-skew trace ending at T2’s SQLSTATE 40001 (predicate.c:4648).

Divergences between paper and code are now reported rather than smoothed over, which is the repo’s negative-result rule applied to prose. RocksDB’s mixgraph key-range model is a two-term exponential (db_bench_tool.cc:1708-1719) while FAST’20 §7.4 fits a two-term power model — a flagged row in a flag↔section table. SSI’s §5.2.1 says predicate checks run coarsest to finest; predicate.c:4287-4290 says the opposite and :4295/:4305/:4314 run tuple, then page, then relation. Topic 1 carries an explicit API-drift caveat because experiments/Cargo.toml asks for fjall = "2" (lockfile 2.11.2) while the pin table reads its source at 80cf6bc, which is 3.x, where Partition→Keyspace and Keyspace→Database; fixing the dependency would change the lane’s measurements, so the guide states the mismatch instead of pretending the names agree.

Six defects in files outside the rollout’s remit were found by the guides and fixed separately. topics/09-concurrency/README.md and notes.md called pad64 “the x86-default CachePadded” — crossbeam’s CachePadded is repr(align(128)) on x86-64 and aarch64 (cache_padded.rs:70-77, :87-94), and what the lane actually catches is the hand-written #[repr(align(64))] in false_sharing.rs:22, i.e. the reader’s assumption. topics/11-execution-models/notes.md’s prediction worksheet quoted a superseded 0.277 s / 180.7 M rows/s against its own Baseline block’s 0.484 s / 103.3 M, which also fixed the per-row cost from 5.5 ns to 9.7 ns. topics/04-lsm-deep-dive/README.md put the filter before the index in the SST diagram when src/table/writer/mod.rs:384 writes the index first. topics/07-networking-protocols/README.md described -P 64 as “~10× -P 1” when its own lane says 66.2× (44,088 → 2,919,728 ops/s). topics/12-columnar-analytics/README.md called the 19,047,619 GB/s hoisted loop “roughly 20 000×” the machine’s bandwidth; against FINDINGS row 12’s 150 GB/s it is ~127 000×. And PLAN.md:112 with resources/papers.md:21 filed the RocksDB experience paper as “TODS’21” when it is FAST ’21 / ACM Transactions on Storage 17(4).

Gate: tools/check-reading-depth.py prints N/N for every one of topics 00–12, and the ratchet stands at 74/230 with --check exiting 0. mdbook build and mermaid validation are deferred to the end of the rollout, because concurrent agents race on book/.

2026-08-05 — topic 00 — the depth rules become checkable, and all five topic-0 guides meet them

The ## Reading-guide depth rules landed with exactly one chapter implementing them. reading-criterion.md was rewritten to the eight rules; the other 229 guides in the repo were untouched, and nothing stopped them drifting further. This entry covers the two tools that make the rules mechanical and the four remaining topic-0 guides converted against them. No measurements were taken and no lane changed — FINDINGS.md and verify.sh are untouched. Every number added below is quoted from pinned source, from a paper section, or from a figure this repo had already measured.

tools/check-reading-depth.py checks the mechanical half of the rules: the section spine (matching the heading variants that already exist across the topics rather than demanding one wording), an > **In:** … **Out:** … blockquote on every ### Step N, a - [ ] checklist under ## Done when introduced by “Answer each before unfolding it.” with a collapsed <details> answer on every item, and a line-number gutter under a file-naming comment on every fenced block that quotes source. The snippet rule was calibrated against the reference chapter, not invented: the first draft demanded a strict file:line header and failed reading-criterion.md, whose actual convention is a header comment naming the file with the numbers in the gutter. A linter that fails the chapter it was modelled on is wrong about the format. --check is a ratchet — a guide that has started following the rules must follow all of them, and guides the rollout has not reached are reported without failing the build, so CI is green today and gets stricter with every topic converted. --all drops the exemption. Baseline at the start: 1/230 guides passed, with 1,496 steps missing an In/Out, 1,082 checklist items missing an answer and 195 snippets missing a gutter.

tools/pinned-source.py makes anchors checkable on a machine with no clones. Roughly 1,300 file:line anchors span ~85 upstream repos; cloning clickhouse, cockroach, tidb and postgres to check a line number is not practical. The tool resolves a repo through the pin table in resources/codebases.md, prefers a clone under $DLP_CLONES/~/repos when one exists, and otherwise fetches that exact commit into a gitignored .cache/ — the same guarantee a clone gives. Subcommands ref, list, show (real gutters), grep and check (assert an anchor still says what a guide claims). Paths resolve by suffix, so mdb.c finds libraries/liblmdb/mdb.c. A lint job was added to .github/workflows/book.yml, and both tools are documented in CONTRIBUTING.md and CLAUDE.md.

reading-redis-benchmark.md, 225 → 573 lines, every anchor re-verified at redis a176d1225 (Redis 8.6.2, confirmed in src/version.h:1). The pipelining claim was wrong: the old text said a 100 µs round trip and a 1 µs command cap an unpipelined connection near 10K ops/s and that -P 100 “lifts it near 1M”. Doing the division, -P 100 gives 100/(100 + 100×1) µs = 500,000 ops/s — a 50× lift and exactly half way to the 1M/s ceiling, which is the command time alone and needs -P 1000 (909,091 ops/s) to approach. Rule 2 forced a new step: one c->latency value forks into two HdrHistograms (config 99-100), a cumulative one that showLatencyReport (830-921) prints and a per-second one driving the live line, so the fork got its own numbered step. Two distortions the old text missed are now stated with anchors: the single measurement at 452 is recorded once per reply inside while(c->pending) (528-541), so a million requests at -P 100 fill the histogram from 10,000 clock readings; and CONFIG_LATENCY_HISTOGRAM_MAX_VALUE is 3,000,000 µs (line 50), so any sample above 3 s is recorded as 3 s. The coordinated-omission example is now arithmetic on stated assumptions: a 100 ms stall over a 1,000,000-request run gives a closed loop 50 samples (0.005%, first visible at the p99.995) against an open loop’s 10,000 (1%, p99.9 ≈ 90 ms). Function-end anchors were corrected — createClient 625-812, showLatencyReport 830-921, benchmark() 946-982 — because the old table cited bare start lines.

reading-fair-benchmarking.md, 226 → 556 lines, every figure checked against the DBTest’18 PDF with its section, figure or table. The chapter gained the numbers it had been describing without quoting: Figure 2’s Escher cycle is MariaDB 12.18 s > PostgreSQL 9.73 > SQLite 8.19 > MariaDB* 4.70 (TPC-H Q1, SF1), and the undisclosed DOUBLE-instead-of-DECIMAL schema choice — both legal under the TPC-H spec, §3.1 citing [2, sec. 1.3] — is worth 12.18/4.70 = 2.59×, more than any of the three pairwise gaps it manufactures (1.25×, 1.19×, 1.74×). Fig. 3a is 1.58 → 0.87 s (1.82×, MonetDB debug against release, the debug build scanning entire columns for sanity checks), Fig. 3b 0.47 → 0.27 s (1.74×, Postgres default against configured), Fig. 3c 0.87 → 0.03 s (29×, MonetDB against hand-written ‘TimDB’); compounding 3.2 with 3.3 gives 1.58/0.03 = 52.7× without a single false statement about arithmetic. The §3 preamble now has its own step, because every one of those timings is one i7-2600K at 3.40 GHz on one of eight threads, 16 GB, Fedora 26 / kernel 4.14, GCC 7.3.1, MariaDB 10.2.13 / MonetDB 11.27.13 / SQLite 3.20.1 / PostgreSQL 9.6.1, median with non-parametric quantile-based 95% CIs. Appendix A’s checklist is condensed into a table, and the “connections” section now cites this repo catching two of the paper’s pitfalls on itself: topic 12’s 19,047,619 GB/s hoisted loop (pitfall 3.8, now 24-57 GB/s on a 150 GB/s machine) and topic 6’s p50 42 ns against max 182 µs (a 4300× spread a mean would hide).

reading-rocksdb-db-bench.md, 248 → 938 lines, every anchor re-verified at rocksdb 7c80a5a. Six claims were wrong. The file is 10,367 lines, not “~10,400”/“10,000”. Benchmark::Run is at 3924; the old 4030 is the fillseq arm inside its dispatch, which runs to 4291. Stats::Merge is 2483-2495 with the bucket add at 2491; 2488 was the loop head. GenerateKeyFromInt does not write a zero-padded decimal key — it writes the integer as 8-byte big-endian binary (3830-3837, the shift at 3833) and pads the remainder with ASCII '0' (3840), which the file’s own comment says at 3797-3801; big-endianness is why fillseq produces sorted keys, so the correction earns its place in the argument. fillsync’s “3-4 orders of magnitude below fillseq” is the wrong rung: include/rocksdb/options.h:2512-2515 pins sync=true to write()+fdatasync(), which is topic 5’s middle rung at 19.4× (856,898 → 44,109 ops/s), not the 2,542× of F_FULLFSYNC; both are now stated with the condition that separates them. The unattributed “5-50× swing” was replaced with measured repo figures (durability 2,542×, space amp 0.45× vs 63.28×, leveled write amp ~20× at T=10/L=4). And mixgraph’s key-range model is a two-term exponential (a·e^(bx) + c·e^(dx), 1708-1719, InitiateExpDistribution 7944) while FAST’20 §7.4 fits a two-term power model — the guide had repeated the paper’s wording over the code’s behaviour, which is rule 6 exactly; the mismatch is now a flagged row in a flag↔section table. Pareto value sizes are the paper’s (§7.2, §7.4). Rule 3 turned the hand-waved “~37% duplicates” into the (1 − 1/n)^n → 1/e derivation run at the guide’s own --num=10000000: 6,321,206 distinct keys, 3,678,794 duplicate writes. Three new findings came out of the re-read: ResetLastOpTime (6531, comment at 6528-6529) deliberately excludes rate-limiter waits from the histogram; BGWriter excludes itself from the reported figure (8373); and every fill* except overwrite sets fresh_db and calls DestroyDB at 4304, so fillseq,fillrandom,readrandom silently throws the fillseq database away — which rewrites the old “the comma list is the methodology” step.

reading-drepper.md, 419 → 1377 lines, every number checked against the actual cpumemory.pdf. Eleven citations were wrong or unsupported. Fig. 3.4 is “Access Times for Random Writes” (§3.2), not the sequential-against-random figure the guide used it for — that is Fig. 3.15 (§3.3.2). Critical-word-first is §3.5.2 / Fig. 3.30 (measured at ~0.7%), not §3.3.2. MESI is §3.3.4 and false sharing §6.4.1, not §3.5. §6.2.1 is matrix multiplication and its blocking is cache-aware (SM derived from getconf LEVEL1_DCACHE_LINESIZE), not the cache-oblivious transpose the guide claimed. “Sequential against random ≈ 10×” understated it 5×: Figs. 3.10/3.15 give ~9 against 450+ cycles (50×), and this repo’s own ladder gives 2.24 against 104 ns/line (46×). The “~100 cycles per bounce” for cache-line ping-pong is not in the paper at all; it is replaced by Fig. 6.10’s 390% / 734% / 1,147% with Fig. 6.11’s caveat that there is no penalty within one quad-core package, alongside topic 9’s measured 17.8×. “~2K TLB entries” is unsourced; Drepper’s experimentally deduced figure is 64 entries (Fig. 3.12, the spike at 2¹³ B) for a 256 KB reach. And the L1/L2/L3/DRAM cycle ladder was presented as modern when ~14 is Drepper’s Pentium M number — the chapter now carries two labelled ladders, his cycles (§3.2: ≤1 / ~3 / ~14 / ~240) and this repo’s measured nanoseconds, plus a stated convention for which era a figure belongs to. Two steps were split under rule 2 (dependent loads from latency-against-bandwidth; MESI from false sharing), taking it from 8 steps to 10. Worked arithmetic was added throughout, including cache-line utilization U = (e × max(1, ⌊L/s⌋))/L on five strides (12.5% / 100% / 12.5% / 6.25% / 100%) and arithmetic intensity I = 0.125 against the roofline ridge I* = P/B = 0.28, with the peak-issue assumption labelled and sensitivity-checked.

Gate: tools/check-reading-depth.py topics/00-performance-toolbox/ prints 5/5, mdbook build is clean, all six mermaid blocks render through mermaid-cli 11.16.0, every <details> survives into the HTML (8 / 10 / 5 / 5 / 6), all relative links resolve, and every SUMMARY.md link title still matches its file’s H1. Repo-wide the ratchet now stands at 5/230, and --check exits 0.

2026-08-04 — topic 00 — reading-drepper: Steps 5–6 rewritten, plus a concept→profiler map

Reader feedback on reading-drepper.md: Step 5 unclear, Step 6’s diagram under-explained, and a general question — how do you identify these eight concepts in a program you did not write? No new measurements; every number below already existed in topic 0’s notes.md and is now cross-referenced from the concept that explains it.

Step 5 (dependent loads) rebuilt around one claim: the cost of a miss is not a property of the miss. It opens with what “dependent” means at the instruction level (chain[idx], node->next->next, a B-tree child pointer inside the parent you are still waiting for), then an ASCII timeline contrasting three overlapping misses (~105 ns total, ~35 ns apiece) with three serialized ones (~300 ns, 100 ns apiece), then the point people skip: latency-bound and bandwidth-bound are opposites. A chase moves one 128-byte line per ~104 ns ≈ 1.2 GB/s against the 24–57 GB/s a single core reaches on topic 12’s streaming scan — slow while the bus idles, so no layout fix touches it. The payoff is a two-row table putting this repo’s own numbers on both sides of the diagram: lookup_shootout hashmap at n=1e7, ~160 MB, 1024 independent probes → 9.3 ns; cache_ladder at 128 MB, a dependent chase → 104 ns. Same DRAM, same misses, 11× apart on overlap alone — which is the real explanation for why the hash table looked suspiciously flat at ten million keys. Then the three construction choices of cache_ladder are each justified separately (the dependency lives in the data so no compiler or core can speculate around it; Sattolo’s cyclic permutation both defeats the prefetcher and stops a short sub-cycle living in L1; the cursor carried across criterion iterations — with the original benchmark’s ~25 ns “DRAM” reading cited as the failure it prevents), and the readout stated plainly: with no arithmetic between loads, elapsed / steps is one access’s latency.

Step 6 (virtual memory) gained the five things the diagram assumed. Why a tree at all — a flat table for a 47-bit space at 16 KB pages is 2³³ × 8 B = 64 GB per process, so the radix tree is what buys sparsity, and depth is the price. A bit-field diagram of one x86-64 address (9/9/9/9 + 12-bit offset) showing why 9 bits — one table is one 4 KB page = 512 entries — with each arrow annotated as a real load whose address comes from the entry just fetched: Step 5’s chain, in silicon, before your access can issue. A three-column naming table (PML4/PDPT/PD/PT = PGD/PUD/PMD/PTE = L0–L3) since all three appear in the sources. The Apple Silicon variant derived rather than asserted: a 16 KB granule means 2048-entry tables = 11-bit indices, and 14 + 11 + 11 + 11 = 47, so the walk is three levels, not four — bigger pages buy a shorter walk and 4× the reach. And four reasons it isn’t catastrophic: hardware walks it (a page fault is the kernel, microseconds, a different event), the tables are ordinary cacheable memory, page-walk caches hold partial translations, and huge pages turn an L2/PMD entry into a block descriptor covering 2 MB (32 MB at a 16 KB granule). Closed against the measurement: cache_ladder’s tail 87 → 113 ns from 64 MB to 512 MB is +26 ns of walk once 32K pages overflow the TLB — not the +400 ns of a fully cold walk, not zero. “That +26 ns is this diagram, priced.”

New section: “Finding these concepts in a real program” — the general question, answered as a method. Three instruments in reach-for order, with the trap stated first: a sampling profiler attributes stall time to the waiting instruction, so memory-bound and compute-bound loops look identical, and this repo has the artifact to prove it (the lookup_shootout flamegraph’s 21% SipHash / ~79% inlined probe loop, which no amount of staring could split). Counters name the wall (perf stat on Linux; Instruments → CPU Counters on macOS, which has no perf; a Linux VM for perf c2c). A differential experiment — change one thing, re-measure — is the only portable instrument and the one this repo leans on, because a counter says a number is high while a differential proves fixing it would help. A mermaid funnel routes from IPC + branch-miss rate + achieved GB/s + dTLB misses to one of five verdicts (compute / branch / bandwidth / translation / latency-bound), with the last split — same flamegraph, opposite fixes — as its point. Then an eight-row table: concept → signature in a profile → Linux counter → the differential that proves it. The sharp ones: pad a stride by one line to separate conflict from capacity; feed the same loop sorted vs shuffled indices to price the prefetcher; run k interleaved cursors and watch per-step time fall ~k× to prove spare MLP (which is what batched lookup APIs collect); perf c2c plus a 128-byte pad to confirm false sharing. Closes on two habits — always pair a counter with a differential, and compute useful-bytes ÷ bytes-moved by hand, since that ratio needs no profiler and decides row-vs-column in topic 12.

Also: a fourth notes.md question (make lookup_shootout’s 1e7 probes dependent and report the new ns/probe — prove the MLP claim with the differential rather than by reasoning), two new Done when items (state the latency/bandwidth distinction and the one measurement that separates them; name counter and differential for all eight concepts), and a Tools block in the references. Verified: mdbook build clean, the new flowchart renders to a real SVG under headless Chrome with no syntax error, and every relative link on the rendered page resolves — including experiments/benches/cache_ladder.rs, which mdbook copies verbatim.

2026-08-03 — reading-guide depth rules, and reading-criterion.md rewritten against them

No new topic — a reading-guide format gap found by actually studying one of the guides, plus the reference chapter rebuilt to close it. Studying reading-criterion.md surfaced two failures that are properties of the format, not of that one chapter. First, borrowed jargon: the chapter said “a bootstrapped two-sample t-test” without ever defining a t-test, and did the same for p-value, quartile, IQR, MAD, standard error and null hypothesis — while CONTRIBUTING.md claims the steps “build each concept using only terms defined in earlier steps”. Second, unstated data lineage: Step 4’s regression never said whether it ran on the previous step’s data. It does not, and that turns out to be the most load-bearing fact in the pipeline.

Three factual defects found while verifying against the pinned crate (criterion 0.5.1). (1) The chapter claimed the fixed per-sample overhead “lands in the intercept, where it can’t contaminate the answer”. Slope::fit is Slope(dot(xs,ys) / dot(xs,xs)) (stats/bivariate/regression.rs:20) over a one-field struct Slope<A>(pub A) — ordinary least squares through the origin. There is no intercept; criterion does not set the overhead aside, it assumes it away. The honest argument is the xᵢ² weighting: the largest batches dominate the fit and those are exactly where a fixed overhead is proportionally smallest. Worked in the chapter on three points with a 500 ns overhead — mean-of-averages +30.6%, slope +21.4% (neither exact, which is the point), and on criterion’s real 100-batch ladder +0.0049% vs +0.0014%, ~3.5× less biased. (2) p_value was anchored to compare.rs:200; it is analysis/mod.rs:200, and the t-test itself is compare.rs:72. (3) The two regression gates were presented as an order-free pair; they are sequential — report.rs:598 tests p_value < significance_level first and prints No change in performance detected. without ever consulting gate 2, so each of the three printed verdicts identifies which gate produced it.

The chapter, rewritten 254 → 728 lines, 8 steps → 9. A new Step 4 exists only to name the fork: avg_times[i] = times[i]/iters[i] (mod.rs:124–129) feeds tukey, estimates() and the t-test, while the untouched (iters, times) pairs (mod.rs:140) feed regression() — so the headline time: comes from the slope while the regression verdict is judged on the mean, two different statistics of the same run. Every term is now defined in bold at first use before any argument leans on it, every step opens with an > **In:** … **Out:** … blockquote naming the step that produced its input, and every formula is run once on concrete numbers: the batch schedule (d = ceil(m_ns/met/(n(n+1)/2)) → d = 15, batches 15…1500, 75,750 iterations ≈ 5.3 s), the Tukey fences (q1 69.9, q3 70.4, IQR 0.5, inner 69.15/71.15, outer 68.40/71.90, one severe outlier), and Welch’s t on 3+3 samples (t = 3.95). Step 9 additionally explains how mixed::bootstrap (mixed.rs:11) pools both samples and re-splits them at random to manufacture the null hypothesis, and that p_value is a rank — min(hits, n−hits)/n × 2 (stats/mod.rs:63), two-tailed because criterion asks “different?”, not “slower?”.

Review feedback closed three more gaps, all of which became rules. (1) No length cap. The first draft’s “250–450 lines” target was the wrong lever — the rule is now “never trade a definition, a worked example or an answer for brevity; cut redundancy instead”, and the chapter finished at 728 lines because that is what nine steps with worked arithmetic cost. (2) Answers on the page. Each of the eight ## Done when items now carries its answer in a collapsed <details> block under “Answer each before unfolding it.”, so the checklist stays a self-test while the answer never requires leaving the page. (3) Line-anchored snippets. The Step 2 block was labelled routine.rs:257 — the fn signature — while quoting the loop body forty lines below it, so no line in the block matched the citation; every one of the nine blocks now carries per-line gutter numbers, marks elided ranges explicitly (three had silently closed gaps: lib.rs 1407/1408/1428, mixed.rs 27/28 then 66–70, analysis/mod.rs 124–129 then 140), and the prose names the line that carries the argument. The bootstrap block is pseudocode and is marked // ILLUSTRATION with a pointer to resamples.rs:37–41.

The rules the chapter now demonstrates are written into CLAUDE.md as a new ## Reading-guide depth section — define every term at first use, declare each step’s input and output, give every formula named symbols and one worked example, verify anchors against the pinned clone file and line, quote snippets with the line numbers they actually occupy and name the load-bearing one, describe what the code does rather than what the technique usually does, put a collapsed answer under every Done when item, and never trade any of those for brevity. CONTRIBUTING.md cross-references it (absolute URL, since CLAUDE.md is not a book chapter and mdbook rewrites relative .md links to .html). The remaining 229 guides are not rewritten here; this establishes the standard and the reference chapter.

Verified: every figure above recomputed rather than estimated, every file:line re-grepped against criterion 0.5.1 (two anchors were stale — routine.rs:154→158, report.rs:602→598), every elision range re-checked, all eight <details> render with their markdown parsed, mdbook build clean, and both mermaid diagrams parsed with the actual mermaid renderer.

2026-07-28 — repo-wide audit: verify.sh coverage, CI, and the conventions backfilled

Repo-wide review and fix pass — no new topics, but the measurement spine rebuilt. Prompted by a full audit of all 44 packages, 230 reading guides, 45 crates and the book build. What the audit found and what was done:

A benchmark reporting a physically impossible number. Topic 12’s scan_bench printed raw sum 800.0 MB 0.000 s **19047619.0 GB/s** — roughly 20,000x this machine’s memory bandwidth. Cause: time() took best-of-3 reps of a pure fold, so LLVM hoisted the whole computation out of the repetition loop and reps 2-3 timed nothing. Fixed with black_box on the input inside each timed closure, plus a MIN_CREDIBLE_SECS guard that prints n/a — below timer resolution instead of a figure. Now measures 24.4 / 50.0 / 57.0 GB/s across the three column shapes (150 GB/s peak on an M3 Pro, so one core gets ~a third of the bus). The spread across shapes is run-to-run noise on identical work — recorded as such, with the observed 24-76 GB/s range, rather than presented as a property of the data. This is topic 0’s first failure mode found in the repo’s own code, and it is written up in the topic and in README rather than quietly deleted.

verify.sh covered 10 of 44 topics while CLAUDE.md claimed it ran every measured lane. Root cause was mechanical, not missing work: topics 34-43 caught the exercise-lane panic and printed [stub — ...], while topics 2-31 let a todo!() abort the process (rc=101) after lane 1 had already printed. Ported a quiet stub_lane helper (suppresses the panic hook, catches, prints one marker line) through every bench binary; topics 17-18 already had it, 19-22 got a STUBBED flag plus one summary line, 23-30 only needed hook suppression. verify.sh now runs 42 bin lanes across 41 topics and exits 0 (plus 3 criterion lanes for topic 0 behind --criterion), with --list and --criterion added. Topic 8’s txn_bench was the one genuine FAIL the new coverage exposed (run_mvcc aborting the whole table); it now prints the global-lock baseline with — in the MVCC column.

Two topics had no measurable lane at all, so two were written. Topic 7’s only binary was the RESP server, which cannot run until the reader implements resp.rs; added loopback_bench, which measures the topic’s actual thesis with no protocol parsing and no store — 44,088 ops/s at P=1 rising to 12,321,414 at P=256, a 279.5x swing on identical zero-work requests, slightly super-linear against the 2/P syscall floor because larger writes amortize per-byte costs too, and per-request latency improving 22.68 → 0.08 µs (client-side batching is not the usual throughput-for-latency trade). Topic 3’s only bench interleaved the reader’s DiskBTree with redb and so died on the first stub; added btree_baseline, which prices the fanout arithmetic (8 B keys: 185 leaf cells, fanout 255, height 3 at 1e6; 32 B keys: 88 / 102 / 4 — a 2.5x interior-slot cost, which is what suffix truncation buys back) against redb measured warm. The height ladder is a negative result and the best thing in the topic: lookups climb 367 → 423 → 862 → 1101 ns from 1e4 to 4e6 keys while height stays pinned at 3 from 1e6 onward. Height sets how many pages a lookup touches; cache residency sets what a touch costs, and at 270 MB the pages are not resident. Long keys: 733 → 882 ns and 67.9 → 135.3 MB (1.20x slower, 1.99x bigger) — redb absorbs most of the predicted fanout loss, which is itself the finding.

CI never ran any Rust. The only workflow built the book, so the repo’s central claim had zero automated protection. Added verify.yml: ./verify.sh --summary plus a -D warnings build of all 45 crates, both cached against ../.dlp-target. Deliberately not cargo test (stub tests are the specification and must fail on a fresh clone) and deliberately not clippy (style lints across 44 independent teaching crates are a different argument). Fixed the 8 warning-emitting crates to make the gate pass: #[allow(dead_code, reason = "...")] on stub scaffolding, #[allow(unused_variables, reason = "used once the todo!() is implemented")] on stub bodies, and three genuine fixes (an unused import, two needless mut, one unused closure arg).

book/ was 7.2 GB, of which 6.7 GB was copied Rust build artifacts. src = "." in book.toml makes mdbook copy every non-markdown file under the root, and it honours neither .gitignore nor .mdbookignore (both tested — hidden directories are copied too), so all 44 target/ dirs were duplicated into the rendered book on every build. Fixed with a root .cargo/config.toml setting target-dir = "../.dlp-target", outside the clone — verified that cargo resolves a relative target-dir against the config file’s parent, and that nested crates inherit it. 16 GB reclaimed; book/ is now 49 MB, and the 44 crates share one dependency build instead of 44. Also un-ignored and committed 45 Cargo.lock files: for a repo whose pitch is that a seeded figure reproduces exactly, floating transitive versions were the one thing that could silently change a generator’s output.

The documented conventions held for topics 26-43 and not for the earlier ones. Backfilled, after correcting two things the audit had initially over-counted:

• notes.md measured baselines (12 added, plus topic 9 refreshed). The audit first flagged “empty measurement columns in topics 1-25”, which was wrong — those cells are the reader’s prediction worksheet and are supposed to be empty. The real gap was narrower: topics 1-8 and 10-15 had no record of the provided lane’s output at all. Added ## Baseline (provided lane, Apple M3 Pro, measured 2026-07-28) sections with the real numbers and the analysis, and for topics 4 and 10 (whose benches measure only the reader’s code) a ## No provided baseline in this topic — and why section giving the arithmetic or the external oracle to predict against instead. Topic 9’s recorded 636 ms / 59x false-sharing figures no longer reproduce — re-measured at 202.7 ms and 17.8x — so both are now recorded with an explicit note that contended-line throughput wants a range, not a point.
• Numbers-first README openers (20 added). Again narrower than first counted: 12 of topics 0-31 already opened with measured output under other names (“Our motivation numbers first”, “The problem, priced”). The 19 that did not, plus topic 12, now do.
• ## Done when in all 230 reading guides (114 added). The gap was a clean band: topics 13-30 had zero, topic 0 had zero, topic 1 had 4 of 8. Each new checklist is specific to its guide’s ### Step sections and questions, and where a topic has a lane the checklist ties back to the measured number.
• The pinned-commit convention was aspirational: exactly one guide had a real SHA, against a few thousand file:line anchors. Rather than scatter thousands of SHAs that would drift independently, added tools/pin-table.py and one authoritative table at the end of resources/codebases.md recording 84 reference clones with verified HEAD, date and origin, ranked by mention count. Only clones with a resolvable HEAD and origin are emitted — unverifiable ones are reported and left out rather than guessed at. The generated block is stripped from its own corpus so --check is idempotent.

New reader-facing pages. FINDINGS.md — the repo’s differentiator was four rows in README; it is now 42 rows, one measured headline per topic with the command that re-derives it, plus a section on how to read it (which rows contradict their own topic’s tidy story, which baselines refuse to be weak, and the observation that topics 34-43 are all measurement failures rather than system failures) and a mermaid dependency DAG with the three threads worth following deliberately (the fsync wall at 337 / 341 / 14 ms in topics 5, 15 and 28; skew in 13, 24, 36, 20; and the measurement itself lying in 0, 12, 34, 39-43).

Presentation fixes. PROGRESS.md showed 43 of 44 topics as todo, accurate for the study but read as “unbuilt” to anyone arriving from the book — split into Package (all 44 done) and Studied columns with the distinction stated up front. SESSION-LOG.md was 132 KB under a single heading: added 50 ## date — topic NN — title headings for anchors and sidebar navigation, verified byte-identical entry text afterwards. capstone/README.md claimed milestones map to topics 0-31 (PROGRESS has M0-M43) and did not say that M0 is the only one built — both fixed. drafts/ was untracked and unmentioned; committed with a README stating it is not part of the book and that the attribution rule still applies. CLAUDE.md and CONTRIBUTING.md updated so every rule they state is now actually true of the repo, including the new stub-degradation rule and the mdbook src = "." wrinkle.

Verified at the end: 42/42 lanes PASS, 0 FAIL, all 45 crates build under -D warnings, mdbook build clean with 66 mermaid blocks intact and 50 SESSION-LOG anchors, zero broken relative links across 292 markdown files, and SUMMARY.md titles matching every on-disk H1.

2026-07-27 — topic 43 — Network & IT-Ops Dependency Graphs

topic 43 Network & IT-Ops Dependency Graphs added (sixth and last of the graph use-case deep dives; the 38-43 expansion is complete): study guide (the alert storm and the gray failure measured — bench lane 1: synthetic microservice topology, 4 frontends / three tiers of 10-16-20 / 5 shared infra leaves, 152 configured edges of which 113 are reachable (an unreachable-configuration finding in itself), 40,000 requests, with a planted gray failure on the most-depended-on infra leaf — infra-0 is SLOW on 55% of calls rather than failing, and its callers time out, so the errors are manufactured one hop ABOVE the cause; result: 34 of 55 services alert above a 5% error rate and the broken service is not one of them, its own error rate is 0.0040 = exactly the baseline, it ranks 35 of 55 by failure count and 41 of 55 by error rate (error-rate ranking puts the three front ends at the top, i.e. it points at the services furthest from the fault), and all five infra leaves sit at 0.0040-0.0041, statistically indistinguishable — no sorting of any per-node column can separate them, which is the entire argument for the topic; lane 2 reference — localization across five topologies: per-node baselines average rank 36.4 (failure count) and 44.0 (error rate) with 0/5 top-3, while a correlation-weighted random walk and Sherlock’s Ferret at k=1 both average rank 1.0 with 5/5 top-1, at 22.8 ms and 21.4 ms respectively; the instructive ablation is that a backward-only walk ranks the cause 3rd instead of 1st because it drains into the leaves with no way to climb out, so the forward and self edges are what let the correlation weights bite; and the detail that makes the Ferret implementation work is clamping the fitted severity to [0,1] — a severity is a probability, so a candidate simply not on enough requests would need one above 1 to explain the observed rates; lane 3 reference — Dapper sampling as two different questions with two different answers: edge recall stays at 1.000 all the way down to 39 traces (1/1024) while rare-path recall collapses 1.000 → 0.249 → 0.062 → 0.016 → 0.004 → 0.001, and the mean latency stays within 5.8% while the p99 error reaches 25.6% — one sample, three verdicts depending on whether the question is aggregate, rare-event or tail, with the honest caveat stated in the output that edge recall saturates this early only because this topology has little path diversity), 4 reading guides (Dapper 2010 read in full — the ubiquity/continuous-monitoring requirements that force negligible overhead, trace trees with clock skew handled by causality rather than NTP, the three instrumentation points (thread-local context, the common control-flow library, the single RPC framework) that make transparency possible in <1000 lines of C++ and <800 of Java, out-of-band collection for two reasons (in-band trace data would dwarf sub-10 KB RPC responses and bias analyses; in-band assumes perfectly-nested RPCs, which middleware violates) at a cost of a bimodal p98 collection latency, the overhead budget (204 ns root span / 176 ns non-root / 9 ns unsampled annotation / 40 ns sampled / <0.3% of a core / 426 bytes per span / <0.01% of network traffic) and the 9-vs-40 ns split that made 70%-of-spans annotation coverage possible, Table 2’s sampling cost (+16.3% latency at 1/1, +2.12% at 1/16, −0.20% at 1/1024 inside experimental error), the “if a notable execution pattern surfaces once it will surface thousands of times” argument together with its own caveat about low-volume services, adaptive sampling by rate-per-unit-time with the probability recorded alongside the trace, and the critical detail that collection-time sampling hashes the trace id so whole traces are kept or dropped — a shredded trace has no causal structure left; Sherlock SIGCOMM’07 read in full — the (P_up, P_troubled, P_down) three-state model with troubled defined as “servers or links continue to function but users perceive poor performance” (differential observability, a decade early), the three node types (root-cause / observation / meta) and three meta-nodes with their truth tables — noisy-max (with probability 1−d the child escapes its parent’s state), selector (a noisy-max node would give a client a 25% chance of being up with both load-balanced servers down), failover — the always-troubled / always-down pseudo-causes at 0.001 (“1 in 1000 failures are caused by a component not in our model”) and router-path edges at 0.9999 as explicitly-priced model error, the O(3ⁿ) → O(n) propagation reduction for noisy-max nodes, and Ferret: 3^r assignment vectors cut to at most (2r)^k by Observation 3.1 (“it is very likely that at any point in time only a few root-cause nodes are troubled or down”, error “vanishingly small for k = 4 onwards”) plus two orders of magnitude from Observation 3.2, scored by fitting two Gaussians (200 ms vs 2 s) to historical response times with a null-hypothesis significance test, over a dependency graph discovered from packet co-occurrence within a 10 ms dependency interval discounted at (10ms)/I; Pivot Tracing SOSP’15 read in full as the database paper hiding in an operations topic — the two failures of ordinary monitoring (“one size does not fit all”, with the Apache issue-tracker evidence and HBase’s “all users pay the 10% overhead”; and crossing boundaries), the query language and the happened-before join Q1 ⋈ Q2 over Lamport’s →, the five advice primitives OBSERVE/UNPACK/FILTER/PACK/EMIT woven at runtime with no jumps or recursion and guaranteed termination, baggage as a per-request tuple container propagated across thread/process/machine boundaries so joins evaluate in situ rather than centrally (Magpie’s strategy is Figure 6a), and Table 3’s rewrite rules pushing projection, selection and aggregation down to the source tracepoints for a 600 → 6 tuples/s reduction — predicate pushdown and join placement, in a tracing system; Huang et al. HotOS’17 Gray Failure — the observer/app/ground-truth model and the four-cell table whose fourth cell is differential observability, why every redundancy mechanism is inert under it (they are all keyed on the observer’s view), three structural reasons detection is hard, and the escalation argument that makes a gray failure the trigger of a topic-35 metastable failure), experiments crate opsgraph-experiments (services.rs PROVIDED — the topology generator, the gray-failure workload with slow-dependency-plus-caller-timeout propagation, traces carrying paths/edges/latency, both per-node baselines, the symptom correlation, and participation = P(service on path | entry frontend), which is the deliberately weak observable Ferret must work from; rca.rs stub — random_walk_rca with three edge types and sherlock_single_fault; sampling.rs stub — whole-trace sample, edge_recall, rare_path_recall; 4 provided tests pass, 9 fix the contract for the stubs, including that a gray failure must not trip its own alert, that all infra error rates stay within 0.01 of each other, that the walk beats both baselines and a backward-only walk is strictly worse, that the ranking is stable across five seeds, and that sampling keeps whole traces), and capstone M43 (trace ingest as an incrementally-maintained dependency graph with sketched edge weights, both localization procedures over the topic-18 CSR, and a happened-before join operator in the query engine with Pivot Tracing’s pushdown rewrites — deliverable numbers include top-1 accuracy under sampling, the question the whole topic converges on and which none of the four papers answers). Cross-topic threads worked: 38/42 (personalized PageRank a third time, same justification), 34 (this is topic 34 at cluster scale), 37 (fan-out arithmetic explains the storm; hedging works where failure detection does not), 35 (gray failure as trigger, retry storm as sustaining loop), 10 (Pivot Tracing’s Table 3 is an optimizer), 26 (edge weights must be sketches — the p99 row is why), 40 (the same graph question with the arrows reversed), 27 (trace ingest is a stream, the dependency graph a materialized view over it), 21 (Sherlock’s model is tuned, not verified).

2026-07-27 — topic 42 — Recommendations & Social Graphs

topic 42 Recommendations & Social Graphs added (fifth of the six graph use-case deep dives): study guide (the popularity trap measured — bench lane 1: synthetic bipartite interaction graph, 3000 users x 6000 items, 30 communities, Zipf(1.1) popularity tail, 60,000 training edges and 6,000 held-out engagements; the bestseller list gets hit-rate@50 = 0.340 with a personalization score of only 0.155 (and that only because each user’s own items are filtered out — everybody is handed the same list), while Pixie’s unmodified Algorithm 1 reaches 0.403 but 45% of every returned list is the bestseller list again, because an unbiased walk’s stationary distribution goes as degree — Pixie’s own complaint from §3.1, “low degree nodes with fewer edges contribute less signal … smaller boards are more likely to produce highly relevant recommendations”; lane 2 reference — the Pixie ablation over 300 users x 8 query pins x 30,000 steps: going from one query pin to eight with sub-linear step allocation takes hit rate 0.403 → 0.823 (the biggest single win, and the least clever idea), early stopping runs in 35% of the steps at 2.2× the speed keeping 0.793 top-50 overlap with hit rate unchanged — almost exactly the paper’s “84% overlap at a third of the runtime” — and the multi-hit booster shows NO gain at all, 0.823 unboosted vs 0.803 boosted at one interest per user and 0.563 vs 0.547 at three, which is the more instructive result: the arithmetic is right (the unit test pins (√2+√2)²=8 against a single-source 4) but the generator does not contain Equation 3’s premise, since it draws its held-out item from the same distribution as the training items, so a published trick’s domain assumption has to be measured on your own data before you ship it (exercise 4 builds a graph where the premise holds); lane 3 reference — link prediction on a collaboration graph grown with preferential attachment + triadic closure where a random guess is right 0.314% of the time (right inside Liben-Nowell’s 0.147–0.475% band): preferential attachment 1.9×, common neighbours 20.7×, Jaccard 25.6×, Adamic/Adar 22.3× — the degree-only measure barely beats chance, exactly as in the paper), 4 reading guides (Pixie WWW’18 read in full — the 30–50%-engagement argument for real-time over batch, Algorithm 1 in twenty lines, the four innovations (user-feature biasing with PersonalizedNeighbor as a subrange operator, weighted query sets with Equation 1’s sub-linear allocation s_q = |E(q)|·(C − log|E(q)|) where C must be the graph-wide maximum or the top query pin gets zero steps, Equation 3’s multi-hit boost, and per-walk early stopping on n_p pins reaching n_v visits), the language-biasing table (En→Slovak target-language content 2.13% → 42.55%, En→Japanese 16.35% → 80.33%), hit rate 6.3/23.1/52.2% at top-10/100/1000 against content-based 2.1/4.6/10.5%, A/B lifts of +48% on homefeed, the pruning result that F1 peaks 58% above the unpruned graph at 20% of the edges, and the implementation section’s edgeVec object pool + open-addressed visit counter sized to N + HugePages cutting page-table entries 512×; GraphJet VLDB’16 read in full — four generations (Cassovary → Hadoop RealGraph → MagicRecs → GraphJet) and what killed each, the single-server bet with its “ten billion edges is a mere 80 GB” arithmetic and the challenge to distributed graph research, MagicRecs’ reformulation of temporal edge detection as an intersection of adjacency lists, the five-method API and the two deliberate omissions (no deletes because interactions are point events, no timestamps as a space/quality trade), temporally-partitioned index segments with only the newest writable and whole-segment discard as coarse pruning, id mapping by double hashing where the hash IS the internal id (hence the power-of-two table chain) with edge type bit-packed to leave 2²⁹ ids, edge pools whose slice sizes double (P_r holds n/2^{r−1} slices of 2^r edges; degree 25 → P1(1),P2(2),P3(0),P4(0)) justified as an allocator that assumes preferential attachment, single-writer/multi-reader with memory barriers instead of locks, background relayout of sealed segments for contiguous iteration, the alias method for O(1) degree-weighted cross-segment sampling, full vs subgraph SALSA (the subgraph fits in cache and needs only a left-to-right index, ~half the memory, at the cost of second-order paths), the deployment numbers (1M edge insertions/s, 500 rec/s per server at p50 19 / p90 27 / p99 33 ms, O(10⁹) edges in <30 GB, >99.99% over 30 days), and §7.3’s rejection of Redis LPUSH as an adjacency-list store for two named reasons — no memory-allocation optimization and no pruning mechanism — which is a two-item feature list for a Redis-module graph engine; TAO ATC’13 read in full — the three failures of lookaside caching (inefficient edge lists, distributed control logic, expensive read-after-write), the two data shapes and four association queries, creation-time locality (“most of the data is old, but many of the queries are for the newest subset”) forcing newest-first association lists and prefix caching, which in turn forces refill rather than invalidate (invalidating truncates a cached prefix and discards edges), sharding associations by id1 so every query is one server — which is why there is no multi-hop traversal — the leader/follower hierarchy sized by read misses being 25× as frequent as writes, hot-spot handling by shard cloning and access-rate-triggered client-side caching, slab allocation with per-type arenas and association counts packed into 14 bytes for 20% more cache entries, and the production envelope (96.4% read hit rate, assoc_get 1.0 ms p50 hit vs 143 ms p99 miss, writes 12.1 ms in-region vs 74.4 ms from 58 ms away, 4.9 × 10⁻⁶ failed queries over 90 days) plus the two workload tails that must be in any honest benchmark — 1% of assoc_count results ≥512K and 64% of non-empty ranges returning exactly one edge; Liben-Nowell & Kleinberg read in full — the training/test interval setup with κ=3 Core filtering, why factor-improvement-over-random is the only interpretable metric when raw accuracy is 0.147–0.475%, the measure catalogue (common neighbours, Jaccard, Adamic/Adar’s 1/log|Γ(z)| hub discount, preferential attachment, Katz, hitting/commute time normalized by the stationary distribution because otherwise popular nodes dominate — the popularity trap from a third direction, rooted PageRank, SimRank), Figure 3’s table in which preferential attachment scores 4.7–15.2× against common neighbours’ 18.0–47.2× and Adamic/Adar’s 16.8–54.8×, “there is no single clear winner among the techniques”, and the three meta-approaches — low-rank approximation, unseen bigrams, and a clustering step that deletes low-confidence edges and recomputes, which is Pixie’s graph pruning arrived at fifteen years earlier), experiments crate social-experiments (graphs.rs PROVIDED — the bipartite interaction graph with communities, a Zipf tail, configurable interests per user and held-out engagements, plus the Liben-Nowell collaboration graph with preferential attachment + triadic closure and a train/test split, the baselines popularity_topk and basic_random_walk (= Pixie Algorithm 1), and the metrics hit_rate / personalization / popularity_overlap / evaluate with factor-over-random; pixie.rs stub — allocate_steps, walk_per_query, multi_hit_boost, pixie_walk with early stopping; linkpred.rs stub — the four measures; 2 provided tests pass, 8 fix the contract for the stubs, including the boost arithmetic being exact and leaving single-source scores unchanged, every query pin getting ≥1 step with a step ratio strictly below the degree ratio, early stopping keeping ≥70% top-100 overlap in strictly fewer steps, two users from different communities sharing <50% of their top-50, Adamic/Adar’s discount being arithmetically exact on a hand-built hub-vs-specialist case, and preferential attachment losing to both common neighbours and Adamic/Adar), and capstone M42 (a temporally-bounded bipartite interaction store with GraphJet’s index segments and doubling edge pools over M31’s storage, a Pixie-shaped walk procedure with sub-linear allocation and early stopping, and a TAO-shaped assoc_range/assoc_time_range/assoc_count API with time-ordered lists and cached counts — plus the benchmark GraphJet §7.3 explicitly invites, a Redis adjacency-list baseline measured on both counts it names). Cross-topic threads worked: 38 (one random-walk primitive, three seedings), 23/39 (Adamic-Adar = IDF = FRAUDAR column weights), 9 (single-writer deletes the whole latch hierarchy), 12 (sealed-segment relayout as LSM compaction; TAO’s 14-byte count as a columnar instinct), 26 (alias method, bit-packing), 6 (TAO’s cache is buffer management), 36 (shard-by-id1 and cloning vs migration), 40 (TAO vs Zanzibar on hot spots), 25 (low-rank approximation is where embeddings come from).

2026-07-27 — topic 41 — On-Chain & Crypto Analytics

topic 41 On-Chain & Crypto Analytics added (fourth of the six graph use-case deep dives): study guide (haircut taint diffusion measured — bench lane 1: synthetic UTXO chain with planted ground truth, 400 entities / 20,400 transactions / 40,400 outputs / 30,342 addresses (76 addresses per entity — the pseudonymity illusion), one stolen coinbase worth 0.25% of all the money; haircut tainting ends up flagging 3657 of 3734 UTXOs (97.9%) and 3553 of 3627 addresses (98.0%), of which 658 are <0.1% tainted, 2997 are 0.1–5%, and exactly two are above 5% — the total is conserved to the satoshi, haircut does not invent money, it just stops being information; the real-chain version from Anderson et al.: the 2012 Linode theft of 46,653 BTC taints 16,855,619 addresses (93% of all of them) under haircut vs 245,120 (1.35%) under FIFO, Flexcoin 2014 taints 10,421,112 (57%) vs 15,265; lane 2 reference — the three policies on the same theft: poison flags 394.67× the stolen amount (it re-counts each descendant output’s full value, so the total explodes with fan-out), haircut 1.00× spread over 97.9% of the UTXO set, FIFO 1.00× concentrated in 0.9% (32 UTXOs, one holding 22.5% of the flagged value) — same conservation law, 114× narrower answer, at 3.1M transactions/s because the whole algorithm is a queue splice; lane 3 reference — the clustering collapse curve: Heuristic 1 (co-spend) holds precision exactly 1.000 at every change-reuse rate because it keys on a property of the protocol, while Heuristic 2 (one-time change address) buys recall 0.041 → 0.397 and then goes precision 1.000 → 0.661 → 0.502 → 0.089 → 0.009 as one change address in {∞, 100, 50, 20, 10} is reused, with the largest cluster growing 93 (1%) → 366 (3%) → 476 (4%) → 1894 (16%) → 7991 (71% of all addresses) — union-find makes every false merge transitive and permanent, which is why a safe heuristic at recall 0.04 beats an effective one at precision 0.09), 4 reading guides (Meiklejohn et al. IMC’13 read in full — the 2013 parse (231,207 blocks / 16,086,073 txs / 12,056,684 keys), Heuristic 1’s safety argument (“these entities would need to reveal their private keys to each other”) taking 12M keys to 5,579,176 clusters, Definition 4.3’s four conditions with condition 4 as the heuristic’s conscience (decline when two outputs are both fresh) and condition 3 explained by 23% of transactions using self-change, the false-positive ladder 13% → 1% (excluding the Satoshi Dice payout pattern) → 0.28% (wait a day) → 0.17% / 7,382 addresses (wait a week) = precision bought with latency, the 1.6M-key super-cluster containing Mt. Gox + Instawallet + BitPay + Silk Road and its two named causes, and the leverage argument (2,197 clusters named covering 1.8M addresses = 1,600× manual tagging) plus Satoshi Dice at ~60% of all activity; Anderson/Shumailov/Ahmed/Rietmann Bitcoin Redux WEIS’18 read in full with the RustyTaintChain @ 4e12fd0 code read — nemo dat quod non habet and why bitcoin being a commodity rather than money keeps theft victims’ claims alive, poison/haircut/FIFO Figures 1–3, Clayton’s Case (1816) as the precedent, the losslessness argument (“the transaction processes it in a lossless way… we can trace a bitcoin’s heritage backwards as well as tracing taint forwards”), TaintPart{name: u16, value: u64}:52 / extract_taint:142 (the three branches — queue dry, run fits, run straddles the cut and must be split) / combine_taints:174 (collisions between crime sources — why name is a u16 not a bool) / reduce_taint:250 (run-length coalescing or the queue fragments forever), the mixer inversion (“one black coin and nine white coins into a laundry isn’t ten white coins, but ten black ones — people designing money laundering mechanisms have been using quite the wrong metrics of quality”), and §5’s self-undermining finding that most victims’ coins never touched the chain at all because exchanges settle off-chain; BlockSci USENIX Sec’20 read in full — the design chain append-only ⟹ static snapshots ⟹ ACID unnecessary ⟹ in-memory analytical database and the “infinite COST” conjecture, Figure 2’s transaction record (32-bit ids, 60-bit value + 4-bit address type in one word) with inputs/outputs stored inline at a deliberate 19% space cost bought for sequential locality (Table 4: 50.09 GB current vs 40.50 normalized vs 69.26 at 64-bit ids, on 489M txs / 1.198B inputs / 1.302B outputs), the snapshot illusion (disk table grows, each instance pins a block height, past state reconstructible because append-only), memory mapping giving zero-synchronisation parallelism because there is exactly one writer (load ~4 min, full parallel pass 0.9 s on 16 vCPUs, parse 5.5 h), the parser’s bloom filter + multi-use address cache exploiting 88% of inputs spending outputs <4000 blocks old and 8.6% of addresses used more than once accounting for 51% of occurrences, union-find address linking in “a few minutes” yielding 474M clusters / 380M singletons / 809 over 20k / one supercluster >17M addresses, the fluent DSL as a miniature query planner (7–11× over the helper method, 3–5× off hand C++), and Table 3 benchmarked against Neo4j, Memgraph and RedisGraph — FalkorDB’s own ancestor (calculate fee: BlockSci 0.57 s vs Neo4j 303.69 vs RedisGraph did-not-finish vs Memgraph 187.02; but Neo4j-with-index beats single-threaded BlockSci on Tx locktime > 0, 0.05 vs 0.31 s) read row-by-row as a spec for what a graph engine must add to win scan-shaped queries back; Weber et al. KDD’19 read in full — the Elliptic data set (203,769 nodes / 234,355 edges / 166 features / 2% illicit / 21% licit / 49 time steps with no edges between time steps), the 94-local vs 72-aggregated feature split making the comparison “learned vs hand-built one-hop aggregation”, and the uncomfortable result Random Forest illicit-F1 0.788 (0.796 with GCN embeddings concatenated) beating GCN 0.628, Skip-GCN 0.705, EvolveGCN 0.720 — plus the dark market shutdown at time step 43 that breaks every method even when retrained after every step with fresh ground truth, and why micro-F1 >0.92 for every method is meaningless at 2% base rate), experiments crate chain-experiments (chain.rs PROVIDED — synthetic UTXO chain with ground truth the real blockchain does not come with: address_entity per address, one stolen coinbase, planted co-spending / change addresses / recipient address reuse, no fees so taint conservation is exactly testable; taint.rs — haircut provided, poison / extract_taint / fifo stubbed; clustering.rs — UnionFind and the O(addresses) pair-precision/recall scorer provided, multi_input_clusters / change_output (Definition 4.3) / full_clusters stubbed; 3 provided tests pass, 10 fix the contract for the stubs, including FIFO conserving the stolen amount exactly, haircut touching >5× as many UTXOs, poison flagging >10×, every policy staying inside the descendant set with FIFO ⊆ poison, extract_taint splitting a straddling run rather than rounding, co-spend precision being exactly 1.000, Definition 4.3 declining every two-fresh-output transaction, and the 5%-reuse collapse below precision 0.2), and capstone M41 (incremental FIFO taint queues in the property layer with run-length coalescing, a maintained union-find cluster index re-pointing M39’s machinery, and a BlockSci-shaped columnar transaction store so the two layouts can be compared on Table 3’s queries). Cross-topic threads worked: 39 (clustering IS entity resolution — same union-find, hand-written conditions vs learned weights), 40 (both score a graph the adversary reads; prefer protocol properties and lossless measures), 12 (BlockSci’s inline layout as the columnar argument), 32 (Table 3 read row-by-row is an HTAP brief), 1 (the taint policies as a RUM triangle), 33 (Elliptic’s missing cross-time edges delete time-respecting paths by construction), 25 (build the aggregates and measure before reaching for a GNN), 36 (the infinite-COST conjecture rests on graph data resisting partitioning). Repos cloned for the code reads: ~/repos/RustyTaintChain @ 4e12fd0, ~/repos/BlockSci @ 14ccc93.

2026-07-27 — topic 40 — Security & Attack Graphs

topic 40 Security & Attack Graphs added (third of the six graph use-case deep dives): study guide (the list-vs-graph gap measured — bench lane 1: synthetic AD-shaped directory, 2000 users / 400 groups / 1000 computers, five edge kinds (MemberOf, AdminTo, HasSession, GenericAll) with a planted over-privileged group, planted service-account groups and planted policy violations; the console answer is 5 direct tier-zero members, 8 with the one nested group expanded, and it never moves, while attack-path reachability with 1% of users (20) in the over-privileged group goes 39 (1.9%) at zero sessions → 1969 (98.5%) at 100 sessions → 2000 (100%) at 500 — the cascade is that each newly exposed user’s own sessions drag in everyone who is local admin on those machines, so exposure is a function of collection time, not of how much privilege exists; separately, with the gateway shut, one Domain Admin token left on an ordinary workstation takes exposure from 8 users to 2000; mean shortest attack path 6.03 hops, worst 8; lane 2 reference — choke points are dominators: in the reverse graph rooted at tier zero, node d dominates u iff every attack path from u crosses d, so d’s dominator subtree IS its blast radius, pricing every single-node remediation in 0.8 ms vs 543 ms for 3400 individual reachability re-runs (Cooper–Harvey–Kennedy iterative dominators, exact agreement with the delete-and-recompute oracle on every node in both regimes) — and the finding that matters more than the speedup, tiering is what makes a graph have choke points: identical 2000-user exposure, but the tiered directory has a group with a 1992-user (99.6%) blast radius and greedy cuts 2000 → 8 → 5, while the flat one has no single node whose removal frees a single user and cutting the whole gateway set one node at a time reads 2000 → 2000 → 2000 → 2000 → 2000 → 8, so remediation is a set problem and the all-zeros dominator pass IS the report; lane 3 reference — Zanzibar Check by pointer chasing costs 19 → 559 tuple reads and 0.46 → 11.28 µs as group nesting goes 2 → 32 while the Leopard-style flattened closure stays 4 → 12 probes at ~0.01 µs, flat in depth, for a 1.7× entry tax (6672 tuples → 11393 entries, closure quadratic in chain depth) and galloping intersection beats a linear merge by >1000× on a 1-vs-500,000 pair), 4 reading guides (BloodHound code read against ~/repos/bloodhound @ 1968388 — 104 StringKind node/edge kinds at graphschema/ad/ad.go:28, the four purposeful partitions Relationships/ACLRelationships/PathfindingRelationships (63 traversable kinds, the attacker’s alphabet) / PostProcessedRelationships (31 kinds that are derived, not collected — AdminTo, CanRDP, DCSync, ADCS ESC1..ESC13 — a materialized view refreshed by the four-stage pipeline at analysis.go:346), principal sets as roaring bitmaps (cardinality.Duplex[uint64], post.go:244) and parallel BFS with CheckedAdd on a thread-safe bitmap as the visited set (membership.go:81), tiering.go:37 IsTierZero, agt.go selector expansion diffed against previous state; Ammann/Wijesekera/Kaushik CCS’02 read in full — monotonicity (“the attacker never needs to backtrack”), the Sheyner numbers it replaced (5 hosts, 8 exploits → 5,948 nodes / 68,364 edges / 2 hours / 229-bit state space vs at most 229 nodes monotone), no negation in preconditions + preConds ∩ postConds = ∅ ⟹ markAttributes is O(|A|²·|E|) converging in ≤|A| layers, findMinimal/findAll/findShort with Results 1–3, minimum attacks NP-complete but minimal easy, the 3-host example (60 attributes, 30 instantiated exploits, only 8 attributes ever change value), and §2.3’s three-sentence cut-set paragraph which lane 2 makes precise; plus MulVAL CCS’06 read in full — logical attack graphs as tabled-Datalog derivation graphs (derivation nodes = AND, fact nodes = OR, primitive vs derived facts), XSB tabling for cycles and memoization, Theorems 1–3 (O(N²) derivation steps / O(N²) graph size / O(δN²) = O(N² log N) build), “useless edges” as a why-provenance test, 1000 fully-connected hosts on a Pentium 4 where Sheyner’s tool blew up at 10 (Fig 14) and Sheyner’s own 10-host/5-vuln case producing a 10-million-edge graph in 15 min; Zanzibar ATC’19 read in full with SpiceDB @ 8422483 anchors — the relation-tuple grammar and why the user slot holds a userset, the three rewrite leaf kinds (_this / computed_userset / tuple_to_userset), Check as ∃-tuple ∨ ∃-userset-with-recursive-Check with concurrent leaf evaluation and subtree cancellation, Leopard (GROUP2GROUP ancestor→descendants, MEMBER2GROUP user→direct parents, membership = O(min(|A|,|B|)) skip-list-seek intersection = topic 23’s galloping intersect doing authorization; 1.56M QPS median, <150 µs median / <1 ms p99, offline snapshot pipeline + Watch-fed incremental layer at ~500 updates/s, one tuple change → tens of thousands of index events), zookies and the new enemy problem (Example A neglecting ACL update order, Example B applying an old ACL to new content; the ≥ semantics is what lets Safe requests outnumber Recent by two orders of magnitude), hot spots §3.2.5 (consistent-hashed distributed cache forming “cache trees”, timestamp quantization to 1 or 10 s so cache keys collide, lock table against stampedes, hot-object prefetch) and the surprise that a 10% check cache hit rate prevents 500K internal RPC/s of hot-spotting, scale (>2 trillion tuples / ~100 TB / >10M QPS / Check Safe p50-p95-p99 = 3.0 / 9.46 / 15.0 ms / >99.999% for 3 years) and the SpiceDB map of which parts are inherent vs Google-shaped (graph/check.go:99→165→304→539→567, membershipset.go set algebra with caveats so a result can be “maybe”, lookupsubjects.go:430 reverse arrow traversal, dispatch/keys/computed.go:58 a uint64 over a canonicalized expression, singleflight.go:47 = Zanzibar’s lock table verbatim, defaultConcurrencyLimit = 50); SLEUTH USENIX Sec’17 read in full — provenance graphs, the dependency-explosion problem, a main-memory dependence graph at <10 bytes/event vs ~250 B/edge for Neo4j-class stores and ~3 KB for STINGER/NetworkX (32-bit ids, events stored inside subjects, variable-length encoding down to 4-byte subject-event and 16-bit object-event records, delta timestamps, 6-byte bidirectional edges, 38M events in 329 MB, <100 ns decode), the tag design (t-tags benign-authentic/benign/unknown × c-tags secret/sensitive/private/public, and the split of code vs data t-tags worth 1305× against 4.68× for a single tag), four objective-based detection policies, backward analysis as Dijkstra with tag-derived edge costs (unknown→benign = 0, benign→benign = high, unknown→unknown = 1, stopping as soon as an entry point joins the shortest-path tree) and forward analysis pruning 100–500×, Table 11’s end-to-end 38.5M events → 130 (297,100×) with a 54,517× average, and Table 7’s 174 correct / 0 incorrect / 2 missed across eight DARPA campaigns where >99.9% of events were benign), experiments crate attack-experiments (lane 1 provided in ad_graph.rs with AdConfig::tiered() as the clean-directory preset; chokepoint.rs stub — immediate_dominators + blast_radius, with exposure, rank_chokepoints and the blast_radius_naive delete-and-recompute oracle provided; authz.rs stub — check_pointer with cycle protection and optional memoization, LeopardIndex::build, intersect_galloping, with the store generator and linear-merge straw man provided; 3 provided tests pass, 9 fix the contract for the stubs, including exact dominator-vs-oracle agreement on every node in both directory regimes, index-equals-pointer-chasing on every user × group pair, cycle termination, and galloping-beats-merge by >1000×), and capstone M40 (edge-kind-filtered variable-length reachability as a Cypher procedure over M31’s storage with the traversable-kind mask as a roaring set, a one-pass dominator choke-point procedure over the topic-18 CSR, and a Zanzibar-shaped check(subject, resource#relation) with a maintained closure index on the property layer). Cross-topic threads worked: 26/23 (roaring principal sets, galloping intersect), 27 (derived edges and the Leopard closure as materialized views; MulVAL’s graph as a Datalog derivation), 1 (lane 3 is a RUM triangle), 37 (SpiceDB’s bounded scatter-gather, and Zanzibar hedging to Spanner/Leopard but never between its own servers), 18 (CSR traversals), 12 (SLEUTH’s encoding as the columnar argument), 33 (provenance as a contact sequence), 39 (both topics score a graph against an adversary who reads the score).

2026-07-26 — topic 39 — Fraud Rings & Identity Graphs

topic 39 Fraud Rings & Identity Graphs added (second of the six graph use-case deep dives; per user, 39-43 proceed without per-topic review): study guide (camouflage kills row scores, measured — bench lane 1: 5000×5000 Zipf(0.7)×Zipf(0.8) background, 50k edges, planted 25×100 block at density 1.0; precision@|fraud users| at camo/fraud-edge {0, 0.5, 1, 2}: degree-rank 0.00/0.28/0.60/0.76 (misses economical fraud, lights up only once camouflage inflates the row), obscurity-rank 0.52/0.00/0.00/0.00 (mirror image — dies the moment camo buys popular columns) — both are functions of the fraudster’s own row and he tunes camo ≈ 0.5 to slip between them; FRAUDAR column-weighted peeling reference holds F = 1.00 in every regime while unweighted g degrades 1.00/0.95/0.69/0.65 (camo glues the block to the power-users × hit-products core); peel of a 100k×50k-node / 1,019,984-edge graph in ~0.2 s at F = 1.00; Fellegi–Sunter lane: 15,000 records (5000 entities × 3 dups, 5 fields pools [200 500 3650 200 2000] typo [.10 .07 .03 .12 .05]) — naive 112,492,500 pairs → blocked 271,012 (415×) via two passes (last name OR dob), sampled u = [0.0052 0.0021 0.0003 0.0051 0.0006] ≈ 1/pool, EM m = [0.80 0.86 0.94 0.78 0.90] vs analytic (1−t)² [0.81 0.87 0.94 0.77 0.90], p = 0.184, link at 12 bits: precision 0.989 / recall 0.992 in 48 ms), 4 reading guides (FRAUDAR KDD’16 read in full — axioms, g(S)=f(S)/|S|, column weights 1/log(d+5), greedy peel O(|E| log |V|), Theorem 2 ½-approximation, Theorem 3 camouflage-resistance (camo lands on honest columns, block columns never change), F above 0.95 for 200×200 injected blocks under all four camo attacks, Twitter 41.7M users/1.47B edges → 4031×4313 block at 68% density with 57% hand-labeled fraud vs 12-25% controls; Winkler 2006 survey pp. 1-22 — FS decision rule R=P(γ|M)/P(γ|U) with T_λ/T_μ + clerical band proved optimal, per-field log2(m/u) weights, exact matching misses over 25% of census matches → Jaro-Winkler comparators, EM (Winkler 1988), multi-pass blocking 10¹⁷ → 10¹² pairs keeping 99.5% of matches, BigMatch 100M×4B at ~100k pairs/s with 10 passes in one data pass, 1990 census clerical 3000×3mo → 200×6wk; FlowScope AAAI’20 read in full — laundering = dense multi-step flow on k-partite X→W→Y, f_i=min(in,out), g=(1/|S|)Σ[(1+λ)f_i−λq_i] λ=4 so parking/camouflage LOWER the score, CBank 6.13M accounts/43.98M transfers with a labeled real ring (4 sources/12 mules/2 destinations ≈452M yuan): FAUC 0.761/0.843 vs FRAUDAR 0.529/0.704, F1 ≥ 0.9 down to 76M vs 180M injected — covered as guide + exercise 5, no stub; splink code read @ 04189f5 with 14 verified anchors — linker.py:66 façade, training.py:163 estimate_u_using_random_sampling / :231 one-EM-session-per-blocking-rule, expectation_maximisation.py:225 (E :18 / M :193), comparison_level.py:148 with match weight log2(m/u) :426 + _tf_adjustment_sql :667, graded levels comparison_level_library.py:406/:458/:493, predict.py:203 prior+weights → 1/(1+2^(−mw)), blocking.py:747 passes as SQL self-joins, clustering.py:43 → connected_components.py:121, dialects.py:24 one model on DuckDB/Spark/SQLite/PostgreSQL :270/:402/:532/:674), experiments crate (review_graph.rs PROVIDED — Zipf background + planted block + Zipf(1.5) popularity-biased camouflage + both naive rankers, 3 tests green incl. obscurity 0.75 → under 0.3 at camo 2; fraudar.rs + er.rs stubs with 6 contract tests: log-weighted F ≥ 0.9 with and without camo / unweighted F below 0.7 at camo 2 (measured 0.643) / g(returned) ≥ g(planted)/2; u within 0.005+expect of 1/pool / per-pass EM p,m within 0.05 of labeled empirical with the blocked field NaN / match-weight gap over 20 bits / blocking ≥ 20× / precision ≥ 0.95 recall ≥ 0.9; the design discovery: a fixed-u EM over the unioned blocked candidates degenerates to fitted p → 1.0 (every candidate agrees on a blocking key by construction, class U cannot explain it) — the fix IS splink’s API shape, one session per pass excluding its own blocking field, m averaged; margins that keep the contracts honest: block density 1.0 required (0.9 → log F 0.702), camo 4 breaks even log weights (0.619), 20×80 wide-short block caps per-column camo at 20 edges ≈ 3.06 weighted degree below block g 4.97, threshold 12 bits clears the coincidence patterns dob+city ≈10.3 / dob+first ≈10.6 / last+phone ≈10.95 where 8 bits chains precision down to 0.85; reference verified 9/9 then reverted, 0 warnings, bench prints lane 1 + [stub …] banners via catch_unwind), PLAN §39, capstone M39 (dense-block peel as a procedure over M31 storage reading weighted degrees off the topic-18 CSR + write-time identity resolution with blocking-key indexes, FS weights in the property layer, incremental union-find; targets: ~5M edges/s peel on 10M-edge synthetic, per-insert resolution latency at 1M records with two blocking indexes, precision/recall vs lane 3’s 0.989/0.992). Same verified-facts-then-agents-write workflow; splink newly cloned, FRAUDAR/FlowScope/Winkler PDFs to /tmp, all read.

2026-07-26 — topic 38 — GraphRAG & Agent Memory

topic 38 GraphRAG & Agent Memory added (first of the six approved graph use-case deep dives, FalkorDB’s core market; pilot — review before 39-43): study guide (the path-finding collapse measured — bench lane 1: mean rank of the true answer among 17 candidates, chance = 9.0 — mention-count ranking (vector RAG’s shape) 1.00 at 1 hop → 9.21 at 2 hops → 8.71 at 3; BFS distance 9.51/8.95/9.15 at all hops — coverage without association; PPR reference restores 1.00/1.00/1.00 since restart mass from both seeds SUMS at the meet node; one PPR query, 100k nodes / ~400k directed edges, 30 power iterations = 56.6 ms; bi-temporal store reference: 10k entities × 10 job changes → 100,000 edges kept, 10,000 current, as-of scan 0.09 ms — nothing deleted, any moment answerable), 4 reading guides (HippoRAG NeurIPS’24 read in full — hippocampal index analogy, 2-step OpenIE, synonymy τ=0.8, PPR damping 0.5, node specificity |Pᵢ|⁻¹; R@2/R@5 MuSiQue 40.9/51.9, 2Wiki 70.7/89.1, HotpotQA 60.5/77.7; 10-30× cheaper 6-13× faster than IRCoT; AR@5 2Wiki 37.1→75.7; Südhof path-finding case; Microsoft GraphRAG 2404.16130v2 read in full — 600-token chunks/gleanings, exact-match dedup with duplicate-count edge weights, hierarchical Leiden (graspologic), degree-ordered bottom-up community summaries, shuffled map-reduce with 0-100 helpfulness; Podcast 8,564 nodes/20,691 edges + News 15,754/19,520, indexing 281 min gpt-4-turbo; comprehensiveness win 72-83%, C0 = 26,657 tokens ≈ 2.6% of TS, 9-43× fewer; Claimify 34.18 vs 25.23 claims/answer; Zep 2501.13956 read in full — episode/entity/community tiers, §2.1 bi-temporal four timestamps, LLM edge invalidation keeps expired edges, dynamic label propagation, φ→ρ→χ retrieval; DMR 94.8 vs MemGPT 93.4, LongMemEval 60.2→71.2% with latency 28.9→2.58 s and context 115k→1.6k tokens, temporal +38.4%, regression single-session-assistant −17.7%; GraphRAG-SDK code read @ f42ab3d — fixed 9-step IngestionPipeline pipeline.py:35 with mandatory lexical graph + concurrent mentions∥index :175, 2-step GLiNER-then-LLM extraction graph_extraction.py:89, 4-strategy resolution ladder up to embedding+LLM llm_verified_resolution.py:192, vector+fulltext indices INSIDE FalkorDB vector_store.py:35, survivor-pattern dedup :228, rule-based router router.py:19, 9-step MultiPathRetrieval multi_path.py:48 with four parallel chunk paths and cosine rerank top_k=15), experiments crate (kg.rs PROVIDED — synthetic path-finding instances, 3 tests green; ppr.rs + temporal.rs stubs with 6 contract tests: PPR is a distribution + chain decay + meet-node rank 1; invalidate-without-delete t_invalid=Some(200)/t_expired=Some(205) + event-time reconstruction + late-fact known-vs-true split; bench lanes 2-3 print [stub …] until solved; reference verified 9/9 then reverted, 0 warnings), PLAN §38, capstone M38 (PPR as graph procedure over topic-18 CSR, bi-temporal versioning; targets: PPR recall@5 ≈ 1.0 where direct mention is chance, under 100 ms on 100k nodes, as-of within 2× current-only).

2026-07-26 — topic 37 — Distributed Query Execution

topic 37 Distributed Query Execution added (new topic, added to PLAN.md this session; second of the two approved scaling topics, completing the pair with 36): study guide (the fan-out tail measured — bench lane 1 run: analytic table P(any slow)=1−(1−p)ⁿ — at p=1/100: 1.0% for n=1 → 63.4% at n=100 → 99.3% at 500 → 100% at 1000; at p=1/10,000 still 18.1% at n=2000 — fan-out exponentiates rarity into certainty, the component’s p99 becomes the service’s median at n≈70 since 0.99⁷⁰≈0.5; simulated 100-leaf scatter-gather at 1-in-100 slowness, 20k queries: one-leaf p50/p95/p99 = 5.6/9.6/10.0 ms, wait-for-all-100 = 1000/1000/1000 ms, wait-for-95% = 9.6/9.9/9.9 ms — the paper’s Table 1 shape reproduced, good-enough results delete the tail; exchange-as-iterator ASCII, hedge timeline ASCII, DataFusion-vs-DistSQL production shapes), 4 reading guides (Volcano exchange TR CS/E 89-007/SIGMOD’90 verified against the PDF read in full — anonymous inputs so parallelism is one more iterator, packets through shared-memory queues, master/slave propagation-tree forking + primed processes, end-of-stream counted per producer 3×4=12, §4.4 broadcast-by-pinning + merging exchange must keep producers’ records separate + exchange-in-the-middle makes flow control obsolete + fork-vs-reuse is a run-time switch, §4.5 two-level buffer locking never-hold-pool-lock-during-I/O + restart removes hold-and-wait = deadlock-free + ~100-instruction spin-locks + read-ahead/write-behind daemon, §4.6 vs GAMMA shared-memory/top-down/bushy vs shared-nothing/bottom-up/left-deep, §5 Sequent Symmetry 12×80386 numbers: 20.28 s single-process vs 28.00 s no-fork = 25.73 µs/record/exchange, forked 4-process pipeline 16.21 s beats single-process, packet sweep 171 s at 1 rec/packet → 94 at 2 → 15.0 at 50 → 13.7 at 83 = batching is a 12× swing, vectorization’s argument made with processes; Tail at Scale CACM’13 verified against the PDF read in full — variability sources incl. SSD-GC-×100-reads, 63%/18% arithmetic, Table 1 real service 1/5/10 ms leaf → 40/87/140 ms at 100% vs 12/32/70 ms at 95% with slowest-5%-of-requests = half the p99, hedged requests at p95 delay ≈5% extra load, BigTable 1000 keys/100 servers hedge-after-10 ms: p99.9 1,800→74 ms at +2% requests, tied requests with cross-server cancellation + ≤1 ms stagger Table 2: idle p99.9 98→61 ms (−38%), with-terasort 159→108 ms (−32%), tied+terasort≈idle-unhedged at <1% disk overhead, probe-first loses 3 ways (staleness/estimation/herding), micro-partitions ~20/machine = 5% shed steps, latency-induced probation via shadow requests, canary requests on every Google fan-out, mutations easy: Paxos quorums inherently tail-tolerant; DataFusion RepartitionExec code-read with 20 verified anchors — RepartitionExec repartition/mod.rs:1150 + preserve_order :1160 = the merging exchange with per-(input,output) spill channels :398-538, BatchPartitioner :560 with pinned seed-0 REPARTITION_RANDOM_STATE :592 so same-key-same-partition always (joins depend on it), partition_iter :825 routes whole batches round-robin but rows by hash via create_hashes :854 + strength-reduced % :675, distributor_channels.rs channels() :55 + Gate :62 + send :131 = N unbounded buffers with one global gate that parks senders only when ALL are non-empty (prevents distribution deadlocks in join plans), Partitioning enum partitioning.rs:117; real finding: EnforceDistribution retired into EnsureRequirements ensure_requirements/mod.rs:159, enforce_distribution.rs:18/:76 are helpers + the retirement note; cockroach DistSQL code-read with 18 verified anchors — checkSupportForPlanNode distsql_check.go:214, mustWrapNode :312 for no-processor-equivalent nodes, PartitionSpans distsql_physical_planner.go:971 = the topic-36 bridge: range ownership becomes the parallel plan, createPhysPlan :3604, OutputRouterSpec data.proto:149 with PASS_THROUGH/MIRROR/BY_HASH/BY_RANGE :152-:160 = Volcano’s routing policies as a protobuf enum, Flow flowinfra/flow.go:72/Setup :272/Run :566, Outbox colrpc/outbox.go:50/:218/:323 + Inbox inbox.go:57/:212/:333 = exchange’s two halves over gRPC with Inbox.Next an ordinary iterator — anonymous inputs surviving a network hop, hashRouter rowflow/routers.go:538 + vectorized HashRouter colflow/routers.go:443), experiments crate compiles: fanout.rs PROVIDED (two-mode leaf 1-10 ms fast/1000 ms stall, closed form, scatter_gather max + 95%-frac variant — 3 tests pass: 63.4%/18.1% exact arithmetic, simulation within ±2% at 20k trials, leaf-tail-becomes-service-median) — exchange.rs (Exchange::partition round-robin-cursor/splitmix64-hash to k outputs: deterministic-and-complete + balance-within-one-row + merge_sorted k-way keeps the multiset sorted) and hedge.rs (request_with_hedge fire-second-copy-only-past-delay: 10 ms hedge cuts p99.9 ≥10× + extra load <10% + zero-delay-doubles-requests) are todo!() stubs — 6 tests fail as todo panics; reference solution verified 9/9 then reverted: round-robin 229.6 M rows/s, hash 543.0 M rows/s balance 1.002, 8×500k merge 80.6 M rows/s, hedge@10 ms p99.9 1000→18.3 ms at +0.5% requests (hedge@0 = +100%, the degenerate case) — the paper’s 1,800→74 ms shape; distq_bench lane 1 RUN (tables above), lanes 2-3 armed behind catch_unwind; notes.md predictions vs measurements + all verified anchors + PDF facts; M37 log: scatter-gather over M36’s slots + in-engine exchange (hash for join build, round-robin for scans, per-producer end-of-stream counting) + hedged reads on slot replicas with p95 delay through topic-35’s admission layer, targets = near-linear scale-up 1→2→4→8, p99.9 with one stalled shard within 2× no-stall when hedging, hedge overhead ≤5%. Same verified-facts-then-agents-write workflow; no new clones (datafusion/cockroach under ~/repos), Volcano + tail-at-scale PDFs to /tmp, both read in full.

2026-07-26 — topic 36 — Sharding, Partitioning & Rebalancing

topic 36 Sharding, Partitioning & Rebalancing added (new topic, added to PLAN.md this session; first of the two approved scaling topics — 37 distributed query execution is next): study guide (mod-N’s failure measured — bench lane 1 run on 1M hashed keys: growing N→N+1 moves 80.0% at 4→5, 83.4% at 5→6, 88.9% at 8→9, 94.1% at 16→17 vs the ring’s ideal 1/(N+1) = 20.0/16.7/11.1/5.9% — the closed form is exact, k mod N == k mod N+1 iff k mod N(N+1) < N (CRT), so movement = N/(N+1) and worsens as you grow; and the skew hashing provably can’t fix: Zipf traffic on 16 hash shards, 10k keys/500k samples, hottest shard carries 9.5% at s=0.8 (1.5× the 6.25% ideal), 14.7% at s=1.0 (2.4×), 23.8% at s=1.2 (3.8×) because a hash maps one key to one shard — only range splitting between keys or hot-key replication answers it; Dynamo strategy 1→2→3 table (fixed-partitions+movable-ownership beats boundaries-follow-node-identity: strategy-1 bootstrap “almost a day”, strategy-3 metadata 3 orders smaller, partition-as-file), ring ASCII, redis MOVED-vs-ASK mermaid, cockroach split/merge/rebalance trigger table, edge-cut vs vertex-cut ASCII), 4 reading guides (Dynamo SOSP’07 verified against the PDF — MD5 128-bit ring, vnodes, preference list skipping same-physical-node, R+W>N with production (3,2,2), sloppy quorum + hinted handoff, per-range Merkle anti-entropy, §6.2’s three partitioning strategies with Fig 8’s efficiency numbers, imbalance 20%-low-load vs 10%-high, 99.94% one-version reads; PowerGraph OSDI’12 verified — α≈2 natural graphs, Twitter in-degree α=1.7 and 1%-of-vertices≈half-the-edges, Thm 5.1 random edge-cut = 1−1/p (87.5% at p=8), Thm 5.2 replication from the degree distribution with gains growing as α falls, Thm 5.3 vertex-cut ≤ ghosts of any edge-cut, greedy Cases 1-4, coordinated vs oblivious; redis cluster code-read with 14 verified anchors — CLUSTER_SLOTS=16384 cluster.h:23, keyHashSlot CRC16 & 0x3FFF + hash-tag carve-out :59, getNodeByQuery cluster.c:1191 → clusterRedirectClient :1443, CLUSTER_REDIR_ASK :1397 vs MOVED :1432 (MOVED updates the client slot map, ASK is one-shot + needs ASKING :1680), migrating_slots_to/importing_slots_from cluster_legacy.h:343-344, SETSLOT state machine cluster_legacy.c:6072-6075; cockroach rebalancing code-read with 12 verified anchors — RangeMaxBytes 512 MB zone.go:257, load splits at 2500 QPS replica_split_load.go:34 / 500 ms CPU :52, split_queue.go:145/:194, merge_queue.go:138, the Decider’s windowed per-key sketch split/decider.go:155/:222/:329 with PopularKeyCount/NoSplitKeyCount as honest failure counters, AllocatorAction allocator.go:125, StoreRebalancer store_rebalancer.go:114/:218 lease-transfers-first — range splits are semantic, between keys, the answer to the Zipf row), experiments crate compiles: placement.rs PROVIDED (splitmix64, modn_movement, Zipf harmonic-CDF sampler, hot_shard_share — exact-80% + hashed-keys + Zipf-hot-shard tests) + graphs.rs PROVIDED (planted-partition + preferential-attachment generators, edge_cut, random baseline — random-cut≈0.875=Thm-5.1 test) — 4 provided tests pass, zero warnings — hashring.rs (consistent-hash ring with vnodes: ≈1/(N+1)-movement-all-to-the-new-node + remove-moves-only-its-keys + more-vnodes-tighter-balance contracts) and partitioner.rs (one-pass LDG greedy: score = placed-neighbors × (1−|P|/C), balanced-within-slack + beats-random-by-40% + deterministic contracts) are todo!() stubs — 6 tests fail as todo panics; shard_bench lane 1 RUN (tables above), lane 2 (ring 4→5 movement ≈20% vs mod-N 80%, removal moves only the removed node’s share, balance vs vnodes 1/8/64/512) and lane 3 (edge-cut at k=8 random-vs-greedy on community + power-law graphs) armed behind catch_unwind; notes.md predictions vs measurements + all verified anchors + PDF facts; M36 log: slot = hash(vertex_key) & 0x3FFF with hash tags, edges live with source vertex, MOVED/ASK-style redirects + per-slot migration state machine with dual routing, migration runs at topic-35’s lowest admission priority, targets = movement ≈1/(N+1), edge-cut + replication beat random on power-law, p99 during live migration within 2× steady state. Same verified-facts-then-agents-write workflow; no new clones (redis/cockroach under ~/repos), Dynamo + PowerGraph PDFs to /tmp.

2026-07-26 — topic 35 — Overload Control & Resource Governance

topic 35 Overload Control & Resource Governance added (new topic, added to PLAN.md this session; grew out of “more topics for maintaining a database in production”): study guide (metastable failure measured — bench lane 1 run on a deterministic virtual-clock queueing sim reproducing HotOS’21 Fig 2: 300 QPS server, clients time out at 1 s and retry once, single 10 s outage at t=30 s — at 280 QPS offered load the outage queues ~2,800 requests, every timeout fires a retry, offered load locks at 560 QPS and goodput is still 0 at t=199 s (160 s after the trigger ended, provably forever: queue grows 260 req/s); at 140 QPS the identical trigger + identical 280 QPS storm heals at t=161 s because 280 is below the 300 QPS capacity — the dividing line is hidden capacity = capacity/(1+retries) = 150 QPS, and recovery takes ~2 min for a 10 s outage because drain rate = headroom = 20 QPS; metastable stable/vulnerable/metastable lifecycle ASCII, work-amplification table (retry ×2, look-aside cache ×10 at 90% hit rate, failover herds, slow error paths), detection ladder response-time-recursive-vs-CPU-busy≠overloaded-vs-queuing-time-local + CoDel min-sojourn, DAGOR cursor mermaid, cockroach slots-vs-tokens table, redis edge-surfaces table), 4 reading guides (metastable HotOS’21 verified against sigops PDF — trigger vs sustaining loop, root cause = the loop not the trigger, Fig 2’s 280/560/300 arithmetic, stable below 150 / recovery needs retries below 20 QPS, 3000-QPS-app-on-300-QPS-db cache example, Facebook link-imbalance 2-years-undiagnosed one-line MRU-pool fix, “emergent behavior… one cannot write a unit or integration test”, Kraken live-traffic testing, trigger intensity 151-vs-299, reproduction needs Tene-honest load gen → topic 34; DAGOR SoCC’18 verified against arXiv:1806.04075 — subsequent overload Def 1 with 0.5×0.5=25% random-shedding math, avg queuing time 20 ms over 1 s/2000-req windows explicitly not response time (recursive false positives: DAGOR_r sheds at 630 QPS where DAGOR_q reaches the 750 QPS saturation) and not CPU, business priority hash table Login-highest/Pay-above-IM-100×-complaints copied down the call tree, 128 hourly-rotated user sublevels fixing τ/τ−1 oscillation (session priority rejected: users re-rolled by logout/login), Algorithm 1 α=5% multiplicative-down β=1% additive-up on admit counts via priority-histogram prefix sums, collaborative shedding piggybacks the cursor upstream so rejects cost the overloaded server nothing, ~50% higher success than CoDel/SEDA on M², fairness uniform M¹–M⁴; redis code-read with 16 verified anchors — EVPOOL_SIZE 16 evict.c:36, evictionPoolPopulate :134 sampling maxmemory-samples=5 config.c:3223, getMaxmemoryState :384, performEvictions :532 before each command, OOM gate is_denyoom_command server.c:4391 → performEvictions()==EVICT_FAIL :4485 → rejectCommand oomerr :4498 reject-before-work, -BUSY server.c:2130 after busy_reply_threshold script.c:150, output-buffer limits checkClientOutputBufferLimits networking.c:5151 / async close :5215 as slow-consumer backpressure, CLIENT PAUSE pauseActions server.c:4850 — single thread can’t shed by priority so every surface converts an unbounded queue (memory/replies/time) into a bounded fast error; cockroach admission code-read with 13 verified anchors — package doc admission.go:1 shift-queueing-out-of-the-goroutine-scheduler-into-reorderable-WorkQueues, slots-vs-tokens grantKind :54 concurrency-for-CPU vs rate-for-IO-because-compaction-debt-lands-later, requester/granter :178/:198, WorkQueue (tenant, WorkPriority int8 ladder admissionpb.go:23 LowPri=MinInt8…UserHighPri=50, FIFO ts) work_queue.go:303/Admit :813, kvSlotAdjuster AIMD on runnable-goroutines-per-CPU sampled at 1 ms kv_slot_adjuster.go:16/:46 = queuing-time detection in scheduler clothing, ioLoadListener L0 file/sub-level thresholds io_load_listener.go:69/:77 = topic 4’s write-stall signals promoted to node-wide policy), experiments crate compiles: sim.rs PROVIDED (open-loop arrivals, client-timeout-but-server-does-the-work-anyway work amplification, retries at arrival+timeout, outage trigger, Policy trait admit/allow_retry/observe_queuing — 3 exact-arithmetic tests pass incl. offered=1600=exactly-2× in the collapsed window and vulnerable-without-trigger-is-invisible) — tokenbucket.rs (retry budget: burst-then-deny, steady-rate 10-in-1s, idle-does-not-accumulate) and admission.rs (DagorGate: healthy-admits-all, overload-sheds-lowest-first-never-prio-0, additive recovery) are todo!() stubs — 6 tests fail as todo panics; overload_bench lane 1 RUN (table above), lane 2 (retry budgets 15 vs 25 QPS straddling the 20 QPS headroom — one heals, one never) and lane 3 (DAGOR-lite at 2× overload: goodput + per-priority success + admitted p99, vs no-control FIFO starving everyone) armed behind catch_unwind; notes.md records the 2,800-queued/560-locked/260-per-s-growth arithmetic + predictions for lanes 2-3; M35 log: per-query priority + queuing-time cursor on the executor (1 s/2000-query windows), -BUSY-style fast reject with retry-after hint, plan-time memory gate (DENYOOM per query), targets ≥80% of saturated throughput at 2× overload + lane 1 reproduced-then-fixed on the real engine. Same verified-facts-then-agents-write workflow as topics 33/34; no new clones (redis/cockroach already under ~/repos).

2026-07-26 — topic 34 — Debugging & Production Diagnosis

topic 34 Debugging & Production Diagnosis added (new topic, added to PLAN.md this session; grew out of “how do I debug a database in production”): study guide (coordinated omission measured — bench lane 1 run on a virtual clock, deterministic: 1M ops, service 1 µs, 100 ms stall every 100K ops, arrivals every 10 µs — closed-loop reports p50/p99/p99.9/p99.99 all 1.0 µs (only max sees a stall) while open-loop reports p99 = 90.0 ms, p99.9 = 99.0 ms, p99.99 = 99.9 ms = a 90,000× lie at p99; each stall queues ~10K arrivals, 9 stalls → ~9% of requests carry decaying queueing delay, so the worst 1% are exactly the ≥90 ms victims — provable arithmetic, not noise; three-failure-currencies diagram wrong-answers/too-slow/crashed → replay/measurement/forensics; rr one-diagram; redis 3-tier cost table always-on-one-compare / armed-160-sample-rings / on-demand-doctors; RocksDB PerfLevel mermaid), 4 reading guides (rr ATC’17 verified against arXiv:1705.05937 PDF — record boundary = user/kernel interface, nondeterminism = syscall results + async-event timing, RCB the only deterministic HW counter so execution point = (RCB, registers), seccomp-bpf + RR-page + 2-byte-syscall→5-byte-call rewrite avoids 4 ctx switches/syscall, <2× slowdown, one-thread-at-a-time so weak-memory unobservable; Gregg flame graphs CACM 59(6) 2016 — x-axis is alphabetical merge not time, width = sample fraction, on-CPU vs off-CPU for lock/fsync waits; redis code-read with 13 verified anchors — slowlogPushEntryIfNeeded slowlog.c:103 with :104 negative-disables/:105 >=-logs, slowlogCreateEntry :28 arg/string trimming, latencyStartMonitor/latencyAddSampleIfNeeded latency.h:50/:63 zero-cost-when-off macro discipline (default 0 config.c:3271), LATENCY_TS_LEN=160 latency.h:17, same-second max-coalescing latency.c:82, LATENCY DOCTOR createLatencyReport latency.c:182, MEMORY DOCTOR object.c:1421, watchdog sigalrmSignalHandler debug.c:2643→logStackTrace :2115; RocksDB code-read with 10 verified anchors — PerfContext perf_context.h:305 thread-local via get_perf_context() :342, PerfLevel ladder perf_level.h:27 kDisable=1/kEnableCount=2/kEnableWait=3/kEnableTimeExceptForMutex=4 (agent corrected brief’s kEnableWaitForMutex against the clone), PERF_TIMER_GUARD perf_context_imp.h:27 compiled out under NPERF_CONTEXT, PerfStepTimer RAII perf_step_timer.h:13, HistogramBucketMapper 109 buckets histogram.h:21/:84, StatisticsImpl/recordTick statistics_impl.h:42/statistics.cc:549 as the global tier), experiments crate compiles: workload.rs PROVIDED (StallModel virtual clock, closed_loop the-liar vs open_loop charging completion−intended, exact-arithmetic tests incl. lat[101]=991_000 — 3 provided tests pass) — histogram.rs (LogHistogram: linear below 2^sub_bits then 2^sub_bits sub-buckets/octave, contracts = est≥true within 1/32 relative error + merge-equals-bulk + memory-never-grows) and slowlog.rs (redis semantics exactly: >=-threshold logs, negative disables, ring evicts oldest, ids monotonic across reset) are todo!() stubs — 6 tests fail as todo panics; debug_bench lane 1 RUN (table above), lane 2 (histogram record ns/op + percentile error vs sort-everything on 10M latency-shaped samples) and lane 3 (the observability tax: hot-loop ns/op bare vs +clock-pair vs +histogram vs +slowlog — M34’s overhead budget) armed behind catch_unwind; notes.md predicts lanes 2-3 + records the lane-1 arithmetic; M34 log: GRAPH.SLOWLOG port (FalkorDB src/slow_log/slow_log.c exists in C) + parse/plan/execute/serialize step timers behind a PerfLevel dial, level 0 provably free via lane 3, full level <5% on M11 suite, before-shot = lane 1 reproduced on the real engine under an induced stall. Same verified-facts-then-agents-write workflow as topic 33; no new clones (redis/rocksdb/FalkorDB already under ~/repos).

2026-07-22 — topic 33 — Temporal Graphs

topic 33 Temporal Graphs added (new topic, added to PLAN.md this session): study guide (the static-condensation lie measured — bench lane 1 run: 2000 nodes, contacts uniform over a 10K-tick horizon, static BFS vs time-respecting reachability for 20 sources: at 4K contacts static claims 25,031 reachable pairs but only 137 have a time-respecting witness = 99.5% false positives, falling 97.5% → 56.9% → 0.0% at 64K contacts where temporal saturates to all 39,980 static pairs — the transition is sharp, static reach is the T→∞ limit; contact (u,v,t,λ) model + valid/transaction/bitemporal axes ASCII; reachability-is-not-transitive so “shortest” splits into earliest-arrival/latest-departure/fastest/shortest; storage-menu table snapshot-per-t / event-log-first-Raphtory / anchor+delta-AeonG / MVCC-as-history keyed on AT-TIME cost + anchor/delta mermaid), 4 reading guides (Wu et al. VLDB’14 — condensing lies, four minima that need four algorithms, Dijkstra’s subpath invariant dies to a cheap-prefix-misses-the-bus counterexample, one-pass O(n+M) earliest-arrival over a time-sorted stream in Rust, dominance lists for fastest/shortest, time-expanded O(M) DAG as the materialized-view alternative; Paranjape/Benson/Leskovec WSDM’17 — δ-temporal motifs, the 36-motif derivation, window-scan DP with cnt[i][j] fragment counters and the expire-shortest-first/insert-longest-first correctness orders, stars-cheap-triangles-O(m√m), blocking-vs-non-blocking fingerprints; AeonG VLDB’24 verified against arXiv:2304.12212v2 — per-VERSION lifespan ω in transaction time, FOR TT AS OF/FROM..TO scoped to MATCH, VP/VE/EP three-clocks split, GC-as-migration Algorithm 1 riding the reaper thread = the 9.74% headline, KV SkipList keys type+Gid+ω with A/D anchor/delta bit, adaptive anchoring Eq 1 three bands, legal check Eq 2 + both-store consults, 5.73× storage / 2.57× latency numbers; Raphtory code-read on fresh clone with 8 verified anchors — EventTime(i64,usize) tiebreaker timeindex.rs:28 solving exactly Wu’s λ=0 tie-order problem in the type system, TimeIndex/TCell size-adaptive enum ladders, TPropCell time→offset into columnar PropColumn, WindowedGraph derives-Copy = BETWEEN as a zero-copy lens + TimeOps::window composing on every view type, db4 segments as the batch-into-arrays correction; caught stale name: TimeIndexEntry renamed EventTime), experiments crate compiles: events.rs PROVIDED (gen_contacts λ=1 sorted, static_reachable the-liar, earliest_arrival_oracle as deliberately-Bellman-Ford fixpoint so lane 2’s one-pass speedup is a measurement not a tautology, replay_at_time naive AT-TIME oracle — 3 provided tests pass) — temporal_reach.rs (one-pass earliest_arrival, matches-oracle-on-3-random-streams + respects-start-time + λ=0-chains contracts) and snapshot.rs (AnchorDeltaStore append/at_time/replay_len, matches-full-replay + anchor-spacing-bounds-replay<every + dense-vs-sparse contracts) are todo!() stubs — 6 tests fail as todo panics; temporal_bench lane 1 RUN (table above), lanes 2 (one-pass vs fixpoint throughput 50K/200K/800K) and 3 (AT-TIME p50/p99 + replay_len vs anchor spacing 1K/10K/100K/∞) armed behind catch_unwind; notes.md predicts lanes 2-3 + records the lane-1 surprise (predicted 30-50% false positives, measured 99.5%); M33 log: temporalPath() defaults earliest-arrival, time-respecting MATCH = non-decreasing timestamps + WITHIN δ, storage choice (anchor+delta over M30 vs MVCC-as-history) pending lane 3’s 2×-p99 crossover, before-shot = lane 1’s column reproduced by static MATCH on temporal data. Guide-writing workflow inverted after subagent sandbox denials (no WebFetch/clone/read-outside-cwd): main session cloned Raphtory, read the AeonG PDF, verified every anchor and number, then a restricted agent wrote markdown from supplied facts only. Cloned raphtory.

2026-07-15 — step-by-step concept format rolled out to all 186 reading guides

step-by-step concept format rolled out to all 186 reading guides (topics 0-1 were the pilot, commit b309537, after feedback that the self-contained chapters were “still hard to learn”): every guide now builds its concepts before pointing at the material — H1 + framing lead kept, then ## The problem in one sentence (plain language, one concrete number), then ## The concepts, step by step with 4-8 ### Step N — <concept> sections (first sentence defines the concept assuming zero DB-internals background, then a real-numbers example / ASCII diagram / the guide’s existing code sample, then why-it-matters; each step uses only terms defined in earlier steps, terms of art defined parenthetically at first use), then the navigation section (“How to read the paper (with the concepts in hand)” for papers, “Where each step lives in the code” with anchors grouped by step for code reads), Questions/Takeaway/References verbatim at the end; all existing assets (diagrams, code samples, file:line anchors, tie-backs) preserved and reorganized, H1 titles unchanged so SUMMARY.md links held. Executed by 17 parallel agents (2-3 topics each; two stalled mid-batch — topics 03 and 09 refinished by follow-up agents); exemplars hand-written first (reading-drepper.md for paper reads, reading-turso-btree.md for code reads). Verification: all 186 guides pass structure checks (≥4 steps, exactly one problem statement and References), 185 SUMMARY.md link titles match on-disk H1s with 0 mismatches, all 49 mermaid diagrams parse under mermaid 11.6.0 (jsdom harness), fence-and-backtick-aware angle-bracket scan clean (2 false positives from multi-line backtick spans), mdBook build green.

2026-07-12 — restructure rollout: all 179 remaining reading guides across topics 00-25 and 27-32…

restructure rollout: all 179 remaining reading guides across topics 00-25 and 27-32 rewritten as self-contained chapters (topic 26 was the pilot, previous entry), executed by 8 parallel agents (4 topics each) against the same spec: concept-first H1 titles replacing “Reading guide — …”, Sources blocks replaced by 2-4 sentence framing leads, one inline Rust-ish code sample of the core algorithm added where the guide lacked one (skips documented for pure surveys / guides already carrying equivalent code), all existing content kept (diagrams, line-anchor tables, questions, tie-backs), ## References appended with Papers (arXiv) + Code (GitHub) links carrying the old reading advice, filenames unchanged to avoid link churn; the 32 topic READMEs’ guide lists updated to the new titles; one agent (topics 16-19) hit context limits with 2 files left — reading-umbra-tidy-tuples.md (retitled “Umbra & copy-and-patch: the war on compile latency” + copy-and-patch memcpy/patch-holes sample + References) and reading-sqlite-vdbe.md (References) finished by hand; SUMMARY.md link titles regenerated centrally by script from the actual on-disk H1s rather than agent reports (179 updated); verification: zero old-style H1s, zero Sources blocks, zero guides missing References, fence-and-backtick-aware bare-angle-bracket scan across all 186 guides found one genuine hazard (HashMap<fd, handler> in topic 7’s ae guide, backticked), mdBook build green. The whole book now reads as chapters instead of pointers.

2026-07-12 — book-quality pass, three moves

book-quality pass, three moves: (1) paper audit against dbscholar’s citation-PageRank ranking (rmarcus.info — pulled the underlying data.json, 11,867 SIGMOD/VLDB/CIDR/PODS papers) — resources/papers.md gains a “Modern systems & directions” section and 6 topic READMEs gain “Further references” (Kung-Robinson OCC ’81, Calcite, Spark SQL, Kipf/Neo/Bao learned optimization, Photon, Velox, GAMMA, Dremel, Lakehouse+Delta Lake, MillWheel, CockroachDB); (2) all ~/repos/... code references linkified to their GitHub repos (scripted, fence-aware: 143 links across 115 files) so the online book’s code pointers resolve; (3) restructure demo on topic 26 — all 7 reading guides rewritten as self-contained chapters: concept titles (“HyperLogLog: count distinct in 12 KB” not “Reading guide — …”), framing lead instead of a Sources block, an inline Rust code sample of each core algorithm (HLL add/merge + Ertl count skeleton, blocked-bloom 6-probe loop with golden-ratio remix, cuckoo kick loop with the XOR involution, PGM shrinking-cone add_point, roaring galloping intersect, BRIN one-sided range prune, Morton interleave64 magic masks), and a “## References” section at the bottom (papers with arXiv links, code with GitHub links); filenames kept (reading-*.md) to avoid link churn; SUMMARY.md + README titles updated; mdBook build verified locally (mdbook-mermaid install + build green). If the format lands, roll it out to the other 32 topics.

2026-07-12 — PLAN.md expansions backfilled into the four already-scaffolded topics

PLAN.md expansions backfilled into the four already-scaffolded topics (the plan-only commit 2fb095a now has matching study material): topic 7 gains “Bolt: the third answer” — RESP/pgwire/Bolt framing-typing-streaming table (Bolt’s PULL{n}/DISCARD = protocol-level backpressure, §4’s problem solved at the wire) + reading-bolt-packstream.md anchored on FalkorDB’s removed Bolt server read frozen via git show 0b11a00b3^:src/bolt/ (#2170, 2026-07-08): session-sequence ASCII with handshake bolt_api.c:803/version-clamp :845-864, RUN-executes-but-PULL-streams :467-482/:504-521 decoupling, PackStream marker nibbles bolt.c:11/:21/:36 + graph types Node 0x4E/Rel 0x52/Path 0x50 in the type system, why-was-it-removed as a question, M7 stretch = Bolt listener beside RESP; topic 13 gains “The query-language landscape” — 6-language table (Cypher/GQL/SQL-PGQ/SPARQL/Gremlin/Datalog) on model/matching/composability/pushdown + reading-query-languages.md (SIGMOD ’22 GQL+PGQ paper, count-2-paths-in-a-triangle under homomorphism/isomorphism/trail as the same-pattern-three-answers demo, family-tree mermaid, kuzu Cypher.g4 anchor, M13 rule: keep the AST GQL-shaped — quantified path patterns + explicit path-mode field); topic 20 gains “Parallelism: OpenMP inside SuiteSparse, rayon in Rust” — saxpy3’s costed static scheduling (coarse/fine tasks GB_AxB_saxpy3.c:22-48, nthreads-from-flopcount slice_balanced.c:418, parallel flopcount pass :219) vs rayon work-stealing (join/mod.rs:93 inline+push+steal, registry.rs:248 crossbeam_deque Stealer) + reading-openmp-vs-rayon.md with the static-vs-stealing trade table, no-native-Rust-GraphBLAS note (crates are FFI), new M20 checkbox: document each OpenMP→rayon mapping decision; topic 26 gains “Geo indexes: 2D keys through 1D indexes” — valkey GEO as geohash-in-a-zset (interleave64 geohash.c:52 → 52-bit Morton score, geohashEstimateStepsByRadius helper.c:64, 9-cell scan geo.c:375 + haversine verify = bloom’s candidate-then-verify control flow) + reading-geo-indexes.md (Z-order seams vs Hilbert, Guttman R-tree/GiST, S2 prefix-containment vs H3 hexagons, M26 mapping: Morton key through the existing sorted property index). SUMMARY.md gains the 4 new guides so they appear in the book.

2026-07-11 — topic 32 scaffolded

topic 32 scaffolded (added to the plan this session, so the scaffold-all-topics run is complete again): study guide (the HTAP problem measured — bench lane 1 run: 1M-row store behind one coarse lock, fixed 2 s window per mode: writes alone = 11,438,647 writes at p99 333 ns; writes + a free-running full scanner = 69 writes with p99 7.49 seconds — not slowdown, starvation: std Mutex is unfair, the scanner re-wins the lock after each ~0.6 ms scan (3261 scans) and the parked writer never gets in; interference at its worst is zero writes, and the coarse lock is deliberate — mitigations ARE the topic; the freshness/isolation/cost trilemma triangle; the architecture-menu table HANA-delta+main / HyPer-fork() / TiFlash-learner / F1-Lightning-CDC / pg_duckdb-offload keyed on one-copy? freshness isolation; the changelog-is-the-glue mermaid tying topic 27’s thesis to every split design; the same-fold-four-costumes thread: topic 4 LSM minor compaction = HANA delta merge = TiFlash segmentMergeDelta = FalkorDB delta-matrix flush), 4 reading guides (TiDB VLDB ’20 — columnar-copy-as-Raft-LEARNER so the replica costs no write-quorum latency, freshness-is-a-WAIT with tiflash LearnerRead.cpp:35 doLearnerRead + :61 waitIndexTimeout as the anchor, one-planner-two-engines via tidb find_best_task.go:535/:1841/:1878 TiFlash-paths-retained-so-cost-not-topology-decides, learner-log vs CDC-changelog trade question; TiFlash DeltaTree — Segment.h:84 delta-over-stable ASCII with MemTableSet/DeltaValueSpace.h:65 as a-little-LSM-inside-the-delta, Delta/MinorCompaction.h why-compact-the-delta-at-all, DeltaIndex.h:27 as the structure that makes delta+stable merge reads cheap (the thing our scan_sum_a lacks), DeltaMergeStore.h:668 segmentMergeDelta with our merge_preserves_scans test as its correctness condition, MVCC-versions-in-both-layers GC question linking topic 31’s causal stability; HyPer ICDE ’11 + HANA SIGMOD Record ’12 paired as the one-copy family — fork() CoW-page ASCII (snapshot cost ∝ dirtied pages = MVCC-where-the-version-chain-is-the-page-table, GC is exit()), snapshot-ages-until-re-fork = lane 3’s apply interval in OS clothing, HANA delta+main = our replica.rs minus segmenting, HANA’s-trilemma-corner-is-exactly-what-lane-1-measures; F1 Lightning VLDB ’20 + Özcan SIGMOD ’17 survey — CDC-fed HTAP with zero OLTP changes, safe-timestamp = applied_lsn productionized (reads never wait, served stale-but-consistent at the max fully-applied ts — the opposite choice from doLearnerRead), Changepump ordering question = topic 27 changelog + topic 29 Spanner timestamps, the survey’s copies×engines quadrant with every cell trading the same three currencies), experiments crate compiles: row.rs PROVIDED (RowStore = rows + every-write-appended-to-log changelog + scan oracle + skewed_key + percentile — 2 provided tests pass) — replica.rs (ColumnarReplica delta+main: apply/scan_sum_a/merge_delta with delta-overrides-main + highest-lsn-per-key-wins + merge-preserves-scans-and-sorts contracts, freshness_is_visible via applied_lsn gap — TiFlash DeltaTree in miniature, 4 tests), learner.rs (read_wait over an apply schedule: first-batch-covering-read_index, Some(0) if already applied, None = waitIndexTimeout — doLearnerRead as arithmetic, 3 tests) are todo!() stubs — 7 tests fail as todo panics; htap_bench lane 1 RUN (table above; original fixed-200K-writes design serialized into minutes behind ~0.6 ms scan lock-holds — switched to fixed-2s-window per mode, making the writes-completed collapse the headline number), lanes 2 (scan row-vs-delta-heavy-vs-merged + freshness max-lsn-gap vs batch 1K/10K/100K) and 3 (learner-read wait distribution vs apply interval 1/10/100, 50K reads demanding lsn==now) armed behind catch_unwind; notes.md predicts lanes 2-3 + records the starvation surprise + the RwLock exercise; M32 log: Lightning-shaped not TiFlash-shaped (no consensus group until M15, decoupling = zero primary changes), M27’s changelog feeds a delta-matrix replica, router advertises applied_lsn safe timestamps + freshness-bound routing with read_wait-or-fallback, before-shot recorded: 69 writes/2s when analytics shares the copy, success = restoring the 11.4M with scans elsewhere. Cloned tiflash + tidb.

2026-07-11 — topic 31 scaffolded

topic 31 scaffolded (the last topic): study guide (consensus-vs-CRDT as the same problem in opposite currencies — agree-on-an-order vs design-so-order-doesn’t-matter, 1-RTT vs 0-RTT, unavailable-in-minority vs available-under-any-partition; SEC via join-semilattice mermaid; CvRDT/CmRDT table with where-each-lives-in-this-crate; the zoo table clock/lww/counter/orset/rga/graph with the one idea per structure; LWW’s lie measured — lane 1 run: two replicas, 20K writes each, LWW map: 10 hot keys + sync-every-write loses 94.98% of writes, 1000 keys + sync-every-100 loses 88.34%, even 100K keys + rare sync loses 12.45% — “eventually consistent” without conflict semantics is not a semantics, priced; sequence-CRDT integration ASCII with the interleaving dragon; code-reading table across all five cloned repos), 4 reading guides (Shapiro SSS’11 + INRIA RR-7506 — SEC’s three clauses, the CvRDT⇔CmRDT equivalence proof, the catalog reading map ending at §4’s graphs where concurrent addEdge∥removeVertex is declared application-specific = the dangling-edge problem M31 inherits, causal-stability GC question; Kleppmann arc JSON-CRDT ’17 + move-op ’21 + Local-First Onward!’19 — ops-address-identities-not-paths with automerge op_set2/op.rs:52 succ as deletion-by-successor-ops, the concurrent-move duplicate/cycle problem and its undo/redo total-order fix, the does-move-survive-in-graphs M31 design question; sequence CRDTs in production — yrs block.rs:160 ID=our-Dot / :1302 Item with origin+right_origin=YATA’s pair vs RGA’s single parent / :1415 Item::integrate as the loop our rga.rs apply implements plus run-coalescing splits, diamond-types merge.rs:142 self-described “bastardization” + yjsspan.rs:29 INSERTED/NOT_INSERTED_YET retreat/advance = only-be-a-CRDT-at-merge-time, Loro/Fugue maximal-non-interleaving with the letter-soup demo, automerge-vs-loro bench as scratch-project exercise per deps convention; cr-sqlite as THE-database-goes-multi-master — crsql_as_crr clock-row-per-CELL diagram, local_writes/mod.rs:83-133 db_version bookkeeping = Lamport-clock spine, compare_values.rs version-tie-broken-by-VALUE-comparison = deterministic convergence with zero clock trust, changes_vtab.rs replication-endpoint-as-virtual-table, delete-wins-for-rows vs our add-wins-for-nodes tension question, the M31 change-feed schema design question), experiments crate compiles: clock.rs PROVIDED (Dot + VClock tick/covers/merge/partial_cmp-None-defines-concurrent, modeled on automerge clock.rs:109/:145) + lww.rs PROVIDED (register/map with (ts,replica) total order; merge counts its own discards so lane 1 can price the lie) — 6 provided tests pass — counter.rs (G/PN with semilattice-law tests + why-PN-is-two-G-Counters), orset.rs (add-wins over Dots: add-tags-fresh-dot / remove-kills-observed-dots, concurrent-add-beats-remove + remove-covers-all-observed-tags + seeded-permutation convergence), rga.rs (insert-after-parent + skip-larger-(counter,replica)-siblings + tombstones-still-anchor, idempotent apply, delete∥insert-after-it convergence), graph.rs (OR-Set nodes/edges + LwwMap props composition; dangling-edge-hidden-NOT-deleted test: edges()-filters-to-visible-endpoints, re-add-resurrects; props keyed by node id survive remove/re-add vs automerge’s key-by-creation-op as an exercise) are todo!() stubs — 18 tests fail as todo panics; crdt_bench lane 1 RUN (table above; also caught state-based-sync’s quadratic cost live — sync_every=1 ships the whole map per write, workload shrunk and the delta-CRDT motivation written into the bench comment), lanes 2-4 armed behind catch_unwind (OR-Set gossip storm + tombstone census, RGA 50K-char trace + tombstone bloat, graph dangling storm 100-removes∥500-edge-adds + resurrection count); notes.md flags lane 1’s honest caveat (counts merge-time discards only — locally-overwritten writes don’t show, so it’s a lower bound); M31 log: node/edge identity must be Dots not user ids (cr-sqlite’s auto-increment-PK trap), dangling policy locked hide-not-delete, props LWW-with-HLC (topic 29), anti-entropy v1 whole-state → v2 db_version-watermark deltas, deliverable = same workload through M15 Raft vs active-active with latency histogram + concrete-conflict table. All 32 topics scaffolded.

2026-07-10 — topic 30 scaffolded

topic 30 scaffolded: study guide (the-shape-of-the-problem ASCII — regular append-mostly writes vs range+selector+aggregation reads; the baseline finding measured: delta+varint lands at a shape-blind 11.00 B/sample because raw f64 values dominate — whatever the codec does about timestamps is a rounding error until it attacks the value bytes, hence XOR; Gorilla→Prometheus/VM→IOx lineage mermaid with Monarch and BtrDB as the bracketing extremes; five-system table on codec / time organization / label index / out-of-order policy; TSDB=LSM-keyed-by-time thesis with retention=drop-the-oldest-level), 4 reading guides (Gorilla VLDB ’15 + prometheus chunkenc/xor.go — prediction-error framing with the dod/XOR ASCII, paper bucket table vs prometheus’s retuned 14/17/20 buckets (:195-208) as buckets-are-workload-parameters, writeVDelta :226 window reuse, :396 tDelta+=dod as the whole model in one line, no-random-access-by-design, entropy-floor bit accounting question; prometheus tsdb — full architecture ASCII head/WAL/2h-blocks/exponential compaction, head_append.go:436/:481/:688-693 as the exact head.rs contract (ErrOutOfOrderSample vs ErrTooOldSample), OutOfOrderTimeWindow head.go:168 quarantine design, MemPostings postings.go:60/:403 = topic 23’s inverted index with labels as terms, the two famous failure modes high-cardinality + churn; VictoriaMetrics + InfluxDB 3 paired as two-rebuttals — VM partition.go:75 rawRows→parts LSM-said-out-loud, nearest_delta2.go:15 byte-aligned varint batches with optionally-lossy precisionBits vs Gorilla’s exact bits, index_db.go:124 tagFilters cache + churn invalidation, vs IOx WAL→Arrow QueryableBuffer→Parquet-on-object-store (influxdb3_wal/lib.rs:75-98 SnapshotTracker, queryable_buffer.rs:41) as topic 28’s landing-zone applied to metrics, vertical-integration-vs-commodity-formats trade table, how-much-of-Gorilla’s-win-was-really-sorting question; Monarch VLDB ’20 + BtrDB FAST ’16 — monitoring-must-not-depend-on-what-it-monitors ⇒ RAM-first lazy durability, push-vs-pull, distribution-typed values as the schema cure for cardinality, query pushdown; BtrDB’s aggregate tree — min/mean/max/count per 64-way node ⇒ query cost ∝ pixels not samples, downsampling as the index structure itself, CoW versions), experiments crate compiles: gen (scrape jitter, gauge/counter/constant/random shapes, OOO arrivals, label sets with the unique-instance cardinality bomb) + bits (MSB-first BitWriter/Reader + sign_extend so the stub is the algorithm not bit plumbing) + baseline (zigzag varint delta) PROVIDED — 7 provided tests pass, lane 1 RUN (table above, decode ~270-330 Msamples/s — byte-aligned codecs have a real throughput edge over bit-packed Gorilla, the actual design axis is ratio-vs-decode-speed) — gorilla.rs (paper dod buckets + XOR leading/trailing windows; bit-exact roundtrip incl. bucket edges, constant ≤~2 bits/sample, gauge beats raw 3×, random must FAIL to compress >8 B/sample — the codec wins on regularity not magic), head.rs (in-order fast path + bounded OOO window + TooOld refusal + LWW merge flush that feeds the in-order-only encoder — prometheus semantics exactly), index.rs (MemPostings-style (name,value)→sorted-ids + shortest-list-first k-way intersect, brute-force oracle, cardinality-bomb-counted test) are todo!() stubs — 15 tests fail as todo panics; tsdb_bench lanes 2-4 (gorilla ratios per shape, OOO tax sweep 0-50%, selector latency at 100K series) armed behind catch_unwind; notes.md predicts all lanes; M30 log: history chunks per (entity, attribute), MATCH ... AT TIME t = latest_write_before ≤ t so M29’s MVCC read path generalizes to time-travel, storage split by age (custom hot chunks → M28 Parquet cold), Gorilla dod survives for changelog timestamps but property values need dictionary+RLE not XOR, BtrDB-shaped rollup tree over the M27 changelog for graph-evolution queries.

2026-07-10 — topic 29 scaffolded

topic 29 scaffolded: study guide (the-problem-priced motivation table — measured conflict probability of the bank workload itself: 0.3% of 8-txn batches collide at zipf θ=0.5 but 29.9% at 0.9, 86.2% at 1.1, 99.6% at 1.3 — contention is the common case at real-workload skew; design-space mermaid rooted at textbook 2PC with the three escapes labeled on the edges — move-the-decision-into-the-data (Percolator), replicate-the-coordinator (Spanner), remove-runtime-agreement (Calvin), decompose+batch (FDB); one-table five-system summary keyed on concurrency control / clock / cross-shard atomicity / blocking window; Percolator-in-six-lines with THE-COMMIT-POINT marked), 4 reading guides (Percolator OSDI ’10 + TiKV — three-column-families ASCII (data/lock/write with write-CF-as-commit-index), lifecycle sequenceDiagram with the any-reader-resolves note, TiKV walk actions/prewrite.rs:37 (pessimistic_action + secondary_keys args as post-paper hardening) → commit.rs:64 with the :57 duplicate-commit-returns-Ok idempotency arm → check_txn_status.rs:92/:241 + MissingLockAction :458 as production resolve_lock → cleanup.rs:24 Rollback records our sim skips → latch.rs/scheduler.rs local-vs-distributed conflict split, txn_status_cache; Spanner OSDI ’12 + HLC OPODIS ’14 paired — bound-the-ERROR-vs-bound-the-SKEW fork diagram, commit-wait derivation, HLC rules + the l≤max-pt anti-Lamport-drift bound, uncertainty-interval restarts, CRDB walk hlc.go:38/:411/:471/:517 (UpdateAndCheckMaxOffset crashes the node — maxOffset is a promise) + txn_coord_sender.go:113 interceptor stack + txn_interceptor_committer.go:128 parallel commits with STAGING-is-implicitly-committed :195-205 as Percolator’s-resolve-idea-shaving-a-latency-round; Calvin SIGMOD ’12 — agree-on-inputs-not-outcomes diagram, sequencer/scheduler/executor layers, deterministic-locking-kills-both-deadlock-and-2PC, OLLP reconnaissance for dependent txns with the graph-traversals-are-the-ultimate-dependent-txn M29 question; FoundationDB SIGMOD ’21 — unbundled roles ASCII, ConflictSet.cpp:947 detectConflicts over the :224 SkipList as the-whole-SI-check-in-one-data-structure, CommitBatchContext :504 batch-is-the-unit, masterserver-is-barely-a-counter, ResolverBug.cpp injectable-wrong-answers as DST culture beyond crash injection, vs-Calvin and vs-Percolator design reads), experiments crate compiles: kv.rs PROVIDED (the three Percolator column families as HashMaps/BTreeMap, strictly-monotonic TSO, latest_write_before range scan, 2-shard cluster, Zipf transfer workload — 4 provided tests pass) — tpc.rs (2PC coordinator with 4-point CrashPoint injection + recovery-from-durable-state-only; blocking_window_demonstrated test names the flaw), percolator.rs (get/prewrite/commit_primary/commit_secondaries/resolve_lock with roll-forward-iff-primary-committed tests, no-lock-leak on failed prewrite, total-conserved-after-rollback), hlc.rs (send/recv rules; monotonic-under-backward-clocks, l-bounded-by-max-pt over 1000 skewed messages, concurrent-events-collide-without-node-id-tiebreak as an assert_eq teaching test) are todo!() stubs — 14 tests fail as todo panics; txn_bench lane 1 RUN (conflict table above), lanes 2 (abort rate vs θ + bank invariant) and 3 (20K-txn crash storm, crash every 100th cycling 4 points, blocked_aborts counts the blocking window empirically) armed behind catch_unwind; notes.md predicts lane 2/3 numbers before implementation; M29 log: shard by node id, cross-shard edge = prewrite both adjacency sides with primary on u, supernodes are the Zipf head — per-shard adjacency segments turn the WW hotspot into scatter-gather reads, every protocol step gets a kill point with no-dangling-half-edges as the invariant.

2026-07-10 — topic 28 scaffolded

topic 28 scaffolded: study guide (the latency ladder measured and priced — local NVMe p50 0.10 ms vs raw S3 p50 14.17 / p99 112.99 ms = 140× median, 940× tail, and why everyone moved anyway: $/GB, 11-nines durability = replication-is-someone-else’s-problem, scale-to-zero; the 2008→Snowflake→Aurora→Socrates→Neon→SlateDB lineage mermaid; Neon’s four-box data flow with the safekeepers-commit-fast / pageserver-serves-pages split; five-system design-space table with what-crosses-the-network as the axis; WAL-rule-promoted-to-architecture rosetta linking topic 27’s Kafka thesis), 5 reading guides (Aurora SIGMOD ’17 — the-log-is-the-database, 6-copy 4/6 AZ+1 quorums over 10 GB protection groups, 35× network amplification killed, VDL-replaces-2PC question, commit=log-quorum-ack + recovery-without-REDO-at-compute; Socrates SIGMOD ’19 — durability≠availability as THE decomposition, XLOG landing zone vs page servers vs XStore mapped onto topic 5’s WAL lifecycle and onto Neon components, RBPEX = buffer pool made restart-durable; Snowflake SIGMOD ’16 + Building-a-DB-on-S3 SIGMOD ’08 paired — the prescient paper’s three blockers (eventual consistency/no CAS/request cost) vs what fixed each (strong consistency 2020, conditional PUT 2024, immutability routed around all three), micro-partitions as CoW-clone-by-file-list, min/max pruning = topic 26’s BRIN at cloud scale; Neon code walk — get_rel_page_at_lsn pgdatadir_mapping.rs:258 → Timeline::get :1227 → LayerMap::search layer_map.rs:448 as an LSM over (page, LSN), walredo.rs:173 = REDO on the read path in a sandboxed Postgres, branch_timeline_impl tenant.rs:4985 O(1) branches + the timeline.rs:4548 ancestor walk our stub reimplements, branch-aware GC retain-point question; SlateDB+Quickwit S3-first code walk — tablestore.rs:835 block-granular ranged GETs, cached_object_store part cache = our cache.rs in production form, fence.rs:105 CAS-epoch fencing = consensus outsourced to S3 conditional PUT, clone.rs:38 zero-copy clones, quickwit bundle hotcache footer + TimeoutAndRetryStorage :37 hedging with the AWS-recommends-it citation, pathology→countermeasure convergence table), experiments crate compiles: virtual-latency sim (charged-not-slept lognormal S3 with 2% 8× stragglers, NVMe, scripted Fixed model for exact contract tests) + block store + zipf + percentiles PROVIDED — 6 provided tests pass, tier_bench provided lanes RUN (numbers above) — LruBlockCache+TieredReader (touch-protects, 1/8-cache zipf hit-rate >50%, block-sharing hits), hedged_get (scripted 50ms-primary/1ms-backup/10ms-deadline ⇒ exactly 11ms, p99-halves-at-<10%-extra-GETs on straggler-heavy S3), BranchStore::get (parent-prefix visibility, sibling isolation, PITR historical branch points, 100-deep chains, branching-copies-nothing proven by version_count) are todo!() stubs — 13 tests fail as todo panics; notes.md predicts cache-fixes-the-median-hedging-fixes-the-tail and flags the O(n)-eviction-scan wall-time trap; M28 log: L0+WAL stay local (landing-zone lesson), manifest-CAS fencing not leases, branch at SST-list not page granularity, image-layer materialization deferred until ancestor walks profile hot.

2026-07-10 — topic 27 scaffolded

topic 27 scaffolded: study guide (recompute-is-the-enemy with the priced motivation table — full recompute per 100-change batch: triangles 97.2 ms / wedge self-join 894.3 ms / re-BFS 24.7 ms vs µs-scale incremental targets; the one algebraic idea as a table — LINEAR ops stream deltas statelessly, BILINEAR joins need arranged inputs via Δ(A⋈B)=ΔA⋈B+A⋈ΔB+ΔA⋈ΔB, NONLINEAR distinct/aggregates need integrals; DBSP I→Q→D mermaid; timestamps/watermarks section: timely frontiers are proofs where Flink watermarks are heuristics; four-system comparison timely/DBSP/Materialize/RisingWave), 5 reading guides (Naiad+timely — could-result-in pointstamp protocol, MutableAntichain frontier.rs:380/update_iter :533, ChangeBatch :16 progress-updates-are-Z-set-shaped, worker.rs:235 step as the topic-7 event loop one layer up, the rosetta table frontier=vacuum-watermark; differential — consolidation.rs:24 = our from_updates verbatim, arrangements as LSM-of-batches with advance=compaction, join_traces join.rs:69 with the fuel/effort loop :348-395 as operator-level cooperative yielding, iterate.rs:192 Variable + bfs.rs:101-107 as the 40 lines our stub can’t do, why deletion-in-recursion needs lattice times; DBSP — Q^Δ=D∘Q∘I with the chain rule as the compositional bombshell, feldera anchors z1.rs:221/integrate.rs:85/differentiate.rs:38/join.rs:123-350/delta0.rs, nested-circuits-vs-lattice trade, the M27 mapping: delta matrix DP−DM=ΔA and wedges need NO new state because the integrals ARE the adjacency matrices; Materialize+RisingWave — dogs^3 delta_join.rs:47 + half_join :315/:402 avoiding intermediate arrangements, indexes-are-arrangements-are-memory, RisingWave Op enum stream_chunk.rs:45 as Z-set-weights-as-protocol, hash_join.rs:158 degree tables :269 as hand-rolled weight bookkeeping vs one consolidation rule, barrier checkpoints, single-writer-gets-the-hard-parts-free table; Kafka NetDB’11 — dumb-broker/smart-consumer, offset=LSN rosetta, log-compaction=arrangement-advance=LSM-GC same operation three communities, exactly-once = where-do-offsets-live, M27’s raw-log-vs-result-delta subscriber decision), experiments crate compiles: ZSet with consolidation + the distinct-is-not-linear load-bearing test, churn generator with set-semantics guard, full-recompute oracles (sorted-intersect triangles, hash join with weight multiplication, BFS) PROVIDED — 6 provided tests pass, ivm_bench baselines RUN (numbers above) — delta_join+IncrementalJoin (algebra-exact vs join(A+ΔA,B+ΔB)−join(A,B), 30-batch drift-free, deletes-retract), IncrementalTriangles (oracle-tracking under churn, K4-minus-edge=−2, <4K probes for 20 changes on 40K edges), SemiNaiveReach (insert-only BY DESIGN — deletion is differential’s lattice territory, documented; matches re-BFS per batch, ≤4 relaxations/edge EVER, intra-component edges free) are todo!() stubs — 9 tests fail as todo panics; notes.md flags the honest suspicion that IncrementalJoin’s Vec-merge state integration may dominate and re-derive why arrangements exist.

2026-07-10 — topic 26 scaffolded

topic 26 scaffolded: study guide (indexes-are-bets framing with the measured motivation table — point-miss binary search 167 ns / BTreeMap 218 / HashSet 24 at 224 MB, vs blocked bloom’s ~15-25 ns at 12 MB target; three-families ASCII filters/sketches/learned; bloom math block with the reproduce-it FPR derivation; bloom→blocked→cuckoo→xor→ribbon lineage mermaid; HLL sparse-30-bytes-to-dense-12KB story; PGM ε-window thesis), 6 reading guides (bloom→ribbon over RocksDB code — FastLocalBloomImpl bloom_impl.h:144 golden-ratio probe remix vs LegacyBloomImpl :364, CacheLocalFpRate :42 as the Poisson-crowding honesty function, ribbon as banded GF(2) solve with StandardBanding ribbon_impl.h:471 / num_starts_=slots−kCoeffBits+1 :504 and the build-can-fail-vs-monotone question; cuckoo+xor — partial-key involution getAltHash cuckoo.c:122, RedisBloom’s LSM-of-subfilters growth CuckooFilter_InsertFP :256 vs the paper’s fail-at-MAX_KICKS, delete-a-false-positive-corrupts-someone-else contract, xor peeling 1.23× vs bloom 1.44× vs ribbon 1.10×; HLL — hllPatLen :467 / Ertl tau+sigma :1016/:1033 replacing HLL++’s empirical bias tables, ZERO/XZERO/VAL sparse opcodes :380 with promote-at-3KB-or-rank>32, merge-is-a-semilattice AVX2 :1116; learned indexes — Kraska RMI’s no-error-bound flaw, PGM_SUB/ADD_EPS pgm_index.hpp:32-33 + optimal hull PLA piecewise_linear_model.hpp:96/:154-190 vs our simpler shrinking cone, ALEX gapped arrays predict_position alex_nodes.h:1448 + exponential search :1462 with the degrades-in-space-vs-time-vs-write-amp scoreboard; roaring internals extending topic 23 — Store enum store/mod.rs:28-31, ARRAY_LIMIT=4096/RUN_MAX_SIZE=2048 as pure arithmetic container.rs:9-11, 3×3 pairwise kernel dispatch, three-adaptive-encodings table roaring/HLL-sparse/GIN-varbyte; postgres indexam as the classical baseline — _bt_search nbtsearch.c:100 + Lehman-Yao moveright :211, GIN varbyte ginCompressPostingList ginpostinglist.c:196 + pending-list-as-mini-LSM, BRIN bringetbitmap brin.c:301 as the one-sided filter that’s 10,000× smaller than bloom when clustering holds), experiments crate compiles: splitmix64/hash2/fastrange PROVIDED (avalanche + coverage tests pass), filter_bench motivation lanes RUN — binary search miss 167 ns ≈ 23 dependent misses, BTreeMap 218, HashSet 24 ns at 224 MB, hit≈miss 169 (the walk is the cost, not the compare) — BlockedBloom (no-FN + FPR<2.5%@10bpk + <4×-theory + halves-8→16 tests), CuckooFilter (no-FN at 90% load, FPR<1%@12-bit, delete-leaves-others-intact — the test bloom can never pass, graceful-full-failure), Hll (err<3% at 1K/100K/5M, merge registers EXACTLY equal union’s), and LearnedIndex (window ≤2ε+2 always contains true pos, uniform-1M <2K segments, ε holds on hostile powers-of-2+quadratic mix) are todo!() stubs — 15 contract tests fail as todo panics, notes.md has predict-before-measure table and the M26 call that learned indexes are NOT in scope (node IDs are dense — a plain array is already the perfect model).

2026-07-10 — topic 25 scaffolded

topic 25 scaffolded: study guide (message-passing-is-SpMM with receipts — the message_and_aggregate table showing GCNConv = spmm(adj_t, x) at gcn_conv.py:273 and SAGEConv = spmm(..., reduce=mean) while GAT can’t fuse because attention recomputes the matrix values per forward; associativity-as-query-plan — (AX)W vs A(XW) swaps which term carries the big dimension, 90× on Cora; GraphRAG closed-loop mermaid graph→embeddings→M14 vector index→hybrid Cypher), 7 reading guides (node2vec KDD ’16 — second-order walk figure, p/q as BFS↔DFS knobs, the alias-table O(m·avg_deg) memory trap with rejection sampling as the fix, PyG Node2Vec.loss node2vec.py:135 as the SGNS reference; Kipf-Welling GCN — renormalization trick, gcn_norm anchors gcn_conv.py:45-71, GCN-forward-is-a-query thesis, oversmoothing as why-2-layers; GraphSAGE — sampling as a page budget (B·10·25 fan-out math), mean+lin_r≈concat, inductive-is-the-only-write-friendly-variant; GAT — SDDMM+softmax+SpMM kernel decomposition = topic 24’s masked SpGEMM, a_src/a_dst per-node split as factor-out-of-join, materialized-vs-computed view line running exactly between GCN and GAT; PyG message-passing machinery — 10-stop code walk, COO gather-scatter materializes an m×d temp (145 MB on our bench) vs CSR spmm’s zero temporaries = materialize-the-join vs pipeline-the-aggregate, message()-as-arbitrary-callable = Ligra’s F-with-CAS tradeoff third community; TransE — relations as translations, symmetric-relation collapse, link-prediction-is-an-ANN-query so M14 serves KG completion natively; GraphRAG-SDK with systems eyes — vector_store.py:344 queryNodes / :219 SET embedding write path, relationship_expansion’s ANN+k-MATCHes as the k+1-round-trip join to push down, multi_path’s client-side cosine rerank, router-as-planner-with-no-cost-model, four systems smells), experiments crate compiles: CSR + SBM generator (ground-truth labels; O(m) inter-block sampling not O(n²) Bernoulli) + ring-of-cliques + dense Mat/glorot/softmax + SpMM + row-norm adjacency + uniform walks + dense GCN oracle PROVIDED and run — SBM 16,384 vertices/566K edges: uniform walks 42.8 Msteps/s, SpMM 21.2 GFLOP/s = 81% of dense matmul’s 26.2 (64-wide feature rows amortize the gather — fat RHS forgives sparsity, the number that makes M25 plausible) — node2vec_walks (4 tests: degree-stationary dist, p=q=1 ≡ uniform, q orders exploration on ring-of-cliques, p orders backtrack rate), train_skipgram (SBM intra-block cosine must beat inter by 0.2), gcn_norm+gcn_forward (dense-oracle 1e-4, sorted rows, transform-before-aggregate) are todo!() stubs.

2026-07-10 — topic 24 scaffolded

topic 24 scaffolded: study guide (per-source vs whole-graph algorithm map; frontier-world vs algebraic-world mermaid with the honest trade — per-vertex tricks like Afforest’s edge skipping vs LAGraph’s batched matrix frontiers and atomics-free bulk ops; rmat-vs-uniform baseline table making skew the headline), 6 reading guides (GAP arXiv:1508.03619 + gapbs anchors — sssp.cc:44’s redundant-relaxation-beats-bookkeeping bet, bc.cc:76 succ bitmap, cc.cc:69/:106/:129 Afforest’s three phases, tc.cc WorthRelabelling, and the 5-graph matrix as topic 22’s change-anything-different-number; Meyer-Sanders delta-stepping as the Dijkstra↔Bellman-Ford dial with gapbs thread-local-bins vs LAGr_SSSP’s MIN_PLUS tmasked vxm + three implementation traps; Brandes ’01 with the dependency-recurrence derivation exercise + gapbs-vs-LAGr_Betweenness table — the batched ns×n matrix frontier amortizes what frontier code cannot; Ligra PPoPP ’13 — edgeMapData ligra.h:235-272, the m/20 threshold :238, dense/sparse/denseForward, PageRank-degenerates-to-SpMV lesson, m/20 = Beamer α/β = dot-vs-saxpy; Louvain→Leiden Sci Rep ’19 — the disconnected-communities bug as topic 21’s greedy-destructive trap, refinement as egg’s keep-both-forms, ΔQ accumulator = SPA, aggregation = S·A·Sᵀ SpGEMM, determinism-needs-seeding for CALL algo.community; LAGraph analytics — FastSV7 mngp/hooking-as-one-mxv :102 + FASTSV_SAMPLES :335, TriangleCount’s six formulations with the :44 urand-flips-to-saxpy exception, PageRankGAP-vs-PageRank as benchmark-specs-fork-implementations, and FalkorDB’s proc_pagerank.c:197 already calling LAGr_PageRank = M24’s pattern exists, re-plumb it), experiments crate compiles: weighted CSR + RMAT/uniform generators + heap Dijkstra with pop counter + pull PageRank + degree-ordered triangle count + union-find CC + O(n³) definitional BC oracle PROVIDED and run — RMAT scale 16 vs uniform same n/m: 15,645,988 vs 5,428 triangles (2,883×) in 376/158 ms, PR 8-vs-6 iters (hubs slow L1 decay), Dijkstra 343K pops = 1.74×n stale-entry tax, 18,844 components at avg_deg 16 (RMAT’s leaf quadrant strands vertices) — delta_stepping (bucketed, extremes-must-still-be-exact test + relaxation counters), brandes (must match the O(n³) oracle exactly on n=128, then sample GAP-style), and afforest (partition-equal + <50%-of-m edges-inspected bound) are todo!() stubs; RMAT skew assertion needed scale-aware bounds (19.1% top-1% share at scale 12, 36.6% at 16).

2026-07-10 — topic 23 scaffolded

topic 23 scaffolded: study guide (inverted-index anatomy ASCII — analyzer → FST term dict → TermInfo{doc_freq, postings_range} → 128-doc Δ-bitpacked blocks with {last_doc, max_score} skip data; write-path mermaid making Lucene-segments-are-an-LSM explicit — tiered LogMergePolicy works for text because queries fan out anyway; the two speed tricks: compression-with-random-access + score upper bounds), 6 reading guides + 2 cross-linked (Zobel-Moffat CSUR ’06 design-space map — TAAT vs DAAT, capped accumulators as 2006’s WAND, merge-based construction = LSM before Lucene; Robertson-Zaragoza BM25 derivation ladder — eliteness ⇒ tf saturation at K1+1 ⇒ the static ceiling WAND needs, mapped to tantivy bm25.rs:8-59 with the 1-byte-fieldnorm quantization question; Ding-Suel SIGIR ’11 block-max WAND with pivot diagram + four implementation traps (θ seeding, livelock-on-failed-refinement, k-boundary ties, docs-evaluated metric); Roaring — 4096 crossover derivation, kernel matrix, containers = GraphBLAS sparse↔bitmap lattice at 64K granularity; tantivy code walk — compression/mod.rs:3 128-blocks, skip.rs:93/:175/:186 SkipReader/block_max_score, term_info.rs:9-13, fst_termdict, block_wand_union.rs:8-24 find_pivot_doc, log_merge_policy.rs:20-24, 90-minute read order; RediSearch redisearch_rs Rust-rewrite — newly cloned — InvertedIndex core.rs:30/:75 chained varint IndexBlocks vs tantivy’s immutable bitpacked segments, Encoder-as-type-parameter monomorphizing 11 codecs, gc_marker/unique_id cursor validation ↔ delta-matrix wait, new-block-on-delta-overflow, and the finding that RediSearch has NO block-max WAND — scored unions walk everything), experiments crate compiles: zipf corpus (term id = rank, df(t0)=99.9%) + tf-counting index builder with per-128-block max-BM25 metadata + saturating-BM25 + exhaustive TAAT oracle PROVIDED and run — 100K docs/7.9M postings built in 335 ms, common∧rare [t0 t12000] top-10 walks 99,964 postings in 6.34 ms at ~32 ns/posting (hash accumulate dominates — Q1’s lesson again) while the rare term carries ~93% of the winning score = the WAND poster child measured, and vec two-pointer dense∧sparse AND costs O(|dense|) 52 µs for 172 hits = the roaring motivation measured — block-max wand_topk (recipe in doc comment, must match oracle top-k while scoring <25% of the postings) and mini-Roaring (array/bitmap containers, 3 density-crossing oracle tests) are todo!() stubs.

2026-07-10 — topic 22 scaffolded

topic 22 scaffolded: study guide (OLTP↔OLAP benchmark map + the number-is-four-choices mermaid workload/data/harness/metric; choke points one-liner table — Q1 tiny-group agg = expression bench, Q6 2%-scan = the GB/s headline, Q9 = optimizer punisher, TPC-C = the D_NEXT_O_ID hot counter institutionalized; benchmarking-sins checklist linking topic 0’s fair-benchmarking guide), 4 new reading guides + 3 cross-linked existing ones (Boncz TPCTC ’13 choke-point taxonomy with duckdb dbgen/queries dir open + hidden messages — uniform data is why JOB exists, Q1’s 4-6 groups make hash-agg invisible; YCSB SoCC ’10 + go-ycsb zipfian.go:92-165 anchors — zetan/eta/alpha math, the two fast paths, scrambled-fnv rationale, coordinated-omission warning; OLTP-Bench VLDB ’13 + benchbase TPCC anchors — keying/think times :85-100, NURand C_LAST load-vs-run constants :94-116, why nobody runs TPC-C honestly = 12.86 tpmC/warehouse; DuckDB tpch extension — dbgen as streaming TABLE FUNCTION tpch_extension.cpp:17-99 with answers/ shipped next to queries/ = benchmark-as-oracle, run-real-TPC-H-here recipe), experiments crate compiles: dbgen-lite lineitem + row-at-a-time Q1/Q6 oracles + YCSB A-F driver over BTreeMap with ns-percentile Hist PROVIDED and run — Q1 oracle 5.6 GB/s effective (HashMap per row even at 6 groups: CP1.2 measured), Q6 branchy oracle 15.7 GB/s (2% selectivity = perfectly-predicted branch, the crater is hiding at 50%), YCSB uniform A-F 2.88/4.15/3.72/4.40/1.11/2.85 Mops/s with E’s scans 4× a point read — Zipfian/Scrambled generators (the actual YCSB math with head-frequency-vs-theory statistical contract tests) and q1_flat/q6_branchless columnar lanes are todo!() stubs; fixed a nearest-rank percentile off-by-one in the harness itself (harness bugs are results bugs).

2026-07-10 — topic 21 scaffolded

topic 21 scaffolded: study guide (tool-per-guarantee table proptest→TLC→SMT→Lean with cost axis; e-graph = union-find + hashcons + congruence closure with egg’s deferred rebuild = delta-matrix wait = LSM compaction — batch the invariant repair; equality-saturation loop mermaid; TLA+ spec-as-math with the measured state counts; Z3 DPLL(T) diagram + the euf_egraph.h:23 comment where Z3 cites egg back; Perceus RC as the Arc::make_mut compiler pass), 5 reading guides (AWS CACM ’15 — 35-step S3 bug, exhaustively-testable-pseudo-code pitch, small-scope hypothesis; egg POPL ’21 with full source anchors — egraph.rs:970 add / :1147 union / :1416 rebuild / :1346 process_unions fixpoint, machine.rs Bind/Scan/Compare pattern VM = topic 19’s bytecode interpreter, extract.rs greedy find_best vs lp_extract, e-graph ≈ Cascades memo; Z3 TACAS ’08 + src/ast/euf anchors — backtracking trail + justifications = WAL for unions, e-matching triggers = index choice; Specifying Systems + Ongaro’s raft.tla — newly cloned — with the un-model-an-assumption exercise that re-derives terms; Beans + Perceus borrowed-vs-owned + reuse tokens with the proof-vs-TLC-vs-proptest calibration exercise), experiments crate compiles on egg 0.9: expr IR + hand-ordered fixpoint rewriter PROVIDED and run — ~30% cost reduction, ~2 µs/firing, and the planted trap measured: (a*2)/2 → strength-reduce fires before div-reassoc → stuck at (a<<1)/2 cost 5 where egg should reach cost 1 — egg_optimize is a todo!() stub with trap + never-worse-than-hand tests; TLA+ WalReplication spec written AND model-checked (tla2tools.jar downloaded, java 17): SyncCommit=TRUE → Durability holds over 1080 distinct states depth 14 in <1 s; SyncCommit=FALSE → TLC finds the 5-state data-loss trace Append→Commit→Crash→Failover after 123 states — the postgres synchronous_commit=off story, found exhaustively.

2026-07-10 — topic 20 scaffolded

topic 20 scaffolded: study guide (format lattice hypersparse→sparse→bitmap→full with the actual switch tests from GB_convert_sparse_to_bitmap_test.c and GB_conform; one-mxm-four-engines mermaid — dot3 iterates the MASK so work ∝ nnz(M) vs saxpy3’s coarse/fine × Gustavson/hash task scheduler with its flopcount pre-pass = cudf size/retrieve five years early; push-vs-pull BFS as vxm-vs-mxv with LAGraph’s shipped α=8/β1=8/β2=512; delta matrices as LSM-over-matrices — DP=memtable, DM=tombstones, wait=minor compaction, delta_mxm’s (A*(M+DP))<!A*DM> fold), 6 reading guides (Davis TOMS ’19+’23 — zombies/pending as the library’s own deltas, iso matrices, 32-bit indices; SuiteSparse internals with saxpy3.c:22-60 scheduling-essay and hash>m/16⇒Gustavson anchors; Gustavson ’78 + Buluç-Gilbert — SPA design space, symbolic/numeric two-phase; Beamer SC ’12 direction-optimizing with the ICPP ’18 linear-algebra translation; LAGraph — BFS template switch block anchors, ANY_SECONDI parent-without-comparisons, six triangle-count formulations, PageRankGAP; FalkorDB delta_matrix with fresh eyes — header state-table as spec, transposed twin, transpose-as-masked-copy sync, over-masking question — LAGraph newly cloned), experiments crate compiles: CSR+RMAT/uniform/path generators, SpMV, hash-SpGEMM, scalar BFS, hypersparse PROVIDED and run — SpMV 16-19 GB/s single-thread (gather tax vs 30 GB/s streaming), hash SpGEMM ~60-75 Mflop/s (15 ns/flop = the accumulator cost the SPA stub should crush), hypersparse 50× index memory and 171× full-sweep on the 10M-nodes/100K-edges FalkorDB shape — dense-SPA Gustavson and push/pull/direction-optimizing BFS (with per-level trace + path-graph-never-pulls test) are todo!() stubs.

2026-07-10 — topic 19 scaffolded

topic 19 scaffolded: study guide (the spectrum tree-walker → bytecode VM → copy-and-patch → IR JIT → LLVM as a compile-latency-vs-run-speed trade with each system placed on it; produce/consume compiles the PIPELINE not the operators — push inverts control so tuples stay in registers; three JIT grains compared — postgres per-query, Umbra per-pipeline with adaptive Flying-Start→LLVM tiering, GraphBLAS per-kernel-specialization cached forever; DuckDB’s deliberate no-JIT with the VLDB ’18 tie as the counter-argument; M19 = expressions only, gate on measured cost), 6 reading guides (Neumann VLDB ’11 pipelines/breakers + produce-consume inversion; SQLite VDBE — vdbe.c:1049 switch over 199 opcodes, register machine, OP_Yield coroutines as flattened-bytecode’s free resumability; Umbra Tidy Tuples single-pass IR + copy-and-patch musttail stencils; postgres llvmjit_expr.c opblocks-per-EEOP-step + the jit_above_cost estimate-gate failure taxonomy + deform-JIT-as-the-real-win; GraphBLAS jitifyer encodify-hash → PreJIT → memory table → dlopen → invoke-cc ladder with FalkorDB cache-warming implications; cranelift-jit-demo declare→define→finalize→transmute ladder + per-node CLIF emission table for the stub), experiments crate compiles on cranelift 0.116: Expr enum + seeded generator, AST interpreter, and column-at-a-time vectorized lane PROVIDED and run — interp ~2.1 ns/node flat, vectorized 6-12× over interp across depths 2-10 (topic 11’s number reproduced; both linear in nodes, no y-intercept until compile time adds one) — jit.rs compile() is a todo!() stub with bit-exact-vs-interpreter tests, jit_bench prints the three-way table with compile µs + e2e winner and survives the stub via catch_unwind.

2026-07-10 — topic 18 scaffolded

topic 18 scaffolded: study guide (GPU-for-DB-people translation table — SIMT = topic 17’s predication in hardware, coalescing = columnar × 32, shared memory = cache blocking made explicit; the bus decides the architecture — Crystal’s regime A ship-per-query vs regime B device-resident, rewritten for Apple unified memory; libcudf size/retrieve two-phase + cooperative-groups probing = SwissTable at warp scale; Gunrock advance/filter + load-balance menu; CAGRA = HNSW with SIMT-hostile parts deleted by construction), 6 reading guides (Crystal SIGMOD ’20 tile model + fair-CPU-baseline lesson; wgpu compute examples ladder incl. the hello_compute doc-comment our bench proves; libcudf join size/retrieve + shared-mem-until-spill groupby with cuco/cooperative-groups anchors — newly cloned; Gunrock Essentials bfs.hxx enactor + advance.hxx thread/block/merge_path dispatch anchors — newly cloned; CAGRA ICDE ’24 + single-CTA kernel/shared-mem-hashmap/bitonic-topk anchors — cuvs newly cloned; Faiss GPU billion-scale paper — WarpSelect register k-select, memory-tier table), experiments crate compiles AND RUNS on Metal: GpuCtx + workgroup-reduction sum kernel PROVIDED with per-phase timings, gpu_bench crossover sweep run on Apple M3 Pro — CPU wins at every size up to 16M elements (~1.5 ms fixed dispatch floor, flat 16K→1M; even amortized the GPU reads the same unified memory at ~9 GB/s effective vs CPU 30 GB/s — regime B’s bandwidth ratio doesn’t exist for streaming ops on this machine, which IS the lesson), filter_count (one-atomicAdd-per-workgroup, WGSL skeleton provided) and l2_batch (one-invocation-per-target + row/column-major coalescing experiment) are todo!() stubs with exact-match/1e-3 tests, notes.md predicts where arithmetic intensity finally flips the verdict.

2026-07-10 — topic 17 scaffolded

topic 17 scaffolded: study guide (ports×latency mental model — M-series 4 FMA ports × 3cy ⇒ ~12 independent chains, the four autovectorization failures, branchy/branchless/compress filter shapes with AVX-512 vpcompress vs NEON’s missing compress, vshrn movemask idiom, FastLanes interleaved layout), 7 reading guides (simdjson VLDB ’19 + arm64 nibble-LUT classification / PMULL prefix_xor quote parity / LUT-shuffle compress emulation / flatten_bits over-write-under-advance — newly cloned; polars-compute float_sum STRIPE=16 + pairwise-128 and simd_filter! with per-ISA compress + selectivity-adaptive scalar bit-iteration fallback; hashbrown Group×3 backends + memchr Vector — newly cloned — with the finding that hashbrown’s NEON group is 8 BYTES so vceq output already IS the bitmask, no vshrn, while memchr keeps 16 lanes and narrows; SimSIMD under its numkong rename — per-instruction latency/port tables in headers, f64-upcast accumulation, 4-target streaming states = M14’s scoring loop, and the FCMLA lesson: the specialized instruction measured 2.3× SLOWER than 4 plain FMAs; SIGMOD ’15 selective-store/load primitives + vertical hash probing + gather-costs-a-load-per-lane; FastLanes VLDB ’23 1024-lane transposed layout; Mojo SIMD[type,width] parametric-width ladder), experiments crate compiles: dot naive+unrolled-8 PROVIDED and run — 10.89 → 42.12 GB/s, 3.9× from accumulator count alone, zero intrinsics — wide-f32x4 and NEON vfmaq 4-accumulator rungs are todo!() stubs; filter branchy+branchless PROVIDED and swept — branchy craters 9× to 1.19 GB/s at 50% selectivity while branchless holds ~12.7 flat, the SIGMOD ’15 curve live — NEON count (vcltq+vsubq mask-accumulate) and LUT-compress compact (simdjson trick, f32 edition, all-16-masks test) are stubs; unpack4 scalar PROVIDED at 10.20 GB/s, NEON shift/mask stub; simd_bench catches stub panics so baselines always print.

2026-07-10 — topic 16 scaffolded

topic 16 scaffolded: study guide (every technique = generator + oracle table, DST determinism boundary diagram, PQS/TLP/NoREC comparison, Jepsen/elle, Z3-as-search-engine), 6 reading guides (turso testing/simulator with clock/io/file fault-injection anchors + interaction-plan properties + doublecheck + structured fuzz targets; FDB simulation + BUGGIFY + Antithesis determinism-boundary table; SQLancer oracle base classes — newly cloned — PQS check()/rectification, TLP 3-way partition, NoREC optimized-vs-forced-scan; PQS OSDI ’20 + TLP OOPSLA ’20 paired; Jepsen redis-raft/Dgraph findings + elle cycle inference; Z3 — newly cloned — TACAS ’08 + tactic/solver/smt_context anchors + Cosette symbolic-row rewrite verification), experiments crate compiles: sim_fs (buffered/synced/torn-tail file) + kv (WAL KV with 4 injectable bugs: LostDelete/NoSyncOnCommit/TornWriteAccepted/StaleRead) PROVIDED, dst harness + ddmin shrinker + TLP Kleene-eval checker are todo!() stubs with 12 contract tests (all bugs caught ≤200 seeds, zero false positives over 500, deterministic replay, 1-minimal repro, null-blind engine exposed), crash_matrix PROVIDED and run: 5000 seeds/0.02 s per bug — 0.0% false positives, bugs caught at 48.8–99.6% per-seed rates, first failing seed ≤ 3; the matrix caught a real bug in this crate’s own recovery (missing WAL tail truncation made torn leftovers join the next batch — 72.7% divergence until fixed), the topic’s thesis self-demonstrated.

2026-07-10 — topic 15 scaffolded

topic 15 scaffolded: study guide (topology menu as WHO-can-ack axis, Raft state-machine mermaid + election/log-matching/§5.4.2 three-way split, write-path comparison valkey/WAIT/raft, consistency ladder + ReadIndex, hash slots vs ranges), 6 reading guides (Raft ATC ’14 with Fig 8 worked by hand; valkey replication.c shared repl buffer + PSYNC replid/offset + REPL_STATE_ handshake + WAIT + FAILOVER with line anchors; tikv raft-rs — newly cloned — RawNode/Ready contract + step_* dispatch + Progress tracking + maybe_commit-is-§5.4.2; qdrant consensus.rs raft-for-metadata-only split with the data path outside raft; VSR Revisited round-robin views + no-disk durability + TigerBeetle disk-can-lie; DDIA ch. 5/8/9 anomaly catalog + fencing tokens + linearizability), experiments crate compiles: sim.rs deterministic lockstep network PROVIDED (seeded delivery, partition/heal — topic 16 DST preview), raft.rs todo!() stub with 5 safety-pinning tests (one leader, one-per-term across 10 seeds, replicate-to-all, minority-commit-freeze, stale-leader truncation), partition_test timeline binary, repl_lag PROVIDED and run: follower fsync policy AS ack latency — every-1 = 339 entries/s at 2973 µs p50 (F_FULLFSYNC) vs never = 18568/s at 6 µs, the topic 5 ladder measured as replication lag.

2026-07-10 — topic 14 scaffolded

topic 14 scaffolded: study guide (recall-vs-QPS curve framing, HNSW-as-skip-list ASCII, quantization ladder u8/PQ/binary with oversample+rescore, IVF + DiskANN families, filtered-search menu with percolation), 6 reading guides (qdrant GraphLayers builder/serve split + visited pool + the per-query algorithm choice HNSW/ACORN/plain via estimate_cardinality + measured percolation at build; qdrant quantization crate u8 affine dot-expansion / PQ ADC LUTs / binary xor_popcnt + get_oversampled_top; usearch — newly cloned — node-tape layout + paper-default constants + striped locks (helix-db dropped: public repo no longer ships engine source); HNSW paper with skip-list lens; Jégou PQ with SDC/ADC + IVFADC residuals-as-FOR; DiskANN Vamana robust-prune α-slack + PQ-steers/f32-ranks SSD layout), experiments crate compiles: brute-force oracle PROVIDED and run (185 QPS at recall 1.0 over 100K×128-d — the floor), hnsw (Alg 1/2/4, level draw, ef knob) and quant (affine u8 + symmetric distance + rescore pipeline) are todo!() stubs with 10 contract tests (self-query top-1, recall@10 ≥ 0.9, sorted results, log level distribution, α/2 error bound, rescored recall ≥ 0.95), ann_bench sweeps ef 16..256 + oversampling 1/2/4.

2026-07-10 — topic 13 scaffolded

topic 13 scaffolded: study guide (adjacency representation menu with CSR ASCII, four-architecture table neo4j/memgraph/kuzu/FalkorDB across store/Expand/pattern-match/MVCC/updates, delta-overlay-as-LSM observation, pointer-chasing cost analysis, WCOJ/AGM section, LDBC referee), 6 reading guides (GraphBLAS 4 sparsity formats + dot-vs-saxpy mxm + masks-as-pushdown + FalkorDB Delta_Matrix M/DP/DM state machine — neo4j/kuzu/GraphBLAS newly cloned; neo4j 15 B node / 34 B rel fixed records + doubly-linked rel chains = one miss per edge; memgraph skip-list vertex + small_vector edges + PointerPack’d delta MVCC; kuzu columnar CSR node groups persistent+transient + Intersect WCOJ + factorization; AGM bound / Generic Join / EmptyHeaded with the C<A>=A² equivalence; LDBC SNB correlated-power-law datagen + updates-during-reads), experiments crate compiles: adj_list oracle PROVIDED and run (1M-node/16M-edge preferential-attachment: 3.5 µs/query random vs 295 µs supernodes — the 85× graph-shaped tail, max degree 6565), csr (counting-sort build + slice two_hop) and matrix (masked-SpMV two_hop) are todo!() stubs with oracle-agreement + exact-layout + cycle-self-exclusion tests, hop_bench cross-checks via checksums.

2026-07-10 — topic 12 scaffolded

topic 12 scaffolded: study guide (row-vs-column ASCII, lightweight-encoding zoo table incl. FSST, analyze→score→compress lifecycle, zone-map pruning diagram, Arrow-vs-Parquet boundary, MergeTree/DuckDB/Pinot architecture table), 6 reading guides (DuckDB compression framework + 4-mode bitpacking + fetch_row-shapes-the-menu + CheckZonemap; ClickHouse MergeTree — newly cloned — parts/granules/sparse-index/marks two-offset trick + merge-time work; arrow-rs + parquet-rs — newly cloned — buffer recipes, RLE-hybrid, two compression layers; C-Store + SIGMOD ’06 process-compressed thesis; BtrBlocks sampling cascade + FSST symbol tables; ClickHouse VLDB ’24 with ClickBench-on-DuckDB exercise), experiments crate compiles: RLE/Dict/BitPacked todo!() stubs with exact-size + maximal-runs + FOR-width + O(1) random-access contract tests, scan_bench PROVIDED (100M values × 3 shapes, raw vs encoded scans incl. RLE sum-without-decode and dict codes-only sum — “raw-equiv GB/s > memory bandwidth” is the compression-IS-performance headline to verify).

2026-07-10 — topic 11 scaffolded

topic 11 scaffolded: study guide (Volcano→X100→HyPer mermaid, selection vectors + vector-type flags, morsel-driven parallelism diagram, vectorized hash join/agg internals), 6 reading guides (DuckDB DataChunk/2048 + pipeline executor push-pull hybrid + join-HT salt-in-pointer probe; postgres ExecProcNode self-replacing dispatch + execExprInterp computed-goto; polars-stream Morsel/MorselSeq/SourceToken + float_sum masked-SIMD multi-accumulator + DataFusion ExecutionPlan streams and intern-then-flat-arrays GroupedHashAggregateStream; X100 CIDR’05 U-curve; VLDB’18 compiled-vs-vectorized scorecard — memory-bound probes favor vectorized, the M11 architecture argument; SIGMOD’14 morsels), experiments crate compiles: one query three engines — Volcano PROVIDED and run (180.7 M rows/s; found LLVM DEVIRTUALIZING the statically-known Box<dyn> chain, 202→180 after black_box — a compiler will silently turn your Volcano into a compiled engine), vectorized (batches + selection vectors + flat group array) and fused branchless kernel are todo!() stubs with oracle-agreement tests incl. partial-final-batch and mask-sign-extension traps, exec_bench sweeps selectivity 5/50/95.

2026-07-10 — topic 10 scaffolded

topic 10 scaffolded: study guide (parse→bind→logical→rewrite→join-order→physical pipeline mermaid, rewrite-rule menu, Selinger DP vs DuckDB DPccp+greedy-fallback, cardinality three-lies table, Selinger-vs-Cascades memo ASCII), 5 reading guides (DuckDB optimizer.cpp 25-pass pipeline + plan_enumerator DPccp with greedy escape hatch :234 + cost=output-cardinality-only; postgres allpaths.c standard_join_search + geqo threshold 12 + DEFAULT_EQ_SEL 0.005; sqlparser-rs Pratt parse_subexpr + DataFusion fixpoint-of-rules vs DuckDB ordered passes — sqlparser/datafusion/polars newly cloned; Selinger ’79 vs Cascades with M10 architecture-choice question; Leis VLDB’15 JOB — cardinality error 10²–10⁴ dwarfs cost model 2× and search 1.2×, graph-JOB design exercise), experiments crate compiles: toy cost-based planner todo!() stubs (parse_and_plan naive left-deep → push_down → greedy reorder_joins → estimate with 1/NDV + independence + containment) with contract tests incl. join_order_flips_with_stats, explain binary PROVIDED for side-by-side DuckDB EXPLAIN comparison.

2026-07-10 — topic 9 scaffolded

topic 9 scaffolded: study guide (latch vs lock table, memory-ordering cheat sheet + publication idiom, latch-coupling→OLC→lock-free ladder, epoch reclamation diagram, Bw-tree cautionary arc, false sharing), 4 reading guides (postgres lwlock.c packed u32 + recheck-after-enqueue lost-wakeup dance; crossbeam-epoch pin/defer/try_advance — newly cloned; RocksDB InlineSkipList CAS+splices vs memgraph lazy-locking skiplist with accessor-id GC — memgraph newly cloned; Bw-tree ICDE’13 + SIGMOD’18 reality check + Leis OLC), experiments crate compiles: lock-free ConcurrentSet todo!() stub over crossbeam-epoch with 5 contract tests (same-key/remove races exactly-one-winner, reader-survives-removal-churn UAF canary), scaling shootout PROVIDED (global mutex / 16-shard / crossbeam SkipSet / yours, 1→16 threads), false_sharing PROVIDED and run — packed 63 M inc/s vs pad128 3707 M (59×), and pad64 still 2.2× slower than pad128: Apple M-series coherence granularity is 128 B, x86-style 64 B padding only half-fixes it.

2026-07-10 — topic 8 scaffolded

topic 8 scaffolded: study guide (anomaly-per-isolation-level table, doctors write-skew walkthrough, 2PL/OCC/MVCC comparison, postgres tuple-header + visibility flowchart, HOT chain, Hekaton contrast), 6 reading guides (postgres heapam.c/heapam_visibility.c HeapTupleSatisfiesMVCC + HOT + prune/vacuum with line anchors; RocksDB optimistic vs pessimistic txns over one base class — memtable-only OCC validation, point lock manager; surrealdb kvs layer — newly cloned — versioned reads + putc as portable OCC; Berenson ’95 history notation + SI dethroned; SSI VLDB’12 dangerous structure + the single-writer M8 shortcut question; Hekaton + Wu/Pavlo 5-axis menu), experiments crate compiles: Mvcc todo!() stub with 8 contract tests including write_skew_HAPPENS_under_SI (test passes when the anomaly occurs) and Serializable-mode prevention via read-set validation, txn_bench PROVIDED (global Mutex baseline vs MVCC, 3 mixes incl. 64-key hot set, abort counts).

2026-07-10 — topic 7 scaffolded

topic 7 scaffolded: study guide (RESP wire anatomy, event-loop mermaid beforeSleep→poll→read→execute→buffer, three threading models table, backpressure: querybuf/output-buffer kills vs pgwire portals), 4 reading guides (redis ae.c + networking.c parse/reply path with line anchors; valkey 8 io_threads.c SPSC inboxes + tagged job pointers + memory_prefetch.c batch-MLP; pgwire Parse/Bind/Execute/Sync portals + qdrant dual tonic servers — both newly cloned; C10K → thread-per-core arc with the shared↔sharded plane exercise), experiments crate compiles: RESP2 parse/encode todo!() stub with 8 format-fixing tests (incomplete-input-keeps-bytes, binary-safe bulks, pipelining), tokio server PROVIDED (16-shard store, parse-all-then-flush-once pending-writes trick) — benches vs real redis via redis-benchmark -P 1/-P 64 + flamegraph once resp.rs is implemented.

2026-07-10 — topic 6 scaffolded

topic 6 scaffolded: study guide (translation-cost table hash/swizzle/MMU, miss-path mermaid, three shapes of approximate-LRU, swip state diagram, mmap CIDR-’22 checklist), 6 reading guides (postgres bufmgr.c packed-atomic state + CLOCK + buffer rings; DuckDB eviction queue with dead nodes + 4096-insert purge — newly cloned; LeanStore swips/cooling/hybrid latches — newly cloned; redis zmalloc per-thread padded counters + turso CLOCK page cache bonus; mmap paper with LMDB rebuttal; LeanStore+vmcache paper arc), experiments crate compiles: CLOCK BufferPool todo!() stub with contract tests (pinned-never-evicted, dirty-writeback, scan-pressure survival), pool_vs_mmap binary (1GiB file, 4× memory budget, Zipf, tail-latency focus), eviction bench PROVIDED and run — CLOCK 67.0% vs strict-LRU 66.3% hit rate at 20× less time per access (32ms vs 678ms per 1M trace): the “nobody ships strict LRU” lesson, measured.

2026-07-10 — topic 5 scaffolded

topic 5 scaffolded: study guide (WAL rule, four-designs axis LMDB→turso→postgres→redis-AOF, fsync ladder table, group-commit mermaid), 5 reading guides (postgres xlog.c — newly cloned — reserve-then-copy/XLogFlush-recheck/FPI with line anchors; turso WAL checksum chain + salts; redis aof.c/rdb.c with the AOF-as-LSM mapping + FalkorDB angle; ARIES three passes/CLRs; Aether four-bottleneck taxonomy), experiments crate compiles: fsync_ladder PROVIDED and run (this Mac: fsync 21µs vs F_FULLFSYNC 3.0ms — 140×, the macOS weak-fsync gap is real), Wal todo!() stub with format-fixing tests (torn tail, uncommitted-txn invisibility, commit_many = 1 fsync), crash_test kill-9 harness (100 rounds, acked-key + atomicity checks), commit_throughput bench (per-commit vs group 8/64/512).

2026-07-10 — topic 4 scaffolded

topic 4 scaffolded: study guide (memtable→SST lifecycle mermaid, SST block anatomy, leveled/tiered/lazy RUM table, stall triggers, Monkey intuition), 6 reading guides (lsm-tree crate — newly cloned, fjall delegates to it — + RocksDB compaction/table with line anchors; Monkey, Dostoevsky, RocksDB TODS ’21, compaction design-space VLDB ’21), experiments crate compiles: mini-LSM with provided Bloom (tests pass) + Memtable, SST writer/reader + Lsm engine todo!() stubs with correctness tests (tombstone-across-compaction, WA>1 check), write_amp binary measuring the full RUM position of leveled vs tiered.

2026-07-10 — topic 3 scaffolded

topic 3 scaffolded: study guide (slotted page anatomy, 3-sibling balance mermaid, LMDB double-meta COW commit diagram), 5 reading guides (turso btree deep + SQLite btree.c + LMDB mdb.c with line anchors from fresh clones; Graefe survey selective-read map, SQLite file-format hex-dump exercise), experiments crate compiles: slotted Page + DiskBTree todo!() stubs with format-fixing tests, bench vs redb (point/scan) + prefix-truncation stress case (32B keys, 24B shared prefix).

2026-07-10 — topic 2 scaffolded

topic 2 scaffolded: study guide (chaining vs open addressing cache stories, incremental-rehash mermaid, skiplist/rax ASCII, dense-filter/fat-payload pattern table), 7 reading guides (redis dict/zset/rax, hashbrown SwissTable, RocksDB InlineSkipList — line numbers from local clones; ART paper, CppCon SwissTable talk), experiments crate compiles: skiplist + incremental_map todo!() stubs with tests (the build work is the learning work), benches vs hashbrown/BTreeMap/crossbeam-skiplist, rehash_spike binary (HdrHistogram per-insert max/p99.9).

2026-07-10 — topic 1 started

topic 1 started: study guide (two-family write/read paths, amplification vocabulary, RUM triangle), 8 reading guides (fjall/turso/tidesdb/rocksdb code + O’Neil/Comer/RUM/Hellerstein papers, line numbers from fresh shallow clones), engine_shootout scaffold (fjall vs redb behind a common trait, db_bench workload names, durability parity) compiles + smoke-tested (space-amp binary at 20K keys shows fixed-overhead floor, not amplification — re-run at 1M+). Topic 0 plan audit: fixed phantom CMU-lecture reference in PLAN.md, added missing roofline-thinking section to topic 0 README §4.

2026-07-10 — topic 0 finished

topic 0 finished: cache_ladder (after fixing a self-caching bug: restarting the pointer chase at 0 measured an 8MB hot path — fixed by carrying the walker across iterations; true ladder 1.0 ns L1 / 5–9 ns L2 / ~110 ns DRAM+TLB), lookup_shootout (HashMap flat at ~7–9 ns thanks to MLP; binary search wins ≤1e4; linear scan never beats hashing at n≥100 — folklore busted), flamegraph captured (21% SipHash in HashMap lookups), reference baselines recorded in capstone/BASELINES.md. Topic 0 + M0 done.

2026-07-10 — topic 0 started

topic 0 started: study guide + 3 experiment benches (cache_ladder, lookup_shootout, branch_misprediction); capstone workspace scaffolded with workload crate (seeded Zipfian generator, ~11M ops/s). First measured result: branchy filter 8.1x slower on shuffled vs sorted data; branchless flat at 15 Gelem/s. Repo published to github.com/AviAvni/database-learning-path.

2026-07-10 — repo initialized

repo initialized: plan, capstone design, resources.