Understanding Raft Leader Election by Building From Scratch

Let’s say you are building distributed software that supports replication (such as a database). There will be multiple nodes running in a distributed environment for that same application. In order to support replication, all the data from one node needs to be copied to other nodes in the network as well. So you came up with an idea of a leader/follower-based system. But now there is a different problem. There are 5 nodes in a distributed system. How will you elect 1 node as leader? Raft is the solution for that.

Consensus Algorithms

Before diving into the Raft algorithm, we must understand what consensus algorithms are. A consensus algorithm is a protocol that lets multiple nodes agree on a value or sequence of state-machine decisions despite failures and unreliable communication. For example, a payment system may replicate important state across multiple nodes rather than relying on a single machine. The exact architecture varies by company, and a real payment system may use several coordination and storage mechanisms; this example is only meant to illustrate why replicas need coordination.

But if there is no coordination between all the databases, you might see inconsistency in your transaction history. What if a database shows 10 transactions and another shows only 7? Which will you trust? This can happen due to network partition, where one node keeps working and another node falls behind due to the partitioned network. Consensus helps replicas agree on an ordered sequence of decisions; it does not mean every node is physically identical at every instant.

Raft Consensus

Raft was developed by Diego Ongaro and John Ousterhout, with Ongaro’s PhD dissertation presenting the work. Raft was designed to make consensus easier to understand and implement. Paxos was highly influential, but Raft was introduced with a different presentation and decomposition intended to make the algorithm easier to reason about.

Note: In order to keep this post beginner-friendly, we are going to discuss only the leader election part of Raft.

In Raft there are 3 types of nodes.

1. Leader — Handles client requests and coordinates log replication.
2. Followers — Respond to the leader’s RPCs and replicate log entries.
3. Candidates — A follower can become a candidate when its election timeout expires and start an election.

Raft is commonly used to replicate a state machine across nodes. The leader coordinates log replication, and followers replicate the same ordered log so the cluster can agree on which commands are committed.

How Does Communication Work in Raft?

Before discussing the actual leader election system, we need to discuss how nodes in the Raft consensus algorithm communicate with each other. The Raft paper specifies the RPCs used by the algorithm, but it does not require a particular network transport. An implementation can carry those RPCs over gRPC, HTTP, raw TCP, or another transport. RPC is an abstraction for remote calls; it is not inherently more reliable or faster than the underlying transport.

Raft defines two main RPCs:

1. AppendEntries — Used by the leader to replicate log entries and send heartbeats to followers.
2. RequestVote — Used by candidates to request votes from other nodes.

Leader Election

To make the discussion concrete, let’s say there is already a leader in the Raft cluster. At regular intervals, the leader sends AppendEntries RPCs to followers. Followers will process this request and return a response to the leader. In case the system is idle and the leader does not get any requests from the client, it will simply send heartbeats to followers in the form of empty AppendEntries requests. These heartbeats are the way in which a leader tells followers that I’m still active.

But what if the leader dies? In that case, followers won’t receive any heartbeat from the leader. Every follower uses a randomized election timeout. The Raft paper gives 150–300 ms as an example range; these values are configuration choices rather than universal Raft constants.

When a follower’s election timeout expires without valid leader communication, it starts an election by becoming a candidate. Once a follower enters the candidate state, it will send a RequestVote request to other nodes in the cluster and ask for a vote. A candidate becomes leader after receiving votes from a majority of the servers in the cluster for the same term.

Election timeouts are randomized so that, in most cases, one server starts the election before the others. This reduces the chance of split votes. Randomized timeouts make simultaneous elections less likely, although split votes can still occur.

Complexities in Election

Although the Raft election system looks easy at first, it is not that easy. Let me ask you some questions. What will you do if there are more than 1 candidate in the election and nobody gets a majority? If 1 candidate won the election, how will you notify other candidates to step down as followers? How will you make sure that the follower can only give a vote to 1 candidate at a time? Let’s look at these problems.

Election Term

