Vector clocks and hybrid logical clocks

You have 3 servers in 3 different data centers. A client posts a message on server A: "going to lunch". A minute later, a friend sees it and replies on server B: "enjoy!". Server C sees both messages but because of network delays, receives the reply before the original post. What order should C display them in?

Wall clocks won't help. Server A's clock might be 300ms ahead of server B's. Server C might see two messages with timestamps that don't reflect the actual causal order: A was written first, then B was a reply to A. If you sort by wall-clock timestamp, you might show the reply first — and it would look like a nonsense conversation.

This is the ordering problem in distributed systems, and it's the reason Leslie Lamport wrote his seminal 1978 paper. Lamport proved that in an asynchronous network, wall-clock timestamps are never enough — you need a logical clock that captures "this event happened because of that event." The paper introduced Lamport clocks; the concept later evolved into vector clocks and (most recently, 2014) hybrid logical clocks (HLC) — the technique CockroachDB, YugabyteDB, and MongoDB (v3.6+) use in production today.

The happens-before relation

Lamport defined a single relation: a → b ( "a happened before b") if one of these holds:

• a and b happen on the same process, and a is earlier in the local timeline.
• a is the sending of a message, and b is the receipt of that message.
• Transitively: if a → c and c → b, then a → b.

Two events not related by → are called concurrent — you can't say which happened first, because there's no causal path from one to the other. A distributed system that respects causal order must always display events consistent with →. Wall-clock timestamps don't know about →. Logical clocks do.

Lamport clocks — one counter per process

The simplest logical clock. Every process maintains a single integer counter. Rules:

• Local event: increment counter by 1.
• Send message: increment counter, then attach it to the message.
• Receive message: set counter = max(local, received) + 1.

This guarantees: if a → b then LC(a) < LC(b). The converse is not true — two events with different Lamport timestamps might be concurrent. So Lamport clocks are useful for total ordering (tie-break by process ID) but can't detect concurrency. Vector clocks fix that.

Vector clocks — one counter per process

Fidge / Mattern 1988. Instead of one counter, each process maintains a vector of N counters (one per process). Rules:

• Local event on process P: increment V[P] by 1.
• Send: increment V[P], attach the whole vector.
• Receive: take element-wise max of local V and received V, then increment V[P].

Now you can detect concurrency. Given vectors Va and Vb: Va → Vb iff Va[i] ≤ Vb[i] for all i AND Va[j] < Vb[j] for some j. If neither Va → Vb nor Vb → Va, the two events are concurrent.

Vector clocks were the conflict-resolution primitive in Dynamo and are the foundation of Riak's sibling model. When two clients write to the same key from different partitions, the store detects (via vector clocks) that the writes are concurrent — neither happened-before the other — and stores both as siblings for the application to reconcile.

The vector clock size problem

The vector grows to size N where N is the number of writers ever seen. For a Cassandra cluster with 1000 nodes writing to a popular key, each value would carry a 1000-entry vector — every read, every write. That's enormous overhead. Real implementations bound the vector by pruning old entries (Riak did this with a "dotted version vector" variant), but the problem remains for high-cardinality writer sets.

This is one reason many modern systems moved away from pure vector clocks. Which brings us to HLC.

Hybrid Logical Clocks — the modern answer

Kulkarni et al. 2014. The insight: wall clocks are pretty good — usually within a few milliseconds of each other via NTP. So let's use them as the base, and use a small logical counter only as a tiebreaker for events that happen "at the same wall-clock time."

HLC = (pt, lc) where pt is a physical timestamp and lc is a small logical counter. Rules:

• Local event: pt' = max(pt, now()); if pt' == pt then lc++, else lc = 0.
• Receive: pt' = max(local.pt, received.pt, now()); logical counter chosen to preserve happens-before.

Because pt is a real wall-clock timestamp bounded by NTP drift (say ±10ms), and lc only counts events at the same pt, HLC combines the causal-safety of logical clocks with the intuitive interpretability of wall clocks. A CockroachDB HLC timestamp looks like 2024-11-20T15:04:23.987Z, 12 — human-readable but causally correct.

CockroachDB, YugabyteDB, and MongoDB all use HLC. Google Spanner goes further with TrueTime — atomic clocks + GPS in every data center to bound clock uncertainty to ~7ms, and then wait out the uncertainty on commit. HLC is TrueTime for people who can't afford atomic clocks in their DC.

Clock family tree

Applied in real systems

Key takeaways

• Wall clocks lie. They're usually within NTP drift, but you can never assume A's timestamp < B's timestamp means A happened before B.
• Lamport clocks (1 counter per process) give total ordering but can't detect concurrency.
• Vector clocks (N counters, one per process) can detect concurrency but grow with the number of writers.
• HLC = wall-clock + tiebreaker. Human-readable timestamps that respect causality. Used by CockroachDB, YugabyteDB, MongoDB v3.6+.
• TrueTime (Spanner) uses atomic clocks + GPS for bounded uncertainty. Waits out the uncertainty on commit. The industrial ceiling.
• Every distributed database has to answer: "how do I establish a global order?" The answer is one of: Lamport, Vector, HLC, TrueTime, or "we give up."

References

• Lamport (1978) — Time, Clocks, and the Ordering of Events in a Distributed System. CACM.
• Fidge (1988), Mattern (1988) — Vector clocks (independently invented).
• DeCandia et al. (2007) — Dynamo used vector clocks for conflict resolution.
• Corbett et al. (2012) — Google Spanner (TrueTime).
• Kulkarni et al. (2014) — Logical Physical Clocks (HLC).
• Kleppmann (2017) — Designing Data-Intensive Applications, Chapter 8.