etcd-io
Discussion: leader election in Raft maybe allows selecting a leader without fully owning committed log entries
In Figure 8 of the Raft paper , there is a scenario where a leader election process results in a leader that does not fully own all committed log entries.
This happens because Raft’s leader election mechanism only considers:
The latest log term
The log index
In the given scenario:
The previous term (term 2) log entries were not committed. However, if the log of term2 is committed, S5 will still be elected as the leader. A new term (term 3) starts, and a node S5 receives a new log entry (term 3) that is not committed. During the next leader election, S5 is elected as the new leader because its latest log term is 3, even though other nodes (e.g., S2, S3) have the same log index but with term 2. As a result, the new leader does not fully own all previously committed log entries.
I found that this is also implemented in the step method of raft.go and the isuptodate method of log.go. Can a new mechanism be added to avoid this situation?
For example, check the candidate's submitted log index and the follower's submitted log index to prevent this situation.
https://raft.github.io/raft.pdf
Not super up to date with raft paper and this problem, however for any changes in the raft algorithm they should be tested using TLA+ spec validation to be considered for implementation. CC @joshuazh-x who added TLA+ validation
In Figure 8 of the Raft paper , there is a scenario where a leader election process results in a leader that does not fully own all committed log entries. This happens because Raft’s leader election mechanism only considers: The latest log term The log index
In the given scenario:
The previous term (term 2) log entries were not committed. However, if the log of term2 is committed, S5 will still be elected as the leader. A new term (term 3) starts, and a node S5 receives a new log entry (term 3) that is not committed. During the next leader election, S5 is elected as the new leader because its latest log term is 3, even though other nodes (e.g., S2, S3) have the same log index but with term 2. As a result, the new leader does not fully own all previously committed log entries.
I found that this is also implemented in the step method of raft.go and the isuptodate method of log.go. Can a new mechanism be added to avoid this situation?
For example, check the candidate's submitted log index and the follower's submitted log index to prevent this situation.
https://raft.github.io/raft.pdf
log of term2 will not committed before new leader commit a log at new term.
You totally misunderstood the meaning of Figure 8. The point of Figure 8 is to illustrate that a leader cannot directly commit log entries from a previous term. You may want to look at phase (c): if the leader commits index=2 with term=2 directly, then its last log term and index will be (2,2). This opens the possibility for a node like S5, with a higher term log (e.g., term=3), to get elected—even though it doesn't contain the committed entry.
The usual way to avoid this is to propose a no-op entry in the current term, say (4,4). Once (4,4) is committed, it indirectly commits (2,2) as well. This ensures that only nodes that have (2,2) can get elected in the future, because otherwise they would lack a committed prefix of the log.