All the above-mentioned problems can be solved by something called an election term. It is just a number that works as a logical clock in the Raft system. When a server starts a new election, it increments its current term before requesting votes. In a given term, a server votes for at most one candidate, subject to Raft’s additional log-up-to-date rule.

Let’s say the initial term was 1. The leader continuously sent AppendEntries RPCs with term 1. But suddenly the leader node crashed. Now followers 1, 2, and 3 have timeouts of 240 ms, 170 ms, and 290 ms, respectively. Follower 2 notices the timeout, increments its term to 2, becomes a candidate, votes for itself, and sends RequestVote RPCs to followers 1 and 3.

Followers 1 and 3 are currently in term 1, as they have not noticed the death of the leader at this time. Followers 1 and 3 learn about the higher term and can update their terms and become followers. Whether they grant the vote also depends on whether they have already voted in that term and whether candidate 2’s log is sufficiently up to date. In this article’s simplified election-only implementation, the log check is intentionally omitted.

Can There Be Multiple Candidates?

Because election timeouts are randomized, two servers can still time out close together and become candidates. Network delays can then cause their RequestVote messages to cross. So another follower might notice that the leader is dead and start its own election because it has not received the RequestVote RPC from anyone else. For a practical example, let’s say follower 2 has a timeout of 170 ms, follower 3 has a timeout of 171 ms, and sending the RequestVote RPC over the network takes 10 ms. So follower 3 will also start an election because it is between the point where it noticed the leader is dead and follower 2’s RequestVote RPC is not received.

What If No Candidate Wins the Election?

We already know that there can be multiple candidates at the same time. This can split votes and cause a scenario where none of the candidates get a majority of votes; hence, none of the candidates will win the election. So what do we have to do to fix this problem? Well, we don’t need to do anything in that case. All candidates will eventually retry the election after randomized timeouts if nobody wins. Repeated split votes are possible in theory, but randomized timeouts make them unlikely and allow the cluster to retry until a candidate wins under normal conditions.

How Do Other Candidates Learn That a Leader Was Elected?

It’s simple. A node does not infer that another node became leader merely because it receives a higher-term RequestVote RPC. The important rule is that a node updates its current term when it sees a higher term in an RPC and steps down to follower. A candidate that wins then sends AppendEntries heartbeats, allowing other nodes to recognize the leader for that term.

Implementation

Scope note: This is a learning implementation of Raft leader election, not a complete Raft implementation. It intentionally omits log replication, log freshness checks in RequestVote, persistence, membership changes, and other production concerns.

Let’s implement this in Go & gRPC. In case you are not familiar with Go and gRPC, you need to learn them first in order to understand this code.

First we will focus on implementing the Raft election and then on the networking part.

raft.go

 1type State int
 2
 3const (
 4	Follower State = iota
 5	Candidate
 6	Leader
 7	Dead
 8)
 9
10type Raft struct {
11	mu            sync.Mutex
12	state         State
13	lastEventTime time.Time
14	votedFor      string
15	term          int64
16	server        *Server
17}
18
19func NewRaft() *Raft {
20	r := &Raft{
21		state:         Follower,
22		lastEventTime: time.Now(),
23		votedFor:      "-1",
24		term:          0,
25	}
26	return r
27}
28
29func generateTimeout() time.Duration {
30	randomTime := rand.Intn(150)
31	raftRandomTime := randomTime + 150
32	return time.Duration(raftRandomTime * int(time.Millisecond))
33}

Just a simple struct that has stuff required for Raft and a helper function to generate time between 150 milliseconds and 300 milliseconds. The server is a networking module we will discuss later.

 1func (r *Raft) startElectionLoop() {
 2	ticker := time.NewTicker(time.Millisecond * 10)
 3	defer ticker.Stop()
 4
 5	timeout := generateTimeout()
 6
 7	for {
 8		<-ticker.C
 9
10		r.mu.Lock()
11		state := r.state
12		elapsed := time.Since(r.lastEventTime)
13		r.mu.Unlock()
14
15		if state == Dead {
16			continue
17		}
18
19		if state != Candidate && state != Follower {
20			continue
21		}
22
23		if elapsed >= timeout {
24			log.Println("Starting Election")
25			r.startElection()
26			timeout = generateTimeout()
27		}
28	}
29}

