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=⌊N/2⌋+1Q = \lfloor N/2 \rfloor + 1what its symbols mean and N=2f+1N = 2f + 1what its symbols mean.
  • 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 QQwhat its symbols mean of the NNwhat its symbols mean servers:

Q=⌊N2⌋+1Q = \left\lfloor \frac{N}{2} \right\rfloor + 1what its symbols mean

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

N=2f+1N = 2f + 1what its symbols mean
Cluster Size (NN) Majority Quorum (QQ) Fault Tolerance (ff)
3 nodes 2 nodes 11 failure tolerated
5 nodes 3 nodes 22 failures tolerated
7 nodes 4 nodes 33 failures tolerated

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

Why majorities work: any two majorities of the same NN servers share at least one server, because 2Q>N2Q > 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:

{S1,S2}∣{S3,S4,S5}\{S_1, S_2\} \quad \Big| \quad \{S_3, S_4, S_5\}what its symbols mean
  1. Minority side: if S1S_1what its symbols mean was leader, it still believes it is. It can append client writes and copy them to S2S_2what its symbols mean, but 2 servers are fewer than Q=3Q = 3what its symbols mean, so nothing commits. Those clients wait or time out; no write is acknowledged.
  2. Majority side: S3S_3what its symbols mean–S5S_5what its symbols mean stop hearing heartbeats. One times out first, starts a higher term and wins 3 votes. That side keeps committing writes.
  3. Healing: S1S_1 sees the higher term and steps down. The new leader overwrites S1S_1's and S2S_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.
Clients1× instanceLeader (server 1)1× instanceFollower (server 2)1× instanceFollower (server 3)1× instanceFollower (server 4)1× instanceCut-off follower(server 5)1× instanceClients1× instanceLeader (server 1)1× instanceFollower (server 2)1× instanceFollower (server 3)1× instanceFollower (server 4)1× instanceCut-off follower(server 5)1× instanceClients1× instanceLeader (server 1)1× instanceFollower (server 2)1× instanceFollower (server 3)1× instanceFollower (server 4)1× instanceCut-off follower(server 5)1× instance
Figure 4

A five-server Raft cluster: the leader copies each entry to the followers, and one server is cut off.

Follow a write from the clients: it goes to the leader, which appends it to its log and sends it to the followers. Once three of the five servers, a majority, hold the entry, it is committed and applied. Server 5 is cut off by a network partition and receives nothing, yet the cluster keeps committing, because the four connected servers still include a majority. If two more servers failed, nothing more could commit.

  • Clients: 1 × Users
  • Leader (server 1): 1 × App server
  • Follower (server 2): 1 × App server
  • Follower (server 3): 1 × App server
  • Follower (server 4): 1 × App server
  • Cut-off follower (server 5): 1 × App server
  • Clients sends requests to Leader (server 1)
  • Leader (server 1) sends requests to Follower (server 2)
  • Leader (server 1) sends requests to Follower (server 3)
  • Leader (server 1) sends requests to Follower (server 4)

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.
Sources5