面向邊緣計(jì)算應(yīng)用的拜占庭式容錯(cuò)分布式一致性算法

張 昊,路紅英

(北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院,北京 100044)

0 引 言

在云計(jì)算中，為保證服務(wù)的可用性與可靠性，業(yè)界廣泛采用副本技術(shù)為服務(wù)在不同節(jié)點(diǎn)上構(gòu)建多個(gè)副本，并采用分布式一致性算法維持副本間的一致性(Consistency)來預(yù)防停止運(yùn)行(Fail-stop)錯(cuò)誤[1]。一致性是指，在所有節(jié)點(diǎn)初始狀態(tài)相同的條件下，執(zhí)行相同的操作命令，最終所有節(jié)點(diǎn)會(huì)達(dá)成完全一致的狀態(tài)[2]。Raft算法由于其簡單易懂的設(shè)計(jì)成為了云計(jì)算中使用最廣泛的分布式一致性算法[3]，并廣泛應(yīng)用于Etcd、Zookeeper等分布式應(yīng)用中。

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，越來越多的物聯(lián)網(wǎng)設(shè)備帶來了數(shù)據(jù)量的爆炸式增長，而云計(jì)算現(xiàn)有的資源和帶寬還不足以對(duì)這些數(shù)據(jù)進(jìn)行高效處理，因此，作為云計(jì)算的有效補(bǔ)充，能夠有效降低云中心計(jì)算負(fù)載的邊緣計(jì)算模型得到了廣泛的重視[4]。邊緣計(jì)算是指在網(wǎng)絡(luò)邊緣端進(jìn)行數(shù)據(jù)處理計(jì)算的一種新型計(jì)算模型[5]，為用戶提供了超低時(shí)延和高性能的計(jì)算服務(wù)解決方案[6]。在邊緣環(huán)境中可以采用Docker容器技術(shù)來解決邊緣節(jié)點(diǎn)異構(gòu)性的問題，使其能夠快速在邊緣端快速部署或終止服務(wù)。通常會(huì)在邊緣集群部署Docker Swarm、Kubernetes等容器編排工具來對(duì)容器進(jìn)行?；?、遷移、調(diào)度等[7]。為了監(jiān)控整個(gè)邊緣集群的全部資源和容器的運(yùn)行狀態(tài)，這些容器編排工具均引入Etcd、Zookeeper等組件同步資源和容器信息，同時(shí)保證邊緣節(jié)點(diǎn)間的數(shù)據(jù)一致性[8]。專門為物聯(lián)網(wǎng)和邊緣計(jì)算設(shè)計(jì)的容器編排工具k3s也于v1.19.5+k3s1版本中將Etcd作為核心組件引入[9]，由此可見，在邊緣環(huán)境中保持分布式應(yīng)用的數(shù)據(jù)一致性是有意義的。

此外，與云計(jì)算不同的是，邊緣計(jì)算節(jié)點(diǎn)處于高度開放環(huán)境中，極易被俘獲或被黑客侵入[10]，為使邊緣集群具有更高的可用性和可靠性，還需進(jìn)一步使邊緣集群具有容忍拜占庭錯(cuò)誤的能力[11]。拜占庭錯(cuò)誤這一概念由Lamport等人[12]首次提出，一般地，將節(jié)點(diǎn)偽造信息惡意響應(yīng)的行為稱為拜占庭錯(cuò)誤，對(duì)應(yīng)的節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)。拜占庭容錯(cuò)是指發(fā)生拜占庭錯(cuò)誤時(shí)，邊緣集群仍然能夠正常提供服務(wù)的能力。由于Raft算法基于所有的錯(cuò)誤都是Fail-stop錯(cuò)誤的假設(shè)[13]，無法應(yīng)對(duì)拜占庭錯(cuò)誤，因此該算法在邊緣環(huán)境中發(fā)生拜占庭錯(cuò)誤時(shí)無法保證副本的一致性。

目前已經(jīng)有許多關(guān)于拜占庭容錯(cuò)算法的研究，其主要分為工作量證明(Proof of Work, PoW )[14]、權(quán)益證明( Proof of Stake, PoS)[15]等概率一致性算法和以基于狀態(tài)機(jī)復(fù)制技術(shù)的[16]絕對(duì)一致性算法。邊緣環(huán)境中采用的拜占庭式容錯(cuò)算法需要兼顧效率與可拓展性，尤其是在大規(guī)模邊緣網(wǎng)絡(luò)中，仍需具備低時(shí)延高吞吐量的特性。而目前已有的一致性拜占庭容錯(cuò)算法，尚不能同時(shí)滿足這些需求。常用于區(qū)塊鏈的PoW算法的效率太低，不適合高并發(fā)度的場景，且嚴(yán)重浪費(fèi)資源。PoS算法及其類似算法易導(dǎo)致“富豪統(tǒng)治的問題”，且這些算法概率一致性算法均依賴虛擬代幣，而在實(shí)際的邊緣場景中并不需要[17]。

由Castro等人[18]提出的PBFT(Practical Byzantine Fault Tolerance)算法是第一個(gè)實(shí)用的拜占庭容錯(cuò)算法，該算法可以在集群中存在少數(shù)拜占庭節(jié)點(diǎn)的場景中保持分布式系統(tǒng)的一致性，但該算法在消息傳遞過程中的時(shí)間復(fù)雜度為多項(xiàng)式級(jí)，在大量節(jié)點(diǎn)的邊緣環(huán)境中易產(chǎn)生廣播風(fēng)暴的問題，可拓展性較差。

本文的主要工作如下：針對(duì)邊緣環(huán)境易于發(fā)生拜占庭錯(cuò)誤從而破壞服務(wù)可用性的問題，提出并實(shí)現(xiàn)一種面向邊緣計(jì)算的拜占庭容錯(cuò)算法Edge-Raft。該算法對(duì)Raft算法進(jìn)行重新設(shè)計(jì)，在保留其易于理解實(shí)現(xiàn)的特性的同時(shí)，添加數(shù)字簽名、同步日志檢測、輪詢選舉、惰性投票、改進(jìn)的三階段投票等機(jī)制。采用Leader節(jié)點(diǎn)協(xié)調(diào)共識(shí)過程中的消息通信，將該算法的通信時(shí)間復(fù)雜度控制在O(N)。實(shí)驗(yàn)結(jié)果表明，與Raft算法相比，在犧牲一定性能的前提下，該算法具備拜占庭容錯(cuò)特性，與傳統(tǒng)的PBFT算法相比，該算法在保留Raft算法的可理解性的基礎(chǔ)上，具有更好的可拓展性。