Our election loop keeps checking whether a heartbeat has been received from the leader recently. Once there is no heartbeat after the generated timeout, we just start the election.

 1
 2func (r *Raft) startElection() {
 3	r.mu.Lock()
 4	r.state = Candidate
 5	r.term++
 6	r.votedFor = r.server.id
 7	savedTerm := r.term
 8	totalVotesReceived := 1
 9	r.lastEventTime = time.Now()
10	r.mu.Unlock()
11
12	for peerID, peerRPC := range r.server.peerRPCs {
13		go func(peerID string, peerRPC pb.RaftServiceClient) {
14			log.Println("Requesting vote from: " + peerID)
15
16			req := &pb.RequestVoteReq{
17				Term:        savedTerm,
18				CandidateID: r.server.id,
19			}
20
21			resp, err := peerRPC.RequestVote(context.Background(), req)
22			if err != nil {
23				log.Printf("vote RPC to %s failed: %v", peerID, err)
24				return
25			}
26
27			log.Printf(
28				"reply from %s granted=%v term=%d",
29				peerID,
30				resp.VoteGranted,
31				resp.Term,
32			)
33
34			r.mu.Lock()
35			defer r.mu.Unlock()
36
37			if r.state != Candidate {
38				if r.state == Leader {
39					log.Println("election already won")
40				} else {
41					log.Println("someone else became leader")
42				}
43				return
44			}
45
46			if resp.Term > savedTerm {
47				r.becameFollower(resp.Term)
48				return
49			}
50
51			if resp.Term == savedTerm {
52				if resp.VoteGranted {
53					log.Println("Vote granted by: " + peerID)
54
55					totalVotesReceived++
56					clusterSize := len(r.server.peerRPCs) + 1
57
58					if totalVotesReceived > clusterSize/2 && r.state == Candidate {
59						log.Println("Won Election")
60						r.becameLeader()
61					}
62				}
63			}
64
65		}(peerID, peerRPC)
66	}
67}

In the election, we send the RequestVote RPC to all other nodes in the cluster and wait for a response. Don’t worry about this PB; it is related to networking, and we will discuss this after the election part.

 1
 2func (r *Raft) becameFollower(term int64) {
 3	r.term = term
 4	r.state = Follower
 5	r.votedFor = "-1"
 6	r.lastEventTime = time.Now()
 7}
 8
 9func (r *Raft) becameLeader() {
10	r.state = Leader
11
12	go func() {
13		ticker := time.NewTicker(time.Millisecond * 50)
14		defer ticker.Stop()
15
16		for {
17			r.sendHeartBeats()
18			<-ticker.C
19
20			r.mu.Lock()
21			if r.state != Leader {
22				r.mu.Unlock()
23				return
24			}
25			r.mu.Unlock()
26		}
27	}()
28}
29
30func (r *Raft) sendHeartBeats() {
31
32	r.mu.Lock()
33	if r.state != Leader {
34		r.mu.Unlock()
35		return
36	}
37	savedTerm := r.term
38	r.mu.Unlock()
39
40	for _, peerRPC := range r.server.peerRPCs {
41		req := &pb.AppendEntriesRequest{
42			Term: savedTerm,
43		}
44
45		go func(peer pb.RaftServiceClient, term int64) {
46			resp, err := peer.AppendEntries(context.Background(), req)
47			if err == nil {
48				r.mu.Lock()
49				defer r.mu.Unlock()
50
51				if resp.Term > savedTerm {
52					r.becameFollower(resp.Term)
53				}
54			}
55		}(peerRPC, savedTerm)
56	}
57}

