14. Time, Clocks, and Ordering (Lamport, Vector, TrueTime)

In distributed systems, "what happened first?" is a much harder question than it sounds. Wall clocks lie. The real foundation is causality, captured by logical clocks.

14.1 Why physical clocks aren't enough

• Clocks drift (~10ppm typical, so ~30s/month uncorrected).
• NTP corrects but jumps: a clock can go backward when NTP overshoots.
• Network sync has delay; clocks across machines disagree by ms even with NTP, sometimes seconds.
• Cloud VMs share clocks with hosts; sleeping/migrating can jump them.

Famous bugs:

• Cassandra's last-writer-wins lost writes when clocks skewed.
• Cloudflare's leap-second outage (2017) crashed services because system clock went backward.

If you sort events across machines by physical timestamp, you will misorder some.

14.2 Lamport timestamps

Leslie Lamport (1978). Captures causality with a single integer per event.

Algorithm:

• Each node maintains a counter c.
• On any local event: c = c + 1.
• On send: include c in message.
• On receive c_msg: c = max(c, c_msg) + 1.

Properties:

• If event A causally precedes B, then c(A) < c(B).
• The converse is not true: c(A) < c(B) does not imply A → B (could be concurrent).
• Total order: tie-break by node ID.

Useful for: total ordering of events when you accept that "concurrent" events get an arbitrary order.

14.3 Vector clocks

Lamport's flaw: you can't tell concurrent from causally-related. Vector clocks fix this.

Each node i maintains a vector V of N counters (one per node).

Algorithm:

• On local event: V[i] += 1.
• On send: include V.
• On receive V_msg: V[k] = max(V[k], V_msg[k]) for all k; then V[i] += 1.

Comparison:

• V_A < V_B iff V_A[k] ≤ V_B[k] for all k AND V_A ≠ V_B → A causally precedes B.
• Otherwise A and B are concurrent.

Used by: Dynamo, Riak, Voldemort, version vectors in CRDTs.

Cost: O(N) per timestamp where N is number of nodes. Doesn't scale to thousands of writers; people use dotted version vectors or interval tree clocks for that.

14.4 Hybrid Logical Clocks (HLC)

Combines wall-clock time with a logical counter. Useful when you want monotonic timestamps that approximate real time.

Used in: CockroachDB, MongoDB.

HLC = (physical_time, logical_counter). Always monotonic. Roughly tracks wall time. Survives clock skew.

14.5 TrueTime (Spanner)

Google Spanner's secret. The TrueTime API:

• TT.now() → TTInterval[earliest, latest]
• Returns an interval guaranteed to contain the actual current time.

The interval is bounded (~1-7 ms in Google's DCs) thanks to GPS receivers and atomic clocks in every datacenter, with redundancy and outlier rejection.

How Spanner uses it:

• Every transaction gets a commit timestamp from TrueTime.
• After committing, wait out the uncertainty: don't return success until TT.now().earliest > commit_timestamp. This is "commit wait" (~7ms typical).
• Guarantees: if T1 commits before T2 starts (in real time), T1's timestamp < T2's. So a globally consistent snapshot read at time t sees all transactions that committed before t.

This gives Spanner external consistency (strict serializability) globally without a single coordinator.

The cost: ~7ms commit wait on every transaction. Worth it for relational ACID at planet scale.

Open-source equivalent: CockroachDB uses HLC with looser bounds (it can't get atomic clocks); offers serializable isolation but with weaker external-consistency guarantees.

14.6 Snapshot isolation needs MVCC + timestamps

Recall MVCC (chapter 6): rows have version timestamps. A transaction's snapshot = "see versions ≤ my snapshot timestamp."

In a single-leader DB, the leader assigns timestamps. Easy.

In a distributed DB:

• If you use physical clocks, snapshots can be inconsistent (clock skew).
• HLC makes them monotonic.
• TrueTime makes them externally consistent.

This is why Spanner is so impressive: it provides snapshot reads at any timestamp globally.

14.7 Ordering events for the application

When you build a multi-node app, you need ordering for:

• Causality: replies after questions.
• Determinism: rebuilding state from a log requires the same order on all nodes.
• Conflict resolution: which write wins?

Approaches:

• Single-writer per partition: all writes ordered by one leader. Simple and common (Kafka partition, Postgres).
• Lamport timestamps: total order, but no causality detection.
• Vector clocks: causality detection, no total order.
• HLC / TrueTime: total order, approximately matches real time.
• Sequence numbers from a coordinator: simple, single point of failure (or use a fault-tolerant counter via consensus).

14.8 Happens-before (Lamport's relation)

A → B ("A happens before B") iff:

• A and B are on the same node and A is earlier, or
• A is a send and B is the corresponding receive, or
• A → C and C → B (transitive).

If neither A → B nor B → A, they are concurrent. Two concurrent operations can be applied in any order; the system must converge regardless.

This is the foundation of causal consistency, CRDTs, and conflict resolution.

14.9 Practical advice

• Use monotonic clocks for durations (std::chrono::steady_clock, time.monotonic()).
• Don't sort events across nodes by wall-clock. If you must, use HLC or TrueTime.
• Propagate causal context in headers (request IDs, trace IDs, vector clocks). Lets downstream systems reason about ordering.
• Single-writer when you can. Saves you from needing logical clocks at all.
• Document your clock model. A DB that says "eventual consistency" without specifying what it does about concurrent writes is hiding ambiguity.

14.10 Trace IDs and distributed tracing

A distant cousin of logical clocks. A unique ID propagates through every service handling a request. Spans (sub-operations) attach to it.

Standards: OpenTelemetry, W3C Trace Context (traceparent header).

You don't usually need vector clocks; you do almost always need trace IDs.

14.11 Example: detecting concurrent writes in Dynamo

Two clients update the same shopping cart:

• Client A reads cart (vector [a:1]), adds item, writes back with [a:2].
• Client B reads cart concurrently (also [a:1]), adds item, writes back with [a:1, b:1].

Now there are two versions: [a:2] and [a:1, b:1]. Neither dominates. They're concurrent — Dynamo keeps both as "siblings"; on next read, the application merges (e.g., union of cart items).

LWW (using wall clock) would silently drop one. Dynamo prefers explicit conflict.

Key takeaways

• Wall clocks lie. Use monotonic for durations.
• Lamport timestamps give total order; vector clocks detect concurrency.
• HLC merges monotonic + physical for practical ordering.
• TrueTime is Spanner's killer feature: bounded clock uncertainty enables external consistency.
• Single-writer per partition removes the need for fancy clocks. Use it when you can.