1 of 82

Raft and Distributed Consensus

Michael

1

2 of 82

A Stateful Service

2

3 of 82

3

client

x:4

x←4

4 of 82

4

client

x:4

ok

5 of 82

High Availability

5

6 of 82

6

S

client 1

M

S

client 2

7 of 82

Challenges

7

8 of 82

Leader Who?

8

S

client 1

M

S

client 2

✘

9 of 82

Brain Split

9

S

client 1

M

S

client 2

10 of 82

Raft

10

11 of 82

11

2

x←2

y←3

x←4

Log

Consensus

Module

App State

Machine

1

x←2

y←3

x←4

Log

Consensus

Module

App State

Machine

client 2

3

x←2

y←3

x←4

Log

Consensus

Module

App State

Machine

client 1

12 of 82

Three Parts of Raft

Leader Election

Raft is a leader based protocol.
How to pick a leader.
How to recover from crashes, choose a new leader.

Log Replication

Leader accepts client command, append to its own log.
Leader replicates log to all followers.

Safety

Restriction on Candidacy, only vote for candidate “better” than me.
When can we consider a log entry as committed?
Why is committed an important concept

12

13 of 82

Leader Election

13

14 of 82

Server States

14

Follower

Candidate

Leader

win election

no heartbeat

start/recover

discover higher term

randomized timeout

discover current leader or new term

passive but expects a leader

request_vote RPC

append_entries RPC

Before we dive into examples, we need to know two concept related to election.

The first one is server state. Each node in the cluster can be one out of three states: Followe, Candidate, and Leader.

Follower is very passive it dies not proactively do anything. It expects to receive messages from leader. It also will answer request from a candidate, and remember who it votes for in a persistent variable called votedFor.

Each follower also has a forever going timer randomly initialized between 150ms to 300ms, if it does not hear from a leader, it will turn into a Candidate.

Candidate runs for election and will send out RPC to all the peers(no need to send message to itself). There are three outcomes of an election, either current node wins the election and it becomes the leader.

Or this current node does not win and two more cases will happen. When there is a split vote, the election timer will timeout and a new election will begin.

The third case is when some other node has won the election it receive the heartbeat from that leader at which point it learned there is a winner and happily get back to a Follower.

Finally if a Candidate wins the election it turns into a Leader. In this state, a node no longer needs to start election but sends out heartbeat at a rate much faster than election timeout(5ms-10ms) to notify other followers it's wellbeing to prevent them from turning into Candidates.

15 of 82

Terms/Quorum(Majority Vote)

15

Raft divide time into Terms

The second concept we need to know is Term.

In order to reach consensus, distributed system needs some mechanism to determine obsolete information. Term is such tool.

Term is a monotonically increasing integer persisted by each node locally and initialized to 0.

It represents each node’s best estimation of time. It is also the number of elections that this node is aware of.

This term information is exchanged at all messages, request has a node’s own term, and the response has the term of the receiver’s.

For example if an existing leader is network segmented, a new leader has been elected in the majority, all the nodes needs to be able to ignore the old leader.

These nodes are able to do this because old leader has a smaller term.

If we have a global view, we can see that wall time is divided into different terms.

The blue part is a short period of time where election happens, and rather quickly leadership is established until the leader crashes and an new election is thrown.

Sometimes there is split vote(Term 3), in which case there is no leader for that term. Re-election happens at Term 4.

16 of 82

Terms

16

Each Term starts with an election