【技術實戰】分布式架構——Gossip 協議詳解

2020-12-26 騰訊網

- 起源 -

Gossip protocol 也叫 Epidemic Protocol （流行病協議）。Gossip protocol在1987年8月由施樂-帕洛阿爾託研究中心發表ACM上的論文

《Epidemic Algorithms for Replicated Database Maintenance》

中被提出。原本用於分布式資料庫中節點同步數據使用，後被廣泛用於資料庫複製、信息擴散、集群成員身份確認、故障探測等。

Gossip協議是基於六度分隔理論（Six Degrees of Separation）哲學的體現，簡單的來說，一個人通過6個中間人可以認識世界任何人。數學公式是：

n表示複雜度，N表示人的總數，W表示每個人的聯繫寬度。依據鄧巴數，即每個人認識150人，其六度就是1506 ＝11,390,625,000,000（約11.4萬億）。

基於六度分隔理論，任何信息的傳播其實非常迅速，而且網絡交互次數不會很多。比如Facebook在2016年2月4號做了一個實驗：研究了當時已註冊的15.9億使用者資料，發現這個神奇數字的「網絡直徑」是4.57，翻成白話文意味著每個人與其他人間隔為4.57人。

- 原理 -

Gossip協議執行過程：

種子節點周期性的散播消息 【假定把周期限定為 1 秒】。

被感染節點隨機選擇N個鄰接節點散播消息【假定fan-out(扇出)設置為6，每次最多往6個節點散播】。

節點只接收消息不反饋結果。

每次散播消息都選擇尚未發送過的節點進行散播。

收到消息的節點不再往發送節點散播：A -> B，那麼B進行散播的時候，不再發給 A。

Goosip 協議的信息傳播和擴散通常需要由種子節點發起。整個傳播過程可能需要一定的時間，由於不能保證某個時刻所有節點都收到消息，但是理論上最終所有節點都會收到消息，因此它是一個最終一致性協議。

Gossip協議是一個多主協議，所有寫操作可以由不同節點發起，並且同步給其他副本。Gossip內組成的網絡節點都是對等節點，是非結構化網絡。

- 消息類型 -

Gossip 協議的消息傳播方式有兩種：Anti-Entropy(反熵傳播)和Rumor-Mongering(謠言傳播)。

反熵傳播是以固定的概率傳播所有的數據。所有參與節點只有兩種狀態：Suspective(病原)、Infective(感染)。這種節點狀態又叫做simple epidemics(SI model)。過程是種子節點會把所有的數據都跟其他節點共享，以便消除節點之間數據的任何不一致，它可以保證最終、完全的一致。缺點是消息數量非常龐大，且無限制；通常只用於新加入節點的數據初始化。

謠言傳播是以固定的概率僅傳播新到達的數據。所有參與節點有三種狀態：Suspective(病原)、Infective(感染)、Removed(愈除)。這種節點狀態又叫做complex epidemics(SIR model)。過程是消息只包含最新 update，謠言消息在某個時間點之後會被標記為 removed，並且不再被傳播。缺點是系統有一定的概率會不一致，通常用於節點間數據增量同步。

- 通信方式 -

Gossip 協議最終目的是將數據分發到網絡中的每一個節點。根據不同的具體應用場景，網絡中兩個節點之間存在三種通信方式：推送模式、拉取模式、Push/Pull。

Push: 節點 A 將數據 (key,value,version) 及對應的版本號推送給 B 節點，B 節點更新 A 中比自己新的數據

Pull：A 僅將數據 key, version 推送給 B，B 將本地比 A 新的數據（Key, value, version）推送給 A，A 更新本地

Push/Pull：與 Pull 類似，只是多了一步，A 再將本地比 B 新的數據推送給 B，B 則更新本地

如果把兩個節點數據同步一次定義為一個周期，則在一個周期內，Push 需通信 1 次，Pull 需 2 次，Push/Pull 則需 3 次。雖然消息數增加了，但從效果上來講，Push/Pull 最好，理論上一個周期內可以使兩個節點完全一致。直觀上，Push/Pull 的收斂速度也是最快的。

