Consensus: Raft

Raft gives you one key guarantee:

If a log entry is committed, every future leader will preserve that entry.

This module is intentionally implementation-first. You will build each follower or leader decision path used in core Raft replication.

Learning goals

• Build a precise mental model for terms, log indices, and commit rules.
• Implement vote, append, and commit decisions exactly as the contracts require.
• Understand why each safety check exists and what breaks if it is skipped.
• Compose single-purpose helpers into one milestone follower RPC handler.

State model used in this pack

All problems use integer terms and 1-based log indexing.

• CurrentTerm: monotonic term seen by node.
• VotedFor: candidate ID voted in CurrentTerm, or -1 if none.
• LogTerms[i]: term at log index i+1.
• CommitIndex: highest log index known committed.

When log is empty:

• LastLogIndex = 0
• LastLogTerm = 0

Core invariants you should never violate

1. Term monotonicity

A node never decreases CurrentTerm.

1. Single vote per term

A follower grants at most one candidate in the same term, except repeated vote for the same candidate.

1. Prev-log match before append

Follower accepts new entries only if (PrevLogIndex, PrevLogTerm) matches its own log.

1. Conflict truncate point

For full append handling, truncate only at first index where existing term and incoming term differ.

1. Commit only current-term entry (leader rule)

Leader should not advance commit index based only on majority unless target index term equals currentTerm.

1. Joint consensus commit rule

During config change, committed index must satisfy majority in old config and majority in new config; final commit is the minimum of those two.

1) Vote granting (raft-vote-grant)

Contract

Grant vote iff all three checks pass:

1. candidateTerm >= currentTerm
2. votedFor == -1 or votedFor == candidateID
3. Candidate log is at least as up-to-date:
   • candidateLastTerm > localLastTerm, or
   • equal term and candidateLastIndex >= localLastIndex

Decision table

• Lower term candidate: reject immediately.
• Different already-voted candidate in same term: reject.
• Candidate newer term log: grant.
• Candidate same last term but shorter index: reject.

Near-solution implementation

func ShouldGrantVote(
    currentTerm, votedFor, candidateID, candidateTerm,
    candidateLastIndex, candidateLastTerm,
    localLastIndex, localLastTerm int,
) bool {
    if candidateTerm < currentTerm {
        return false
    }
    if votedFor != -1 && votedFor != candidateID {
        return false
    }

    if candidateLastTerm > localLastTerm {
        return true
    }
    if candidateLastTerm < localLastTerm {
        return false
    }
    return candidateLastIndex >= localLastIndex
}

Worked trace

currentTerm=5, votedFor=-1 candidateTerm=5 candidateLastTerm=3, candidateLastIndex=10 localLastTerm=3, localLastIndex=12

Term check passes, vote availability passes, log freshness fails (10 < 12), so result is false.

Common mistakes

• Comparing only indices and ignoring terms.
• Rejecting same candidate when votedFor == candidateID.
• Forgetting empty log baseline (0,0).

2) AppendEntries (simple truncate+append) (raft-append-entries)

Contract

Accept request only if:

• prevLogIndex <= len(logTerms)
• if prevLogIndex > 0, then logTerms[prevLogIndex-1] == prevLogTerm

On accept:

• Keep prefix [1..prevLogIndex]
• Append all incoming entries

On reject:

• Return original log unchanged.

Why this exists

This isolates the fundamental "prefix must match" rule before full Raft conflict handling.

Near-solution implementation

func AppendEntries(logTerms []int, prevLogIndex int, prevLogTerm int, entries []int) ([]int, bool) {
    if prevLogIndex < 0 || prevLogIndex > len(logTerms) {
        return append([]int{}, logTerms...), false
    }
    if prevLogIndex > 0 && logTerms[prevLogIndex-1] != prevLogTerm {
        return append([]int{}, logTerms...), false
    }

    newLog := append([]int{}, logTerms[:prevLogIndex]...)
    newLog = append(newLog, entries...)
    return newLog, true
}

Worked trace

log=[1,1,2,2], prev=(2,1), entries=[3,3]

• Prefix [1,1] matches.
• Keep [1,1], append [3,3].
• New log [1,1,3,3].

Common mistakes

• Appending to full log without truncating at prevLogIndex.
• Mutating input slice in place in tests that expect defensive copy behavior.

3) Full AppendEntries follower handling (raft-append-entries-full)

This is the real follower-side append logic including term update, conflict scan, and commit index update.

Contract recap

1. Reject if rpc.Term < state.CurrentTerm.
2. If rpc.Term > state.CurrentTerm, set state.CurrentTerm = rpc.Term.
3. Reject if prev-log pointer does not match.
4. On accept, compare existing entries against incoming entries starting at PrevLogIndex+1:
   • same term at same index: keep and continue
   • different term at same index: truncate at that index and append remaining
   • ran past end of local log: append remaining
