伍桂鋒，胡 伐，曾 新，楊鄧奇，李曉偉

（大理大學數(shù)學與計算機學院，云南大理 671003）

區(qū)塊鏈技術(shù)是密碼學、分布式系統(tǒng)和存儲系統(tǒng)的綜合應(yīng)用，具有不可篡改、表示價值所需的唯一性、智能合約和去中心自組織這四大特性，其可以廣泛應(yīng)用于各種分布式賬本系統(tǒng)〔1-2〕。區(qū)塊鏈根據(jù)開放對象的不同可以分為公有鏈、私有鏈和聯(lián)盟鏈。聯(lián)盟鏈因具有一定的準入機制，進一步提高了應(yīng)用的可信度，是區(qū)塊鏈3.0 的一個重要方向〔3〕。

共識算法是區(qū)塊鏈要解決的關(guān)鍵問題。根據(jù)區(qū)塊鏈性質(zhì)的不同，區(qū)塊鏈的共識算法也有所區(qū)別〔4〕。存在惡意節(jié)點的環(huán)境中共識算法一般采用拜占庭容錯（Byzantine fault tolerance，BFT）算法，如實用拜占庭容錯（practice Byzantine fault tolerance，PBFT）算法〔5〕及HotStuff 算法〔6〕，這兩種算法可以在惡意節(jié)點的攻擊下達成正確的共識。同時在這種場景下多位學者也提出了改進的策略〔7-9〕。在節(jié)點可信的環(huán)境中一般采用非拜占庭容錯也稱作崩潰容錯（crash fault tolerance，CFT）算法，具有代表性的算法有Paxos〔10〕、Raft〔11〕。由于Raft 算法簡明高效，已成為聯(lián)盟鏈中默認的共識算法。本文詳細分析Raft 相關(guān)算法，總結(jié)出已有Raft 改進算法的優(yōu)缺點。

K-Raft（Kademlia-Raft）算法由Wang 等〔12〕設(shè)計，通過在分布式網(wǎng)絡(luò)中加入Kademlia 的P2P 層，檢查網(wǎng)絡(luò)節(jié)點之間的ping 值，通過異或運算建立一種分布式哈希表保存節(jié)點信息使內(nèi)部形成一個完整拓撲結(jié)構(gòu)。該算法每個節(jié)點的內(nèi)部保存一個紅黑樹結(jié)構(gòu)的K-Bucket，在選舉的過程中，節(jié)點優(yōu)先從K-Bucket 中進行選舉活動，在未獲取到超過半數(shù)的節(jié)點投票情況下才會再進行全局選舉。這樣會減少節(jié)點狀態(tài)的切換，從而使分布式網(wǎng)絡(luò)選舉過程得到穩(wěn)定。B-Raft（Byzantine fault-tolerant Raft）算法由Tian 等〔13〕設(shè)計，算法運用Schnorr 進行數(shù)字簽名（一種橢圓曲線的非對稱加密算法），在每個節(jié)點初始的時候加入證書。在選舉的過程中，節(jié)點收到選舉信號后，對信息進行驗證。如果驗證通過則進行相應(yīng)的投票，以此保證信息沒有被篡改，保證符合BFT 節(jié)點能當選。LC-Raft（log calculation Raft）算法由馬博韜等〔14〕設(shè)計，算法通過節(jié)點內(nèi)部計算歷史日志記錄的方式，將各節(jié)點的日志中對心跳信號的反應(yīng)情況保存在最近的時間節(jié)點內(nèi)，如節(jié)點報錯、節(jié)點當選以及日志異常等情況。對上述這些情況，算法通過打分機制來定義節(jié)點的穩(wěn)定性。

上述工作大都只考慮了影響Raft 算法的網(wǎng)絡(luò)因素，然而實際Raft 算法還應(yīng)考慮節(jié)點自身的影響因素。本文考慮在節(jié)點多維度影響因素下研究Raft算法，提出一種新的基于多維向量的聯(lián)盟鏈共識算法——MV-Raft（multidimensional vector Raft）。算法在某些特定場景下采用設(shè)定多維特征值向量的方式，解決共識達成的速度問題以及日志同步問題，提高Raft 算法的效率。

