15. Raft

Goal

Build the raft example from an empty file, one piece at a time.

New in this chapter

Nothing new: this chapter only puts what you know to use.

Steps

Nothing in this chapter is new. You know every form it needs; the work is to put them together in the right order. Raft is an algorithm by which a group of nodes agrees on one leader, even when nodes crash. The idea fits in one page:

A node is a follower, a candidate or a leader, and has a term, a counter that only grows.
A follower that hears nothing for a while becomes a candidate: it adds one to its term and asks the others for their vote.
A node votes for at most one candidate per term. A candidate with a majority of votes becomes the leader.
The leader sends heartbeats, so that nobody starts another election.
Seeing a higher term, anyone steps down.

We build it in seven steps, each adding one piece. Step 1 has the node: its role, its term, who it voted for, its peers, and the phrase that makes it a follower. Names that start in lower case, such as votes and lastHeard, are private to the package. The demo builds a cluster; nothing happens yet:

Step 1

# package main
use example.com/tutorial/raft
use std/net
use std/sim

define main
  sim.Seed 3
  net.Latency between 5ms and 15ms
  set nodes to (sim.Cluster of 5 running raft)
  raft.Meet nodes
  sim.StopAt 3s

# package raft
use std/lists
use std/sim

Node has
  set Role to "follower"
  set Term to 0
  set VotedFor to sim.Nobody
  set Peers to {}
  set votes to 0
  set lastHeard to 0s

define Meet [ns: list of Node]
  each n in ns
    set n.Peers to (lists.Without n from ns)

define [n: Node] BecomeFollower [t: number]
  set n.Term to t
  set n.Role to "follower"
  set n.VotedFor to sim.Nobody

Step 2 starts elections. Waiting is done with after and a random duration, so that the nodes do not all become candidates at the same instant and split the vote again and again. A node watches the clock: if it is not a leader and has heard nothing for 150ms, it starts an election and sends a RequestVote to every peer. Nobody answers yet, so every node keeps trying:

Step 2

# package raft
use std/lists
use std/net
use std/random
use std/sim
use std/time

RequestVote has
  set term to 0

Node has
  set Role to "follower"
  set Term to 0
  set VotedFor to sim.Nobody
  set Peers to {}
  set votes to 0
  set lastHeard to 0s

define Meet [ns: list of Node]
  each n in ns
    set n.Peers to (lists.Without n from ns)

define [n: Node] BecomeFollower [t: number]
  set n.Term to t
  set n.Role to "follower"
  set n.VotedFor to sim.Nobody

define [n: Node] StartElection
  set n.Role to "candidate"
  set n.Term to (n.Term plus 1)
  set n.VotedFor to n
  set n.votes to 1
  set n.lastHeard to time.Now
  each p in n.Peers
    net.Send (message RequestVote with term n.Term) from n to p

# A randomized timeout keeps candidates from colliding forever
define [n: Node] WatchElection
  after (random.TimeBetween 150ms and 300ms)
    if ((n.Role is not "leader") and ((time.Now minus n.lastHeard) at least 150ms))
      n.StartElection
    n.WatchElection

define [n: Node] start
  n.WatchElection

Step 3 counts votes. A node grants its vote when the candidate's term is its own and it has not voted for anyone else. It answers with a Vote that says whether it was granted, and a candidate that collects a majority of the cluster (Majority of is half and one) becomes the leader. Any message with a higher term makes the receiver step down first. There are leaders now, but they say nothing, so the followers time out and start new elections:

Step 3

# package raft
use std/lists
use std/math
use std/net
use std/random
use std/sim
use std/time

RequestVote has
  set term to 0

Vote has
  set term to 0
  set granted to false

Node has
  set Role to "follower"
  set Term to 0
  set VotedFor to sim.Nobody
  set Peers to {}
  set votes to 0
  set lastHeard to 0s

define Meet [ns: list of Node]
  each n in ns
    set n.Peers to (lists.Without n from ns)

define Majority of [n: number]
  result ((math.Floor (n divided by 2)) plus 1)

define [n: Node] BecomeFollower [t: number]
  set n.Term to t
  set n.Role to "follower"
  set n.VotedFor to sim.Nobody

define [n: Node] StartElection
  set n.Role to "candidate"
  set n.Term to (n.Term plus 1)
  set n.VotedFor to n
  set n.votes to 1
  set n.lastHeard to time.Now
  each p in n.Peers
    net.Send (message RequestVote with term n.Term) from n to p

# A randomized timeout keeps candidates from colliding forever
define [n: Node] WatchElection
  after (random.TimeBetween 150ms and 300ms)
    if ((n.Role is not "leader") and ((time.Now minus n.lastHeard) at least 150ms))
      n.StartElection
    n.WatchElection

define [n: Node] start
  n.WatchElection

