基于在網計算加速的拜占庭容錯算法

楊 帆 張 鵬 王 展 元國軍 安學軍

1(中國科學院計算技術研究所 北京 100190)

2(中國科學院大學 北京 100049)(yangfan@ncic.ac.cn)

隨著計算機網絡和分布式應用的不斷發展，網絡中充斥著越來越多的惡意攻擊，應用的復雜度越來越高，穩定性受到嚴重威脅.為了給分布式應用提供可靠性保障，人們提出了拜占庭容錯技術，該技術能夠容忍包括人為失誤、軟件故障和安全漏洞等各種形式的錯誤和攻擊[1]，因此被廣泛應用于區塊鏈、數據庫等對系統穩定性、安全性有著高要求的分布式系統中.

實用拜占庭容錯算法(practical Byzantine fault tolerance， PBFT)[2]是最具代表性的拜占庭容錯技術之一.該技術以多副本形式保證對錯誤的容忍，使用3階段的共識過程來保證各副本能夠以相同順序執行相同的客戶端請求，系統在受到部分節點的惡意干擾時也不會出錯.與工作量證明(proof-of-work， PoW)[3]、權益證明(proof-of-stake， PoS)[4]等其他拜占庭容錯算法相比，該算法具有高吞吐、低延遲的優點；而與非拜占庭容錯算法(non-Byzantine fault tolerant， NBFT)相比，其穩定性較高，但是性能卻較為低下.因此，在實際使用中，人們在選擇使用不同的算法時往往需要在穩定性和高性能之間做出取舍.

表1給出了各種共識算法的優劣對比.為了兼顧系統的穩定性和高性能，人們提出了各項針對實用拜占庭容錯算法的優化技術.我們將其分為3個方面：1)優化算法設計.盡可能簡化算法的一致性協議，使得算法在沒有惡意節點干擾的情況下提供高性能服務.2)降低算法開銷.算法執行過程中包含大量的密碼學相關的計算，降低這些計算的開銷有助于提升整體性能.3)提高算法并行度.充分利用多核處理器的優勢，使用多線程技術提升執行效率.

Table 1 Comparison of Different Consensus Algorithms

現有研究工作主要著力于上述3種方案的某一方面，而缺少三者的協同優化設計.本文嘗試從在網計算的角度提出一種新的實用拜占庭容錯算法的優化方案，同時兼顧降低算法開銷和提升算法并行度.該方案主要使用在網計算的方式將PBFT算法中共識過程中的部分計算任務卸載到網卡上去完成.一方面網卡強大的流式處理能力有助于降低延遲開銷；另一方面網卡和處理器組成的多級處理流水線能夠提高算法的吞吐量.同時，我們使用多線程方法進一步提高算法并行度，擴展了優化方案的適用場景.實驗表明基于在網計算的拜占庭容錯算法最多能夠獲得46%的吞吐量提升以及65%的延遲下降.

1 背景介紹

1.1 實用拜占庭容錯算法

實用拜占庭容錯算法廣泛應用于大規模分布式系統中，為系統安全性和穩定性提供保障.該算法能夠容忍不超過節點總數13的惡意節點；換言之，當系統節點總數為n，惡意節點數為f時，只要滿足n≥3f+1，系統就能夠對外界表現出正常的工作狀態.在后續論述中我們將沿用這些參數定義.

使用該算法的系統中包含2類節點：主節點和備份節點.其中主節點負責為客戶端請求選擇序號，并向各備份節點廣播請求.各節點按序執行客戶端請求.節點通過運行3種基本協議進行協同工作，包括一致性協議(agreement)、檢查點協議(checkpoint)以及視圖更換協議(view change).其中一致性協議負責節點間的共識，檢查點協議負責生成節點的穩定狀態，視圖更換協議負責主節點的切換.一致性協議是算法的主體執行部分，占據了絕大部分的時間開銷，因此我們將重點介紹一致性協議，而對后兩者略去不表.

一致性協議運行在主節點為非惡意節點的情況下，該協議通過Pre-Prepare，Prepare，Commit這3階段完成備份節點之間的共識，使得每個節點能夠按相同順序收到相同的請求，并執行相同的操作，從而保證副本之間的一致性.在一致性協議中，客戶端與節點之間通過Request和Reply操作完成交互：客戶端向主節點提交Request，并收集節點返回的Reply.當客戶端收到f+1條相同的Reply后，便表示Request已經在系統中成功提交并執行.整個算法流程分5個階段執行：

