概述

Practical Byzantine Fault Tolerance： PBFT，是聯(lián)盟幣的共識算法的基礎(chǔ)。實現(xiàn)了在有限個節(jié)點的情況下的拜占庭問題，有3f+1的容錯性，并同時保證一定的性能。

容錯率

• raft算法的的容錯只支持容錯故障節(jié)點，不支持容錯作惡節(jié)點，所以容錯率高，過半節(jié)點正常即可
• PBFT算法可以容忍小于1/3個無效或者惡意節(jié)點
  作惡節(jié)點：除了可以故意對集群的其它節(jié)點的請求無響應(yīng)之外，還可以故意發(fā)送錯誤的數(shù)據(jù)，或者給不同的其它節(jié)點發(fā)送不同的數(shù)據(jù)，使整個集群的節(jié)點最終無法達成共識，這種節(jié)點就是作惡節(jié)點。

角色

Primary節(jié)點和普通節(jié)點，PBFT系統(tǒng)的Primary是輪流當(dāng)選的，這和zab、raft不一樣

• 主節(jié)點 p = v mod |R|
• p：主節(jié)點編號
• v：視圖編號
• |R|節(jié)點個數(shù)

Primary角色分析

Primary節(jié)點的作用：

1. 正常工作時，接收客戶端的事務(wù)請求，驗證request身份后，為該請求設(shè)置編號，廣播pre-prepare消息
2. 新Primary當(dāng)選時，根據(jù)自己收集的View-Change消息，發(fā)送View-New信息，讓其它節(jié)點同步數(shù)據(jù)
3. Primary與所有的其它節(jié)點維系心跳

Primary節(jié)點地位和follower節(jié)點一樣，并沒有什么特權(quán)

1. 如果Primary宕機，會因為心跳超時，而觸發(fā)重新選舉，保證系統(tǒng)運行穩(wěn)定
2. 如果Primary惡意發(fā)送錯誤編號的消息，那么會在后續(xù)的操作中，被follower察覺，因為 prepare和commit階段都是會進行廣播的，一旦不一致，view-change
3. 如果Primary不發(fā)送接收到的request，client在超時未回復(fù)時，會重發(fā)request到所有的replica，小弟們發(fā)現(xiàn)primary竟然私藏消息，view-change
4. 如果Primary節(jié)點篡改消息，因為有Request里面有data和client的簽名，所以primary無法篡改消息，其它replica會先驗證消息的合法性，否則丟棄，view-change
   綜上所述，限制了權(quán)限的Primary節(jié)點，如果宕機、或者不發(fā)生消息、或者發(fā)送錯誤編號的消息、或者篡改消息，都會被其它節(jié)點感知，并觸發(fā)view-change。

PBFT工作正常的詳細流程

客戶端發(fā)起請求-->轉(zhuǎn)發(fā)請求到primary-->primary生成proposal-->primary廣播proposal-->所有節(jié)點復(fù)制proposal并廣播-->復(fù)制過半節(jié)點完成-->廣播commit節(jié)點-->commit過半節(jié)點完成-->應(yīng)用狀態(tài)機-->反饋客戶端-->客戶端統(tǒng)計f+1個反饋消息-->交易完成

1. 系統(tǒng)根據(jù)機器編號順序輪流選舉出一個primary，primary初始化時發(fā)出View-new消息，同步所有節(jié)點的數(shù)據(jù)
2. Client發(fā)起請求轉(zhuǎn)發(fā)給primary，primary驗證通過后，廣播這個請求，發(fā)起pre-prepare消息給所有的follower節(jié)點，并且自己也保存這個request
3. 所有的follower收到pre-prepare消息后，第一步是進行校驗，包括數(shù)據(jù)的順序是否正確，操作的先后有序性，以及交易是否有效比如簽名。（防止客戶端造假或者primary節(jié)點篡改造假）
4. follower驗證正確之后，寫到自己的磁盤里，然后廣播Prepare消息，并且自己也進入Prepare階段
5. 所有節(jié)點統(tǒng)計針對某個Request的Prepare消息，當(dāng)統(tǒng)計結(jié)果超過2f節(jié)點時，表明大部分節(jié)點已經(jīng)完成了持久化，則自己進入commit階段
6. 廣播 commit 消息，并且統(tǒng)計收到的commit 消息的數(shù)量，當(dāng)超過2f節(jié)點都發(fā)出commit的消息時
7. 該節(jié)點完成commit階段，寫入數(shù)據(jù)（該操作已經(jīng)完成2/3共識了），運用自己的狀態(tài)機，更新 stable checkpoint，緩存該客戶端最后一次的請求，并且反饋給客戶端
8. 當(dāng)客戶端統(tǒng)計反饋的節(jié)點超過f個時，表示交易已經(jīng)被大部分節(jié)點確認(rèn)了，交易成功。如果超時還不成功，則向所有的replica廣播這個request

