Working with Time and Ordering
1. Understanding Physical Clocks
Source Accuracy Notes NTP 1-50 ms over WAN Stratum hierarchy; can jump backward PTP (IEEE 1588) sub-µs LAN Hardware timestamping GPS / Atomic ns Required for Spanner TrueTime System.currentTimeMillis()Wall clock; NOT monotonic Use for display only System.nanoTime() / CLOCK_MONOTONICMonotonic Use for elapsed time
Warning: Never use wall-clock time to enforce ordering or correctness — clocks drift, jump, and lie.
2. Understanding Logical Clocks (Lamport timestamps)
Rule Action Local event L = L + 1 Send msg L = L + 1; attach L Recv msg(L_msg) L = max(L, L_msg) + 1 Property a → b ⟹ L(a) < L(b) (one direction only)
Example: Lamport clock
public class LamportClock { private long counter = 0 ; public synchronized long tick () { return ++ counter; } public synchronized long onReceive ( long msgTs ) { counter = Math. max (counter, msgTs) + 1 ; return counter; } }
3. Understanding Vector Clocks
Aspect Detail Structure VC = [c₁, c₂, …, cₙ] one entry per node Compare VC₁ < VC₂ iff ∀i VC₁[i] ≤ VC₂[i] and ∃j VC₁[j] < VC₂[j] Concurrent Neither VC₁ < VC₂ nor VC₂ < VC₁ Cost O(n) per message Used By Dynamo, Riak, Voldemort
4. Understanding Hybrid Logical Clocks (HLC)
Property Detail Combines Physical (NTP) + logical counter Format (pt, l) — wall-clock + logical tick Bound Drift-bounded, monotonic Used By CockroachDB, YugabyteDB, MongoDB
5. Implementing Happened-Before Relationship
Rule Definition Same process a before b in program order ⟹ a → b Send/receive send(m) → recv(m) Transitive a → b ∧ b → c ⟹ a → c Concurrent ¬(a → b) ∧ ¬(b → a) ⟹ a ∥ b
6. Handling Clock Skew and Drift
Issue Mitigation Skew Periodic NTP sync; slewing (gradual adjust) Drift Rate-adjusted clocks (chronyd) Backward jumps Use CLOCK_MONOTONIC Leap seconds Smear (Google) or step Bounded uncertainty Spanner TrueTime returns interval [earliest, latest]
7. Using Time for Event Ordering
Approach Order Strength Wall clock Approximate; unsafe for correctness Lamport Total order extending happened-before Vector clock Detects concurrency HLC Causally consistent + close to wall time TrueTime External consistency (Spanner)
8. Implementing Causal Ordering
Step Action 1 Tag each message with sender's vector clock 2 Receiver buffers msg until VC dependencies satisfied 3 Deliver in causal order; merge VCs
9. Understanding Total vs Partial Ordering
Type Property Mechanism Partial Order Some events comparable, others concurrent Vector clocks Total Order Every pair comparable Lamport (with tie-break by node id), consensus log Total Order Broadcast All nodes deliver msgs in same order Atomic broadcast (Paxos/Raft log)
10. Working with Timestamps in Distributed Transactions
Approach System TrueTime (commit wait) Spanner — wait out uncertainty before commit HLC CockroachDB, YugabyteDB Centralized timestamp oracle TiDB (TSO), Percolator MVCC snapshot PostgreSQL, MySQL InnoDB