分布式架構(gòu)——Gossip 協(xié)議詳解
起源
Gossip protocol 也叫 Epidemic Protocol （流行病協(xié)議）。Gossip protocol 在 1987 年 8 月由施樂-帕洛阿爾托研究中心發(fā)表 ACM 上的論文 《Epidemic Algorithms for Replicated Database Maintenance》 中被提出。原本用于分布式數(shù)據(jù)庫中節(jié)點(diǎn)同步數(shù)據(jù)使用，后被廣泛用于數(shù)據(jù)庫復(fù)制、信息擴(kuò)散、集群成員身份確認(rèn)、故障探測(cè)等。
Gossip 協(xié)議是基于六度分隔理論（Six Degrees of Separation）哲學(xué)的體現(xiàn)，簡(jiǎn)單的來說，一個(gè)人通過 6 個(gè)中間人可以認(rèn)識(shí)世界任何人。數(shù)學(xué)公式是：
n 表示復(fù)雜度，N 表示人的總數(shù)，W 表示每個(gè)人的聯(lián)系寬度。?依據(jù)鄧巴數(shù)，即每個(gè)人認(rèn)識(shí) 150 人，其六度就是 1506 ＝ 11,390,625,000,000（約 11.4 萬億）。
基于六度分隔理論，任何信息的傳播其實(shí)非常迅速，而且網(wǎng)絡(luò)交互次數(shù)不會(huì)很多。比如 Facebook 在 2016 年 2 月 4 號(hào)做了一個(gè)實(shí)驗(yàn)：研究了當(dāng)時(shí)已注冊(cè)的 15.9 億使用者資料，發(fā)現(xiàn)這個(gè)神奇數(shù)字的“網(wǎng)絡(luò)直徑”是 4.57，翻成白話文意味著每個(gè)人與其他人間隔為 4.57 人。
原理
Gossip 協(xié)議執(zhí)行過程：
?種子節(jié)點(diǎn)周期性的散播消息 【假定把周期限定為 1 秒】。?被感染節(jié)點(diǎn)隨機(jī)選擇 N 個(gè)鄰接節(jié)點(diǎn)散播消息【假定 fan-out(扇出)設(shè)置為 6，每次最多往 6 個(gè)節(jié)點(diǎn)散播】。?節(jié)點(diǎn)只接收消息不反饋結(jié)果。?每次散播消息都選擇尚未發(fā)送過的節(jié)點(diǎn)進(jìn)行散播。?收到消息的節(jié)點(diǎn)不再往發(fā)送節(jié)點(diǎn)散播：A -> B，那么 B 進(jìn)行散播的時(shí)候，不再發(fā)給 A。
Goosip 協(xié)議的信息傳播和擴(kuò)散通常需要由種子節(jié)點(diǎn)發(fā)起。?整個(gè)傳播過程可能需要一定的時(shí)間，由于不能保證某個(gè)時(shí)刻所有節(jié)點(diǎn)都收到消息，但是理論上最終所有節(jié)點(diǎn)都會(huì)收到消息，因此它是一個(gè)最終一致性協(xié)議。
Gossip 協(xié)議是一個(gè)多主協(xié)議，所有寫操作可以由不同節(jié)點(diǎn)發(fā)起，并且同步給其他副本。Gossip 內(nèi)組成的網(wǎng)絡(luò)節(jié)點(diǎn)都是對(duì)等節(jié)點(diǎn)，是非結(jié)構(gòu)化網(wǎng)絡(luò)。
消息類型
Gossip 協(xié)議的消息傳播方式有兩種：Anti-Entropy(反熵傳播)和 Rumor-Mongering(謠言傳播)。
反熵傳播是以固定的概率傳播所有的數(shù)據(jù)。所有參與節(jié)點(diǎn)只有兩種狀態(tài)：Suspective(病原)、Infective(感染)。這種節(jié)點(diǎn)狀態(tài)又叫做 simple epidemics(SI model)。過程是種子節(jié)點(diǎn)會(huì)把所有的數(shù)據(jù)都跟其他節(jié)點(diǎn)共享，以便消除節(jié)點(diǎn)之間數(shù)據(jù)的任何不一致，它可以保證最終、完全的一致。缺點(diǎn)是消息數(shù)量非常龐大，且無限制；通常只用于新加入節(jié)點(diǎn)的數(shù)據(jù)初始化。
謠言傳播是以固定的概率僅傳播新到達(dá)的數(shù)據(jù)。所有參與節(jié)點(diǎn)有三種狀態(tài)：Suspective(病原)、Infective(感染)、Removed(愈除)。這種節(jié)點(diǎn)狀態(tài)又叫做 complex epidemics(SIR model)。過程是消息只包含最新 update，謠言消息在某個(gè)時(shí)間點(diǎn)之后會(huì)被標(biāo)記為 removed，并且不再被傳播。缺點(diǎn)是系統(tǒng)有一定的概率會(huì)不一致，通常用于節(jié)點(diǎn)間數(shù)據(jù)增量同步。
通信方式
Gossip 協(xié)議最終目的是將數(shù)據(jù)分發(fā)到網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)。根據(jù)不同的具體應(yīng)用場(chǎng)景，網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間存在三種通信方式：推送模式、拉取模式、Push/Pull。
?Push: 節(jié)點(diǎn) A 將數(shù)據(jù) (key,value,version) 及對(duì)應(yīng)的版本號(hào)推送給 B 節(jié)點(diǎn)，B 節(jié)點(diǎn)更新 A 中比自己新的數(shù)據(jù)?Pull：A 僅將數(shù)據(jù) key, version 推送給 B，B 將本地比 A 新的數(shù)據(jù)（Key, value, version）推送給 A，A 更新本地?Push/Pull：與 Pull 類似，只是多了一步，A 再將本地比 B 新的數(shù)據(jù)推送給 B，B 則更新本地
如果把兩個(gè)節(jié)點(diǎn)數(shù)據(jù)同步一次定義為一個(gè)周期，則在一個(gè)周期內(nèi)，Push 需通信 1 次，Pull 需 2 次，Push/Pull 則需 3 次。雖然消息數(shù)增加了，但從效果上來講，Push/Pull 最好，理論上一個(gè)周期內(nèi)可以使兩個(gè)節(jié)點(diǎn)完全一致。直觀上，Push/Pull 的收斂速度也是最快的。
總結(jié)
綜上所述，我們可以得出?Gossip 是一種去中心化的分布式協(xié)議，數(shù)據(jù)通過節(jié)點(diǎn)像病毒一樣逐個(gè)傳播。因?yàn)槭侵笖?shù)級(jí)傳播，整體傳播速度非常快，很像現(xiàn)在美國失控的 2019-nCoV(新冠)一樣。它具備以下優(yōu)勢(shì)：
?擴(kuò)展性：允許節(jié)點(diǎn)的任意增加和減少，新增節(jié)點(diǎn)的狀態(tài) 最終會(huì)與其他節(jié)點(diǎn)一致。?容錯(cuò)：任意節(jié)點(diǎn)的宕機(jī)和重啟都不會(huì)影響 Gossip 消息的傳播，具有天然的分布式系統(tǒng)容錯(cuò)特性。?去中心化：無需中心節(jié)點(diǎn)，所有節(jié)點(diǎn)都是對(duì)等的，任意節(jié)點(diǎn)無需知道整個(gè)網(wǎng)絡(luò)狀況，只要網(wǎng)絡(luò)連通，任意節(jié)點(diǎn)可把消息散播到全網(wǎng)。?一致性收斂：消息會(huì)以“一傳十的指數(shù)級(jí)速度”在網(wǎng)絡(luò)中傳播，因此系統(tǒng)狀態(tài)的不一致可以在很快的時(shí)間內(nèi)收斂到一致。消息傳播速度達(dá)到了 logN。?簡(jiǎn)單
同樣也存在以下缺點(diǎn)：
?消息延遲：節(jié)點(diǎn)隨機(jī)向少數(shù)幾個(gè)節(jié)點(diǎn)發(fā)送消息，消息最終是通過多個(gè)輪次的散播而到達(dá)全網(wǎng)；不可避免的造成消息延遲。?消息冗余：節(jié)點(diǎn)定期隨機(jī)選擇周圍節(jié)點(diǎn)發(fā)送消息，而收到消息的節(jié)點(diǎn)也會(huì)重復(fù)該步驟；不可避免的引起同一節(jié)點(diǎn)消息多次接收，增加消息處理壓力。
Gossip 協(xié)議由于以上的優(yōu)缺點(diǎn)，所以適合于 AP 場(chǎng)景的數(shù)據(jù)一致性處理，常見應(yīng)用有：P2P 網(wǎng)絡(luò)通信、Apache Cassandra、Redis Cluster、Consul。
長按識(shí)別下圖二維碼，關(guān)注公眾號(hào)「Doocs開源社區(qū)」，第一時(shí)間跟你們分享好玩、實(shí)用的技術(shù)文章與業(yè)內(nèi)最新資訊。