1 Raft算法概述及分析

1.1 Raft算法概述

Lamport等人[19-22]為解決分布式副本的一致性問題，首次提出了Paxos算法，但該算法難以理解并工程實(shí)現(xiàn)[23]。為此，Ongaro等人[13]在Paxos算法基礎(chǔ)上提出了更易于理解實(shí)現(xiàn)的Raft算法。Raft算法是一種強(qiáng)領(lǐng)導(dǎo)者(Strong Leader)算法，主要分為Leader選舉和日志復(fù)制2個(gè)流程。

在Raft算法中，時(shí)間軸被分為若干任意長度的時(shí)間段，每段稱之為一個(gè)任期(Term)，任期編號(hào)為單調(diào)遞增的整數(shù)。Raft算法的任一節(jié)點(diǎn)均處于Leader、Follower、Candidate這3種狀態(tài)之一，僅在每個(gè)任期開始時(shí)進(jìn)行一次Leader選舉[24]。圖1描述了Raft算法的角色狀態(tài)轉(zhuǎn)換，初始狀態(tài)下所有節(jié)點(diǎn)均為Follower節(jié)點(diǎn)，當(dāng)Follower節(jié)點(diǎn)一段時(shí)間內(nèi)未收到Leader節(jié)點(diǎn)發(fā)送的心跳時(shí)，F(xiàn)ollower節(jié)點(diǎn)將自身角色轉(zhuǎn)變?yōu)镃andidate節(jié)點(diǎn)并發(fā)起Leader選舉請(qǐng)求，要求其他節(jié)點(diǎn)選擇自己為Leader節(jié)點(diǎn)，其他節(jié)點(diǎn)收到請(qǐng)求后會(huì)對(duì)Candidate節(jié)點(diǎn)進(jìn)行投票響應(yīng)，若該Candidate收到半數(shù)以上的贊同票，則晉升為Leader節(jié)點(diǎn)，否則進(jìn)行下一個(gè)任期的選舉。

圖1 Raft算法狀態(tài)轉(zhuǎn)換圖

圖2是Raft算法日志復(fù)制示意圖。正常狀態(tài)下，Leader節(jié)點(diǎn)負(fù)責(zé)為日志追加條目。Leader接收到來自客戶端的請(qǐng)求后，會(huì)將該請(qǐng)求追加至日志中，并向Follower節(jié)點(diǎn)廣播復(fù)制日志請(qǐng)求，一旦半數(shù)以上的服務(wù)器確認(rèn)復(fù)制了該條目，Leader節(jié)點(diǎn)就將該條目發(fā)送至狀態(tài)機(jī)執(zhí)行，并將執(zhí)行結(jié)果返回至客戶端。

圖2 Raft算法日志復(fù)制示意圖

1.2 Raft算法在邊緣環(huán)境中面臨的拜占庭問題

Raft算法基于所有發(fā)生的錯(cuò)誤均為Fail-stop錯(cuò)誤這一假設(shè)。在云計(jì)算中，云服務(wù)器處于集中監(jiān)控下，在大多情況下Raft算法足以保證數(shù)據(jù)的一致性，而邊緣環(huán)境中發(fā)生的拜占庭錯(cuò)誤Raft算法沒有能力應(yīng)對(duì)，從而無法保證服務(wù)的可用性與一致性。

在日志復(fù)制階段，拜占庭節(jié)點(diǎn)能夠偽裝成客戶端發(fā)送偽造請(qǐng)求，或偽裝成Leader節(jié)點(diǎn)向其他節(jié)點(diǎn)同步未知請(qǐng)求，從而對(duì)集群造成不可預(yù)知的危害，該過程如圖3所示[25]。此外，拜占庭節(jié)點(diǎn)可能會(huì)對(duì)收到的消息進(jìn)行篡改，從而破壞集群的一致性。當(dāng)拜占庭節(jié)點(diǎn)作為Leader節(jié)點(diǎn)時(shí)，可能在不斷發(fā)送心跳以維持自身Leader身份的同時(shí)，拒絕任何客戶端請(qǐng)求，從而無法對(duì)外提供任何服務(wù)，該過程如圖4所示。

圖3 偽造消息的拜占庭錯(cuò)誤示意圖

圖4 拒絕用戶請(qǐng)求的拜占庭錯(cuò)誤示意圖

在選舉階段，集群中任一節(jié)點(diǎn)均可發(fā)起Leader選舉，拜占庭節(jié)點(diǎn)可以不斷發(fā)送Leader選舉請(qǐng)求，使整個(gè)集群陷入不斷的選舉，破壞Raft算法的可用性[18]。此外，如圖5所示，拜占庭節(jié)點(diǎn)還可以偽造其余節(jié)點(diǎn)的投票或偽造最高任期的條目來上任為Leader，并通過復(fù)制自身不完整日志的方式來覆蓋其他節(jié)點(diǎn)日志列表中已經(jīng)達(dá)成共識(shí)的日志項(xiàng)，無法保證算法的安全性。

圖5 偽造最新的日志贏得選舉的拜占庭錯(cuò)誤示意圖

2 Edge-Raft算法

以上分析指出，Raft算法在易于發(fā)生拜占庭錯(cuò)誤的邊緣環(huán)境中存在著種種局限。因此，本文提出Edge-Raft算法，該算法對(duì)Raft算法的Leader選舉機(jī)制和日志復(fù)制機(jī)制進(jìn)行重新設(shè)計(jì)，在保留Raft算法的可理解性同時(shí)實(shí)現(xiàn)算法的拜占庭容錯(cuò)特性。

Edge-Raft算法可分解為Leader選舉和日志復(fù)制2個(gè)部分。針對(duì)日志結(jié)構(gòu)，Edge-Raft算法保留了Raft算法獨(dú)特的任期(Term)、索引(Index)的結(jié)構(gòu)。針對(duì)節(jié)點(diǎn)角色狀態(tài)，該算法僅保留Leader與Follower這2種角色狀態(tài)。

