# DDIA Ch. 10: a backward NTP step reorders wall-clock timestamps; an HLC stays monotonic ## Concept One node performs a causal chain of writes — event `k` reads `x=k-1` and writes `x=k`, so each event provably happens-*after* the last. Timestamp the chain two ways: plain physical (wall-clock) time, and a **Hybrid Logical Clock (HLC)**. Partway through, NTP decides the clock is fast and **steps it back 100 ms**. The plain physical timestamps then go **non-monotonic**: event 5 commits at **940 ms** though its own cause, event 4, committed at **1030 ms** — a *later* event with a *smaller* timestamp. Sorting the events by physical time places `e5, e6, e7` **before** `e4`, the write they read — causality inverted — and a snapshot read in the gap sees the effects but not the committed cause. The HLC applies one rule per event — `pt = max(pt_last, phys); counter += 1 if pt unchanged else 0` — and its timestamps stay **strictly monotonic** (`(1030,c0) < (1030,c1) < …`), preserving the causal order while staying within the jump's bound of physical time. "Our clocks are NTP-synced, so timestamps are ordered" is wrong the instant the clock steps back; the HLC's max-and-increment rule buys the ordering back with no special hardware. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 10 — *Consistency and Consensus*, §"Hybrid logical clocks": > A hybrid logical clock combines a physical timestamp with a logical counter, > giving it the best of both worlds: it stays close to the actual time of day, > while also preserving the causal ordering of events like a Lamport clock. The book presents the HLC (used by CockroachDB) as the clock that keeps physical time meaningful *and* never lets it regress. Here you watch a real backward step break the plain wall-clock ordering, then watch the HLC absorb the same step into its counter and keep the causal order intact. ## Prerequisites The whole result turns on one line: `pt = max(seen, physical); bump the counter on a tie or regression`. These place *why*; one line each, with a free resource, and the one that carries the result flagged. 1. **Physical vs logical clocks** — a physical clock reports civil time and is corrected by an external authority (NTP); a logical clock (Lamport) is a counter that only encodes happened-before, with no tie to real time. An HLC fuses the two. It shows up as the `(pt, counter)` pair: `pt` is physical, `counter` is logical. 2. **NTP can step a clock backward** — when a clock is too far off to slew away gently, NTP *steps* it, instantly, and the step can go **back**. That backward step is the whole event. It shows up as `clock.step(-100)` mid-chain. 3. **Monotonicity & causal order** — an ordering source is only valid if a later causal event never gets a smaller timestamp; plain physical time loses this property the moment it is stepped back. It shows up as `e5 (940) < e4 (1030)` inverting the sort. 4. **The HLC update rule** *(carries the result)* — on every event `pt = max(pt_last, phys)`; if `pt` did not advance (a tie, or physical time regressed) `counter += 1`, else `counter = 0`; `receive` first takes the max with the remote HLC. `pt` never decreases and the counter breaks ties, so the `(pt, counter)` pair is strictly monotonic. It shows up as `e5` becoming `(1030, c1)` instead of going back to `940`. ### Where to learn the prerequisites - **Physical vs logical clocks and the HLC rule (#1, #4):** DDIA §"Hybrid logical clocks" and §"Sequence number ordering"; Kulkarni et al., "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases" (2014) — the paper that defines the HLC and proves its bounds. - **NTP stepping and monotonicity (#2, #3):** the `ntpd` docs on the step/slew threshold; the Ch. 9 exercise `monotonic-vs-wallclock` for what a backward step does to a *duration*, which this exercise's ordering failure is the sibling of. If only one is new, make it #4 — `max`-and-increment is the entire reason the HLC stays monotonic while tracking physical time. ## Environment macOS 26.5.2 (Darwin 25.5.0), arm64; Python 3.15.0a8, standard library only; no Docker; the physical clock and its backward step are modeled by a mock, so the transcript is fully deterministic. ## Mental model An HLC is **physical time that is never allowed to go backward.** It carries a logical counter alongside the physical reading, and that counter does two jobs: it breaks ties when two events read the same physical millisecond, and it absorbs a backward jump — when physical time tries to regress, the HLC holds `pt` where it was and bumps the counter instead. So the HLC still *tracks* real time (its `pt` is a real millisecond value, within a bound of the wall clock) yet stays **monotonic**, because the pair `(pt, counter)` — compared lexicographically — can only ever increase. - **Plain physical timestamp** — read straight off the wall clock. Correct and ordered *only if nothing moved the clock*. An NTP step backward makes a later event's timestamp smaller than an earlier one's; the ordering is now a lie. - **HLC** — `(pt, counter)`. On each event `pt = max(pt_last, phys)`; if physical time carried `pt` forward the counter resets to 0, otherwise it increments. `receive(remote)` takes the max with the remote HLC first, so a message's causality crosses the wire. The pair never decreases. Both stamp the identical causal chain; only the second keeps the order honest across the step. The whole thing is one script, `code/hybrid_logical_clock.py`. ## Setup ``` cd study/ddia/ch10/code python3 hybrid_logical_clock.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — the physical timestamps of the causal chain **Predict.** Seven causal writes, physical clock starting at 1000 ms and normally advancing +10 ms per event — but NTP steps the clock **back 100 ms** between event 4 and event 5. What physical timestamp does event 5 get, and how does it compare to event 4's? **Observe.** ``` e1 x:=1 physical_ts = 1000 ms e2 x:=2 physical_ts = 1010 ms e3 x:=3 physical_ts = 1020 ms e4 x:=4 physical_ts = 1030 ms e5 x:=5 physical_ts = 940 ms e6 x:=6 physical_ts = 950 ms e7 x:=7 physical_ts = 960 ms The NTP step lands between e4 and e5: e4 committed at physical_ts = 1030 ms e5 committed at physical_ts = 940 ms (clock was stepped BACK 100 ms) e5 happens-AFTER e4 (it read x=4, wrote x=5), yet 940 < 1030: a LATER event carries a SMALLER physical timestamp -- NON-MONOTONIC. ``` **940 < 1030 — a later event with a smaller timestamp.** The clock ran forward to 1030, NTP stepped it back to ~930, and event 5 read 940. Event 5 causally happens-after event 4, but its physical timestamp is *earlier*. The timestamps are no longer a valid order. ### Step 2 — the failure: order the events by physical timestamp **Predict.** A timestamp-ordered log (or a snapshot) sorts these events by their physical timestamp. What order comes out — and where do e5, e6, e7 land relative to e4, the write they read? **Observe.** ``` sorted by physical_ts (what a timestamp-ordered log / snapshot would do): physical_ts = 940 ms e5 x:=5 physical_ts = 950 ms e6 x:=6 physical_ts = 960 ms e7 x:=7 physical_ts = 1000 ms e1 x:=1 physical_ts = 1010 ms e2 x:=2 physical_ts = 1020 ms e3 x:=3 physical_ts = 1030 ms e4 x:=4 causal order actually performed : e1 -> e2 -> e3 -> e4 -> e5 -> e6 -> e7 order by physical timestamp : e5 -> e6 -> e7 -> e1 -> e2 -> e3 -> e4 e5, e6, e7 sort BEFORE e4 -- their cause. Sorting by physical time places the effect ahead of the write it read: causality INVERTED. a snapshot read at physical_ts T = 1025 ms (writes with ts <= T are visible): visible: e1, e2, e3, e5, e6, e7 -> e5, e6, e7 are visible but e4 (which they causally depend on) is NOT. The snapshot shows x=7 while the write that set x=4 is missing: a state that never existed. A committed earlier-in-causal-order write is lost. ``` **The sort puts effects before their cause.** `e5, e6, e7` — each of which read a value written by `e4` — sort ahead of `e4`. Worse, a snapshot read at `T = 1025` sees `e5, e6, e7` (their ts ≤ 1025) but *not* `e4` (ts 1030 > T): it exposes `x=7` while the write that produced the chain's middle is invisible. Nothing errored; the ordering is just wrong. ### Step 3 — the same chain, timestamped by the HLC **Predict.** Same seven events, same backward step, but each stamped by the HLC rule `pt = max(pt_last, phys); counter += 1 if pt unchanged else 0`. What HLC does event 5 get — does it go back to 940, or something else? Are the HLC timestamps strictly increasing? **Observe.** ``` e1 x:=1 physical_ts = 1000 ms hlc = (1000, c0) e2 x:=2 physical_ts = 1010 ms hlc = (1010, c0) e3 x:=3 physical_ts = 1020 ms hlc = (1020, c0) e4 x:=4 physical_ts = 1030 ms hlc = (1030, c0) e5 x:=5 physical_ts = 940 ms hlc = (1030, c1) e6 x:=6 physical_ts = 950 ms hlc = (1030, c2) e7 x:=7 physical_ts = 960 ms hlc = (1030, c3) Across the jump the HLC does NOT go back: e4 hlc = (1030, c0) e5 hlc = (1030, c1) (pt held at 1030, counter bumped 0 -> 1) physical time tried to regress, so pt stayed put and the counter absorbed the step. e5, e6, e7 keep climbing on the counter: (1030,c1) < (1030,c2) < (1030,c3). HLC timestamps strictly increasing (lexicographic (pt, counter))? True Ordering the events by HLC reproduces the exact causal order e1..e7. ``` **Event 5 is `(1030, c1)`, not `940`.** When physical time tried to regress, `max` held `pt` at 1030 and the tie-branch bumped the counter to 1. The next two events keep climbing on the counter — `(1030,c1) < (1030,c2) < (1030,c3)` — so the HLC timestamps are **strictly increasing** and sorting by them reproduces the true causal order `e1..e7`. ### Step 4 — receive(): causality carried across a message **Predict.** A peer node B, whose clock is *ahead*, sends a message stamped `hlc = (1200, c4)`. Our node (whose HLC is `(1030, c3)`, physical clock 960 ms) applies `receive()`. What does our HLC become — and is it strictly greater than the message's own stamp? **Observe.** ``` our physical clock now = 960 ms message arrives from B stamped hlc = (1200, c4) (B is ahead) our HLC before receive = (1030, c3) our HLC after receive = (1200, c5) it jumped up to B's physical part (1200) and set counter = 5: strictly greater than the message's own stamp, so the receipt is ordered AFTER the send even though our local physical clock never read that high. ``` **Our HLC jumps to `(1200, c5)`.** `receive` takes `max(pt_last, remote_pt, phys) = 1200`, and because that came from the remote, sets `counter = remote_counter + 1 = 5`. The receipt is now strictly greater than the send's `(1200, c4)`, so the message's causality is preserved even though our own physical clock never read as high as 1200. This is how the HLC carries happened-before across a wire, exactly like a Lamport clock. ### Step 5 — bounded skew: the HLC still tracks physical time **Predict.** After absorbing a 100 ms backward step, how far can the HLC's `pt` run *ahead* of the true wall clock? Bounded, or does it drift without limit? **Observe.** ``` Right after the backward step, before the remote message: e7 physical_ts = 960 ms e7 hlc.pt = 1030 skew = hlc.pt - physical_ts = 70 ms The HLC ran at most 70 ms ahead of the wall clock -- exactly the part of the 100 ms backward step not yet re-covered by real time. The counter, not an unbounded drift, carried the ordering; the skew is bounded by the jump. ``` **70 ms — bounded by the jump.** At `e7` the wall clock reads 960 ms but the HLC's `pt` is still 1030 ms: 70 ms ahead, the part of the 100 ms step that real time has not yet caught back up to. The counter, not an ever-growing physical offset, carried the ordering across the gap, so the HLC never drifts unboundedly from physical time. ## What you should see - Physical timestamps go **non-monotonic**: `e5 = 940 ms < e4 = 1030 ms`, a later event with a smaller timestamp. - Sorting by physical time yields `e5 → e6 → e7 → e1 → e2 → e3 → e4` — effects before their cause — and a snapshot at `T = 1025` shows `e5, e6, e7` but not `e4`. - HLC timestamps are **strictly increasing**: `(1000,c0) < (1010,c0) < (1020,c0) < (1030,c0) < (1030,c1) < (1030,c2) < (1030,c3)`; sorting by them reproduces the causal order. - `receive()` from a peer at `(1200, c4)` lifts our HLC to `(1200, c5)` — strictly after the send. - The HLC's skew above the wall clock stays **bounded** — 70 ms, the unrecovered part of the 100 ms step. ## Why From first principles, plain physical time has an **external authority** — NTP — that is *allowed to move it backward*. That is not a bug in NTP; it is its job: when the local clock is too far from UTC to slew away gently, it steps it, possibly back. But an ordering source must be *monotonic along causality* — a later event may never receive a smaller value — and a quantity someone else can decrement has forfeited that property. So the moment the step lands, two events on either side of it are stamped from *different calibrations of the same dial*; comparing them is meaningless, and when the step is backward and larger than the real elapsed time, the later event's timestamp comes out smaller. That is exactly `e5 = 940 < e4 = 1030`, and it is why sorting inverts causality and the snapshot loses a committed write. The HLC fixes this by clamping: on every event it sets `pt = max(pt_last, phys)`. The `max` is the whole trick — it makes `pt` a **running maximum** of every physical reading ever seen, and a running maximum can never decrease. When physical time moves forward, `pt` follows it and the counter resets to 0 (a fresh millisecond, no tie to break). When physical time *regresses* (or two events share a millisecond), `pt` stays put — `max` ignores the smaller value — and the counter `+= 1`. So a backward step doesn't invert anything; it just spends counter increments. Because `(pt, counter)` is compared lexicographically and `pt` is monotonic with the counter breaking every tie, the pair is **strictly increasing** by construction — a total order that never regresses. And since `pt` is still a real max of physical readings, it stays *close* to the wall clock: at most the un-recovered part of the last backward step ahead of it (70 ms here). `receive` extends the same `max` to remote timestamps, so happened-before crosses messages too — the HLC is a Lamport clock whose "counter" is anchored to real time. **The boundary — the HLC matters exactly when the clock jumps or ties.** If NTP only ever *slews* the clock forward and it never steps back (and no two events share a physical instant), plain physical timestamps stay ordered and the counter sits at 0 forever — the HLC reduces to the wall clock and buys you nothing. Its value shows up precisely at backward steps and ties. And note what it does *not* give you: the HLC bounds — it does not eliminate — reliance on rough physical sync. `pt` staying "close" to real time depends on the clocks being roughly synced; a wildly wrong clock still produces a large-but-monotonic `pt`. The HLC guarantees a monotonic *order*, not an accurate *instant*. ### Go deeper 1. **HLC vs TrueTime/commit-wait.** Spanner's commit-wait (the Ch. 9 `commit-wait` exercise) *waits out* the clock's uncertainty interval to guarantee external consistency — it pays latency for a stronger guarantee. The HLC is **wait-free**: it never blocks, but it only preserves the causal order it actually *observes* (through process order and messages), not the real-time order of two events that never communicated. Weaker guarantee, zero wait — compare the two exercises side by side. 2. **Flip the step forward.** Make NTP step the clock *forward* 100 ms instead. Physical timestamps stay ordered (no inversion), and the HLC's counter never leaves 0 — confirm the boundary above by watching the HLC add nothing. 3. **Two events, same millisecond.** Fire two events at the identical physical time with no step at all, and watch the counter alone (`(t,c0)` then `(t,c1)`) impose an order the physical clock could not.