Raft Conflict Backtracking

When a follower rejects AppendEntries, it can return conflict information to help the leader skip back efficiently.

Given the leader's log terms and the follower's conflict reply:

• If conflictTerm == 0, the follower is missing entries. Set nextIndex = conflictIndex.
• Otherwise, if the leader has entries with conflictTerm, set nextIndex to last index of conflictTerm in the leader log + 1.
• If the leader does not have conflictTerm, set nextIndex = conflictIndex.

Indices are 1-based. An empty log has length 0.

Function signature

func NextIndexAfterConflict(leaderLog []int, conflictTerm int, conflictIndex int) int

Example

leaderLog     = [1,1,2,2,3]
conflictTerm  = 2
conflictIndex = 3

last index of term 2 is 4, so nextIndex = 5

Constraints

• 0 <= len(leaderLog) <= 100000
• 0 <= conflictTerm <= 1_000_000
• 1 <= conflictIndex <= len(leaderLog)+1

Notes

• This models the optimization described in the Raft paper.