There are a number of questions here on StackOverflow around Figure 8, discussed in section 5.4.2 in the original Raft paper:
What has not been made clear by the paper and by none of the answers is the exact fate of that problematic entry (2, 3). My question is two-fold:
(2, 3), made by S5? The figure mentions that S5 will not become a leader because majority will reject its RequestVotes. Does that mean that upon receiving AppendEntries RPC, S5 will then overwrite its entry (2, 3) with (2, 2) and (3, 4) as per current leader in (e)?(1, 3) receive? Do the clients receive acknowledgements for uncommitted entries as if they were already applied to a state-machine?The figure mentions that S5 will not become a leader because majority will reject its RequestVotes
As in (e) in raft paper, S5 will not become a leader because the logs of S5 is not at least up to date with the logs of majority (S1,S2,S3)
Does that mean that upon receiving AppendEntries RPC, S5 will then overwrite its entry (2, 3) with (2, 2) and (3, 4) as per current leader in (e)?
Yes, the logs of S5 will be overwritten by the logs of the current leader. Quoted from raft paper:
If a follower’s log is inconsistent with the leader’s, the AppendEntries consistency check will fail in the next AppendEntries RPC. After a rejection, the leader decrements nextIndex and retries the AppendEntries RPC. Eventually nextIndex will reach a point where the leader and follower logs match. When this happens, AppendEntries will succeed, which removes any conflicting entries in the follower’s log and appends entries from the leader’s log (if any).
Do the clients receive acknowledgements for uncommitted entries as if they were already applied to a state-machine?
No, the clients only receive acknowledgements for committed entries when the entry has been safely replicated. Please see a quote from raft paper:
When the entry has been safely replicated (as described below), the leader applies the entry to its state machine and returns the result of that execution to the client.
There is also a case when the leader has replicated the log entry but crashes before responding to client or the response is lost when being sent over the network, the client needs to retry causing the command to be executed multiple times. Quouted from raft paper:
However, as described so far Raft can execute a command multiple times: for example, if the leader crashes after committing the log entry but before responding to the client, the client will retry the command with a new leader, causing it to be executed a second time. The solution is for clients to assign unique serial numbers to every command. Then, the state machine tracks the latest serial number processed for each client, along with the associated response. If it receives a command whose serial number has already been executed, it responds immediately without re-executing the request