A simple totally ordered broadcast protocol
📜 Abstract
This is a short overview of a totally ordered broadcast protocol used by ZooKeeper, called Zab. It is conceptually easy to understand, is easy to implement, and gives high performance. In this paper we present the requirements ZooKeeper makes on Zab, we show how the protocol is used, and we give an overview of how the protocol works.
✨ Summary
Summary
The paper presents Zab, a leader-based totally ordered broadcast protocol developed for the ZooKeeper coordination service. ZooKeeper maintains replicated in-memory state across a small ensemble of servers and uses Zab to ensure that write transactions are applied consistently at every replica.
Zab is designed around several guarantees: reliable delivery, total order, causal order, and a prefix property ensuring that proposals made by a leader before a delivered message cannot be lost. These guarantees are necessary because ZooKeeper transactions may be conditional, state-dependent, and non-idempotent before the leader converts them into idempotent state-record transactions.
The protocol has two operating modes. In broadcast mode, a leader assigns each proposal a monotonically increasing transaction identifier called a zxid, sends the proposal to followers over FIFO TCP channels, and waits for acknowledgements from a quorum. Once the proposal is durably recorded by the quorum, the leader issues a COMMIT and delivers the transaction. Followers deliver the transaction after receiving the COMMIT. This design permits multiple proposals in flight and avoids waiting for every server, improving throughput and availability during follower failures.
Recovery mode handles leader failures and loss of quorum. A newly elected leader must contain all transactions that may already have been committed, synchronize a quorum of followers, and ensure that transactions from the previous leader are either committed or discarded consistently. Zab uses epochs in the high-order bits of zxids to distinguish leadership periods and permits uncommitted proposals from older epochs to be skipped safely. Persistent transaction logs, snapshots, batching, and idempotent transactions support crash recovery and allow replay without requiring strict at-most-once delivery.
Influence and adoption
The paper established the initial concise description of Zab as the atomic-broadcast layer underlying ZooKeeper. Apache ZooKeeper documentation continues to identify Zab as the protocol used to propagate state changes and describes its leader-based recovery, prefix-ordering, and unique-sequence-number mechanisms. (cwiki.apache.org)
The work was subsequently developed into the more formal paper “Zab: High-performance broadcast for primary-backup systems,” which introduced and analyzed primary order and provided a fuller treatment of recovery and performance. (researchgate.net)
Its principal industry impact is through ZooKeeper, an Apache coordination service used as infrastructure by systems including Kafka, Hadoop, and HBase. The current Apache ZooKeeper project describes the service as a coordination system used by these distributed platforms, although that statement concerns ZooKeeper as a whole rather than independently measuring the impact of this specific paper. (zookeeper.apache.org)