when [n: Node] (net.Received RequestVote from candidate)
  if (RequestVote.term more than n.Term)
    n.BecomeFollower RequestVote.term
  set grant to ((RequestVote.term is n.Term) and ((n.VotedFor is sim.Nobody) or (n.VotedFor is candidate)))
  if grant
    set n.VotedFor to candidate
    set n.lastHeard to time.Now
  net.Send (message Vote with term n.Term, granted grant) from n to candidate

when [n: Node] (net.Received Vote from voter)
  if (Vote.term more than n.Term)
    n.BecomeFollower Vote.term
  else
    if (((n.Role is "candidate") and Vote.granted) and (Vote.term is n.Term))
      set n.votes to (n.votes plus 1)
      if (n.votes is (Majority of ((lists.Size n.Peers) plus 1)))
        set n.Role to "leader"

Step 4 adds the heartbeat. The leader sends one every 50ms, and a follower that hears one remembers when, so its election timer never runs out:

Step 4

# package raft
use std/lists
use std/math
use std/net
use std/random
use std/sim
use std/time

RequestVote has
  set term to 0

Vote has
  set term to 0
  set granted to false

Heartbeat has
  set term to 0

Node has
  set Role to "follower"
  set Term to 0
  set VotedFor to sim.Nobody
  set Peers to {}
  set votes to 0
  set lastHeard to 0s

define Meet [ns: list of Node]
  each n in ns
    set n.Peers to (lists.Without n from ns)

define Majority of [n: number]
  result ((math.Floor (n divided by 2)) plus 1)

define [n: Node] BecomeFollower [t: number]
  set n.Term to t
  set n.Role to "follower"
  set n.VotedFor to sim.Nobody

define [n: Node] StartElection
  set n.Role to "candidate"
  set n.Term to (n.Term plus 1)
  set n.VotedFor to n
  set n.votes to 1
  set n.lastHeard to time.Now
  each p in n.Peers
    net.Send (message RequestVote with term n.Term) from n to p

# A randomized timeout keeps candidates from colliding forever
define [n: Node] WatchElection
  after (random.TimeBetween 150ms and 300ms)
    if ((n.Role is not "leader") and ((time.Now minus n.lastHeard) at least 150ms))
      n.StartElection
    n.WatchElection

define [n: Node] start
  n.WatchElection
  time.Every 50ms
    if (n.Role is "leader")
      each p in n.Peers
        net.Send (message Heartbeat with term n.Term) from n to p

when [n: Node] (net.Received RequestVote from candidate)
  if (RequestVote.term more than n.Term)
    n.BecomeFollower RequestVote.term
  set grant to ((RequestVote.term is n.Term) and ((n.VotedFor is sim.Nobody) or (n.VotedFor is candidate)))
  if grant
    set n.VotedFor to candidate
    set n.lastHeard to time.Now
  net.Send (message Vote with term n.Term, granted grant) from n to candidate

when [n: Node] (net.Received Vote from voter)
  if (Vote.term more than n.Term)
    n.BecomeFollower Vote.term
  else
    if (((n.Role is "candidate") and Vote.granted) and (Vote.term is n.Term))
      set n.votes to (n.votes plus 1)
      if (n.votes is (Majority of ((lists.Size n.Peers) plus 1)))
        set n.Role to "leader"

when [n: Node] (net.Received Heartbeat from leader)
  if (Heartbeat.term at least n.Term)
    if (Heartbeat.term more than n.Term)
      n.BecomeFollower Heartbeat.term
    set n.Role to "follower"
    set n.lastHeard to time.Now

Now the rule that must always hold. Step 5 adds the invariant of chapter 11: never two leaders in the same term. It also makes the system announce a new leader with an event, Elected, for the look to catch, and a phrase Leaders that lists the running leaders. This is the whole raft.synod of the examples, byte for byte:

Step 5

# package raft
use std/lists
use std/math
use std/net
use std/random
use std/sim
use std/time

Elected has
  set Term to 0

RequestVote has
  set term to 0

Vote has
  set term to 0
  set granted to false

Heartbeat has
  set term to 0

Node has
  set Role to "follower"
  set Term to 0
  set VotedFor to sim.Nobody
  set Peers to {}
  set votes to 0
  set lastHeard to 0s

define Meet [ns: list of Node]
  each n in ns
    set n.Peers to (lists.Without n from ns)

define Majority of [n: number]
  result ((math.Floor (n divided by 2)) plus 1)

define Leaders
  set found to {}
  each n in (sim.NodesRunning raft)
    if ((n.Role is "leader") and (sim.IsUp n))
      set found to (lists.Append n to found)
  result found

define LeadersAgree
  set terms to {}
  each n in (sim.NodesRunning raft)
    if (n.Role is "leader")
      if (n.Term is in terms)
        result false
      set terms to (lists.Append n.Term to terms)
  result true

# Election safety: never two leaders in the same term
always LeadersAgree

