Part 05：Raft論文翻譯-《CONSENSUS: BRIDGING THEORY AND PRACTICE》（基礎(chǔ)Raft-Leader選舉）
3.4 Leader Election（Leader選舉）
Raft使用心跳機制來觸發(fā)Leader選舉。當(dāng)服務(wù)器啟動時，它們一開始是Follower。只要服務(wù)器從Leader或Candidate接收有效的rpc，它將處于Follower狀態(tài)。Leader定期向所有Follower發(fā)送心跳(沒有Log Entry的RPC請求)，以維持Leader狀態(tài)。如果Follower在被稱為選舉超時的時間內(nèi)沒有收到來自Leader的通信，那么它就假設(shè)沒有有效的Leader，那么這個Follower就會編程Candidate并開始選舉來選擇新的Leader。
當(dāng)開始選舉時，Candidate將增加其當(dāng)前的任期，并過渡到Candidate狀態(tài)。然后，它為自己投票，并與集群中的每個其他服務(wù)器并行地發(fā)出RquestVote RPC請求。一個Candidate繼續(xù)這個狀態(tài)，直到以下三件事發(fā)生：(a)它贏得選舉，(b)另一個服務(wù)器確立自己作為Leader，或者(c)選舉超時，沒有獲勝者。這些結(jié)果將在下文的段落中分別進行討論。
如果Candidate在同一term內(nèi)獲得來自整個集群中大多數(shù)服務(wù)器的投票，他將贏得選舉。每個服務(wù)器將在給定任期內(nèi)以先到先得的基礎(chǔ)上最多投票一名候選人（注：第3.6節(jié)增加了對投票的額外限制）。多數(shù)派的選舉規(guī)則確保最多有一個Candidate可以贏得特定term的選舉（圖3.2中的選舉安全屬性）。一旦一個Candidate贏得了一次選舉，它就會成為Leader。然后，它向所有其他服務(wù)器發(fā)送心跳消息（通過AppendEntries RPC），以通知其勝選消息并防止新的選舉。
在等待投票時，Candidate可能會從另一個服務(wù)器接收到一個 AppendEntries RPC消息聲稱自己是Leader。如果Leader的term(包括在其RPC中)至少與Candidate的當(dāng)前任期相同，那么Candidate就會承認(rèn)Leader是合法的，并返回到Follower狀態(tài)。如果RPC中的term小于Candidate的當(dāng)前term，則Candidate拒絕RPC并繼續(xù)處于候選狀態(tài)。
第三個可能的結(jié)果是，Candidate既不獲勝也不失?。喝绻S多Follower同時成為Candidate，選票可以被分割，因此沒有Candidate獲得多數(shù)選票。當(dāng)這種情況發(fā)生時，每位Candidate將超時，通過增加term和啟動另一輪請求投票，開始新的選舉。然而，如果沒有額外的措施，分裂的投票可能會無限期地重復(fù)。
Raft使用隨機選舉超時，以確保分裂選票罕見，并迅速解決。為了防止投票分裂，首先是從一個固定的時間間隔（例如，150-300毫秒）中隨機選擇選舉超時。這將使服務(wù)器分散，以便在大多數(shù)情況下，只有一個服務(wù)器將超時；它贏得選舉，并在任何其他服務(wù)器超時之前發(fā)送心跳。同樣的機制也用于處理分裂投票。每位Candidate在選舉開始時重新開始其隨機選舉的超時，并等待超時后開始下一次選舉；這降低了新選舉中再次分裂投票的可能性。第9章表明，這種方法可以迅速選出一Leader。
選舉就是可理解性指導(dǎo)我們選擇的一個例子。最初我們計劃使用一個排名系統(tǒng)：每個Candidate被分配一個唯一的排名，用于在相互競爭的Candidate之間進行選擇。如果一個Candidate發(fā)現(xiàn)了另一個排名較高的Candidate，它將回到追Follower，這樣排名較高的Candidate就可以更容易地贏得下次選舉。我們發(fā)現(xiàn)，這種方法圍繞可用性產(chǎn)生了微妙的問題（如果排名較高的服務(wù)器失敗，排名較低的服務(wù)器可能需要超時并再次成為Candidate，但如果這樣做得過早，它可以重置選擇Leader的進度）。我們對算法進行了幾次調(diào)整，但每次調(diào)整后都出現(xiàn)了新的特殊情況。最終，我們得出結(jié)論，隨機重試方法更明顯和更容易理解。
這里用下面的流程圖說明一下Leader Election的流程，一遍更加直觀的說明Leader Election流程。首先要說明的是，發(fā)起選舉的服務(wù)器起始狀態(tài)是Follower，當(dāng)其在預(yù)設(shè)的時間間隔內(nèi)未收到來自Leader的心跳（也就是AppendEntries RPC請求），那么其就編程Candidate并發(fā)起新的選舉。這里有一個問題，如果是這個Follower服務(wù)器與Leader的網(wǎng)絡(luò)通信斷開/延遲時間過長，那么這個服務(wù)器也會執(zhí)行重新選舉的操作?？梢钥紤]一下，如果僅僅是Leader和這個Follower之間的網(wǎng)絡(luò)通信出現(xiàn)問題，其它Leader和其它Follower之間以及所有Follower之間的網(wǎng)絡(luò)通信正常，這樣也會導(dǎo)致重新選舉，而這樣又會導(dǎo)致新的Leader和當(dāng)前Leader（當(dāng)前Leader后面將變?yōu)镕ollower）之間的網(wǎng)絡(luò)不通，這里存在一個問題：老的Leader會不會發(fā)起新的Leader選舉請求？就算老的Leader不會發(fā)起新的選舉，那這個操作其實就是互換了一下Leader和Follower，但是要存在多余的Log復(fù)制操作，其實沒有必要。（本人暫時還沒有想到好的解決方法，看看后面的文章有沒有回答這個問題）。
還需要說的是，這里Candidate進行選舉時可能存在分裂的問題，Raft使用了隨機超時的方法降低選舉分裂概率，這個方法不一定是最好的，但是是比較容易理解的，這也服務(wù)Raft算法的設(shè)計目標(biāo)（可理解性至上）。
