Distributed Systems · 8 min read

Distributed Systems #5

Distributed Systems Part-5 (Consensus Algorithms)

Consensus Algorithms in Distributed Systems

On this page
  1. What consensus actually means
  2. Paxos
  3. Raft
  4. Leader election
  5. Log replication
  6. Safety
  7. ZAB
  8. Why consensus is expensive

Part 5: Consensus Algorithms

In Part 4, we talked about linearizability as the strongest consistency guarantee a system can offer, and mentioned that providing it requires real coordination between nodes. This part is about what that coordination actually looks like in practice. Consensus algorithms are the machinery that lets a group of unreliable nodes, running on an unreliable network, agree on a single value or a single sequence of operations, even when some of them crash along the way.

This is also where the FLP impossibility result from Part 1 comes back into the picture. FLP tells us that perfect, guaranteed consensus is impossible in a fully asynchronous system if even one node can fail. Every algorithm in this part is a practical way of living with that limitation, usually by leaning on timeouts and the partially synchronous model we discussed back then, rather than trying to defeat it outright.

What consensus actually means

Before getting into specific algorithms, it helps to be precise about what problem they are solving. Consensus means getting a group of nodes to agree on one single value, even if multiple nodes propose different values at the same time, and even if some nodes crash or messages get delayed along the way.

This sounds abstract, but it shows up constantly in real systems. Electing a leader is a consensus problem, since every node needs to agree on who the leader is. Committing a transaction across multiple nodes is a consensus problem. Appending an entry to a replicated log, the kind of log a database uses to keep replicas in sync, is a consensus problem too, since every replica needs to agree on the exact sequence of entries.

A correct consensus algorithm needs to guarantee two things:

  • Safety, meaning nodes never agree on two different values for the same decision, no matter what fails.
  • Liveness, meaning the system eventually makes progress and actually reaches a decision, as long as enough nodes are healthy and can talk to each other.

Safety is usually the easier property to guarantee. Liveness is where FLP bites, which is why every practical algorithm accepts some risk of temporarily stalling rather than promising it can always make progress no matter what.

Paxos

Paxos, introduced by Leslie Lamport in the late 1980s, was the first widely studied algorithm to solve this problem rigorously. It has a reputation for being difficult to understand, and that reputation is largely deserved, but the core idea is not as scary as it sounds.

Paxos works in rounds, and involves nodes playing one or more of three roles: proposers, who suggest values, acceptors, who vote on proposed values, and learners, who find out what value was chosen. A single node can play multiple roles at once.

Each round happens in two phases. In the first phase, a proposer picks a round number higher than any it has used before, and asks a majority of acceptors to promise that they will ignore any proposal with a lower number. Along with that promise, each acceptor reports back any value it has already accepted in an earlier round. If a majority agrees, the proposer moves to the second phase, where it actually proposes a value, and acceptors either accept it or reject it depending on what they have already promised. There is one crucial rule here: if any acceptor reported an earlier accepted value, the proposer must propose that value (the one from the highest-numbered round), not its own. This is what stops a later round from overturning a value that may already have been chosen. A value is considered chosen once a majority of acceptors have accepted it, which is why Paxos, like most consensus algorithms, needs a majority of nodes to be alive and reachable to make progress at all.

text
Phase 1  Proposer → acceptors:  "Prepare round 5"
         Acceptors → proposer:  "Promise: nothing below 5. I already accepted: none"
Phase 2  Proposer → acceptors:  "Accept round 5, value X"
         Majority accepts       → X is chosen, learners are told

The tricky part of Paxos, and the reason it has a reputation for being hard to implement correctly, is handling competing proposers, retries, and edge cases around crashes mid round, all while still preserving safety. Basic Paxos also only agrees on a single value at a time, so real systems use a variant called Multi-Paxos, which streamlines the process for agreeing on a long sequence of values, like the entries in a replicated log, without repeating the full two phase process for every single entry.

Raft

Raft was designed specifically to be easier to understand and implement correctly than Paxos, without sacrificing the same safety guarantees. It has become extremely popular in real systems precisely because of this, showing up in etcd, Consul, and CockroachDB, among others.

Raft splits the problem into three separate, more approachable pieces: leader election, log replication, and safety.

Leader election

