# DDIA Ch. 9: an uncertain clock orders causal writes backwards 38.9% of the time; commit-wait fixes it for a fixed price of 2ε ## Concept A real clock is not a point. Read it and you get an *interval* — TrueTime's `[earliest, latest]` of half-width ε — and the true instant is somewhere inside; you cannot know where. Give each transaction a commit timestamp from its interval and try to order two **causally-dependent** transactions (B reads what A wrote, so B happens-after A) separated by a real gap *smaller than ε*. Their intervals **overlap**, so you cannot tell which timestamp is later — and picking a point out of each interval orders them **backwards (B before A) 38.9% of the time**. Now apply Spanner's fix: after choosing a timestamp, **wait** until the true time has certainly passed the interval's `latest` before revealing the write. Any later transaction's `earliest` is now provably above this one's `latest`; the intervals never overlap; the ordering errors drop to **0**. The surprise: the fix for a too-*imprecise* clock is to make the system **slower on purpose** — and the wait equals the uncertainty, **2ε**. Tighten the clock and the wait shrinks with it. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 9 — *The Trouble with Distributed Systems*, §"Clock readings with a confidence interval" and §"Synchronized clocks for global snapshots": > Rather than thinking of a clock reading as a point in time, it is more helpful > to think of it as a range of times, within a confidence interval [...] Spanner > deliberately waits for the length of the confidence interval before committing > a read-write transaction. The book presents TrueTime's interval and Spanner's commit-wait as the way to make timestamps safe for *external consistency* — if A causally precedes B, A's timestamp is less than B's. Here you watch the intervals overlap, watch the naive point-timestamp order causal writes backwards, and watch commit-wait close the gap for a fixed latency cost. ## Prerequisites The whole result turns on one move: treating a clock reading as an *interval*, not a point. These help; each line notes where it shows up. 1. **Clock synchronization has bounded error** — NTP (or GPS/atomic references) keeps a node's clock within some offset of true time, but never exactly on it. That bound is ε. It shows up as the clock's fixed `offset` in `[-ε, +ε]`. 2. **Happens-before / causality** — if B reads what A wrote, B *happened-after* A, and any correct timestamp order must put A before B. It shows up as B starting only after A's write is visible, `GAP` ms later. 3. **Confidence intervals** — a measurement reported as `[earliest, latest]` asserts the true value lies inside, not at any particular point. It shows up as `IntervalClock.now()` returning `(reading - ε, reading + ε)`. 4. **Google TrueTime / Spanner** — TrueTime's API returns that interval and guarantees the true time is inside it; Spanner's commit-wait sleeps out the interval so timestamps become externally consistent. It shows up as the `commit_wait=True` branch that advances the true clock past `latest`. ### Where to learn the prerequisites - **The interval idea (carries the whole result):** DDIA §"Clock readings with a confidence interval" — a reading is a range `[earliest, latest]`, and two readings are safely orderable only if their ranges don't overlap. - **TrueTime & commit-wait (#4):** Corbett et al., "Spanner: Google's Globally-Distributed Database" (OSDI 2012), §3 — the `TT.now()` interval, the `TT.after()` predicate, and the commit-wait rule `commit_ts < TT.now().earliest`. - **Clock sync & causality (#1–#2):** DDIA §"Unreliable Clocks" and §"Relying on Synchronized Clocks"; Lamport, "Time, Clocks, and the Ordering of Events" (1978) for happens-before. If only one is new, make it #3-into-#4 — the interval clock is the idea the entire exercise rides on. ## Environment Deterministic, so the counts reproduce exactly: - macOS 26.5.2 (Darwin 25.5.0), arm64 - Python 3.15.0a8, standard library only — no Docker - The interval clock and time advancement are modeled explicitly (no wall-clock sleeping), so the transcript is fully deterministic - Fixed workload: ε = 4.0 ms, real causal gap = 1.0 ms (< ε), 10000 causal pairs, node clock offsets drawn from a seeded RNG (seed 42) ## Mental model A point timestamp *pretends* the clock is exact. An interval timestamp *admits* it isn't. Commit-wait converts that admitted uncertainty into latency so that order becomes provable. - **Point timestamp (no commit-wait)** — read the clock, get an interval, collapse it to a single number (here, `latest`), and use that to order transactions. Because the number is off from true time by up to ε, two transactions whose true times differ by less than 2ε can get numbers in the wrong order. Nothing errors; the order is just silently wrong. - **Commit-wait (Spanner)** — read the clock, take `latest` as the commit timestamp, then *do not reveal the write* until the true time has certainly passed `latest` (until `now().earliest > commit_ts`). Any transaction that starts afterwards reads the clock strictly later, so its `earliest` sits above this transaction's `latest`. The intervals are disjoint by construction; order is provable. The wait is the interval width, 2ε. Both paths run the same causal workload — B always reads what A wrote — and assign timestamps the same way. The only difference is whether A sleeps out its uncertainty before B is allowed to see it. The whole thing is one script, `code/commit_wait.py`. ## Setup ``` cd study/ddia/ch09/code python3 commit_wait.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — do the intervals overlap? **Predict.** A commits at true time 0; B reads A's write 1.0 ms later. The clock's uncertainty is ε = 4.0 ms, so each reading is a ±4 ms interval. B happens *after* A in real time — will B's interval `earliest` sit above A's interval `latest` (clean, orderable), or will the two intervals overlap? **Observe.** ``` one pair WITHOUT commit-wait -- A commits at true time 0, B reads it 1.0 ms later: A's interval latest (A's commit timestamp) = +5.115 ms B's interval earliest = -6.800 ms B.earliest <= A.latest ? True -> intervals OVERLAP ``` The intervals **overlap** — B's `earliest` (−6.800) is far *below* A's `latest` (+5.115), even though B really happened 1 ms *after* A. A 1 ms real gap is invisible inside ±4 ms of clock slop. ### Step 2 — how often does the point timestamp order them backwards? **Predict.** Assign each transaction its interval's `latest` as the commit timestamp, run 10000 causal pairs (B after A by 1 ms every time), and count how often B's timestamp lands at-or-before A's — a causality violation. Roughly what fraction: near 0%, a few %, or tens of %? **Observe.** ``` WITHOUT commit-wait -- assign timestamp = interval latest, then check order: ordering errors (B's timestamp <= A's) = 3886 / 10000 (38.9%) mandatory wait per transaction = 0.0 ms e.g. one violation: A's ts = +5.115 ms, B's ts = +1.200 ms -> B ordered BEFORE A ``` **38.9%** — more than a third of causally-ordered pairs get timestamped backwards. The clock didn't error; it confidently returned numbers that put the *effect* before the *cause*. ### Step 3 — commit-wait **Predict.** Now A holds its write until the true time has certainly passed its interval's `latest`, and only then may B read it and commit. What happens to the ordering-error rate — and what does that safety cost per transaction? **Observe.** ``` WITH commit-wait -- A holds its write until true time passes its `latest`, THEN B may read: ordering errors (B's timestamp <= A's) = 0 / 10000 (0.0%) mandatory wait per transaction = 8.0 ms (= 2 * epsilon = 2 * 4.0) ``` **Zero errors** — every causal pair now orders correctly — bought with a fixed **8.0 ms** wait per transaction, exactly **2ε**. By waiting out its own uncertainty before revealing the write, A guarantees that anything B reads afterwards is stamped strictly later. ### Step 4 — the trade-off: a better clock buys a cheaper wait **Predict.** Shrink ε (a better clock: GPS, atomic). The commit-wait was 2ε. As ε goes 8 → 4 → 2 → 1 → 0.5 ms, what happens to the wait — and to the *un*-waited error rate? **Observe.** ``` trade-off -- shrink the clock uncertainty epsilon and the mandatory wait shrinks with it: epsilon (ms) errors WITHOUT wait commit-wait = 2*eps 8.0 4424/10000 (44.2%) 16.0 ms 4.0 3886/10000 (38.9%) 8.0 ms 2.0 2871/10000 (28.7%) 4.0 ms 1.0 1274/10000 (12.7%) 2.0 ms 0.5 0/10000 (0.0%) 1.0 ms a tighter clock (GPS/atomic) makes the timestamps safer AND the wait cheaper. ``` The wait tracks the clock: it is always **2ε**, so halving ε halves the wait. The un-waited error rate falls too, and once ε drops to half the causal gap (ε = 0.5, so 2ε = 1.0 = the gap), the intervals can no longer overlap and even the naive point timestamp is safe. ## What you should see - A 1 ms causal gap is swallowed by ±4 ms uncertainty: A's and B's intervals **overlap**. - The point timestamp orders causal pairs backwards **3886 / 10000 = 38.9%** of the time, at zero wait. - Commit-wait drops that to **0 / 10000**, for a fixed **8.0 ms = 2ε** wait per transaction. - The wait is always **2ε**: shrink ε and the wait shrinks proportionally; at ε = 0.5 ms the un-waited error rate itself reaches 0. ## Why Two events are safely orderable by timestamp only if the *uncertainty intervals* you read for them do not overlap. That is the whole game. A clock synchronized to within ε of true time cannot hand you the true instant — the honest thing it can return is the range `[reading − ε, reading + ε]`, which is guaranteed to *contain* the true time but pins it nowhere. When you collapse that range to a point to get a comparable number, you reintroduce an error of up to ε in each direction. For two transactions whose true times differ by δ, their points can cross whenever δ < 2ε — and here δ = 1 ms while 2ε = 8 ms, so crossing is common, not rare. That is exactly the 38.9%: the timestamps are not *wrong* about the intervals, they are just being forced into a total order the intervals don't support. The only way to *guarantee* two intervals don't overlap, when the second event is caused by the first, is to make sure the first event's interval is entirely in the past before the second is even allowed to happen. That is commit-wait. A picks its commit timestamp `s = latest`, then refuses to reveal its write until a fresh clock reading's `earliest` exceeds `s` — which, since `earliest(t) = t + offset − ε` and `s = 0 + offset + ε`, happens exactly when the true time reaches `2ε`. So A sleeps for `2ε`. Now B, which cannot start until A's write is visible, reads the clock strictly after that instant; its whole interval sits above `s`; its timestamp is provably greater. The uncertainty didn't go away — it was *paid off* as latency. And because the wait is precisely the interval width `2ε`, the arithmetic gives the punchline directly: buy a better clock, halve ε, and the mandatory wait halves too. Spanner runs GPS and atomic clocks in every datacenter for exactly this reason — not to know the time, but to keep ε (and therefore the wait) small. **The boundary — commit-wait only matters for cross-node ordering under real clock uncertainty.** A single node handing out timestamps from a monotonic counter never needs to wait: it just makes each timestamp larger than the last, and causal order is free because one authority sees every event. The wait is the price of *not* having such an authority — of ordering events across machines whose clocks disagree by ε. And it is only worth paying if you actually need *external consistency* (the timestamp order must match real-time causal order visible to outside clients). If a weaker guarantee suffices — say, causal order only among operations that actually touched the same data — you can track causality directly with version vectors or Lamport/hybrid logical clocks and skip the wait entirely. Commit-wait converts a too-imprecise clock into a provably-orderable one; if you don't need that proof, don't buy it. ### Go deeper 1. **Widen the gap past 2ε.** Set `GAP` above `2 * EPSILON` and watch the un-waited error rate fall to 0 on its own — when the real causal gap already exceeds the uncertainty, the intervals can't overlap and commit-wait becomes redundant. 2. **Spanner's real numbers.** Corbett et al. report ε on the order of a few milliseconds (roughly 1–7 ms, sawtoothing with NTP re-sync). Plug a realistic ε into the trade-off table and see the two-times-ε commit-wait Spanner actually pays on every read-write transaction. 3. **Hybrid logical clocks (a wait-free alternative).** HLCs combine a physical timestamp with a Lamport counter to preserve causality *without* sleeping — but they only order events that are causally linked through messages, not the external real-time order commit-wait guarantees. Trade the 2ε latency for a weaker consistency guarantee and see what you give up.