Implementing a Simplified Raft Consensus Protocol in Python

The Raft consensus algorithm is a fundamental piece of distributed systems, enabling fault-tolerant coordination among a cluster of servers. This challenge asks you to implement a simplified version of Raft in Python, focusing on the core mechanisms of leader election and log replication. This exercise will deepen your understanding of distributed consensus, crucial for building reliable and scalable applications.

Problem Description

Your task is to implement a simplified Raft consensus protocol for a cluster of servers communicating over a network. You will need to simulate the behavior of Raft nodes, including their transitions between follower, candidate, and leader states. The primary goals are to correctly implement the leader election process and the basic log replication mechanism.

Key Requirements:

1. Node States: Implement the three Raft node states:

   • Follower: Listens for heartbeats from the leader and transitions to candidate if a heartbeat is missed.
   • Candidate: Initiates an election when it doesn't hear from a leader. It requests votes from other servers and becomes leader if it receives a majority.
   • Leader: Manages the cluster, accepts client requests, replicates log entries to followers, and sends heartbeats.

2. Leader Election:

   • When a follower times out (no heartbeats received from the current leader), it becomes a candidate.
   • Candidates increment their term, vote for themselves, and send RequestVote RPCs to all other servers.
   • Servers grant votes if the candidate's term is at least as high as their own and they haven't voted in that term yet.
   • A candidate that wins a majority of votes becomes the leader.
   • If an election splits votes (no candidate gets a majority), a new election will be triggered after a timeout.

3. Log Replication (Simplified):

   • Once a leader is elected, it should be able to receive (simulated) client commands.
   • The leader appends these commands as log entries.
   • The leader sends AppendEntries RPCs to followers to replicate log entries.
   • Followers append entries to their logs and respond to the leader.
   • A leader considers an entry committed once it's replicated on a majority of servers. (For this simplified challenge, you can assume an entry is "replicated" when a follower acknowledges receipt).

4. Timeouts:

   • Election Timeout: Followers use this to decide when to start an election. This timeout should be randomized to prevent split votes.
   • Heartbeat Timeout: Leaders use this to send periodic AppendEntries RPCs (even if there are no new entries) to maintain authority.

5. RPC Simulation: You will need to simulate Remote Procedure Calls (RPCs) between nodes. For this challenge, you can use a simple message passing mechanism (e.g., queues or direct method calls within your simulation environment) instead of actual network sockets.

Expected Behavior:

• In a cluster of N servers, a single leader should emerge and remain stable as long as it's functioning.
• Followers should correctly transition to candidates and participate in elections when the leader fails or becomes partitioned.
• Once a leader is established, it should be able to receive and acknowledge (in simulation) new log entries.
• The system should be resilient to the failure and recovery of individual nodes (simulated by stopping/starting nodes).

Edge Cases to Consider:

• Split Votes: How does the system handle scenarios where no candidate receives a majority of votes?
• Network Partitions: How would your implementation behave if some nodes cannot communicate with others? (You might not need to fully implement partition handling, but consider how it would affect your design).
• Leader Failure: What happens when the current leader stops responding?

Examples

Example 1: Basic Leader Election

Imagine a cluster of 3 nodes (Node A, Node B, Node C). Initially, all are followers.

• Time 0: All nodes start. Node A's election timeout is the shortest.
• Time 10 (arbitrary): Node A times out, becomes a candidate, term 1, votes for itself, sends RequestVote to B and C.
• Time 12: Node B receives RequestVote from A (term 1). B has not voted, so it votes for A.
• Time 13: Node C receives RequestVote from A (term 1). C has not voted, so it votes for A.
• Time 14: Node A receives votes from B and C. It has a majority (2 out of 3, including itself), becomes leader for term 1. Node A starts sending heartbeats.

Input: A cluster of 3 nodes, initial state: all followers.
Output: Node A becomes the leader after initiating an election.
Explanation: Node A times out first, becomes a candidate, requests votes, and receives a majority, thus becoming the leader.

Example 2: Log Replication

Assume Node A is the leader (term 1).

• Leader A: Receives a client command "SetX=10". Appends this to its log as entry (term=1, index=1, command="SetX=10").
• Leader A: Sends AppendEntries RPC to Node B and Node C, including the new log entry.
• Node B: Receives AppendEntries. Appends the entry to its log: (term=1, index=1, command="SetX=10"). Responds to A with success.
• Node C: Receives AppendEntries. Appends the entry to its log: (term=1, index=1, command="SetX=10"). Responds to A with success.
• Leader A: Receives acknowledgments from B and C. Now, entry (term=1, index=1) is considered committed.

Input: Node A is leader. Cluster has 3 nodes. Client sends command "SetX=10" to A.
Output: Log entry `(term=1, index=1, command="SetX=10")` is replicated to Node B and Node C, and considered committed by Node A.
Explanation: The leader appends the command to its log and replicates it to followers. Upon receiving a majority of acknowledgments, the entry is committed.

Example 3: Leader Failure and Re-election

Cluster of 3 nodes (A, B, C). A is the leader.

• Scenario: Node A suddenly stops responding (simulated failure).
• Node B and C (Followers): Haven't received heartbeats from A for their election timeout period.
• Node B: Times out, becomes candidate, term 2, votes for itself, sends RequestVote to C.
• Node C: Receives RequestVote from B (term 2). C's current term might be 1 (from A's leadership). C votes for B.
• Node B: Receives vote from C. Has majority (2/3). Becomes leader for term 2.
• (Eventually, A might recover and become a follower in the new term)

Input: A cluster of 3 nodes. Node A is leader. Node A then fails.
Output: Node B or C (whichever times out first) becomes the new leader after a new election.
Explanation: When the leader fails, followers time out and initiate a new election. A new leader is elected in the next term.

Constraints

• You will simulate a cluster of 3 to 5 nodes.
• The communication between nodes will be simulated using Python's built-in data structures (e.g., queues, lists) or simple object interactions. No actual network programming is required.
• The implementation should be in Python.
• Your solution should handle node failures and recoveries by stopping and starting node simulations.
• Focus on the core Raft logic; complex optimizations or advanced RPC error handling are not required for this challenge.

Notes

• You will need to manage the state of each node (Follower, Candidate, Leader) and its current term.
• Randomizing election timeouts is crucial for preventing split votes. A common approach is to pick a random value within a given range (e.g., 150-300ms).
• Consider how you will manage timers for election timeouts and heartbeat intervals.
• Think about how messages (like RequestVote and AppendEntries) will be structured and passed between simulated nodes.
• A common way to model RPCs in a simulation is to have a central "message bus" or directly call methods on other node objects, passing the message data.
• The concept of "committed" log entries is important. In Raft, an entry is committed when it is replicated to a majority of servers. For this simplified challenge, you can consider an entry committed on the leader once it has been acknowledged by a majority of followers.