關于 raft 算法 leader 選舉的一點改進想法
對于 raft 算法，leader 選舉算法如下：
1. 節點角色
Raft 算法中的節點有三種角色：
（1）Leader：負責處理客戶端請求、管理日志復制和發送心跳。
（2）Follower：被動接受 Leader 的日志和心跳，不主動發起請求。
（3）Candidate: 在選舉過程中，Follower 可以轉變為 Candidate，發起選舉。
2. 選舉觸發條件
Leader 選舉通常在以下情況下觸發：
（1）Leader 失效：Follower 在一定時間內（選舉超時時間）沒有收到 Leader 的心跳。
（2）新節點加入：新加入的節點可能觸發選舉。
（3）分區恢復：網絡分區恢復后，可能觸發選舉。
3. 選舉過程
選舉過程分為以下幾個步驟：
（1）Follower 轉為 Candidate
1）當 Follower 在選舉超時時間內沒有收到 Leader 的心跳，它會認為 Leader 失效。
2）Follower 將自己的角色轉變為 Candidate，并開始一次新的選舉。
（2）Candidate 發起投票
1）Candidate 首先將自己的任期號（Term）加 1，表示新的一輪選舉。
2）Candidate 向集群中的其他節點發送 RequestVote RPC，請求投票。
3）Candidate 會投票給自己。
（3）其他節點投票
1）收到 RequestVote RPC 的節點會檢查以下條件：
- Candidate 的 Term 是否大于或等于自己的 Term。
- 自己是否已經投票給其他 Candidate。
- Candidate 的日志是否至少和自己一樣新
2） 如果滿足條件，節點會投票給 Candidate，并重置自己的選舉超時時間。
（4）選舉結果
1) 如果 Candidate 收到超過半數節點的投票，它將成為新的 Leader。
2) 新的 Leader 會立即向其他節點發送心跳，以阻止其他節點發起新的選舉。
（5）選舉失敗
1）如果 Candidate 在選舉超時時間內沒有獲得足夠的投票，選舉失敗。
2）Candidate 會等待一段隨機時間后重新發起選舉（避免多個節點同時發起選舉導致分裂投票）。
4. 選舉超時時間
（1）為了防止多個節點同時發起選舉，Raft 使用隨機化的選舉超時時間（通常為 150ms-300ms）。
（2）隨機化超時時間可以減少選舉沖突的概率。
5. 日志一致性保證
（1）在選舉過程中，Raft 通過比較日志的 Term 和 Index 來確保只有日志足夠新的節點才能成為 Leader。
（2）這保證了 Leader 的日志包含所有已提交的日志條目，從而確保一致性。
6. 選舉優化
（1）Pre-Vote 機制：在正式發起選舉前，Candidate 可以先發起 Pre-Vote 請求，確認自己是否有機會贏得選舉，避免不必要的 Term 增加。
（2）Leader 轉移：在某些情況下，Leader 可以主動將領導權轉移給其他節點，避免頻繁選舉。
下面是改動內容：
選舉過程：
選舉過程分為以下幾個步驟：
(1) Follower 轉為 Candidate （這個步驟沒有改變）
1） 當 Follower 在選舉超時時間內沒有收到 Leader 的心跳，它會認為 Leader 失效。
2）Follower 將自己的角色轉變為 Candidate，并開始一次新的選舉。
(2) Candidate 發起投票 （這個步驟發生改變）
1) Candidate 首先將自己的任期號（Term）加 1，同時 Candidate 生成一個 int64 的隨機數 randPriority，表示新的一輪選舉。
2) Candidate 向集群中的其他節點發送 RequestVote RPC（這個 RPC 請求中會攜帶這個隨機數 randPriority），請求投票。
3) Candidate 會投票給自己。
(3) 其他節點投票
1）收到 RequestVote RPC 的節點會檢查以下條件：
- Candidate 的 Term 是否大于或等于自己的 Term。
- 自己是否已經投票給其他 Candidate。
- Candidate 的日志是否至少和自己一樣新
2）如果滿足條件，節點會投票給 Candidate，并重置自己的選舉超時時間。
3）收到 RequestVote RPC 的節點會記錄下滿足如下條件的 Candidate 節點中的最大值 maxNodePriority（先日志的 offset，后Term，最后隨機數 randPriority）：
- Candidate 的 Term 是否大于或等于自己的 Term。
- Candidate 的日志 offset 是否至少和自己一樣新
4) 節點如果拒絕投票給這個 Candidate（不滿足條件，或者已經投票給其他的節點），將會返回一條消息，告訴這個 Candidate。
（4）投票結果（收到拒絕投票）
1) 如果 Candidate 收到拒絕投票的消息，而且滿足許下的條件
- 如果這個消息告訴投票節點，因為日志比較舊的原因，
- 如果這個消息告訴投票節點，該節點已經投票給了其他節點，那么這個 Candidate 節點會把其他節點記錄下來形成一個其他節點列表（VoteOtherList），一直到這個節點收到的被拒絕的節點數超過半數（意味著這個節點按照 raft 的標準算法已經不可能被選上，這種情況下，需要自救），那么，如果這個 candidate 節點的 nodePriority 比這個節點記錄的 maxNodePriority 小，或者比 VoteOtherList 中的最大的 nodePriority 小
那么這個節點會發起特定節點重新投票的流程。
2） 特定節點重新投票的流程
- 主動放棄這一輪的 Candidate 身份
- 給所有投票給自己的節點發送讓其重新投票的消息（發送的消息中包含這個節點記錄最大 nodePriority 的 Candidate 節點，從 VoteOtherList 和 maxNodePriority 中獲取最大值）
- 收到這個消息的節點，會對比消息中的 maxNodePriority 和本地記錄的 maxNodePriority 中的較大值，然后發送投票給這個節點的消息
特定節點重新投票的流程是為了讓票盡可能得匯聚到擁有最大 nodePriority 的節點上面，從而完成選舉過程。
（5）投票結果 （收到同意投票）
1）如果 Candidate 收到超過半數節點的投票，它將成為新的 Leader。
2）新的 Leader 會立即向其他節點發送心跳，以阻止其他節點發起新的選舉。
(6) 選舉失敗
1）如果 Candidate 在選舉超時時間內沒有獲得足夠的投票，選舉失敗
2) Candidate 會等待一段隨機時間后重新發起選舉
Leader 選舉示例：
假設有一個 5 節點的集群（A、B、C、D、E）：
raft 一次選舉就可以成功的情況：
1. 初始狀態下，A 是 Leader，其他節點是 Follower。
2. A 失效后，B 和 C 的選舉超時時間到期，轉為 Candidate。
3. B 和 C 分別發起選舉，向其他節點發送 RequestVote RPC。
4. 假設 B 的日志比 C 新，D 和 E 投票給 B。
5. B 獲得 3 票（包括自己），成為新的 Leader。
raft 一次選舉不成功的情況：
1. 初始狀態下，A 是 leader，其他節點是 Follower。
2. A 失效后，B，C，D，E 的選舉超過時間到期，轉為 Candidate。
3. B，C，D，E 分別發起選舉，向其他節點發送 RequestVote RPC。同時 B，C，D，E 分別獲得隨機數 100， 90， 80， 70。
4. 假設 B，C，D，E 分別獲得 1 票，由于 C，D，E 都收到了三票被拒絕的消息（超過半數），所以這三個節點都會聲稱放棄這一輪的candiate身份，然后向自己發送消息（這三個都向自己投票），告訴轉投票給 B 節點。
5. B 節點獲取了 4 票，超過多數，完成選舉過程。
raft 另外一種情況：
1. 初始狀態下，A 是 leader，其他節點是 Follower。
2. A 失效后，B 和 C 的選舉超時時間到期，轉為 Candidate。
3. B 和 C 分別發起選舉，向其他節點發送 RequestVote RPC，同時 B 和 C 的隨機數分別為 900, 1000。
4. 假設 B 和 C 的日志 offset 相同，分別獲得了 D 和 E 的投票，那么這里可以考慮使用一種啟發式想法，我們認為 A 節點沒辦法投票，那么 B 和 C 都認為在現有的 raft 算法邏輯下，都不會成為主節點，由于 C 節點 offset 大，C 節點不會發起特定節點的重新投票。而 B 節點會放棄這一輪的 candidate 身份，同時告訴投給它的 B 節點和 D 節點，讓這兩個節點轉投 C 節點。
5. C 節點獲取了 4 票，超過多數，完成了選舉過程。
關于這個想法的正確性說明：
在任何時刻，每個節點只會投一個 Candidate，那么任何時刻，就最多有一個節點擁有超過半數的節點投票。
效率說明：
在 raft 正常 work 的狀態，新的改動不會有什么影響，而在 raft 算法在一次選舉過程中，沒辦法選出一個節點作為主節點時，可能促使選出一個主節點。
歡迎就上面的想法提出各種意見或者建議，謝謝。
浙公網安備 33010602011771號