#!/usr/bin/env python3 """Spanner's commit-wait makes clock-uncertain timestamps safe to order, DDIA 2e Ch. 9. A real clock is not a point. Read it and you get an *interval* -- TrueTime's [earliest, latest], half-width epsilon -- and the true instant is somewhere inside; you cannot know where. Assign 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 by a small real gap). WITHOUT commit-wait: if the real gap is smaller than the clock uncertainty, A's and B's intervals OVERLAP. You genuinely cannot tell which timestamp is later, and the timestamps land BACKWARDS -- B before A -- a fair fraction of the time. That is a causality violation invented by the clock. WITH commit-wait (Spanner's fix): after choosing a timestamp, do not reveal the write until the true time has certainly passed the interval's `latest` -- i.e. sleep out the uncertainty. Only then may a later transaction start and read it. Now the later transaction's `earliest` is provably above this one's `latest`; the intervals never overlap; causal order is guaranteed. The price is latency: the mandatory wait is ~2*epsilon per transaction. Tighten the clock (GPS/atomic) and the wait shrinks with it. No wall-clock sleeping: we drive the underlying true time explicitly and model "waiting" as advancing it past `latest`. Offsets are drawn from a seeded RNG, so the transcript is fully deterministic and reproducible. """ import random # --- The clock uncertainty and the causal workload ------------------------------- EPSILON = 4.0 # clock uncertainty: now() reports a +/- 4 ms interval (Spanner-ish, ms) GAP = 1.0 # real time between A committing and B reading it -- deliberately < EPSILON N_PAIRS = 10000 # how many causally-dependent (A then B) pairs to run SEED = 42 # seed the per-node clock offsets so every run is identical class IntervalClock: """One node's clock. It is off from true time by a fixed, unknown `offset` with |offset| <= epsilon. Reading it does NOT reveal the true time -- it returns a confidence interval [earliest, latest] = [reading-eps, reading+eps] that is guaranteed to CONTAIN the true time (because |offset| <= eps). The width of that interval, 2*eps, is the whole problem.""" def __init__(self, epsilon, offset): self.epsilon = epsilon self.offset = offset def now(self, true_time): reading = true_time + self.offset # what this node THINKS the time is return (reading - self.epsilon, reading + self.epsilon) # (earliest, latest) def run_pair(epsilon, gap, offset_a, offset_b, commit_wait): """Run one causally-dependent pair: A commits, then B (which reads A's write) commits `gap` real-milliseconds later. Each takes its commit timestamp to be its interval's `latest` -- exactly what Spanner does (TT.now().latest). Returns (ts_a, ts_b, a_latest, b_earliest, wait). `wait` is the real time A was forced to hold its write before revealing it.""" clock_a = IntervalClock(epsilon, offset_a) clock_b = IntervalClock(epsilon, offset_b) # A commits at true time 0. t_a = 0.0 a_earliest, a_latest = clock_a.now(t_a) ts_a = a_latest # commit timestamp = latest of the interval if commit_wait: # Spanner's fix: do not reveal the write until now().earliest has passed # ts_a, i.e. until the true time is CERTAINLY beyond ts_a. Since # earliest(t) = t + offset_a - eps, that condition is t > t_a + 2*eps. # We model the sleep as advancing the true clock, not by blocking. t_a_revealed = t_a + 2 * epsilon wait = t_a_revealed - t_a # == 2*epsilon else: # No wait: A's write is visible the instant it commits. t_a_revealed = t_a wait = 0.0 # B is causally after A: it cannot start until A's write is visible, then it # takes `gap` real-ms to read and commit. t_b = t_a_revealed + gap b_earliest, b_latest = clock_b.now(t_b) ts_b = b_latest return ts_a, ts_b, a_latest, b_earliest, wait def measure(epsilon, gap, commit_wait): """Run N_PAIRS causally-dependent pairs with seeded random node offsets and count how often the assigned timestamps put B at-or-before A (an ordering error / causality violation).""" rng = random.Random(SEED) errors = 0 total_wait = 0.0 example = None for _ in range(N_PAIRS): offset_a = rng.uniform(-epsilon, epsilon) offset_b = rng.uniform(-epsilon, epsilon) ts_a, ts_b, a_latest, b_earliest, wait = run_pair( epsilon, gap, offset_a, offset_b, commit_wait) total_wait += wait if ts_b <= ts_a: # B should be AFTER A, but its timestamp isn't errors += 1 if example is None: example = (ts_a, ts_b, a_latest, b_earliest) return errors, total_wait / N_PAIRS, example def main(): print("Clock uncertainty is an INTERVAL, not a point. TrueTime's now() returns") print(f"[earliest, latest] of half-width epsilon = {EPSILON} ms; the true instant is") print("somewhere inside. We order pairs where B reads what A wrote (B happens-after A).") print(f" epsilon (clock uncertainty half-width) = {EPSILON} ms") print(f" real gap from A's commit to B's read = {GAP} ms (deliberately < epsilon)") print(f" causally-dependent pairs run = {N_PAIRS}\n") # One concrete pair, no commit-wait, to see the intervals overlap. rng = random.Random(SEED) oa, ob = rng.uniform(-EPSILON, EPSILON), rng.uniform(-EPSILON, EPSILON) ts_a, ts_b, a_latest, b_earliest, _ = run_pair(EPSILON, GAP, oa, ob, commit_wait=False) print("one pair WITHOUT commit-wait -- A commits at true time 0, B reads it " f"{GAP} ms later:") print(f" A's interval latest (A's commit timestamp) = {a_latest:+.3f} ms") print(f" B's interval earliest = {b_earliest:+.3f} ms") overlap = "OVERLAP" if b_earliest <= a_latest else "disjoint" print(f" B.earliest <= A.latest ? {b_earliest <= a_latest} -> intervals {overlap}\n") # WITHOUT commit-wait: measure the ordering-error rate over many pairs. errors_no, wait_no, example = measure(EPSILON, GAP, commit_wait=False) print("WITHOUT commit-wait -- assign timestamp = interval latest, then check order:") print(f" ordering errors (B's timestamp <= A's) = {errors_no} / {N_PAIRS} " f"({errors_no * 100 / N_PAIRS:.1f}%)") print(f" mandatory wait per transaction = {wait_no:.1f} ms") if example: ex_ts_a, ex_ts_b, _, _ = example print(f" e.g. one violation: A's ts = {ex_ts_a:+.3f} ms, B's ts = {ex_ts_b:+.3f} ms" f" -> B ordered BEFORE A\n") # WITH commit-wait: A holds its write for 2*epsilon before B can read it. errors_yes, wait_yes, _ = measure(EPSILON, GAP, commit_wait=True) print("WITH commit-wait -- A holds its write until true time passes its `latest`, " "THEN B may read:") print(f" ordering errors (B's timestamp <= A's) = {errors_yes} / {N_PAIRS} " f"({errors_yes * 100 / N_PAIRS:.1f}%)") print(f" mandatory wait per transaction = {wait_yes:.1f} ms " f"(= 2 * epsilon = 2 * {EPSILON})\n") # The trade-off: the wait is 2*epsilon, so a better clock buys a shorter wait. print("trade-off -- shrink the clock uncertainty epsilon and the mandatory wait " "shrinks with it:") print(f" {'epsilon (ms)':>14} {'errors WITHOUT wait':>22} {'commit-wait = 2*eps':>22}") for eps in (8.0, 4.0, 2.0, 1.0, 0.5): e_no, _, _ = measure(eps, GAP, commit_wait=False) e_yes, w_yes, _ = measure(eps, GAP, commit_wait=True) assert e_yes == 0, "commit-wait must eliminate ordering errors" print(f" {eps:>14.1f} {f'{e_no}/{N_PAIRS} ({e_no*100/N_PAIRS:.1f}%)':>22} " f"{f'{w_yes:.1f} ms':>22}") print(" a tighter clock (GPS/atomic) makes the timestamps safer AND the wait cheaper.") if __name__ == "__main__": main()