這裡簡要紀錄選舉演算法的想法
節點角色 [local-0]
節點的角色應該是以下三種之一
- Follower
- Candidate
- Leader
我們希望leader至多只有一個，只有有leader的集群才會對外提供服務
任期 [local-1]
任期可以叫term或是generation clock，用來這是第幾輪的決策，每個節點都要有這個資訊
日誌 [local-2]
日誌的每個entry應該包含
- 索引（index），每次新增entry都應該嚴格遞增的數字
- 任期（term），entry寫入時的任期
- 指令（command），要進行什麼操作
狀態轉換 [local-5]
節點啟動時可以不知道leader是誰，我們可以設定為
- term為1
- 角色為follower
- 設定定時任務檢查leader發送的heartbeat訊號
如果定時任務歸零時沒有收到leader發送的heartbeat訊號，就發起選舉；反之，重設定時任務
發起選舉 [local-3]
發起選舉可以定義為
- 把節點的term加一
- 轉換為candidate
- 投給自己
- 要求其他節點投給自己
- 等待有限時間N
現在會有幾種可能
- 在N時間內有過半節點投給自己。這時候表示自己就是leader，轉換狀態並設定循環任務不斷發送heartbeat訊號給所有節點
- 在N時間後沒有得到過半節點的票，逾時再次發起選舉（回到最前面）
- 在N時間內收到leader廣播的heartbeat，而且這個leader的term比自己大。這時候就轉變為follower，更新term並紀錄誰是leader
- 在N時間內收到其他candidate要求投給它的投票訊息，而且該投票訊息的term比自己大。這時候也轉為follower，更新term
由於candidate把term加一了才繼續，舊的領導者（比如斷線之後再連回來）的heartbeat就不會影響candidate跟其他節點
處理投票請求 [local-4]
收到投票請求的時候需要按照以下順序決策，以下的同意就表示同時要轉換為follower狀態
- candidate的term小於當前節點的term：回覆拒絕
- candidate的term大於當前節點的term：回覆同意
- candidate的term跟當前節點一樣時要繼續攤開
- 已經投過票了：請求candidate就是已經投過的candidate，回覆同意；反之回覆拒絕
- candidate的log index大於自己：回覆同意
- 其餘情況都回覆拒絕
之所以要看log index，是要避免狀態比較落後的節點成為leader，以免資料遺失
原則上就是
- 任期高者不投給任期低者
- log index高者不投給log index低者
- 每個任期只投一張票（否則過半就沒有意義）
leader如果直接看到比自己大的term（無論是heartbeat還是投票訊息），都應該放棄leader身份轉換為follower
現在我們來看逾時後投票的效果