Module 10d - RAFT

Question 1

What does RAFT stand for?

Answer 1

Replicated
And
Fault
Tolerant

Question 2

What does consensus mean in the context of RAFT?

Answer 2

Consensus:

• Allows collection of machines to work as coherent group
• Continuous service, even if machines fail

Question 3

What are some disadvantages with Paxos when compared to RAFT?

Answer 3

• Paxos is harder to understand
• Paxos is incomplete, it only agrees on a single value
• Paxos is inefficient

Question 4

What are the 3 main properties of RAFT

Answer 4

1. Leader election:
   - Selects one server to act as leader
   - If a crash is detected, it chooses a new leader
2. Log replication
   - Leader accepts commands from clients, appends to its log
   - Leader replicates its log to other servers
3. Safety
   - Keep logs consistent
   - Only servers with up-to-date logs can become leader

Question 5

What 3 states do servers have in RAFT?

Answer 5

1. Follower (servers start as this)
2. Candidate
3. Leader

Question 6

In RAFT, how does a Follower server become a Candidate server?

What does a candidate server do?

Answer 6

• Follower becomes a Candidate if there’s no heartbeat

- Candidates issue RequestVote RPCs to get elected as a leader

Question 7

In RAFT, how does a Candidate server become a Leader server?

What does a Leader server do?

Answer 7

• Candidate server becomes a leader if it wins an election

- Leader server issues AppendEntries RPCs to replicate its log to other servers & uses heartbeats to maintain leadership

Question 8

In RAFT, how many leaders per term? Give an upper and lower bound. Explain briefly

Answer 8

There can be either 1 or 0 leaders per term.

1 leader if there’s a successful election, and 0 if there’s a failed election

Question 9

In RAFT, how does a Leader or a Candidate server become a follower server?

What does a Follower server do?

Answer 9

Leader or Candidate servers become followers by discovering a higher term

Follower servers are passive, but they expect regular heartbeats

Question 10

In RAFT, each server maintains its current term value, and it is exchanged in every RPC.
From the perspective of the server:
1. What happens if a peer has a later term?
2. What happens if an incoming RPC has an obsolete term?

Answer 10

1. Peer has a later term? Update term, and then revert to being a follower
2. If the incoming RPC is from a peer with an obsolete term, then reply with an error

Question 11

RAFT election correctness has some safety mechanisms.
How many votes does each each server give?

For what case would there be 0 leaders?

Answer 11

• Each server gives only one vote per term
• A majority vote is required to win an election (at least 50%)
• Whenever the election leads to a failed election, by no majority vote from the other servers.

Question 12

RAFT’s election correctness has a liveness property that some candidate must eventually win an election. This is done with some randomness property - which is simpler than ranking
How does this work?

Answer 12

• There are election timeouts, which are randomly chosen between 150 and 300 ms
• Whichever server times out first wins the election
• Works well if broadcast time is low

Question 13

In RAFT, what happens in a normal series of operations step-by-step?

Answer 13

1. Client sends command to leader
2. Leader appends command to its log
3. Leader sends AppendEntries RPCs to all followers
4. Leader executes command in its state machine, returns result to client
5. Leader notifies followers to execute committed commands in their state machines

Question 14

In RAFT, what does the leader do in an operation if there are crashed or slow followers?

Answer 14

In the event of a failed operation, leader retries AppendEntries RPCs until they succeed

Question 15

How does RAFT ensure that the entries are not lost in the event of a crash?

Answer 15

Entries are stored on disk

Question 16

In RAFT, what is a replicated state machine?

Answer 16

A collection of servers, which contain:

• A log of events (which are operations)
• A state machine to compute logic
• Consensus module to ensure proper log replication

Question 17

In RAFT, what is the motivation for using a replicated log?

Answer 17

The replicated log ensures that state machines execute the same commands in the same order

Question 18

In RAFT, under what condition does the system stop making progress?

Answer 18

When less than a majority of servers are up and running

Question 19

How does RAFT remove the need for additional mechanisms to repair inconsistencies?

Answer 19

1. Leader assumes that its log is correct

2. Because of the structure of logs, normal operations will ensure all inconsistencies are eventually repaired

Question 20

In RAFT, the goal of the log matching property is that there should be a high level of consistency. What does this mean?

Answer 20

If log entries on different servers have the same index and term:

• They must store the same command
• The logs must be identical in all preceding entries
• If an entry is committed, all preceding entries are also committed

Question 21

For RAFT’s AppendEntries Consistency Check (sent by the leader):

1. What data does each AppendEntries RPC contain?
2. What must a follower contain to accept the request?
3. What happens if a follower rejects the request?

Answer 21

1. AppendEntries RPCs must include of entry preceding new one(s)
2. Follower must contain a matching entry (term and index) for the entry to be appended
3. If Follower rejects request, then leader will retry with a lower log index, and keep on retrying until a matching log

Question 22

For RAFT’s Safety Completeness property, what must happen to future leaders whenever a log entry is committed?

Answer 22

Once log entry is committed, then all future leaders must store that entry

Question 23

Explain the leader election rules in RAFT

Answer 23

• Servers with incomplete logs must not get elected
• Candidates include index and term of last log entry in RequestVote RPCs
• Voting server denies vote if its log is more up-to-date
• Logs are ranked by in the voting priority
• Servers can vote for themselves