- 總結 -

綜上所述，我們可以得出Gossip是一種去中心化的分布式協議，數據通過節點像病毒一樣逐個傳播。因為是指數級傳播，整體傳播速度非常快，很像現在美國失控的2019-nCoV(新冠)一樣。它具備以下優勢：

擴展性：允許節點的任意增加和減少，新增節點的狀態 最終會與其他節點一致。

容錯：任意節點的宕機和重啟都不會影響 Gossip 消息的傳播，具有天然的分布式系統容錯特性。

去中心化：無需中心節點，所有節點都是對等的，任意節點無需知道整個網絡狀況，只要網絡連通，任意節點可把消息散播到全網。

一致性收斂：消息會以「一傳十的指數級速度」在網絡中傳播，因此系統狀態的不一致可以在很快的時間內收斂到一致。消息傳播速度達到了 logN。

簡單

同樣也存在以下缺點：

消息延遲：節點隨機向少數幾個節點發送消息，消息最終是通過多個輪次的散播而到達全網；不可避免的造成消息延遲。

消息冗餘：節點定期隨機選擇周圍節點發送消息，而收到消息的節點也會重複該步驟；不可避免的引起同一節點消息多次接收，增加消息處理壓力。

Gossip協議由於以上的優缺點，所以適合於AP場景的數據一致性處理，常見應用有：P2P網絡通信、Apache Cassandra、Redis Cluster、Consul。

-the end-

IT東方會推出專欄作者特輯，來自社群的技術大咖和公眾號大V們，用他們的技術見解與經驗，與你一起認知提升。

如果你也有精彩原創公眾號，歡迎添加小助手微信，加入公眾號互推聯盟，報名加入專欄作家，更有機會參與免費出書活動哦。

▼▼▼

（為保證社群質量，入群需審核哦）

「IT東方會」