表1是在邊緣環(huán)境中存在的潛在拜占庭錯(cuò)誤及Edge-Raft算法增加相應(yīng)的應(yīng)對(duì)機(jī)制，具體實(shí)現(xiàn)細(xì)節(jié)見下文對(duì)應(yīng)章節(jié)。

表1 邊緣環(huán)境中潛在的拜占庭錯(cuò)誤及解決方案

該算法的容錯(cuò)率為1/3，即當(dāng)集群中節(jié)點(diǎn)總數(shù)為3f+1時(shí)，能夠容忍f個(gè)拜占庭節(jié)點(diǎn)存在，以下是詳細(xì)的證明。若邊緣節(jié)點(diǎn)總數(shù)為N，其中存在f個(gè)拜占庭節(jié)點(diǎn)，則剩余的非拜占庭節(jié)點(diǎn)數(shù)目為N-f個(gè)，此時(shí)僅需要收集到N-f個(gè)相同的消息即可向客戶端發(fā)出響應(yīng)，但這N-f條相同的消息中仍有可能存在最多f條拜占庭節(jié)點(diǎn)偽造的消息，為了讓正確的消息占其中的一半以上，以達(dá)到多數(shù)一致，即(N-f)/2>f,N>3f，也就是說當(dāng)集群中至少保持2/3以上的正常節(jié)點(diǎn)才能為用戶提供有效服務(wù)，以下各種機(jī)制均遵循該約束條件。

2.1 數(shù)字簽名

在邊緣環(huán)境下，若無任何保護(hù)機(jī)制，拜占庭節(jié)點(diǎn)能夠偽裝成其他節(jié)點(diǎn)或客戶端發(fā)送消息，且傳遞中的任一消息均存在被拜占庭節(jié)點(diǎn)篡改的風(fēng)險(xiǎn)。因此，Edge-Raft算法引入了數(shù)字簽名機(jī)制來防止消息篡改或身份偽造，為此Edge-Raft算法的節(jié)點(diǎn)需要滿足以下幾個(gè)條件：

1)邊緣集群中的任一節(jié)點(diǎn)和客戶端均擁有客戶端和所有節(jié)點(diǎn)的公鑰。

2)邊緣節(jié)點(diǎn)的私鑰僅自身持有。

3)邊緣節(jié)點(diǎn)無偽造密鑰的能力。

Edge-Raft采用ECDSA加密算法[26]用私鑰對(duì)發(fā)送消息的摘要進(jìn)行加密，其余節(jié)點(diǎn)收到該消息用對(duì)應(yīng)公鑰進(jìn)行解密，通過核對(duì)解密后得到的摘要與原摘要是否一致來核對(duì)消息是否被篡改，從而保證了算法的安全性。對(duì)消息摘要進(jìn)行加密的目的是為了減少傳輸過程的網(wǎng)絡(luò)消耗。

2.2 同步日志檢測

Raft算法中，Candidate節(jié)點(diǎn)具有全部的日志條目才可當(dāng)選為Leader節(jié)點(diǎn)，其具體約束條件如下：

(LastTC=LastTF&&LastIC≥LastIF)‖LastTC>LastTF

(1)

其中LastTC和LastTF分別為Candidate節(jié)點(diǎn)與Follower節(jié)點(diǎn)的最后一條日志的任期，LastIC與LastIF分別為Candidate節(jié)點(diǎn)與Follower節(jié)點(diǎn)最后一條日志的索引。滿足該約束條件的Candidate才具有當(dāng)選為Leader節(jié)點(diǎn)的資格。

在邊緣環(huán)境下，拜占庭節(jié)點(diǎn)具有在未擁有全部日志的情況下通過偽造日志條目來繞過該約束條件進(jìn)而當(dāng)選為Leader的能力，這會(huì)導(dǎo)致先前已經(jīng)達(dá)成一致的條目被覆蓋，或向整個(gè)集群強(qiáng)行寫入偽造條目，從而導(dǎo)致不可預(yù)知的結(jié)果。為此Edge-Raft算法引入了同步日志檢測機(jī)制，節(jié)點(diǎn)每次進(jìn)行日志寫入時(shí)會(huì)在消息的末尾添加一個(gè)哈希值，該哈希值由上一日志條目的哈希值LastHash與本次寫入的日志條目Entries一同生成，即：

Hash=hash(LastHash, Entries)

(2)

哈希算法的抗碰撞性保證了使用同一哈希算法的不同數(shù)據(jù)所生成的哈希值完全不同。這種當(dāng)前條目哈希值包含上一條目的信息的鏈?zhǔn)缴煞绞绞沟貌煌?jié)點(diǎn)的2條日志哈希值一致時(shí)，2個(gè)節(jié)點(diǎn)在此條目之前的所有日志條目均相同，若其中某一節(jié)點(diǎn)的日志缺失、增添或遭到篡改，根據(jù)哈希算法的抗碰撞性，該節(jié)點(diǎn)會(huì)生成完全不同的結(jié)果。進(jìn)行Leader選舉時(shí)，F(xiàn)ollower節(jié)點(diǎn)不僅對(duì)備選節(jié)點(diǎn)的最后一條日志的任期、索引進(jìn)行核對(duì)，還會(huì)向備選節(jié)點(diǎn)請(qǐng)求自身最后一次同步的日志條目對(duì)應(yīng)的哈希值HashC，并與自身最后一條日志的哈希值HashF進(jìn)行比對(duì)，2值相等時(shí)才能確定該節(jié)點(diǎn)擁有全部的日志條目。該檢測機(jī)制將原有的約束條件更新為：

(LastTC>LastTF‖(LastTC=LastTF&&LastIC≥LastIF))&&HashC=HashF

(3)

2.3 輪詢選舉

Edge-Raft算法摒棄了任一節(jié)點(diǎn)均可發(fā)起選舉的Leader選舉策略，將發(fā)起Leader選舉的權(quán)利賦予所有節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)在一定時(shí)間內(nèi)未收到Leader心跳時(shí)，會(huì)主動(dòng)向公式(4)確定的節(jié)點(diǎn)發(fā)送投票申請(qǐng)，推舉該節(jié)點(diǎn)作為Leader選舉的目標(biāo)節(jié)點(diǎn)：

NodeID=TmodN

(4)

