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 C — Replication & Consensus
   • Majority Quorum
   • Replicated Log
   • Paxos
   • Consistent Core

Group C — Replication & Consensus Link to heading

Individual nodes can now store data and elect a leader. The next challenge is keeping data consistent across multiple nodes when failures occur.

C1. Majority Quorum Link to heading

The rule: get at least ⌊N/2⌋ + 1 nodes to agree.

Problem Link to heading

In a cluster of N nodes, some nodes may be unavailable. If you require all nodes to confirm an operation, one slow node blocks everything. If you require any single node, you might accept a write that only one node knows about (and loses it on crash).

Solution Link to heading

Require a majority (more than half) of nodes to confirm any decision. Because any two majorities always share at least one node in common, you can never have two conflicting majorities — guaranteeing consistency.

How it works Link to heading

Cluster of 5 nodes (need majority = 3)

Write "x=10":
  Node 1: confirmed ✓
  Node 2: confirmed ✓
  Node 3: confirmed ✓   ← majority reached → commit!
  Node 4: timeout
  Node 5: timeout

The write is committed. Nodes 4 and 5 are out of date but the cluster proceeds.

Fault tolerance formula: A cluster of N nodes can tolerate ⌊N/2⌋ failures.

• 3 nodes → 1 failure tolerated
• 5 nodes → 2 failures tolerated
• 7 nodes → 3 failures tolerated

Real-world analogy Link to heading

A board vote: you need more than half to pass a resolution, not unanimous agreement, not just one person.

Example systems Link to heading

Raft (replication quorum), Paxos, ZooKeeper (ensemble quorum), etcd

Trade-offs Link to heading

Related patterns Link to heading

→ Leader and Followers (quorum used to commit writes) → Paxos / Raft (implement quorum-based consensus) → Replicated Log

C2. Replicated Log Link to heading

The backbone of fault-tolerant stateful services.

Problem Link to heading

A single-node server can use a Write-Ahead Log to survive crashes. But if the server’s disk fails, all data is lost. You need multiple servers to hold the same log so any one server’s failure doesn’t lose data.

Solution Link to heading

Combine Write-Ahead Log, Leader and Followers, and Majority Quorum: the leader accepts writes, appends them to its log, replicates the log entries to followers, and only commits (marks as durable) once a majority of followers acknowledge.

How it works Link to heading

Client write: "SET x = 42"

Leader:
  1. Append [index=100, SET x=42] to own WAL
  2. Send AppendEntries(index=100, SET x=42) to all followers
  3. Wait for majority acks
  4. Advance High-Water Mark to 100
  5. Apply to state machine → x=42
  6. Reply to client: SUCCESS

Follower 1: Receives entry, appends to local WAL → acks
Follower 2: Receives entry, appends to local WAL → acks
Follower 3: Slow/dead → no ack (doesn't block commit — majority already met)

This is essentially how Raft works.

Real-world analogy Link to heading

A shipping manifest: the captain (leader) records every item loaded onto the ship. First mates (followers) keep identical copies. If the captain’s copy is destroyed, any first mate’s copy reconstructs the full cargo list.

Example systems Link to heading

Raft (etcd, CockroachDB, TiKV), ZooKeeper ZAB, Viewstamped Replication, Kafka (ISR replication)

Trade-offs Link to heading

Related patterns Link to heading

→ Write-Ahead Log → Leader and Followers → Majority Quorum → High-Water Mark → Generation Clock

C3. Paxos Link to heading

The original distributed consensus algorithm.

Problem Link to heading

How can a set of nodes agree on a single value (e.g., the next entry to commit to the log) even when some nodes crash or messages are lost?

Solution Link to heading

Paxos splits consensus into two phases and uses ballot numbers (generation numbers) to handle concurrent proposals safely.

How it works Link to heading

Phase 1 — Prepare:

1. A proposer picks a ballot number n (higher than any it has seen)
2. Sends Prepare(n) to a majority of acceptors
3. Each acceptor responds with the highest-numbered proposal it has already accepted (if any), and promises to reject any future proposal with ballot < n

Phase 2 — Accept: 4. If proposer receives majority responses, it picks the value from the highest-accepted proposal (or its own value if none) 5. Sends Accept(n, value) to a majority 6. Acceptors accept unless they’ve already promised to a higher ballot 7. Once a majority accepts, the value is chosen

Proposer ──► Prepare(n=5) ──► Acceptors (majority)
Acceptors ──► Promise(n=5, already-accepted=null) ──► Proposer
Proposer ──► Accept(n=5, value="x=42") ──► Acceptors
Acceptors ──► Accepted(n=5) ──► Proposer/Learners
Value "x=42" is CHOSEN

Real-world analogy Link to heading

A sealed-bid auction with two rounds. In round one, bidders announce their intent and the highest bidder gets priority in round two. In round two, if anyone outbid you in round one, you must use their preferred item instead of yours.

Example systems Link to heading

Google Chubby (Multi-Paxos), Apache ZooKeeper ZAB (Paxos-inspired), etcd (Raft is Paxos-equivalent), CockroachDB

Trade-offs Link to heading

Related patterns Link to heading

→ Generation Clock (ballot numbers) → Majority Quorum → Replicated Log (Paxos implements this)

C4. Consistent Core Link to heading

Delegate the hard coordination problem to a small, specialized cluster.

Problem Link to heading

Running a quorum-based consensus protocol (Paxos/Raft) on every node in a large data cluster (hundreds of nodes) is operationally and computationally expensive. But you still need a reliable coordination service for things like leader election, distributed locks, and configuration.

Solution Link to heading

Run a small cluster (3–5 nodes) with strong consistency guarantees (using Replicated Log/Paxos/Raft) as the “brain” of the system. Large data nodes offload coordination tasks to this consistent core, using it as a trusted oracle.

How it works Link to heading

Large Data Cluster (100 nodes, eventual consistency)
    │
    │ uses for: leader election, locks, config, membership
    ▼
Consistent Core (5 nodes, strong consistency: Raft/Paxos)
    │
    │ stores:
    │ - which data node is the current master?
    │ - cluster configuration
    │ - distributed locks (leases)
    └──────────────────────────────────────

The data cluster nodes register with the consistent core. The core manages their lifecycle and coordinates split-brain prevention. Data nodes handle the scale; the core handles correctness.

Real-world analogy Link to heading

A large corporation has a main trading floor (the data cluster) and a small legal/compliance department (the consistent core). All binding decisions (contracts, approvals) must go through legal. Traders don’t need to implement contract law themselves.

Example systems Link to heading

ZooKeeper (consistent core for Kafka, HBase, Hadoop) etcd (consistent core for Kubernetes) Consul (consistent core for service discovery)

Trade-offs Link to heading

Related patterns Link to heading

→ Replicated Log (how the core achieves consistency) → Lease (commonly provided by the core) → State Watch (clients observe core state) → Gossip Dissemination (data nodes may use gossip; core does not)