Patterns of Distributed Systems
Based on: Catalog of Patterns of Distributed Systems by Unmesh Joshi (published on martinfowler.com, Nov 2023)
Table of Contents
Group D — Time & Ordering
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
Logical time: if A happened before B, then clock(A) < clock(B).
Problem
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
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
Rules:
- Increment your counter before every event you generate
- When you send a message, include your current counter value
- 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
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
Distributed databases for version numbering, message ordering in distributed logs
Trade-offs
| Pro | Con |
|---|---|
| Simple to implement | Cannot distinguish truly concurrent events |
| No clock synchronization needed | Only provides a partial ordering |
| Enables causal reasoning | Not human-readable (not real time) |
Related patterns
→ 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
Wall-clock time + logical counter: the best of both worlds.
Problem
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
A hybrid logical clock (HLC) combines a physical wall-clock component with a logical counter. It:
- Advances to match the physical clock when possible
- Falls back to a pure logical counter when the physical clock would go backwards or when causality requires it
How it works
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 matchedReal-world analogy
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
CockroachDB (HLC for MVCC), YugabyteDB, MongoDB (oplog timestamps)
Trade-offs
| Pro | Con |
|---|---|
| Human-readable timestamps | More complex than pure Lamport or pure wall clock |
| Maintains causality guarantees | Requires bounded clock skew between nodes (e.g., 500ms) |
| Enables time-travel queries with real timestamps | — |
Related patterns
→ Lamport Clock (the logical component) → Versioned Value (HLC values used as versions) → Clock-Bound Wait (deals with clock uncertainty)
D3. Clock-Bound Wait
Wait out the clock uncertainty window before making decisions.
Problem
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
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
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
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
Google Spanner (TrueTime API), CockroachDB (approximate clock-bound wait with HLC)
Trade-offs
| Pro | Con |
|---|---|
| Enables externally consistent distributed transactions | Adds latency equal to clock uncertainty |
| Correct global ordering without communication overhead | Requires precise clock infrastructure (GPS, atomic clocks for short waits) |
| Simplifies transaction protocols | Standard NTP makes uncertainty too large for most practical use |
Related patterns
→ Hybrid Clock → Two-Phase Commit (Clock-Bound Wait is used here) → Versioned Value
D4. Version Vector
Track causality per-node: detect concurrent writes.
Problem
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
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
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
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
Riak (vector clocks), Amazon Dynamo (inspired much of the theory), CouchDB, Git (similar concept)
Trade-offs
| Pro | Con |
|---|---|
| Detects concurrent writes reliably | Vector size grows with number of nodes |
| Enables "last-write-wins" or "merge" conflict resolution | Complex to reason about with many nodes |
| Works in eventually consistent, multi-master systems | Requires nodes to share their vectors on sync |
Related patterns
→ Lamport Clock (simpler predecessor) → Versioned Value → Gossip Dissemination (how vectors are exchanged)
0 Comments