1) 客戶端向主節點發送Request；

2) 主節點在收到了客戶端的Request后進入Pre-Prepare階段，將Request廣播給主節點及其他備份節點；

3) 備份節點收到Request后，進入Prepare階段，將Request廣播給主節點及其他備份節點；

4) 主節點及備份節點收到廣播消息后，首先進行消息驗證以保證消息的完整性與不可否認性，然后保存消息以作為節點當前狀態的憑證，最后將其與Pre-Prepare階段的Request進行匹配，以判斷本節點與其他節點是否可以就請求序號和請求內容達成一致,當節點收到2f條匹配的消息后，進入Commit階段，將Request廣播給其他節點；

5) 所有節點重復Prepare階段的消息接收與驗證，并在收到2f條匹配的消息后按照序號所規定的順序依次執行各請求，在請求執行完成后向客戶端返回Reply.

圖1給出了一致性協議的詳細執行過程，其中節點1是主節點，其余節點是備份節點.分析可知，在一致性協議的執行過程中，一條客戶端請求的成功執行至少需要進行6f2+6f次節點間的通信，且每次通信過程都包含消息驗證、消息保存等操作，因此降低這些操作的開銷對提升算法的性能有著重要意義.

Fig. 1 Consensus protocol in PBFT

1.2 在網計算

在網計算是一種以數據為中心的計算模式[5]，其核心思想是將一部分流式計算任務卸載到網絡設備上執行，以達到提升計算效率、減少網絡流量的目的.當前，在網計算已經成為優化分布式應用的重要手段之一.例如Dang等人[6-7]提出的NetPaxos使用可編程交換機對非拜占庭容錯算法Paxos進行優化，István等人[8]提出了基于可編程網卡的原子廣播優化.

通過分析我們發現，拜占庭容錯算法與在網計算有著極佳的適配性.一方面，消息驗證與消息保存操作都可以在網卡上以專用硬件結構實現，其處理效率高于通用處理器；另一方面，網卡和處理器構成了多級處理流水線，能夠提升算法執行的并行度.

2 設計與分析

本節著重介紹系統的整體設計方案以及設計中的考量與取舍.如引言所述，對PBFT的優化主要有3個方面：減少算法執行開銷，提高并行度，以及簡化算法設計.

2.1 系統整體設計

本文設計并實現了一種軟硬件協同的實用拜占庭容錯算法優化方案.算法的一致性協議中，特別是Prepare和Commit階段，節點對消息的處理可以分為4個階段：消息驗證、消息保存、消息計數、請求執行(或生成新消息).不同的執行階段被分配到系統中不同的組件上執行，這樣的設計方案帶來了2個方面的顯著優勢：

1) 算法的密碼學驗證與消息保存被卸載到專用硬件網卡上執行，大大降低了處理時間開銷；

2) 多個組件協同完成整個處理過程，形成了多級流水線，提升了系統的吞吐率.

圖2和圖3分別給出了軟硬件流水線示意和系統的軟硬件架構圖.硬件部分的核心組件是消息保存模塊及消息驗證模塊.其中，消息驗證模塊從以太網模塊中獲取網絡數據，并使用密碼學方法對消息進行安全驗證，將通過驗證的消息傳遞給消息保存模塊；消息保存模塊使用散列表將以鍵值形式組織的消息存儲到主存中供拜占庭容錯算法使用.軟件方面，基于實用拜占庭容錯算法，本文借助多線程方法，由不同線程負責客戶端請求的共識和已共識請求的執行.

Fig. 2 Multi-stage pipeline of CPU and NIC

Fig. 3 Byzantine fault tolerant system architecture based on in-network computing

2.2 網卡硬件加速的優勢

與僅使用多線程進行優化的方式相比，使用專用硬件執行算法能夠帶來顯著的性能提升，這種收益來自于2個方面：1)與通用處理器相比，專用硬件針對算法特征做了定制化設計，避免了處理器中繁瑣的取指譯碼等流程，執行效率更高.例如，使用定制化的電路可以在幾個時鐘周期內完成密碼學驗證、散列等復雜的計算.2)多個線程主要通過共享內存的方式進行數據交互，頻繁的通信過程會帶來較大的內存讀寫開銷.而硬件模塊之間可以通過硬件隊列和信號進行數據傳遞，時間開銷較低.