define [n: Node] BecomeFollower [t: number]
  set n.Term to t
  set n.Role to "follower"
  set n.VotedFor to sim.Nobody

define [n: Node] StartElection
  set n.Role to "candidate"
  set n.Term to (n.Term plus 1)
  set n.VotedFor to n
  set n.votes to 1
  set n.lastHeard to time.Now
  each p in n.Peers
    net.Send (message RequestVote with term n.Term) from n to p

# A randomized timeout keeps candidates from colliding forever
define [n: Node] WatchElection
  after (random.TimeBetween 150ms and 300ms)
    if ((n.Role is not "leader") and ((time.Now minus n.lastHeard) at least 150ms))
      n.StartElection
    n.WatchElection

define [n: Node] start
  n.WatchElection
  time.Every 50ms
    if (n.Role is "leader")
      each p in n.Peers
        net.Send (message Heartbeat with term n.Term) from n to p

when [n: Node] (net.Received RequestVote from candidate)
  if (RequestVote.term more than n.Term)
    n.BecomeFollower RequestVote.term
  set grant to ((RequestVote.term is n.Term) and ((n.VotedFor is sim.Nobody) or (n.VotedFor is candidate)))
  if grant
    set n.VotedFor to candidate
    set n.lastHeard to time.Now
  net.Send (message Vote with term n.Term, granted grant) from n to candidate

when [n: Node] (net.Received Vote from voter)
  if (Vote.term more than n.Term)
    n.BecomeFollower Vote.term
  else
    if (((n.Role is "candidate") and Vote.granted) and (Vote.term is n.Term))
      set n.votes to (n.votes plus 1)
      if (n.votes is (Majority of ((lists.Size n.Peers) plus 1)))
        set n.Role to "leader"
        emit (message Elected with Term n.Term) by n

when [n: Node] (net.Received Heartbeat from leader)
  if (Heartbeat.term at least n.Term)
    if (Heartbeat.term more than n.Term)
      n.BecomeFollower Heartbeat.term
    set n.Role to "follower"
    set n.lastHeard to time.Now

Step 6 adds a look in a package of its own, raftlook, and imports it from the demo. It replaces the card of each node with one whose color follows its role, and pulses and glows the card of a new leader:

Step 6

# package main
use example.com/tutorial/raft
use example.com/tutorial/raftlook
use std/net
use std/sim

define main
  sim.Seed 3
  net.Latency between 5ms and 15ms
  set nodes to (sim.Cluster of 5 running raft)
  raft.Meet nodes
  sim.StopAt 3s

# package raftlook
use example.com/tutorial/raft
use std/look
use std/look/basic
use std/sim
use std/theme

define RoleColor [r: text]
  if (r is "leader")
    result theme.Accent
  if (r is "candidate")
    result theme.Warning
  result theme.Ink

# Replace the basic card with one whose fill follows the node's role
when (sim.Added [n: raft.Node])
  draw (look.Card for n) as card for n
    look.Fill card with (RoleColor n.raft.Role)

when (sim.Emitted raft.Elected by n)
  look.Pulse (card of n)
  look.Effect "glow" on (card of n)

The last step is the demo of the example. After two seconds it crashes the leader, asks the viewer to predict what the followers do, and restarts the old leader three seconds later, when it comes back as a follower:

Step 7

# package main
use example.com/tutorial/raft
use example.com/tutorial/raftlook
use std/lesson
use std/net
use std/sim

define main
  sim.Seed 3
  net.Latency between 5ms and 15ms
  set nodes to (sim.Cluster of 5 running raft)
  raft.Meet nodes
  after 2s
    set old to (item 0 of raft.Leaders)
    sim.Crash old
    lesson.Ask "The leader just crashed. What do the followers do now?" choosing {"Wait for the old leader to return", "Time out and start an election", "Ask a coordinator service to pick a new leader", "Stop accepting writes for good"}
    after 3s
      sim.Restart old
      lesson.Note "The old leader returns as a follower: it sees a higher term."
  sim.StopAt 8s

Compare it with the file raft/raft.synod in the examples repository: only the module path differs.

What to watch

At the start, five followers, then a candidate, then a leader in amber that sends dots to every other card. After the crash, the dots stop; one follower times out first, becomes a candidate (yellow), and wins a new term. The old leader returns as a follower: it sees a higher term and steps down.

Exercises

Change random.TimeBetween 150ms and 300ms to random.TimeBetween 150ms and 160ms. What happens to the elections?

Expected

Candidates collide more often, so more terms pass before somebody wins a majority. A safe system does not depend on luck, but a fast one does.

Make the cluster 3 nodes, and crash two.

Expected

No leader can be elected again: a majority of three is two, and only one node is left. The system stays safe, but cannot make progress.

Turn LeadersAgree into a rule that is false by design: replace n.Term is in terms with n.Term is not in terms.

Expected

sim.Broken fires as soon as there is a leader, which shows that the rule is checked after every step.