1 背景知識

1.1 Raft 的概念Raft 算法是由Ongaro 和Ousterhout于2014 年在Raft：In Search of an Understandable Consensus Algorithm 論文中提出的，其是在Paxos 算法的基礎(chǔ)上結(jié)合實際工程的改進。Paxos 算法由Lamport 于1998 年在The Part-Time Parliament 論文中首次公開，在實際的工程中應(yīng)用于國內(nèi)外多個系統(tǒng)中。但是Paxos 算法晦澀難懂，工程實現(xiàn)上也有難度，所以在Paxos 算法的基礎(chǔ)上開發(fā)出了Raft 算法。在近些年的工程應(yīng)用以及研究中，Raft 算法成為很多分布式系統(tǒng)的基礎(chǔ)〔15-18〕，如開源系統(tǒng)Etcd、Consul 及Google Omega 調(diào)度架構(gòu)，國內(nèi)阿里巴巴的DLedger 等。在區(qū)塊鏈中，聯(lián)盟鏈HyperLedger Fabric的默認共識算法機制就是Raft。

Raft 算法易于理解和實現(xiàn)，其原理如下：在一個網(wǎng)絡(luò)域中存在著多個節(jié)點，它們可能存在3 種狀態(tài)，跟隨者（follower）、領(lǐng)導者（leader）和候選者（candidate）。跟隨者節(jié)點會定時向領(lǐng)導者節(jié)點發(fā)送心跳信息，一旦跟隨者發(fā)現(xiàn)接收不到領(lǐng)導者節(jié)點的心跳返回信息，它就會將狀態(tài)機轉(zhuǎn)為候選者節(jié)點。在成為候選者狀態(tài)時，節(jié)點內(nèi)部會激活選舉隨機定時器。通常這個定時器的時間范圍在［150，300］，在這個隨機時間之后，候選者節(jié)點會發(fā)送選舉信號廣播給其他節(jié)點（信號中包含了它的版本號和任期）進行拉取選票。節(jié)點狀態(tài)機的轉(zhuǎn)換過程見圖1。

圖1 Raft 選舉狀態(tài)機的轉(zhuǎn)換

在以上過程中，得到滿足條件票數(shù)（通常是超過半數(shù)的選票，以免使系統(tǒng)產(chǎn)生腦裂即多個領(lǐng)導者）的候選者當選為領(lǐng)導者節(jié)點。當選的領(lǐng)導者節(jié)點會向所有節(jié)點發(fā)送當選的信號從而結(jié)束競選過程，之后由領(lǐng)導者節(jié)點發(fā)起日志復制過程。由于不同時期的日志不同，所以日志需要分塊，系統(tǒng)中稱之為日志條目。這些日志根據(jù)不同的任期進行壓縮分塊以及快照，跟隨者節(jié)點向領(lǐng)導者節(jié)點發(fā)送心跳信號的時候會校驗這些日志，并由此同步更新當前任期日志條目。完整的Raft 流程見圖2。

圖2 Raft 運行流程

綜上，Raft 算法是分布式基礎(chǔ)理論BASE 理論的一種最佳實踐，即算法同步了所有節(jié)點的信息滿足了最終一致性（eventually consistent）；在狀態(tài)轉(zhuǎn)換過程中滿足了軟狀態(tài)的特性（soft state）；領(lǐng)導者節(jié)點崩潰也可快速恢復從而滿足了基本可用（basically available）。

1.2 多維向量的概念與應(yīng)用多維向量是一種數(shù)學上的概念，將不同維度的統(tǒng)計數(shù)據(jù)組成多維向量，而多維向量是在多維空間的點。其在現(xiàn)實中的意義可以描述事物在多維空間中的關(guān)系，有很廣泛的用途。在多維空間中兩個多維向量間的距離可以表達出事物的關(guān)聯(lián)度。在機器學習中K-Means 算法利用的是多維向量的歐氏距離的原理，對抽象節(jié)點進行聚類。相鄰近節(jié)點間的共性一定更多，所以鄰近節(jié)點間交互更加便利。