為進一步說明這一點，本文分別使用FPGA和通用處理器進行32 B數據的SHA-256運算，其中硬件電路的頻率為200 MHz，處理器使用Intel Xeon CPU E3.圖4給出了2種計算模式的延遲對比.可以看到，使用硬件加速方案相對于通用處理器減少了95%的延遲開銷.

Fig. 4 Latency of different methods of SHA-256

使用加速器能夠在一定程度上減少計算開銷，但目前的加速器[9-10]大部分采用的是主從模式，這種模式存在較大的數據拷貝開銷.以圖5為例，網絡數據首先被搬移到主存，然后處理器通知加速卡獲取待處理數據.當加速卡計算完成后，主處理器讀回處理結果，整個過程包含了多次數據搬移.而可編程網卡天然位于網絡數據路徑上，當數據從網卡流經內存就已經完成了處理，不會帶來額外的數據拷貝開銷.因此，在網卡上對算法流程進行卸載是較好的選擇.表2給出了我們對網卡硬件加速與多線程和普通加速卡的優劣對比.

Fig. 5 Comparison of in-network computing and other accelerators

Table 2 Comparison of Different Optimization Strategies

2.3 多線程的必要性

使用網卡硬件進行計算卸載需要滿足一個先決條件，即數據包的處理應當能夠達到線速，否則有可能造成網絡丟包.為滿足這一限制條件，我們抽象了2個特征對不同的計算任務進行篩選：1)沒有循環計算；2)沒有數據依賴.具備這2種特征的計算任務被稱為流式計算.

基于上述分析，我們提取了算法中各個執行階段的計算特征，如表3所示:

Table 3 Characteristics of Different Tasks

通過分析我們發現，算法中的消息驗證與消息保存的核心是散列計算，是一種典型的流式計算，因此，這2部分的計算被卸載到網卡上執行.而算法中的消息計數，客戶端請求的執行涉及到內存訪問及循環操作，更適合在通用處理器上以更靈活的多線程方式實現.

2.4 簡化算法的一致性協議

簡化算法的一致性協議是拜占庭容錯算法的一種重要的優化手段，許多工作使用這種方式獲得了顯著的優化效果，如Zyzzyva[11]，fastBFT[12]，SBFT[13].

在簡化算法一致性協議方面，通常是引入1個或多個收集節點，由該節點收集其他節點消息并廣播統計情況，將多對多的消息傳遞轉化為多對1和1對多消息傳遞，以降低系統的消息復雜度.Zyzzyva，fastBFT，SBFT等都不同程度上使用了這一手段，Zyzzyva選擇使用客戶端作為收集節點，而fastBFT和SBFT則從備份節點中選拔收集節點.

使用收集節點雖然能夠簡化算法一致性協議，但也會帶來一些負面影響.首先，它會讓算法的其他部分變得復雜，如Zyzzyva雖然在理想情況下可以將一致性協議的消息復雜度由O(n2)降低至O(n)，但付出的代價是需要一個更為復雜的視圖更換協議，而且這種更為復雜的視圖更換協議有可能存在被攻擊的漏洞[14].其次，使用收集節點會為算法引入更為復雜的密碼學操作，如fastBFT和SBFT使用多簽名的方式來保證收集節點所廣播消息的可信度.

簡化算法的一致性協議雖然能夠降低系統消息復雜度，但也有其自身的局限性，因此我們并沒有采用這種優化方式.

3 實 現

3.1 定制化消息格式

為了將計算任務嵌入到網絡數據流的處理過程中，我們需要對消息進行標識，網卡通過識別消息中的特殊標志位后進行相應的處理.因此，我們對消息格式進行了定制化設計.

如圖6所示，消息被劃分為3個部分：消息頭(header)、消息鍵(key)以及消息值(value).消息頭主要提供消息的長度信息，以便網卡對消息負載進行界定和處理；消息內容以鍵值對的形式進行組織，承載應用要傳遞的信息.消息鍵承載了消息的特征信息，包括消息類型、源節點序號、請求序號、視圖號，用于消息保存中的散列值計算.消息值則包含了客戶端請求摘要、消息驗證碼向量.消息驗證碼向量可以保證消息在傳播過程中的完整性與不可否認性，它由一組面向不同接收節點的消息驗證碼組成.

Fig. 6 Customized message format

3.2 基于網卡的消息驗證模塊

