MV-Raft：一種新的基于多維向量的聯盟鏈共識算法

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

（大理大學數學與計算機學院，云南大理 671003）

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

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

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

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

1 背景知識

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

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

圖1 Raft 選舉狀態機的轉換

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

圖2 Raft 運行流程

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

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

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

2 算法設計與分析

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

圖3 算法的整體流程

經過上述流程后，每個節點會緩存歐氏距離近的節點，整個系統在選舉和同步日志時會得到性能上的優化。領導者節點會根據內部的緩存數組來操作，節點壓力也會減輕。詳細過程如下：首先根據每個節點的內部數組進行選舉；其次，若獲得足夠選票節點可直接當選，若不夠則通過P2P 網絡全局獲取選票；最后再通過內部數組同步日志，同步過的節點再調用其內部數組記錄同步日志直到全局完成日志同步。領導者節點的操作見圖4。

圖4 算法優化示意

2.1 算法多維向量處理過程

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

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

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

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

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

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

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

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

其中m 為dis［］長度，n 為節點總數。

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

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

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

（2）相鄰節點得到新的日志條目后，再根據它們內部的dis［］數組來發送相應的日志條目給歐氏距離較近的節點，依此類推。

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

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

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

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

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

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

節點的同步壓力為：

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

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

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

3 算法實現及性能分析

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

（1）創建一個三維數組vector 的變量放入節點中，變量為隨機數產生，其中數據類型為float64 其值介于［0，1］。

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

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

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

（5）在領導者節點當選之后，發送領導者節點日志復制信號，從所有節點設置為從ids［］數組中取得，然后再遞歸調用日志復制。

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

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

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

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

圖6 選舉耗時柱狀圖

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

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

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

圖7 系統節點同步次數

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