Lesson 8.4• 10 min read

Consensus and leader election: Raft and Paxos

Split-brain prevention, majority quorums, state machine replication, and randomized election timeouts.

What you will learn

Say what consensus and a replicated log are for, and why split brain is dangerous.
Size a cluster from the failures it must survive: $Q = \lfloor N/2 \rfloor + 1$ and $N = 2f + 1$ .
Follow Raft through leader election, log replication and a network partition.

The consensus problem and split-brain hazards

Consensus is getting several servers to agree on a value, or on the order of a sequence of commands, despite failures. With a replicated log, every server applies the same commands in the same order and so reaches the same state. This is the state machine replication Raft is built for.

If two servers both believe they are the primary (split brain), both accept writes, and their data diverges in ways that may not be reconcilable automatically. Consensus algorithms are designed so this cannot happen.

Majorities and fault tolerance

Decisions need a majority $Q$ of the $N$ servers:

Q = \left\lfloor \frac{N}{2} \right\rfloor + 1

Raft and Paxos tolerate servers that crash or become unreachable, not ones that lie (non-Byzantine failures). To keep working with $f$ such servers down, you need:

N = 2f + 1

Cluster Size ( $N$ )	Majority Quorum ( $Q$ )	Fault Tolerance ( $f$ )
3 nodes	2 nodes	$1$ failure tolerated
5 nodes	3 nodes	$2$ failures tolerated
7 nodes	4 nodes	$3$ failures tolerated

Even clusters gain nothing: 4 servers tolerate 1 failure, the same as 3.

Why majorities work: any two majorities of the same $N$ servers share at least one server, because $2Q > N$ . So a value accepted by one majority is held by at least one member of every later majority. Raft builds its safety rule on this overlap (below).

Raft

Ongaro and Ousterhout (Stanford) designed Raft to be easier to understand than Paxos. Their paper says it "produces a result equivalent to (multi-)Paxos, and it is as efficient as Paxos". Raft separates leader election, log replication and safety.

1. Leader election

Each server is a follower, candidate or leader. Time is divided into numbered terms, and each term has at most one leader.
A follower that hears no heartbeat before its election timeout increments its term, becomes a candidate, votes for itself and sends RequestVote to the others. It wins with votes from a majority.
Timeouts are "chosen randomly from a fixed interval (e.g., 150–300ms)", so one server usually times out first and wins before others start. This makes split votes rare.
Terms act as a logical clock. A leader or candidate that sees a higher term "immediately reverts to follower state".

2. Log replication

Clients send commands to the leader. The leader appends each command to its log and sends AppendEntries to the followers.
An entry is committed once the leader that created it has stored it on a majority of servers. The leader then applies it to its state machine and returns the result to the client. Followers apply committed entries in log order.
If a follower's log disagrees with the leader's, the leader overwrites the conflicting entries with its own.
A subtlety (Raft section 5.4.2): a leader only commits entries from its own term by counting copies. Older entries become committed along with them. That is why a new leader starts its term by committing a blank no-op entry (Raft section 8).

3. Safety: the election restriction

A voter refuses its vote if its own log is more up to date than the candidate's. The later last term wins; if those are equal, the longer log wins.
Every committed entry is on a majority, and a winner needs votes from a majority. Those majorities overlap, so a candidate missing a committed entry cannot win. Every new leader therefore already holds all committed entries.

A network partition in Raft

Split a 5-server cluster:

\{S_1, S_2\} \quad \Big| \quad \{S_3, S_4, S_5\}

Minority side: if $S_1$ was leader, it still believes it is. It can append client writes and copy them to $S_2$ , but 2 servers are fewer than $Q = 3$ , so nothing commits. Those clients wait or time out; no write is acknowledged.
Majority side: $S_3$ – $S_5$ stop hearing heartbeats. One times out first, starts a higher term and wins 3 votes. That side keeps committing writes.
Healing: $S_1$ sees the higher term and steps down. The new leader overwrites $S_1$ 's and $S_2$ 's uncommitted entries with its own log. Two servers may each have thought they were leader for a while, in different terms, but only one could ever commit, so no committed write is lost.

Raft leader election and log replication

Majority Q = ⌊N/2⌋ + 1 = 3. Time out a server to start an election, write through a leader, or split the network.

Server 1

Leader, term 1

t1t1

2 committed, 0 pending

Server 2

Follower, term 1

t1t1

2 committed, 0 pending

Server 3

Follower, term 1

t1t1

2 committed, 0 pending

Server 4

Follower, term 1

t1t1

2 committed, 0 pending

Server 5

Follower, term 1

t1t1

2 committed, 0 pending

Committed log (stored by a majority)

#1t1SET balance:usr_1=500
#2t1SET balance:usr_2=320

Events

5-server cluster. Server 1 leads term 1. A majority is 3 servers, so the cluster survives 2 crashed servers.

Figure 4: 5-Node Raft Consensus Cluster replicating append-only commit logs across majority quorum (3 of 5 nodes).

Key takeaways

Any two majorities share a server, so a value accepted by one majority is held by at least one member of every later majority.
Even clusters gain nothing: 4 servers tolerate one failure, the same as 3.
Raft elects a leader with randomized timeouts and terms, and commits an entry once the leader that created it has stored it on a majority; voters refuse candidates with less up-to-date logs.
During a partition only the majority side can commit; the old leader steps down when it sees a higher term, and its uncommitted entries are overwritten.

Sources

Adapted from The System Design Primer by Donne Martin, licensed under CC BY 4.0. Changes were made.