消息驗證模塊被卸載到網卡硬件上執行，它提供了基于SHA-256安全散列算法的消息驗證功能.如圖7所示，該模塊通過消息預處理、驗證碼提取、安全散列值計算、驗證碼對比等操作完成消息的驗證.其中消息預處理模塊提取出消息的長度信息、源節點信息以及消息驗證向量，將其傳遞給驗證碼提取模塊使用，同時，將消息的負載傳遞給安全散列計算模塊進行密碼學運算；安全散列計算模塊實現了SHA-256安全散列算法，該算法根據消息和對應密鑰計算目標驗證碼；驗證碼提取模塊則從消息所攜帶的驗證碼向量中提取出與本節點對應的驗證碼.最后驗證碼對比模塊將消息攜帶的驗證碼與安全散列計算得到的目標驗證碼對比，決定是否向后續模塊傳遞該信息.其中安全散列計算的處理過程較為復雜，這里對其設計方案進行詳細說明.

Fig. 7 Message verification module

1) 初始化

這一步包含散列值初始化和密鑰初始化.在SHA-256中，散列值是一段256 b的二進制串，它的初始值按如下規則計算得到：使用二進制形式計算自然數中前8個質數(2,3,5,7,11,13,17,19)的平方根，分別取每個計算結果小數部分的前32 b.密鑰是一段長度為2 048 b的二進制串，被劃分為64個字(1個字是4 B)，密鑰由用戶指定.表4給出了初始散列值.

Table 4 Initial Hash Values

2) 數據分塊

SHA-256是一種增量式的散列算法，即一邊輸入數據一邊更新散列值.為了實現增量計算，算法對輸入數據分塊，以塊為單位進行散列計算，每個塊的長度是512 b.同時，算法規定要在輸入數據的尾部進行填充操作.填充內容主要有數據長度和比特.數據長度填充指將輸入數據的長度轉換為64 b二進制數，填寫在輸入數據最后一個塊的最后64 b上.比特填充則是用附加的位將輸入數據長度擴充至512 b的整數倍，保證輸入數據能夠被劃分為整數個塊.而且，算法規定比特填充的長度不能為0，至少1 b，填充的第1個位為1，其余位為0.比特填充的位置在輸入數據尾部長度填充之前.圖8給出了數據分塊示意圖.

Fig. 8 Message filling and data partitioning

3) 預處理

當數據分塊完成后，所得結果并不能直接被散列計算模塊使用.需要先將一個數據塊構造成64個4 B大小的字.構造規則為：

① 前16個字由該塊平均劃分得到；

② 其余字由迭代得到，其中Wt指代第t個字，>>>指循環右移，>>指邏輯右移：

Wt=δ1(Wt-2)+Wt-7+δ0(Wt-15)+Wt-16，

(1)

δ0(x)=(x>>>7)?(x>>>18)?(x>>3)，

(2)

δ1(x)=(x>>>17)?(x>>>19)?(x>>10).

(3)

4) 散列計算

散列計算是一個循環迭代的過程，一輪循環包括64步，每步輸入預處理生成的1個字以及密鑰中對應的1個字，每步都更新1次散列值，1輪循環恰好處理輸入的1個塊.一步散列計算的過程依照式(4)～(10)進行：

f0(x,y,z)=(x∧y)?(y∧z)?(x∧z),

(4)

f1(x,y,z)=(x∧y)?(x∧z),

(5)

Σ0(x)=(x>>2)?(x>>13)?(x>>22),

(6)

Σ1(x)=(x>>6)?(x>>11)?(x>>25),

(7)

{Bi+1,Ci+1,Di+1,Fi+1,Gi+1,Hi+1}={Ai,Bi,Ci,Ei,Fi,Gi},

(8)

Ei+1=Di+Σ1(Ei)+f1(Ei,Fi,Gi)+Hi+Ki+Wi,

(9)

Ai+1=Σ0(Ai)+f0(Ai,Bi,Ci)+Σ1(Ei)+f1(Ei,Fi,Gi)+Hi+Ki+Wi，

(10)

其中，A～H是8個字，它們共同組成散列值，Wi代表輸入的第i個字，Ki代表密鑰的第i個字.

圖9是計算過程示意圖.從圖9可以看到，散列計算過程中，新散列值可以分為3個不同部分：1)B，C，D，F，G，H，它們僅僅由舊散列值的對應字右移得到;2)E，它由舊散列值的D,E,F,G,H以及輸入字和密鑰經過與、非、異或、加法計算得到;3)A，它由舊散列值中除D外所有字以及輸入字和密鑰經過與、非、異或、加法計算得到.實際上，算法通過對A和E的計算及以字為單位的右移，讓輸入數據信息能夠影響散列值每一位，從而使最終得到的散列值能夠代表輸入數據.

