Free link

The Raft consensus algorithm is a distributed consensus protocol, designed to manage a replicated log in a network of computers or servers. Raft was created by Diego Ongaro and John Ousterhout in 2013 as an easier-to-understand alternative to the Paxos algorithm, which was notoriously challenging to implement. Raft’s main goal is to achieve consensus among distributed nodes, ensuring they all agree on a single state, even in the presence of failures.

Put it in simple words, Raft is a way for a group of computers (or “nodes”) to agree on some information and keep it the same across all of them, even if some of the computers fail or get disconnected. This is useful in distributed systems where you need multiple copies of data, but you want those copies to always match.

Key Concepts in Raft

Raft breaks down the consensus problem into three main components:

  1. Leader Election: Ensures that only one server is the “leader” at any given time, which will be responsible for handling client requests and managing log replication.
  2. Log Replication: The leader receives requests from clients, appends them to its own log, and then replicates these entries to other servers (called followers). This keeps all logs consistent.
  3. Safety: Ensures that even if nodes fail or messages are delayed, the cluster remains in a consistent state.

The Three Roles

In Raft, computers have three possible roles:

  1. Leader: This computer is in charge and tells others what to do.
  2. Follower: Follower computers wait for instructions from the leader.
  3. Candidate: If a leader stops talking, a follower can try to become the new leader. When it does this, it’s called a candidate.

Let’s consider a set of 3 nodes,

Step-by-Step of Raft:

1. Leader Election:

  • Every computer starts as a follower.
  • If a follower doesn’t hear from a leader for a little random while, it transitions to a candidate and it says, “Hey, I’ll be the leader!” and asks others to vote for it by sending RequestVote RPCs to other nodes.
  • Each node votes for the first candidate it receives a request from in a given term.
  • If it gets enough votes, it becomes the leader.
  • As the leader, it’ll regularly send out “I’m alive” messages so no one else tries to take over.
  • Terms are like “rounds” in Raft, and each time an election happens, the term increases by one. Each node keeps track of the term, and a vote request is only granted if the request comes from the highest term seen by the node.

The followers expect regular heartbeat messages from the leader to confirm it’s active. If followers stop receiving these heartbeats within a certain timeout period, they suspect the leader has failed.

When a follower detects the leader’s failure, it waits a random amount of time (to avoid multiple nodes acting at once) and then transitions to a candidate. The candidate increases the term by 1 and begins a new election for this new term.

2. Log Replication

  • When the leader gets a task (like a client asking to store data), it writes it down in its log (like a checklist of tasks).
  • Then, the leader tells all the followers to write the same thing in their logs via AppendEntries RPCs.
  • Once a majority of computers have written down this task, the leader marks it as “done,” meaning everyone agrees.
  • The leader then notifies followers, allowing them to apply the log entry to their states. Kind of like committing a transaction.

3. Ensuring Safety

Raft uses several mechanisms to ensure consistency and safety:

  • Election Restriction: Only candidates with up-to-date logs (matching or longer than a majority) can win an election. This prevents split-brain scenarios.
  • Commit Index: This index indicates the highest log entry known to be committed, ensuring consistency across nodes.
  • Leader Completeness Property: A leader is guaranteed to have the most up-to-date log, preventing outdated data from being applied.
  • Log Matching Property: If two logs contain a particular entry at a given index, the preceding entries are identical.

Handling Failures

Leader Crashes:

If the leader crashes, one of the followers will eventually notice, step up, and ask others to vote it as the new leader. The new leader will check the logs of the followers and make sure everyone has the same list of tasks.

Network Partitions:

Sometimes, due to network issues, the group of computers might get divided into two smaller groups that can’t talk to each other — this is called a network partition.

Only the group that has more than half of the nodes can continue to work normally and elect a new leader. The group with fewer nodes won’t elect a new leader because they know they aren’t in the majority, so they wait until they can reconnect with the full group.

This approach keeps things safe because:

  • It prevents each split group from choosing their own leaders, which could lead to conflicting decisions.
  • Only one group can control the log and make changes, which keeps everything consistent.

Node Recovery:

When this crashed node comes back online:

  1. It will try to catch up on everything it missed while it was gone.
  2. The leader will send it all the latest log entries (messages or updates) to bring it up-to-date.

This way, the recovered node can be fully synced with the rest of the group, making sure it has the same information as everyone else.

Split Vote Scenario:

