Implementing a Simplified Raft Consensus Algorithm in Python

The Raft consensus algorithm is a widely used method for achieving distributed consensus in fault-tolerant systems. This challenge asks you to implement a simplified version of the Raft protocol in Python, focusing on the core leader election and log replication aspects. Successfully completing this challenge demonstrates understanding of distributed systems principles and consensus algorithms.

Problem Description

You are tasked with implementing a simplified Raft protocol in Python. The system consists of multiple nodes (servers) that communicate with each other to maintain a consistent, replicated log. Your implementation should handle leader election, log replication, and basic fault tolerance.

What needs to be achieved:

• Node Representation: Create a RaftNode class representing a single server in the Raft cluster. Each node should maintain its own state, including its log, current term, votedFor, and whether it believes it is the leader.
• Leader Election: Implement the leader election process. Nodes should periodically send election requests (heartbeats) to other nodes. If a node doesn't receive heartbeats from the current leader within a timeout period, it should initiate an election. The node with the highest term wins the election.
• Log Replication: Implement the log replication process. When a leader is elected, it should append new log entries to its log and replicate them to follower nodes. Followers should acknowledge log entries.
• Communication: Simulate communication between nodes using a simple message passing mechanism (e.g., a dictionary or queue).
• Fault Tolerance: The system should be able to tolerate the failure of a single node. If a leader fails, a new leader should be elected.

Key Requirements:

• The RaftNode class should have methods for:
  • __init__(self, node_id, initial_term=0): Initializes the node with a unique ID and initial term.
  • requestVote(self, term, candidate_id, last_log_index, last_log_term): Handles vote requests from candidates.
  • appendEntries(self, term, leader_id, prev_log_index, prev_log_term, entries, leader_commit): Handles log replication requests from the leader.
  • run(self): Simulates the node's operation, including sending heartbeats, initiating elections, and replicating logs.
• The system should maintain a consistent log across all nodes.
• The system should handle term transitions correctly.
• The system should elect a leader when no leader exists.

Expected Behavior:

• Nodes should periodically send heartbeats when they believe they are the leader.
• Nodes should initiate elections when they don't receive heartbeats from the leader within a timeout period.
• The node with the highest term should be elected as the leader.
• The leader should replicate log entries to follower nodes.
• Follower nodes should acknowledge log entries.
• The system should tolerate the failure of a single node.

Important Edge Cases to Consider:

• Split Brain: Handle scenarios where the network is partitioned, and multiple nodes believe they are the leader. (This simplified version doesn't require a full split-brain resolution, but the election process should prevent multiple leaders from being elected simultaneously).
• Log Conflicts: Handle scenarios where log entries on different nodes are inconsistent. (This simplified version assumes the leader's log is always correct).
• Election Timeout: The election timeout should be randomized to prevent split votes.
• Term Transitions: Ensure that nodes correctly handle term transitions during elections and log replication.

Examples

Example 1:

Input: 3 nodes (N1, N2, N3) with initial term 0. N1 initiates an election.
Output: N1 is elected as the leader (assuming N1 has the highest random timeout).
Explanation: N1 sends RequestVote messages to N2 and N3. If N2 and N3 vote for N1, N1 becomes the leader.

Example 2:

Input: N1 is the leader. N1 appends a new log entry (entry = "data1") to its log.
Output: The log entry "data1" is replicated to N2 and N3.
Explanation: N1 sends AppendEntries messages to N2 and N3. N2 and N3 append the entry to their logs and acknowledge N1.

Example 3: (Edge Case)

Input: N1 is the leader. N1 fails. N2 and N3 don't receive heartbeats from N1 within the timeout period.
Output: N2 or N3 initiates an election and is elected as the new leader.
Explanation: N2 and N3 send RequestVote messages to each other. The node with the highest random timeout wins the election.

Constraints

• Number of Nodes: The number of nodes in the cluster should be between 3 and 5 (inclusive).
• Log Entries: Each log entry should be a simple string.
• Timeout: The election timeout should be a random value between 1 and 3 seconds.
• Communication: Simulate communication using a dictionary where keys are node IDs and values are lists of messages.
• No Persistence: The log and node state are not persisted to disk. They are lost when the program terminates.
• Simplified Log: The log entries are simple strings. No complex data structures are required.

Notes

• This is a simplified implementation of the Raft protocol. Focus on the core concepts of leader election and log replication.
• You can use threads or asynchronous programming to simulate concurrent node operation.
• Consider using a dictionary to represent the communication channel between nodes.
• Randomize the election timeout to prevent split votes.
• Start with a small number of nodes (e.g., 3) and gradually increase the complexity.
• Test your implementation thoroughly with different scenarios, including node failures and log conflicts.
• Focus on clarity and readability of your code. Good comments are appreciated.
• The goal is to demonstrate understanding of the Raft algorithm, not to create a production-ready implementation.