โ Final Challenge
โบ A Deterministic Cluster
100 ptsTime to assemble the machine. You get a three-node in-memory cluster where time is ticks and the network is a queue, and you implement the entire Raft node logic โ election, log replication, and commitment โ as two pure functions:
Tick(n *Node) []Messageโ one clock tick (lesson 5).Step(n *Node, m Message) []Messageโ apply one incoming message, return the replies (lessons 1โ4).
The Cluster harness is already written for you โ read it, leave it alone. It
ticks nodes in ID order, queues whatever they emit, and Deliver/DeliverAll
pump the queue FIFO, dropping messages that cross a partition (Isolate/
Heal). Propose appends a client command to a node's log stamped with that
node's current term. The tests stage everything deterministically: election
timeouts are [4, 6, 8] ticks for nodes 0, 1, 2, heartbeats every 2 ticks โ so
node 0 always wins the first election, and node 1 takes over when node 0 is
isolated.
Implement to this spec (Figure 2, restated for our tick model):
Tick โ as in lesson 5, with one upgrade: a leader's broadcast is a full
MsgAppendRequest per peer, in Peers order, carrying
Entries = Log[NextIndex[peer]-1:] (copy the slice), PrevLogIndex = NextIndex[peer]-1 with the matching PrevLogTerm, and
LeaderCommit = CommitIndex. When there is nothing new for a peer this is
naturally an empty heartbeat.
Step โ for every message: if m.Term > n.CurrentTerm, adopt the term,
become Follower, reset VotedFor to -1 and VotesGranted to 0, then keep
processing. Then by type:
MsgVoteRequest: the lesson-2 receiver rules. Always reply with aMsgVoteReplycarrying yourCurrentTerm; on granting, also resetElectionElapsedto 0.MsgVoteReply: only candidates count them, only ifGrantedandm.Term == CurrentTerm. On reaching a majority oflen(Peers)+1, become leader: for every peer setNextIndex[peer] = len(Log)+1andMatchIndex[peer] = 0, resetHeartbeatElapsedto 0, and immediately return a first round of heartbeats (same form as a leader tick) to assert authority.MsgAppendRequest: the lesson-3 receiver rules. Any valid request (term not stale) makes you aFollowerand resetsElectionElapsed. Reply with aMsgAppendReplycarrying yourCurrentTerm,Success, and โ when successful โMatchIndex = m.PrevLogIndex + len(m.Entries).MsgAppendReply: leaders only, and only form.Term == CurrentTerm. OnSuccess: raiseMatchIndex[m.From]andNextIndex[m.From](tom.MatchIndexandm.MatchIndex+1; never lower them), then advanceCommitIndexwith the lesson-4 rule โ largestN > CommitIndexwithLog[N-1].Term == CurrentTermstored on a majority, counting yourself. On failure: decrementNextIndex[m.From](not below 1); the retry rides the next heartbeat tick.
Every reply's From/To must be set (From = n.ID, To = m.From). If a
message needs no reply, return nothing for it.
The tests walk the cluster through the full Raft story: nothing happens before the first timeout; node 0 is elected in term 1; a proposed command replicates and commits on a majority, with followers learning the commit index one heartbeat later; node 0 is partitioned away, node 1 wins term 2 with node 2's vote while the stale leader keeps ruling its network of one; and after the partition heals, the old leader sees term 2, steps down, and converges on the new leader's log.
Log in to submit a solution and earn points.