Consistency Levels and Consensus Algorithms: Paxos, ZAB, and Raft

Since Google introduced the Google File System (GFS) in 2003, the importance of building reliable storage on cheap, unreliable hardware has become evident, with multi‑replica redundancy being a key factor and data consistency across replicas emerging as a core challenge in distributed systems.

The CAP theorem states that a distributed system can at most simultaneously satisfy two of three properties—Consistency, Availability, and Partition tolerance—making consistency a trade‑off against availability depending on application requirements, such as strong consistency for financial transactions versus eventual consistency for media storage.

Common consistency levels include strong consistency, monotonic consistency, session consistency, eventual consistency, and weak consistency, each defining how and when updates become visible to clients.

Paxos Consensus Algorithm —proposed by Leslie Lamport in 1990—relies on message passing, tolerates lost, delayed, or duplicated messages, and proceeds through a two‑phase process (prepare and accept) with roles such as proposer, acceptor, and learner, ensuring that once a value is chosen it remains immutable.

ZAB Consensus Algorithm underpins Apache Zookeeper, operating in a recovery mode during leader failures and a broadcast mode during normal operation, using a leader‑centric proposal (ZXID) and majority acknowledgments to achieve replication and fault tolerance.

Raft Consensus Algorithm simplifies Paxos by defining three roles (leader, follower, candidate) and three core components: leader election, log replication, and safety. It uses terms as logical clocks, assigns monotonically increasing indices to log entries, and ensures that a majority of nodes must acknowledge entries before they are committed.

In CB‑SQL, Raft is employed to guarantee strong consistency across range replicas. The system addresses two challenges: Multi‑Raft network optimization—sharing a single communication link between any two nodes to reduce connection overhead—and consistency reads, which use a lease‑based lock (Latch) to enforce linearizability without incurring the full cost of log‑based reads.

Overall, the article provides a comprehensive overview of consistency models and consensus mechanisms essential for designing reliable, scalable distributed storage systems.