db-19 step 01 — Epoch, zxid, and Fast Leader Election

Goal

Build the persistent state every ZAB node carries and the election protocol that picks the next leader when no one is currently broadcasting. Election must converge in bounded ticks for any quorum-available network, and the chosen leader must always be the node with the highest committed zxid in the surviving quorum.

Tasks

  1. ZxId { epoch: u32, counter: u32 } with lexicographic ordering (epoch first, then counter). Provide a ZxId::ZERO constant. Every zxid comparison in the rest of the protocol uses this ordering — never compare the u64 representations directly, because the lab keeps them as a struct for clarity.

  2. Persistent node state. A ZabNode carries:

    • id: u32, n_nodes: u32, quorum = n_nodes/2 + 1.
    • role: Role (Looking / Following / Leading).
    • current_epoch: u32 — the epoch of the leader we last followed. Bumped on NewLeader.
    • accepted_epoch: u32 — the epoch we promised on NewEpoch. Always >= current_epoch.
    • history: Vec<Txn> — committed and uncommitted txns in zxid order.
    • last_committed: ZxId — high-water mark; entries <= this have been applied.

    These are the four values that would survive a crash in a real implementation. Everything else (vote tables, ack tables) is transient and rebuilt on the next election.

  3. Rpc::LookForLeader / Vote. A Looking node broadcasts its current vote each tick. On receiving a peer's vote, update via update_vote(peer.last_zxid, peer.id):

    • Adopt peer as our vote target if (peer.last_zxid, peer.id) > (current_vote.last_zxid, current_vote.id).
    • Record the peer's choice in vote_view[voter_id] = leader_id.

  4. Quorum detection. Walk vote_view and count entries whose value equals each candidate id. The first candidate (in id order) whose count >= quorum becomes the elected leader. If that leader is us, transition to Leading; otherwise transition to Following with leader_id = Some(...).

  5. Election timeout. Track election_deadline per node. If now > election_deadline and we're still Looking, reset the vote table and broadcast a fresh LookForLeader from our current (last_zxid, id). Reseed the deadline with ELECTION_TIMEOUT_MIN + splitmix64(seed) % ELECTION_TIMEOUT_SPAN.

Acceptance

Inline unit tests in each language. Names below are the Rust form; Go uses TestZxIdOrdering style, C++ uses test_zxid_ordering:

  • zxid_ordering_is_lexicographic — ZxId{0,9} < ZxId{1,0}, ZxId{1,0} < ZxId{1,1}, ZERO < ZxId{0,1}. Locks the comparator.
  • vote_adopts_higher_last_zxid — node 0 with last_zxid=(1,5) votes for itself; receives a vote from node 1 with (2,0); adopts node 1. Then receives from node 2 with (2,0) — does not re-adopt (tie on zxid, lower id loses).
  • quorum_of_votes_elects_highest — in a 3-node cluster all voting for node 2, node 2 transitions to Leading after the second matching Vote arrives.
  • election_does_not_decide_in_minority — partition isolates node 0 from {1,2}; node 0 must never leave Looking regardless of how many ticks elapse.

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