5. Set CommitIndex = min(LeaderCommit, len(LogTerms)).
6. Success response uses MatchIndex = PrevLogIndex + len(Entries) after apply.

Mental model

Think in 3 phases:

• Gate: term and prev-log checks.
• Merge: preserve matching prefix, replace conflicting suffix.
• Commit: follower moves commit pointer only up to what it actually stores.

Near-solution implementation

type State struct {
    CurrentTerm int
    LogTerms    []int
    CommitIndex int
}

type AppendEntriesRPC struct {
    Term         int
    PrevLogIndex int
    PrevLogTerm  int
    Entries      []int
    LeaderCommit int
}

type AppendResp struct {
    Term       int
    Success    bool
    MatchIndex int
}

func ApplyAppendEntries(state State, rpc AppendEntriesRPC) (State, AppendResp) {
    resp := AppendResp{Term: state.CurrentTerm, Success: false, MatchIndex: 0}

    if rpc.Term < state.CurrentTerm {
        return state, resp
    }
    if rpc.Term > state.CurrentTerm {
        state.CurrentTerm = rpc.Term
        resp.Term = rpc.Term
    }

    if rpc.PrevLogIndex > len(state.LogTerms) {
        return state, resp
    }
    if rpc.PrevLogIndex > 0 && state.LogTerms[rpc.PrevLogIndex-1] != rpc.PrevLogTerm {
        return state, resp
    }

    idx := rpc.PrevLogIndex
    for i := 0; i < len(rpc.Entries); i++ {
        pos := idx + 1 + i // 1-based index for incoming entry
        term := rpc.Entries[i]

        if pos <= len(state.LogTerms) {
            if state.LogTerms[pos-1] != term {
                state.LogTerms = append([]int(nil), state.LogTerms[:pos-1]...)
                state.LogTerms = append(state.LogTerms, rpc.Entries[i:]...)
                idx = pos - 1 + len(rpc.Entries[i:])
                goto commit
            }
            // matching term, continue
        } else {
            state.LogTerms = append(state.LogTerms, rpc.Entries[i:]...)
            idx = pos - 1 + len(rpc.Entries[i:])
            goto commit
        }
    }

    idx = rpc.PrevLogIndex + len(rpc.Entries)

commit:
    if rpc.LeaderCommit < len(state.LogTerms) {
        state.CommitIndex = rpc.LeaderCommit
    } else {
        state.CommitIndex = len(state.LogTerms)
    }

    resp.Success = true
    resp.MatchIndex = idx
    resp.Term = state.CurrentTerm
    return state, resp
}

Worked conflict trace

Initial:

• LogTerms=[1,1,2,4,4]
• PrevLogIndex=3, PrevLogTerm=2
• Entries=[3,3]

Compare from index 4:

• local term at 4 is 4, incoming is 3 -> conflict.
• Truncate from index 4 onward: [1,1,2].
• Append remaining incoming [3,3] -> [1,1,2,3,3].

Common mistakes

• Truncating unconditionally before comparing terms.
• Updating commit index beyond local log length.
• Returning stale response term after term bump.

4) Leader commit index (raft-commit-index)

Contract

Find largest committed index N such that:

• majority has matchIndex >= N
• logTerms[N-1] == currentTerm

Return 0 if none.

Mental model

1. Majority support gives a highest possible candidate.
2. Current-term filter may force backing off to older index in same majority envelope.

Near-solution implementation

func CommitIndex(matchIndex []int, logTerms []int, currentTerm int) int {
    if len(matchIndex) == 0 || len(logTerms) == 0 {
        return 0
    }

    indexes := append([]int{}, matchIndex...)
    sort.Sort(sort.Reverse(sort.IntSlice(indexes)))

    // For n nodes, majority element in descending order is at n/2.
    majorityPos := len(indexes) / 2
    candidate := indexes[majorityPos]

    if candidate > len(logTerms) {
        candidate = len(logTerms)
    }

    for i := candidate; i >= 1; i-- {
        if logTerms[i-1] == currentTerm {
            return i
        }
    }
    return 0
}

Worked trace

match=[5,5,4,3,2], sorted descending already.

• majority position 5/2 = 2 -> candidate 4.
• if logTerms[3] is current term, commit 4; else scan down to first current term entry.

Common mistakes

• Returning candidate immediately without current-term check.
• Using strict majority formula wrong for even cluster sizes.
• Forgetting to cap candidate by log length.

5) Conflict backtracking optimization (raft-conflict-backtrack)

Contract

Given follower conflict reply (conflictTerm, conflictIndex):