根據(jù)上述思想可以推斷出：在分布式網(wǎng)絡(luò)中，如果不同的節(jié)點之間由多維向量所計算的歐氏距離較小，則它們之間相似度較高。相似節(jié)點間進行操作消耗的各類資源會比歐氏距離大的節(jié)點間操作所消耗的資源少。在大量的實踐中，人們發(fā)現(xiàn)只要提取的特征值是正確的，那么歐氏距離較小的節(jié)點之間的相似度較高，從而容易歸類讓節(jié)點間操作更節(jié)省資源。

2 算法設(shè)計與分析

本節(jié)基于多維向量特征值提出MV-Raft 算法并從多維向量的處理過程、節(jié)點選舉優(yōu)化、日志復制優(yōu)化和新節(jié)點的處理這4 個方面來詳細描述，最后分析整個算法過程中對分布式系統(tǒng)的影響。算法中節(jié)點在初始化或新加入分布式系統(tǒng)時提取特征值和做初始化計算。過程如下：首先依據(jù)影響因素選取m 個特征值組成特征值向量，將其放入節(jié)點所在局域網(wǎng)，將上述特征值向量廣播全網(wǎng)絡(luò)，每個節(jié)點計算出歐氏距離并保存歐氏距離最小的節(jié)點放入緩存數(shù)組以便選舉和同步時使用。在節(jié)點內(nèi)部放入定時器重復上述流程，對新加入節(jié)點也重復上述過程。流程見圖3。

圖3 算法的整體流程

經(jīng)過上述流程后，每個節(jié)點會緩存歐氏距離近的節(jié)點，整個系統(tǒng)在選舉和同步日志時會得到性能上的優(yōu)化。領(lǐng)導者節(jié)點會根據(jù)內(nèi)部的緩存數(shù)組來操作，節(jié)點壓力也會減輕。詳細過程如下：首先根據(jù)每個節(jié)點的內(nèi)部數(shù)組進行選舉；其次，若獲得足夠選票節(jié)點可直接當選，若不夠則通過P2P 網(wǎng)絡(luò)全局獲取選票；最后再通過內(nèi)部數(shù)組同步日志，同步過的節(jié)點再調(diào)用其內(nèi)部數(shù)組記錄同步日志直到全局完成日志同步。領(lǐng)導者節(jié)點的操作見圖4。

圖4 算法優(yōu)化示意

2.1 算法多維向量處理過程

2.1.1 特征值提取為特征值向量 在初始化一個節(jié)點時，首先依據(jù)業(yè)務(wù)的要求進行數(shù)據(jù)挖掘，定義m 個特征值T＝｛t1，t2，t3，…，tm｝，并且根據(jù)它的重要性乘上相應(yīng)的權(quán)重系數(shù)｛ρ1，ρ2，ρ3，…，ρm｝，最后得到特征值向量為｛ρ1t1，ρ2t2，ρ3t3，…，ρmtm｝，簡化表示為：

得到的向量值存入節(jié)點對象的dis 字段中。依此類推遍歷對所有節(jié)點進行向量的計算組合。

2.1.2 對特征值向量計算歐氏距離 在所有節(jié)點得到了m 個特征值向量之后，進入整個系統(tǒng)的初始化，即所有節(jié)點開始廣播數(shù)據(jù)兩兩傳遞它們的特征值向量和節(jié)點的標識信息id。計算出它們相互之間的歐氏距離：

得到了整個歐氏距離d（x，y），在節(jié)點內(nèi)部開辟一個長度為m 的數(shù)組（m 根據(jù)節(jié)點規(guī)模和工程需求來定），根據(jù)需求取n 個d（x，y）的值最小的節(jié)點id放入數(shù)組dis［］，數(shù)組中遍歷節(jié)點可以充分利用CPU 的步長特性。算法的復雜度為O（1）級別，有利于后續(xù)的取數(shù)據(jù)運算。2.1.3 節(jié)點中設(shè)置過濾器 由于節(jié)點廣播的時候可能會重復收到同一節(jié)點的信息，并且由于歐氏距離的運算較為復雜，所以使用過濾器來過濾相同標識節(jié)點發(fā)送的信息可以減少節(jié)點間的壓力。如果數(shù)據(jù)量較小，可以采用位圖方式構(gòu)建的Bitset 數(shù)據(jù)結(jié)構(gòu)。若數(shù)據(jù)量很大，則可以采用布隆過濾器（bloom filter）的方式。這兩種數(shù)據(jù)結(jié)構(gòu)都可以壓縮數(shù)據(jù)，并且由于采用二進制運算，所以運行速度也比較快。

