Gossip協議:“八卦版”區塊鏈通訊協議
隨著比特幣等數字加密貨幣的興起,區塊鏈技術逐漸升溫,霎時間,各種區塊鏈技術落地場景應運而生。但是關於區塊鏈技術本身,“去中心化”、“資料不可篡改”、“資料溯源”、“共識機制”等詞語散落在大眾的腦海中。
鑑於區塊鏈的分散式架構, 第一個要解決的問題便是在通訊中如何保證資訊的一致性,如果分散式叢集的處理結果不能得到一致性的保障,那麼建立在其上的任何業務也就無法正常執行。 廣為人知的 Gossip 協議在節點間的資訊同步問題中,便能夠發揮巨大的作用。
CAP 原理指出,分散式計算系統中不可能同時確保一致性(Consistency)、可用性(Availability)、分割槽容錯性(Partition Tolerance),因此,在設計系統時往往需要弱化對某個特性的支援。
Gossip協議是什麼
Gossip協議就是為一些弱化了一致性的應用場景設計、用來實現節點間的資訊同步,解決分散式架構中的資訊一致性問題。
Gossip 協議,又稱“八卦”協議,用於系統內節點之間的相互通訊,就是模擬人類傳播八卦的方式而產生的,類似於 社交網路訊息 傳播方式或者是 流行性疾病 的傳染方式。Gossip 是以數學為基礎、具有紮實理論分析基礎的去中心化分散式通訊協議,即系統內節點之間相互通訊的通訊機制。
Gossip協議可類比八卦新聞在社交網路中的傳播。
最初只有一個或者少數幾個人知道某個八卦新聞,得知該八卦新聞的人都在自己的好友圈轉發,雖然每個人的好友數量有限,但該八卦新聞卻能夠在社交網路中快速發酵。
簡單來說,在一個網路中,每個節點都隨機地和其他節點進行通訊,當一個節點要傳送訊息時,該節點隨機地選擇對等的節點併發送訊息,這些節點收到訊息後將重複同樣的過程,再將訊息轉發給網路中其他隨機選擇的對等節點,最終所有節點的狀態都能夠達成一致。
要進行“謠言”傳播,首先需要有種子節點,種子節點經過一定時間間隔都會隨機向其他節點發送自己所擁有的節點列表以及需要傳播的訊息。任何新加入的節點,通過這樣的傳播便很快地被整個網路獲取。
在最開始,並不需要將資訊傳遞給所有的節點,但隨著時間的增長,“謠言”逐步擴散,在“最終”的某一時刻,全網便會得到相同的資訊,也即 弱化了一致性,強調實現最終一致性 。Gossip 解決的問題也就是在分散式環境下資訊高效分發的問題,決定了系統的一致性程度。
在超級賬本 Fabric 和 Cassandra 資料庫中,Gossip 協議在其資訊同步中都發揮了重要作用。
在 Hyperledger Fabric 的交易流程中,Peer 節點作為參與交易的主體,主要負責儲存完整的區塊鏈資料、執行智慧合約,Peer 節點之間可以通過 Gossip 協議來完成區塊分發、狀態同步等問題。
在每個 Peer 節點上都維護了其它 Peer 節點的資訊,通過隨機的與其它 Peer 節點通訊來交換資訊,達到最終一致性。主要過程為通過 GossipClient 客戶端的 GossipStream 雙向流進行通訊,傳送 SignedGossipMessage 訊息結構。
Apache 的分散式資料庫 Cassandra 中,各節點地位平等、各自獨立,通過 Gossip 協議進行各個節點間的資料通訊,其主要功能是在 Cassandra 叢集中的所有節點之間快速高效地傳遞各個節點的狀態和資訊。
如果處於交換狀態的節點在資訊傳遞時長時間未響應,則此時執行請求的節點就會將目標節點標記為失靈,並通過 Gossip 協議將該節點的狀態傳出去。
通過這樣的方式,Cassandra 資料庫就可以確定能夠用來高效儲存資料的健康節點,並在這些節點上進行資料的操作,從而避免了節點資訊交換故障導致的無效或者錯誤操作,降低了時間成本,同時提高了系統效率。
Gossip協議模型
明白了 Gossip 協議及其用途,我們來探究一下 Gossip 協議的具體模型,它主要由 時間模型 和 訊息更新模型 組成。
按照採用的時間模型來看,Gossip 協議可以分為同步 Gossip 協議和非同步 Gossip 協議。同步 Gossip 協議是指網路中的節點有確定的時序關係,節點按照一定的時序關係進行資料交換。
而非同步單播 Gossip 協議是在每一個時間間隔中隨機地喚醒網路中的一個節點,被喚醒的節點再隨機地選擇鄰接節點進行資料交換。因為同步問題較為複雜,所以同步 Gossip 協議在實際生產環境中的應用較少。
按照節點之間資訊更新的方式,Gossip 協議可以分為基於單播的 Gossip 協議和基於廣播的 Gossip 協議。
單播 Gossip 協議是指被喚醒的節點每次只選擇它的一個鄰接節點進行資料交換。單播 Gossip 協議的收斂性和收斂速度可證明,且能夠收斂於網路的初始均值。但是單播 Gossip 的收斂速度很大程度上依賴於網路結構。
廣播 Gossip 協議是指在一次迭代過程中,隨機地喚醒一個節點,被喚醒的節點與所有的鄰接節點均進行資訊交換。廣播 Gossip 協議無法保證其收斂狀態值等於網路初始狀態的均值。
“八卦”協議下的節點互動模式
Gossip的兩個節點A、B之間有三種互動模式:
1、Push 模式:B節點將資料(key,value,version)及對應的版本號推送給 A 節點,A 節點更新 B 節點中比自己新的資料。在 Push 模式中,發起資訊交換的節點隨機選取節點並向其傳送自己的資訊,一般擁有新資訊的節點才會作為發起節點。
假設存在 n 個節點,採用 Push 方式,在資料傳播的初期,已收到訊息的節點數目呈指數增長,直到有一半節點收到該訊息。此後,未收到訊息的節點集合將會在每一輪以一個常數因子進行收縮。當訊息傳播過程結束時該常數因子為,因為在一輪中沒有收到訊息的節點的佔。因此,收縮過程將會通過輪直到所有的節點均收到訊息,Push 模式在每一輪中傳送的訊息數量為。
2、Pull 模式:A 僅將資料 key、version 推送給 B,B 將本地比 A 新的資料(key,value,version)推送給 A,A 更新本地。
在 Pull 模式中,發起資料交換的節點隨機選擇節點並獲取所選節點的資料,一般無新資料的節點才會作為發起節點。Pull 方式與 Push 方式相反,在資料傳播的初期,收到訊息的節點的數量增長緩慢;當已有一半節點收到訊息之後,每輪過後未收到訊息的節點佔比將呈平方收縮。
這是因為在一輪開始時假設有個未收到訊息的節點,每一個節點將有的概率收到訊息,因此節點保持未收到訊息狀態的概率為,這一輪結束後未收到訊息的節點數量為。因此,未收到訊息的節點數量的收縮過程僅需要輪,該過程中每一輪傳遞的訊息數量為。
3、Push-Pull 模式:在 Pull 的基礎上,A 再將本地比 B 新的資料推送給 B,然後 B 再更新本地資料。也就是在 Pull 之後,A 再對比自己掌握的資訊,更新 B 手中掌握的資訊。
Push-Pull 模式是結合了具備可預測性的 Push 機制和具備平方收縮特性的 Pull 機制,在這種模式下,訊息雙向傳送。發起資訊交換的節點先初始化一個時間計數器來代表資訊的生命值,初始計數為 0。
資訊的生命值會隨著每次傳播而遞增。發起資訊交換的節點隨機選取節點並向其傳送自己的訊息,同時從所選取的節點上獲取該節點的訊息,這個過程將持續進行直到訊息的生命值超過。
假設存在 n 個節點,在全連通網路中採用 Push-Pull 的方式,那麼完成 Gossip 過程需要輪和次資料交換。
- 想象 A、B 是老同學,畢業後工作在同一家公司,朝夕相處, A 想要了解 B 的資訊,B 就只需要把 A 不知道的事情告訴他,類似於“推”模式。
- 倘若只是工作在同一棟樓,兩人掌握的資訊依然有一定的交集,A 與 B 在簡單的交流後,B 就可以告訴 A 所不知道的資訊,就類似於“拉”模式。
- 如果兩個人畢業後在不同的國家,在資訊內容上基本沒有交集,這時候就需要將自己知道的全部資訊告訴彼此,也就類似於“推-拉”模式。
通過這樣類似“推”、“拉”的方式,完成了節點間資訊的同步。
知識拓展:其他通訊協議
在分散式中,除了 Gossip 這個通訊協議,還有 Totem 協議、Paxos 協議等。
其中, Totem 協議 在節點間形成單環結構,通過 token,利用類似於 “丟手絹” 的形式,實現訊息的傳遞,只有拿到 token 的節點才能夠傳送訊息,以此來保證訊息的有序性。
Paxos 協議通俗來講,類似於 二階段提交 ,就是在第一個階段由一個節點詢問其它節點是否可以進行訊息的提交,如果超過半數節點響應,則可以進行訊息提交,否則失敗;在第二階段超過半數響應才能夠進行訊息寫入,同時需要滿足一定的前提。
相比 Totem 協議、Paxos 協議等強一致性的協議,Gossip協議適當放寬了對一致性的要求,降低了系統實現的難度,強調在一定約束下實現最終一致性,即總會在某一個時刻,系統達到一致的狀態。