"Lamport clocks, vector clocks and hybrid logical clocks"

Ordering events without trusting wall clocks: the happened-before relation, Lamport timestamps, vector clocks and version vectors for detecting concurrency, hybrid logical clocks used by modern databases, their sizes and limits, and where each appears in system design.

Reading is half of it. See this used in a real interview: walk through Design a Distributed Key-Value Store →

Machines' clocks disagree by milliseconds or more, and they can jump. So "which write happened first?" cannot be answered reliably with timestamps alone. Distributed systems use logical clocks instead: counters that capture cause and effect. They show up in interviews when you design a key-value store with conflict detection, a chat with ordering, or explain how a database orders transactions. This guide covers the three you should know.

Happened-before

Leslie Lamport defined the relation that matters: event A happened before B if

• A and B are on the same process and A came first, or
• A is sending a message and B is receiving it, or
• there is a chain of such steps from A to B.

If neither happened before the other, they are concurrent: no information flowed between them, so neither could have influenced the other. Wall-clock times cannot reliably tell these cases apart; logical clocks can.

Lamport timestamps

Each process keeps a counter:

• Increment it before each local event.
• Attach it to every message sent.
• On receiving, set it to max(local, received) + 1.

Guarantee: if A happened before B, then L(A) < L(B). Ties are broken by process id to give a total order consistent with causality.

Limit: the converse does not hold. L(A) < L(B) does not tell you whether A caused B or they were concurrent. Lamport clocks are enough when you just need *some* order that respects causality (for example ordering operations in a replicated log), not when you must detect conflicts.

Vector clocks

Each process keeps a vector of counters, one entry per process:

• Increment your own entry on each event.
• Send the whole vector with messages.
• On receive, take the element-wise maximum, then increment your own entry.

Comparing two vectors:

• If every entry of V(A) is ≤ V(B) (and one is smaller), A happened before B.
• If some entries are larger and some smaller, A and B are concurrent.

That detection is the point: a database can tell that two writes to the same key were concurrent and keep both as siblings for the application to merge, instead of silently discarding one. Dynamo and Riak used this approach (with version vectors per replica rather than per client). See quorums and leaderless replication.

Costs: vectors grow with the number of participants. Systems bound them by tracking replicas rather than clients, and pruning old entries, at the risk of occasional false conflicts.

Hybrid logical clocks (HLC)

HLCs combine a physical timestamp with a logical counter:

• The physical part stays close to real time (useful for humans, TTLs and snapshot reads "as of" a time).
• The logical part breaks ties and preserves causality when clocks are slightly off: if a message arrives from a node whose clock is ahead, the receiver's HLC moves forward to stay greater.

The result fits in a 64-bit value, is monotonic, respects happened-before, and stays within the clock-skew bound of real time. CockroachDB, YugabyteDB and MongoDB use HLC-style timestamps to order transactions without atomic clocks. See Spanner and distributed SQL.

Comparison

In practice

• Chat ordering: a per-conversation sequence number assigned by the server is simpler than vector clocks; use logical clocks when there is no single sequencer (peer-to-peer, offline-first). See message ordering and sequence numbers.
• Collaborative editing: CRDTs embed logical clocks (Lamport-style ids per operation) to order and merge edits. See CRDTs vs operational transformation.
• Key-value stores: version vectors to detect concurrent writes, or last-writer-wins with HLC timestamps if you accept losing concurrent updates.
• Distributed tracing and debugging: causal ordering of events across services.

In the interview

For a Design a Key-Value Store answer: "Each value carries a version vector keyed by replica; a read returning concurrent versions returns siblings that the client merges, while writes that descend from all siblings replace them. If the product accepts last-writer-wins, we use hybrid logical clock timestamps instead of wall clocks so causality is preserved." Being precise about what each clock can and cannot tell you is the signal.

Checklist

• Happened-before as the order that matters; concurrency is real.
• Lamport timestamps for a causal total order.
• Vector or version vectors to detect concurrent updates.
• Hybrid logical clocks for compact, near-real-time causal timestamps.
• A single sequencer when one exists is simpler than any clock.
• Never order cross-machine events by raw wall clocks for correctness.