Fig. 9 SHA-256 Hash calculation

3.3 基于網卡的消息保存

如2.1節所述，消息保存功能也被卸載到網卡上執行.如圖10所示，消息保存模塊由散列計算、沖突管理、數據上傳3個子模塊組成.節點收到的消息通過散列表的方式進行保存，我們在板載DRAM中保存散列表的元數據，在主存中保存實際數據.散列計算模塊負責提取消息鍵并計算散列值，散列值決定了消息所占用的散列表項；沖突管理模塊負責解決散列沖突問題；數據上傳模塊負責將消息封裝為PCIe事務包并上傳.接下來闡述3個模塊的詳細設計.

Fig. 10 Message store module

1) 散列計算子模塊

散列計算子模塊根據消息中的鍵計算出消息的散列值.該模塊實現了非密碼學相關散列算法Murmur來進行散列表索引的計算，與密碼學相關算法SHA-256相比，該算法計算過程更加簡潔，延遲更低.同時，Murmur已經被廣泛應用于主流數據庫應用中，具有較高的安全性和穩定性.

Murmur的主要計算過程分為3部分：數據體處理、數據尾處理和散列值處理.數據體指輸入數據中可以被劃分為整塊的部分，塊長度為128 b，數據體處理指將輸入數據以塊為單位劃分并進行散列計算.數據尾是指輸入數據結尾不夠一整塊的部分，數據尾處理指以數據尾為輸入時進行的散列計算.散列值處理，數據尾計算得到的散列值并不是最終的輸出散列值，還需要經過散列值處理才能輸出.

步驟1. 數據體處理.輸入數據被切分成128 b的塊，每一塊分別進行常量乘、循環左移、異或、常量加等操作.具體計算過程:

