摘要：區塊鏈技術中，共識算法是其中核心的一個組成部分，本文將詳細闡述私鏈的raft算法和聯盟鏈的pbft算法，從算法的基本流程切入，分析兩者的區別。

區塊鏈技術中，共識算法是其中核心的一個組成部分。首先我們來思考一個問題：什麼是共識？對於現實世界，共識就是一群人對一件或者多件事情達成一致的看法或者協議。那麼在計算機世界當中，共識是什麼呢？

我的理解包含兩個層面，第一個層面是點的層面，即多個節點對某個數據達成一致共識。第二個層面是線的層面，即多個節點對多個數據的順序達成一致共識。這裡的節點可以是任意的計算機設備，比如 pc電腦，筆記本，手機，路由器等，這裡的數據可以是交易數據，狀態數據等。其中對數據順序達成一致共識是很多共識算法要解決的本質問題。

常見的共識算法都有哪些呢？現階段的共識算法主要可以分成三大類：公鏈，聯盟鏈和私鏈。下面描述這三種類別的特徵：

• 私鏈：私鏈的共識算法即區塊鏈這個概念還沒普及時的傳統分佈式系統裡的共識算法，比如 zookeeper 的 zab 協議，就是類 paxos 算法的一種。私鏈的適用環境一般是不考慮集群中存在作惡節點，只考慮因為系統或者網絡原因導致的故障節點。

• 聯盟鏈：聯盟鏈中，經典的代表項目是 Hyperledger 組織下的 Fabric 項目， Fabric0.6 版本使用的就是 pbft 算法。聯盟鏈的適用環境除了需要考慮集群中存在故障節點，還需要考慮集群中存在作惡節點。對於聯盟鏈，每個新加入的節點都是需要驗證和審核的。

• 公鏈：公鏈不斷需要考慮網絡中存在故障節點，還需要考慮作惡節點，這一點和聯盟鏈是類似的。和聯盟鏈最大的區別就是，公鏈中的節點可以很自由的加入或者退出，不需要嚴格的驗證和審核。

本文接下來將會主要闡述私鏈的raft算法和聯盟鏈的 pbft 算法，以及它們的區別和對比。

一、raft算法

因為網上已經有大量文章對raft算法進行過詳細的介紹，因此這部分只會簡單的闡述算法的基本原理和流程。raft 算法包含三種角色，分別是：跟隨者（ follower ），候選人（ candidate ）和領導者（ leader ）。集群中的一個節點在某一時刻只能是這三種狀態的其中一種，這三種角色是可以隨著時間和條件的變化而互相轉換的。

raft 算法主要有兩個過程：一個過程是領導者選舉，另一個過程是日誌複製，其中日誌複製過程會分記錄日誌和提交數據兩個階段。raft 算法支持最大的容錯故障節點是（N-1）/2，其中 N 為 集群中總的節點數量。

國外有一個動畫介紹raft算法介紹的很透徹，鏈接地址為：http://thesecretlivesofdata.com/raft/。這個動畫主要包含三部分內容，第一部分介紹簡單版的領導者選舉和日誌複製的過程，第二部分內容介紹詳細版的領導者選舉和日誌複製的過程，第三部分內容介紹的是如果遇到網絡分區（腦裂），raft 算法是如何恢復網絡一致的。有興趣的朋友可以結合這個動畫來更好的理解raft算法。

二、 pbft算法

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 的算法介紹基本上是基於 liskov 在 1999 年發表的論文《 Practical Byzantine Fault Tolerance 》來進行解釋的。當前網上介紹 pbft 的中文文章不算太多，基本上只有那幾篇，並且感覺有些關鍵點解釋得不夠清晰，因此接下來會詳細描述下pbft算法的過程和原理。

1.raft和pbft的最大容錯節點數

首先我們先來思考一個問題，為什麼 pbft 算法的最大容錯節點數量是（n-1）/3，而 raft 算法的最大容錯節點數量是（n-1）/2 ？

對於 raft 算法，raft 算法的的容錯只支持容錯故障節點，不支持容錯作惡節點。什麼是故障節點呢？就是節點因為系統繁忙、宕機或者網絡問題等其它異常情況導致的無響應，出現這種情況的節點就是故障節點。那什麼是作惡節點呢？作惡節點除了可以故意對集群的其它節點的請求無響應之外，還可以故意發送錯誤的數據，或者給不同的其它節點發送不同的數據，使整個集群的節點最終無法達成共識，這種節點就是作惡節點。

