Section 8: Order Survives the Leader - Deep Dive: Zab — Atomic Broadcast, Election & Recovery
Executive Summary: Every guarantee in Section 7 rests on one claim: all five servers apply the same transactions in the same zxid order, even when the leader dies mid-stream. Zab delivers that with primary order. A leader's transactions are delivered in the order it proposed them, and a new leader delivers everything its predecessors committed before it broadcasts anything of its own. It runs in three phases. Election picks the server with the most complete log. Discovery and synchronization opens a new epoch and makes every follower's history match the leader's. Broadcast commits pipelined proposals once 3 of 5 servers have fsynced them. When S1 crashes with proposal 0x5_0000a3f2 logged only on its own disk, S3 leads epoch 6 within ≈ 1 s of detection, and no client ever learns that a3f2 existed.
Interviewer: "Your write path says 'Zab proposal' and moves on. Why isn't that just Paxos?"
You: "Because ZooKeeper needs a property that plain per-operation Paxos doesn't give. Property first, then the three phases, then Sam's cluster losing its leader."
Why Primary Order, Not Paxos Per Operation
Section 6's request processor turns a client request into an idempotent transaction computed against the leader's current state. A setData with version 7 becomes a setDataTXN carrying "800" and version 8. That transaction is only correct if every earlier transaction it was computed on top of is also applied. Transactions from one leader depend on each other, and the leader pipelines many of them at once.
Multi-Paxos decides each log slot independently. Suppose a leader proposes A in slot 27 and B in slot 28, and B was computed assuming A. If the leader crashes, a new leader recovering the slots can find B accepted by a majority but A on no majority. It fills slot 27 with a no-op and keeps B. Every replica then applies B on top of a state that never contained A. Never pipelining avoids this but costs throughput. The Zab paper builds the dependency into the protocol instead:
| Property (Zab paper) | What it promises | Why ZooKeeper needs it |
|---|---|---|
| Local primary order | If a leader proposes A before B, any server that delivers B has delivered A first | Pipelined transactions build on each other |
| Global primary order | Everything from epoch 5 is delivered before anything from epoch 6 | A new leader's transactions build on the old leader's state |
| Primary integrity | A new leader broadcasts only after it has delivered every transaction committed in earlier epochs | No committed write is skipped or reordered by a failover |
Key Insight: Zab replicates a history, not a set of independent decisions. A server either holds a prefix of the leader's log or gets corrected until it does. That one invariant is what keeps idempotent, state-computed transactions safe to pipeline.
This is Decision 4. Asynchronous primary-backup was rejected because it loses acknowledged writes on failover. There is no flip trigger on correctness grounds. Raft, which came later, makes the same trade under different names.
Quick check before moving on:
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson