Skip to content

Logical Clocks — Detailed#

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