t=Hi?(((Ci×c1)<<

(11)

Hi+1=(t<<

(12)

其中,Ci為輸入塊，<<<代表循環左移操作，Hi代表當前散列值，Hi+1代表更新后的散列值,c1，c2，r1，r2，m，n均為常量.

步驟2. 消息尾處理.當輸入數據結尾部分不足以構成一個完整的塊時，需要使用專門的消息尾處理操作進行散列值計算.消息尾有其特定的計算方式，首先調整消息尾端序，若本身是大端序則調整為小端序，反之亦然；然后進行常量乘、循環左移、異或操作：

Ho=Hi?((S(T)×c<<

(13)

其中，T代表數據尾，S代表端序調整函數，Hi代表當前散列值，Ho代表計算所得散列值.

步驟3. 散列值處理.Murmur算法規定，當所有數據輸入完畢，計算所得到的散列值不能直接輸出，而是通過一系列異或、移位、常量乘運算才能獲得最終的散列值，計算過程為

f(x,y)=x?(x>>r),

(14)

Ho=f(f(f(Hi?L,r3)×c3,r2)×c4,r3)，

(15)

其中L代表輸入消息的長度.

2) 沖突管理子模塊

散列沖突指的是多個輸入在經過散列計算后得到同一個散列值的情況.在散列表中，發生散列沖突時，多個輸入會被映射到同一個散列表項中，導致數據的丟失.因此，本文設計了一種多槽位散列沖突解決方案.如圖11(a)所示，每一個散列表項包含多個槽位，發生散列沖突的消息放置在同一個散列表項的不同槽位中.同時，如圖11(b)所示，該模塊在網卡的板載DRAM中維護一個位圖，以記錄散列表項中槽位的使用情況.

Fig. 11 Multi-slot Hash table and bitmap

圖12給出了沖突管理模塊的架構圖，該模塊包含3個子模塊：位圖讀取模塊、位圖管理模塊以及調度模塊.位圖讀取模塊根據散列值生成位圖訪問請求，該請求讀取位圖中對應項槽位的使用情況.位圖管理模塊主要負責接收位圖返回的信息，根據槽位的使用情況為消息分配槽位，并將新的槽位使用情況寫回位圖中.由于位圖讀取模塊和位圖管理模塊均需要向板載DRAM發送請求，所以需要調度模塊負責消息的調度，避免發生競爭.

Fig. 12 Collision management module

3) 數據上傳模塊

數據上傳模塊根據消息的散列值和槽位號計算消息在散列表中的偏移，進而計算消息在內存中的地址，然后將消息封裝為PCIe事務包傳遞給網卡的PCIe接口.表5給出了各項參數的含義.需要說明的是這里的內存地址指的是物理內存地址，我們配置操作系統預留充足的物理內存空間供散列表使用，應用程序通過內存重映射方式訪問該內存區域.

待保存消息對應內存地址的計算方法為

A=HA+SW×(H×SN+SID)，

(16)

其中各參數的定義如表5所示：

Table 5 Parameters of Memory Address

3.4 多線程拜占庭容錯

Fig. 13 Flow chart of consensus protocol

圖13是算法一致性協議的流程圖.我們將算法的一致性協議劃分為共識和執行客戶端請求2個過程，分別由圖13(a)(b)表示的線程負責.其中虛線部分為卸載到網卡上的消息驗證與消息保存操作.如圖13所示，圖13(a)是共識線程中部分流程圖，該線程監聽等待網絡消息，當網絡消息到達后，判斷網絡消息類型，執行相關處理流程.Request消息是客戶端發送的請求，只有主節點會收到該請求，當主節點收到Request請求后，使用消息驗證碼驗證消息來源是否可靠，并為其選取一個請求號，請求號按主節點收到客戶端請求的順序遞增選取，然后根據客戶端請求生成Pre-Prepare消息并廣播.節點收到Pre-Prepare消息，先根據消息驗證碼對消息來源進行驗證，保存PrePrepare消息及其包含的客戶端請求，生成Prepare請求并廣播.節點收到Prepare消息，根據消息驗證碼驗證消息來源，保存消息及其驗證碼向量作為憑證，為剔除惡意節點的干擾檢查收到的Prepare消息與同請求號的Pre-Prepare消息內容是否相符，對通過檢查的消息計數，當計數值達到閾值時，生成Commit消息.收到Commit消息的處理流程與收到Prepare的流程類似，區別在于消息計數值達到閾值時共識完成，提交本次所共識客戶端請求；這里的提交是指，將客戶端請求插入優先隊列，并發送執行信號給請求執行線程.需要說明的是圖13(a)中虛線部分在本文中卸載到網卡上以硬件形式完成，而非以軟件形式實現.

圖13(b)是請求執行線程流程圖，該線程并沒有采用無間斷輪詢優先隊列的方式，而是在沒有請求待執行的時候，讓線程阻塞在相關信號的等待上，節約了系統計算資源.該線程收到請求執行信號后，讀優先隊列頭部請求的序號，判斷該請求序號與最近執行的最后1條請求序號是否連續，執行該判斷的目的是保證節點嚴格按照已共識的請求號順序執行客戶端請求.若連續，則從優先隊列取出并執行該請求，并根據執行結果向客戶端發送Reply響應；然后，按照上述描述繼續讀取并執行請求，直到隊頭請求與最近執行請求的序號不連續為止.

4 系統評測

4.1 實驗環境

本文使用2臺物理機作為測試平臺，物理機配置如表6所示.我們通過配置內核啟動參數memmap預留4 GB內存作為保存消息的散列表使用.散列表中每個散列表項靜態配置4個槽位，每個槽位寬度為256 b.網卡硬件使用NetFPGA-SUME開發板進行消息驗證與消息保存的卸載，通過8通道PCIe Gen3接口與主板連接，提供SFP+網絡接口，帶寬為10 Gbps，同時，我們使用Intel X710-DA4網卡作為對照實驗.

Table 6 System Configurations

NetFPGA網卡的網絡通信部分借助于cHPP控制器[15-16]實現，cHPP控制器提供了一整套節點間通過直接網絡互聯通信的解決方案，包括硬件網卡、設備驅動和軟件通信庫.

為了在2個物理節點上真實展現多節點執行拜占庭共識算法時的通信場景，每個節點上使用2張網卡.如圖14(a)所示，1張網卡發送消息，1張網卡接收消息，接收消息的網卡負責消息驗證與消息保存的卸載.2個物理節點共使用4張網卡，網卡之間通過以太網交換機進行數據轉發.圖14(b)展示了本文搭建的原型系統.

Fig. 14 Interconnection of different nodes

4.2 評測方法

測評主要針對多種不同場景對系統進行壓力測試，以觀察各種優化手段的效果.客戶端和服務器端以同步方式工作，客戶端向主節點發送請求并等待節點響應，當收到f+1條符合要求的響應后認為系統已經完成當前請求的提交，繼續發送下一條請求.為了給系統提供足夠的壓力，需要使用多個客戶端同時發起請求.

評測主要關注系統吞吐和延時，以每秒鐘系統所完成的共識次數來代表系統吞吐，以客戶端發出請求到收到f+1條響應之間的間隔為系統延時.所有測試結果均是多次測量并去掉最大值、最小值，取剩余測試結果的平均值得到.

由于本文同時使用了在網計算和多線程的優化方法，因此，為了評估每種優化手段對性能提升的影響，測評中共包含4種配置拜占庭容忍共識算法實現，如表7所示.首先，根據是否使用在網計算方法將實驗配置劃分為2類：使用在網計算方法的實驗配置中由我們的在網計算平臺NetFPGA完成消息驗證與消息保存的卸載；不使用在網計算方法的實驗配置則采用具有相同帶寬的Intel X710網卡.同時，根據是否使用多線程方法將實驗配置劃分為2類：1)使用單線程串行執行算法共識過程和請求執行過程；2)使用多線程分別負責算法共識過程和請求執行過程.

Table 7 Experiment Configuration

為簡述起見，下文的描述以及圖表中，以INC代表在網計算，N-INC代表非在網計算，ST代表單線程，MT代表多線程.

4.3 評測結果分析

4.3.1 不同請求壓力下的系統性能表現

本節對比了不同請求壓力下系統的吞吐和延時變化.客戶端以同步方式工作，單客戶端不足以讓服務端滿負荷運轉，所以使用多客戶端同時發送請求的方式，客戶端數量代表了請求壓力大小.這里共啟動2個服務節點，然后逐步增加客戶端的數量，服務端對該請求提供簡單的計數器服務.

圖15是2種配置下系統吞吐隨客戶端數量增長的對比.首先，2種配置下吞吐變化趨勢相同，都是隨著客戶端數量的增長，吞吐先快速上升，后慢速上升，最后到達一個穩定值.當客戶端數量過少時，不能給系統提供足夠的壓力；隨著客戶端數量增加，系統壓力逐漸增大，吞吐隨之升高；當客戶端數量為12個時，系統滿負荷運轉，系統吞吐到達一個穩定值.其次，綜合使用在網計算與多線程的配置能獲得更好的吞吐性能，與非在網計算加單線程配置相比，最大可獲得46%的吞吐提升.吞吐性能的提升得益于系統并行度的提升.如4.2節所提到的，NetFPGA卸載消息驗證與消息保存操作，能夠在網卡和CPU上形成一個消息處理的多級流水線；而且多線程方式執行共識過程和請求執行過程，進一步提升了系統的并行度.

Fig. 15 System throughput

當客戶端數量繼續增加，系統吞吐量出現下降趨勢，這是因為實驗中使用的物理機1具有16個核，主節點程序的4個線程(輪詢客戶端請求、輪詢共識請求、共識線程以及請求執行線程)分別綁定到4個核上，每個客戶端程序也綁定到一個特定的核上.因此當客戶端數量超過12個時，就會出現處理器資源的競爭，從而使得單位時間內完成的共識請求數量減少，同時，單次共識請求的延時也隨之上升.但是，與非在網計算加單線程的配置相比，在網計算加多線程的優化方式仍然具有較高的吞吐提升.

Fig. 16 Latency of request

圖16是2種配置下系統延時隨客戶端數量增長的對比.與吞吐量的變化趨勢類似，延時先慢速增長，后快速提升.比較兩者最小延時，可以看到，在請求壓力較大時，系統延時下降達到了65%.系統延時的降低有2方面原因：1)正如2.2節所介紹的，基于在網計算的消息驗證與消息保存的卸載會降低系統延時；2)在NetFPGA上借助cHPP 通信庫實現網絡通信，用戶程序可以借助其通信庫直接訪問網卡驅動，繞過了操作系統內核，減少了軟件調用層次和內存拷貝，從而進一步降低了系統延時.

