Logical Clocks

Pradeep P

Sep 2

3 min read

Series: Modern System Design · Layer 4 — Data

Layer 4 · Post 16 of 17

← Previous: CRDTs → Next: Bloom Filters

Layer 4 — Data · Post 110 of 119

You cannot trust NTP to order events. Logical clocks track causality without a shared timeline.

What you'll learn

Why wall clocks are a bad uniqueness and ordering story
Lamport clocks vs vector clocks: total order vs detecting concurrency
Where Dynamo version vectors, HLCs, and TrueTime fit

The idea in one minute

Machines' wall clocks lie: NTP steps, VMs pause, two regions disagree by tens of milliseconds. Sorting events by now() creates false order (and false LWW winners).

Logical clocks count causality, not time of day.

Lamport clock: each node has integer t. On send, t++ and attach t. On receive, t = max(t, message.t) + 1. If a.t < b.t, either a happened-before b or they were concurrent (Lamport clocks do not detect concurrency). They do give a total order if you break ties with node id (useful for some logs).

Vector clock: each node has a vector of counters, one per node. You can tell happened-before vs concurrent. That is what you want to merge (keep both, or CRDT) instead of pretending one was first.

A: [1,0] --msg-->  B: [1,1]
Concurrent C: [0,0] -> [0,1]  vs  A's [1,0]  — incomparable = concurrent

Happened-before (→) (Lamport): local order, plus send→receive. Not "who the user clicked first in the real world" if those clicks never messaged.

Why it matters

Fallacy "we have time." Version vectors in Dynamo/Riak, Cassandra timestamps (a different, cruder choice), Git history, and "which replica is newer" are this topic.

Interviews: do not say "we'll timestamp with NTP" as the uniqueness story for money. Say causality or a leader's log.

How it works

Lamport: cheap (one integer). Good for total order broadcast sketches and debugging "roughly who knew what." Bad as a conflict detector.

Vector clocks / version vectors: size O(nodes) or O(replicas writing this key). Dynamo used them per key so the vector is "authors of this value," not all servers in the universe. Pruning / dotted version vectors exist because vectors grow.

Hybrid logical clocks (HLC): mix wall time with a logical component so you get mostly human-readable timestamps and causality. Cockroach/Yugabyte-style. Still not GPS-perfect; still better than raw NTP for ordering inside a cluster.

TrueTime (Spanner): wait out clock uncertainty. Different bet: synchronize better, then sleep until the interval is sure. That is physics + protocol, not a Lamport integer.

You still need a policy for concurrent writes. Vector clocks surface the fork; they do not pick. CRDT, merge app-side, or last-write-wins (admit data loss).

A simple example

Shopping cart: replica A adds milk (offline). Replica B adds eggs (offline). Wall clocks: B's NTP is 2 seconds behind; LWW keeps only milk. Vector clocks: concurrent; merge {milk, eggs}. That is the cart you wanted.

Same structure for "comment edited on two laptops." LWW drops a paragraph. A version vector plus app merge or a text CRDT keeps both until a human (or CRDT) resolves.

Common mistakes

Sorting logs with datetime.now() across services. Traces use causal ids (trace/span) plus happens-after from RPC; they still do not make NTP a global order.

A vector of all 10,000 nodes. Per-key authors, or you will melt.

Lamport clock as "this was first in real life." It is not a physical clock.

Ignoring siblings. Storing a vector then still LWW-ing in Redis without looking at it.

How this shows up in real systems

Dynamo, Riak: version vectors; siblings on conflict.
Cassandra: often server timestamps (LWW) — know that it is not a vector clock.
Cockroach HLC, Mongo cluster times, Kafka offsets (per partition: a log clock).
Git commit graphs: causality without NTP.

Recap

Wall clocks order badly. Lamport orders cheaply; vectors detect concurrent writes.
Concurrent ⇒ merge policy, not a bigger NTP pool.
Next: a tiny structure for "is this key even worth looking up?" — Bloom filters.