• if conflictTerm == 0: follower is too short -> nextIndex = conflictIndex
• else if leader has conflictTerm: nextIndex = lastIndexOf(conflictTerm)+1
• else: nextIndex = conflictIndex

Why this matters

Without this, leader decrements one by one and replication can become very slow on large divergent tails.

Near-solution implementation

func NextIndexAfterConflict(leaderLog []int, conflictTerm int, conflictIndex int) int {
    if conflictTerm == 0 {
        return conflictIndex
    }

    last := -1
    for i := len(leaderLog) - 1; i >= 0; i-- {
        if leaderLog[i] == conflictTerm {
            last = i + 1 // convert to 1-based
            break
        }
    }

    if last == -1 {
        return conflictIndex
    }
    return last + 1
}

Worked trace

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

• last index of term 2 is 4
• return 5

6) Snapshot compaction (raft-snapshot-compact)

Contract

Given snapshotIndex, drop all log entries with index <= snapshotIndex.

Important note for this pack

snapshotTerm is part of realistic snapshot metadata but is not used by this problem's expected function.

Near-solution implementation

func CompactLog(logTerms []int, snapshotIndex int, snapshotTerm int) []int {
    if snapshotIndex <= 0 {
        return append([]int(nil), logTerms...)
    }
    if snapshotIndex >= len(logTerms) {
        return []int{}
    }
    return append([]int(nil), logTerms[snapshotIndex:]...)
}

Worked trace

log=[1,1,2,2,3], snapshotIndex=3 -> keep entries 4..5 -> [2,3].

Common mistakes

• Using snapshotIndex-1 as slice start (off by one).
• Returning original slice alias and failing mutation-safety tests.

7) Election timeout synthesis (raft-election-timeout)

This problem is a deterministic timeline generator.

Contract highlights

• Timer base starts at lastHeartbeat=0.
• Election deadlines are lastHeartbeat + k*timeout.
• Heartbeat at exact deadline suppresses election (heartbeat reset wins first).
• Emit only times <= end.

Interval mental model

For each effective heartbeat hb, process interval [last, hb):

• emit last+timeout, last+2*timeout, ... while < hb
• then set last = hb

After last heartbeat, process final interval [last, end] using <= end.

Near-solution implementation

func ElectionTimeouts(heartbeats []int, timeout int, end int) []int {
    out := make([]int, 0)
    if timeout <= 0 || end < 0 {
        return out
    }

    last := 0

    for _, hb := range heartbeats {
        if hb <= last {
            continue // duplicate/backward timestamps ignored
        }

        if hb > end {
            for t := last + timeout; t <= end; t += timeout {
                out = append(out, t)
            }
            return out
        }

        for t := last + timeout; t < hb; t += timeout {
            out = append(out, t)
        }
        last = hb
    }

    for t := last + timeout; t <= end; t += timeout {
        out = append(out, t)
    }
    return out
}

Worked traces

• heartbeats=[], timeout=7, end=20 -> [7,14]
• heartbeats=[5,40], timeout=10, end=50 -> [15,25,35,50]
• heartbeats=[10,20], timeout=10, end=25 -> []

Common mistakes

• Using <= hb in the pre-heartbeat loop (should be < hb).
• Not handling heartbeat beyond end correctly.
• Emitting events for timeout <= 0.

8) Joint consensus commit (raft-joint-consensus-commit)

Contract

Compute commit for old and new configs independently, then take minimum.

Per config:

• collect each member's match index (missing member -> 0)
• sort descending
• quorum index is indices[len(config)/2]

Final joint commit:

• min(oldCommit, newCommit)

Near-solution implementation

type Match struct {
    ID    int
    Index int
}

func JointCommitIndex(oldConfig []int, newConfig []int, matches []Match) int {
    matchMap := make(map[int]int, len(matches))
    for _, m := range matches {
        matchMap[m.ID] = m.Index
    }

    oldCommit := quorumCommit(oldConfig, matchMap)
    newCommit := quorumCommit(newConfig, matchMap)

    if oldCommit < newCommit {
        return oldCommit
    }
    return newCommit
}

func quorumCommit(config []int, matchMap map[int]int) int {
    if len(config) == 0 {
        return 0
    }

    indices := make([]int, 0, len(config))
    for _, id := range config {
        indices = append(indices, matchMap[id])
    }

    sort.Sort(sort.Reverse(sort.IntSlice(indices)))
    return indices[len(config)/2]
}

Worked trace

old=[1,2,3], new=[2,3,4] match: 1->5, 2->4, 3->6, 4->3

• old indices [6,5,4] -> quorum value 5
• new indices [6,4,3] -> quorum value 4
• joint commit min(5,4)=4

Common mistakes