相關焦點

  • 騰訊宣布企業級分布式高性能KV存儲資料庫Tendis正式開源
    12月22日消息 近期，騰訊宣布企業級分布式高性能 KV 存儲資料庫 Tendis 正式開源。 　　Tendis 是騰訊互娛 CROS DBA 團隊 & 騰訊雲資料庫團隊自主設計和研發的分布式高性能 KV 存儲資料庫，兼容 Redis 核心數據結構與接口，可提供大容量、低成本、強持久化的資料庫能力，適用於兼容 Redis 協議、需要大容量且較高訪問性能的溫冷數據存儲場景。Tendis 目前已經被應用到騰訊內、外部大型項目中。
  • 企業級分布式高性能KV存儲資料庫,騰訊Tendis正式開源
    12月22日消息，騰訊宣布其企業級分布式高性能KV存儲資料庫Tendis開源。消息稱，Tendis是由騰訊互娛CROS DBA團隊和騰訊雲資料庫團隊自主設計和研發的分布式高性能KV存儲資料庫。
  • 左耳朵耗子:分布式系統架構經典資料
    前段時間，我寫了一系列分布式系統架構方面的文章（拉到文末看目錄），有很多讀者紛紛留言討論相關的話題，還有讀者留言表示對分布式系統架構這個主題感興趣，希望我能推薦一些學習資料。就像我在前面的文章中多次提到的，分布式系統的技術棧巨大無比，所以我要推薦的學習資料也比較多，會在後面的文章中陸續發出。在今天這篇文章中，我將推薦一些分布式系統的基礎理論和一些不錯的圖書和資料。
  • 騰訊開源分布式存儲系統 Tendis,可完全兼容 Redis
    近日，騰訊宣布開源一個與 Redis 協議完全兼容的高性能分布式存儲系統 Tendis。
  • 華銳金融技術董事長鄒勝:五年內證券業將完成核心交易分布式轉型...
    財聯社（上海，記者 劉超鳳）訊，2020年12月17-18日，華銳金融技術在珠海舉辦了第二屆「平臺戰略、開放重構——2020分布式轉型高峰論壇」，華銳金融技術董事長鄒勝表示，「華銳的目標就是做分布式低時延金融技術的引領者，提升中國金融基礎設施自主能力，5年內證券行業將完成本輪的分布式技術轉型。」
  • 阿里雲服務網格ASM架構技術解析
    本文整理自阿里雲高級技術專家王夕寧撰寫的《Istio服務網格技術解析與實戰》一書以及阿里雲服務網格產品ASM最新發布內容，針對服務網格的未來發展、服務網格技術帶來的優勢以及對業內首個全託管Istio兼容服務網格產品ASM進行了詳細的介紹。雲計算已成為企業應用程式的主要範式。
  • 京東資深架構師爆肝純手打700頁架構進階寶典我粉了
    而作為參與其中的主力之一的京東，他們的基礎架構與底層系統是如何搭建的呢？作為程序猿的我們，該如何脫離CRUD的苦海讓自己也加入到這億級系統的搭建中來呢？不要慌！網際網路雷鋒（小編我）為大家整理出兩份真京東大牛編寫的架構實戰文檔，可以說是國內架構文檔的經典之作。
  • 達內Java網際網路架構課程升級,制定Java人才培訓標準
    企業軟體發展大概經歷了三個階段：第一階段是軟體功能時代，這個時代的特點是企業軟體以功能為核心，開發一個企業軟體實現其功能就完成了，核心技術是Servlet/JSP、SSM、MySQL等。　　隨著網際網路的不斷發展和迭代，對網際網路軟體的性能要求越來越高，這時就進入到軟體性能時代，標誌性核心技術包括：微服務/分布式、SpringCloud、Nginx/Redis/Kafka/ES。
  • 達內升級Java網際網路架構課程,培養符合職業教育4.0時代人才
    隨著網際網路的不斷發展和迭代，對網際網路軟體的性能要求越來越高，這時就進入到軟體性能時代，標誌性核心技術包括：微服務/分布式、SpringCloud、Nginx/Redis/Kafka/ES。網際網路軟體要求高性能、高並發、高可用，網際網路軟體承載量要求直線攀升，這時就要解決網際網路的架構問題，用網際網路架構問題來解決網際網路軟體的性能問題。
  • 支付寶資深技術專家尹博學:新一代金融核心突破之全分布式單元化...
    微服務、容器、無伺服器架構、服務網格等新技術的出現，在技術社區中激起了一浪又一浪的創新熱潮。然而由於金融行業對性能和安全的嚴苛要求，雲原生技術在企業實際場景中的實施落地，特別是在金融場景的實施落地，仍然面臨諸多挑戰。本文整理自2020阿里雲線上峰會螞蟻集團資深技術專家尹博學的主題演講，為大家分享螞蟻關於金融級IT架構及分布式架構的思考和應用實踐。
  • 13張圖搞懂分布式系統服務註冊與發現原理
    本文轉載自【微信公眾號：五角錢的程式設計師，ID:xianglin965】經微信公眾號授權轉載，如需轉載與原文作者聯繫在微服務架構或分布式環境下，服務註冊與發現技術不可或缺，這也是程式設計師進階之路必須要掌握的核心技術之一，本文通過圖解的方式帶領大家輕輕鬆鬆掌握。
  • 今日推薦|對央行《金融分布式帳本技術安全規範》的解讀
    上海散列信息科技合夥企業創始合伙人、中國計算機學會區塊鏈專委會委員高承實博士，於2月28日在陀螺財經組織的線上活動中，對《金融分布式帳本技術安全規範》進行了解讀。 （1）分布式帳本技術。這個規範沒有用區塊鏈，而是用了分布式帳本技術。但從規範的「引言」給出的定義中，我們基本可以判定，這個分布式帳本技術就是區塊鏈。
  • 行業引領產品——VATION巨洋光分布式圖像處理器系統(功能篇)
    V-Spider光分布式圖像處理器是巨洋針對不同用戶所推出的一套基於分布式架構的圖像處理系統，不但可實現現有各種類型信號源的實時上屏顯示，還提供豐富的開發接口，供用戶選擇。1、系統採用分布式系統架構，系統自由搭建，提高系統的擴展性，即插即用；降低節點故障率、提升系統的穩定性。
  • 他趣已有平臺引入直播的實戰之路|架構師實踐日
    那麼，已有平臺在引入直播技術的過程中，有哪些經驗值得借鑑又該如何合理避坑呢？9 月 3 日，在七牛雲主辦的架構師實踐日上，他趣首席架構師 張嵩，帶來了他趣在已有平臺上引入直播的實戰經驗。以下是對他現場內容的整理。張嵩 他趣首席架構師演講嘉賓：廈門大學計算機碩士， 14 年加入他趣，負責業務服務化改造，現主要負責微服務體系健全及持續交付體系建設。
  • DTCC2020阿里雲李飛飛:雲原生分布式資料庫與數據倉庫系統點亮數據...
    挑戰二：對資源的使用方式傳統的馮諾依曼架構下計算和存儲是緊密耦合的，可將多個伺服器通過分布式協議和處理的方式連成一個系統，但是伺服器和伺服器之間、節點和節點之間，分布式事務的協調、分布式查詢的優化，尤其要保證強一致性、強ACID的特性保證的時候，具有非常多的挑戰。
  • 「青」心打造 為「雲」而生 青雲科技分布式存儲全線升級
    與國內眾多廠商基於開源的分布式存儲作為底層進行二次封裝和二次開發，QingStor從架構設計階段就與之有本質的不同。目前，QingStor產品家族裡有四款專業存儲產品，共同支撐市面上幾乎全部主流的雲計算產品。
  • 未來的分布式帳本技術:不是區塊鏈,會是哈希圖?
    Leemon, 革命性的分布式帳本技術---哈希圖技術發明人. 2年9個月獲得卡內基梅隆大學博士學位. 該技術各方面都優於區塊鏈。當我接觸一些在區塊鏈社區工作的人時，似乎也沒有一個人知道這個協議。這是一個了不起的技術, 一個了不起的算法，主要處理基本上達成共識，並解決了區塊鏈社區一直在努力的許多問題。如果您先解釋區塊鏈和分布式帳本技術之間的區別，再談哈希圖可能對別人理解會更有幫助。
  • 華為雲擎天架構技術再突破
    近日，華為雲擎天架構調度算法團隊打破了51項由全球優化算法領域權威機構SINTEF維護的PDPTW榜單紀錄，成為中國研究機構中最多紀錄的保持者。這也是繼今年GECCO國際會議摘得運籌優化算法賽道雙榜首後，華為雲在分布式雲資源調度、智能決策與優化等技術領域的再一次突破。
  • 青雲科技自研分布式存儲全線升級 挖掘數字時代潛力
    「現如今，企業內部分布式存儲部署的佔比越來越重，甚至在一些企業裡超過了傳統存儲。分析其背後的原因，主要來源於過去10年裡，包括移動網際網路、大數據、5G、AIoT等新興技術應用場景對於存儲提出新的需求。比如對高容量的需求，對更複雜場景（如雲計算）的需求。分布式存儲正因為場景的不同而產生巨大的增長。」 王煜表示。
  • 美軍「分布式殺傷」作戰概念的關鍵支撐技術分析
    概述美國海軍開發試驗新的「分布式殺傷概念」——海洋空間分散化部署並實現攻防兼備。這是一種兵力分散、火力集中式的構想，是以「全新的隊形」取代「傳統的方陣」，這一新型作戰模式體現了美海軍「由海制陸」到「重回制海」作戰思路的轉變，提升水面艦艇的反艦作戰能力是其最重要的調整思路，美軍未來除了會大力發展反艦飛彈技術外，還要依託三項基礎性技術——「宙斯盾」系統、「一體化防空和飛彈防禦」和「海軍一體化防空火控」。「分布式殺傷」的核心和關鍵就是數據互聯和協同作戰。