ZAB (Zookeeper Atomic Broadcast)

When you think about the systems that keep the modern internet running—Apache Kafka processing trillions of messages, Hadoop clusters coordinating petabytes of computation, distributed databases maintaining consistency across continents—there's an invisible force orchestrating it all. That force is Apache Zookeeper, and at its core lies one of the most elegant yet practical consensus protocols ever designed: ZAB (Zookeeper Atomic Broadcast).

ZAB isn't just another consensus algorithm. It's a protocol purpose-built for the unique demands of coordination services—systems that must provide total order, exactly-once delivery, and strong consistency while maintaining the performance characteristics necessary for production workloads. Where Paxos provides theoretical foundations and Raft offers understandability, ZAB delivers the precise guarantees needed by coordination services: primary-backup replication with atomic broadcast semantics.

Before diving into ZAB's mechanics, we must understand why the Zookeeper team didn't simply adopt Paxos or an existing consensus algorithm. The answer lies in the specific requirements of coordination services—requirements that existing protocols didn't fully address.

The Coordination Service Challenge:

Zookeeper was designed to be a high-performance coordination kernel for distributed systems. It needed to handle millions of read requests per second while maintaining strict ordering guarantees for write operations. More importantly, it needed to support the patterns that coordination services require:

• Sequential consistency for all operations
• Atomicity across multiple operations
• Total ordering of all state changes
• Efficient primary-backup replication
• Fast leader election and recovery

The Atomic Broadcast Distinction:

At its heart, ZAB is an atomic broadcast protocol rather than a pure consensus protocol. This distinction is subtle but profound:

Consensus solves the problem of getting distributed nodes to agree on a single value. Once agreement is reached on value V, the consensus instance is complete.

Atomic Broadcast solves the problem of delivering a sequence of messages to all nodes in exactly the same order. Every message must be delivered exactly once, and all nodes must see the same sequence of messages.

Zookeeper needs atomic broadcast because it's maintaining a replicated state machine. Clients issue a stream of state-changing operations, and every replica must apply those operations in exactly the same order to maintain consistency. ZAB provides precisely this guarantee.

ZAB operates in two distinct phases, each designed to handle different system states. Understanding these phases is crucial to grasping how ZAB maintains correctness while maximizing availability.

Phase 1: Recovery (Discovery + Synchronization)

The recovery phase executes whenever the ensemble must establish or re-establish a leader. This happens at startup, after leader failure, or when network partitions heal. Recovery has two sub-phases:

1. Discovery: Nodes elect a prospective leader and the prospective leader discovers the most up-to-date transaction history among a quorum of followers.

2. Synchronization: The leader synchronizes its state with followers, ensuring every follower has a consistent prefix of committed transactions before broadcasting begins.

Phase 2: Broadcast

Once recovery completes successfully, ZAB enters the broadcast phase—its steady-state operation mode. In this phase:

• The leader receives all client write requests
• The leader broadcasts proposals to followers in FIFO order
• Followers acknowledge proposals
• Once a quorum acknowledges, the leader commits and broadcasts the commit
• All nodes apply committed transactions in order

The Critical Invariant:

ZAB's correctness depends on a fundamental invariant: a new leader must have all committed transactions from previous epochs before starting broadcast. This ensures that no committed state is ever lost, even across leader changes.

This invariant is enforced through the epoch mechanism and quorum intersection. Since any quorum in the current epoch must overlap with the quorum that committed the previous epoch's transactions, the new leader will always discover all committed history during the discovery phase.

ZAB uses a sophisticated numbering system to uniquely identify and order all transactions across the distributed system. This system consists of epochs and zxids (Zookeeper Transaction IDs).

Epoch: The Leadership Era

An epoch is a 32-bit number that identifies a particular leadership term. Every time a new leader is elected, the epoch is incremented. Epochs serve several critical purposes:

1. Leader disambiguation: If two nodes both believe they're the leader (split-brain scenario), the one with the higher epoch wins
2. Message filtering: Followers reject messages from old epochs
3. Ordering guarantee: Higher epochs always represent more recent leadership
4. Recovery identification: Epochs help determine which transactions are from previous leaders

Zxid: The Global Transaction Ordering

A zxid is a 64-bit number composed of two 32-bit parts:

• High 32 bits: The epoch number
• Low 32 bits: The counter (incremented for each transaction within an epoch)

Why This Structure Matters:

