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 A — Durability & Storage
These are the foundational patterns. Before nodes can coordinate, each individual node must be able to survive a crash and recover its own state reliably.
A1. Write-Ahead Log
The single most fundamental pattern in distributed storage.
Problem
A server maintains data structures in memory (e.g., a B-tree, a hash map). If the server crashes, all in-memory state is lost. Writing every change immediately to the final storage structure is too slow — it requires random-access disk writes.
Solution
Before applying any change to an in-memory or on-disk data structure, first append a record describing that change to a sequential log file. This log is the source of truth. On restart, replay the log to reconstruct state.
How it works
Client request → 1. Append entry to WAL (append-only, sequential)
2. Apply change to in-memory state
3. Acknowledge client
On crash/restart: replay WAL from last checkpoint → state restoredThe key properties of the log:
- Append-only — sequential writes are extremely fast on disk
- Each entry has a monotonically increasing index — enables replay
- Fsynced to disk before acknowledging — guarantees durability
Real-world analogy
A bank teller writes every transaction in a ledger book before touching the cash drawer. Even if the teller is interrupted mid-transaction, the ledger tells you exactly what happened.
Example systems
PostgreSQL WAL, MySQL binlog, Kafka (the log is the data), etcd, RocksDB
Trade-offs
| Pro | Con |
|---|---|
| Crash recovery without full data flush | Log grows indefinitely (see Low-Water Mark) |
| Sequential writes are fast | Replay can be slow if log is huge |
| Enables replication (ship the log) | Storage overhead |
Related patterns
→ Segmented Log (manage log size) → Low-Water Mark (garbage collect old log entries) → High-Water Mark (track safe replication point) → Replicated Log (extend WAL to multiple nodes)
A2. Segmented Log
Problem
A single, ever-growing log file becomes impractical: it is slow to search, hard to truncate, and risky to delete portions of without careful bookkeeping.
Solution
Split the log into multiple fixed-size segment files. Each segment covers a range of log indices. Old segments can be safely deleted once they are no longer needed.
How it works
Segment 1: [index 0 – 999] ← can be deleted once replicated
Segment 2: [index 1000 – 1999]
Segment 3: [index 2000 – 2999] ← active segment (current writes go here)- A new segment file is created when the current one reaches a size or time threshold.
- Each segment has a metadata file recording its index range.
- Log reads span multiple segment files transparently.
Real-world analogy
Instead of one never-ending journal notebook, you use separate dated volumes. When a volume is filled and backed up, you can archive or shred old ones safely.
Example systems
Kafka (partition log segments), etcd, Apache Bookkeeper
Trade-offs
| Pro | Con |
|---|---|
| Easy log cleanup (delete whole segments) | Slightly more complex to read across segments |
| Faster startup (fewer files to check) | Segment boundary management overhead |
| Parallel operations on different segments | — |
Related patterns
→ Write-Ahead Log (the log being segmented) → Low-Water Mark (determines which segments are safe to delete)
A3. Low-Water Mark
Problem
A Write-Ahead Log grows forever. You need to know which portion is safe to discard — but you cannot just delete old entries if a slow follower node still needs them for replication.
Solution
Maintain a low-water mark index: the highest log index that has been safely processed (replicated AND applied) by all followers. Everything below the low-water mark can be deleted.
How it works
Log: [0][1][2][3][4][5][6][7][8]
↑
Low-Water Mark = 4
(entries 0–4 can be discarded)The leader tracks acknowledgements from all followers. The low-water mark advances to the minimum index acknowledged by all followers.
Follower A confirmed up to index 7
Follower B confirmed up to index 4
Follower C confirmed up to index 9
Low-Water Mark = min(7, 4, 9) = 4Real-world analogy
A newspaper delivery company keeps back-issues in a warehouse. Once all subscribers have received a particular issue (the slowest subscriber has collected it), that issue can be shredded.
Example systems
Kafka (consumer offsets drive log retention), Raft implementations, ZooKeeper
Trade-offs
| Pro | Con |
|---|---|
| Prevents unbounded log growth | A single slow/dead follower can hold up cleanup |
| Safe — nothing is deleted prematurely | Requires tracking per-follower acknowledgements |
Related patterns
→ Write-Ahead Log → Segmented Log (enables deletion of whole segments) → High-Water Mark (complementary concept)
A4. High-Water Mark
Problem
In a replicated system, followers receive log entries from a leader. However, the leader might crash before some entries are fully replicated. Followers must not expose or apply entries that weren't confirmed replicated — those might be rolled back.
Solution
Maintain a high-water mark index: the last log entry that has been successfully replicated to a majority of nodes. Only entries at or below the high-water mark are considered committed and safe to serve to clients.
How it works
Leader log: [0][1][2][3][4][5]
↑
High-Water Mark = 5
Entries 0–5 are replicated to majority → committed → safe to serve
Entry 6 exists on leader but not yet replicated → NOT committedThe leader piggybacks the high-water mark in every message to followers, so followers also know what they can expose.
Real-world analogy
A newspaper printing press prints 10,000 copies per run. The "ready for distribution" marker advances only when QA has confirmed enough copies passed inspection — not when the press first produces them.
Example systems
Raft protocol, Kafka (Log End Offset vs. High Watermark), ZooKeeper ZAB
Trade-offs
| Pro | Con |
|---|---|
| Clients never read uncommitted data | Adds latency (wait for replication before committing) |
| Safe crash recovery — no rollback of visible state | Under-replicated state is invisible but takes storage |
Related patterns
→ Write-Ahead Log → Leader and Followers (leader broadcasts high-water mark) → Replicated Log
A5. Versioned Value
Problem
In a distributed system, multiple clients may update the same key simultaneously. You need to track the history of a value to handle conflicts, support time-travel queries, and enable multi-version concurrency control (MVCC).
Solution
Instead of overwriting a value on update, store every version of the value alongside a monotonically increasing version number (or timestamp). Reads can request a specific version or always get the latest.
How it works
Key: "user:42:email"
Version 1 → "alice@old.com" (written at t=100)
Version 2 → "alice@new.com" (written at t=200)
Version 3 → "alice@latest.com" (written at t=300) ← current
Read latest → "alice@latest.com"
Read at version 2 → "alice@new.com"Old versions are eventually garbage collected based on a retention policy.
Real-world analogy
Google Docs keeps a full revision history of every document. You can always look at what a document looked like three months ago.
Example systems
etcd, CockroachDB, Spanner, Cassandra (with timestamps), HBase
Trade-offs
| Pro | Con |
|---|---|
| Supports historical reads | Storage grows with number of versions |
| Enables snapshot isolation | Garbage collection complexity |
| Conflict detection and resolution | Clients must handle multiple versions |
Related patterns
→ Version Vector (track causal versions across nodes) → Lamport Clock / Hybrid Clock (provide the version numbers) → Replicated Log (applies versioned writes across nodes)
0 Comments