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_MONOTONIC | Monotonic | 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 |