Bitset 和布隆過濾器的作用都是判斷一個元素是否已經(jīng)存在于集合中。這里以Bitset 為例解釋。在節(jié)點廣播信號中存放節(jié)點id，接收信號時如果id 之前沒有接收過，則放入到Bitset 中；如果接收過，通過id 和Bitset 中的數(shù)據(jù)比較可以快速判斷節(jié)點存在于集合中而不再進行其他操作。位圖的原理是將整數(shù)x 作為一個bit 數(shù)組的下標存放于a[x]的bit 數(shù)組中，而一般的int 類型在計算機中占32 個bit，所以存放bit 大大地節(jié)省了內(nèi)存空間。同理布隆過濾器底層也是位圖，通過對數(shù)據(jù)進行多次哈希映射得到對應(yīng)數(shù)組。布隆過濾器存在一定的誤判率，但是只會誤判已存在集合的數(shù)據(jù)而一定不會誤判不存在的數(shù)據(jù)，且誤判的概率非常小，可以忽略。

2.2 選舉過程當在整個Raft 算法的系統(tǒng)中出現(xiàn)領(lǐng)導者節(jié)點宕機的情況下，未接收到返回心跳信號的節(jié)點發(fā)生狀態(tài)機改變成為候選者節(jié)點發(fā)起選舉。在選舉的過程中，任意的候選者節(jié)點都會首先遍歷節(jié)點內(nèi)部dis［］數(shù)組，通過RPC（remote procedure call）方式發(fā)起拉票請求RequestVote，由于歐氏距離近的節(jié)點在通信速度和可靠性方面要強于歐氏距離遠的節(jié)點，所以達成共識的速度會加快。在CFT算法達成共識的過程需要節(jié)點能更快交互，所以可以根據(jù)經(jīng)驗和系統(tǒng)的節(jié)點數(shù)對dis［］數(shù)組的長度m設(shè)置為一個特定的值以加快選舉速度，但是這個過程需要和下面的日志復制過程綜合考慮。

在獲取選票過程中成為候選者狀態(tài)的節(jié)點首先遍歷自身dis［］中的節(jié)點，但是此節(jié)點不一定會獲得超過半數(shù)的選票，所以還需要進行下一輪的Raft選舉來實現(xiàn)原始獲取選票的目的。在Raft 算法過程中加入過濾器避免重復選舉請求消耗整體資源，讓整個系統(tǒng)的性能得到優(yōu)化。這里給每個節(jié)點在RequestVote 帶上節(jié)點id 作為主鍵，讓Bitset（或者布隆過濾器）來過濾請求，避免重復請求消耗系統(tǒng)資源。

綜上整個選舉過程分為兩個部分，即內(nèi)部近距離投票和全局投票，節(jié)點選舉成功的概率可以如下表示：

其中m 為dis［］長度，n 為節(jié)點總數(shù)。

由于m 個節(jié)點的交互速度總體是高于全局的Raft 算法選舉，所以算法選舉的過程是快于原始算法的。

2.3 日志復制過程在日志復制過程中，同樣采用就近節(jié)點的原則。通過內(nèi)部dis［］數(shù)組的值，優(yōu)先找到歐氏距離近的節(jié)點，進行日志復制操作AddEntities，步驟如下：

（1）首先領(lǐng)導者節(jié)點發(fā)送第一輪日志條目給歐氏距離近的m 個節(jié)點，由于歐氏距離近，其平時運行時的日志條目通常會比較相近，需復制的日志條目不會太多。

（2）相鄰節(jié)點得到新的日志條目后，再根據(jù)它們內(nèi)部的dis［］數(shù)組來發(fā)送相應(yīng)的日志條目給歐氏距離較近的節(jié)點，依此類推。

