Leader Election and Randomised Timeouts

How an election runs

A follower expects regular heartbeats. If its election timeout expires without hearing from a valid leader, it increments its term, becomes a candidate, votes for itself and sends RequestVote to every other server. Each server grants at most one vote per term, first come first served, and only if the candidate's log is at least as up-to-date as its own: compare the last entry's term first, and only if equal compare the last index. One of three things happens. The candidate wins a majority and becomes leader, then immediately sends heartbeats to stop new elections. Or it receives an AppendEntries from a leader with an equal or higher term and steps down. Or nobody wins (a split vote), the timeout fires again and a new term begins. Raft makes split votes rare by picking each timeout randomly from a range (the paper uses 150-300 ms), so usually one server times out well ahead of the others.

Granting votes

Candidate B has a longer log but an older last term, so it loses. C is exactly as up-to-date and gets the vote. D is more up-to-date but this follower already voted for C in term 4.

def grant_vote(me, req):
    """Raft RequestVote receiver rules (simplified)."""
    if req["term"] < me["term"]:
        return False
    if req["term"] > me["term"]:
        me["term"], me["voted_for"] = req["term"], None
    up_to_date = (req["last_log_term"], req["last_log_index"]) >= (
        me["last_log_term"], me["last_log_index"])
    if me["voted_for"] in (None, req["candidate"]) and up_to_date:
        me["voted_for"] = req["candidate"]
        return True
    return False

follower = {"term": 3, "voted_for": None, "last_log_term": 3, "last_log_index": 10}
print(grant_vote(follower, {"term": 4, "candidate": "B", "last_log_term": 2, "last_log_index": 50}))
print(grant_vote(follower, {"term": 4, "candidate": "C", "last_log_term": 3, "last_log_index": 10}))
print(grant_vote(follower, {"term": 4, "candidate": "D", "last_log_term": 3, "last_log_index": 12}))

Output:

False
True
False

Randomised timeouts spread candidates apart

With a seeded random generator, each round has one node timing out first with a margin of several milliseconds, usually enough to collect votes before anyone else starts.

import random

random.seed(7)
nodes = ["n1", "n2", "n3", "n4", "n5"]
for rnd in range(1, 4):
    timeouts = {n: random.randint(150, 300) for n in nodes}   # milliseconds
    first = min(timeouts, key=timeouts.get)
    gap = sorted(timeouts.values())[1] - timeouts[first]
    print(f"round {rnd}: {first} times out first at {timeouts[first]} ms, "
          f"next node {gap} ms later")

Output:

round 1: n4 times out first at 162 ms, next node 6 ms later
round 2: n5 times out first at 164 ms, next node 10 ms later
round 3: n3 times out first at 159 ms, next node 13 ms later

Who speaks first in a silent meeting

When the chair leaves a meeting, if everyone waits exactly five seconds and then speaks, they all talk over each other. If each person waits a random three to six seconds, one usually starts first and the others listen.

Quick check: Candidate log ends at (term 4, index 9). Voter log ends at (term 5, index 3). Will the voter grant its vote, assuming it has not voted this term?

• No, the voter's last entry has a higher term, so it is more up-to-date
• Yes, the candidate's log is longer
• Yes, votes are granted to the first candidate regardless of logs
• No, the candidate's index is not equal to the voter's