Leader election works through randomized timeouts. Every node starts as a follower. If a follower does not hear from a leader within a random amount of time, it assumes the leader is gone, becomes a candidate, starts a new term (a numbered election period, so everyone can tell an old leader from a new one), and requests votes from the other nodes. Each node votes for at most one candidate per term, and whichever candidate gets votes from a majority becomes the new leader. Randomizing the timeout is a small but important detail, since it makes it unlikely that two nodes become candidates at exactly the same time and split the vote repeatedly.

mermaid
stateDiagram-v2
    direction LR
    [*] --> Follower
    Follower --> Candidate: no heartbeat before timeout
    Candidate --> Leader: wins a majority of votes
    Candidate --> Candidate: split vote, new term
    Candidate --> Follower: sees a leader with a newer term
    Leader --> Follower: sees a newer term

Log replication

Log replication is the leader's job once elected. All client requests go through the leader, which appends them to its own log and then replicates them to followers. An entry is considered committed, meaning it is safe and will not be lost, once a majority of nodes have it in their log. Followers apply committed entries to their own state in the same order the leader did, which is what keeps replicas consistent with each other.

Safety

Safety in Raft comes from a set of rules around exactly which node is allowed to become leader. Roughly speaking, a node will refuse to vote for a candidate whose log is less up-to-date than its own, so a candidate can only win if its log is at least as up-to-date as a majority of the cluster. This prevents a node with stale or missing data from ever overwriting more recent, committed entries. Terms also handle the split-brain case from Part 3: an old leader that comes back still using an older term is ignored, and steps down as soon as it sees the newer one.

The reason Raft feels more approachable than Paxos is that it maps very directly onto an actual implementation. Where Paxos is often described as an abstract protocol, Raft was designed from the start with real systems and real logs in mind, which is a big part of why it has become the default choice for new systems that need consensus.

ZAB

ZAB, short for ZooKeeper Atomic Broadcast, is the consensus protocol behind Apache ZooKeeper, one of the older and still widely used coordination services in distributed systems.

ZAB is conceptually similar to Raft in that it relies on a single leader that proposes updates, and followers that acknowledge and apply them once a majority has agreed. Where ZAB differs is that it was designed specifically around ZooKeeper's use case, atomic broadcast of state changes, meaning every node applies the exact same sequence of updates in the exact same order, which is exactly the kind of primitive tools like distributed locks and configuration management need underneath them. (The Key-Value Store design uses ZooKeeper for exactly this kind of cluster configuration.)

ZooKeeper predates Raft by several years. Raft's creators, Diego Ongaro and John Ousterhout, built it mainly because they found Paxos too hard to understand and teach, and they drew on earlier leader-based protocols like ZAB along the way, aiming for the same guarantees with a specification that was actually easy to reason about. That said, ZAB has been running in production for a very long time, and plenty of real systems still depend on it today through ZooKeeper directly.

PaxosRaftZAB
LeaderNot required (Multi-Paxos usually uses one)Always one leader per termAlways one leader
Main goalAgree on a value, proven correctBe easy to understand and implementAtomic broadcast for ZooKeeper
Where you'll find itGoogle's Chubby and Spanneretcd, Consul, CockroachDBZooKeeper

Why consensus is expensive

It is worth being honest about the cost of all this. Every consensus algorithm in this part requires a round trip to a majority of nodes before anything can be considered official, whether that is electing a leader or committing a log entry. That majority requirement is not a detail, it is the actual mechanism that provides safety, since any two majorities in a cluster are guaranteed to overlap by at least one node, which is what prevents the system from making two contradictory decisions at once. (It's the same overlap idea as W + R > N in leaderless quorums.)

It also explains why consensus clusters almost always have an odd number of nodes. A cluster needs a majority alive to make progress, so adding a fourth node to a three-node cluster costs another machine without letting it survive any more failures:

Cluster sizeMajority neededNode failures it survives
321
431
532
743

This is exactly why consensus is reserved for the operations that genuinely need it, like leader election or committing critical metadata, rather than being used for every single read and write an application makes. Using it everywhere would mean paying a majority round trip on every operation, which defeats the point of having fast, highly available systems in the first place. Most real architectures use consensus sparingly and specifically, often through a small dedicated coordination service like etcd or ZooKeeper, rather than baking it directly into every part of the application.