4.3.2 在網計算與多線程的特點分析

本節主要對比了不同應用負載下多線程和硬件卸載的優化效果.實驗配置是2個服務節點、多客戶端同時發起請求，客戶端數量為12個，服務端對請求提供簡單的計數服務.本實驗引入了不同的應用負載，用服務端收到一個已共識請求后對計數器進行的循環自增次數代表應用負載.

圖17展示了不同應用負載下在網計算和多線程優化的效果.從圖17中能夠看到，隨應用負載的增加，系統的吞吐性能是逐漸降低的.而且，在應用負載較小時，在網計算方法在優化中起主導作用，隨著應用負載增大，多線程優化的效果逐漸凸顯，當增大到10萬次循環自增時，多線程方法在優化中占據主導作用.從圖17中我們能得到2點結論：1)綜合使用多線程和在網計算優化方法的效果要好于單獨使用一種優化方法；2)多線程優化和在網計算優化是一種相輔相成的優化方式，在網計算優化在應用負載較小時有較好的優化效果，多線程優化在應用負載較大時有較好的表現.

Fig. 17 System throughput of different applications

與單獨使用一種優化方式相比，綜合優化能夠在網卡與CPU上建立一條更深的多級流水線，獲得更好的系統并行度.另一方面，當應用負載較小時，執行客戶端請求消耗的時間較小，單線程與多線程的吞吐差別不大，這時使用多線程優化收益較低；而隨著應用負載增大，請求執行時間增加，使用多線程優化收益逐漸凸顯. 圖18展示不同應用負載下的系統最小延時.從圖18中能夠看到，系統延時隨應用負載的增大而增大；在網計算方法能夠降低系統延時，但是多線程方法會在一定程度上提高系統延時.