becameFollower() simply changes the state of the Raft to follower. becameLeader() changes the state of the Raft to leader and starts sending heartbeats.

 1func (r *Raft) HandleRequestVote(req *pb.RequestVoteReq) (*pb.RequestVoteResp, error) {
 2	r.mu.Lock()
 3	defer r.mu.Unlock()
 4
 5	resp := &pb.RequestVoteResp{}
 6
 7	if r.state == Dead {
 8		resp.Term = r.term
 9		resp.VoteGranted = false
10		return resp, nil
11	}
12
13	if req.Term > r.term {
14		r.becameFollower(req.Term)
15	}
16
17	if r.term == req.Term && (r.votedFor == "-1" || r.votedFor == req.CandidateID) {
18		resp.VoteGranted = true
19		r.votedFor = req.CandidateID
20		r.lastEventTime = time.Now()
21	} else {
22		resp.VoteGranted = false
23	}
24
25	resp.Term = r.term
26	return resp, nil
27}

The HandleRequestVote() function is invoked through networking by other nodes. When a candidate node wants to request a vote from other nodes, it invokes this function through gRPC. It simply does some checks and votes if the candidate is valid.

 1func (r *Raft) HandleAppendEntries(req *pb.AppendEntriesRequest) (*pb.AppendEntriesResponse, error) {
 2	r.mu.Lock()
 3	defer r.mu.Unlock()
 4
 5	r.lastEventTime = time.Now()
 6
 7	resp := &pb.AppendEntriesResponse{
 8		Success: false,
 9	}
10
11	if req.Term > r.term {
12		r.becameFollower(req.Term)
13	}
14
15	if req.Term == r.term {
16		if r.state != Follower {
17			r.becameFollower(req.Term)
18		}
19		resp.Success = true
20	}
21
22	resp.Term = r.term
23
24	return resp, nil
25}

HandleAppendEntries(): This function is currently used only for heartbeat purposes, as we are focused on the election system. In production-grade systems you will see commands and instructions being sent over this function.

raft.proto

 1syntax = "proto3";
 2
 3package raft;
 4
 5option go_package = "github.com/x-sushant-x/raft/proto/pb";
 6
 7message RequestVoteReq {
 8    int64 term = 1;
 9    string candidateID = 2;
10}
11
12message RequestVoteResp {
13    int64 term = 1;
14    bool voteGranted = 2;
15}
16
17message AppendEntriesRequest {
18    int64 term = 1;
19}
20
21message AppendEntriesResponse {
22    bool success = 1;
23    int64 term = 2;
24}
25
26
27service RaftService {
28    rpc RequestVote(RequestVoteReq) returns (RequestVoteResp);
29    rpc AppendEntries(AppendEntriesRequest) returns (AppendEntriesResponse);
30}

As we are using gRPC as a communication protocol, this file has all the contracts for gRPC. If you are not able to understand it, just read about gRPC once. You will also need to generate code for this contract, and here is the command for that.

1protoc \
2	--go_out=. --go_opt=module=github.com/x-sushant-x/raft \
3	--go-grpc_out=. --go-grpc_opt=module=github.com/x-sushant-x/raft \
4	proto/raft.proto