解釋：

1. 為什么客戶端收到f+1個確認(rèn)時，交易就成功了？
   因為默認(rèn)問題節(jié)點為f，那么f+1個確認(rèn)節(jié)點中，肯定有1個是誠實的節(jié)點，只要有1個誠實的確認(rèn)消息，則交易成功，因為1個誠實的消息必須是2f+1個節(jié)點都commit操作成功了，才可能有這個1個最終確認(rèn)消息的。所以為了提升交易處理的速度，只要有f+1個確認(rèn)反饋，就可以表示交易成功。

客戶端Client發(fā)起請求

1. 客戶端 c 通過向副本多播一條<REQUEST，o，t，c>到系統(tǒng)中
2. 副本對Request進行身份驗證
3. 驗證成功，則接受請求并將其添加到它們的日志中，請求執(zhí)行使用request中的時間戳進行排序執(zhí)行
4. 副本直接將請求的回復(fù)發(fā)送給客戶端
5. 客戶端在接受結(jié)果 r 之前，等待一個來自不同副本的有 f + 1 個帶有有效 MACs 的以及相 同的 t 和 r 的 weak certificate
6. 如果客戶端沒有足夠迅速的收到一個 reply certificate，則會重新發(fā)送請求。如果請求已被處理，則副本只是重新發(fā)送回復(fù);副本記住他們發(fā)送給每個客戶端的最后一個回復(fù)消息以 啟用此重傳

客戶端請求消息:客戶端直接向Primary節(jié)點發(fā)起一個請求 ： 消息的格式<REQUEST, o, t, c>

• o: 請求的具體操作，operation
• t: 請求時客戶端追加的時間戳，time，這里面追加的是client的時間戳，會在后面的時候，客戶端的請求做時間戳排序，結(jié)合請求編號一起，保證消息的有序性（不僅僅是寫操作，還有讀寫操作）
• c：客戶端標(biāo)識，clientID，其中 c + t 就是requestID
• REQUEST: 包含消息內(nèi)容m，以及消息摘要d(m)?？蛻舳藢φ埱筮M行簽名。

服務(wù)端在執(zhí)行request時會進行簽名驗證，因為PBFT應(yīng)用的是聯(lián)盟鏈，而不是私鏈，所以要對操作者的身份進行校驗，比如A發(fā)起一筆轉(zhuǎn)賬，則服務(wù)端需要check是不是A發(fā)起的轉(zhuǎn)賬，防止盜刷

服務(wù)端回復(fù)消息：<REPLY, v, t, c, i, r>

• REPLY，消息類型為回復(fù)客戶端
• v，當(dāng)前view
• t，c 哪個client的時間戳為t的回復(fù)（而不是通過zxid，是通過時間戳，相當(dāng)于requestID）
• i 當(dāng)前node編號
• r 操作結(jié)果，還必須有server i的簽名，客戶端要驗證的，防止網(wǎng)絡(luò)攔截和欺詐

消息

• 消息的類型（pre-prepare、prepare、commit）

• View（類似于term)

• n（類似于index)

• d（交易的詳細信息)

