Raft Joint Consensus Commit

During configuration changes, Raft uses joint consensus: a log index is committed only if it is stored on a majority of the old config and a majority of the new config.

Given the old/new configuration IDs and each server's matchIndex, return the largest index that is committed under joint consensus.

Types

type Match struct {
    ID    int
    Index int
}

Function signature

func JointCommitIndex(oldConfig []int, newConfig []int, matches []Match) int

Example

old = [1,2,3]
new = [2,3,4]
match = [{1,5}, {2,4}, {3,6}, {4,3}]

old majority indices: [6,5] -> 5
new majority indices: [6,4] -> 4
joint commit = min(5,4) = 4

Constraints

• 0 <= len(matches) <= 100000
• 0 <= Index <= 1_000_000
• IDs are unique within a config slice

Notes

• If a server in a config is missing from matches, treat its Index as 0.
• If a config is empty, its committed index is 0.