Consensus: Raft

Implementation-first walkthrough for election, replication, and commit safety.

Learning outcomes

• Translate Raft rules into exact branch logic.
• Avoid off-by-one and stale-term bugs.
• Understand why each guard preserves safety.
• Compose helpers into a full follower RPC handler.

State and indexing conventions

• CurrentTerm: monotonic term.
• VotedFor: candidate ID or -1.
• LogTerms: term per log entry.
• CommitIndex: highest known committed index.
• External contracts are 1-based indices.
• Empty log -> LastLogIndex=0, LastLogTerm=0.

Invariants to hold at every step

1. Never decrease term.
2. At most one vote per term (except same candidate replay).
3. Never append without prev-log match.
4. In full append logic, truncate at first mismatching term only.
5. Leader commit candidate must be from currentTerm.
6. Joint config commit requires majority in both old and new configs.

Problem 1: Vote grant

Grant iff:

• candidateTerm >= currentTerm
• votedFor empty or same candidate
• candidate log is at least as up-to-date:
  • higher last term wins
  • same last term: higher/equal last index wins

if candidateTerm < currentTerm { return false }
if votedFor != -1 && votedFor != candidateID { return false }
if candidateLastTerm != localLastTerm {
    return candidateLastTerm > localLastTerm
}
return candidateLastIndex >= localLastIndex

Problem 2: AppendEntries (simple)

Accept only if prev pointer matches.

Reject conditions:

• prevLogIndex > len(log)
• prevLogIndex > 0 && log[prevLogIndex-1] != prevLogTerm

Accept action:

• keep prefix [1..prevLogIndex]
• append all entries

newLog := append([]int{}, log[:prevLogIndex]...)
newLog = append(newLog, entries...)

Problem 3: AppendEntries (full)

Follower pipeline:

1. Term gate.
2. Prev-log gate.
3. Conflict-aware merge.
4. Commit index update.

Conflict merge rule:

• matching term at position -> continue
• mismatching term at position -> truncate there, append remainder
• past end -> append remainder

Full append near-solution loop

idx := rpc.PrevLogIndex
for i := 0; i < len(rpc.Entries); i++ {
    pos := idx + 1 + i
    if pos <= len(state.LogTerms) {
        if state.LogTerms[pos-1] != rpc.Entries[i] {
            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
        }
    } 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:
state.CommitIndex = min(rpc.LeaderCommit, len(state.LogTerms))

Problem 4: Commit index

Goal: largest N where majority replicated and logTerms[N-1] == currentTerm.

Implementation trick:

• sort matchIndex descending
• majority candidate at indexes[len/2]
• cap by len(logTerms)
• scan down to first current-term index

candidate := sorted[len(sorted)/2]
for i := candidate; i >= 1; i-- {
    if logTerms[i-1] == currentTerm { return i }
}
return 0

Why current-term filter matters

Without filter, leader may commit an old-term entry only due to current quorum shape, which can break Raft safety during leadership changes.

Practical rule in this pack:

• Majority gives upper bound.
• Current-term check gives safe commit point.

Problem 5: Conflict backtracking

Follower conflict reply: (conflictTerm, conflictIndex).

Leader next index:

• conflictTerm == 0 -> conflictIndex
• if leader has conflictTerm -> lastIndex(conflictTerm)+1
• else -> conflictIndex

for i := len(leaderLog)-1; i >= 0; i-- {
    if leaderLog[i] == conflictTerm { return i + 2 }
}
return conflictIndex

Problem 6: Snapshot compaction

Drop all entries <= snapshotIndex.

if snapshotIndex <= 0 { return copy(logTerms) }
if snapshotIndex >= len(logTerms) { return []int{} }
return copy(logTerms[snapshotIndex:])

Notes:

• API is 1-based, slice start uses 0-based snapshotIndex.
• snapshotTerm exists in signature but not used in this exercise.

Problem 7: Election timeouts

Model intervals by effective heartbeats.

State:

• lastHeartbeat starts at 0.

Per heartbeat hb:

• emit t = last+timeout, ... while t < hb
• set last = hb

After all heartbeats:

• emit t <= end.

Boundary rule:

• heartbeat exactly at deadline suppresses election.

Election timeout near-solution

if timeout <= 0 || end < 0 { return []int{} }
last := 0
for _, hb := range heartbeats {
    if hb <= last { continue }
    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) }

Problem 8: Joint consensus commit

Compute per-config quorum commit, then take min.

Per config:

• collect each member's matchIndex (default 0 if missing)
• sort descending
• choose indices[len(config)/2]

Final:

joint = min(oldCommit, newCommit)

Problem 9: Milestone follower RPC handler

Normalize rpc.Kind, term-bump first, then dispatch.

Vote branch:

• reject old term
• reject conflicting prior vote
• check up-to-date log
• set VotedFor and grant

Append branch:

• reject old term
• reject prev mismatch
• truncate-to-prev and append entries
• CommitIndex = min(LeaderCommit, len(LogTerms))

Milestone skeleton

kind := strings.ToLower(strings.TrimSpace(rpc.Kind))
if rpcTerm > state.CurrentTerm {
    state.CurrentTerm = rpcTerm
    state.VotedFor = -1
}
switch kind {
case "vote":
    // vote logic
case "append":
    // append logic
default:
    // unchanged
}

Keep helper functions small and reusable:

• isUpToDate
• prevLogMatches
• min

End-to-end trace

Initial:

• term=3, votedFor=-1, log=[1,2,2], commit=2

Vote RPC (term=4, candidate=9, last=(3,4)):

• bump term, reset vote, grant vote.

Append RPC (term=4, prev=(3,2), entries=[4,4], leaderCommit=4):

• prev matches
• new log [1,2,2,4,4]
• commit moves to 4

This is the follower-side Raft control loop in practice.

Pitfall checklist before submission

• 1-based index at API, 0-based at slice access.
• Do not mutate log on reject paths.
• Do not over-commit beyond local log length.
• Enforce current-term rule in commit index problem.
• Handle heartbeat-at-deadline suppression correctly.

Build outcomes

• Vote correctness
• Append correctness (simple + full)
• Commit correctness
• Conflict recovery optimization
• Snapshot compaction
• Timer synthesis
• Joint consensus commit
• Unified follower RPC handling