Raft: Leader Election

What this implementation is

labs/raft is a complete Raft core in about 700 lines of Go (plus a 110-line simulated network): leader election, log replication, persistence, and ReadIndex. It runs over an abstract Transport, so the same code is exercised by an in-process simulated network in tests. The concepts — terms, roles, the replicated log — are in Raft Consensus; this page and Raft: Log Replication are the implementation, with the details that make or break it.

State

type Node struct {
    mu        sync.Mutex
    id        int
    peers     []int // all member ids, including id
    tr        Transport
    storage   Storage // Save(Update) must be durable before returning

    // Persistent state (saved before answering any RPC that changed it).
    term     uint64
    votedFor int     // -1 = none in this term
    log      []Entry // log[0] is a sentinel {Term: 0, Index: 0}

    // Volatile state.
    state            State // Follower, Candidate, Leader
    commitIndex      uint64
    lastApplied      uint64
    electionDeadline time.Time

    // Leader-only state, reinitialized on election.
    nextIndex  map[int]uint64
    matchIndex map[int]uint64
    // ...
}

The concurrency design is the simplest that is correct: one mutex per node, held while reading or changing state, and never held across an RPC. Each RPC is sent from its own goroutine; when the reply arrives, the goroutine re-takes the lock and must re-check that the world has not changed (same term, same role) before acting on it. That re-check is where most Raft bugs live.

Exactly three things are persistent — term, votedFor, and the log (plus the snapshot, see Raft in Production) — and they are written with n.save(Update{...}) before any reply that depends on them leaves the node. If a node voted for A in term 5, crashed, and forgot, it could vote for B in term 5 after restarting: two leaders in one term.

The RPCs

type RequestVoteArgs struct {
    Term         uint64
    CandidateID  int
    LastLogIndex uint64
    LastLogTerm  uint64
}

type AppendEntriesArgs struct {
    Term         uint64
    LeaderID     int
    PrevLogIndex uint64
    PrevLogTerm  uint64
    Entries      []Entry // empty = heartbeat
    LeaderCommit uint64
}

Every RPC and every reply carries a term. The universal rule: if you see a higher term, you are out of date — adopt the term, clear your vote, become a follower. A reply with a higher term deposes a leader instantly; a request with a lower term is rejected. The term is Raft's fencing token (Leases and Fencing).

Starting an election

func (n *Node) startElectionLocked() {
    n.state = Candidate
    n.term++
    n.votedFor = n.id
    n.save(Update{HardState: n.hardState()})
    n.resetElectionTimer()
    args := RequestVoteArgs{Term: n.term, CandidateID: n.id,
        LastLogIndex: n.lastIndex(), LastLogTerm: n.lastTerm()}
    votes := 1
    for _, p := range n.peers {
        if p == n.id {
            continue
        }
        go func() {
            reply, ok := n.tr.RequestVote(p, args)
            if !ok {
                return
            }
            n.mu.Lock()
            defer n.mu.Unlock()
            if reply.Term > n.term {
                n.becomeFollower(reply.Term)
                return
            }
            // Ignore stale replies: we may have moved on to another term or role.
            if n.state != Candidate || n.term != args.Term || !reply.VoteGranted {
                return
            }
            votes++
            if votes == n.majority() { // ==, not >=: become leader exactly once
                n.becomeLeader()
            }
        }()
    }
}

The check n.term != args.Term matters: replies to an election from term 7 can arrive after the node has started an election for term 8; counting them would elect a leader with votes from the wrong term.

Granting a vote

func (n *Node) HandleRequestVote(args RequestVoteArgs) RequestVoteReply {
    n.mu.Lock()
    defer n.mu.Unlock()
    if args.Term < n.term {
        return RequestVoteReply{Term: n.term}
    }
    if args.Term > n.term {
        n.becomeFollower(args.Term)
    }
    // Election restriction: only vote for a candidate whose log is at
    // least as up-to-date as ours, so a leader always holds every
    // committed entry.
    upToDate := args.LastLogTerm > n.lastTerm() ||
        (args.LastLogTerm == n.lastTerm() && args.LastLogIndex >= n.lastIndex())
    if (n.votedFor == -1 || n.votedFor == args.CandidateID) && upToDate {
        n.votedFor = args.CandidateID
        n.save(Update{HardState: n.hardState()}) // the vote must survive a crash
        n.resetElectionTimer()
        return RequestVoteReply{Term: n.term, VoteGranted: true}
    }
    return RequestVoteReply{Term: n.term}
}

The election restriction is what makes Raft safe. A committed entry is stored on a majority; a candidate needs votes from a majority; the two majorities overlap in at least one node; that node refuses to vote for a candidate whose log is behind its own. So every elected leader already holds every committed entry, and leaders never need to fetch missing entries from followers — data flows only from leader to followers.

"Up to date" compares the last entry's term first, then length. A longer log is not necessarily more up to date: a deposed leader can have many uncommitted entries from an old term.

Note also when the election timer is reset: when granting a vote and when receiving a valid AppendEntries from the current leader — not when rejecting a vote. Resetting on every RequestVote would let a node with a stale log, which can never win, keep everyone else from timing out.