raft 算法只支持容錯故障節點，假設集群總節點數為n，故障節點為 f ，根據小數服從多數的原則，集群裡正常節點只需要比 f 個節點再多一個節點，即 f+1 個節點，正確節點的數量就會比故障節點數量多，那麼集群就能達成共識。因此 raft 算法支持的最大容錯節點數量是（n-1）/2。

對於 pbft 算法，因為 pbft 算法的除了需要支持容錯故障節點之外，還需要支持容錯作惡節點。假設集群節點數為 N，有問題的節點為 f。有問題的節點中，可以既是故障節點，也可以是作惡節點，或者只是故障節點或者只是作惡節點。那麼會產生以下兩種極端情況：

1. 第一種情況，f 個有問題節點既是故障節點，又是作惡節點，那麼根據小數服從多數的原則，集群裡正常節點只需要比f個節點再多一個節點，即 f+1 個節點，確節點的數量就會比故障節點數量多，那麼集群就能達成共識。也就是說這種情況支持的最大容錯節點數量是 （n-1）/2。

2. 第二種情況，故障節點和作惡節點都是不同的節點。那麼就會有 f 個問題節點和 f 個故障節點，當發現節點是問題節點後，會被集群排除在外，剩下 f 個故障節點，那麼根據小數服從多數的原則，集群裡正常節點只需要比f個節點再多一個節點，即 f+1 個節點，確節點的數量就會比故障節點數量多，那麼集群就能達成共識。所以，所有類型的節點數量加起來就是 f+1 個正確節點，f個故障節點和f個問題節點，即 3f+1=n。

結合上述兩種情況，因此 pbft 算法支持的最大容錯節點數量是（n-1）/3。下圖展示了論文裡證明 pbft 算法為什麼 3f+1<=n的一段原文，以及根據原文提到的兩種情況對應的示意圖。

3f+1<=n 這個結論在 pbft 算法的流程中會大量使用到，因此在介紹 pbft 算法流程前先解釋下這個推論。

2.算法基本流程

pbft 算法的基本流程主要有以下四步：

1. 客戶端發送請求給主節點

2. 主節點廣播請求給其它節點，節點執行 pbft 算法的三階段共識流程。

3. 節點處理完三階段流程後，返回消息給客戶端。

4. 客戶端收到來自 f+1 個節點的相同消息後，代表共識已經正確完成。

為什麼收到 f+1 個節點的相同消息後就代表共識已經正確完成？從上一小節的推導裡可知，無論是最好的情況還是最壞的情況，如果客戶端收到 f+1 個節點的相同消息，那麼就代表有足夠多的正確節點已全部達成共識並處理完畢了。

3.算法核心三階段流程

下面介紹 pbft 算法的核心三階段流程，如下圖所示：

算法的核心三個階段分別是 pre-prepare 階段（預準備階段），prepare 階段（準備階段）， commit 階段（提交階段）。圖中的C代表客戶端，0，1，2，3 代表節點的編號，打叉的3代表可能是故障節點或者是問題節點，這裡表現的行為就是對其它節點的請求無響應。0 是主節點。整個過程大致是如下：

首先，客戶端向主節點發起請求，主節點 0 收到客戶端請求，會向其它節點發送 pre-prepare 消息，其它節點就收到了pre-prepare 消息，就開始了這個核心三階段共識過程了。

Pre-prepare 階段：節點收到 pre-prepare 消息後，會有兩種選擇，一種是接受，一種是不接受。什麼時候才不接受主節點發來的 pre-prepare 消息呢？一種典型的情況就是如果一個節點接受到了一條 pre-pre 消息，消息裡的 v 和 n 在之前收到裡的消息是曾經出現過的，但是 d 和 m 卻和之前的消息不一致，或者請求編號不在高低水位之間（高低水位的概念在下文會進行解釋），這時候就會拒絕請求。拒絕的邏輯就是主節點不會發送兩條具有相同的 v 和 n ，但 d 和 m 卻不同的消息。

