Zab: High-performance broadcast for primary-backup systems
📜 Abstract
Zab is a crash-recovery atomic broadcast algorithm we designed for the ZooKeeper coordination service. ZooKeeper implements a primary-backup scheme in which a primary process executes clients operations and uses Zab to propagate the corresponding incremental state changes to backup processes¹. Due the dependence of an incremental state change on the sequence of changes previously generated, Zab must guarantee that if it delivers a given state change, then all other changes it depends upon must be delivered first. Since primaries may crash, Zab must satisfy this requirement despite crashes of primaries. Applications using ZooKeeper demand high-performance from the service, and consequently, one important goal is the ability of having multiple outstanding client operations at a time. Zab enables multiple outstanding state changes by guaranteeing that at most one primary is able to broadcast state changes and have them incorporated into the state, and by using a synchronization phase while establishing a new primary. Before this synchronization phase completes, a new primary does not broadcast new state changes. Finally, Zab uses an identification scheme for state changes that enables a process to easily identify missing changes. This feature is key for efficient recovery. Experiments and experience so far in production show that our design enables an implementation that meets the performance requirements of our applications. Our implementation of Zab can achieve tens of thousands of broadcasts per second, which is sufficient for demanding systems such as our Web-scale applications.
✨ Summary
Paper summary
Zab is a crash-recovery atomic broadcast protocol designed for ZooKeeper’s primary-backup replication model. Its central contribution is primary order, which preserves the order of state changes both within one primary’s tenure and across successive primaries. This is necessary because ZooKeeper transactions are incremental, non-commutative updates whose correctness depends on applying them in sequence.
The protocol uses three phases: discovery, synchronization, and broadcast. Discovery selects a prospective leader and identifies the most advanced surviving transaction history. Synchronization establishes the leader and causes a quorum to adopt and deliver the selected history before new transactions can be broadcast. Broadcast then disseminates transactions in increasing zxid order, requiring stable-storage acknowledgments from a quorum before committing them. A zxid combines an epoch number with a per-epoch counter, allowing missing suffixes of transaction histories to be identified efficiently during recovery.
The paper argues that ordinary Paxos does not directly provide the required primary-order behavior when multiple transactions are outstanding, unless proposals are serialized or batched. Zab instead permits a continuous stream of outstanding transactions while retaining ordering and recovery guarantees. The reported Java implementation achieved tens of thousands of broadcasts per second; performance was primarily limited by leader network bandwidth when disk write caching was enabled, while disabling the cache made the system substantially more I/O-bound.
Influence
Zab became the atomic broadcast foundation of ZooKeeper. Apache’s documentation describes ZooKeeper’s synchronization mechanism as a quorum-based atomic messaging system using ordered proposals, persistent acknowledgments, and transaction identifiers that expose the global order. (zookeeper.apache.org)
Subsequent research formalized and generalized the paper’s primary-order concept. On Barriers and the Gap between Active and Passive Replication explicitly analyzes Zab alongside other primary-order atomic broadcast protocols and characterizes the synchronization barrier required when changing primaries. (arxiv.org)
The protocol has also been used as a subject for formal specification, testing, and systems research. A later study developed a TLA+ specification of Zab and used it to guide testing of the ZooKeeper implementation, while storage-recovery work has adapted Zab’s epoch-and-index transaction identifiers for protocol-aware recovery. (arxiv.org)
The paper was published in the 2011 IEEE/IFIP 41st International Conference on Dependable Systems and Networks, held June 27–30, 2011. (proceedings.com)