raft

README

Raft Consensus Algorithm

Raft is a consensus algorithm designed to be easy to understand while achieving the same goals as Paxos. Raft is often used in distributed systems for managing replicated logs, ensuring that all participating nodes in the network agree on the same series of actions or events. The primary idea behind Raft is to achieve consensus in a distributed cluster by electing a leader node that is responsible for log replication.

How Raft Works

1. Nodes and Roles:
   • Leader: Responsible for managing the replicated log, handling client requests, and distributing them to other nodes.
   • Followers: Passively replicate the log entries as dictated by the leader.
   • Candidate: A node that can become a leader by initiating an election.
2. Phases of Raft:
   • Leader Election: If a leader fails or is unreachable, nodes enter a candidate state and initiate an election to select a new leader.
   • Log Replication: The leader accepts commands from clients, adds them to its log, and then replicates these log entries to follower nodes.
   • Commit and Apply: Once an entry is safely replicated to a majority of nodes, the leader commits the entry and applies it to the state machine. Followers apply entries once they receive confirmation of commitment.
3. Heartbeats:
   • Leaders periodically send heartbeat messages to followers to maintain authority and prevent new elections from occurring.

Features of Raft

• Leader-Based Consensus: Raft simplifies consensus by always having a single leader that handles all requests and manages replication.
• Partition Tolerance: Raft can continue to make progress as long as a majority of nodes are available.
• Log Consistency: All nodes eventually reach consensus on the same sequence of log entries, ensuring consistency in the distributed state machine.

Structure of This Implementation

In this folder, we provide a Go implementation of the Raft consensus algorithm. The implementation simulates leader election, log replication, and achieving consensus in a distributed network.

Files

• raft.go: Contains the Go implementation of the Raft consensus algorithm.

Key Elements of the Code

• Blockchain: Represents the distributed replicated log.
• Node: Represents individual nodes that can be a leader, follower, or candidate.
• Leader Election: Nodes can transition between follower, candidate, and leader roles as required to maintain a consistent leader in the cluster.

Code Example

package main

import (
    "fmt"
    "consensus-algorithms-edu/algorithms/raft"
)

func main() {
    blockchain := raft.NewRaftNetwork(5)

    blockchain.Leader.Lead("First log entry")
    blockchain.Leader.Lead("Second log entry")
    blockchain.Leader.Lead("Third log entry")

    for _, block := range blockchain.Blocks {
        fmt.Printf("Index: %d\nTimestamp: %s\nData: %s\nPrevious Hash: %s\nHash: %s\n\n", 
            block.Index, block.Timestamp, block.Data, block.PrevHash, block.Hash)
    }
}

How to Run the Example

1. Initialize the Network: Use NewRaftNetwork() to create a new Raft network with multiple nodes.
2. Leader Election: Initially, one of the nodes is selected as the leader. If the leader fails, other nodes can initiate an election.
3. Add Log Entries: Use the Lead() function from the leader node to add log entries, which are replicated to other nodes.

Advantages of Raft

• Understandable: Raft was explicitly designed to be easier to understand compared to other consensus algorithms like Paxos, making it suitable for educational purposes and practical implementations.
• Strong Leadership: Raft maintains a strong and clear distinction between leader and follower roles, which simplifies log management and consistency.
• Fault Tolerance: Raft can tolerate failures of up to half of the nodes (i.e., it requires a majority of nodes to operate).

Limitations

• Single Leader Bottleneck: The leader handles all the requests, which could become a bottleneck under heavy load.
• Leader Failures: When the leader fails, the system must perform a new election, which may introduce temporary unavailability until a new leader is elected.

Use Cases

• Replicated State Machines: Raft is often used to implement consistent replicated state machines in distributed systems.
• Distributed Key-Value Stores: Systems like etcd and Consul use Raft to achieve consensus for configuration management and service discovery.

License

This implementation is licensed under the MIT License.

Documentation

Overview

Package raft implements a basic version of the Raft consensus algorithm for a distributed blockchain network. Raft is a consensus algorithm designed for managing replicated logs in distributed systems, focusing on simplicity and understandability compared to other consensus algorithms like Paxos. It relies on leader election to ensure that only one node is actively managing updates, thereby simplifying the consensus process. This implementation simulates the core functions of Raft, including leader election, proposing new blocks, and achieving consensus before committing blocks to the blockchain.

