Distributed Systems Time & Order

Clock Synchronization

Why physical wall-clocks cannot be trusted for event ordering in distributed systems — NTP drift, logical clocks, Lamport timestamps, hybrid logical clocks, and TrueTime.

⏱ 11 min read

What it is

Clock synchronization is the problem of maintaining consistent time or event ordering across nodes in a distributed system. Physical clocks (wall clocks) on independent machines drift relative to each other — a server's clock may run slightly fast or slow, and NTP corrections cause non-monotonic jumps. Because events on different machines cannot be reliably ordered by wall-clock timestamps alone, distributed systems need clock synchronization protocols or logical alternatives to establish causally correct event ordering.

Why it exists

Many operations depend on knowing the order of events across machines: database snapshot isolation requires a consistent timestamp for reads, distributed caches need to invalidate stale entries, audit logs must reflect true causality, and conflict resolution in replicated systems requires knowing which write came "later". Wall-clock timestamps are unreliable for these purposes because clock drift between machines can be tens of milliseconds (NTP) to hundreds of milliseconds (VMs), easily exceeding the latency between causally related events.

When to use

Ordering events across distributed nodes for audit logs, debugging, or causality tracking.
Implementing snapshot isolation in distributed databases (requires consistent timestamps or logical equivalents).
Conflict detection in multi-leader replication or CRDTs.
Implementing bounded staleness or external consistency guarantees.

When not to use

Wall-clock timestamps are fine for human-readable logging and monitoring where millisecond precision is not critical for correctness.
Lamport clocks add complexity without benefit if causal ordering is not needed for the use case.

Typical architecture

Lamport Clock Algorithm
════════════════════════
Rules:
  1. Each node maintains counter L, initially 0.
  2. Before each event, increment L: L = L + 1.
  3. When sending message, attach current L.
  4. On receiving message with timestamp T:
     L = max(L, T) + 1

Example:
  Node A          Node B          Node C
  L=1: event a1   │               │
  L=2: send(B)──►L=3: event b1   │
                  L=4: send(C)──────────►L=5: event c1
  L=3: event a2   │               L=6: event c2

  Lamport clock gives partial order: if a→b then L(a) < L(b)
  But L(a) < L(b) does NOT imply a→b (concurrent events
  may have arbitrary ordering).

Hybrid Logical Clock (HLC)
═══════════════════════════
  l (logical): max of wall-clock and peer timestamps
  c (counter): tie-breaking counter within same wall-clock second

  On send/local event:
    l = max(l, now); if l == old_l then c++ else c=0
    send (l, c)

  On receive (l', c'):
    if l' == l: c = max(c, c') + 1
    elif l' > l: l = l'; c = c' + 1
    else: c++

  HLC: close to wall-clock time, yet causally ordered ✓

Pros and cons

Pros of logical clocks

Lamport timestamps are simple to implement and provide a consistent partial ordering.
HLC stays close to wall-clock time (useful for TTLs and human-readable timestamps) while maintaining causal correctness.
No dependency on hardware or external time service for correctness.

Cons

Lamport timestamps only give partial order — concurrent events get arbitrary order, not a true "happened before" relationship.
Vector clocks (the complete solution) have O(n) space overhead per event, impractical for large clusters.
TrueTime requires specialised hardware (GPS + atomic clocks) not available outside Google's data centres.
NTP accuracy (~1–10 ms in LAN, ~50 ms on internet) is insufficient for sub-millisecond event ordering.

Implementation notes

NTP and PTP: NTP (Network Time Protocol) synchronises clocks to within ~1–10 ms on a local network and ~50 ms on the internet. PTP (Precision Time Protocol, IEEE 1588) achieves sub-microsecond accuracy on dedicated hardware. Neither provides the guarantees required for strict event ordering in distributed databases.

Google Spanner's TrueTime API provides an interval [earliest, latest] rather than a point-in-time. The system waits until the uncertainty window passes before committing a transaction (commit_wait), guaranteeing that any transaction committed after this wait will have a strictly later timestamp than the current transaction. This enables external consistency (serialisability that respects real time) without coordination across data centres. The uncertainty bound is typically 1–7 ms, achieved using GPS receivers and atomic clocks in every data centre.

Hybrid Logical Clocks (used in CockroachDB) provide a practical middle ground: timestamps are close to wall-clock time (for compatibility with TTL, user-visible timestamps) but carry a logical component that ensures causal ordering even if physical clocks drift. CockroachDB uses HLC to implement serialisable snapshot isolation across a distributed cluster without requiring atomic clocks.

Common failure modes

NTP step correction: NTP makes a step adjustment (clock jumps backward), causing timestamp inversion and TTL/lease expiry bugs.
Clock drift on VM live migration: when a VM is migrated between hypervisors, the guest clock may drift by hundreds of milliseconds.
Distributed lock TTL expiry due to clock difference: a lock server and a lock holder have differing clocks; from the server's perspective the TTL expired while the holder believes it still holds the lock.
Causality violations in audit logs: events logged with wall-clock timestamps appear out of order when logs from two servers are merged.

Decision checklist

Do you rely on wall-clock timestamps for ordering guarantees? If so, what is your clock accuracy budget?
Would logical clocks (Lamport or HLC) serve your ordering needs without physical clock dependency?
Are your TTL and lease durations much larger than worst-case clock drift between nodes?
Is NTP chrony/ntpd running and monitored for drift on all nodes?
Do you need full causal ordering (requiring vector clocks) or partial order (Lamport clocks sufficient)?

Example use cases

CockroachDB using HLC for serialisable distributed transactions without atomic clocks.
Google Spanner using TrueTime for globally distributed serialisable transactions with external consistency.
Cassandra using wall-clock timestamps for last-write-wins conflict resolution (and why timestamp skew causes lost updates).
Distributed tracing systems (Jaeger, Zipkin) using Lamport-style logical timestamps alongside wall-clock times to reconstruct causally ordered traces.

Vector Clocks — extend Lamport clocks to capture full causality between nodes, not just partial order.
Distributed Locking — clock drift is a primary hazard for TTL-based distributed locks.
Split Brain Problem — lease expiry due to clock skew can trigger unnecessary leader elections.