db-17 step 01 — Leader election

Goal

A cluster of nodes followers, started cold, must elect exactly one leader in a bounded number of ticks, and that leader must remain stable as long as it can deliver heartbeats. The election protocol must be byte-deterministic across Rust, Go, and C++.

Tasks

  1. Persistent state. Each RaftNode carries current_term: u64, voted_for: Option<u32>, and log: Vec<LogEntry>. The dump encodes voted_for=None as the signed integer -1 (i64 LE); Some(id) becomes id as i64.

  2. Election timer. reset_election_timer(t) sets election_deadline = t + 150 + splitmix64(seed ^ node_id ^ t) % 150. Heartbeat-due is t + 50.

  3. on_tick(t). Followers and candidates that hit election_deadline start a new election: bump current_term, vote for self, broadcast RequestVote to all peers, transition to Candidate. Leaders that hit heartbeat_due broadcast an empty AppendEntries (heartbeat).

  4. RequestVote handling. Grant a vote iff (a) term == current_term, (b) voted_for is None or equal to the candidate, and (c) the candidate's log is at least as up-to-date as ours (the standard last_log_term/last_log_index lex compare). Grant resets the election timer.

  5. RequestVoteReply handling. A candidate that collects a majority of granted replies in the same term transitions to Leader, initializes next_index[p] = log.len() and match_index[p] = 0 for every peer p, and immediately broadcasts AppendEntries (initial heartbeat).

  6. become_follower(term). Used whenever a node sees term > current_term (in any RPC). Sets current_term = term, clears voted_for, resets the election timer, transitions to Follower.

Acceptance

Inline unit tests in each language:

  • splitmix64_known_vectors — splitmix64(0) == 0xE220A8397B1DCDAF (the value Vigna's reference C produces).
  • election_timer_in_range — 1000 consecutive resets all land in [t+150, t+300).
  • request_vote_grants_first_only — vote for candidate A, then a RequestVote from B in the same term is denied.
  • become_leader_from_majority — 3-node cluster, two RequestVoteReply with granted=true transitions the candidate to Leader.
  • term_bump_demotes_leader — a Leader receiving any RPC with term > current_term becomes Follower and clears voted_for.

All five green in Rust, Go, and C++.

Discussion prompts

  • Why is voted_for persistent (in the canonical dump) but commit_index volatile (also dumped, but only because the dump is a debug oracle, not a recovery file)?
  • What goes wrong if you reset the election timer on send of RequestVote instead of on grant of someone else's vote? (Hint: split-vote loops.)
  • Why must "majority" be computed against nodes, not against nodes that have replied?