Search code examples
raft

Confusion about raft algorithm

In the paper 《 In Search of an Understandable Consensus Algorithm 》, Figure 8 shows a problem in (d) and (e) that some old logs may be overwritten and never come back.

In section 5.4.2, it says “To eliminate problems like the one in Figure 8, Raft never commits log entries from previous terms by counting replicas. Only log entries from the leader’s current term are committed by counting replicas; once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property”.

I'm confused about that part, how does it works in Figure 8? What will happen and what will not?

Solution

  • By adding the rule to figure 8.

    Raft never commits log entries from previous terms by counting replicas.

    So now we never commits log entries from previous terms, let see what will happen again at figure 8. I modified figure 8 to show the situation after apply the rule. enter image description here

    (a) and (b) works the same.

    Start from (c), log entry at index 2 is append at term 2 since step (a), where I draw a yellow circle. So it is from previous terms. Thus the leader will not replicate that entry (the yellow 2 with my black cross) according the rule. It must start replicate from entry at index 3.

    This rule also mentioned at Figure 2 "Rules for Servers" leader's rule 3.1:

    Send AppendEntries RPC with entries startting at nextIndex.

    The nextIndex is initialized with last log index + 1, so it should start at log index 3 at (c), not index 2.

    So for the hypothetical procedure at original (c), it is impossible to append log 2 to majority before log 3（the pink one appended at term 4） replicate at majority. and (d) will not happen.

    UPDATE: 2020-12-04

    @coderx and @OrlandoL have comments discussed about the (a), (b) and how S5 can't be a leader. Their discuss makes this answer more complete, So I put a reference here.

    Basically, (a), (b) is not a must-happen condition, there are cases that S5 won't elected leader, such as S3,S4 have same chance to become leader. (please see the comments for detail)

    These assumption is correct that S5 may not become a leader and the following procedure won't happen.

    But let's go back to the paper Figure 8 and read the annotation of the figure:

    A time sequence showing why a leader cannot determine commitment using log entries from older terms. In (a) S1 is leader and partially replicates the log entry at index 2. In (b) S1 crashes; S5 is elected leader for term 3 with votes from S3, S4, and itself, and accepts a different entry at log index 2.

    IMO, the author is talking about the case that S5 is elected leader. Thus the whole procedure makes scene.

    As @OrlandoL mentioned, In a MIT 6.824 Lab, you should consider all conditions to have a correct Raft implementation.

    Hope this helps.