Who blocks, who may decide, and what the log says on restart
One transaction, coordinator C, participants P1–P3. Click any arrow to drop that message. Set crash points per node. The verdict cards assume timeouts eventually fire, a live coordinator answers inquiries, and crashed nodes lose every log record that was not forced.
| Presumed abort (PA) | Presumed commit (PC) | |
|---|---|---|
| Coordinator before PREPARE | Nothing | Force COLLECTING with participant list |
| Commit path | C forces COMMIT · P forces COMMIT · P sends ACK · C writes END lazily | C forces COMMIT · P writes COMMIT lazily · no ACKs · C forgets at once |
| Abort path | No forced writes, no ACKs; C forgets at once | P forces ABORT · ACKs required · then END |
| Inquiry with no record | Answer ABORT | Answer COMMIT (safe only because COLLECTING is forced first) |
| Wins when | Aborts and read-only participants are common. Default in most XA-style systems. | Commits dominate and the per-transaction COLLECTING force is cheaper than commit ACKs. |
Pre-commit removes blocking under crash-stop, and breaks safety under partitions
3PC inserts PRE-COMMIT between the vote and the commit. Nobody commits until everyone alive has learned the decision will be commit. That makes the survivors' own states enough to decide, as long as a timeout really means a crash.
Why the extra phase helps
In 2PC, a PREPARED survivor sits next to both outcomes: the crashed coordinator might have committed or aborted. Skeen's nonblocking rule says no local state may be concurrent with both COMMIT and ABORT, and no noncommittable state may be concurrent with COMMIT. 3PC satisfies it:
- If any survivor is PRE-COMMITTED, every node voted YES, so nobody can have aborted. Survivors commit.
- If every survivor is only PREPARED, nobody can have committed, because commit needs a PRE-COMMIT ack from every participant. Survivors abort.
- A recovering node never decides alone; it asks the survivors.
Assumptions that make this sound: crash-stop failures, bounded message delay, and a perfect failure detector. The price is one extra round trip and one extra forced write per participant.
| Local state | Can coexist with | Committable? |
|---|---|---|
| 2PC · PREPARED | PREPARED, COMMIT, ABORT | no → blocks |
| 3PC · PREPARED | PREPARED, PRE-COMMIT, ABORT | no |
| 3PC · PRE-COMMIT | PREPARED, PRE-COMMIT, COMMIT | yes |
| 3PC · COMMIT | PRE-COMMIT, COMMIT | yes |
Partition lab
5 nodes · all voted YES · C is sending PRE-COMMITClick a node to move it to the other side of the cut.
Why no deterministic protocol can guarantee a decision
Asynchronous messages, at most one crash, deterministic processes. FLP shows there is always an infinite run that never decides. Safety is untouched; termination is what you lose.
Valence. A configuration (all process states plus in-flight messages) is 0-valent if every continuation decides 0, 1-valent if every continuation decides 1, and bivalent if both are still reachable. Deciding means moving from bivalent to univalent. The proof shows an adversarial scheduler can avoid that move forever.
Lemma 2: some initial configuration is bivalent
3 processes · walk from 000 to 111Lemma 3: bivalence can always be preserved
Take a bivalent configuration C and any pending event e = (p, m). Look at every configuration reachable from C without applying e, then apply e. Suppose all of those were univalent. Then two neighbours differ by one extra step e′, and applying e makes one 0-valent and the other 1-valent.
- If e and e′ touch different processes, they commute (Lemma 1), so both orders reach the same configuration. It can't be both 0- and 1-valent.
- If e and e′ are both at process p, run a schedule where p takes no more steps. The rest of the system can't tell the two branches apart, so they must decide the same. Contradiction again.
So the adversary can always deliver e somewhere that stays bivalent. Repeat forever, delivering every message eventually. Note the punchline: the non-deciding run has zero crashes. The protocol is defeated by the mere possibility that a slow process is dead.
How real systems get around it
Dwork, Lynch, Stockmeyer (1988): delays are bounded after some unknown global stabilization time. Safety never depends on timing; timeouts only drive liveness. Before GST you can have dueling candidates forever, which is exactly the FLP run.
Chandra & Toueg (1996): add an oracle that is eventually accurate. Ω, "eventually everyone trusts the same live leader", is the weakest detector that solves consensus with a correct majority. An election timeout is an implementation of Ω that is only right once the network calms down.
Processes flip coins when undecided. The adversary can't predict the coins, so the run terminates with probability 1. Basic Ben-Or can take exponential expected rounds; a shared coin makes it constant. Raft's randomized timeouts are a liveness heuristic for elections, not a randomized consensus protocol.
Keeper chooses to stall rather than diverge. When it can't form a quorum, ClickHouse replicas go read-only instead of accepting writes that could fork the replication log. FLP is why "stall" is always a possible outcome.
Paxos Commit: make each vote a consensus instance
2PC blocks because one process, the TM, holds the decision. Paxos Commit stores each resource manager's vote in its own Paxos instance on 2F+1 acceptors. The outcome is a function of chosen values: COMMIT if every instance chose Prepared. Any leader can finish the job.
- Each RM owns ballot 0 of its instance, so it sends phase 2a ("Prepared") straight to the acceptors with no phase 1.
- A replacement leader runs phase 1 with a higher ballot. If a Prepared value might have been chosen, Paxos forces the leader to learn it. Otherwise the leader may propose only Aborted.
- With F = 0 there is one acceptor and one leader, and the protocol degenerates into 2PC. 2PC is Paxos Commit that tolerates no TM failure.
- Same idea in production: Spanner runs 2PC where coordinator and participants are Paxos groups, so the coordinator's decision survives a machine loss.
Message flow
N = 3 RMs · F = 1 · acceptors A1–A3Cost calculator
formulas from the paper's comparison tableTwo forced-write delays sit on the critical path in all three protocols (the paper treats Paxos Commit's write delay as equal to 2PC's). The extra cost of fault tolerance is messages and acceptor writes, not latency: Faster Paxos Commit matches 2PC's four message delays.
Reading from the leader isn't enough
A node can believe it is leader after a newer leader has committed writes. If it serves reads from local state, a client can read a value that a completed write already replaced. Linearizability needs the reader to prove it is still leader at some point after the read arrived.
Append the read as a log entry and answer when it applies. Correct and simple, but every read costs a disk write and replication.
Leader must have committed an entry in its current term (the no-op at election). Record readIndex = commitIndex, send a heartbeat round, wait for a majority, wait until applied ≥ readIndex, then answer. Heartbeats batch across many reads.
After a majority acks a heartbeat sent at t, nobody can win an election before t + election timeout, so the leader serves locally until t + timeout / (1 + ρ). Needs bounded drift rate ρ and monotonic clocks, not synchronized wall time. A pause between the lease check and the reply breaks it.
Follower asks the leader for a readIndex, waits until its own applied index reaches it, then serves locally. Linearizable. Serving from a follower without asking is bounded staleness at best.
Stale-read lab
5 servers · old leader partitionedWhat ClickHouse needs from its coordination service
Keeper speaks the ZooKeeper protocol but replicates with Raft through eBay's NuRaft library, in C++, with no JVM pauses. Writes are linearizable; reads, by default, are not. ClickHouse uses it to agree on the order and identity of parts, while the data itself moves replica to replica.
| ZAB (ZooKeeper) | Raft (Keeper via NuRaft) | |
|---|---|---|
| Epoch id | zxid = (epoch, counter) | term + log index |
| Election | Fast leader election picks the highest (epoch, zxid), then a discovery phase fixes the new epoch | Votes go only to candidates whose log is at least as up to date |
| Recovery | Separate synchronization phase: leader brings a quorum to its history (DIFF, TRUNC or SNAP) before broadcasting | Repair happens inline: AppendEntries consistency check walks nextIndex back; prior-term entries commit only once a current-term entry commits |
| Ordering promise | Primary order: a leader's transactions in order, and after every earlier leader's | Log matching: same index and term means identical prefix |
| Replicated item | Idempotent state deltas computed by the leader | Log entries applied deterministically by every state machine |
| Reads | Local on any server; per-session FIFO and read-your-writes; sync() to catch up | Same by default in Keeper; quorum_reads routes reads through Raft for linearizability |
| Membership | Dynamic reconfig (3.5+) | Single-server changes, one at a time |
Sessions, ephemeral nodes, sync()
- A session is a client lease kept alive by heartbeats. The leader decides expiry and replicates a close-session entry, so every server deletes that session's ephemeral nodes at the same log position.
- A partitioned client first sees connection loss, which is ambiguous: the session may still be alive and its last request may have applied. Only session expired is definitive. ClickHouse treats expiry as fatal for that client and reinitializes the replica.
- An expired client can still think it holds a lock (GC pause, slow disk). ClickHouse guards critical steps with multi-ops that check versions or create-if-absent, so a stale holder fails instead of corrupting state.
sync(path)makes the server you're connected to catch up with the leader before your next read. Write-then-tell-someone-else patterns need it. Strict linearizable reads needquorum_reads.
| Keeper path (per table) | Used for |
|---|---|
block_numbers/<partition> | Monotonic block numbers. An ephemeral-sequential lock is held while an insert is in flight. Numbers define part names and the order of merges and mutations. |
blocks/ | Insert dedup: hashes of recent blocks, created in the same multi-op as the part. Window set by replicated_deduplication_window. |
log/ · replicas/<r>/queue | Shared replication log (GET_PART, MERGE_PARTS, MUTATE_PART, DROP_RANGE…). Each replica copies entries into its queue and executes them. |
replicas/<r>/parts · is_active | Each replica's part set with checksums; ephemeral liveness node. |
mutations/ · quorum/ · columns | Mutation queue, insert_quorum progress, schema version. |
/clickhouse/task_queue/ddl | ON CLUSTER DDL queue. Every host executes entries in order and writes its status; the initiator waits up to distributed_ddl_task_timeout. |
Anatomy of one INSERT into ReplicatedMergeTree
R1 receives the block · R2 fetchesKeeper quorum lab
3 Keeper nodes · 2 replicasTen questions, short model answers
Answer out loud first, then open. Each answer leads with the one-line claim, then the mechanism, then the ClickHouse knob.
Further reading
What to read, and which part to read if you only have twenty minutes.
quorum_reads, force_sync, session timeouts, feature flags beyond ZooKeeper, and the recovery procedure with --force-recovery after quorum loss.insert_quorum, and recovery after a lost replica.sync exists.