其中T為投票節(jié)點(diǎn)任期，N為節(jié)點(diǎn)總數(shù)。該節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)請(qǐng)求Leader選舉投票所需的對(duì)應(yīng)條目的任期、索引、哈希值等判據(jù)，若判據(jù)核對(duì)成功則向該節(jié)點(diǎn)投贊成票，當(dāng)目標(biāo)節(jié)點(diǎn)接收到2f+1張以上的贊同票時(shí)，該節(jié)點(diǎn)晉升為Leader節(jié)點(diǎn)。這一機(jī)制保證了同一拜占庭節(jié)點(diǎn)不會(huì)連續(xù)2次作為Leader選舉的目標(biāo)節(jié)點(diǎn)，且Leader節(jié)點(diǎn)不會(huì)連續(xù)f+1個(gè)任期以上出現(xiàn)問題，從而保證了集群的活躍性。

邊緣節(jié)點(diǎn)動(dòng)態(tài)加入和退出是邊緣計(jì)算不同于云計(jì)算的一個(gè)重要特性，Edge-Raft算法大體上沿用了Raft算法的單節(jié)點(diǎn)成員變更機(jī)制(One Server ConfChange)來處理集群成員的動(dòng)態(tài)變更，每次僅向集群中加入或刪除一個(gè)節(jié)點(diǎn)，防止腦裂現(xiàn)象產(chǎn)生多個(gè)Leader節(jié)點(diǎn)，從而保證該算法的可用性[13]。

節(jié)點(diǎn)加入時(shí)，首先將自身公鑰發(fā)送至Leader節(jié)點(diǎn)，并從Leader節(jié)點(diǎn)上下載集群中其他邊緣節(jié)點(diǎn)的公鑰。同時(shí)，由于Leader節(jié)點(diǎn)仍在向日志內(nèi)寫入條目，該節(jié)點(diǎn)會(huì)在固定數(shù)目的輪次內(nèi)，多次從Leader節(jié)點(diǎn)上復(fù)制日志條目，以追趕Leader的同步日志，若最后一輪同步日志的耗時(shí)小于自身選舉定時(shí)器設(shè)定的時(shí)間，則認(rèn)為該節(jié)點(diǎn)與Leader節(jié)點(diǎn)的日志已足夠接近，可以將此節(jié)點(diǎn)加入至邊緣集群中，否則拋出異常。當(dāng)確定該節(jié)點(diǎn)能夠加入集群時(shí)，Leader節(jié)點(diǎn)更新節(jié)點(diǎn)數(shù)N的值，并將該節(jié)點(diǎn)的公鑰及集群配置更新至集群中其他邊緣節(jié)點(diǎn)。

節(jié)點(diǎn)退出或鏈接異常時(shí)，Leader節(jié)點(diǎn)無法接收到該節(jié)點(diǎn)對(duì)于心跳消息的回應(yīng)，在經(jīng)過一定預(yù)設(shè)輪次的重復(fù)發(fā)送后，Leader節(jié)點(diǎn)認(rèn)為該節(jié)點(diǎn)已經(jīng)脫離邊緣集群，此時(shí)Leader節(jié)點(diǎn)更新節(jié)點(diǎn)數(shù)N的值，并將該更新同步至集群中的其他邊緣節(jié)點(diǎn)。

2.4 惰性投票

Leader選舉時(shí)，Edge-Raft算法的節(jié)點(diǎn)不會(huì)接收其他節(jié)點(diǎn)的投票請(qǐng)求來為其他節(jié)點(diǎn)投票，而是顯現(xiàn)出一種“惰性”，即只有當(dāng)收到客戶端發(fā)送的強(qiáng)行更新Leader的請(qǐng)求或自身定時(shí)器時(shí)間內(nèi)未收到Leader所發(fā)送的心跳時(shí)，該節(jié)點(diǎn)認(rèn)定當(dāng)前的Leader存在故障，才會(huì)根據(jù)輪詢算法進(jìn)行主動(dòng)投票。至少總數(shù)2/3的節(jié)點(diǎn)都進(jìn)行投票后，整個(gè)輪次的投票才會(huì)產(chǎn)生結(jié)果，這一機(jī)制防止了拜占庭節(jié)點(diǎn)不斷發(fā)起不必要的選舉，使整個(gè)集群失效。

2.5 三階段日志同步

為防止拜占庭Leader節(jié)點(diǎn)向集群中同步未達(dá)成共識(shí)的日志條目，Edge-Raft算法引入了三階段式的日志同步機(jī)制。該機(jī)制將日志同步分為預(yù)寫入(PRE_APPEND)、寫入(APPEND)、執(zhí)行(COMMIT)這3個(gè)階段，將Raft算法現(xiàn)有的僅由Leader節(jié)點(diǎn)即可進(jìn)行同步?jīng)Q策的同步機(jī)制，更改為由所有節(jié)點(diǎn)共同決策，Leader節(jié)點(diǎn)僅用于協(xié)調(diào)各個(gè)節(jié)點(diǎn)間的消息傳遞。

預(yù)寫入階段，Leader節(jié)點(diǎn)廣播PRE_APPEND消息，F(xiàn)ollower節(jié)點(diǎn)接收到消息后核對(duì)消息附帶的時(shí)間戳、任期、索引及哈希值來驗(yàn)證自身是否具有與Leader節(jié)點(diǎn)相同的全部日志，若驗(yàn)證成功，證明該節(jié)點(diǎn)具有日志同步的條件，此時(shí)該節(jié)點(diǎn)會(huì)向Leader節(jié)點(diǎn)返回帶有自身簽名的消息作為回應(yīng)，當(dāng)Leader節(jié)點(diǎn)接收到2f+1條以上不同的回應(yīng)消息時(shí)，證明集群已經(jīng)對(duì)日志寫入這一操作達(dá)成一致，此時(shí)Leader節(jié)點(diǎn)進(jìn)入寫入階段。

寫入階段，Leader節(jié)點(diǎn)將接收到的2f+1個(gè)不同的簽名作為證據(jù)進(jìn)行打包作為APPEND消息廣播至所有節(jié)點(diǎn)，F(xiàn)ollower節(jié)點(diǎn)接收到消息后，確認(rèn)存在2f+1個(gè)不同的數(shù)字簽名時(shí)，認(rèn)為該消息已經(jīng)達(dá)到達(dá)成共識(shí)的條件。此時(shí)節(jié)點(diǎn)將該消息寫入日志，并向Leader返回?cái)y帶自身簽名的消息，作為寫入日志操作的證明。同樣地，當(dāng)Leader節(jié)點(diǎn)接收到2f+1條以上不同的回應(yīng)消息時(shí)，證明寫入日志成功，集群對(duì)該日志條目已達(dá)成共識(shí)，此時(shí)進(jìn)入執(zhí)行階段。