Prepare 階段：節點同意請求後會向其它節點發送 prepare 消息。這裡要注意一點，同一時刻不是隻有一個節點在進行這個過程，可能有 n 個節點也在進行這個過程。因此節點是有可能收到其它節點發送的 prepare 消息的。在一定時間範圍內，如果收到超過 2f 個不同節點的 prepare 消息，就代表 prepare 階段已經完成。

Commit 階段：於是進入 commit 階段。向其它節點廣播 commit 消息，同理，這個過程可能是有 n 個節點也在進行的。因此可能會收到其它節點發過來的 commit 消息，當收到 2f+1 個 commit 消息後（包括自己），代表大多數節點已經進入 commit 階段，這一階段已經達成共識，於是節點就會執行請求，寫入數據。

處理完畢後，節點會返回消息給客戶端，這就是 pbft 算法的全部流程。為了更清晰的展現 這個過程和一些細節，下面以流程圖來表示這個過程：

註解：

V：當前視圖的編號。視圖的編號是什麼意思呢？比如當前主節點為 A，視圖編號為 1，如果主節點換成 B，那麼視圖編號就為 2，這個概念和 raft 的 term 任期是很類似的。

N：當前請求的編號。主節點收到客戶端的每個請求都以一個編號來標記。

M：消息的內容

d或D（m）：消息內容的摘要

i： 節點的編號

4.高低水位

什麼是 checkpoint 呢？ checkpoint 就是當前節點處理的最新請求序號。前文已經提到主節點收到請求是會給請求記錄編號的。比如一個節點正在共識的一個請求編號是101，那麼對於這個節點，它的 checkpoint 就是101.

那什麼是 stable checkpoint （穩定檢查點）呢？stable checkpoint 就是大部分節點 （2f+1） 已經共識完成的最大請求序號。比如系統有 4 個節點，三個節點都已經共識完了的請求編號是 213 ，那麼這個 213 就是 stable checkpoint 了。

那設置這個 stable checkpoint 有什麼作用呢？最大的目的就是減少內存的佔用。因為每個節點應該記錄下之前曾經共識過什麼請求，但如果一直記錄下去，數據會越來越大，所以應該有一個機制來實現對數據的刪除。那怎麼刪呢？很簡單，比如現在的穩定檢查點是 213 ，那麼代表 213 號之前的記錄已經共識過的了，所以之前的記錄就可以刪掉了。

那什麼是高低水位呢？下面以一個示意圖來進行解釋：

圖中A節點的當前請求編號是 1039，即checkpoint為1039，B節點的 checkpoint 為1133。當前系統 stable checkpoint 為 1034 。那麼1034這個編號就是低水位，而高水位 H=低水位 h+L ，其中L是可以設定的數值。因此圖中系統的高水位為 1034+100=1134。

舉個例子：如果 B 當前的 checkpoint 已經為 1034，而A的 checkpoint 還是 1039 ，假如有新請求給 B 處理時，B會選擇等待，等到 A 節點也處理到和 B 差不多的請求編號時，比如 A 也處理到 1112 了，這時會有一個機制更新所有節點的 stabel checkpoint ，比如可以把 stabel checkpoint 設置成 1100 ，於是 B 又可以處理新的請求了，如果 L 保持100 不變，這時的高水位就會變成 1100+100=1200 了。

5.ViewChange事件

當主節點掛了（超時無響應）或者從節點集體認為主節點是問題節點時，就會觸發 ViewChange 事件， ViewChange 完成後，視圖編號將會加 1 。下圖展示 ViewChange 的三個階段流程：

如圖所示， viewchange 會有三個階段，分別是 view-change ， view-change-ack 和 new-view 階段。從節點認為主節點有問題時，會向其它節點發送 view-change 消息，當前存活的節點編號最小的節點將成為新的主節點。當新的主節點收到 2f 個其它節點的 view-change 消息，則證明有足夠多人的節點認為主節點有問題，於是就會向其它節點廣播 New-view 消息。注意：從節點不會發起 new-view 事件。對於主節點，發送 new-view 消息後會繼續執行上個視圖未處理完的請求，從 pre-prepare 階段開始。其它節點驗證 new-view 消息通過後，就會處理主節點發來的 pre-prepare 消息，這時執行的過程就是前面描述的 pbft 過程。到這時，正式進入 v+1 （視圖編號加1）的時代了。

為了更清晰的展現 ViewChange 這個過程和一些細節，下面以流程圖來表示這個過程：