Before looking at the code, let’s also understand how Raft handles scenario’s where there is more than 1 leader. I have left this for last to minimize confusion.

Split votes or election conflicts can happen when two nodes become candidates at the same time and request votes from other nodes. This can result in a situation where no candidate receives a majority of votes, leading to a “tie.” Raft resolves this by using randomized election timeouts to help one candidate gain a majority in the next election round.

Hands-On: Code A Distributed Key-Value Store Using Raft:

Instead of implementing Raft itself from scratch, we can make use Go libraries that have already implemented the inner workings of Raft. One of them is the Hashicorp Raft library.

Code Reference: https://notes.eatonphil.com/minimal-key-value-store-with-hashicorp-raft.html

Running The Cluster:

Open multiple terminal windows and start instances with unique values:

go run main.go node1 localhost:2222 :8222
go run main.go node2 localhost:2223 :8223
go run main.go node3 localhost:2224 :8224

Once each node is running, join additional nodes to the cluster by making HTTP requests to the leader’s /join endpoint.

Example to join node2 and node3 to the leader node1:

curl "http://localhost:8222/join?followerId=node2&followerAddr=localhost:2223"
curl "http://localhost:8222/join?followerId=node3&followerAddr=localhost:2224"

This adds node2 and node3 to the Raft cluster under node1's leadership.

With the cluster set up, we can test the key-value storage:

Set a Key-Value Pair:

curl -X POST -d '{"Key": "hello", "Value": "world"}' http://localhost:8222/set

Get the Key-Value Pair from any node (the value should be replicated across the cluster):

curl "http://localhost:8222/get?key=hello"
# Or from node2
curl "http://localhost:8223/get?key=hello"

You should see {"Data": "world"} returned.

Code Explanation:

This Go code is a simplified example of a key-value store using Raft, a consensus algorithm for managing a replicated log in distributed systems.

Libraries:

github.com/hashicorp/raft and raftboltdb are third-party libraries from HashiCorp, used to implement Raft consensus and store logs in BoltDB.

State Machine and Set Payload Definition:

kvFsm is a structure representing the finite state machine for the Raft cluster. It holds a sync.Map, which acts as the in-memory key-value database that all nodes agree upon via Raft consensus.

setPayload is a struct representing data for key-value pairs. This struct is used to define commands (key-value pairs) sent to the Raft state machine.

Applying Commands:

Apply is called when a Raft log entry is committed. This method:

  • Decodes the log data into a setPayload structure.
  • Stores the key-value pair in the sync.Map.
  • Returns an error if decoding fails.
  • Logs the applied key-value pair.

Snapshot and Restore:

Raft can take periodic snapshots to capture the state. Here, snapshots are used to restore the database in case of crashes.

This Snapshot method creates a snapshot, but in our code, we have left it empty to keep things simple.Restore reads the snapshot and populates the sync.Map. First, it clears existing data and then decodes key-value pairs from the snapshot, storing them in the map.

Setting up Raft:

setupRaft function initializes and configures a Raft node.

  1. Directory Setup: Creates a directory to store Raft logs and snapshots.
  2. BoltDB Store: Initializes a BoltDB store to persist logs.
  3. Snapshot Store: Sets up the snapshot mechanism to save snapshots.
  4. TCP Transport: Configures network communication using a TCP transport for Raft communication.
  5. Raft Configuration: Sets up Raft configurations, including assigning a LocalID.
  6. Raft Initialization: Finally, it creates and initializes a Raft instance with these settings and adds the current server as a member of the Raft cluster.

HTTP Server and Handlers:

Finally, we have the http server and handlers that configure the HTTP server with join, set, and get endpoints.

A Quick Summary:

Raft is considered one of the easiest distributed consensus protocols to learn because it was explicitly designed with understandability in mind. Unlike Paxos, which we will learn later and can be complex due to its theoretical model and decentralized decision-making, Raft uses a structured approach to achieve consensus in a clear and straightforward manner. Here’s why Raft is often recommended for newcomers:

Raft organizes nodes into distinct roles — Leader, Follower, and Candidate — making the responsibilities of each node clear. The leader handles most of the decision-making, while followers replicate state, simplifying the flow.

Several widely used distributed systems and infrastructure tools implement Raft to provide consistent and fault-tolerant operations: HashiCorp Consul, etcd, TiDB and even the newer versions of Apache Kafka use Raft to work without Zookeeper.