概述

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

容錯率

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

角色

Primary節(jié)點和普通節(jié)點留储，PBFT系統的Primary是輪流當選的翼抠，這和zab丐膝、raft不一樣

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

Primary角色分析

Primary節(jié)點的作用：

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

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

1. 如果Primary宕機凛俱，會因為心跳超時紊馏，而觸發(fā)重新選舉，保證系統運行穩(wěn)定
2. 如果Primary惡意發(fā)送錯誤編號的消息蒲犬，那么會在后續(xù)的操作中朱监，被follower察覺，因為 prepare和commit階段都是會進行廣播的暖哨，一旦不一致赌朋，view-change
3. 如果Primary不發(fā)送接收到的request，client在超時未回復時篇裁，會重發(fā)request到所有的replica沛慢，小弟們發(fā)現primary竟然私藏消息，view-change
4. 如果Primary節(jié)點篡改消息达布，因為有Request里面有data和client的簽名团甲，所以primary無法篡改消息，其它replica會先驗證消息的合法性黍聂，否則丟棄躺苦，view-change
   綜上所述，限制了權限的Primary節(jié)點产还，如果宕機匹厘、或者不發(fā)生消息、或者發(fā)送錯誤編號的消息脐区、或者篡改消息愈诚，都會被其它節(jié)點感知，并觸發(fā)view-change。

PBFT工作正常的詳細流程

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

1. 系統根據機器編號順序輪流選舉出一個primary炕柔，primary初始化時發(fā)出View-new消息酌泰，同步所有節(jié)點的數據
2. Client發(fā)起請求轉發(fā)給primary，primary驗證通過后匕累，廣播這個請求陵刹，發(fā)起pre-prepare消息給所有的follower節(jié)點，并且自己也保存這個request
3. 所有的follower收到pre-prepare消息后欢嘿，第一步是進行校驗衰琐，包括數據的順序是否正確，操作的先后有序性际插，以及交易是否有效比如簽名碘耳。（防止客戶端造假或者primary節(jié)點篡改造假）
4. follower驗證正確之后绍移，寫到自己的磁盤里迫卢，然后廣播Prepare消息，并且自己也進入Prepare階段
5. 所有節(jié)點統計針對某個Request的Prepare消息励背，當統計結果超過2f節(jié)點時瑟枫，表明大部分節(jié)點已經完成了持久化斗搞，則自己進入commit階段
6. 廣播 commit 消息，并且統計收到的commit 消息的數量慷妙，當超過2f節(jié)點都發(fā)出commit的消息時
7. 該節(jié)點完成commit階段僻焚，寫入數據（該操作已經完成2/3共識了），運用自己的狀態(tài)機膝擂，更新 stable checkpoint虑啤，緩存該客戶端最后一次的請求，并且反饋給客戶端
8. 當客戶端統計反饋的節(jié)點超過f個時架馋，表示交易已經被大部分節(jié)點確認了狞山，交易成功。如果超時還不成功叉寂，則向所有的replica廣播這個request

解釋：

1. 為什么客戶端收到f+1個確認時萍启，交易就成功了？
   因為默認問題節(jié)點為f屏鳍，那么f+1個確認節(jié)點中勘纯，肯定有1個是誠實的節(jié)點，只要有1個誠實的確認消息钓瞭，則交易成功驳遵，因為1個誠實的消息必須是2f+1個節(jié)點都commit操作成功了，才可能有這個1個最終確認消息的山涡。所以為了提升交易處理的速度超埋，只要有f+1個確認反饋搏讶，就可以表示交易成功佳鳖。

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

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

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

• o: 請求的具體操作帽衙，operation
• t: 請求時客戶端追加的時間戳，time贞绵，這里面追加的是client的時間戳厉萝，會在后面的時候，客戶端的請求做時間戳排序榨崩，結合請求編號一起谴垫，保證消息的有序性（不僅僅是寫操作，還有讀寫操作）
• c：客戶端標識母蛛，clientID翩剪，其中 c + t 就是requestID
• REQUEST: 包含消息內容m，以及消息摘要d(m)彩郊∏巴洌客戶端對請求進行簽名。

服務端在執(zhí)行request時會進行簽名驗證秫逝，因為PBFT應用的是聯盟鏈恕出，而不是私鏈，所以要對操作者的身份進行校驗筷登，比如A發(fā)起一筆轉賬剃根，則服務端需要check是不是A發(fā)起的轉賬，防止盜刷

服務端回復消息：<REPLY, v, t, c, i, r>

• REPLY前方，消息類型為回復客戶端
• v狈醉，當前view
• t，c 哪個client的時間戳為t的回復（而不是通過zxid惠险，是通過時間戳苗傅，相當于requestID）
• i 當前node編號
• r 操作結果，還必須有server i的簽名班巩，客戶端要驗證的渣慕，防止網絡攔截和欺詐

消息

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

• View（類似于term)

• n（類似于index)

• d（交易的詳細信息)

• m(交易的簽名）

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

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

• stable checkpoint：系統參數眨猎，該系統中，最新的超過2f節(jié)點commit過了的proposal的編號强经∷悖可以減少內存的占用，已經2f+1確認過的操作匿情，就最終確認了兰迫，后續(xù)不需要操作了，可以從內存中移除了炬称。

重新選舉 viewChange

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

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

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

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

• V是有效的VIEW-CHANGE消息集合
• O是主節(jié)點重新發(fā)起的未經完成的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都統計view-change的個數）距芬，有效的話涝开，進入v+1狀態(tài)，并且開始O中的PRE-PREPARE消息處理流程框仔。

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

Raft Vs PBFT

1. Raft系統中l(wèi)eader擁有最高權限操软，follower如果和leader數據不一致嘁锯，那么必須刪除自己的數據，保持和leader一致

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

PBFT的特點

1. 客戶端事務請求的嚴格有序性
   request里面包含了時間戳野芒，request在服務端執(zhí)行的時候蓄愁，按照時間戳進行排序執(zhí)行。而zab協議狞悲、raft協議都是按照先到先執(zhí)行的有序性（服務端）撮抓，但是PBFT卻能按照Client的有序性。即使網絡問題摇锋，先發(fā)起的請求晚于后發(fā)起的請求抵達服務端丹拯，服務端也不會打亂執(zhí)行的順序，PBFT是更嚴格的操作有序性荸恕。這也提高了系統的復雜度乖酬。

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

參考

美圖架構師 講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