上圖裡紅色字體部分的 O 集合會包含哪些 pre-prepare 消息呢？假設 O 集合裡消息的編號範圍：（min～max），則 Min 為 V 集合最小的 stable checkpoint ， Max 為 V 集合中最大序號的 prepare 消息。最後一步執行 O 集合裡的 pre-preapare 消息，每條消息會有兩種情況: 如果 max-min>0，則產生消息 ；如果 max-min=0，則產生消息 。

三、raft和pbft的對比

下圖列出了 raft 算法和 pbft 算法在適用環境，通信複雜度，最大容錯節點數和流程上的對比。

關於兩個算法的適用環境和最大容錯節點數，前文已經做過闡述，這裡不再細說。而對於算法通信複雜度，為什麼 raft 是 o（n），而 pbft 是 o（n^2）呢？這裡主要考慮算法的共識過程。

對於 raft 算法，核心共識過程是日誌複製這個過程，這個過程分兩個階段，一個是日誌記錄，一個是提交數據。兩個過程都只需要領導者發送消息給跟隨者節點，跟隨者節點返回消息給領導者節點即可完成，跟隨者節點之間是無需溝通的。所以如果集群總節點數為 n，對於日誌記錄階段，通信次數為 n-1，對於提交數據階段，通信次數也為 n-1，總通信次數為 2n-2，因此raft算法複雜度為O（n）。

對於 pbft 算法，核心過程有三個階段，分別是 pre-prepare （預準備）階段，prepare （準備）階段和 commit （提交）階段。對於 pre-prepare 階段，主節點廣播 pre-prepare 消息給其它節點即可，因此通信次數為 n-1 ；對於 prepare 階段，每個節點如果同意請求後，都需要向其它節點再 廣播 parepare 消息，所以總的通信次數為 n*（n-1），即 n^2-n ；對於 commit 階段，每個節點如果達到 prepared 狀態後，都需要向其它節點廣播 commit 消息，所以總的通信次數也為 n*（n-1） ，即 n^2-n 。所以總通信次數為 （n-1）+（n^2-n）+（n^2-n） ，即 2n^2-n-1 ，因此pbft算法複雜度為 O（n^2） 。

流程的對比上，對於 leader 選舉這塊， raft 算法本質是誰快誰當選，而 pbft 算法是按編號依次輪流做主節點。對於共識過程和重選 leader 機制這塊，為了更形象的描述這兩個算法，接下來會把 raft 和 pbft 的共識過程比喻成一個團隊是如何執行命令的過程，從這個角度去理解 raft 算法和 pbft 的區別。

一個團隊一定會有一個老大和普通成員。對於 raft 算法，共識過程就是：只要老大還沒掛，老大說什麼，我們（團隊普通成員）就做什麼，堅決執行。那什麼時候重新老大呢？只有當老大掛了才重選老大，不然生是老大的人，死是老大的鬼。

對於 pbft 算法，共識過程就是：老大向我發送命令時，當我認為老大的命令是有問題時，我會拒絕執行。就算我認為老大的命令是對的，我還會問下團隊的其它成員老大的命令是否是對的，只有大多數人 （2f+1） 都認為老大的命令是對的時候，我才會去執行命令。那什麼時候重選老大呢？老大掛了當然要重選，如果大多數人都認為老大不稱職或者有問題時，我們也會重新選擇老大。

四、結語

raft 算法和 pbft 算法是私鏈和聯盟鏈中經典的共識算法，本文主要介紹了 raft 和 pbft 算法的流程和區別。 raft 和 pbft 算法有兩點根本區別：

1. raft 算法從節點不會拒絕主節點的請求，而 pbft 算法從節點在某些情況下會拒絕主節點的請求 ;

2. raft 算法只能容錯故障節點，並且最大容錯節點數為 （n-1）/2 ，而 pbft 算法能容錯故障節點和作惡節點，最大容錯節點數為 （n-1）/3 。

本文沒有涉及算法正確性和收斂性的證明，從算法設計的角度來講，是需要做這兩方面工作的。

梁敏鴻，美圖區塊鏈架構師，專注於區塊鏈技術研究與產品應用落地。

閱讀更多 美圖技術團隊 的文章

關鍵字: 共識 通信 筆記本電腦