Time & Clocks in Distributed Systems

Why wall clocks alone cannot order two datacenter writes

Raft left 100 ranges with 100 independent terms that never compare, and a withdrawal plus a deposit 150ms apart still needs a real order. Two servers disagree by 150ms from NTP drift, where NTP means the standard protocol that nudges clocks toward reference time but never tightly. Timestamps alone cannot say whether write A happened before write B, and a restarted phone can jump a year. Ordering needs logical clocks, meaning counters advanced by message causality rather than wall time. Picture mail postmarks from two towns with unsynchronized stamp machines: the earlier postmark may simply be the faster stamper, not the earlier letter.

NTP sync: ±1–100ms typical, jumps after VM pause
Spanner TrueTime: interval [earliest, latest] with bounded uncertainty (7ms)
Hybrid: wall time + logical counter for local ordering

TrueTime, meaning Google's clock API that returns a bounded uncertainty interval from atomic clocks plus GPS, and HLC, meaning Hybrid Logical Clock combining wall time with a Lamport-style counter, exist precisely because raw wall time mixes recency with causality and answers neither reliably.

How Lamport, vector, and hybrid clocks divide ordering labor

The naive fix trusts timestamps with greater-than comparisons, which fails the moment skew exceeds event spacing. Lamport clocks, meaning one counter per node ticked on send and max-plus-one on receive, give a total order consistent with causality but cannot detect it. Vector clocks, meaning one counter per node kept as a vector so element-wise comparison reveals happened-before versus concurrency, detect causality at O(N) memory. TrueTime and HLC add wall-closeness for database timestamps.

The 150ms ledger flip that billed a customer for money never owed

Two data-center regions, an ocean apart, process one account. The east region records a $100 withdrawal at 10:00:00.120 while the west records a $100 deposit slightly earlier in real time, but the western clock runs 150ms fast so its stamp reads later. Sorted by wall time, the ledger shows withdrawal before deposit and flags an overdraft that never existed. The bug hides for months because NTP, the standard time-sync protocol, is usually close enough, until a virtual-machine pause or leap second makes it very much not.

True order:   deposit (t=100ms) ──► withdraw (t=120ms)   → balance never negative
Observed:     withdraw stamped 10:00:00.120, deposit stamped 10:00:00.200
              (West clock +150ms fast) → sorted order flips → false overdraft

NTP reality:  ±1ms on LAN, ±10–100ms across regions, unbounded jump after pause
Spanner TrueTime: returns interval [earliest, latest], uncertainty ~7ms by default
HLC: physical clock + logical counter → monotonic even when NTP steps backward

Tracing one Lamport exchange where equal stamps prove nothing

You and a friend each keep a counter from 0. Before anything local you tick up; on receiving a message you jump to one past the larger of yours and theirs. That rule guarantees that if A caused B, A's stamp is smaller, which is the cheapest ordering promise in distributed systems. Its limit is symmetric: equal stamps with no message path mean concurrency, not simultaneity, and no comparison can recover which came first.

A: event a1 → L=1, sends (msg, L=1)
B: receives → L = max(0,1)+1 = 2, event b1 → L=3, replies (msg, L=3)
A: receives → L = max(1,3)+1 = 4
Order L: a1(1) < b1(3), respects causality.
But: A:2 and B:2 can coexist with no causal link, equal stamps prove nothing.
Tie-break total order: compare (L, nodeId) → (2,A) < (2,B) always.

Picking NTP, HLC, or TrueTime by the question you must answer

Stamping writes with a clock that survives NTP stepping backward

Databases want stamps close to wall time so yesterday's-rows queries work, plus monotonicity, meaning never decreasing, so a retry never sorts before its original. HLC, the Hybrid Logical Clock combining physical time with a logical counter, gives both: take the maximum of wall time, last stamp, and any incoming stamp, tick the counter on ties, reset it when wall time genuinely advances.

HLC state: (pt = physical time, l = logical counter, node id)
  local event:  pt = now();  l = (pt == last.pt) ? last.l + 1 : 0
  receive(m):   pt = max(now(), last.pt, m.pt)
                l  = max(last.l, m.l) + 1  if pt ties the max, else 0
  stamp = (pt, l, nodeId); sorts by pt, then l, then id

NTP steps backward 200ms? pt freezes at last.pt, l keeps ticking → stamps still grow.
CockroachDB: HLC timestamps on every write + closed-timestamp protocol so reads
  never block on uncertainty; commit-wait replaced by bounded staleness reads.

Sizing the counter: 16 bits per millisecond survives 65k causally linked events in one ms. Past that, stall the minter exactly like a Snowflake sequence overflow, meaning a time-ordered ID generator pausing when its per-millisecond slots run out. Same stall, same reason: time ran out of room.

Matching each timestamp question to the cheapest clock that answers it

