簡介

? ? ? ?dledger是openmessaging的一個組件， raft算法實現，用于分布式日志，本系列分析dledger如何實現raft概念，以及dledger在rocketmq的應用

? ? ? 本系列使用dledger v0.40

? ? ? 本文分析dledger的選主

關鍵詞

Raft

Openmessaging

心跳/選主

參考資料

In Search of an Understandable Consensus Algorithm ?raft論文簡版

選主

? ? ? ? ?選主是dledger的關鍵特性，主節點承擔處理Client請求，復制日志到跟隨者節點，dledger通過心跳發起選舉。

關鍵屬性

本節介紹關鍵屬性，為下面分析準備

• term 任期/輪次

任期: 新的選舉開始到下一個選舉開始，左閉右開的時間區間，包括選舉期和工作期兩部分

輪次：任期內選舉的輪次，任期內可多輪不提升term選舉

• needIncreaseTermImmediately

需要立即增加term的設置，只提升任期，但不對其他節點發起投票請求，用于term落后的節點

• nextTimeToRequestVote

下次請求投票時間

System.currentTimeMillis() + minVoteIntervalMs + random.nextInt(maxVoteIntervalMs - minVoteIntervalMs)

dledger根據情況有不同的設定，下次發起選舉時間的差異正是選舉的關鍵

• currVotedFor

本節點投票給誰了，該值提升term時設置為null；該值設置地方只有一處，處理投票handlerVote，即，不提升term節點，投票給誰不會改變

• currTerm

節點當前所處任期

• ledgerEndTerm/ledgerEndIndex

已寫入日志的term；已寫入日志的索引

兩個數據是節點成為leader的關鍵數據，作為leader已寫入日志的term/已寫入日志的索引越多越好

分析

選舉分3塊，第一投票邀請；第二投票；第三投票統計，部署下一步操作，其中

投票邀請

候選者定時維護狀態，maintainAsCandidate方法發起投票邀請，邀請其他節點(包括自己)為自己投票

1 檢查是否符合投票條件，投票時間到 或者 設置了需要立即提升term

2 double check 節點處于候選者角色

3 是否提升term

lastParseResult是上一輪發起投票分析結果，參考后面投票統計

只需提升term，追趕上該輪投票的term，不發起投票邀請

4 獲取節點的已寫入的term/index

5 重置needIncreaseTermImmediately

term落后，設置該標記為true，提升term后，恢復默認

6 邀請節點投自己一票，邀請也發給自己

投票

節點，包括發起投票的領導者，處理投票請求

1 投票發起者的合法性檢查

投票請求的leader是發起者，投票實際是拉票，邀請其他節點投自己一票

1.1 leader是否組內的節點

目前版本不知道集群變更，實際不會出現

1.2 不應該出現的leader

參看問題分析

-----------------------------------------分割線------------------------------------------

2 檢查已寫入日志term和index

這個好理解，想做leader，寫入的日志應該比我多；比我少的，沒資格讓我投你票

-----------------------------------------分割線------------------------------------------

term相關檢測

3? 請求節點的term < 本節點term，拒絕投票，請求節點的term落后了

4? term一致

4.1 currVoteFor為空，還沒投票

后面的檢測沒問題的話，本節點投票給發起節點

4.2? currVoteFor不為空，已投票，而且投的是發起節點

4.3? currVoteFor不為空，投票給其他節點了

下面繼續細分，本節點是否已有leader，這里考慮一個問題，有無可能currVoteFor為空，并且有leader?

不可能，分兩種情況，

1. 本節點是跟隨者，本節點未進入本term選舉，本節點term小于發起者term
2. 本節點是候選者，提升term置空currVoteFor，成為候選者要置空leader

4.4 本節點term落后了

設置needIncreaseTermImmediately，提升term，但不發起投票請求

5 發起節點term與本節點已寫入日志term比較

與2相同，發起節點資格不夠，不能投你

-----------------------------------------分割線------------------------------------------

6 本節點用戶設置優先當領導，而且條件符合，不投票給發起節點，自己優先

7 最后，投票給請求節點

投票統計

7 首先準備好統計量

-----------------------------------------分割線------------------------------------------

統計不詳細分析，看注釋便清楚

-----------------------------------------分割線------------------------------------------

7.3 提早通過latch等待，3個條件

1. 已有選出leader

2. 票數已過半，自己將成為leader

3. 本節點未夠票，剩下的票不過半，即，也沒有其他人選上

7.4 統計所有節點數

總數達到allNum.get() == memberState.peerSize()，所有心跳請求返回(包括連接不上)，退出

* memberState.peerSize() 實為 memberState.peerSize()+1-1，peerSize從0開始，數量需+1，排除自己，數量-1

部署下一論投票行動

8 投票統計結果決定下一步投票行動

8.1 本節點term落后了

提升任期，再發起投票請求，這點跟投票者不一樣，投票者term落后設置needIncreaseTermImmediately=true，即只提升，不發起投票請求，這樣做容易理解，選出主節點，需要爭票的少，投票的多，投票發起節點只有一個，投票的節點多個

8.2 集群已有leader，無需再發起投票，但不立即轉為follower，延長下次投票，等待下一個leader的心跳，調整為正確的leader，便進入正常工作

8.3 有效返回節點數過少，通常是網絡原因，只有等

8.4 除去日志比自身完整的節點，還不夠票數當選，讓賢，延遲下次投票邀請的時間，讓其他節點發起投票

8.5 當選leader

8.6 加上term落后的節點夠票數讓本節點當選

此時，term落后的節點提升term，立即選舉增加本節點當選的幾率，但REVOTE_IMMEDIATELY實際沒使用

8.7 選票分散，提升任期，投票

9 選上了，趕快坐上寶座當領導

總結：行動的目標是盡快選到領導者，策略上盡量逼近目標無疑是正確的。

有效性

本節去掉異常情況，只看選舉的主體流程，分析一下選主的有效性，dledger的規則/邏輯怎樣讓分布節點獲得過半票數

去掉的異常情況

1 本節點term落后

2 有效返回過少

3 寫入日志term/index比投票節點小

4 投票節點term小于本節點

選舉主體：

1 已經選出領導者

2 獲得投票過半

3 投票分散，未能選為領導者

1/2 兩種情況選舉完成

3，提升term；設置下次投票時間，投票時間有范圍的隨機值，只要有不多于2個節點率先發起投票，其他節點投票，這就可以選出主節點

問題

選舉未分析出來的點

不是預期的leader

目前沒有分析出怎么出現這種情況

系列文章

• 架構，核心組件和rpc組件 完成
• 心跳和選舉 完成
• 日志寫入/復制和存儲 TBD? 包括日志寫入和復制，日志存儲組件
• 集成rocketmq rocketmq使用dledger實現消息存儲復制；broker控制器 元數據復制
• 快照/狀態機
• 集群成員變更? 成員變更管理，節點的上線下線發現，dledger v0.4未實現，但計劃中，未來版本實現
• jraft? ?“double check” ?多重分析，jraft比較忠實實現了raft算法，在dledger基礎上，再深入研究jraft對raft更深入的認識