Clocks & Ordering · System Design Lab

Two kinds of clock, and the one you keep misusing

Time-of-day clock (System.currentTimeMillis, time.time()) returns wall-clock time synchronised to NTP. It can jump backwards when NTP corrects drift, when a leap second is smeared or applied, or when a VM is restored from a snapshot.

Monotonic clock (System.nanoTime, time.monotonic()) only ever moves forward. Its absolute value is meaningless — it's only useful as a difference.

The rule that follows:

How wrong are clocks, really?

With good NTP inside a datacenter: typically under a millisecond, occasionally tens of milliseconds. Across the public internet or on a busy VM: tens to hundreds of milliseconds. When NTP is misconfigured, firewalled, or the machine has just booted: seconds to years.

Nothing announces the drift. A machine with a clock 5 seconds fast looks entirely healthy and happily wins every last-write-wins race in the cluster.

This is why the replication lesson called last-write-wins a data loss policy: it doesn't resolve conflicts by recency, it resolves them by whose clock is furthest ahead.

Happens-before: ordering without clocks

Leslie Lamport's insight is to stop asking about time and ask about causality.

Event A happens-before B (written A → B) if:

A and B are in the same process and A came first, or
A is sending a message and B is receiving it, or
there's a chain: A → C → B.

If neither A → B nor B → A, the events are concurrent — not "at the same time", but causally independent. Nothing either one did could have influenced the other, so any order is equally valid.

That's the key reframing: you rarely need to know what time something happened. You need to know what it could have depended on.

Lamport timestamps

The minimal implementation:

Each process keeps a counter.
Increment before every event.
Send the counter with every message.
On receive: counter = max(local, received) + 1.

Now A → B implies L(A) < L(B). Total ordering, tiny overhead, one number.

The limitation: the converse doesn't hold. L(A) < L(B) does not mean A happened before B — they might be concurrent. Lamport timestamps give you a consistent total order, but they cannot detect concurrency, which is exactly what you need to know when resolving a conflict.

Vector clocks

Keep one counter per node instead of one overall. Node i increments its own entry on each event, and on receiving a message takes the element-wise max.

Now comparison is genuinely informative:

V(A) < V(B) element-wise → A happened before B
V(B) < V(A) → B happened before A
Neither → concurrent, and you have a genuine conflict to resolve

This is what Dynamo-style stores use to detect siblings and hand them to the application rather than silently discarding one. (In replication contexts they're usually called version vectors — same mechanism, tracking replicas rather than processes.)

The cost: size grows with the number of nodes, and entries for departed nodes need pruning. For a cluster of 5 that's trivial; for millions of mobile clients each acting as a replica, it's not.

	Size	Detects concurrency?	Total order?
Wall clock	1 value	No	Yes, but wrong
Lamport	1 counter	No	Yes
Vector clock	O(nodes)	Yes	Partial order
HLC	2 values	Approximately	Yes

Hybrid Logical Clocks

The practical compromise, and increasingly the default in modern databases.

An HLC is a pair: a physical component (close to wall-clock time) and a logical counter. It updates like a Lamport clock but keeps the physical part tracking real time within the bound of clock skew.

You get: causality preserved (if A → B then HLC(A) < HLC(B)), timestamps that are meaningful as approximate wall time — you can ask "what did this look like at 14:32" — and constant size. CockroachDB, MongoDB, and YugabyteDB all use HLCs.

TrueTime, and buying your way out

Google's Spanner takes the opposite approach: rather than working around clock uncertainty, measure and bound it.

TrueTime uses GPS receivers and atomic clocks in every datacenter, and its API doesn't return a timestamp — it returns an interval [earliest, latest] guaranteed to contain the true time. The uncertainty ε is typically a few milliseconds.

The trick is commit-wait: to commit a transaction, Spanner picks a timestamp and then deliberately waits out the uncertainty window — a few milliseconds of doing nothing — before making the write visible. That guarantees no other transaction can be assigned an overlapping timestamp, which makes timestamps globally meaningful and yields externally consistent (strictly serializable) transactions across continents.

Practical guidance

Measuring elapsed time? Monotonic clock. Always.
Ordering events in one process? A local counter is enough.
Detecting conflicts between replicas? Version vectors. Accept the size cost.
Need approximate wall time and causality? HLC.
Need global external consistency? Consensus or TrueTime — and expect to pay latency.
Generating IDs? Prefer a scheme that doesn't assume synchronised clocks. Snowflake-style IDs embed a timestamp plus a node ID and sequence number specifically so two nodes can't collide even with skewed clocks — and note they can still go backwards if the clock does, which is why implementations refuse to issue IDs while the clock is behind their last issued timestamp.

In interviews

"How do you order events across servers?" — do not say "timestamps". Say happens-before, then Lamport or vector clocks depending on whether concurrency detection is needed.
"Why is last-write-wins dangerous?" — clock skew decides the winner, and losers are discarded silently. Connect it to version vectors as the alternative.
"How does Spanner get global consistency?" — TrueTime's bounded uncertainty plus commit-wait. The insight to voice: it pays latency rather than escaping the tradeoff.
"Design a unique ID generator" — a common question (and Ch 7). The clock-skew and clock-going-backwards edge cases are what separate answers.
"Two events have the same timestamp. Which came first?" — if they're concurrent, the question has no answer, and saying so is correct rather than evasive.

What to take away

Monotonic clocks for durations; wall clocks only for display. Wall clocks jump backwards.
Clock skew is normally milliseconds and occasionally catastrophic, with no warning.
Happens-before replaces "when" with "what could have influenced what".
Lamport gives total order but can't detect concurrency; vector clocks can, at O(nodes) size.
HLCs are the practical middle ground and are what modern distributed databases use.
TrueTime bounds uncertainty and waits it out — buying ordering with latency and hardware.

Check yourself

You measure how long an operation took by subtracting two System.currentTimeMillis() readings. What can go wrong?
The time-of-day clock is synchronised to an external source and can step backwards when corrected, when a leap second is applied, or when a VM is restored. Durations must come from a monotonic clock, whose absolute value is meaningless but which never moves backwards.
Lamport timestamps give L(A) < L(B). What does that tell you?
Lamport timestamps guarantee only one direction: if A happened before B then L(A) < L(B). The converse does not hold, so a smaller timestamp is consistent with either causal precedence or concurrency. Detecting concurrency requires vector clocks.
What is the essential trick behind Spanner's TrueTime?
TrueTime returns an interval guaranteed to contain the true time rather than a single value. Commit-wait then deliberately pauses for the uncertainty window before making a write visible, guaranteeing non-overlapping timestamps. It pays latency to obtain global ordering rather than escaping the tradeoff.
Two replicas hold conflicting values and their version vectors are neither less than nor greater than one another. What does this mean?
Incomparable version vectors mean neither write could have known about the other — they are causally independent. There is no correct automatic ordering, so the system must surface both siblings for application-level merging, use a CRDT, or accept the data loss that last-write-wins implies.