raft是一個共識算法（consensus algorithm），所謂共識，就是多個節點對某個事情達成一致的看法，即使是在部分節點故障、網絡延時、網絡分割的情況下。這些年最為火熱的加密貨幣（比特幣、區塊鏈）就需要共識算法，而在分布式系統中，共識算法更多用于提高系統的容錯性，比如分布式存儲中的復制集（replication），在帶著問題學習分布式系統之中心化復制集一文中介紹了中心化復制集的相關知識。raft協議就是一種leader-based的共識算法，與之相應的是leaderless的共識算法。 為了達到易于理解的目標，raft做了很多努力，其中最主要是兩件事情： 問題分解 狀態簡化 ?? 問題分解是將"復制集中節點一致性"這個復雜的問題劃分為數個可以被獨立解釋、理解、解決的子問題。在raft，子問題包括，leader election， log replication，safety，membership changes。而狀態簡化更好理解，就是對算法做出一些限制，減少需要考慮的狀態數，使得算法更加清晰，更少的不確定性（比如，保證新選舉出來的leader會包含所有commited log entry） raft會先選舉出leader，leader完全負責replicated log的管理。leader負責接受所有客戶端更新請求，然后復制到follower節點，并在“安全”的時候執行這些請求。如果leader故障，followes會重新選舉出新的leader。所有節點啟動時都是follower狀態；在一段時間內如果沒有收到來自leader的心跳，從follower切換到candidate，發起選舉；如果收到majority的造成票（含自己的一票）則切換到leader狀態；如果發現其他節點比自己更新，則主動切換到follower。 ?? 總之，系統中最多只有一個leader，如果在一段時間里發現沒有leader，則大家通過選舉-投票選出leader。leader會不停的給follower發心跳消息，表明自己的存活狀態。如果leader故障，那么follower會轉換成candidate，重新選出leader。 如果follower在election timeout內沒有收到來自leader的心跳，（也許此時還沒有選出leader，大家都在等；也許leader掛了；也許只是leader與該follower之間網絡故障），則會主動發起選舉。步驟如下： 增加節點本地的 current term ，切換到candidate狀態 投自己一票 并行給其他節點發送 RequestVote RPCs 等待其他節點的回復 ?? 在這個過程中，根據來自其他節點的消息，可能出現三種結果 收到majority的投票（含自己的一票），則贏得選舉，成為leader 被告知別人已當選，那么自行切換到follower 一段時間內沒有收到majority投票，則保持candidate狀態，重新發出選舉 ?? 第一種情況，贏得了選舉之后，新的leader會立刻給所有節點發消息，廣而告之，避免其余節點觸發新的選舉。在這里，先回到投票者的視角，投票者如何決定是否給一個選舉請求投票呢，有以下約束： 在任一任期內，單個節點最多只能投一票 候選人知道的信息不能比自己的少（這一部分，后面介紹log replication和safety的時候會詳細介紹） first-come-first-served 先來先得 ?? 第二種情況，比如有三個節點A B C。A B同時發起選舉，而A的選舉消息先到達C，C給A投了一票，當B的消息到達C時，已經不能滿足上面提到的第一個約束，即C不會給B投票，而A和B顯然都不會給對方投票。A勝出之后，會給B,C發心跳消息，節點B發現節點A的term不低于自己的term，知道有已經有Leader了，于是轉換成follower。 第三種情況，沒有任何節點獲得majority投票，比如下圖這種情況：  ?? 總共有四個節點，Node C、Node D同時成為了candidate，進入了term 4，但Node A投了NodeD一票，NodeB投了Node C一票，這就出現了平票 split vote的情況。這個時候大家都在等啊等，直到超時后重新發起選舉。如果出現平票的情況，那么就延長了系統不可用的時間（沒有leader是不能處理客戶端寫請求的），因此raft引入了randomized election timeouts來盡量避免平票情況。同時，leader-based 共識算法中，節點的數目都是奇數個，盡量保證majority的出現。