Logical clocks: Lamport timestamps, vector clocks and hybrid clocks

What it is

Lamport's 1978 paper (listed on his publications page, cited) defines the "happened before" relation: event a precedes b if both occur in the same process in that order, if a is the sending of a message and b its receipt, or by transitivity. A Lamport clock is a counter per process: increment it on every local event, attach it to every message, and on receipt set the counter to the maximum of the local and received values plus one. If a happened before b, then clock(a) < clock(b); the converse does not hold, so equal or nearby timestamps say nothing about causality. Breaking ties with a process identifier yields a total order.

A vector clock, as described in the Dynamo paper (cited), is a list of (node, counter) pairs attached to each version of an object. Comparing two vectors shows whether one version descends from the other or whether they are on parallel branches, which is how Dynamo detects conflicting writes to reconcile on read.

Hybrid logical clocks combine both ideas. CockroachDB's documentation (cited) describes an HLC as a physical component close to local wall time plus a logical component that distinguishes events with the same physical value, so HLC time is always greater than or equal to wall time and still orders causally related events.

Why it matters

"Last writer wins by timestamp" silently discards updates when clocks skew by more than the time between two writes. Replicated data, offline-capable clients and multi-region deployments all meet this problem.

How to apply

• Give every mutable record a version counter that increases on each write and use it for optimistic concurrency (UPDATE ... WHERE version = $seen); this is a per-record Lamport clock.
• In event streams, order by sequence number within a partition, not by producer timestamp.
• Where several replicas accept writes, keep a version vector per record or use a data type with a defined merge (a CRDT), and surface conflicts instead of picking a winner by wall clock.
• Use wall-clock timestamps for display and retention, and note the clock source (NTP-disciplined or not) in the design.

Pitfalls

Vector clocks grow with the number of writers and need pruning rules. Lamport clocks order but cannot detect concurrency. A monotonic clock on one machine says nothing about another machine's clock.