執(zhí)行階段，Leader節(jié)點(diǎn)同樣將2f+1個(gè)不同簽名打包作為日志條目已達(dá)成共識(shí)的證據(jù)，作為COMMIT消息廣播至集群中的所有節(jié)點(diǎn)，F(xiàn)ollower節(jié)點(diǎn)接收到消息后，確認(rèn)存在2f+1個(gè)不同的數(shù)字簽名時(shí)，認(rèn)為該日志條目在整個(gè)集群中已達(dá)成共識(shí)，此時(shí)節(jié)點(diǎn)將該日志條目交付給狀態(tài)機(jī)執(zhí)行，并將執(zhí)行結(jié)果返回給客戶端。

Edge-Raft算法采用數(shù)字簽名作為節(jié)點(diǎn)參與共識(shí)的證據(jù)，通過Leader節(jié)點(diǎn)收集并構(gòu)建證據(jù)包并廣播至Follower節(jié)點(diǎn)，每次同步日志條目時(shí)，必須通過核對(duì)簽名的方式確保存在2f+1個(gè)節(jié)點(diǎn)已經(jīng)對(duì)該條目達(dá)成一致，從而使所有節(jié)點(diǎn)都參與了日志同步的決策，保證了拜占庭Leader節(jié)點(diǎn)無法獨(dú)自進(jìn)行日志同步?jīng)Q策。

3 算法流程

3.1 Leader選舉

圖6和表2分別是Edge-Raft算法在Leader選舉過程中的消息傳遞示意圖及對(duì)應(yīng)的消息定義。

圖6 Edge-Raft算法Leader選舉過程消息傳遞示意圖

表2 Leader選舉過程中消息定義

表2中REQVOTE、REQVOTE-RES、VOTE、VOTE-RES為消息標(biāo)識(shí)符，LastT、LastI分別為當(dāng)前節(jié)點(diǎn)最后一次同步的日志條目的任期和索引，T、I為節(jié)點(diǎn)當(dāng)前任期和索引，HashC為根據(jù)請(qǐng)求返回的哈希值，Sign為節(jié)點(diǎn)對(duì)當(dāng)前節(jié)點(diǎn)ID的數(shù)字簽名，E為節(jié)點(diǎn)收集到2/3節(jié)點(diǎn)總數(shù)的票數(shù)時(shí)，將數(shù)字簽名打包生成的證據(jù)包，用來證明該節(jié)點(diǎn)確實(shí)收到了2/3以上節(jié)點(diǎn)的投票。Edge-Raft算法的Leader選舉部分的算法描述如算法1所示。

算法1 Leader選舉算法

初始狀態(tài)下，所有邊緣節(jié)點(diǎn)均為Follower節(jié)點(diǎn)：

1)節(jié)點(diǎn)在定時(shí)器超時(shí)仍未收到Leader心跳，通過公式(4)確定目標(biāo)節(jié)點(diǎn)，向目標(biāo)節(jié)點(diǎn)發(fā)送REQVOTE消息，啟動(dòng)選舉計(jì)時(shí)器；2)目標(biāo)節(jié)點(diǎn)會(huì)根據(jù)REQVOTE消息中攜帶的LastT、LastI生成并返回REQVOTE-RES消息；3)接收REQVOTE-RES消息，若目標(biāo)節(jié)點(diǎn)滿足邊界條件式(3)，則發(fā)送VOTE消息為其投贊成票；4)目標(biāo)節(jié)點(diǎn)接收到2f+1個(gè)贊同票時(shí)，晉升為Leader，將VOTE消息中附帶的Sign打包為E并向整個(gè)集群廣播VOTE-RES消息；5)接收到VOTE-RES消息的節(jié)點(diǎn)，對(duì)E進(jìn)行解析，確認(rèn)其中確實(shí)存在2f+1個(gè)不同的節(jié)點(diǎn)數(shù)字簽名時(shí)，更新自身Leader的ID及任期，停止選舉定時(shí)器，完成一輪Leader選舉；6)若選舉定時(shí)器超時(shí)后仍未選出Leader，此時(shí)節(jié)點(diǎn)將自身任期加1，忽略比自身任期小的節(jié)點(diǎn)發(fā)送的消息，并開始下一輪選舉，若在選舉過程中接收到比自身任期大的Leader發(fā)送的心跳，節(jié)點(diǎn)會(huì)向其請(qǐng)求上任的證據(jù)包，若對(duì)證據(jù)包解析成功，則更新自身Leader，完成Leader選舉。

圖7為Leader選舉過程的流程圖，相比于Raft算法，盡管Edge-Raft算法在Leader選舉階段增加了一次廣播消息，增加了一部分通信消耗，但仍將通信時(shí)間復(fù)雜度控制在了與Raft算法相同的O(N)，同時(shí)避免了Raft算法在Leader選舉階段可能發(fā)生的拜占庭錯(cuò)誤。

圖7 Edge-Raft算法Leader選舉流程圖

3.2 日志復(fù)制

Edge-Raft算法在日志復(fù)制的過程中采用了3階段式日志同步，以防止?jié)撛诘陌菡纪eader進(jìn)行的將未達(dá)成共識(shí)的日志進(jìn)行同步的行為。圖8和表3分別是Edge-Raft算法在日志復(fù)制時(shí)的消息傳遞示意圖及對(duì)應(yīng)的消息定義。

圖8 Edge-Raft算法日志復(fù)制時(shí)消息傳遞示意圖

表3 日志復(fù)制過程中的消息定義

表3中PREAPPEND、PREAPPEND-RES、APPEND、APPEND-RES、COMMIT、COMMIT-RES為消息標(biāo)識(shí)符，T為節(jié)點(diǎn)當(dāng)前任期，LastT、LastT、LastHash分別為節(jié)點(diǎn)最后一次同步日志條目的任期索引及哈希值，Ts為客戶端發(fā)送請(qǐng)求時(shí)附帶的時(shí)間戳，用于作為請(qǐng)求的唯一性標(biāo)識(shí)，Sign為節(jié)點(diǎn)的數(shù)字簽名，E為節(jié)點(diǎn)收集到2/3節(jié)點(diǎn)總數(shù)的數(shù)字簽名時(shí)，將數(shù)字簽名打包生成的證據(jù)包，Hash為本次同步日志條目生成的哈希值，Result為狀態(tài)機(jī)對(duì)請(qǐng)求的處理結(jié)果。Edge-Raft算法日志復(fù)制部分的算法描述如算法2所示。

