因為網上大量的文章已經詳細介紹了raft算法，所以本部分只簡單說明算法的基本原理和流程。Raft算法包括三個角色:跟隨者、候選者和領導者。集群中的壹個節點在某壹時刻只能是這三種狀態中的壹種，並且這三種角色可以隨著時間和條件的變化而轉換。
Raft算法主要有兩個過程:壹是領袖選舉，二是日誌復制，其中日誌復制過程會分為記錄日誌和提交數據兩個階段。raft算法支持的最大容錯節點數為(N-1)/2，其中N為集群中的節點總數。
國外有個動畫把raft算法介紹的很透徹，鏈接地址在這裏【1】。這部動畫主要包括三個部分。第壹部分介紹了簡單版的首領選舉和日誌復制的流程，第二部分介紹了詳細版的首領選舉和日誌復制的流程，第三部分介紹了raft算法在遇到網絡分區(腦裂)的情況下如何恢復網絡壹致性。有興趣的朋友可以結合這個動畫更好的理解raft算法。
2.。pbft算法
Pbft算法主要用於解決拜占庭問題。拜占庭將軍的問題是什麽？拜占庭位於土耳其伊斯坦布爾，是古代東羅馬帝國的首都。拜占庭羅馬帝國疆域遼闊。為了達到防禦的目的，每個封地都駐紮了壹支由將軍指揮的軍隊。各軍相距甚遠，將領之間的消息只能通過信使傳遞。戰爭期間，拜占庭軍隊中的所有將領都必須達成共識，決定是否有勝算，才能進攻敵方陣營。但軍隊中可能有漢奸和敵特，將軍的決定會影響將軍們的共識。鑒於壹些將領是眾所周知的叛徒，其他忠誠的將領如何達成壹致？這就是拜占庭將軍的問題。
下圖列出了raft算法和pbft算法在適用環境、通信復雜度、最大容錯節點數和進程上的對比。
兩種算法的適用環境和最大容錯節點數在上壹節已經介紹過了，這裏不再贅述。至於算法的通信復雜度，為什麽raft是o(n)，pbft是O(n ^ 2)？這裏主要考慮算法的* * *知識過程。
對於raft算法，知識的核心過程是日誌復制的過程，分為兩個階段，壹個是日誌記錄，壹個是數據提交。兩個過程都只需要領導者向跟隨者節點發送消息，跟隨者節點向領導者節點返回消息，跟隨者節點之間不需要通信。因此，如果集群中的節點總數為n，則日誌階段的通信次數為n-1，數據提交階段的通信次數為n-1，總通信次數為2n-2，因此raft算法的復雜度為O(n)。
對於pbft算法，核心過程有三個階段，分別是預準備、準備和提交。對於預準備階段，主節點只需要向其他節點廣播預準備消息，因此通信頻率為n-1；對於準備階段，如果每個節點同意請求，則需要再次向其他節點廣播parepare消息，所以總通信次數為n (n-1)，即n ^ 2-n；對於提交階段，如果每個節點達到準備狀態，需要向其他節點廣播提交消息，那麽總的通信次數也是n (n-1)，即n ^ 2-n，因此總的通信次數是(n-1)+(n ^ 2-n)+(n ^ 2-n)，即2n ^ 2-n-1，所以pbft算法的復雜度是O (N2)。
對比流程，對於領袖選舉，raft算法的本質是誰選得快，而pbft算法是根據人數輪流做主節點。對於* * *知識過程和重選領袖機制，為了更形象地描述這兩種算法，我們將raft和pbft的* * *知識過程比作壹個團隊如何執行命令的過程，從這個角度來理解raft和pbft的區別。
壹個團隊必須有壹個老板和普通成員。對於raft算法，* * *知識的過程是:只要老板還活著，我們(團隊的普通成員)就會按照老板說的去做，堅決執行。那妳什麽時候再當老板？只有老板死了，才重新選老板，否則當老板的人會死老板的鬼。
對於pbft算法，* * *知識的過程是:當老板給我發命令的時候，當我認為老板的命令有問題的時候，我會拒絕執行。即使我覺得老板的命令是對的，我也會問團隊其他成員老板的命令是不是對的。只有大部分人(2f+1)認為老板的命令是對的，我才會執行命令。老板什麽時候改選？當然，如果老板死了，我們必須重新選舉。如果大多數人認為老板不稱職或者有問題，我們會重新選舉老板。