Becoming leader

func (n *Node) becomeLeader() {
    n.state, n.leaderID = Leader, n.id
    n.nextIndex, n.matchIndex = map[int]uint64{}, map[int]uint64{}
    for _, p := range n.peers {
        n.nextIndex[p] = n.lastIndex() + 1 // optimistic: assume followers are caught up
        n.matchIndex[p] = 0                // pessimistic: nothing confirmed yet
    }
    n.appendLocal(nil) // no-op entry of the new term; see Log Replication
    n.broadcastLocked()
}

Timers: randomization only works if the timer can express it

If all followers time out at the same moment, they all become candidates, all vote for themselves, and nobody gets a majority — a split vote — and they time out together again. Raft avoids this by picking each election timeout randomly from a range.

The first version of the ticker in labs/raft checked the deadline by polling every 10 ms. With a narrow 300–310 ms range, the simulation never elected a leader: every node checked its deadline on the same 10 ms grid, so the 10 ms of randomization collapsed into a single tick, and all five nodes always started their elections in the same instant (in simulation the tickers are perfectly in phase; real clocks drift, which hides the bug without fixing it). The timer's resolution had erased the randomness. The ticker now sleeps until exactly the next deadline:

func (n *Node) ticker() {
    timer := time.NewTimer(0)
    defer timer.Stop()
    for {
        select {
        case <-n.done:
            return
        case <-timer.C:
        }
        n.mu.Lock()
        now := time.Now()
        var wait time.Duration
        if n.state == Leader {
            if now.Sub(n.lastBroadcast) >= n.cfg.HeartbeatInterval {
                n.broadcastLocked()
            }
            wait = n.cfg.HeartbeatInterval - time.Since(n.lastBroadcast)
        } else {
            if !now.Before(n.electionDeadline) {
                n.startElectionLocked()
            }
            wait = time.Until(n.electionDeadline)
        }
        n.mu.Unlock()
        timer.Reset(max(time.Millisecond, min(wait, n.cfg.HeartbeatInterval)))
    }
}

A second, related bug appeared while measuring: each node's random generator was seeded from time.Now(). Under synctest the fake clock starts at the same instant in every run, so every run produced the same timeouts and the "distribution" had no spread. Seeds now come from rand.Uint64().

Measured: election time vs. timeout range

5 nodes start simultaneously; time until the first leader, over 100 runs each (simulated network, 1–10 ms per message):

Election timeout range Median p95 Max Highest term needed
300–310 ms (10 ms spread) 612 ms 1,532 ms 3,367 ms 11
300–600 ms (300 ms spread) 352 ms 422 ms 495 ms 1

With a narrow range, a first-round split vote is the norm (median above two timeouts), and some runs needed 11 rounds. With a spread an order of magnitude larger than the network round trip, the first node to time out almost always collects its votes before anyone else wakes up. The rule of thumb from the Raft paper: broadcast time ≪ election timeout ≪ mean time between failures, with enough spread that one node usually wins outright.

Tests

All tests run under testing/synctest on the simulated network, so seconds of cluster time take milliseconds:

Test Checks
TestInitialElection One leader is elected; the term stays stable for 5 s without failures
TestReElection Disconnecting the leader elects a new one; the old one rejoins and steps down; with 2 of 3 nodes gone, no leader is elected
TestElectionTimeoutSpread The table above

checkOneLeader also fails the test if two nodes ever claim leadership of the same term — the property Election Safety.

Pre-vote and check-quorum

Two additions every production Raft has are now part of labs/raft and on by default; their effect is measured in Raft in Production:

  • Pre-vote: before incrementing its term, a node asks "would you vote for me?". Peers say yes only if its log is up to date and they have not heard from a leader recently. A node isolated by a partition then never inflates its term, and cannot force a healthy leader to step down when it reconnects.
  • Check-quorum: a leader that has not heard from a majority within an election timeout steps down. Without it, a leader isolated in a minority keeps believing it is leader indefinitely — which is what lets the unsafe local reads in Replicated Key-Value Store return stale data for as long as the partition lasts.

etcd's raft package implements both, plus leadership transfer and learners (non-voting members that catch up before joining).

Common pitfall

Forgetting to re-check state after an RPC returns. A candidate sends RequestVote in term 7, times out, starts term 8, and then the replies from term 7 arrive. If the reply handler only checks reply.VoteGranted and increments the vote count, term-7 votes are counted toward the term-8 election, and a node can become leader with votes no majority gave it in that term — two leaders can coexist. The same bug appears on the leader side when an AppendEntries reply from an earlier term updates matchIndex. Every handler that runs after releasing the lock must start with "am I still in the same term and role as when I sent this?"

Review questions

  1. Which three fields must be persisted, and what goes wrong if votedFor is not?
  2. Why does the election restriction guarantee that a new leader has every committed entry?
  3. Why is the election timer not reset when a vote is rejected?
  4. How did polling every 10 ms prevent a narrow timeout range from ever electing a leader in simulation?
  5. What do pre-vote and check-quorum each prevent?