算法2 日志復(fù)制算法

1)客戶端生成并廣播帶時(shí)間戳的APPEND-ENTRIES請(qǐng)求；2)節(jié)點(diǎn)接收到APPEND-ENTRIES請(qǐng)求時(shí)，若該消息Ts大于上次同步條目的Ts，將該條目存儲(chǔ)至寄存隊(duì)列，準(zhǔn)備進(jìn)行同步；3)Leader節(jié)點(diǎn)進(jìn)入預(yù)準(zhǔn)備階段，向所有節(jié)點(diǎn)廣播PREAPPEND消息；4)Follower節(jié)點(diǎn)接收到PREAPPEND消息后核對(duì)該消息的Ts與自身寄存器Ts是否一致，節(jié)點(diǎn)與LastT、LastI,對(duì)應(yīng)位置的Hash值與LastHash是否一致，若均一致，向Follower節(jié)點(diǎn)返回PREAPPEND-RES消息；5)Leader節(jié)點(diǎn)接收到2f+1條PREAPPEND-RES消息后，進(jìn)入準(zhǔn)備階段，將消息中附帶的Sign打包為E并廣播APPEND消息；6)Follower節(jié)點(diǎn)接收到APPEND消息后對(duì)E進(jìn)行解析，當(dāng)確認(rèn)其中確實(shí)存在2f+1個(gè)不同的節(jié)點(diǎn)數(shù)字簽名時(shí)，將寄存器中條目寫入自身日志中，并向Leader節(jié)點(diǎn)返回APPEND-RES消息；7)Leader節(jié)點(diǎn)接收到2f+1條APPEND-RES消息后，進(jìn)入提交階段，將同步的日志條目交付給狀態(tài)機(jī)執(zhí)行，同時(shí)將消息中附帶的Sign打包為E并廣播COMMIT消息；8)Follower節(jié)點(diǎn)接收到COMMIT消息后對(duì)E進(jìn)行解析，當(dāng)確認(rèn)其中確實(shí)存在2f+1個(gè)不同的節(jié)點(diǎn)數(shù)字簽名時(shí)，將同步的日志條目交付給狀態(tài)機(jī)執(zhí)行，得到執(zhí)行結(jié)果Result；9)節(jié)點(diǎn)生成COMMIT-RES消息，將狀態(tài)機(jī)執(zhí)行結(jié)果Result返回至客戶端。

Edge-Raft算法更改了Raft算法的日志同步機(jī)制，使所有節(jié)點(diǎn)共同參與同步?jīng)Q策，Leader節(jié)點(diǎn)的作用僅為協(xié)調(diào)消息傳遞，防止了拜占庭節(jié)點(diǎn)強(qiáng)行同步未達(dá)成一致的日志項(xiàng)。Edge-Raft算法的日志同步機(jī)制雖然存在3次消息廣播，但由于僅有單一節(jié)點(diǎn)發(fā)起消息廣播，其時(shí)間復(fù)雜度仍為O(N)。與Raft算法相比，犧牲了一部分的性能，但實(shí)現(xiàn)了抵抗拜占庭錯(cuò)誤的特性。

3.3 客戶端交互

除以上2點(diǎn)外，邊緣節(jié)點(diǎn)在與客戶端交互的過程中，拜占庭節(jié)點(diǎn)作為Leader節(jié)點(diǎn)可能發(fā)生拒絕響應(yīng)甚至篡改響應(yīng)結(jié)果惡意響應(yīng)客戶端的情況。因此，Edge-Raft算法與客戶端交互要求所有節(jié)點(diǎn)將執(zhí)行結(jié)果經(jīng)簽名后直接反饋至客戶端，客戶端接收到響應(yīng)消息后，通過校檢響應(yīng)消息的數(shù)字簽名以保證響應(yīng)消息未被篡改，及每個(gè)節(jié)點(diǎn)僅響應(yīng)一次客戶端請(qǐng)求。

當(dāng)集群內(nèi)最多僅允許存在f個(gè)拜占庭節(jié)點(diǎn)時(shí)，若客戶端接收到f+1個(gè)相同的響應(yīng)結(jié)果，則可認(rèn)為該響應(yīng)結(jié)果是正確的。由于僅存在f個(gè)拜占庭節(jié)點(diǎn)，針對(duì)單條請(qǐng)求，當(dāng)客戶端接收到f+1條響應(yīng)時(shí)，其中必然有一條是正確的響應(yīng)，若f+1條響應(yīng)一致，則這些響應(yīng)一定是正確的。

此外，客戶端在一定時(shí)間內(nèi)未收到響應(yīng)結(jié)果時(shí)會(huì)重新發(fā)送請(qǐng)求，當(dāng)超過設(shè)定的最大重傳次數(shù)i時(shí)，客戶端會(huì)向所有節(jié)點(diǎn)廣播消息來請(qǐng)求更換Leader，節(jié)點(diǎn)接收到該消息后會(huì)初始化自身的Leader信息，并拒絕接收當(dāng)前Leader所發(fā)出的心跳，從而觸發(fā)惰性投票機(jī)制，開始新一輪的選舉。圖9是客戶端交互階段的流程圖。

圖9 客戶端交互流程圖

4 算法分析

4.1 安全性(Safety)

在任何場景下，Edge-Raft算法都需要保證被篡改的日志條目無法在非拜占庭節(jié)點(diǎn)間達(dá)成一致。Edge-Raft算法通過以下幾種機(jī)制來保證算法在邊緣環(huán)境中的安全性。

引入了數(shù)字簽名來實(shí)現(xiàn)消息篡改檢測和防止身份偽造。Edge-Raft算法的密碼學(xué)基礎(chǔ)是穩(wěn)固的。集群中傳遞的任一消息均攜帶了發(fā)送者的數(shù)字簽名，且簽名所用私鑰僅為簽名節(jié)點(diǎn)所有，集群中的每個(gè)節(jié)點(diǎn)均可用公鑰驗(yàn)證消息是否被篡改，由于所有的節(jié)點(diǎn)均無偽造密鑰的能力，從而確保了拜占庭節(jié)點(diǎn)無法偽造身份，且無法生成有效的客戶端命令。