（3）得到了新版本日志條目的節(jié)點會對這一次收到的版本號進行記錄。其他節(jié)點發(fā)送心跳信號時，未同步節(jié)點給領(lǐng)導者節(jié)點發(fā)送信號進行第二輪的日志復制。這樣就可以恢復到系統(tǒng)之前的日志狀態(tài)。

2.4 新節(jié)點加入與定時心跳數(shù)據(jù)設(shè)置對于新加入的節(jié)點，首先，向已存在節(jié)點發(fā)送特征值向量請求計算歐氏距離的廣播信號；其次，將得到的歐氏距離d（x，y）選取最小的若干值設(shè)置到自身dis［］數(shù)組；最后對整個系統(tǒng)進行其他的Raft 心跳操作。

其整體運算為串行，消耗運算時間為

其中，T 為消耗的總時間，t 為每個節(jié)點消耗的時間，n 為第n 個節(jié)點。

依據(jù)Raft 算法的定時器機制會設(shè)置范圍在［150，300］的隨機延時來發(fā)送心跳數(shù)據(jù)包，其中包含有領(lǐng)導者節(jié)點的任期和日志條目數(shù)量等，然后節(jié)點再對發(fā)送心跳信號的節(jié)點進行回復。在這個過程中可以設(shè)置一個較長時間的定時器，在一個非峰值的時段內(nèi)發(fā)送心跳數(shù)據(jù)的同時對節(jié)點中的向量進行廣播，重新調(diào)整歐氏距離，并且依據(jù)歐氏距離的大小重新調(diào)整內(nèi)部的dis［］數(shù)組內(nèi)容。其運算為并行的計算，時間的消耗為：

其中，T 為消耗的總時間，t 為每個節(jié)點消耗的時間，n 為第n 個節(jié)點。

節(jié)點的同步壓力為：

其中，Q 為總的節(jié)點壓力，q 為每個節(jié)點的壓力，n 為第n 個節(jié)點。

2.5 分布式理論驗證上文已經(jīng)提到過Raft 算法是BASE 理論的最佳實踐，同樣MV-Raft 算法也是滿足BASE 理論的最佳實踐，并且可以提高BASE理論的相應(yīng)性能。分析如下：在選舉和日志復制的過程中優(yōu)先選擇歐氏距離較近的節(jié)點，可以提高基本可用的性能。優(yōu)先選擇歐氏距離近的節(jié)點不但可以減輕一塊區(qū)域中的節(jié)點帶寬壓力，且由向量的計算后歐氏距離近節(jié)點日志的差異小，進行日志復制時節(jié)點之間需要傳輸?shù)娜罩緱l目減少，提高了可用性。在領(lǐng)導者節(jié)點崩潰后，同一時間相近區(qū)域內(nèi)出現(xiàn)候選者的概率會相對減少，使得軟狀態(tài)切換也減少，節(jié)點中狀態(tài)切換的可能性變低，這會加快選出新領(lǐng)導者節(jié)點的過程，讓最終一致性能更快實現(xiàn)。

上述的這些優(yōu)化結(jié)果都是在選取了正確特征值的條件下產(chǎn)生的。在日常的開發(fā)過程中，選擇特征值需要根據(jù)實際場景來確定。例如在HyperLedger Fabric 中需要考慮節(jié)點的機構(gòu)信用擔保授權(quán)（即背書）情況，每個節(jié)點的背書使得該節(jié)點擁有不同的權(quán)值。給不同節(jié)點的背書確立相對應(yīng)的分數(shù)編入多維向量，在計算歐氏距離中得到很大的體現(xiàn)，使得整體系統(tǒng)的網(wǎng)絡(luò)速度加快。

3 算法實現(xiàn)及性能分析

3.1 算法實現(xiàn)過程本實驗將按照如下5 個步驟進行實驗：

（1）創(chuàng)建一個三維數(shù)組vector 的變量放入節(jié)點中，變量為隨機數(shù)產(chǎn)生，其中數(shù)據(jù)類型為float64 其值介于［0，1］。

（2）通過遍歷所有節(jié)點，計算歐氏距離，取6 個最小數(shù)。

（3）將以上的6 個數(shù)放入dis［］數(shù)組中，同時將這6 個數(shù)的id 放入節(jié)點的ids［］數(shù)組中依據(jù)數(shù)組下標來一一映射。