Fig. 18 System delay of different applications

在網計算方法能夠降低系統延時的現象可以從2方面解釋：1)消息驗證與消息保存的卸載會在一定程度上降低系統延時；2)非在網計算配置下系統使用X710網卡，而在網計算配置下系統借助NetFPGA上實現的cHPP控制器進行網絡通信，該配置下用戶使用通信庫直接訪問網卡驅動，繞過了系統內核，也有利于降低系統延遲.

多線程方式會在一定程度上提高系統延時的現象主要原因是：為了使用多線程優化，需要通過隊列進行線程間的消息傳遞，而且在完成共識后還需要共識線程發送事件信號喚醒請求執行線程，線程間的交互和線程從掛起到喚醒的時間損耗為系統延時帶來了負面影響.不過從實驗結果中可以看到，多線程方式對系統延時的影響并不大，僅有10～30 μs的額外時間開銷.

4.3.3 優化對算法可擴展性的影響

從2.1節的分析中我們知道，實用拜占庭容忍共識算法的消息復雜度為O(n2)，n為節點數目，系統可擴展性不佳.本節通過觀察在不同節點規模下的優化效果，探討本文所述優化方法對算法可擴展性的影響.實驗配置是采用2個物理節點，運行2～7個服務節點進程，多客戶端同時發起請求，服務端對請求提供簡單的計數服務.

圖19和圖20展示了不同服務節點規模下綜合使用在網計算優化和多線程優化的效果.圖19是不同系統規模下的吞吐性能表現，圖20是不同系統規模下的延時表現.首先，隨著服務節點數量的增加，系統吞吐逐漸下降，系統延時逐漸上升.因為隨著服務節點數量的增加，完成一次共識所需通信次數也隨之增加，每個節點需要處理更多消息.其次，使用本文所述的優化方法能夠在不同系統規模下獲得較好的性能表現，緩解系統規模擴大帶來的性能下降問題.本文所述優化方法能夠在一定程度上提高系統的可擴展性.

Fig. 19 System throughput of different scales

Fig. 20 System delay of different scales

5 總結與展望

拜占庭容忍共識算法為云計算和高性能計算提供了一種高可靠的容錯方案，但是其通信需求高、消息驗證需求高、消息保存需求高的“三高”特點限制了它的性能表現.本文提出一種基于在網計算的拜占庭容忍共識算法優化方案，嘗試解決其性能低下的問題.該解決方案將算法中的部分執行流程卸載到網卡硬件上執行，并通過多線程優化方法提高算法并行度.測試結果證明本文所述優化方法不僅可以提高算法吞吐、降低延時，還可以增強算法的可擴展性.

未來我們將考慮對現有設計方案進行優化，主要方向有2點：

1) 硬件廣播.當前算法實現中使用了應用層廣播而非硬件廣播，在網絡中加入硬件廣播的支持，可能會獲得進一步的性能提升.

2) 更多操作的硬件卸載.可以嘗試卸載更多的處理流程，如發送端的消息驗證碼的生成等.實際上，最終可以把共識過程作為下層協議與上層的請求執行過程分離，整個共識過程實現在NetFPGA或專用芯片上，通用處理器只負責業務邏輯的執行.