Vector Clocks & Logical Clocks

Overview

In a distributed system there is no single global clock, so you cannot trust wall-clock timestamps to tell you the true order of events across machines. Logical clocks - Lamport timestamps and vector clocks - order events by causality instead of by time, and hybrid approaches (HLC, Google's TrueTime) combine physical and logical time to get the best of both.

🧠 Mental model: Imagine two people writing letters back and forth, each dated by their own wristwatch. If the watches disagree, the dates lie about who replied to whom. To reconstruct the true conversation, you track "this letter is a reply to that one" (causality) rather than trusting the printed dates.

Key Concepts

Physical clocks on each machine drift and are periodically corrected by NTP, which can jump time forward or backward. This makes System.currentTimeMillis() unsafe for ordering: a later event can carry an earlier timestamp.

Happens-before (->) is the causal relationship at the heart of everything here: if event A could have influenced event B (same process in order, or a message sent then received), then A -> B. Events with no such path are concurrent.

Lamport timestamps assign each event a counter: increment on every local event, and on receiving a message set the counter to max(local, received) + 1. If A -> B then L(A) < L(B), but the converse does not hold - a smaller Lamport value does not prove causality. They give a total order but cannot detect concurrency.

Vector clocks fix that: each node keeps a vector of counters, one per node. Comparing two vectors tells you whether one happened before the other or whether they are truly concurrent (a conflict to resolve).

Mechanism	Orders events?	Detects concurrency?	Cost
Physical clock	By wall time (unreliable)	No	Cheap, but drifts
Lamport clock	Total order	No	One counter
Vector clock	Partial (causal) order	Yes	One counter per node
Hybrid (HLC/TrueTime)	Near-real time + causal	Yes	Moderate

Hybrid Logical Clocks (HLC) combine a physical timestamp with a logical counter, so ordering tracks real time yet never goes backward. Google TrueTime takes a hardware approach: GPS and atomic clocks bound the uncertainty to a small interval, and Spanner simply waits out that interval before committing, achieving globally consistent timestamps.

These clocks underpin the consistency models a store can offer and are how AP systems detect conflicting writes to reconcile later.

Trade-offs

Lamport clocks are cheap and give a total order, but they throw away the information needed to detect concurrent updates, so they suit ordering (e.g., mutual exclusion) not conflict detection. Vector clocks detect conflicts precisely but grow with the number of nodes, which is why systems prune or cap them. TrueTime delivers globally consistent timestamps but requires specialized hardware and pays a commit-wait latency. The practical rule: use logical clocks for causality, and only trust physical time when you have explicitly bounded its uncertainty.

Interview Tips

Say early: "There is no global clock, so I won't rely on wall-clock time to order events across nodes."
Offer Lamport clocks when you need a total order and vector clocks when you must detect concurrent writes.
If asked about globally consistent transactions, name Spanner/TrueTime and the commit-wait trade-off.
Flag last-write-wins as convenient but lossy under clock skew, and pair it with NTP discipline or HLC.

Summary

Distributed systems have no single clock; physical timestamps drift and can move backward.
Happens-before captures causality; events with no causal path are concurrent.
Lamport clocks give a total order but cannot detect concurrency; vector clocks detect it at higher cost.
HLC and TrueTime blend physical and logical time for near-real, monotonic, causally-correct ordering.
Use logical clocks for causality; trust wall-clock time only when its uncertainty is explicitly bounded.