Rethinking the leader election process #13826

ss-torres · 2025-02-24T02:26:15Z

ss-torres
Feb 24, 2025

We know that the current leader election is as following: https://redis.io/docs/latest/operate/oss_and_stack/reference/cluster-spec/ (Replica election and promotion). I have an idea about this stage, but I don't make sure whether I miss something or not. And I would give the idea in the following:
Masters reply to replica vote request

A replica would send the election request to the master with epoch, and a random number. And if other conditions is same, we think the replica with a bigger random number have a higher priority.
A master only votes a single time for a given epoch, and refuses to vote for older epochs: every master has a lastVoteEpoch field and will refuse to vote again as long as the currentEpoch in the auth request packet is not greater than the lastVoteEpoch. When a master replies positively to a vote request, the lastVoteEpoch is updated accordingly, and safely stored on disk. But there is an exception. If a master vote for a replica, but the replica send a message to a master that the replica give up the election for currentEpoch, then the master could vote for another replica, which with a higher priority.
When a replica send a election request to a master, and the master have voted. The master would tell it which replica gets its vote. If a replica have found that more than half of the master nodes have voted to other replicas and there are some replicas with higher priority. The replica would send messages to all the masters, who vote for the replica and tell them the replica give up the election for currentEpoch, and tells them the replica with the highest number, who also want to win the election, then these master would vote for the highest priority replica.
The masters, who receive the give up message, would compare the priority that it receives from the give up replica with the replica election requests they receive. And then these masters would vote for the replicas with highest priority again.
The replica, who receives the vote for more than one half of masters will win the election.
A master votes for a replica only if the replica's master is flagged as FAIL.
Auth requests with a currentEpoch that is less than the master currentEpoch are ignored. Because of this the master reply will always have the same currentEpoch as the auth request. If the same replica asks again to be voted, incrementing the currentEpoch, it is guaranteed that an old delayed reply from the master can not be accepted for the new vote.

Thanks for the opinions about the ideas before.

ShooterIT · 2025-02-26T03:49:40Z

ShooterIT
Feb 26, 2025
Collaborator

Hi, what's the problem you're trying to solve, i.e. do you encounter some issues with current version?

1 reply

ss-torres Feb 26, 2025
Author

Hi, @ShooterIT. For Raft Protocol, there are some cases that no candidate could get the majority votes. For example, there are five candidates, the two of the candidates get two votes, and one candidate get one vote. Then no candidate could get the majority votes. I have an idea that may help to get the majority votes in this case, so that it could speed up the election progress. I want to know whether this idea is taking into account all aspects?

ss-torres · 2025-03-08T03:49:55Z

ss-torres
Mar 8, 2025
Author

@ShooterIT , you could refer to the following description.

For the Raft algorithm, the leader election process is as follows:

Node Roles
Nodes in the Raft algorithm have three roles:
(1) Leader: Responsible for handling client requests, managing log replication, and sending heartbeats.
(2) Follower: Passively accepts logs and heartbeats from the Leader and does not initiate requests.
(3) Candidate: During the election process, a Follower can transition to a Candidate and initiate an election.
Election Trigger Conditions
Leader elections are typically triggered under the following conditions:
(1) Leader failure: A Follower does not receive a heartbeat from the Leader within a certain period (election timeout).
(2) New node joining: A newly joined node may trigger an election.
(3) Partition recovery: An election may be triggered after network partition recovery.
Election Process
The election process consists of the following steps:
(1) Follower Transitions to Candidate
When a Follower does not receive a heartbeat from the Leader within the election timeout period, it considers the Leader to have failed.
The Follower transitions its role to Candidate and initiates a new election.
(2) Candidate Initiates Voting
The Candidate first increments its term number (Term) by 1, indicating a new round of elections.
The Candidate sends a RequestVote RPC to other nodes in the cluster to request votes.
The Candidate votes for itself.
(3) Other Nodes Vote
Upon receiving the RequestVote RPC, nodes check the following conditions:
• Whether the Candidate's Term is greater than or equal to their own Term.
• Whether they have already voted for another Candidate.
• Whether the Candidate's log is at least as up-to-date as their own.
If the conditions are met, the node votes for the Candidate and resets its election timeout.
(4) Election Result
If the Candidate receives votes from a majority of nodes, it becomes the new Leader.
The new Leader immediately sends heartbeats to other nodes to prevent them from initiating new elections.
(5) Election Failure
If the Candidate does not receive enough votes within the election timeout period, the election fails.
The Candidate waits for a random period before re-initiating the election (to avoid split votes caused by multiple nodes initiating elections simultaneously).
Election Timeout
(1) To prevent multiple nodes from initiating elections simultaneously, Raft uses randomized election timeout periods (typically 150ms-300ms).
(2) Randomized timeout periods reduce the probability of election conflicts.
Log Consistency Guarantee
(1) During the election process, Raft ensures that only nodes with sufficiently up-to-date logs can become Leaders by comparing the Term and Index of logs.
(2) This guarantees that the Leader's log contains all committed log entries, ensuring consistency.
Election Optimization
(1) Pre-Vote Mechanism: Before formally initiating an election, a Candidate can first send a Pre-Vote request to confirm whether it has a chance to win the election, avoiding unnecessary Term increments.
(2) Leader Transfer: In certain situations, the Leader can proactively transfer leadership to another node to avoid frequent elections.

Modified Election Process:
The election process is divided into the following steps:
(1) Follower Transitions to Candidate (unchanged)

