Patterns of Distributed Systems Link to heading

Based on: Catalog of Patterns of Distributed Systems by Unmesh Joshi (published on martinfowler.com, Nov 2023)

Table of Contents Link to heading

1. Group D — Time & Ordering
   • Lamport Clock
   • Hybrid Clock
   • Clock-Bound Wait
   • Version Vector

Group D — Time & Ordering Link to heading

In a distributed system, there is no global clock. Machines’ clocks drift, network delays cause message reordering, and concurrent events are impossible to order without explicit mechanisms. These patterns address event ordering.

D1. Lamport Clock Link to heading

Logical time: if A happened before B, then clock(A) < clock(B).

Problem Link to heading

Two events on different servers each have a timestamp from their local system clock. But clocks drift. You cannot tell from wall-clock timestamps alone which event happened first.

Solution Link to heading

Use logical timestamps: each node maintains an integer counter. The counter obeys one rule: if event A causally preceded event B, then A’s counter value is less than B’s. This gives a partial ordering of events without relying on synchronized clocks.

How it works Link to heading

Rules:

1. Increment your counter before every event you generate
2. When you send a message, include your current counter value
3. When you receive a message, set your counter to max(local, received) + 1

Initial state: Node A counter=0, Node B counter=0

Node A does something:  A.counter=1  (event a1)
Node A sends message to B with timestamp=1
Node B receives message: B.counter = max(0, 1) + 1 = 2
Node B does something:  B.counter=3  (event b1)
Node A does something:  A.counter=2  (event a2)

Ordering: a1(1) → b1(3), a2(2) → b1(3)
But: a1 and a2 are on the same node, so a1(1) < a2(2) ✓

Limitation: If two events are concurrent (no causal relationship), their Lamport timestamps may be identical or inverted — you can’t distinguish them.

Real-world analogy Link to heading

A project timeline that only records “Task B started after Task A finished” rather than actual calendar dates. The sequence is correct, even if you don’t know the exact dates.

Example systems Link to heading

Distributed databases for version numbering, message ordering in distributed logs

Trade-offs Link to heading

Related patterns Link to heading

→ Versioned Value (Lamport timestamps used as versions) → Version Vector (extends Lamport to track per-node causality) → Hybrid Clock (adds real-time component)

D2. Hybrid Clock Link to heading

Wall-clock time + logical counter: the best of both worlds.

Problem Link to heading

Lamport Clocks give correct ordering but produce timestamps that are meaningless to humans (they are just integers). Real-world systems often need to query data “as of a point in time” — which requires real timestamps. But wall-clock timestamps alone are unreliable due to clock drift and NTP jumps.

Solution Link to heading

A hybrid logical clock (HLC) combines a physical wall-clock component with a logical counter. It:

1. Advances to match the physical clock when possible
2. Falls back to a pure logical counter when the physical clock would go backwards or when causality requires it

How it works Link to heading

A hybrid timestamp is a pair: (wall_time, logical_counter)

Rules:

• On a local event: if wall clock > current HLC time → use wall clock, reset counter to 0; else increment counter
• On receiving a message: take max of (local HLC, received HLC), then handle counter

Node A: HLC = (10:00:01.000, 0)
  Local event → wall time is 10:00:01.500 → HLC = (10:00:01.500, 0)
  Send message with HLC (10:00:01.500, 0)

Node B (wall clock slightly behind at 10:00:01.300):
  Receives message with (10:00:01.500, 0)
  HLC = max(local=10:00:01.300, received=10:00:01.500) = (10:00:01.500, 1)
  → Logical counter increments because wall times matched

Real-world analogy Link to heading

A traveler adjusts their watch to the local timezone when they arrive (physical), but also keeps a universal logical sequence number for all events in their trip journal.

Example systems Link to heading

CockroachDB (HLC for MVCC), YugabyteDB, MongoDB (oplog timestamps)

Trade-offs Link to heading

Related patterns Link to heading

→ Lamport Clock (the logical component) → Versioned Value (HLC values used as versions) → Clock-Bound Wait (deals with clock uncertainty)

D3. Clock-Bound Wait Link to heading

Wait out the clock uncertainty window before making decisions.

Problem Link to heading

Even with Hybrid Clocks, there is uncertainty about the exact current time. Two nodes’ clocks can differ by up to some maximum skew ε. If Node A writes a value at time T and Node B reads at time T (where both T values could be off by ε), they may disagree on ordering.

Google Spanner makes this concrete: it uses GPS and atomic clocks to know that the real time is within [T-ε, T+ε]. Before committing a transaction, it waits until the lower bound of the interval has definitely passed.

Solution Link to heading

Before reading or writing a value that must be ordered relative to another, wait for 2ε (the maximum possible clock uncertainty) to elapse. This guarantees that by the time you proceed, all other nodes’ clocks have definitely passed the same point in real time.

How it works Link to heading

Node A wants to commit transaction at real time T_real:
  1. Capture TrueTime interval: [T_now - ε, T_now + ε]
  2. Assign commit timestamp = T_now + ε  (upper bound)
  3. Wait until wall clock ≥ commit timestamp  (the "commit wait")
  4. Commit

Result: Any transaction that started after this one
        will have a commit timestamp > T_now + ε ✓

The wait is typically small (10–20ms in Spanner with GPS/atomic clocks; potentially longer with NTP).

Real-world analogy Link to heading

Before announcing a policy change that must take effect “simultaneously” across all offices worldwide, you schedule a delay to ensure the announcement has reached every office (accounting for communication lag).

Example systems Link to heading

Google Spanner (TrueTime API), CockroachDB (approximate clock-bound wait with HLC)

Trade-offs Link to heading

Related patterns Link to heading

→ Hybrid Clock → Two-Phase Commit (Clock-Bound Wait is used here) → Versioned Value

D4. Version Vector Link to heading

Track causality per-node: detect concurrent writes.

Problem Link to heading

Lamport Clocks tell you if A happened before B, but cannot tell you if A and B happened concurrently (neither caused the other). In multi-master systems (where multiple nodes can accept writes for the same key), you need to detect conflicts: did server 1’s write of key K happen before or after server 2’s write? Or simultaneously?

Solution Link to heading

Instead of a single counter, maintain a vector of counters — one per node. Each node increments only its own counter. Comparing two version vectors:

• V1 dominates V2 if every element of V1 ≥ V2 (V2 happened before V1)
• V1 and V2 are concurrent if neither dominates the other

How it works Link to heading

3-node cluster: [A, B, C]
Initial: all version vectors = [0, 0, 0]

Node A writes key K:  version vector = [1, 0, 0]
Node B writes key K:  version vector = [0, 1, 0]

These are concurrent writes! Neither [1,0,0] nor [0,1,0] dominates the other.
→ System detects conflict → merge or present both to user

Node A receives B's update, merges:
  New vector = [max(1,0), max(0,1), max(0,0)] = [1, 1, 0]
  → This version causally follows both ✓

Real-world analogy Link to heading

A shared document edited by two authors simultaneously. Track which edits each author made. If author A edited section 3 while author B also edited section 3 independently, you have a conflict. If A’s edit was sent to B first and B then made changes, there’s no conflict — B’s version is newer.

Example systems Link to heading

Riak (vector clocks), Amazon Dynamo (inspired much of the theory), CouchDB, Git (similar concept)

Trade-offs Link to heading

Related patterns Link to heading

→ Lamport Clock (simpler predecessor) → Versioned Value → Gossip Dissemination (how vectors are exchanged)