raft-split-brain-recovery

Answer

The split-brain recovery protocol for a Raft-based KV store merges two divergent logs after a network partition using Lamport clocks (Raft terms) and last-writer-wins (LWW) semantics.

Algorithm:

1. Find the longest common prefix — entries committed before the partition are identical in both logs and form the deterministic base.
2. Collect divergent entries — entries after the divergence point from both logs are pooled together.
3. Sort by Lamport clock — entries are ordered by (term, index, key) ascending. Term is the Lamport clock providing causal ordering; index breaks ties within the same term; key is the final tiebreaker for full commutativity.
4. Apply LWW dedup — iterate in reverse, keeping only the last occurrence of each key (which has the highest term/index). This guarantees no lost acknowledged writes: every key appears with its latest (winner) value.
5. Restore ascending order — reverse the collected LWW entries back to causal order.

Code:

// LogEntry represents a single committed entry in a Raft log.
type LogEntry struct {
    Index uint64
    Term  uint64
    Key   string
    Value string
}

// MergeLogs reconciles two divergent Raft logs from a split-brain scenario.
func MergeLogs(logA, logB []LogEntry) []LogEntry {
    // Edge cases: both empty, one empty, identical logs
    if len(logA) == 0 && len(logB) == 0 {
        return []LogEntry{}
    }
    if len(logA) == 0 {
        return append([]LogEntry(nil), logB...)
    }
    if len(logB) == 0 {
        return append([]LogEntry(nil), logA...)
    }
    if len(logA) == len(logB) {
        identical := true
        for i := range logA {
            if !equal(logA[i], logB[i]) { identical = false; break }
        }
        if identical {
            return append([]LogEntry(nil), logA...)
        }
    }

    // Step 1: Find divergence point
    divergence := 0
    for divergence < len(logA) && divergence < len(logB) {
        if !equal(logA[divergence], logB[divergence]) { break }
        divergence++
    }

    // Step 2: Copy common prefix
    merged := make([]LogEntry, divergence)
    copy(merged, logA[:divergence])

    // Step 3: Collect and sort divergent entries
    tail := append(append([]LogEntry{}, logA[divergence:]...), logB[divergence:]...)
    sort.SliceStable(tail, func(i, j int) bool {
        if tail[i].Term != tail[j].Term { return tail[i].Term < tail[j].Term }
        if tail[i].Index != tail[j].Index { return tail[i].Index < tail[j].Index }
        return tail[i].Key < tail[j].Key
    })

    // Step 4+5: LWW (reverse pass) then restore ascending order
    seen := make(map[string]bool, len(tail))
    for i := len(tail) - 1; i >= 0; i-- {
        if !seen[tail[i].Key] {
            seen[tail[i].Key] = true
            merged = append(merged, tail[i])
        }
    }
    // Reverse the appended LWW entries
    for i, j := divergence, len(merged)-1; i < j; i, j = i+1, j-1 {
        merged[i], merged[j] = merged[j], merged[i]
    }
    return merged
}