The genius of this zxid structure is that comparison is trivial—it's just a 64-bit integer comparison! Yet it encodes complete ordering information:

1. All transactions from a later epoch are greater than all transactions from earlier epochs, regardless of counter values
2. Within an epoch, transactions are ordered by counter
3. No coordination is needed to compare zxids—any node can determine transaction ordering independently
4. Zxids are globally unique—the same zxid can never be reused, even after leader failures

This structure enables efficient log comparison during recovery. When a new leader syncs with followers, it can quickly determine exactly which transactions each follower is missing by comparing their last zxid with its own log.

The broadcast phase is where ZAB spends most of its time in a healthy cluster. Understanding this protocol is essential for reasoning about Zookeeper's consistency guarantees and performance characteristics.

The Two-Phase Commit Flow:

ZAB's broadcast uses a variant of two-phase commit optimized for the primary-backup model:

Phase 1: Propose

1. Leader receives client write request
2. Leader assigns the next zxid to the transaction
3. Leader creates a PROPOSAL message containing: zxid, transaction data
4. Leader sends PROPOSAL to all followers (and logs locally)
5. Each follower logs the proposal to disk and sends ACK to leader

Phase 2: Commit

1. Leader waits for ACKs from a quorum (majority) of followers
2. Once quorum is achieved, leader creates COMMIT message with the zxid
3. Leader sends COMMIT to all followers
4. Each node (leader and followers) applies the transaction to their state machine

Critical Properties of the Broadcast Protocol:

1. FIFO Ordering The leader sends proposals in the order it assigns zxids. Followers process proposals in the order received. Since there's only one leader and TCP guarantees in-order delivery, all followers see proposals in the same order.

2. Prefix Consistency If a follower has committed transaction with zxid Z, it has committed all transactions with zxid < Z. This is the "prefix" property—committed logs are always prefixes of each other.

3. Quorum Acknowledgment The leader waits for acknowledgment from a majority (quorum) before committing. For a 5-node cluster, quorum is 3. This means:

• At most 2 nodes can fail while maintaining progress
• Any two quorums overlap by at least 1 node
• Committed transactions are stored on a majority

4. Reliable Delivery Once a transaction is committed, it will eventually be delivered to all non-failed nodes. Followers that were temporarily down will catch up during synchronization.

ZAB provides three fundamental guarantees that together constitute atomic broadcast. These guarantees form the contract that Zookeeper relies upon to provide its consistency semantics.

Guarantee 1: Agreement

If a correct (non-failed) process delivers message m, then all correct processes eventually deliver m.

This means that once any node commits a transaction, you can be certain that all other nodes will eventually commit the same transaction. There's no possibility of one replica having transaction T committed while another replica permanently lacks it.

Guarantee 2: Total Order

If correct processes p and q both deliver messages m1 and m2, then p delivers m1 before m2 if and only if q delivers m1 before m2.

This is perhaps the most critical guarantee. All replicas apply transactions in exactly the same order. This means their state machines evolve identically, maintaining perfect replica consistency.

Guarantee 3: Local Primary Order

If a primary broadcasts m1 before m2, then a correct process that delivers m2 must have already delivered m1.

This ensures that a client's operations are applied in the order the client issued them. If client C issues operations A, then B, then C, they're applied in that order on all replicas.

The Relationship to Linearizability:

ZAB provides sequential consistency for writes—all writes appear in a total order that respects the order issued by each client. However, reads in Zookeeper are served locally by any replica, which means they might not see the most recent writes.

To achieve linearizable reads (read-your-writes and reading the latest value), Zookeeper provides:

1. sync() operation: Forces the follower to catch up to the leader's committed state before returning
2. Leader reads: Option to read from the leader only (not commonly used due to performance impact)

This design trades some consistency guarantees on reads for dramatically better read performance—reads don't require any inter-node communication.

When Zookeeper nodes need to synchronize—whether during initial startup, after a follower restarts, or during leader election—ZAB uses the zxid to efficiently bring lagging nodes up to date.

The Synchronization Decision Process:

When a follower connects to a leader, the leader examines the follower's last committed zxid and determines the synchronization strategy:

Case 1: DIFF (Differential Sync) If the follower's last zxid is in the leader's transaction log and the gap is small:

• Leader sends only the missing transactions
• Most efficient for followers that were briefly disconnected
• Preserves incremental log without full state transfer

