Logical Clocks#

Problem statement (interviewer prompt)

Across distributed nodes there is no global wall clock. Design a way to order events causally for use in a multi-region key-value store. Compare Lamport timestamps, vector clocks, hybrid logical clocks (HLC), and TrueTime; pick one and explain why.

flowchart LR
  A[Node A] -- send msg ts=3 --> B[Node B]
  A -- local event ++ --> A
  B -- on recv: ts = max local, msg + 1 --> B

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class A,B service;

Lamport / vector clocks order events causally without synchronized wall clocks. HLC mixes wall-clock + logical to get both.

flowchart TB
  subgraph Lamport[Lamport Timestamps]
    LL[Each node has counter L]
    LE[local event: L = L + 1]
    LS[send msg: include L]
    LR[on recv m: L = max L, m.L + 1]
    LO[Order: L_a < L_b ⇒ a may causally precede b]
    LP[Total order via tiebreak by node id]
  end

  subgraph Vector[Vector Clocks]
    VV["Each node i keeps V[1..n]"]
    VE["local event: V[i]++"]
    VS[send: include V]
    VR["on recv m: V[k] = max V[k], m.V[k] all k, V[i]++"]
    VO["a -> b iff V_a ≤ V_b and exists k: V_a[k] < V_b[k]"]
    VC[Concurrent if neither ≤ the other]
  end

  subgraph DV[Dotted Version Vectors]
    DVV[Per replica dot history]
    DVU[Used by Riak, Cassandra-LWT alt]
  end

  subgraph HLC[Hybrid Logical Clocks - Kulkarni 2014]
    H1[HLC = max wall ms, prev HLC + 1]
    H2[Bounded skew from real time]
    H3[Used by CockroachDB, YugabyteDB]
  end

  subgraph TT[TrueTime - Spanner]
    T1[Hardware: GPS + atomic clocks per DC]
    T2[TT.now returns interval, ε]
    T3[commit wait: wait out ε to guarantee external consistency]
  end

  subgraph Failures
    F1[Out-of-order delivery]
    F2[Clock skew, NTP step]
    F3[Replica add/remove resize V]
  end

  Lamport --> Vector --> DV
  Vector --> HLC --> TT

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class LL,LE,LS,LR,LO,LP,VV,VE,VS,VR,VO,VC,DVV,H1,H2,T1,T2,T3,F1,F2,F3 service;
    class DVU,H3 datastore;

When to use each#

Clock	Compact	Detects concurrency	Real-time bound
Wall clock + tiebreak	8 B	no	yes (with NTP)
Lamport	8 B	no (only happens-before)	no
Vector	O(N) B	yes	no
Dotted version vector	bounded	yes, scalable	no
HLC	16 B	partial	yes (bounded)
TrueTime	bounded interval	no	yes (small ε)

Real-world#

Cassandra: writes carry wall-ts → last-write-wins.
DynamoDB: vector clock (early), now version metadata.
Riak: dotted version vectors.
CockroachDB / YugabyteDB: HLC.
Spanner: TrueTime + 2PC.

Pitfalls#

LWW with wall clocks loses data on clock skew.
Vector clocks explode with many writers - prune via dotted vectors.
HLC needs NTP slewed (not stepped) clocks.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	Leader/follower replication	sync/semi-sync/async replication, failover	replication-leader-follower
`HLD`	Distributed transactions	2PC, TCC, sagas, outbox/inbox	distributed-transactions
`HLD`	Logical clocks	Lamport, vector clocks, HLC, TrueTime	logical-clocks
`LLD`	Testing strategy	pyramid, doubles, TDD, contracts	testing-strategy
`LLD`	Concurrency primitives	mutex, semaphore, RW lock, atomic, CAS	concurrency-primitives

Quick reference#

Problem#

Across distributed nodes there is no global wall clock; physical clocks drift. We still need to: - Order events causally. - Detect concurrent updates that must be merged. - Provide consistent reads / snapshots.

Lamport's "happens-before" (1978)#

a → b if a precedes b in same process, or a is a send and b the matching receive, transitively.
a || b (concurrent) if neither happens-before the other.
Lamport TS gives total order consistent with → (but loses concurrency info).

Vector clocks#

One counter per node.
Compares element-wise: ≤ everywhere ⇒ happens-before; some less / some greater ⇒ concurrent.
Memory O(N) replicas - fine for small N, not for millions of clients.

HLC = wall ms + logical counter#

tick(now): pt = max(pt, now); l = max(l + 1, pt + 1) (simplified).
Read as causal but stays within bounded ε of real time → good for OLTP.

TrueTime (Spanner)#

API returns [earliest, latest] interval.
Commit wait = wait out ε; ε ≈ a few ms with atomic clocks + GPS.

Where this matters in this repo#

CRDTs need vector / dotted version vectors.
Spanner-style designs (Spanner, CRDB, YugabyteDB) need HLC/TrueTime.
Multi-leader replication needs conflict ordering.
Distributed tracing uses logical span IDs (causal ordering across services).

Refs#

Lamport: "Time, Clocks, and the Ordering of Events" (CACM '78).
Mattern: "Virtual Time and Global States of Distributed Systems."
Kulkarni et al.: "Logical Physical Clocks" (HLC, 2014).
Spanner paper, CockroachDB blog "Living without atomic clocks."

FAQ#

What is a logical clock?#

A logical clock assigns each event a counter that respects causality, so if event A could have caused event B, A's timestamp is smaller, with no global wall clock needed.

Lamport vs vector clocks?#

Lamport gives one counter per node and only proves order, not concurrency. Vector clocks carry one counter per node, so you can tell which pairs of events are concurrent.

What is a hybrid logical clock?#

HLC combines a physical wall-clock reading with a logical counter. It stays close to real time for humans while still preserving causal ordering across nodes.

What is Google TrueTime?#

TrueTime is an API in Spanner that returns a wall-clock interval with a known max uncertainty, using GPS and atomic clocks so commits can wait out clock skew safely.

When do you need logical clocks?#

Whenever wall clocks across machines cannot be trusted to order events, like in multi-region databases, CRDTs, distributed key-value stores, and audit logs.

Consensus: Raft and Paxos: consensus algorithms use logical clocks and version numbers to order events across replicas
CAP and PACELC Theorems: logical clocks are the tool for reasoning about event ordering in systems that sacrifice strict consistency
CRDTs: CRDTs use vector clocks and logical timestamps to merge concurrent updates without coordination