• m(交易的簽名）

• i（節(jié)點的編號）

• checkpoint ：節(jié)點參數(shù)，該節(jié)點最新的proposal編號

• stable checkpoint：系統(tǒng)參數(shù)，該系統(tǒng)中，最新的超過2f節(jié)點commit過了的proposal的編號?？梢詼p少內(nèi)存的占用，已經(jīng)2f+1確認(rèn)過的操作，就最終確認(rèn)了，后續(xù)不需要操作了，可以從內(nèi)存中移除了。

重新選舉 viewChange

當(dāng)普通節(jié)點感知到primary異常的時候，觸發(fā)viewchange，重新選舉必須要有2f+1個節(jié)點都confirm（VIEW-CHANGE）了，發(fā)起重選才生效，一旦超過2f節(jié)點都發(fā)起VIEW-CHANGE消息，則選舉結(jié)束，p =v+1 mod |R|節(jié)點當(dāng)選為new Primary。并且new primary會根據(jù)自己統(tǒng)計的VIEW-CHANGE的內(nèi)容,生成并廣播NEW-VIEW消息，其它節(jié)點驗證之后，開始新的view

<VIEW-CHANGE, v+1, n, C, P, i>消息

• v+1 ：新的view編號
• n是最新的stable checkpoint的編號
• C是2f+1驗證過的CheckPoint消息集合
• P是當(dāng)前副本節(jié)點未完成的請求的PRE-PREPARE和PREPARE消息集合
  新的主節(jié)點就是 newPrimary = v + 1 mod |R|。當(dāng)newPrimary收到2f個有效的VIEW-CHANGE消息后，向其他節(jié)點廣播NEW-VIEW消息

<NEW-VIEW, v+1, V, O>

• V是有效的VIEW-CHANGE消息集合
• O是主節(jié)點重新發(fā)起的未經(jīng)完成的PRE-PREPARE消息集合

未完成的PRE-PREPARE消息集合的生成邏輯：

1. 選取V中最小的stable checkpoint編號min-s，選取V中prepare消息的最大編號max-s。
2. 在min-s和max-s之間，如果存在P消息集合，則創(chuàng)建<<PRE-PREPARE, v+1, n, d>, m>消息。否則創(chuàng)建一個空的PRE-PREPARE消息，即：<<PRE-PREPARE, v+1, n, d(null)>, m(null)>, m(null)空消息，d(null)空消息摘要。

副本節(jié)點收到主節(jié)點的NEW-VIEW消息，驗證有效性（各個replica都統(tǒng)計view-change的個數(shù)），有效的話，進入v+1狀態(tài)，并且開始O中的PRE-PREPARE消息處理流程。

特殊情況：
那么如果一半的節(jié)點和primary網(wǎng)絡(luò)分區(qū)了，那也無法發(fā)起重選。
同時primary也執(zhí)行不了新的操作，因為新的消息有一半節(jié)點收不到，整個集群陷入癱瘓狀態(tài)。所以primary也應(yīng)該和zab一樣，具備自我檢測超時，超過一定個數(shù)的ack缺失時，觸發(fā)重新選舉。

Raft Vs PBFT

1. Raft系統(tǒng)中l(wèi)eader擁有最高權(quán)限，follower如果和leader數(shù)據(jù)不一致，那么必須刪除自己的數(shù)據(jù)，保持和leader一致

2. PBFT中，Primary向我發(fā)送命令時，當(dāng)我認(rèn)為老大的命令是有問題時，我會拒絕執(zhí)行。并且很有可能會觸發(fā)view-change。就算我認(rèn)為老大的命令是對的，我還會問下團隊的其它成員老大的命令是否是對的，只有大多數(shù)人 （2f+1） 都認(rèn)為老大的命令是對的時候，我才會去執(zhí)行命令

PBFT的特點

1. 客戶端事務(wù)請求的嚴(yán)格有序性
   request里面包含了時間戳，request在服務(wù)端執(zhí)行的時候，按照時間戳進行排序執(zhí)行。而zab協(xié)議、raft協(xié)議都是按照先到先執(zhí)行的有序性（服務(wù)端），但是PBFT卻能按照Client的有序性。即使網(wǎng)絡(luò)問題，先發(fā)起的請求晚于后發(fā)起的請求抵達服務(wù)端，服務(wù)端也不會打亂執(zhí)行的順序，PBFT是更嚴(yán)格的操作有序性。這也提高了系統(tǒng)的復(fù)雜度。

2. 性能尚可
   PBFT 算法通信復(fù)雜度 o（n^2），因為系統(tǒng)在嘗試達成狀態(tài)共識時，涉及到N個幾點都需要廣播N-1個其它節(jié)點。而在沒有作惡節(jié)點的zab、raft系統(tǒng)中，通信復(fù)雜度 O(N)

參考

美圖架構(gòu)師 講PBFT 和Raft區(qū)別
https://zhuanlan.zhihu.com/p/35847127

原始論文的地址
http://pmg.csail.mit.edu/papers/osdi99.pdf

論文翻譯中文版
https://blog.csdn.net/DeveloperRen/article/details/82771710