A Raft node must survive a crash at any point between three events that are normally treated as separate steps:
The solution is implemented and verified in ~/solution (all 6 tests pass, including -race -count=20). Here is the complete, self-contained markdown deliverable (also saved at ~/solution/SOLUTION.md):
A Raft node must survive a crash at any point between three events that are normally treated as separate steps:
C_old,new is committed,If the configuration is not reconstructed identically after restart, a node can count the wrong majority, grant a vote to a stale candidate, or accept a snapshot that rolls membership back. Any of these breaks quorum intersection: two disjoint majorities can exist at the same time, and two leaders can be elected in the same term.
The transition that must be supported is C_old -> C_old,new -> C_new (joint consensus). During C_old,new a value is committed only when a majority of C_old and a majority of C_new have accepted it. A snapshot taken in the middle of this transition must carry the joint configuration with it.
Constraints for the solution:
There are four independent defects that combine into the unsafe behavior:
Non-durable vote / non-durable term. If currentTerm and votedFor are acknowledged before they are persisted, a crash lets the node vote again in the same term. Two leaders in one term -> split brain. The fix is to persist before any externally visible response (vote grant, append ack, snapshot ack).
Configuration is not part of the snapshot record. A snapshot stores (lastIndex, lastTerm, data) but not the membership in effect at lastIndex. If the node restarts from such a snapshot, it recomputes the configuration from an empty truncated log and sees C_old (or nothing), losing the committed C_old,new. It then happily accepts a majority of C_old alone. The fix is to store the configuration in the same durable record as the snapshot and truncate the log only after that record is durable.
Snapshot install is not fenced. A restarting node or an old leader can deliver an InstallSnapshot whose (term, lastIndex) is behind what the node already committed. Installing it discards committed configuration state. The fix is a three-part fence: reject args.term < currentTerm, reject snapIndex <= localSnapIndex, and reject snapIndex < commitIndex.
Quorum is evaluated against a single set. If commit / vote counting uses only C_old (or only C_new) during a transition, the two majorities need not intersect. The fix is to make the active configuration the last configuration appearing in the log (committed or not, as Raft prescribes), and require majority(Old) && majority(New) whenever it is joint.
Note on ordering: Raft does not persist commitIndex; a restarted node is allowed to have a lower commitIndex and learns it again from the leader. That is safe precisely because any snapshot/configuration it does persist is at or below the real commit index (fences in defect 3).
Four invariants, enforced by code:
persist() is called before returning any RequestVoteResp, AppendResp, or InstallSnapshotResp.CreateSnapshot and stepInstallSnapshot compute the configuration at the snapshot index, write snapshot bytes + configuration + the truncated log in one durable record.term >= currentTerm, snapIndex > localSnapIndex, and snapIndex >= commitIndex.Configuration.HasQuorum requires a majority of Old and, when Joint, also a majority of New. The active configuration is derived by replaying EntryConfChange entries from the snapshot config forward, so it is reconstructed identically after any crash.Because the active configuration is a pure function of the durable snapshot configuration plus the durable log, a crash can never produce a node whose membership differs from what its log records.
Create a module and drop in the three files below.
go.modmodule solution
go 1.26
raft.go// Package raft implements the safety-critical core of Raft with joint
// consensus and snapshot install. It is deliberately deterministic: no
// goroutines, no clocks, and every transition is driven by an explicit
// message. This makes crash/restart and message reordering testable.
package raft
import "sort"
// ---------------------------------------------------------------------------
// Roles and message kinds
// ---------------------------------------------------------------------------
type State uint8
const (
StateFollower State = iota
StateCandidate
StateLeader
)
type MessageType uint8
const (
MsgRequestVote MessageType = iota
MsgRequestVoteResp
MsgAppend
MsgAppendResp
MsgInstallSnapshot
MsgInstallSnapshotResp
)
type EntryType uint8
const (
EntryNormal EntryType = iota
EntryConfChange
)
// ConfChange is the payload of a configuration change.
// If LeaveJoint is false the receiver enters a joint configuration whose
// outgoing set is the current voter set and whose incoming set is NewVoters.
// If LeaveJoint is true the receiver collapses the joint configuration to its
// incoming set.
type ConfChange struct {
NewVoters []uint64
LeaveJoint bool
}
// Configuration is a Raft membership configuration. A joint configuration
// (Joint == true) requires quorum from *both* Old and New. This is what makes
// quorum intersection hold across a restart in the middle of a membership
// change.
type Configuration struct {
Old map[uint64]struct{}
New map[uint64]struct{}
Joint bool
}
func NewSet(ids ...uint64) map[uint64]struct{} {
m := make(map[uint64]struct{}, len(ids))
for _, id := range ids {
m[id] = struct{}{}
}
return m
}
func cloneSet(m map[uint64]struct{}) map[uint64]struct{} {
out := make(map[uint64]struct{}, len(m))
for id := range m {
out[id] = struct{}{}
}
return out
}
// SimpleConf builds a non-joint configuration.
func SimpleConf(voters []uint64) Configuration {
return Configuration{Old: NewSet(voters...)}
}
// Apply folds a ConfChange into the configuration.
func (c Configuration) Apply(cc *ConfChange) Configuration {
if cc == nil {
return c
}
if cc.LeaveJoint {
return Configuration{Old: cloneSet(c.New)}
}
cur := c.Old
if c.Joint {
// Re-entering a joint config is illegal in real Raft; collapse to the
// incoming set so we never silently widen. Callers enforce the rule.
cur = c.New
}
return Configuration{
Old: cloneSet(cur),
New: NewSet(cc.NewVoters...),
Joint: true,
}
}
// Voters returns the union of all voter sets (everyone who may vote/replicate).
func (c Configuration) Voters() map[uint64]struct{} {
if !c.Joint {
return cloneSet(c.Old)
}
u := cloneSet(c.Old)
for id := range c.New {
u[id] = struct{}{}
}
return u
}
func majority(voters map[uint64]struct{}, acked map[uint64]bool) bool {
n := len(voters)
if n == 0 {
return false
}
cnt := 0
for id := range voters {
if acked[id] {
cnt++
}
}
return cnt > n/2
}
// HasQuorum is the single source of truth for commit and election safety.
// A joint configuration needs a majority of both sides.
func (c Configuration) HasQuorum(acked map[uint64]bool) bool {
if !c.Joint {
return majority(c.Old, acked)
}
return majority(c.Old, acked) && majority(c.New, acked)
}
func cloneConf(c Configuration) Configuration {
out := Configuration{Joint: c.Joint}
out.Old = cloneSet(c.Old)
if c.New != nil {
out.New = cloneSet(c.New)
}
return out
}
// ---------------------------------------------------------------------------
// Log entries, messages and durable state
// ---------------------------------------------------------------------------
type Entry struct {
Term uint64
Index uint64
Type EntryType
Data []byte
Conf *ConfChange
}
type Message struct {
Type MessageType
From, To uint64
Term uint64
LastLogIndex uint64 // RequestVote
LastLogTerm uint64
PrevLogIndex uint64 // AppendEntries
PrevLogTerm uint64
Entries []Entry
LeaderCommit uint64
SnapIndex uint64 // InstallSnapshot
SnapTerm uint64
SnapData []byte
SnapConf Configuration
Success bool // responses
VoteGranted bool
MatchIndex uint64
}
// Durable is the state that must survive a crash. A real implementation writes
// it atomically (term, vote, log prefix/suffix, snapshot and the configuration
// that accompanies the snapshot). Here one struct models that atomic record.
type Durable struct {
Term uint64
Vote uint64
Log []Entry
SnapIndex uint64
SnapTerm uint64
SnapData []byte
SnapConf Configuration
}
func (d *Durable) clone() *Durable {
if d == nil {
return nil
}
out := &Durable{Term: d.Term, Vote: d.Vote, SnapIndex: d.SnapIndex,
SnapTerm: d.SnapTerm, SnapConf: cloneConf(d.SnapConf)}
out.Log = cloneEntries(d.Log)
out.SnapData = append([]byte(nil), d.SnapData...)
return out
}
func cloneEntries(in []Entry) []Entry {
out := make([]Entry, len(in))
for i, e := range in {
out[i] = e
out[i].Data = append([]byte(nil), e.Data...)
if e.Conf != nil {
cc := *e.Conf
cc.NewVoters = append([]uint64(nil), e.Conf.NewVoters...)
out[i].Conf = &cc
}
}
return out
}
// ---------------------------------------------------------------------------
// Node
// ---------------------------------------------------------------------------
type Node struct {
ID uint64
term uint64
vote uint64 // 0 == none
state State
log []Entry // entries with Index > snapIndex, contiguous
snapIndex uint64
snapTerm uint64
snapData []byte
snapConf Configuration
commit uint64
applied uint64
votes map[uint64]bool
nextIndex map[uint64]uint64
matchIndex map[uint64]uint64
disk *Durable
}
// NewNode builds a node, optionally restoring from a durable record.
func NewNode(id uint64, d *Durable) *Node {
n := &Node{ID: id, state: StateFollower, snapConf: SimpleConf(nil)}
if d != nil {
n.term = d.Term
n.vote = d.Vote
n.log = cloneEntries(d.Log)
n.snapIndex = d.SnapIndex
n.snapTerm = d.SnapTerm
n.snapData = append([]byte(nil), d.SnapData...)
n.snapConf = cloneConf(d.SnapConf)
n.commit = d.SnapIndex
n.applied = d.SnapIndex
} else {
d = &Durable{SnapConf: SimpleConf(nil)}
}
n.disk = d
return n
}
// persist models an atomic durable write. It MUST be called before any
// externally visible action that other nodes can observe (granting a vote,
// acknowledging an append, installing a snapshot).
func (n *Node) persist() {
if n.disk == nil {
return
}
n.disk.Term = n.term
n.disk.Vote = n.vote
n.disk.Log = cloneEntries(n.log)
n.disk.SnapIndex = n.snapIndex
n.disk.SnapTerm = n.snapTerm
n.disk.SnapData = append([]byte(nil), n.snapData...)
n.disk.SnapConf = cloneConf(n.snapConf)
}
// Snapshot returns a copy of the node's current durable state (test hook).
func (n *Node) Snapshot() *Durable { return n.disk.clone() }
func (n *Node) Term() uint64 { return n.term }
func (n *Node) Commit() uint64 { return n.commit }
func (n *Node) Applied() uint64 { return n.applied }
func (n *Node) State() State { return n.state }
func (n *Node) SnapIndex() uint64 { return n.snapIndex }
// Config returns the configuration in effect. Per Raft the latest
// configuration *in the log*, committed or not, governs quorum. Recomputing it
// from the log makes the joint configuration crash-safe without extra state.
func (n *Node) Config() Configuration {
c := cloneConf(n.snapConf)
for _, e := range n.log {
if e.Type == EntryConfChange {
c = c.Apply(e.Conf)
}
}
return c
}
func (n *Node) configAt(idx uint64) Configuration {
c := cloneConf(n.snapConf)
for _, e := range n.log {
if e.Index > idx {
break
}
if e.Type == EntryConfChange {
c = c.Apply(e.Conf)
}
}
return c
}
// ---------------------------------------------------------------------------
// Log helpers
// ---------------------------------------------------------------------------
func (n *Node) lastIndex() uint64 {
if len(n.log) == 0 {
return n.snapIndex
}
return n.log[len(n.log)-1].Index
}
func (n *Node) lastIndexTerm() (uint64, uint64) {
if len(n.log) == 0 {
return n.snapIndex, n.snapTerm
}
e := n.log[len(n.log)-1]
return e.Index, e.Term
}
func (n *Node) termAt(idx uint64) uint64 {
if idx == 0 {
return 0
}
if idx == n.snapIndex {
return n.snapTerm
}
if idx < n.snapIndex {
return 0
}
for _, e := range n.log {
if e.Index == idx {
return e.Term
}
}
return 0
}
func (n *Node) truncateFrom(idx uint64) {
out := n.log[:0]
for _, e := range n.log {
if e.Index < idx {
out = append(out, e)
}
}
n.log = out
}
func discardUpTo(log []Entry, idx uint64) []Entry {
out := log[:0:0]
for _, e := range log {
if e.Index > idx {
out = append(out, e)
}
}
return out
}
func (n *Node) upToDate(idx, term uint64) bool {
li, lt := n.lastIndexTerm()
if term != lt {
return term > lt
}
return idx >= li
}
// ---------------------------------------------------------------------------
// Proposals (leader side)
// ---------------------------------------------------------------------------
func (n *Node) Propose(data []byte) (Entry, bool) {
if n.state != StateLeader {
return Entry{}, false
}
e := Entry{Term: n.term, Index: n.lastIndex() + 1, Type: EntryNormal, Data: data}
n.log = append(n.log, e)
n.matchIndex[n.ID] = e.Index
n.persist()
return e, true
}
func (n *Node) ProposeConf(cc *ConfChange) (Entry, bool) {
if n.state != StateLeader {
return Entry{}, false
}
// Rule: never enter a joint config while already in one. Leave first.
if n.Config().Joint && !cc.LeaveJoint {
return Entry{}, false
}
e := Entry{Term: n.term, Index: n.lastIndex() + 1, Type: EntryConfChange, Conf: cc}
n.log = append(n.log, e)
n.matchIndex[n.ID] = e.Index
n.persist()
return e, true
}
// ---------------------------------------------------------------------------
// Elections
// ---------------------------------------------------------------------------
func (n *Node) becomeFollower(term uint64) {
if term > n.term {
n.term = term
n.vote = 0
n.state = StateFollower
n.persist()
return
}
n.state = StateFollower
}
func (n *Node) becomeCandidate() {
n.state = StateCandidate
n.term++
n.vote = n.ID
n.votes = map[uint64]bool{n.ID: true}
n.persist()
}
func (n *Node) becomeLeader() {
n.state = StateLeader
n.nextIndex = map[uint64]uint64{}
n.matchIndex = map[uint64]uint64{}
li := n.lastIndex()
for id := range n.Config().Voters() {
n.nextIndex[id] = li + 1
n.matchIndex[id] = 0
}
n.matchIndex[n.ID] = li
}
// StartElection is called by the driver (no timers here). It returns the vote
// requests to deliver.
func (n *Node) StartElection() []Message {
n.becomeCandidate()
li, lt := n.lastIndexTerm()
var out []Message
for id := range n.Config().Voters() {
if id == n.ID {
continue
}
out = append(out, Message{Type: MsgRequestVote, From: n.ID, To: id,
Term: n.term, LastLogIndex: li, LastLogTerm: lt})
}
n.maybeWinElection()
return out
}
func (n *Node) maybeWinElection() {
if n.state != StateCandidate {
return
}
if n.Config().HasQuorum(n.votes) {
n.becomeLeader()
}
}
// ---------------------------------------------------------------------------
// Step: the whole node logic, fully deterministic
// ---------------------------------------------------------------------------
func (n *Node) Step(m Message) []Message {
switch m.Type {
case MsgRequestVote:
return n.stepRequestVote(m)
case MsgRequestVoteResp:
return n.stepRequestVoteResp(m)
case MsgAppend:
return n.stepAppend(m)
case MsgAppendResp:
return n.stepAppendResp(m)
case MsgInstallSnapshot:
return n.stepInstallSnapshot(m)
case MsgInstallSnapshotResp:
return n.stepInstallSnapshotResp(m)
}
return nil
}
func (n *Node) stepRequestVote(m Message) []Message {
resp := Message{Type: MsgRequestVoteResp, From: n.ID, To: m.From}
if m.Term < n.term {
resp.Term = n.term
return []Message{resp}
}
if m.Term > n.term {
n.becomeFollower(m.Term)
}
resp.Term = n.term
canVote := n.vote == 0 || n.vote == m.From
if canVote && n.upToDate(m.LastLogIndex, m.LastLogTerm) {
n.vote = m.From
n.persist() // durable before the grant is observable
resp.VoteGranted = true
}
return []Message{resp}
}
func (n *Node) stepRequestVoteResp(m Message) []Message {
if n.state != StateCandidate || m.Term != n.term {
return nil
}
if m.VoteGranted {
n.votes[m.From] = true
n.maybeWinElection()
}
return nil
}
func (n *Node) stepAppend(m Message) []Message {
resp := Message{Type: MsgAppendResp, From: n.ID, To: m.From}
if m.Term < n.term {
resp.Term = n.term
return []Message{resp}
}
n.becomeFollower(m.Term)
resp.Term = n.term
// Log matching property. A prev index covered by our snapshot is accepted
// because the snapshot term already encodes the matching history.
if m.PrevLogIndex > n.lastIndex() {
return []Message{resp}
}
if m.PrevLogIndex > n.snapIndex && n.termAt(m.PrevLogIndex) != m.PrevLogTerm {
return []Message{resp}
}
for i := range m.Entries {
e := m.Entries[i]
if e.Index <= n.snapIndex {
continue
}
if e.Index <= n.lastIndex() {
if n.termAt(e.Index) == e.Term {
continue
}
n.truncateFrom(e.Index) // conflict: truncate, then append the tail
}
n.log = append(n.log, cloneEntries(m.Entries[i:])...)
break
}
if m.LeaderCommit > n.commit {
last := n.lastIndex()
c := m.LeaderCommit
if c > last {
c = last
}
if c > n.commit {
n.commit = c
}
}
n.persist() // log, term and commit-observation are durable before ack
resp.Success = true
resp.MatchIndex = n.lastIndex()
return []Message{resp}
}
func (n *Node) stepAppendResp(m Message) []Message {
if n.state != StateLeader || m.Term != n.term {
return nil
}
if m.Success {
if m.MatchIndex > n.matchIndex[m.From] {
n.matchIndex[m.From] = m.MatchIndex
}
n.nextIndex[m.From] = n.matchIndex[m.From] + 1
n.maybeCommit()
} else if n.nextIndex[m.From] > 1 {
n.nextIndex[m.From]--
}
return nil
}
func (n *Node) stepInstallSnapshot(m Message) []Message {
resp := Message{Type: MsgInstallSnapshotResp, From: n.ID, To: m.From}
// 1. Term fence: an old leader can never mutate our state.
if m.Term < n.term {
resp.Term = n.term
return []Message{resp}
}
n.becomeFollower(m.Term)
resp.Term = n.term
// 2. Monotonicity fence: only strictly newer snapshots are useful.
if m.SnapIndex <= n.snapIndex {
return []Message{resp}
}
// 3. Rollback fence: a snapshot behind our commit index would discard
// committed configuration/log state. Reject it.
if m.SnapIndex < n.commit {
return []Message{resp}
}
// 4. Atomic install: snapshot bytes, snapshot configuration and the
// truncated log are written together. A crash cannot leave the node
// with the new snapshot but the old (or missing) configuration.
n.snapIndex = m.SnapIndex
n.snapTerm = m.SnapTerm
n.snapData = append([]byte(nil), m.SnapData...)
n.snapConf = cloneConf(m.SnapConf)
n.log = discardUpTo(n.log, m.SnapIndex)
if n.commit < m.SnapIndex {
n.commit = m.SnapIndex
}
if n.applied < m.SnapIndex {
n.applied = m.SnapIndex
}
n.persist()
resp.Success = true
resp.MatchIndex = n.snapIndex
return []Message{resp}
}
func (n *Node) stepInstallSnapshotResp(m Message) []Message {
if n.state != StateLeader || m.Term != n.term {
return nil
}
if m.Success {
if m.MatchIndex > n.matchIndex[m.From] {
n.matchIndex[m.From] = m.MatchIndex
}
n.nextIndex[m.From] = n.matchIndex[m.From] + 1
n.maybeCommit()
}
return nil
}
// maybeCommit advances commit to the highest entry that (a) is from our term
// and (b) has a quorum under the *current* configuration. In a joint config
// this demands a majority of both sides.
func (n *Node) maybeCommit() {
for idx := n.lastIndex(); idx > n.commit; idx-- {
if n.termAt(idx) != n.term {
break
}
acked := map[uint64]bool{n.ID: true}
for id, mi := range n.matchIndex {
if mi >= idx {
acked[id] = true
}
}
if n.Config().HasQuorum(acked) {
n.commit = idx
return
}
}
}
// MakeAppend builds the AppendEntries the leader would send to `to`.
func (n *Node) MakeAppend(to uint64) Message {
ni := n.nextIndex[to]
if ni == 0 {
ni = 1
}
prev := ni - 1
var entries []Entry
for _, e := range n.log {
if e.Index >= ni {
entries = append(entries, e)
}
}
return Message{Type: MsgAppend, From: n.ID, To: to, Term: n.term,
PrevLogIndex: prev, PrevLogTerm: n.termAt(prev), Entries: entries,
LeaderCommit: n.commit}
}
// AdvanceApplied moves applied forward (used by snapshot creation).
func (n *Node) AdvanceApplied(to uint64) {
if to > n.commit {
to = n.commit
}
if to > n.applied {
n.applied = to
}
}
// CreateSnapshot durably captures state through `applied` together with the
// configuration in effect at that index, then truncates the covered log. The
// configuration is stored in the same durable record, so a restart can never
// forget the joint configuration.
func (n *Node) CreateSnapshot(data []byte) {
idx := n.applied
n.snapIndex = idx
n.snapTerm = n.termAt(idx)
n.snapData = append([]byte(nil), data...)
n.snapConf = n.configAt(idx)
n.log = discardUpTo(n.log, idx)
n.persist()
}
// AppliedEntries returns the data of normal entries up to `applied` for tests.
func (n *Node) AppliedEntries() [][]byte {
var out [][]byte
for _, e := range n.log {
if e.Index <= n.applied && e.Type == EntryNormal {
out = append(out, e.Data)
}
}
return out
}
// VotersSorted returns a sorted slice for deterministic logging/tests.
func (n *Node) VotersSorted() []uint64 {
v := n.Config().Voters()
out := make([]uint64, 0, len(v))
for id := range v {
out = append(out, id)
}
sort.Slice(out, func(i, j int) bool { return out[i] < out[j] })
return out
}
raft_test.gopackage raft
import (
"fmt"
"reflect"
"testing"
)
func newTestNode(id uint64, voters []uint64) *Node {
return NewNode(id, &Durable{SnapConf: SimpleConf(voters)})
}
// ---------------------------------------------------------------------------
// 1. Stale leaders are rejected by term fencing.
// ---------------------------------------------------------------------------
func TestStaleLeaderAppendRejected(t *testing.T) {
n := newTestNode(2, []uint64{1, 2, 3})
n.term = 5
n.persist()
resp := n.Step(Message{Type: MsgAppend, From: 1, To: 2, Term: 3,
PrevLogIndex: 0, PrevLogTerm: 0,
Entries: []Entry{{Term: 3, Index: 1, Type: EntryNormal}}})
if len(resp) != 1 || resp[0].Success {
t.Fatalf("stale-term append was accepted: %+v", resp)
}
if n.Term() != 5 {
t.Fatalf("term changed to %d", n.Term())
}
if n.Commit() != 0 || n.lastIndex() != 0 {
t.Fatalf("stale append mutated log/commit: commit=%d last=%d", n.Commit(), n.lastIndex())
}
}
// ---------------------------------------------------------------------------
// 2. A vote is durable: after a crash the node cannot vote twice in a term.
// ---------------------------------------------------------------------------
func TestVoteIsDurableAcrossRestart(t *testing.T) {
d := &Durable{SnapConf: SimpleConf([]uint64{1, 2, 3})}
n := NewNode(1, d)
n.term = 5
n.persist()
resp := n.Step(Message{Type: MsgRequestVote, From: 2, To: 1, Term: 5})
if !resp[0].VoteGranted {
t.Fatalf("expected grant: %+v", resp[0])
}
// Duplicate delivery of the same request is idempotent.
resp = n.Step(Message{Type: MsgRequestVote, From: 2, To: 1, Term: 5})
if !resp[0].VoteGranted {
t.Fatalf("duplicate vote request should be idempotent")
}
// Simulated crash/restart from the durable record.
r := NewNode(1, d.clone())
resp = r.Step(Message{Type: MsgRequestVote, From: 3, To: 1, Term: 5})
if resp[0].VoteGranted {
t.Fatal("double vote in the same term after restart")
}
resp = r.Step(Message{Type: MsgRequestVote, From: 3, To: 1, Term: 6})
if !resp[0].VoteGranted {
t.Fatal("new term must reset votedFor and allow a grant")
}
}
// ---------------------------------------------------------------------------
// 3. Joint consensus cannot commit without a majority of BOTH sides.
// ---------------------------------------------------------------------------
func TestJointConsensusNeedsBothMajorities(t *testing.T) {
n := newTestNode(1, []uint64{1, 2, 3})
// Make node 1 a leader without a network round-trip.
n.becomeCandidate()
n.votes = map[uint64]bool{1: true, 2: true, 3: true}
n.maybeWinElection()
if n.State() != StateLeader {
t.Fatal("not leader")
}
if _, ok := n.ProposeConf(&ConfChange{NewVoters: []uint64{3, 4, 5}}); !ok {
t.Fatal("could not propose joint config")
}
if !n.Config().Joint {
t.Fatalf("expected joint config, got %+v", n.Config())
}
// Old majority {1,2} but no majority of new {3,4,5}: must NOT commit.
n.matchIndex = map[uint64]uint64{1: 1, 2: 1}
n.maybeCommit()
if n.Commit() != 0 {
t.Fatalf("committed joint entry without new-config majority: %d", n.Commit())
}
// Majority of both: old {1,3}, new {3,4}.
n.matchIndex = map[uint64]uint64{1: 1, 3: 1, 4: 1}
n.maybeCommit()
if n.Commit() != 1 {
t.Fatalf("joint entry should be committed, got %d", n.Commit())
}
}
// ---------------------------------------------------------------------------
// 4. Snapshot install is fenced by term, monotonicity and commit index, and
// it carries the configuration atomically.
// ---------------------------------------------------------------------------
func TestSnapshotFencesStaleLeader(t *testing.T) {
d := &Durable{Term: 7, SnapIndex: 50, SnapTerm: 6,
SnapConf: SimpleConf([]uint64{1, 2, 3})}
n := NewNode(1, d)
n.commit = 100
n.applied = 100
n.log = []Entry{{Term: 6, Index: 51}, {Term: 7, Index: 52}}
// (a) stale term
resp := n.Step(Message{Type: MsgInstallSnapshot, From: 2, To: 1, Term: 5,
SnapIndex: 200, SnapTerm: 5, SnapConf: SimpleConf([]uint64{9})})
if resp[0].Success || n.SnapIndex() != 50 {
t.Fatal("accepted snapshot from a stale leader")
}
// (b) would roll back committed state
resp = n.Step(Message{Type: MsgInstallSnapshot, From: 2, To: 1, Term: 8,
SnapIndex: 40, SnapTerm: 8, SnapConf: SimpleConf([]uint64{9})})
if resp[0].Success {
t.Fatal("accepted a snapshot behind commitIndex")
}
// (c) valid newer snapshot carrying a joint configuration
joint := Configuration{Old: NewSet(1, 2, 3), New: NewSet(3, 4, 5), Joint: true}
resp = n.Step(Message{Type: MsgInstallSnapshot, From: 2, To: 1, Term: 8,
SnapIndex: 120, SnapTerm: 8, SnapConf: joint})
if !resp[0].Success {
t.Fatalf("rejected a valid snapshot: %+v", resp[0])
}
if n.SnapIndex() != 120 || !n.Config().Joint {
t.Fatalf("snapshot config not adopted: snap=%d joint=%v", n.SnapIndex(), n.Config().Joint)
}
}
// ---------------------------------------------------------------------------
// 5. Crash between joint-consensus commitment and snapshot/truncation must
// never lose the joint configuration. Quorum intersection survives restart.
// ---------------------------------------------------------------------------
func TestCrashBetweenJointCommitAndSnapshotKeepsJointConfig(t *testing.T) {
d := &Durable{SnapConf: SimpleConf([]uint64{1, 2, 3})}
n := NewNode(1, d)
n.becomeCandidate()
n.votes = map[uint64]bool{1: true}
n.becomeLeader()
if _, ok := n.ProposeConf(&ConfChange{NewVoters: []uint64{3, 4, 5}}); !ok {
t.Fatal("propose failed")
}
n.commit = 1 // joint entry committed
n.persist()
// Crash A: after commit, before snapshot. Log must reproduce joint config.
crashA := NewNode(1, d.clone())
if !crashA.Config().Joint {
t.Fatal("plain restart lost the joint configuration")
}
// Crash B: after the snapshot (which includes the joint config) is durable.
n.applied = 1
n.CreateSnapshot([]byte("state"))
if !n.Config().Joint {
t.Fatal("snapshot dropped the joint configuration")
}
crashB := NewNode(1, d.clone())
if !crashB.Config().Joint {
t.Fatal("restart from snapshot lost the joint configuration")
}
// In both recovered nodes, neither side alone can form a quorum.
for name, node := range map[string]*Node{"A": crashA, "B": crashB} {
oldOnly := node.Config().HasQuorum(map[uint64]bool{1: true, 2: true})
newOnly := node.Config().HasQuorum(map[uint64]bool{3: true, 4: true})
cross := node.Config().HasQuorum(map[uint64]bool{1: true, 3: true, 4: true})
if oldOnly || newOnly {
t.Fatalf("crash %s: joint quorum satisfied by one side alone", name)
}
if !cross {
t.Fatalf("crash %s: valid cross quorum rejected", name)
}
}
}
// ---------------------------------------------------------------------------
// 6. Deterministic reordering + duplicate delivery converges to the same
// committed log. No clocks, no randomness.
// ---------------------------------------------------------------------------
func electLeader(nodes map[uint64]*Node, leader uint64) {
l := nodes[leader]
for _, m := range l.StartElection() {
for _, resp := range nodes[m.To].Step(m) {
l.Step(resp)
}
}
}
func runScenario(chaos bool) (map[uint64]uint64, map[uint64][][]byte) {
voters := []uint64{1, 2, 3}
nodes := map[uint64]*Node{}
for _, id := range voters {
nodes[id] = newTestNode(id, voters)
}
electLeader(nodes, 1)
if nodes[1].State() != StateLeader {
panic("election failed")
}
for i := 0; i < 4; i++ {
nodes[1].Propose([]byte(fmt.Sprintf("cmd-%d", i)))
}
for round := 0; round < 40; round++ {
var q []Message
for _, nd := range nodes {
if nd.State() != StateLeader {
continue
}
for id := range nd.Config().Voters() {
if id == nd.ID {
continue
}
q = append(q, nd.MakeAppend(id))
}
}
if chaos {
rev := make([]Message, 0, len(q)*2)
for i := len(q) - 1; i >= 0; i-- {
rev = append(rev, q[i], q[i]) // reorder + duplicate
}
q = rev
}
for _, m := range q {
tgt := nodes[m.To]
if tgt == nil {
continue
}
for _, r := range tgt.Step(m) {
nodes[r.To].Step(r)
}
}
}
commits := map[uint64]uint64{}
logs := map[uint64][][]byte{}
for id, nd := range nodes {
commits[id] = nd.Commit()
var data [][]byte
for _, e := range nd.log {
if e.Type == EntryNormal {
data = append(data, append([]byte(nil), e.Data...))
}
}
logs[id] = data
}
return commits, logs
}
func TestDeterministicReorderingAndDuplicates(t *testing.T) {
orderedCommits, orderedLogs := runScenario(false)
chaosCommits, chaosLogs := runScenario(true)
for id := uint64(1); id <= 3; id++ {
if orderedCommits[id] != chaosCommits[id] {
t.Fatalf("node %d commit differs: ordered=%d chaos=%d",
id, orderedCommits[id], chaosCommits[id])
}
if !reflect.DeepEqual(orderedLogs[id], chaosLogs[id]) {
t.Fatalf("node %d log differs:\n ordered=%v\n chaos=%v",
id, orderedLogs[id], chaosLogs[id])
}
want := uint64(4)
if chaosCommits[id] != want {
t.Fatalf("node %d did not converge: commit=%d want=%d", id, chaosCommits[id], want)
}
}
}
Run everything with the race detector and repeated iterations (determinism):
cd solution
go vet ./...
gofmt -l . # must print nothing
go test -race -count=20 ./...
Observed output:
$ go test ./... -v
=== RUN TestStaleLeaderAppendRejected
--- PASS: TestStaleLeaderAppendRejected (0.00s)
=== RUN TestVoteIsDurableAcrossRestart
--- PASS: TestVoteIsDurableAcrossRestart (0.00s)
=== RUN TestJointConsensusNeedsBothMajorities
--- PASS: TestJointConsensusNeedsBothMajorities (0.00s)
=== RUN TestSnapshotFencesStaleLeader
--- PASS: TestSnapshotFencesStaleLeader (0.00s)
=== RUN TestCrashBetweenJointCommitAndSnapshotKeepsJointConfig
--- PASS: TestCrashBetweenJointCommitAndSnapshotKeepsJointConfig (0.00s)
=== RUN TestDeterministicReorderingAndDuplicates
--- PASS: TestDeterministicReorderingAndDuplicates (0.00s)
PASS
ok solution 0.002s
$ go test -race -count=20 ./...
ok solution 1.034s
What each test proves:
| Test | Property verified |
|---|---|
TestStaleLeaderAppendRejected |
Term fencing: an old-term AppendEntries cannot mutate term, log or commit. |
TestVoteIsDurableAcrossRestart |
I1: after a restart the node rejects a different candidate in the same term (no double vote). Duplicate requests are idempotent. |
TestJointConsensusNeedsBothMajorities |
I4: {1,2} (old only) cannot commit; {1,3,4} (both) can. |
TestSnapshotFencesStaleLeader |
I3: stale-term, monotonicity and rollback-behind-commit snapshots are all rejected; a valid snapshot adopts its embedded joint config. |
TestCrashBetweenJointCommitAndSnapshotKeepsJointConfig |
I2: restart from the log and from the snapshot both yield the joint config, and neither C_old nor C_new alone forms a quorum. |
TestDeterministicReorderingAndDuplicates |
The full 3-node replication run produces byte-identical committed logs under FIFO delivery and under reversed + duplicated delivery. |
conf state field that can desync from the log, so a crash cannot produce a torn membership view.Configuration.HasQuorum and term comparison, so reordering/duplication only changes when a message is processed, never whether it is safe.time.Now(), no goroutines and no randomness appear in the package, which is what makes the tests reproduce exactly.# Evidence - Problem class: go-raft-joint-consensus-snapshot-restore-fencing-20261012 - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-12T10:08:11.296Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a Raft membership transition and snapshot restore path that remains safe when a node crashes between joint-consensus commitment, snapshot installation, and log truncation. The implementation must reject stale leaders, preserve quorum intersection across restart, and provide deterministic tests that explore message reordering and duplicate delivery without assuming synchronized clocks.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-raft-joint-consensus-snapshot-restore-fencing-20261012", "provider": "openrouter", "solved_at": "2026-10-12T10:08:11.299Z", "version": "1.26"}