Raft Consensus Algorithm

Raft Consensus

A prototype for demonstrating the raft consensus algorithm.
Explore the docs »

View Demo · Report Bug · Request Feature

Table of Contents

About The Project
- Built With
Getting Started
Project Details
Usage
License
Contact
Acknowledgments

About The Project

This project demonstrates the implementation of the Raft Consensus algorithm which is a consensus based protocol for distributed systems. This project is built as a part of the course CS60002 Distributed Systems at Indian Institute of Technology, Kharagpur. This project implements a simple version of the raft protocol, which can be used as a base template to build your own distributed system by adding features. Following are the core features implemented in this projects:

Raft Consensus RPCs
- RequestVote RPC
- AppendEntries RPC
Raft Log
- Log class
Raft State Machine
- StateMachine (a simple state machine)
Raft Leader Election
- LeaderElection RPC
Raft Consensus
- RaftConsensus class
Membership Change Feature
Visualization with timing diagram
Single client interface for testing the features

A single client interface was built mainly because this is a simple working protoype and not industrial-strength distributed system. The client interface is a simple command line interface which can be used to test the features of the project. All the RPCs are implemented in accordance with In Search of an Understandable Consensus Algorithm by Diego Ongaro and John Ousterhout. This implementation of the raft can be used as a base model and can be extended to build your own distributed system by adding advanced features and implementing multiple client gateway.

(back to top)

Built With

Following mentioned are the major frameworks/libraries used to bootstrap this project. Also included are the dependencies and addons used in this project.

Golang
- Leak Test - Required for memory leak testing
- Pretty Tables - Used in Timing Diagram visualization
- net/rpc - Wrappers required for building Raft RPCs
Shell Script

(back to top)

Project Details

Following are the details of the file structure of this project:

raft-consensus
├──── LICENSE
├──── README.md
├──── go.mod
├──── go.sum
├──── images
│     └── logo.png
│     └── overall.png
│     └── test1.png
│     └── test2.png
│     └── timing.png
├──── main.go
├──── raft
│     ├── config.go
│     ├── raft.go
│     ├── raft_test.go
│     ├── server.go
│     ├── simulator.go
│     └── storage.go
└──── utils
      ├── viz.go
      ├── visualize.sh
      ├── sample_logs.txt
      └── sample_output.txt

Following are the details of the file structure and their functionalities that are present in this code base.

raft/server.go - This file contains all the necessary code for implementing servers in a network using TCP along with various Remote Procedural Calls
- Server struct - Structure to define a service object
- Server methods - Methods to implement the server
  - CreateServer: create a Server Instance with serverId and list of peerIds
  - ConnectionAccept: keep listening for incoming connections and serve them
  - Serve: start a new service
  - Stop: stop an existing service
  - ConnectToPeer: connect to another server or peer
  - DisconnectPeer: disconnect from a particular peer
  - RPC: make an RPC call to the particular peer
  - RequestVote: RPC call from a raft node for RequestVote
  - AppendEntries: RPC call from a raft node for AppendEntries
raft/raft.go - This file contains the implementation of the Raft Consensus algorithm
- RNState - Enum to define the state of the Raft Node
  - Follower: Follower state
  - Candidate: Candidate state
  - Leader: Leader state
  - Dead: Dead/Shutdown state
- CommitEntry - Structure to define a commit entry
  - Command: Command to be executed
  - Term: Term in which the command was executed
  - Index: Index of the command in the log
- LogEntry - Structure to define a log entry
  - Command: Command to be executed
  - Index: Index of the command in the log
- RequestVoteArgs - Structure to define the arguments for RequestVote RPC
  - Term: Term of the candidate requesting vote
  - CandidateId: Id of the candidate requesting vote
  - LastLogIndex: Index of the last log entry
  - LastLogTerm: Term of the last log entry
- RequestVoteReply - Structure to define the reply for RequestVote RPC
  - Term: Term of the leader
  - VoteGranted: Vote granted or not
- AppendEntriesArgs - Structure to define the arguments for AppendEntries RPC
  - Term: Term of the leader
  - LeaderId: Id of the leader
  - PrevLogIndex: Index of the previous log entry
  - PrevLogTerm: Term of the previous log entry
  - Entries: List of log entries
  - LeaderCommit: Index of the leader's commit
- AppendEntriesReply - Structure to define the reply for AppendEntries RPC
  - Term: Term of the leader
  - Success: Success or not
  - ConflictIndex: Index of the conflicting log entry
  - ConflictTerm: Term of the conflicting log entry
- RaftNode - Structure to define a raft node
  - id: Id of the raft node
  - peerList: List of peers
  - state: State of the raft node
  - currentTerm: Current term of the raft node
  - votedFor: Id of the candidate voted for in the current term
  - CommitIndex: Index of the last committed entry
  - lastApplied: Index of the last applied entry
  - Log: Log of the raft node
  - NextIndex: Next index of the follower
  - MatchIndex: Match index of the follower
  - server: Server object of the raft node
  - db:_ Database object of the raft node
  - commitChan: Channel to send the commit index of logs to the state machine
  - newCommitReady: Internal channel used to notify that new log entries may be sent on commitChan
  - trigger: Trigger AppendEntries RPC when some relevant condition is met
  - electionResetEvent: Last time at which the election timer was reset