server.go

 1package main
 2
 3import (
 4	"context"
 5	"log"
 6	"net"
 7	"sync"
 8
 9	"github.com/x-sushant-x/raft/proto/pb"
10	"google.golang.org/grpc"
11	"google.golang.org/grpc/connectivity"
12	"google.golang.org/grpc/credentials/insecure"
13)
14
15type Server struct {
16	pb.UnimplementedRaftServiceServer
17
18	mu       sync.Mutex
19	id       string
20	host     string
21	port     string
22	cluster  map[string]string
23	peerRPCs map[string]pb.RaftServiceClient
24
25	raft *Raft
26}
27
28func NewServer(id, host, port string, cluster map[string]string) *Server {
29	return &Server{
30		id:       id,
31		host:     host,
32		port:     port,
33		cluster:  cluster,
34		peerRPCs: make(map[string]pb.RaftServiceClient),
35	}
36}
37
38func (s *Server) RequestVote(ctx context.Context, req *pb.RequestVoteReq) (*pb.RequestVoteResp, error) {
39	return s.raft.HandleRequestVote(req)
40}
41
42func (s *Server) AppendEntries(ctx context.Context, req *pb.AppendEntriesRequest) (*pb.AppendEntriesResponse, error) {
43	return s.raft.HandleAppendEntries(req)
44}
45
46func (s *Server) serve() {
47	ln, err := net.Listen("tcp", ":"+s.port)
48	if err != nil {
49		panic("unable to serve: " + err.Error())
50	}
51
52	grpcServer := grpc.NewServer()
53	pb.RegisterRaftServiceServer(grpcServer, s)
54
55	log.Println("Listening...")
56	log.Fatal(grpcServer.Serve(ln))
57}
58
59func (s *Server) connectToAllPeers() {
60	log.Printf("Node: %s trying to connect to all peers.\n", s.id)
61
62	for id, addr := range s.cluster {
63		if id == s.id {
64			continue
65		}
66
67		if err := s.connectToPeer(id, addr); err != nil {
68			log.Printf("Node: %s failed to connect to peer %s.\n", s.id, id)
69		}
70	}
71}
72
73func (s *Server) connectToPeer(id string, address string) error {
74	conn, err := grpc.NewClient(
75		address,
76		grpc.WithTransportCredentials(insecure.NewCredentials()),
77	)
78
79	if err != nil {
80		return err
81	}
82
83	conn.Connect()
84
85	for {
86		state := conn.GetState()
87
88		if state == connectivity.Ready {
89			break
90		}
91	}
92
93	s.mu.Lock()
94	defer s.mu.Unlock()
95	s.peerRPCs[id] = pb.NewRaftServiceClient(conn)
96
97	log.Printf("Connected to node %s\n", id)
98	return nil
99}

In server.go, we start a gRPC server and implementing the proto contract that we made. So when a request comes over gRPC, it will either land on the following functions:

1func (s *Server) RequestVote(ctx context.Context, req *pb.RequestVoteReq) (*pb.RequestVoteResp, error) {
2	return s.raft.HandleRequestVote(req)
3}
4
5func (s *Server) AppendEntries(ctx context.Context, req *pb.AppendEntriesRequest) (*pb.AppendEntriesResponse, error) {
6	return s.raft.HandleAppendEntries(req)
7}

They will then call the appropriate Raft function.

Our networking part is also done. Let’s write the main function and finish this.

main.go

 1package main
 2
 3import (
 4	"fmt"
 5	"log"
 6	"os"
 7	"strings"
 8	"time"
 9)
10
11func main() {
12	if len(os.Args) != 2 {
13		log.Fatal("Usage: go run . <node-id>")
14	}
15
16	var nodeID string
17	fmt.Sscanf(os.Args[1], "%s", &nodeID)
18
19	cluster := map[string]string{
20		"1": "localhost:5001",
21		"2": "localhost:5002",
22		"3": "localhost:5003",
23	}
24
25	addrParts := strings.Split(cluster[nodeID], ":")
26
27	server := NewServer(nodeID, addrParts[0], addrParts[1], cluster)
28
29	raft := NewRaft()
30	raft.server = server
31	server.raft = raft
32
33	go server.serve()
34	time.Sleep(time.Second * 2)
35
36	server.connectToAllPeers()
37
38	go raft.startElectionLoop()
39
40	select {}
41}

There will be 3 nodes running on port 5001, 5002, 5003. We are first starting the gRPC server, then connecting to other nodes in the cluster, and then starting the election loop. In order to run this open, 3 terminals run the following commands.

1go run . 1

1go run . 2

1go run . 3

Monitor the output in all 3 terminals, and you will notice that 1 node will become the leader. Try stopping that node and see what happens. Well, this was all in this post. I hope you found this informative.

Source Code for this can be found in this GitHub Repo.

If you think I can improve anything in this post, please write me a comment.

Before You Go

You can also subscribe to my Newsletter to get latest posts in your inbox. Also you can connect with me via LinkedIn or Email. Thanks and have a good day.