針對(duì)Leader節(jié)點(diǎn)日志完整性問題，Edge-Raft算法采用了同步日志檢測機(jī)制，將所有節(jié)點(diǎn)最后同步的日志條目的哈希值與Leader日志中對(duì)應(yīng)任期和索引的日志條目的哈希值進(jìn)行核對(duì)，確保了在Leader選舉階段當(dāng)選的節(jié)點(diǎn)的日志列表必定擁有所有已經(jīng)達(dá)成共識(shí)的全部日志條目，從而避免了拜占庭節(jié)點(diǎn)通過偽造最新的日志條目來晉升為Leader，并用自身不完整的日志將已同步的日志覆蓋的行為。

為了保證日志復(fù)制過程中的安全性，Edge-Raft算法采用三階段式同步協(xié)議，三階段消息均需在同一任期內(nèi)完成，且完成時(shí)間需小于心跳定時(shí)器的時(shí)間。預(yù)寫入階段確保了存在至少2f+1個(gè)節(jié)點(diǎn)對(duì)寫入日志這一操作達(dá)成一致。寫入階段確保了存在至少2f+1個(gè)節(jié)點(diǎn)達(dá)成了日志條目寫入的一致性。提交階段確保足夠數(shù)目的Follower已經(jīng)接收并通過準(zhǔn)備階段的證據(jù)包，從而防止再次接收相同任期和索引的日志條目，把已經(jīng)同步的日志項(xiàng)覆蓋，從而保證算法的安全性。

4.2 活性(Liveness)

Edge-Raft算法與Raft算法類似，作為一種強(qiáng)領(lǐng)導(dǎo)式算法，任意時(shí)刻集群內(nèi)部都僅存在一個(gè)Leader節(jié)點(diǎn)來維持整個(gè)集群的正常工作，當(dāng)Leader為非拜占庭節(jié)點(diǎn)時(shí)，Leader通過定時(shí)發(fā)送心跳的方式維持自身Leader身份，進(jìn)而維持整個(gè)集群的活性，當(dāng)Leader節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)時(shí)，為了確保拜占庭節(jié)點(diǎn)不會(huì)無限期地控制整個(gè)集群，若客戶端在規(guī)定時(shí)間內(nèi)未得到正確的反饋，客戶端將向所有節(jié)點(diǎn)廣播更新Leader請(qǐng)求來更換Leader節(jié)點(diǎn)。

進(jìn)行Leader選舉時(shí)，Edge-Raft引入以下2個(gè)特性來保持集群的活性，首先每個(gè)任期內(nèi)僅存在NodeID=TmodN所確定的一個(gè)候選者，這保證了Leader不會(huì)在連續(xù)f個(gè)任期以上出現(xiàn)問題，避免了拜占庭節(jié)點(diǎn)連續(xù)進(jìn)行Leader選舉判定。其次，節(jié)點(diǎn)必須收集到2f+1個(gè)選舉請(qǐng)求時(shí)才可發(fā)起選舉，這保障了拜占庭節(jié)點(diǎn)無法隨意啟動(dòng)Leader選舉，進(jìn)而維持了整個(gè)集群的活性。

5 實(shí)驗(yàn)結(jié)果

5.1 實(shí)驗(yàn)設(shè)置

本文采用Python3.7對(duì)Edge-Raft算法進(jìn)行實(shí)現(xiàn)，其中采用SHA-256算法作為消息的摘要算法，采用ECDSA算法對(duì)消息進(jìn)行數(shù)字簽名，采用Socket機(jī)制進(jìn)行節(jié)點(diǎn)間通信，從而將該算法運(yùn)行于邊緣設(shè)備上進(jìn)行多次實(shí)驗(yàn)。本節(jié)主要從Leader選舉、日志復(fù)制、通信開銷、吞吐量、時(shí)延5個(gè)方面來對(duì)該算法的性能進(jìn)行分析，并與Raft算法及目前在物聯(lián)網(wǎng)中最常用的拜占庭容錯(cuò)算法PBFT進(jìn)行對(duì)比，從而驗(yàn)證該算法的有效性及優(yōu)勢[27]。

5.2 Leader選舉耗時(shí)

圖10描述了Raft算法與Edge-Raft算法在不同節(jié)點(diǎn)規(guī)模的邊緣集群下的Leader選舉耗時(shí)。與Raft算法相比，Edge-Raft算法的選舉耗時(shí)高于Raft算法約25%，這是由于Raft算法在選舉開始時(shí)，Candidate節(jié)點(diǎn)僅采用一輪廣播消息即可完成當(dāng)前Term的投票收集，而Edge-Raft算法中，F(xiàn)ollower僅會(huì)在認(rèn)定當(dāng)前Leader失效時(shí)才會(huì)進(jìn)行投票，這在進(jìn)行一輪廣播消息的基礎(chǔ)上，F(xiàn)ollower節(jié)點(diǎn)在等待投票定時(shí)器超時(shí)過程中增加了一定的時(shí)間損耗。此外由于增加了數(shù)字簽名及摘要等必要的信息，使得消息的體積增加，從而增加了消息的傳輸耗時(shí)。

圖10 Leader選舉耗時(shí)對(duì)比圖

5.3 日志復(fù)制耗時(shí)

圖11描述了Raft算法與Edge-Raft算法在不同節(jié)點(diǎn)規(guī)模下單次日志復(fù)制的同步耗時(shí)。與Raft算法相比，Edge-Raft算法在進(jìn)行單次日志復(fù)制時(shí)所消耗的時(shí)間約為Raft算法的4倍。這是因?yàn)樵赗aft算法中同步條目時(shí)，Leader節(jié)點(diǎn)僅需采用一輪消息廣播即可完成日志復(fù)制，而Edge-Raft算法進(jìn)行日志同步時(shí)，Leader節(jié)點(diǎn)需要進(jìn)行3輪廣播操作，且發(fā)送的消息中包含了節(jié)點(diǎn)簽名、哈希值等信息，增加了數(shù)據(jù)包的體積，從而增加了一部分通信開銷。為了防止在消息的傳輸過程中遭到篡改或偽造，該算法采用了數(shù)字簽名、消息摘要等機(jī)制，這也進(jìn)一步加大了時(shí)間開銷。