Every timestamp choice bills a different currency. NTP, the standard sync protocol, bills nothing and guarantees nothing. HLC bills bytes per stamp and guarantees monotonic causal order. TrueTime, Google's bounded-uncertainty clock, bills hardware plus milliseconds of commit-wait and guarantees external consistency, meaning global real-time ordering visible to any later reader. Rejected alternative: one global timestamp oracle handing out every stamp. Each write then waits a round trip (about 1ms on LAN, 70ms cross-region), the oracle caps near 100k stamps per second, and its outage freezes every writer at once. Match currency to the query that must be right: causality needs Lamport or vector, concurrent-edit detection needs vectors with sibling retention, and global read-after-commit needs HLC causal stamps or TrueTime commit-wait.

Reconciling phone and laptop carts that both edited offline

Phone and laptop edit one cart offline: phone adds headphones at vector [P:2, L:1], meaning two phone events and one laptop event seen, while laptop removes the case at [P:1, L:2]. Neither dominates, since each leads on one coordinate, so the store keeps both siblings instead of picking a winner. Last-writer-wins by wall clock would silently delete someone's edit; vectors preserve both for merge logic or the shopper to decide.

Start: cart v0 = [P:0, L:0] = {case}
  phone: add headphones → [P:1, L:0] = {case, headphones}
  laptop (offline, saw v0): remove case → [P:0, L:1] = {}
  sync: compare [1,0] vs [0,1]; neither dominates → CONCURRENT siblings kept
  merge (add-wins set): {case removed} ∪ {headphones added} = {headphones}
  next write bumps to [P:2, L:2] dominating both; history collapses to one truth

Dynamo/Riak rule: siblings on read, reconcile on write, never silent LWW for user data.

Pruning reality: vectors grow with every replica that ever wrote. Dotted version vectors, meaning one dot per writer instead of full history, plus read-repair collapsing keep stamps small. Unbounded vectors are the Dynamo footnote everyone skips until production.

Waiting out uncertainty in ten lines that buy global ordering

TrueTime commit-wait, meaning stamping at the top of the uncertainty interval then sleeping until that time provably passed, looks deep until written out: stamp at latest, apply locally, sleep until earliest passes the stamp, then acknowledge. Every later reader anywhere observes the write, because any transaction starting afterwards in real time necessarily stamps higher. The sleep is the entire price of external consistency.

function commitWithTrueTime(write):
  [earliest, latest] = TrueTime.now()   // e.g. [10.000, 10.007], ε ≈ 7ms
  stamp = latest                        // commit timestamp s = 10.007
  apply write locally with stamp s
  sleep until TrueTime.now().earliest > s   // ~7ms: uncertainty passes provably
  return s to client                    // any reader with time > s sees the write

Invariant: if txn B starts (in real time) after txn A commits, stamp_B > stamp_A.
  → global snapshots read at timestamp T see exactly the writes committed before T.
CockroachDB without atomic clocks: HLC + closed timestamps approximate this;
  bounded-staleness reads wait seconds, not milliseconds, on the slow path.

Reading your own profile edit from the region that has not caught up

You update your profile in the eastern US region, the CDN routes your next read west, and your old name stares back: monotonic reads, meaning a session never moving backward in time, violated. Fixes escalate by strength: sticky-route the session to the writer region briefly, attach the write's HLC stamp and make replicas wait until applied past it, or read from the leader or a quorum, meaning an overlapping majority, when freshness is mandatory. Read-your-write is a per-session promise you engineer, not a network gift.

write W stamped (pt=100, l=3) in east; client carries stamp to west replica
  west applied through (pt=99, l=9) → W not yet visible → replica WAITS, then serves
  wait bound: replication lag (ms–s), not TrueTime ε; HLC stamps order without clocks agreeing.
CockroachDB follower reads: serve at a closed timestamp (slightly stale, always consistent)
  or gateway to the leaseholder (fresh, one RPC further). Say which your SLA needs.

Expiring leases safely when the clock holding them lies

Leader leases and lock TTLs, meaning time-boxed ownership grants, expire by wall clock, so 150ms of skew lets two nodes each believe they hold the same lease. The naive expiry trusts NTP, the standard sync protocol, and double-grants under every pause. The working guard bounds skew explicitly: leases last an interval minus maximum assumed drift, holders renew at a third of the interval, and fencing tokens, meaning monotonically increasing generations checked on every write, reject stale holders even when clocks disagree. TrueTime, Google's bounded-uncertainty clock, makes the bound explicit near 7ms; HLC, the Hybrid Logical Clock, keeps monotonicity but cannot bound wall error, so pair it with fencing rather than tighter timeouts.

Lease 10s, skew bound 7ms (TrueTime ε): holder renews at 3s, stops serving at 10s − ε
  stale holder at 10.005s real: fencing token 41 < current 42 → writes rejected anyway
  NTP-only expiry: 150ms skew → two holders overlap 150ms, both write, last wins blindly
  rule: clocks grant speed, fencing grants safety; expiry without fencing is hope.

Never trust a timestamp again (without asking which clock)

HLC stamps order every write causally and fencing tokens reject the stale leaseholder at token 41 versus 42. Yet those stamps travel on messages between nodes that never elected a leader. What carries versioned aliveness to 3,000 machines with no coordinator and no voting?