• Taking max(oldCommit, newCommit) instead of min.
• Ignoring missing IDs as zero.

9) Milestone follower RPC handler (raft-milestone)

This combines vote and append behavior into one state transition function.

Milestone response contract

• Input RPC kinds: "vote" or "append".
• Normalize kind with lowercase + trim.
• If incoming term is higher, update CurrentTerm and reset VotedFor=-1.
• Dispatch to vote/append logic.
• On reject, state must remain unchanged except term bump from higher term.

Milestone architecture

Use small helpers exactly like earlier problems:

• isUpToDate(...)
• prevLogMatches(...)
• min(...)

Near-solution implementation sketch

func HandleRPC(state State, rpc RPC) (State, Response) {
    kind := strings.ToLower(strings.TrimSpace(rpc.Kind))
    resp := Response{Kind: kind, Term: state.CurrentTerm}

    rpcTerm := 0
    if kind == "vote" {
        rpcTerm = rpc.Vote.Term
    } else if kind == "append" {
        rpcTerm = rpc.Append.Term
    }

    if rpcTerm > state.CurrentTerm {
        state.CurrentTerm = rpcTerm
        state.VotedFor = -1
    }
    resp.Term = state.CurrentTerm

    switch kind {
    case "vote":
        // reject old term
        // reject if already voted different candidate
        // reject if candidate log not up-to-date
        // else grant and set VotedFor

    case "append":
        // reject old term
        // reject if prev-log mismatch
        // else truncate to PrevLogIndex and append new entries
        // advance commit index with min(LeaderCommit, len(LogTerms))

    default:
        // return unchanged response
    }

    return state, resp
}

Complete vote branch logic

if rpc.Vote.Term < state.CurrentTerm {
    resp.VoteGranted = false
    return state, resp
}
if state.VotedFor != -1 && state.VotedFor != rpc.Vote.CandidateID {
    resp.VoteGranted = false
    return state, resp
}

localLastIndex := len(state.LogTerms)
localLastTerm := 0
if localLastIndex > 0 {
    localLastTerm = state.LogTerms[localLastIndex-1]
}

if !isUpToDate(rpc.Vote.LastLogTerm, rpc.Vote.LastLogIndex, localLastTerm, localLastIndex) {
    resp.VoteGranted = false
    return state, resp
}

state.VotedFor = rpc.Vote.CandidateID
resp.VoteGranted = true
return state, resp

Complete append branch logic

if rpc.Append.Term < state.CurrentTerm {
    resp.AppendSuccess = false
    return state, resp
}
if !prevLogMatches(state.LogTerms, rpc.Append.PrevLogIndex, rpc.Append.PrevLogTerm) {
    resp.AppendSuccess = false
    return state, resp
}

newLog := append([]int{}, state.LogTerms[:rpc.Append.PrevLogIndex]...)
newLog = append(newLog, rpc.Append.Entries...)
state.LogTerms = newLog

if rpc.Append.LeaderCommit > state.CommitIndex {
    state.CommitIndex = min(rpc.Append.LeaderCommit, len(state.LogTerms))
}

resp.AppendSuccess = true
resp.MatchIndex = len(state.LogTerms)
return state, resp

Integration test mindset

Before coding, verify these transition patterns mentally:

1. Higher-term vote request resets VotedFor, then may grant.
2. Append with mismatched prev log rejects and preserves log.
3. Append with match truncates from PrevLogIndex+1 and appends entries.
4. Commit index never exceeds local log length.

End-to-end mini walkthrough

Start state:

• CurrentTerm=3, VotedFor=-1, LogTerms=[1,2,2], CommitIndex=2

Step A: vote request (term=4, candidate=9, last=(3,4))

• term bump to 4 and reset vote.
• candidate log is newer (3 > 2) -> grant.
• new state: CurrentTerm=4, VotedFor=9.

Step B: append (term=4, prev=(3,2), entries=[4,4], leaderCommit=4)

• prev matches.
• truncate after index 3, append [4,4] -> [1,2,2,4,4].
• commit becomes min(4,5)=4.

This is exactly how leader election, log replication, and commit movement compose in follower behavior.

Implementation checklist

• Keep all index math 1-based at API boundary.
• Convert to 0-based only at slice access points.
• Copy slices on reject/return paths when tests expect immutability.
• Guard all boundary conditions before indexing.
• Preserve monotonic term and safe commit movement.

What you will build

• Vote-grant predicate for RequestVote correctness.
• Prefix-match append logic.
• Full append conflict resolution + commit advancement.
• Majority-based current-term commit calculation.
• Conflict backtracking next-index optimization.
• Snapshot-driven log compaction.
• Deterministic election timeout timeline synthesis.
• Joint consensus commit computation.
• Unified follower RPC handler milestone.