圖11 日志復(fù)制耗時(shí)對(duì)比圖

相較于Raft算法，Edge-Raft算法在損失了一定性能的基礎(chǔ)上實(shí)現(xiàn)了拜占庭容錯(cuò)的特性，從而保證了該算法能夠應(yīng)用于邊緣環(huán)境中，與此相比，本文認(rèn)為犧牲的部分性能是值得的。

5.4 同步通信開銷

圖12描述了PBFT算法與Edge-Raft算法在不同節(jié)點(diǎn)規(guī)模的邊緣環(huán)境中，在進(jìn)行日志同步時(shí)節(jié)點(diǎn)間通信次數(shù)的對(duì)比，實(shí)驗(yàn)表明，當(dāng)節(jié)點(diǎn)規(guī)模增加時(shí)PBFT的通信次數(shù)要顯著高于Edge-Raft算法。這是由于在PBFT算法中，當(dāng)節(jié)點(diǎn)總數(shù)為n時(shí)，其總通信次數(shù)為：

圖12 節(jié)點(diǎn)通信次數(shù)對(duì)比圖

f(n)=1+(n-1)+(n-1)2+n(n-1)+n=2n2-n+1

其通信時(shí)間復(fù)雜度為O(n2)。而Edge-Raft算法的總通信次數(shù)為：

f(n)=n+2(n-1)+2(n-1)+2(n-1)=7n-6

其通信時(shí)間復(fù)雜度為O(N)，這導(dǎo)致了隨著節(jié)點(diǎn)規(guī)模的擴(kuò)大，PBFT算法所增加的通信次數(shù)要顯著高于Edge-Raft算法，會(huì)給網(wǎng)絡(luò)環(huán)境帶來更高的壓力。

圖13描述了PBFT算法與Edge-Raft算法在不同節(jié)點(diǎn)規(guī)模下進(jìn)行單次共識(shí)的通信開銷，實(shí)驗(yàn)表明，在節(jié)點(diǎn)規(guī)模較小時(shí)，兩者通信開銷差別不大，隨著節(jié)點(diǎn)規(guī)模增加，PBFT算法的通信開銷的增量要遠(yuǎn)高于Edge-Raft算法。這是由于PBFT算法的通信次數(shù)呈多項(xiàng)式級(jí)增加，而Edge-Raft算法的通信次數(shù)呈線性級(jí)增加，節(jié)點(diǎn)間每次通信時(shí)，會(huì)對(duì)消息進(jìn)行加密，并附上數(shù)字簽名，通信次數(shù)越多該部分開銷在總的通信開銷中占比越大。因此，在大規(guī)模邊緣集群中，Edge-Raft算法與PBFT算法相比，能夠顯著降低通信開銷，緩解了網(wǎng)絡(luò)壓力。

圖13 通信開銷對(duì)比圖

5.5 處理吞吐量

吞吐量衡量了單位時(shí)間內(nèi)算法處理客戶端請(qǐng)求的效率，在本文實(shí)驗(yàn)中體現(xiàn)為單位時(shí)間內(nèi)達(dá)成共識(shí)的日志條目數(shù)。圖14描述了PBFT與Edge-Raft算法在不同節(jié)點(diǎn)規(guī)模下的吞吐量的對(duì)比結(jié)果，PBFT與Edge-Raft算法的吞吐量隨著節(jié)點(diǎn)數(shù)量的增多均有一定程度的降低，在節(jié)點(diǎn)規(guī)模較小時(shí)二者的吞吐量相差不大，而隨著節(jié)點(diǎn)數(shù)目不斷增多，Edge-Raft算法的吞吐量會(huì)逐漸優(yōu)于PBFT。這是由于PBFT算法在共識(shí)時(shí)消息傳遞時(shí)算法的時(shí)間復(fù)雜度為O(N2)，而Edge-Raft算法消息傳遞的時(shí)間復(fù)雜度為O(N)，在大規(guī)模邊緣環(huán)境中Edge-Raft算法的同步效率要優(yōu)于PBFT算法。

圖14 Edge-Raft與PBFT的吞吐量對(duì)比圖

5.6 達(dá)成一致時(shí)延

共識(shí)時(shí)延指從客戶端發(fā)送請(qǐng)求到客戶端收到正常響應(yīng)回復(fù)這一過程所消耗的時(shí)間，如圖15所示，PBFT算法與Edge-Raft算法在節(jié)點(diǎn)數(shù)目較少時(shí)，其時(shí)延差距并不明顯，但由于通信成本的差異，PBFT算法的時(shí)延隨著集群規(guī)模的擴(kuò)大呈指數(shù)趨勢上升，而Edge-Raft算法的時(shí)延呈線性上升，這表明與PBFT算法相比Edge-Raft算法具有更好的可拓展性。

圖15 Edge-Raft與PBFT的時(shí)延對(duì)比圖

6 結(jié)束語

本文提出了一種面向邊緣計(jì)算應(yīng)用的拜占庭容錯(cuò)共識(shí)算法——Edge-Raft，該算法基于Raft算法，在保留現(xiàn)有Raft算法可理解性的同時(shí)，使其具有拜占庭容錯(cuò)的特性，從而保證了該算法在邊緣環(huán)境中的安全性與活性。實(shí)驗(yàn)結(jié)果表明，相比于僅支持非拜占庭容錯(cuò)的Raft算法，該算法在犧牲一定性能的前提下具備了拜占庭容錯(cuò)的特性。相比于主流的拜占庭容錯(cuò)分布式共識(shí)算法PBFT，Edge-Raft算法在不失性能的前提下具備同Raft一致的可理解性，且可拓展性強(qiáng)，適用于大規(guī)模邊緣節(jié)點(diǎn)網(wǎng)絡(luò)。

接下來的研究工作中，筆者將進(jìn)一步研究如何對(duì)該算法的消息傳遞進(jìn)行優(yōu)化，及采用高效的簽名算法等方式以進(jìn)一步提升該算法的性能。當(dāng)向邊緣集群中增加新節(jié)點(diǎn)時(shí)，如何在邊緣集群運(yùn)行時(shí)更迅速地動(dòng)態(tài)擴(kuò)充集群也是未來需要進(jìn)行研究的方向之一。