（4）在選舉的交互過程中，利用雙方的vector 設(shè)置模擬延遲數(shù)據(jù)，進行測試。內(nèi)部保存歐氏距離的節(jié)點屬性dis［］數(shù)組長度將參數(shù)設(shè)置為6 用來實驗。

（5）在領(lǐng)導者節(jié)點當選之后，發(fā)送領(lǐng)導者節(jié)點日志復制信號，從所有節(jié)點設(shè)置為從ids［］數(shù)組中取得，然后再遞歸調(diào)用日志復制。

本文實驗采用Go 語言來實現(xiàn)Raft 算法并加以改進，通過上述的參數(shù)來設(shè)置Raft 算法的多維向量。運用多輪模擬選舉和日志復制的過程來實驗，觀察領(lǐng)導者節(jié)點的選舉消耗時間，以及日志復制對各個節(jié)點的壓力。

3.2 實驗結(jié)果與分析Raft 算法由于需獲得過半投票才能當選，所以節(jié)點數(shù)一般要求是奇數(shù)。對奇數(shù)個節(jié)點采取隨機抽樣檢驗方式搜集數(shù)據(jù)。下面列出MV-Raft 算法中節(jié)點選舉的比較數(shù)據(jù)，統(tǒng)計圖見圖5。

圖5 MV-Raft 算法平均耗時柱狀圖

由于Raft 算法的定時器機制會帶來數(shù)據(jù)波動，節(jié)點少會讓算法耗時不明顯，節(jié)點多會讓并發(fā)加大使得數(shù)據(jù)偏差變大，所以選擇中位數(shù)11 個節(jié)點來測試。通過測試的中位數(shù)和原始Raft 算法做比較，通過10 次選舉后做出對比，見圖6。

圖6 選舉耗時柱狀圖

由于Raft 算法具有隨機定時器機制，選舉耗時具有一定的波動性造成單次選舉耗時也出現(xiàn)波動。在統(tǒng)計平均值后得出，原始Raft 算法平均耗時118 ms，而MV-Raft 算法平均耗時99 ms。以上結(jié)果證明，改進后的MV-Raft 算法在選舉的整體效果中要優(yōu)于原始Raft 算法。MV-Raft 算法相較于原始Raft算法選舉耗時減少16%，整體顯示出來MV-Raft 算法的平均數(shù)據(jù)更好。

在節(jié)點的日志復制過程中，首先是尋找歐氏距離較近節(jié)點。對于領(lǐng)導者節(jié)點的壓力可以相對于原有算法的節(jié)點數(shù)減去ids［］數(shù)組的長度。歐氏距離較近節(jié)點之間傳輸數(shù)據(jù)會較快，此處采用的方式是P2P 的Gossip 協(xié)議的算法，節(jié)點是通過push 的方式同步數(shù)據(jù)，在一輪的同步中節(jié)點被同步的概率為（每個節(jié)點在每個周期被感染的概率都是固定的p，其中0＜p＜1，因此Gossip 算法是基于p 的平方收斂，也稱為概率收斂）：

在每一輪的同步過程中原始算法的領(lǐng)導者節(jié)點是全節(jié)點同步壓力隨著節(jié)點數(shù)的增加呈線性增長的，MV-Raft 算法由于內(nèi)部緩存節(jié)點固定為5 個，所以領(lǐng)導者節(jié)點的壓力固定為5 沒有變化。數(shù)據(jù)測試壓力見圖7。

圖7 系統(tǒng)節(jié)點同步次數(shù)

本文對Raft 算法進行研究，提出一種基于多維向量的Raft 算法——MV-Raft。MV-Raft 算法通過業(yè)務(wù)需求權(quán)重計算獲取多維向量并計算其歐氏距離，使得在領(lǐng)導者節(jié)點選舉和日志復制方面有效地提高整體性能，并且減輕節(jié)點的壓力使得系統(tǒng)不易崩潰。本文提出的多維向量機制需要根據(jù)業(yè)務(wù)的實際需求來確定特征值，未來的研究中將進一步針對文中的參數(shù)調(diào)整使用機器學習的方法搜集大量業(yè)務(wù)數(shù)據(jù)做出新的研究。