對數據順序達成壹致***識是很多***識算法要解決的本質問題
Fabic的pbft算法實現
現階段的***識算法主要可以分成三大類：公鏈，聯盟鏈和私鏈
私鏈，所有節點可信
聯盟鏈，存在對等的不信任節點
私鏈：私鏈的***識算法即區塊鏈這個概念還沒普及時的傳統分布式系統裏的***識算法，比如 zookeeper 的 zab 協議，就是類 paxos 算法的壹種。私鏈的適用環境壹般是不考慮集群中存在作惡節點，只考慮因為系統或者網絡原因導致的故障節點。
聯盟鏈：聯盟鏈中，經典的代表項目是 Hyperledger 組織下的 Fabric 項目， Fabric0.6 版本使用的就是 pbft 算法。聯盟鏈的適用環境除了需要考慮集群中存在故障節點，還需要考慮集群中存在作惡節點。對於聯盟鏈，每個新加入的節點都是需要驗證和審核的。
公鏈：公鏈不僅需要考慮網絡中存在故障節點，還需要考慮作惡節點，這壹點和聯盟鏈是類似的。和聯盟鏈最大的區別就是，公鏈中的節點可以很自由的加入或者退出，不需要嚴格的驗證和審核。
在公有鏈中用的最多的是pow算法和pos算法，這些算法都是參與者的利益直接相關，通過利益來制約節點誠實的工作，解決分布式系統中的拜占庭問題。拜占庭容錯算法是壹種狀態機副本復制算法，通過節點間的多輪消息傳遞，網絡內的所有誠實節點就可以達成壹致的***識。
使用拜占庭容錯算法不需要發行加密貨幣，但是只能用於私有鏈或者聯盟鏈，需要對節點的加入進行權限控制；不能用於公有鏈，因為公有鏈中所有節點都可以隨意加入退出，無法抵擋女巫攻擊（sybil attack）
raft 算法包含三種角色，分別是：跟隨者（ follower ），候選人（candidate ）和領導者（ leader ）。集群中的壹個節點在某壹時刻只能是這三種狀態的其中壹種，這三種角色是可以隨著時間和條件的變化而互相轉換的。
raft 算法主要有兩個過程：壹個過程是領導者選舉，另壹個過程是日誌復制，其中日誌復制過程會分記錄日誌和提交數據兩個階段。raft 算法支持最大的容錯故障節點是（N-1）/2，其中 N 為 集群中總的節點數量。
國外有壹個動畫介紹raft算法介紹的很透徹，鏈接地址為： /raft/ 。這個動畫主要包含三部分內容，第壹部分介紹簡單版的領導者選舉和日誌復制的過程，第二部分內容介紹詳細版的領導者選舉和日誌復制的過程，第三部分內容介紹的是如果遇到網絡分區（腦裂），raft 算法是如何恢復網絡壹致的。
pbft 算法的提出主要是為了解決拜占庭將軍問題
要讓這個問題有解，有壹個 十分重要的前提 ，那就是 信道必須是可靠的 。如果信道不能保證可靠，那麽拜占庭問題無解。關於信道可靠問題，會引出兩軍問題。兩軍問題的結論是，在壹個不可靠的通信鏈路上試圖通過通信以達成壹致是基本不可能或者十分困難的。
拜占庭將軍問題最早是由 Leslie Lamport 與另外兩人在 1982 年發表的論文《The Byzantine Generals Problem 》提出的， 他證明了在將軍總數大於 3f ，背叛者為f 或者更少時，忠誠的將軍可以達成命令上的壹致，即 3f+1<=n 。算法復雜度為 o（n^(f+1)) 。而 Miguel Castro (卡斯特羅)和 Barbara Liskov （利斯科夫）在1999年發表的論文《 Practical Byzantine Fault Tolerance 》中首次提出 pbft 算法，該算法容錯數量也滿足 3f+1<=n ，算法復雜度為 o（n^2）。
首先我們先來思考壹個問題，為什麽 pbft 算法的最大容錯節點數量是（n-1）/3，而 raft 算法的最大容錯節點數量是（n-1）/2 ？
對於raft算法，raft算法的的容錯只支持容錯故障節點，不支持容錯作惡節點。什麽是故障節點呢？就是節點因為系統繁忙、宕機或者網絡問題等其它異常情況導致的無響應，出現這種情況的節點就是故障節點。那什麽是作惡節點呢？作惡節點除了可以故意對集群的其它節點的請求無響應之外，還可以故意發送錯誤的數據，或者給不同的其它節點發送不同的數據，使整個集群的節點最終無法達成***識，這種節點就是作惡節點。
raft 算法只支持容錯故障節點，假設集群總節點數為n，故障節點為 f ，根據小數服從多數的原則，集群裏正常節點只需要比 f 個節點再多壹個節點，即 f+1 個節點，正確節點的數量就會比故障節點數量多，那麽集群就能達成***識。因此 raft 算法支持的最大容錯節點數量是（n-1）/2。
對於 pbft 算法，因為 pbft 算法的除了需要支持容錯故障節點之外，還需要支持容錯作惡節點。假設集群節點數為 N，有問題的節點為 f。有問題的節點中，可以既是故障節點，也可以是作惡節點，或者只是故障節點或者只是作惡節點。那麽會產生以下兩種極端情況：
第壹種情況，f 個有問題節點既是故障節點，又是作惡節點，那麽根據小數服從多數的原則，集群裏正常節點只需要比f個節點再多壹個節點，即 f+1 個節點，確節點的數量就會比故障節點數量多，那麽集群就能達成***識。也就是說這種情況支持的最大容錯節點數量是 （n-1）/2。
第二種情況，故障節點和作惡節點都是不同的節點。那麽就會有 f 個問題節點和 f 個故障節點，當發現節點是問題節點後，會被集群排除在外，剩下 f 個故障節點，那麽根據小數服從多數的原則，集群裏正常節點只需要比f個節點再多壹個節點，即 f+1 個節點，確節點的數量就會比故障節點數量多，那麽集群就能達成***識。所以，所有類型的節點數量加起來就是 f+1 個正確節點，f個故障節點和f個問題節點，即 3f+1=n。
結合上述兩種情況，因此 pbft 算法支持的最大容錯節點數量是（n-1）/3
pbft 算法的基本流程主要有以下四步：
客戶端發送請求給主節點
主節點廣播請求給其它節點，節點執行 pbft 算法的三階段***識流程。
節點處理完三階段流程後，返回消息給客戶端。
客戶端收到來自 f+1 個節點的相同消息後，代表***識已經正確完成。
為什麽收到 f+1 個節點的相同消息後就代表***識已經正確完成？從上壹小節的推導裏可知，無論是最好的情況還是最壞的情況，如果客戶端收到 f+1 個節點的相同消息，那麽就代表有足夠多的正確節點已全部達成***識並處理完畢了。
3.算法核心三階段流程
算法的核心三個階段分別是 pre-prepare 階段（預準備階段），prepare 階段（準備階段）， commit 階段（提交階段）
流程的對比上，對於 leader 選舉這塊， raft 算法本質是誰快誰當選，而 pbft 算法是按編號依次輪流做主節點。對於***識過程和重選 leader 機制這塊，為了更形象的描述這兩個算法，接下來會把 raft 和 pbft 的***識過程比喻成壹個團隊是如何執行命令的過程，從這個角度去理解 raft 算法和 pbft 的區別。
壹個團隊壹定會有壹個老大和普通成員。對於 raft 算法，***識過程就是：只要老大還沒掛，老大說什麽，我們（團隊普通成員）就做什麽，堅決執行。那什麽時候重新老大呢？只有當老大掛了才重選老大，不然生是老大的人，死是老大的鬼。
對於 pbft 算法，***識過程就是：老大向我發送命令時，當我認為老大的命令是有問題時，我會拒絕執行。就算我認為老大的命令是對的，我還會問下團隊的其它成員老大的命令是否是對的，只有大多數人 （2f+1） 都認為老大的命令是對的時候，我才會去執行命令。那什麽時候重選老大呢？老大掛了當然要重選，如果大多數人都認為老大不稱職或者有問題時，我們也會重新選擇老大。
四、結語
raft 算法和 pbft 算法是私鏈和聯盟鏈中經典的***識算法，本文主要介紹了 raft 和 pbft 算法的流程和區別。 raft 和 pbft 算法有兩點根本區別：
raft 算法從節點不會拒絕主節點的請求，而 pbft 算法從節點在某些情況下會拒絕主節點的請求 ;
raft 算法只能容錯故障節點，並且最大容錯節點數為 （n-1）/2 ，而 pbft 算法能容錯故障節點和作惡節點，最大容錯節點數為 （n-1）/3 。
pbft算法是通過投票來達成***識，可以很好的解決包括分叉等問題的同時提升效率。但僅僅比較適合於聯盟鏈私有鏈，因為兩兩節點之間通信量是O(n^2)（通過優化可以減少通信量），壹般來說不能應用於超過100個節點。
pbft有解的前提是 信道必須是可靠的 ，存在的問題是 可擴展性（scalability）差
部分來自： /kojhliang/article/details/80270223
區塊鏈在設計上就是為了BFT