Commit and Consensus - Systems - Jordi Villar
Interactive explainer

How distributed systems agree

Two-phase commit, three-phase commit, Paxos and Raft, and how ZooKeeper and ClickHouse Keeper put them to work. Every diagram on this page runs: step through it, break it, and watch what happens.

0 · Start here

Two problems that look alike

These five protocols usually get mentioned together, but they solve two different problems. Getting that distinction straight makes everything else easier.

Atomic commit

Several nodes hold different pieces of one transaction: shard A has your debit, shard B has your credit. They must all apply it or none of them can. Every participant can veto, so you need every participant.

2PC, 3PC

Consensus

Several replicas hold copies of the same data and must agree on one ordered list of changes. Nobody has a reason to veto, so a majority is enough, and a minority can fail without stopping anything.

Paxos, Raft, ZAB

ZooKeeper and ClickHouse Keeper are consensus systems. ZooKeeper runs ZAB and ClickHouse Keeper runs Raft, and both expose the result as a small replicated filesystem that other systems use for coordination: locks, leader election, configuration, and replication metadata.

Protocol family map
Diagram

How to read it. The top band is atomic commit, the middle band is consensus, and the bottom row is real systems built on each protocol. Click any box to jump to its section. The dashed arrow from Paxos up to Paxos Commit is where the two families meet: 2PC made safe by running it on top of consensus. The double-headed link means ClickHouse Keeper speaks ZooKeeper's client protocol.

1 · Atomic commit

Two-phase commit (2PC)

A transaction has written rows on several shards, and the client says COMMIT. One node acts as coordinator (usually the one that received the transaction). The others are participants.

  1. Prepare. The coordinator asks every participant whether it can commit. Each participant writes its changes and a PREPARED record to its write-ahead log, keeps its row locks, and votes yes or no.
  2. Commit or abort. If every vote is yes, the coordinator writes COMMIT to its own log. That single log write is the real commit point. It then tells everyone to commit. A single no makes it abort instead.

The weakness: a participant that has voted yes has given up the right to decide on its own. If the coordinator disappears at the wrong moment, that participant can neither commit nor abort, and it keeps holding its locks until the coordinator comes back. This is called blocking.

Where you meet it: XA transactions, PostgreSQL's PREPARE TRANSACTION, and cross-shard transactions in Spanner, CockroachDB and Vitess.

2PC simulator
Step-through

How to use it. Pick a scenario, then press Next to advance one round of messages. Arrows show messages in flight and their labels sit above each shard. Box colors show state: blue is waiting on others, amber is prepared and holding locks, green committed, red aborted, dashed gray crashed. Start with Happy path, then run Coordinator crashes and watch the shards get stuck in amber.

2 · Atomic commit

Three-phase commit (3PC)

3PC tries to remove the blocking by adding a preCommit phase between voting and committing. After everyone votes yes, the coordinator first tells everyone the outcome will be commit, waits for acknowledgements, and only then says doCommit. The point is that no participant is ever uncertain while some other participant might already have committed.

If the coordinator dies, the survivors elect a replacement and apply one rule:

The catch is that the rule assumes a node that stops answering has crashed. In a real network, a timeout can't tell a crashed node from an unreachable one. Under a network partition, each side applies the rule to what it can see and may reach a different answer. 3PC pays for a third round trip on every transaction and is still unsafe under partitions, so it is rarely used in practice.

3PC simulator
Step-through

How to use it. Run Coordinator crashes first: unlike 2PC, the survivors elect a new coordinator (purple) and finish on their own. Then run Network partition. The red dashed line is a network split, and on the last step the two sides reach different outcomes for the same transaction.

3 · Consensus

Majorities instead of unanimity

Consensus avoids both failure modes by changing the question. The replicas hold copies of the same data, so no one has a reason to veto. They only need to agree on which change comes next, and for that a majority is enough.

Majorities work because any two majorities of the same cluster always share at least one server. That shared server carries knowledge from one decision into the next, which is why a later leader can never contradict an earlier commit. They also make split brain impossible: during a partition, at most one side can hold a majority.

The price is latency. Every write waits until a majority has it on disk, so the leader needs acknowledgements from enough followers to reach that majority.

Quorum calculator
Interactive

How to use it. Drag Servers to change the cluster size and see how many crashes it survives. Drag Left side of partition to split the network in two: green servers are on a side with a majority and keep working, gray servers stall. Try an even cluster size, and try an exact 50/50 split.

5 2
Quorum size
3
Crashes survived
2
Follower acks per write
2

4 · Consensus

Paxos

Paxos is the original consensus protocol. In its basic form, called single-decree Paxos, a group of acceptors chooses exactly one value, and that choice can never change afterwards. Proposers try to get a value chosen using proposal numbers that are unique and always increasing. A round has two phases:

  1. Prepare and promise. A proposer picks number n and sends prepare(n). Each acceptor promises to ignore anything numbered below n, and reports any value it has already accepted.
  2. Accept and accepted. With promises from a majority, the proposer sends accept(n, value). If any acceptor reported a prior value, the proposer must use the one with the highest number instead of its own. Once a majority accepts, the value is chosen.