When a Follower does not receive a heartbeat from the Leader within the election timeout period, it considers the Leader to have failed.
The Follower transitions its role to Candidate and initiates a new election.
(2) Candidate Initiates Voting (modified)
The Candidate first increments its term number (Term) by 1 and generates a random int64 number, randPriority, indicating a new round of elections.
The Candidate sends a RequestVote RPC to other nodes in the cluster (this RPC request carries the random number randPriority) to request votes.
The Candidate votes for itself.
(3) Other Nodes Vote
Upon receiving the RequestVote RPC, nodes check the following conditions:
• Whether the Candidate's Term is greater than or equal to their own Term.
• Whether they have already voted for another Candidate.
• Whether the Candidate's log is at least as up-to-date as their own.
If the conditions are met, the node votes for the Candidate and resets its election timeout.
Upon receiving the RequestVote RPC, nodes record the maximum value maxNodePriority (first by log offset, then by term, then by the random number randPriority) among Candidate nodes that meet the following conditions:
• The Candidate's Term is greater than or equal to their own Term.
• The Candidate's log offset is at least as up-to-date as their own.
If a node refuses to vote for the Candidate (conditions not met or already voted for another node), it will return a message informing the Candidate.
(4) Voting Result (Receiving Rejected Votes)
If the Candidate receives rejected vote messages and the following conditions are met:
• If the message informs the voting node that the log is outdated,
• If the message informs the voting node that it has already voted for another node, then the Candidate node will record these nodes in a list (VoteOtherList) until the number of rejected nodes exceeds a majority (meaning the node cannot be elected according to the standard Raft algorithm, in which case it needs to self-rescue). If the Candidate's nodePriority is less than the recorded maxNodePriority or less than the maximum nodePriority in VoteOtherList, the node will initiate a specific node re-voting process.
Specific Node Re-Voting Process:
• Actively relinquish the Candidate role for this round.
• Send a message to all nodes that voted for it, requesting them to re-vote (the message includes the Candidate node with the maximum nodePriority recorded, obtained from VoteOtherList and maxNodePriority).
• Upon receiving this message, nodes compare the maxNodePriority in the message with the locally recorded maxNodePriority and send a vote to the node with the larger value.
• The specific node re-voting process aims to concentrate votes on the node with the highest nodePriority, thereby completing the election process.
(5) Voting Result (Receiving an Accepted Vote)
If the Candidate receives votes from a majority of nodes, it becomes the new Leader.
The new Leader immediately sends heartbeats to other nodes to prevent them from initiating new elections.

(6) Election Failure

If the Candidate does not receive enough votes within the election timeout period, the election fails.
The Candidate waits for a random period before re-initiating the election.

Leader Election Examples
Example 1: Raft Election Succeeds in One Round
Assume a 5-node cluster (A, B, C, D, E):

Initially, A is the Leader, and the other nodes are Followers.
After A fails, B and C's election timeout expires, and they transition to Candidates.
B and C initiate elections, sending RequestVote RPCs to other nodes.
Assume B's log is more up-to-date than C's, and D and E vote for B.
B receives 3 votes (including its own) and becomes the new Leader.

Example 2: Raft Election Fails in One Round

Initially, A is the Leader, and the other nodes are Followers.
After A fails, B, C, D, and E's election timeout expires, and they transition to Candidates.
B, C, D, and E initiate elections, sending RequestVote RPCs to other nodes. B, C, D, and E receive random numbers 100, 90, 80, and 70, respectively.
Assume B, C, D, and E each receive 1 vote. Since C, D, and E each receive three rejected vote messages (exceeding a majority), these three nodes relinquish their Candidate roles for this round and send messages to themselves (these three nodes vote for themselves), instructing them to transfer their votes to node B.
Node B receives 4 votes, exceeding a majority, and completes the election process.

Example 3: Another Raft Scenario

Initially, A is the Leader, and the other nodes are Followers.
After A fails, B and C's election timeout expires, and they transition to Candidates.
B and C initiate elections, sending RequestVote RPCs to other nodes, with random numbers 900 and 1000, respectively.
Assume B and C have the same log offset and receive votes from D and E, respectively. Here, a heuristic approach can be considered: since node A cannot vote, both B and C believe that under the existing Raft algorithm logic, neither will become the Leader. Since node C has a larger offset, node C will not initiate specific node re-voting. Node B will relinquish its Candidate role for this round and instruct nodes B and D, which voted for it, to transfer their votes to node C.
Node C receives 4 votes, exceeding a majority, and completes the election process.

Correctness of the Idea
At any moment, each node will only vote for one Candidate, so at any moment, there is at most one node with votes from a majority of nodes.

Efficiency
Under normal Raft operation, the new modifications have no impact. However, when the Raft algorithm cannot elect a Leader in one election round, the new modifications may facilitate the election of a Leader.

0 replies

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Rethinking the leader election process #13826

Uh oh!

{{title}}

Uh oh!

Replies: 2 comments 1 reply

Uh oh!

{{title}}

Uh oh!

Uh oh!

{{title}}

Uh oh!

Uh oh!

{{title}}

Uh oh!

Uh oh!

{{editor}}'s edit

{{editor}}'s edit

Uh oh!

Select a reply

Uh oh!

Rethinking the leader election process #13826

Uh oh!

ss-torres Feb 24, 2025

Replies: 2 comments · 1 reply

Uh oh!

ShooterIT Feb 26, 2025 Collaborator

Uh oh!

ss-torres Feb 26, 2025 Author

Uh oh!

Uh oh!

ss-torres Mar 8, 2025 Author

ss-torres
Feb 24, 2025

Replies: 2 comments 1 reply

ShooterIT
Feb 26, 2025
Collaborator

ss-torres Feb 26, 2025
Author

ss-torres
Mar 8, 2025
Author