Index

• type Block
  • func NewBlock(data string, prevHash string, index int) Block
  • func (b *Block) CalculateHash() string
• type Blockchain
  • func NewBlockchain() *Blockchain
  • func NewRaftNetwork(size int) *Blockchain
  • func (bc *Blockchain) AddBlock(block Block)
  • func (bc *Blockchain) BroadcastBlock(block Block) bool
• type Node
  • func NewNode(id int, blockchain *Blockchain) *Node
  • func (n *Node) CommitBlock(block Block)
  • func (n *Node) Lead(data string)
  • func (n *Node) ProposeBlock(data string) Block
  • func (n *Node) RequestVote() bool
  • func (n *Node) VerifyBlock(block Block) bool
  • func (n *Node) VoteFor(candidateID int) bool

Types

type Block

type Block struct {
	Index     int    // Position of the block in the blockchain.
	Timestamp string // Time when the block was created.
	Data      string // Data contained within the block (e.g., transactions).
	PrevHash  string // Hash of the previous block to maintain immutability.
	Hash      string // SHA-256 hash of the current block.
}

Block represents an individual block in the blockchain. It contains information such as the index, timestamp, data, and cryptographic hashes.

func NewBlock

func NewBlock(data string, prevHash string, index int) Block

NewBlock creates a new block given data, the previous block's hash, and the index. It calculates the block's hash to ensure integrity.

func (*Block) CalculateHash

func (b *Block) CalculateHash() string

CalculateHash generates the SHA-256 hash of the block's contents. This ensures that any change to the block's data will produce a completely different hash.

type Blockchain

type Blockchain struct {
	Blocks []Block // A slice of all blocks in the blockchain.
	Nodes  []Node  // A list of nodes participating in the Raft consensus network.
	Leader *Node   // Pointer to the current leader node responsible for managing updates.
}

Blockchain represents the distributed ledger that is managed by multiple nodes.

func NewBlockchain

func NewBlockchain() *Blockchain

NewBlockchain initializes a new blockchain with a genesis block. The genesis block is the initial block that forms the foundation of the blockchain.

func NewRaftNetwork

func NewRaftNetwork(size int) *Blockchain

NewRaftNetwork initializes a Raft network with the specified number of nodes. The nodes collaborate to reach consensus and elect a leader to manage block proposals.

func (*Blockchain) AddBlock

func (bc *Blockchain) AddBlock(block Block)

AddBlock appends a new block to the blockchain. This function is called once a new block is validated and consensus is achieved.

func (*Blockchain) BroadcastBlock

func (bc *Blockchain) BroadcastBlock(block Block) bool

BroadcastBlock sends a proposed block to all nodes for verification. A block is considered valid if more than half of the nodes approve it.

type Node

type Node struct {
	ID         int         // Unique identifier for the node.
	IsLeader   bool        // Indicates if the node is the leader.
	Blockchain *Blockchain // Reference to the blockchain managed by the node.
}

Node represents an individual node within the Raft network. Nodes can participate in leader elections, propose blocks, and verify or commit blocks.

func NewNode

func NewNode(id int, blockchain *Blockchain) *Node

NewNode creates a new node with the given ID and associates it with a blockchain.

func (*Node) CommitBlock

func (n *Node) CommitBlock(block Block)

CommitBlock commits a verified block to the blockchain. This function is called by all nodes once consensus has been achieved.

func (*Node) Lead

func (n *Node) Lead(data string)

Lead allows the leader to propose and commit a new block to the blockchain. The leader proposes a block, broadcasts it for approval, and if approved, commits it.

func (*Node) ProposeBlock

func (n *Node) ProposeBlock(data string) Block

ProposeBlock allows the leader node to create a new block proposal based on the latest block.

func (*Node) RequestVote

func (n *Node) RequestVote() bool

RequestVote allows a node to request votes from other nodes during the leader election process. If the node receives a majority of votes, it becomes the new leader.

func (*Node) VerifyBlock

func (n *Node) VerifyBlock(block Block) bool

VerifyBlock allows a node to verify the validity of a proposed block. It checks if the previous hash matches the last block in the chain and if the block hash is correct.

func (*Node) VoteFor

func (n *Node) VoteFor(candidateID int) bool

VoteFor allows a node to vote for a candidate during the leader election. In this simplified version, nodes always vote for the requesting candidate.