go-raft-witness-quorum-log-replication

Answer

The bug. In Raft, an entry is committed only when it is stored on a majority of voting nodes (paper §5.4.1). A witness (non-voting) node replicates entries and applies them to its state machine, but its matchIndex must never be included when the leader computes the commit quorum. A naive leader that counts the witness's matchIndex sees "2 of 3 nodes match" (leader + witness) and advances commitIndex — even though only 1 of 2 voters holds the entry. If the leader then fails, the remaining voters elect a new leader that never saw the "committed" entry, and the committed entry is lost.

The fix. Compute the commit index from the sorted matchIndex values of voting nodes only (the paper's median-of-matchIndex rule), then apply Raft's current-term rule (§5.4.2). Witnesses keep replicating and applying — they just drop out of the quorum arithmetic.

type Role int

const (
    RoleVoter Role = iota
    RoleWitness
)

type Node struct {
    ID         string
    Role       Role
    MatchIndex int // highest log index known replicated on this node
}

type Leader struct {
    ID          string
    CurrentTerm int
    Log         []Entry // Log[0] is a dummy entry; real entries start at index 1
    Nodes       []*Node // every member, including the leader itself
    CommitIndex int
}

// votingQuorum: majority over VOTING nodes only — witnesses never counted.
func (l *Leader) votingQuorum() int {
    voters := 0
    for _, n := range l.Nodes {
        if n.Role == RoleVoter {
            voters++
        }
    }
    return voters/2 + 1
}

// AdvanceCommitIndex is the fix: quorum = voting nodes only.
func (l *Leader) AdvanceCommitIndex() int {
    var match []int
    for _, n := range l.Nodes {
        if n.Role == RoleVoter { // witnesses excluded — they cannot skew commit
            match = append(match, n.MatchIndex)
        }
    }
    if len(match) == 0 {
        return l.CommitIndex // a witness-only cluster can never commit
    }
    sort.Ints(match)
    // The (quorum)-th largest voting matchIndex is the highest index that a
    // quorum of voters is guaranteed to hold.
    candidate := match[len(match)-l.votingQuorum()]

    // Raft §5.4.2: only commit entries from the current term.
    if candidate > l.CommitIndex &&
        candidate <= l.LastIndex() &&
        l.Log[candidate].Term == l.CurrentTerm {
        l.CommitIndex = candidate
    }
    return l.CommitIndex
}

For contrast, the buggy variant differs in exactly two lines — it iterates over all nodes and uses the total node count for the quorum:

func (l *Leader) AdvanceCommitIndexNaive() int { // BUG: witness counted
    var match []int
    for _, n := range l.Nodes {
        match = append(match, n.MatchIndex) // ← witnesses included
    }
    sort.Ints(match)
    quorum := len(match)/2 + 1 // ← quorum over all nodes, not voters
    candidate := match[len(match)-quorum]
    // ...same commitTo logic
}

Witness behavior on the follower side is unchanged — witnesses receive AppendEntries, append to their log, and apply committed commands exactly like voters:

// Apply returns the commands a follower (voter OR witness) applies.
// Replication/application are identical; the witness distinction exists only
// in the leader's quorum computation.
func Apply(log []Entry, commitIndex int) []string {
    if commitIndex >= len(log) {
        commitIndex = len(log) - 1
    }
    out := make([]string, 0, commitIndex)
    for i := 1; i <= commitIndex; i++ {
        out = append(out, log[i].Data)
    }
    return out
}

Supporting details in the implementation: Replicate is monotonic (a follower that stored index N can never un-store it, so matchIndex only moves forward), and VoterCount(i) exposes the safety invariant checker (VoterCount(commitIndex) >= votingQuorum() must always hold).