Zab: primary-ordered atomic broadcast with recovery synchronization

Zab is a crash-recovery atomic-broadcast protocol tailored to ZooKeeper primary-backup replication. A primary assigns monotonically ordered zxids, pipelines proposals, and commits after quorum acknowledgement. Transactions are prefix-dependent: a delivered transaction cannot skip earlier dependencies.

A new primary first discovers and synchronizes a quorum to a safe prefix before broadcasting new updates. With 2f+1 servers, majority progress tolerates f crashes. Writes stop when no quorum can support a primary. ZooKeeper writes are linearizable, but ordinary reads are served locally and may be stale; sync() is an explicit barrier before a subsequent read.

Prerequisites and model

• Servers use durable transaction logs and snapshots across crash recovery.
• Only the established primary for an epoch broadcasts new transactions after quorum synchronization.
• zxid carries epoch/order information and replicas preserve prefix order.
• Client session FIFO is distinct from global freshness of local reads.

Correctness claims and invariants

• ZAB-C1. Zab provides primary-ordered atomic broadcast for prefix-dependent state changes.
• ZAB-C2. A proposal commits after quorum acknowledgement; leader election alone does not commit it.
• ZAB-C3. A new primary synchronizes a quorum to a safe prefix before new broadcasts.
• ZAB-C4. A majority quorum carries committed-prefix evidence across epoch change and a minority cannot continue writes.
• ZAB-C5. ZooKeeper local reads can be stale; sync() before a subsequent read provides the documented freshness barrier.
• ZAB-C6. Watches are one-shot ordered notifications and may not expose every intermediate state between re-registration.

What the scenarios prove

• Primary-ordered zxid broadcast (leader-broadcast-zxid): The primary assigns an epoch/order zxid and preserves proposal prefix.

• Quorum acknowledgement commits (quorum-ack-commit): A majority durably acknowledges before commit is broadcast and applied.

• Primary crash and prefix synchronization (leader-crash-recovery-sync): A new epoch recovers a quorum prefix before any new transaction.

• Local read then sync barrier (stale-read-sync): A follower read may lag; sync before a later read establishes the documented barrier.

• One-shot watch gap (watch-one-shot-gap): A watch fires once; client rereads and re-registers instead of assuming every intermediate value.

• Minority partition stops writes (minority-partition): A server subset without majority cannot establish a primary or commit updates.

Failure, concurrency, and retry traps

• Calling Zab “Paxos with another name” hides primary-order and recovery-prefix design.
• Serving writes in a minority partition creates split brain.
• A locally served read is not automatically linearizable.
• A watch callback is a prompt to reread state, not a durable stream of every transition.
• A new leader cannot append before synchronizing outstanding history.

Boundaries and non-guarantees

• Zab assumes crash faults, not Byzantine replicas.
• Election selects a candidate; synchronization and quorum broadcast establish a safe log.
• Writes pause during election/synchronization and without a quorum.
• Read freshness requires client protocol such as sync or leader-aware access.

Related material

Raft consensus is an explore diagram and is linked as Markdown.

Primary sources

1. Junqueira, Reed, Serafini: Zab, High-performance broadcast for primary-backup systems
2. Hunt et al., ZooKeeper: Wait-free Coordination for Internet-scale Systems
3. USENIX ZooKeeper publication page
4. Apache ZooKeeper Programmer’s Guide
5. Apache ZooKeeper Administrator’s Guide