Case 2: TRUNC (Truncation) If the follower has transactions beyond the leader's committed point (orphaned transactions from a failed leader):

• Leader instructs follower to truncate log to specific zxid
• Then sends any missing committed transactions
• Handles the case where a failed leader had proposed but not committed transactions

Case 3: SNAP (Snapshot) If the follower is too far behind or its log is incompatible:

• Leader sends a full state snapshot
• Slower but handles any state divergence
• Necessary after prolonged outages or log corruption

Log Retention and Snapshots:

Zookeeper maintains a transaction log for recent operations and periodic snapshots of the complete state. The log retention policy is configurable and affects sync behavior:

• More log retention: More likely to do DIFF sync, less network and CPU for snapshots, but more disk usage
• Less log retention: More frequent SNAP syncs for lagging nodes, but lower disk overhead

In practice, production deployments tune this based on expected failure patterns. If nodes typically recover quickly, short log retention works well. If network partitions can last hours, longer retention reduces recovery time.

While ZAB and Paxos solve related problems, they have fundamental differences in design philosophy and guarantees. Understanding these differences helps clarify when each protocol is appropriate.

Design Philosophy:

Paxos: Designed as a general consensus primitive. It answers: "How do N nodes agree on a single value?" Multi-Paxos extends this to sequences of values but fundamentally views each slot independently.

ZAB: Designed specifically for primary-backup replication. It answers: "How does a single leader reliably broadcast a sequence of updates to followers?" The sequence nature is fundamental, not an extension.

Key Technical Differences:

The Hole Problem:

One critical difference involves "holes" in the transaction sequence. In Multi-Paxos:

• Proposals can be decided out of order
• Slot 5 might be decided before slot 4
• The state machine must handle gaps, waiting for earlier slots

In ZAB:

• No holes are possible by construction
• If transaction Z is committed, all transactions with zxid < Z are committed
• This simplifies state machine implementation significantly

The FIFO Guarantee:

ZAB's FIFO ordering per client is crucial for coordination patterns. Consider a client that:

1. Creates a lock node
2. Writes data
3. Deletes the lock node

ZAB guarantees these operations are applied in order. If operation 3 were applied before operation 2, data corruption could result. Paxos doesn't inherently provide this guarantee—it would need to be built on top.

Understanding ZAB's performance profile is essential for deploying and tuning Zookeeper effectively. The protocol's design creates specific performance characteristics that affect system architecture decisions.

Write Latency:

Every write in ZAB requires:

1. Leader receives request
2. Leader logs proposal to disk
3. Proposal sent to followers (parallel)
4. Followers log to disk and ACK
5. Leader receives quorum of ACKs
6. Leader sends commit
7. State machine applies transaction

The critical path for latency is: network RTT + disk fsync + network RTT

For a 3-node cluster with 1ms network latency and 5ms fsync:

• Minimum write latency: ~7ms (1ms to leader + 5ms fsync + 1ms ACK)
• This assumes leader wasn't waiting for previous commits

Read Latency:

Reads are served locally without any inter-node communication:

• Read latency: essentially just local memory access
• This makes reads orders of magnitude faster than writes
• Typical: microseconds for simple reads

Throughput Considerations:

Write Throughput:

• Bounded by leader's ability to process and sequence writes
• Single leader is a fundamental bottleneck
• Batching proposals can dramatically improve throughput
• Typical: 10K-100K writes/second depending on payload size

Read Throughput:

• Scales linearly with cluster size (more replicas = more read capacity)
• Not affected by write load (reads don't coordinate)
• Can easily handle millions of reads/second

The 5-Node Sweet Spot:

Most production Zookeeper deployments use 5 nodes:

• Tolerates 2 failures (quorum = 3)
• Writes involve 3 nodes (quorum)
• Good read scalability (5 nodes serving reads)
• Manageable consistency overhead

Going beyond 5 nodes has diminishing returns—write latency increases (larger quorum), and the additional fault tolerance is rarely needed.

We've explored the foundations of ZAB—the atomic broadcast protocol that makes Zookeeper possible. Let's consolidate the essential knowledge:

What's Next:

Now that you understand ZAB's core mechanics, the next page dives into leader-based ordering—how ZAB leverages a single leader to simplify the protocol, how leader election works, and what happens during leader transitions. This is where the rubber meets the road for understanding Zookeeper's behavior under failure conditions.