【共識專欄】Quorum機制與PBFT
正文
正文
正文
實用性拜占庭容錯算法（Practical Byzantine Fault Tolerance，PBFT），是一種在信道可靠的情況下解決拜占庭將軍問題的實用方法。拜占庭將軍問題最早由Leslie Lamport等人在1982年發表的論文[1]提出，論文中證明了在將軍總數n大於3f，背叛者為f或者更少時，忠誠的將軍可以達成命令上的一致，即3f+1<=n，算法複雜度為O(n^(f+1))。隨後Miguel Castro和Barbara Liskov在1999年發表的論文[2]中首次提出PBFT算法，該算法容錯數量也滿足3f+1<=n，算法複雜度降低到了O(n^2)。
如果對於PBFT共識算法有所了解，對節點總數n與容錯上限f的關係可能會比較熟悉：在系統內最多存在f個錯誤節點的前提下，系統內總節點數量n應該滿足n>3f，在推進共識過程中則需要收集一定數目的投票，才能完成認證過程。在本節當中，我們將首先討論這些數值間關係該如何得出。
--Quorum機制--
在有冗餘數據的分佈式存儲系統當中，冗餘數據對象會在不同的機器之間存放多份拷貝。但是在同一時刻，一個數據對象的多份拷貝只能用於讀或者寫。為了保持數據冗餘與一致性，需要對應的投票機制進行維持，這就是Quorum機制。區塊鏈作為一種分佈式系統，同樣也需要該機制進行集群維護。
為了更好地理解Quorum機制，我們先來了解一種與之類似，但是更加極端的投票機制——WARO機制（Write All Read One）。使用WARO機制維護節點總數為n的集群時，節點執行寫操作的“票數”應當為n，而讀操作時的“票數”可以設置為1。也就是說，在執行寫入時，需要保證全部節點完成寫入操作才可視該操作為完成，否則會寫入失敗；相應地，在執行讀操作時，只需要讀取一個節點的狀態，就可以對該系統狀態進行確認。可以看到，在使用WARO機制的集群中，寫操作的執行非常脆弱：只要有一個節點執行寫入失敗，那麼這次操作就無法完成。不過，雖然犧牲了寫操作健壯性，但是，在WARO機制下，對於該集群執行讀操作會非常容易。
Quorum機制[3]就是對讀寫操作的折衷考慮，對於同一份數據對象的每一份拷貝，不會被超過兩個訪問對象讀寫，並且權衡讀寫時的集合大小要求。在一個分佈式集群當中，每一份數據拷貝對像都被賦予了一票。假設：
系統中有V票，這就意味著一個數據對像有V份冗餘拷貝；
對於集群中的共識節點，在推進共識算法時，參與共識的節點會同時對集群進行讀寫操作。為了平衡讀寫操作對於集合大小的要求，每個節點的R與W取同樣大小，記為Q。當集群中總共存在n個節點，並且其中最多出現f個錯誤節點的情況下，我們該如何計算n、f、Q之間的關係呢？接下來，我們將從最簡單的CFT場景出發，逐步探索如何在BFT場景中得到這些數值取值之間的關係。
▲CFT
正文
正文
正文
CFT（Crash Fault Tolerance），表示系統中的節點只會出現宕機（Crash）這種錯誤行為，任何節點不會主動發出錯誤消息。當我們在討論共識算法可靠性時，通常會關注算法兩種基本性質：活性（liveness）與安全性（safety）。在計算Q的大小時，同樣也可以從這兩個角度出發進行考慮。
對於活性與安全性，有一種比較直觀的描述方式：
something eventually happens[4]，某個事件最終會發生
something good eventually happens[4]，這個最終會發生的事件合理<=n-f。
從活性角度出發，我們的集群需要能夠持續運行下去，不會由於某些節點的錯誤導致無法繼續共識。從安全性角度出發，我們的集群在共識推進的過程中，能夠持續獲得某個合理的結果，對於分佈式系統來說，這種“合理”的結果，其最基本的要求就是集群整體狀態的一致性。
▲BFT
於是，在CFT場景下，對於Q數值的確定就變得簡單明確：
活性：由於我們需要保證集群能夠持續運行，所以，在任何場景下都要保證有獲取到Q票的可能性，從而為集合讀寫數據。由於集群中最多會有f個節點發生宕機，所以為了保證能獲取到Q票，該值的大小需要滿足：Q<=n-f。
安全性：由於我們需要保證集群不發生分歧，所以，按照Quorum機制的基本要求，需要滿足在上一節當中提到的兩個不等式，將Q作為最小讀集合與最小寫集合帶入該組不等式，此時，Q滿足不等關係，Q+Q>n且Q>n/2，因此，該值的大小需要滿足：Q>n/2。
▲節點總數與容錯上限
正文
正文
對於節點總數n與容錯上限f，在PBFT論文當中給出的解釋[1]：由於存在f個節點可能發生宕機，因此我們至少需要在收到nf條消息時進行響應，而對於我們收到的來自nf個節點的消息，由於其中最多可能存在f條消息來自於不可靠的拜占庭節點，因此需要滿足nff>f，所以，n>3f。簡單來說，PBFT的作者從集群活性與安全性出發，得到了節點總數與容錯上限之間的關係。上一節中，我們也是從活性與安全性角度，獲得了n、f與Q的關係，在這裡也可以用來推導n與f的關係：為了同時滿足活性與安全性的要求，Q需要滿足不等關係，Q<=nf且Q>(n+f)/2，因此，可以得到n與f之間的不等關係，(n+f)/2
(通過類似的方式，也可以得到CFT場景中n與f的關係，n>2f。)
▲兩階段共識
正文
正文
正文
相比較常見的“三階段“概念（pre-preapre、prepare、commit），將PBFT視為一種兩階段共識協議或許更能體現每個階段的目的：提案階段（pre-prepare與prepare）和提交階段（commit）。在每個階段中，各個節點都需要收集來自Q個節點一致的投票後，才會進入到下一個階段。為了更方便討論，這裡將討論節點總數為3f+1時的場景，此時，讀寫集票數Q為2f+1。
1) 提案階段
在該階段中，由主節點發送pre-prepare發起共識，由從節點發送prepare對主節點的提案進行確認。主節點在收到客戶端的請求後，會主動向其它節點廣播pre-prepare消息
v為當前視圖
n為主節點分配的請求序號
D(m)為消息摘要
m為消息本身
從節點在收到pre-prepare消息之後，會對該消息進行合法性驗證，若通過驗證，那麼該節點就會進入pre-prepared狀態，表示該請求在從節點處通過合法性驗證。否則，從節點會拒絕該請求，並觸發視圖切換流程。當從節點進入到pre-prepared狀態後，會向其它節點廣播prepare消息
i為當前節點標識序號
▲檢查點機制
正文
正文
正文
PBFT共識算法在運行過程中，會產生大量的共識數據，因此需要執行合理的垃圾回收機制，及時清理多餘的共識數據。為了達成這個目的，PBFT算法設計了checkpoint流程，用於進行垃圾回收。
checkpoint即檢查點，這是檢查集群是否進入穩定狀態的流程。在進行檢查時，節點廣播checkpoint消息
n為當前請求序號
i為當前節點表示
當節點收到來自不同節點的2f+1條有相同
▲視圖變更
正文
正文
正文
當主節點超時無響應或者從節點集體認為主節點是問題節點時，就會觸發視圖變更（view-change）。視圖變更完成後，視圖編號將會加1，隨之主節點也會切換到下一個節點。如圖所示，節點0發生異常觸發視圖變更流程，變更完成後，節點1成為新的主節點。
當視圖變更發生時，節點會主動進入到新視圖v+1中，並廣播view-change消息，請求進行主節點切換。此時，共識集群需要保證，在舊視圖中已經完成共識的請求能夠在新視圖中得到保留。因此，在視圖變更請求中，一般需要附加部分舊視圖中的共識日誌，節點廣播的請求為
i為發送者節點的身份標識
h為當前節點最近一次的穩定檢查點的高度
的方式進行存儲，表示當前節點已經執行過序號為n摘要為d的checkpoint檢查，並發送過相應的共識消息。
的方式進行存儲，表示在視圖v中，摘要為d序號為n的請求已經進入了prepared狀態。由於請求已經達成了prepared狀態，說明至少有2f+1個節點擁有並且認可該請求，只差commit階段即可完成一致性確認，因此，在新的視圖中，這一部分消息可以直接使用原本的序號，無需分配新序號。
Q：在當前節點已經達成pre-prepared狀態的請求的集合，即，當前節點已經針對該請求發送過對應的pre-prepare或prepare消息。在集合Q中，數據同樣按照
的方式進行存儲。由於請求已經進入pre-prepared狀態，表示該請求已經被當前節點認可。
但是，視圖v+1對應的新主節點P在收到其他節點發送的view-change消息後，無法確認view-change消息是否拜占庭節點發出的，也就無法保證一定使用正確的消息進行決策。 PBFT通過view-change-ack消息讓所有節點對所有它收到的view-change消息進行檢查和確認，然後將確認的結果發送給P。主節點P統計view-change-ack消息，可以辨別哪些view-change是正確的，哪些是拜占庭節點發出的。
節點在對view-change消息進行確認時，會對其中的P、Q集合進行檢查，要求集合中的請求消息小於等於視圖v，若滿足要求，就會發送view-change-ack消息
i為發送ack消息的節點標識
j為要確認的view-change消息的發送者標識
d為要確認的view-change消息的摘要
新的主節點P維護了一個集合S，用來存放驗證正確的view-change消息。當P獲取到一條view-change消息以及合計2f-1條對應的view-change-ack消息時，就會將這條view-change消息加入到集合S。當集合S的大小達到2f+1時，證明有足夠多的非拜占庭節點發起視圖變更。主節點P會按照收到的view-change消息，產生new-view消息並廣播，
V：視圖變更驗證集合，按照
的方式進行存儲，表示節點i發送的view-change消息摘要為d，均與集合S中的消息相對應，其他節點可以使用該集合中的摘要以及節點標識，確認本次視圖變更的合法性。
▲改進空間與RBFT
1) 交易池
RBFT（Robust Byzantine Fault Tolerance），是趣鏈科技基於PBFT為企業級聯盟鏈平台研發的高魯棒性共識算法。相比較PBFT來說，我們在共識消息處理、節點狀態恢復、集群動態維護等多方面進行了優化改良，使得RBFT共識算法能夠應對更複雜多樣的實際場景。
1) 交易池
包括RBFT在內，許多共識算法的工業實現中，都設計了獨立的交易池模塊。在收到交易後，將交易本身存放在交易池裡，並通過交易池對交易進行共享，使得各個共識節點都能獲得共享的交易。在共識的過程中，只需對交易哈希進行共識即可。
在處理較大交易時，交易池對於共識的穩定性有不錯的提升。將交易池與共識算法本身進行解耦，也更方便通過交易池實現更多的功能特性，比如交易去重。
2) 主動恢復
在PBFT中，當節點藉由checkpoint或view-change發現自身的低水位落後，即穩定檢查點落後時，落後節點就會觸發相應的恢復過程，以拉取該穩定檢查點之前的數據。這樣的落後恢復機制有一些不足：一方面，該恢復流程的觸發是被動的，需要在checkpoint過程或者觸發view-change完成時才能觸發落後恢復；另一方面，對於落後節點來說，如果通過checkpoint發現自身穩定檢查點落後時，落後節點只能恢復到最新的穩定檢查點，而無法獲得該檢查點後落後的共識消息，可能一直無法真正參與到共識當中。
在RBFT中，我們設計了主動的節點恢復機制：一方面，該恢復機制可以主動觸發，更快地幫助落後節點進行恢復；另一方面，在恢復到最新的穩定檢查點基礎之上，我們設計了水位間的恢復機制，從而使得落後節點能夠獲取到最新的共識消息，更快地參與到正常共識流程。
3) 集群動態維護
Raft作為一種廣泛應用在工程中的共識算法，其重要優勢之一，就是能夠動態完成集群成員變更。而PBFT沒有給出集群成員動態變更方案，在實際應用中存在不足。在RBFT中，我們設計了一種動態變更集群成員的方案，使得不需要停啟集群整體的情況下，就可以對集群成員進行增刪。
通過這樣的動態變更集群成員的方式，使得集群配置維護更加可靠與便捷，並且可以為動態修改更多配置信息提供了可能。
作者簡介
作者簡介
作者簡介
參考文獻
[1] Lamport L, Shostak R, Pease M. The Byzantine generals problem[M]//Concurrency: the Works of Leslie Lamport. 2019: 203-226.
[2] Castro M, Liskov B. Practical Byzantine fault tolerance[C]//OSDI.1999, 99(1999): 173-186.
[3] https://en.wikipedia.org/wiki/Quorum _ (distributed_computing)
[4] Owicki S, Lamport L. Proving liveness properties of concurrent programs[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 455-495.
[5] Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Comput. Surv., 22(4):299–319, 1990.
[6] Castro M, Liskov B. Practical Byzantine fault tolerance andproactive recovery[J]. ACM Transactions on Computer Systems (TOCS), 2002,20(4): 398-461.