- Raft utility functions
  - sendCommit: Send the commit index to the state machine
  - runElectionTimer: Reset the election timer
  - electionTimeout: Set Election timeout
  - startElection: Start an election
  - becomeLeader: helper function to become the leader
  - leaderSendAEs: Send AppendEntries RPCs to all the followers in the cluster and update Node
  - lastLogIndexAndTerm: Get the last log index and term
  - AppendEntries: Send AppendEntries RPCs to all the followers
  - RequestVote: Send RequestVote RPCs to all the peers
  - becomeFollower: helper function to become the follower
  - restoreFromStorage: Restore the state of the raft node from storage
  - readFromStorage: Read the state of the raft node from storage
  - Submit: Submit a command to the raft node
  - Stop: Stop the raft node
  - Report: Report the state of the raft node
raft/simulator.go - This file contains all the necessary code to setup a cluster of raft nodes, interact with the cluster and execute different commands such as read, write and config change on the cluster.
- ClusterSimulator struct - Structure to define a Raft cluster
- Simulator methods - Methods to implement the cluster
  - CreateNewCluster: create a new Raft cluster consisting of a given number of nodes and establish
  - connections between them
  - Shutdown: shut down all servers in the cluster
  - CollectCommits: reads channel and adds all received entries to the corresponding commits
  - DisconnectPeer: disconnect a server from other servers
  - ReconnectPeer: reconnect a disconnected server to other servers
  - CrashPeer: crash a server and shut it down
  - RestartPeer: restart a crashed server and reconnect to other peers
  - SubmitToServer: submit a command to a server
  - Check_Functions: auxiliary helper functions to check the status of the raft cluster: CheckUniqueLeader, CheckNoLeader and CheckCommitted
raft/raft_test.go - This file has a set of test functions designed to test the various functionalities of the raft protocol. The tests can be designed into 3 major classes:
- Tests to check Leader Election
- Tests to check Command Commits
- Tests to check Membership Changes
raft/config.go - This file has a custom implementation of a Set Data Structure as it is not provided inherently by Go. This implementation is inspired by Set in Golang. It provides the following functions:
- makeSet: make a new set of type uint64
- Exists: check if an element exists in the set
- Add: add a new element to the set
- Remove: remove an element from the set
- Size: get the number of elements in the set
util/viz.go - This file contains the visualization functions for the raft protocol. It is used to visualize the raft protocol's timing diagram
- ParseTestLog:_ parse the log file and return the list of commands
- TableViz: visualize the raft protocol in a table format

(back to top)

Getting Started

To get a local copy up and running follow these simple steps.

Prerequisites

Go
To run the code in this Assignment, one needs to have Go installed in their system. If it is not already installed, it can be done by following the steps in Install Go Ubuntu

Installation

In order to setup a local copy of the project, you can follow the one of the 2 methods listed below. Once the local copy is setup, the steps listed in Usage can be used to interact with the system.

Clone the repo

git clone https://github.com/debajyotidasgupta/raft-consensus

Alternatively, unzip the attached submission zip file to unpack all the files included with the project.
```
unzip <submission_file.zip>
```
Change directory to the raft-consensus directory
```
cd raft-consensus
```
If some dependency is missing, install it with the following command
```
go get <dependency>
```

(back to top)

Setting DEBUG level

In order to obtain logs regarding the execution of Raft algorithm you need to set DEBUG variable as 1 inside raft/raft.go Similarly if you do not wish to see huge logs and just see the outputs of execution you can set the DEBUG level to 0 (recommended)

Usage

Once the local copy of the project has been setup, follow these steps to interact with the system and run tests on the system

User interaction with the system

To interact with the system from the console, do the following steps:

Open terminal from the main project directory
Run the main go file (Ensure that DEBUG is set to 0 in raft/raft.go file)
```
go run main.go
```
You will be presented with a menu with necessary commands to create raft cluster, send commands, etc.

NOTE: While using the features like set value, get value etc., that should pass through the leader node, you can user the 9th menu and find the leader and then send the request to leader node. Sending a such a request to a non leader node will lead to failure. This implementation is in accordance with the official Raft Implementation from the paper.

Running tests

A comprehensive set of tests has been provided in raft/raft_test.go. In order to run these tests, do the following steps:

To run a particular test execute the following command from the main project directory
```
go test -timeout 30s -v -run ^[Test Name]$ raft-consensus/raft
```
To run the entire test suite run the following command from the main project directory
```
go test -v raft-consensus/raft
```

Visualizing Test Results

The utils directory provides functionalities to cleanly visualize the test logs in the form of a timing diagram table. To visualize the test logs follow the steps below:

[Important] Ensure that the DEBUG level is set to 1 in raft/raft.go
```
const DEBUG = 1
```
Run a test and save its logs in the utils directory (execute from root project folder raft-consensus).
```
go test -timeout 30s -v -run ^[Test Name]$ raft-consensus/raft > utils/logs.txt
```
Use the logs to generate the timing diagram using the utils/viz.go file (This is to be executed from inside the utils directory)
```
cd utils
go run viz.go < logs.txt > output.txt
```

Alternatively, you can use the following command to generate the timing diagram from the logs

[Important] Ensure that the DEBUG level is set to 1 in raft/raft.go
```
const DEBUG = 1
```
Run the following command from inside the utils directory
```
./visualize.sh -t <test_name>
```

In both cases, the output will be saved in the utils directory as output.txt
A sample log file and output file is provided in the utils directory.

(back to top)

License

Distributed under the MIT License. See LICENSE.txt for more information.

(back to top)

Contact

Name	Roll No.	Email
Debajyoti Dasgupta	18CS30051	debajyotidasgupta6@gmail.com
Somnath Jena	18CS30047	somnathjena.2011@gmail.com
Sagnik Roy	18CS10063	sagnikr38@gmail.com

(back to top)

Acknowledgments

List of resources we found helpful and we would like to give them some credits.

(back to top)