That second rule is what makes Paxos safe. If a value might already have been chosen, every later majority overlaps it, so any later proposer is forced to carry it forward.

Real systems need to agree on a whole log of values, not just one. Multi-Paxos runs one Paxos instance per log slot, with a stable leader that runs phase 1 once for all future slots. After that, each new value costs only phase 2, which is one round trip to a majority. Google's Chubby lock service and Spanner are built on Multi-Paxos.

Paxos simulator
Step-through

How to use it. Basic round shows the four message types in order. Safety: competing proposer is the important one: at step 6, watch Acceptor 1 report an earlier value, and at step 7 watch Proposer B give up its own value Y. Dueling proposers shows that two impatient proposers can block each other forever, and why real systems elect a leader.

5 · Consensus

Raft

Raft (Ongaro and Ousterhout, 2014) was designed to be easy to understand and implement. It is essentially Multi-Paxos with the leader built in and every detail specified. Time is divided into numbered terms, and each term has at most one leader. Every server is a follower, a candidate, or the leader.

Raft cluster, running live
Live simulation
How to use it. This is a simplified Raft running in your browser. The gray ring around each follower is its election timer running down. Try these in order:
  1. Wait a moment for the first election. One server turns purple: that's the leader.
  2. Press Client write a few times. Each entry appears dashed in the log table, then turns solid green once a majority has stored it.
  3. Press Crash leader. The timers run out, a candidate turns amber and asks for votes, and a new leader takes over in a higher term.
  4. Crash three servers with the S1 to S5 buttons, or by clicking them. New writes stay dashed: without a majority nothing commits. Restore them and watch them catch up.
vote request vote reply AppendEntries (bigger dot carries entries) AppendEntries reply
6 · From protocol to product

ZAB and Raft: nearly the same machine

ZAB (ZooKeeper Atomic Broadcast) is the protocol inside ZooKeeper. It was designed around 2008, before Raft, but the two arrived at the same design:

The differences are in bookkeeping:

Both write paths have the same shape as 2PC (propose, acknowledge, commit) with two changes: a majority is enough, and nobody can vote no.

One write, two protocols
Step-through

How to use it. Step through the ZAB write, then switch to Raft. Switching keeps the current step, so you can compare the two protocols at the same point. In both, Follower 2 has a slow disk, to show that a three-server cluster only needs the leader plus one follower to commit.

7 · From protocol to product

ZooKeeper vs ClickHouse Keeper

ZooKeeper presents its replicated state as a tree of small nodes called znodes, like a tiny filesystem. Clients can:

ClickHouse Keeper reimplements that data model and ZooKeeper's client protocol, but uses Raft (through eBay's NuRaft library) instead of ZAB. ClickHouse servers talk to it exactly as they talk to ZooKeeper, so switching is a configuration change.

ZooKeeperClickHouse Keeper
ConsensusZABRaft, via NuRaft
RuntimeJava on the JVM, so garbage-collection pauses need tuningC++, part of the clickhouse binary; runs standalone or embedded in clickhouse-server
Write orderingzxid = epoch plus 32-bit counter. When the counter rolls over, ZooKeeper forces a leader electionRaft term plus 64-bit log index, so no rollover
Client port21819181
Server-to-server ports2888 for the quorum, 3888 for elections9234 for Raft
Data modelZnodes, sessions, watches, ephemeral and sequential nodes, multi-opsThe same, plus some ClickHouse-specific extensions
WritesLinearizableLinearizable
ReadsServed locally by whichever server the client is connected to, so possibly stale. Call sync first for a fresh readSame default behavior
Migrationclickhouse-keeper-converter turns ZooKeeper logs and snapshots into a Keeper snapshot
OperationsFour-letter commands such as ruok, mntr, statSupports the same commands, plus Keeper-specific system tables

Ports are defaults. Exact options vary by version, so check the docs for the release you run.

8 · From protocol to product

What ClickHouse stores in Keeper

Keeper never holds table data. It holds the small amount of metadata that replicas must agree on:

Replication in ClickHouse is multi-master: any replica accepts inserts, and Keeper's single ordered log is what keeps them consistent.

One INSERT into a ReplicatedMergeTree table
Step-through

How to use it. Press Next to follow one insert from the client to both replicas. Green arrows are the messages at that step. The panel underneath lists the znodes in Keeper for this table: lines marked + were created at that step, and lines marked − were removed. Notice that at step 6 the data itself goes straight from replica to replica, never through Keeper.

Keeper coordinates replicas within one shard. It does not provide transactions across shards: an insert through a Distributed table is not atomic across shards, because ClickHouse doesn't run 2PC between them.

9 · Recap

Putting it together

Operational consequences