Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

ECE 454 - Distributed Computing > Module 10d - RAFT > Flashcards

Module 10d - RAFT Flashcards

You may prefer our related Brainscape-certified flashcards:
Early Childhood Education flashcards
1
Q

What does RAFT stand for?

A

Replicated
And
Fault
Tolerant

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What does consensus mean in the context of RAFT?

A

Consensus:

  • Allows collection of machines to work as coherent group
  • Continuous service, even if machines fail
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are some disadvantages with Paxos when compared to RAFT?

A
  • Paxos is harder to understand
  • Paxos is incomplete, it only agrees on a single value
  • Paxos is inefficient
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the 3 main properties of RAFT

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What 3 states do servers have in RAFT?

A
  1. Follower (servers start as this)
  2. Candidate
  3. Leader
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

What does a candidate server do?

A
  • Follower becomes a Candidate if there’s no heartbeat

- Candidates issue RequestVote RPCs to get elected as a leader

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

What does a Leader server do?

A
  • 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

What does a Follower server do?

A

Leader or Candidate servers become followers by discovering a higher term

Follower servers are passive, but they expect regular heartbeats

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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?

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

For what case would there be 0 leaders?

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

Entries are stored on disk

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

In RAFT, what is a replicated state machine?

A

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
17
Q

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

A

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

18
Q

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

A

When less than a majority of servers are up and running

19
Q

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

A
  1. Leader assumes that its log is correct

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

20
Q

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

A

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
21
Q

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?
A
  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
22
Q

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

A

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

23
Q

Explain the leader election rules in RAFT

A
  • 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

ECE 454 - Distributed Computing (22 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions