背景

Gossip protocol 也叫 Epidemic Protocol （流行病協(xié)議），實(shí)際上它還有很多別名，比如：“流言算法”、“疫情傳播算法”等。

這個(gè)協(xié)議的作用就像其名字表示的意思一樣，非常容易理解，它的方式其實(shí)在我們?nèi)粘Ｉ钪幸埠艹Ｒ姡热珉娔X病毒的傳播，森林大火，細(xì)胞擴(kuò)散等等。

Gossip protocol 最早是在 1987 年發(fā)表在 ACM 上的論文 《Epidemic Algorithms for Replicated Database Maintenance》中被提出。主要用在分布式數(shù)據(jù)庫系統(tǒng)中各個(gè)副本節(jié)點(diǎn)同步數(shù)據(jù)之用，這種場(chǎng)景的一個(gè)最大特點(diǎn)就是組成的網(wǎng)絡(luò)的節(jié)點(diǎn)都是對(duì)等節(jié)點(diǎn)，是非結(jié)構(gòu)化網(wǎng)絡(luò)，這區(qū)別與之前介紹的用于結(jié)構(gòu)化網(wǎng)絡(luò)中的 DHT 算法 Kadmelia。

我們知道，很多知名的 P2P 網(wǎng)絡(luò)或區(qū)塊鏈項(xiàng)目，比如 IPFS，Ethereum 等，都使用了 Kadmelia 算法，而大名鼎鼎的 Bitcoin 則是使用了 Gossip 協(xié)議來傳播交易和區(qū)塊信息。

實(shí)際上，只要仔細(xì)分析一下場(chǎng)景就知道，Ethereum 使用 DHT 算法并不是很合理，因?yàn)樗褂霉?jié)點(diǎn)保存整個(gè)鏈數(shù)據(jù)，不像 IPFS 那樣分片保存數(shù)據(jù)，因此 Ethereum 真正適合的協(xié)議應(yīng)該像 Bitcoin 那樣，是 Gossip 協(xié)議。

這里先簡(jiǎn)單介紹一下 Gossip 協(xié)議的執(zhí)行過程：

Gossip 過程是由種子節(jié)點(diǎn)發(fā)起，當(dāng)一個(gè)種子節(jié)點(diǎn)有狀態(tài)需要更新到網(wǎng)絡(luò)中的其他節(jié)點(diǎn)時(shí)，它會(huì)隨機(jī)的選擇周圍幾個(gè)節(jié)點(diǎn)散播消息，收到消息的節(jié)點(diǎn)也會(huì)重復(fù)該過程，直至最終網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都收到了消息。這個(gè)過程可能需要一定的時(shí)間，由于不能保證某個(gè)時(shí)刻所有節(jié)點(diǎn)都收到消息，但是理論上最終所有節(jié)點(diǎn)都會(huì)收到消息，因此它是一個(gè)最終一致性協(xié)議。

Gossip 演示

現(xiàn)在，我們通過一個(gè)具體的實(shí)例來深入體會(huì)一下 Gossip 傳播的完整過程

為了表述清楚，我們先做一些前提設(shè)定

1、Gossip 是周期性的散播消息，把周期限定為 1 秒

2、被感染節(jié)點(diǎn)隨機(jī)選擇 k 個(gè)鄰接節(jié)點(diǎn)（fan-out）散播消息，這里把 fan-out 設(shè)置為 3，每次最多往 3 個(gè)節(jié)點(diǎn)散播。

3、每次散播消息都選擇尚未發(fā)送過的節(jié)點(diǎn)進(jìn)行散播

4、收到消息的節(jié)點(diǎn)不再往發(fā)送節(jié)點(diǎn)散播，比如 A -> B，那么 B 進(jìn)行散播的時(shí)候，不再發(fā)給 A。

注意：Gossip 過程是異步的，也就是說發(fā)消息的節(jié)點(diǎn)不會(huì)關(guān)注對(duì)方是否收到，即不等待響應(yīng)；不管對(duì)方有沒有收到，它都會(huì)每隔 1 秒向周圍節(jié)點(diǎn)發(fā)消息。異步是它的優(yōu)點(diǎn)，而消息冗余則是它的缺點(diǎn)。

這里一共有 16 個(gè)節(jié)點(diǎn)，節(jié)點(diǎn) 1 為初始被感染節(jié)點(diǎn)，通過 Gossip 過程，最終所有節(jié)點(diǎn)都被感染：

image

Gossip 的特點(diǎn)（優(yōu)勢(shì)）

1）擴(kuò)展性

網(wǎng)絡(luò)可以允許節(jié)點(diǎn)的任意增加和減少，新增加的節(jié)點(diǎn)的狀態(tài)最終會(huì)與其他節(jié)點(diǎn)一致。

2）容錯(cuò)

網(wǎng)絡(luò)中任何節(jié)點(diǎn)的宕機(jī)和重啟都不會(huì)影響 Gossip 消息的傳播，Gossip 協(xié)議具有天然的分布式系統(tǒng)容錯(cuò)特性。

3）去中心化

Gossip 協(xié)議不要求任何中心節(jié)點(diǎn)，所有節(jié)點(diǎn)都可以是對(duì)等的，任何一個(gè)節(jié)點(diǎn)無需知道整個(gè)網(wǎng)絡(luò)狀況，只要網(wǎng)絡(luò)是連通的，任意一個(gè)節(jié)點(diǎn)就可以把消息散播到全網(wǎng)。

4）一致性收斂

Gossip 協(xié)議中的消息會(huì)以一傳十、十傳百一樣的指數(shù)級(jí)速度在網(wǎng)絡(luò)中快速傳播，因此系統(tǒng)狀態(tài)的不一致可以在很快的時(shí)間內(nèi)收斂到一致。消息傳播速度達(dá)到了 logN。

5）簡(jiǎn)單

Gossip 協(xié)議的過程極其簡(jiǎn)單，實(shí)現(xiàn)起來幾乎沒有太多復(fù)雜性。

Márk Jelasity 在它的 Gossip一書中對(duì)其進(jìn)行了歸納：

image

Gossip 的缺陷

分布式網(wǎng)絡(luò)中，沒有一種完美的解決方案，Gossip 協(xié)議跟其他協(xié)議一樣，也有一些不可避免的缺陷，主要是兩個(gè)：

1）消息的延遲

由于 Gossip 協(xié)議中，節(jié)點(diǎn)只會(huì)隨機(jī)向少數(shù)幾個(gè)節(jié)點(diǎn)發(fā)送消息，消息最終是通過多個(gè)輪次的散播而到達(dá)全網(wǎng)的，因此使用 Gossip 協(xié)議會(huì)造成不可避免的消息延遲。不適合用在對(duì)實(shí)時(shí)性要求較高的場(chǎng)景下。

2）消息冗余

Gossip 協(xié)議規(guī)定，節(jié)點(diǎn)會(huì)定期隨機(jī)選擇周圍節(jié)點(diǎn)發(fā)送消息，而收到消息的節(jié)點(diǎn)也會(huì)重復(fù)該步驟，因此就不可避免的存在消息重復(fù)發(fā)送給同一節(jié)點(diǎn)的情況，造成了消息的冗余，同時(shí)也增加了收到消息的節(jié)點(diǎn)的處理壓力。而且，由于是定期發(fā)送，因此，即使收到了消息的節(jié)點(diǎn)還會(huì)反復(fù)收到重復(fù)消息，加重了消息的冗余。

Gossip 類型

Gossip 有兩種類型：

• Anti-Entropy（反熵）：以固定的概率傳播所有的數(shù)據(jù)
• Rumor-Mongering（謠言傳播）：僅傳播新到達(dá)的數(shù)據(jù)

Anti-Entropy 是 SI model，節(jié)點(diǎn)只有兩種狀態(tài)，Suspective 和 Infective，叫做 simple epidemics。

Rumor-Mongering 是 SIR model，節(jié)點(diǎn)有三種狀態(tài)，Suspective，Infective 和 Removed，叫做 complex epidemics。

其實(shí)，Anti-entropy 反熵是一個(gè)很奇怪的名詞，之所以定義成這樣，Jelasity 進(jìn)行了解釋，因?yàn)?entropy 是指混亂程度（disorder），而在這種模式下可以消除不同節(jié)點(diǎn)中數(shù)據(jù)的 disorder，因此 Anti-entropy 就是 anti-disorder。換句話說，它可以提高系統(tǒng)中節(jié)點(diǎn)之間的 similarity。

在 SI model 下，一個(gè)節(jié)點(diǎn)會(huì)把所有的數(shù)據(jù)都跟其他節(jié)點(diǎn)共享，以便消除節(jié)點(diǎn)之間數(shù)據(jù)的任何不一致，它可以保證最終、完全的一致。

由于在 SI model 下消息會(huì)不斷反復(fù)的交換，因此消息數(shù)量是非常龐大的，無限制的（unbounded），這對(duì)一個(gè)系統(tǒng)來說是一個(gè)巨大的開銷。

但是在 Rumor Mongering（SIR Model） 模型下，消息可以發(fā)送得更頻繁，因?yàn)橄⒅话钚?update，體積更小。而且，一個(gè) Rumor 消息在某個(gè)時(shí)間點(diǎn)之后會(huì)被標(biāo)記為 removed，并且不再被傳播，因此，SIR model 下，系統(tǒng)有一定的概率會(huì)不一致。

而由于，SIR Model 下某個(gè)時(shí)間點(diǎn)之后消息不再傳播，因此消息是有限的，系統(tǒng)開銷小。

Gossip 中的通信模式

在 Gossip 協(xié)議下，網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間有三種通信方式:

• 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 的收斂速度也是最快的。

復(fù)雜度分析

對(duì)于一個(gè)節(jié)點(diǎn)數(shù)為 N 的網(wǎng)絡(luò)來說，假設(shè)每個(gè) Gossip 周期，新感染的節(jié)點(diǎn)都能再感染至少一個(gè)新節(jié)點(diǎn)，那么 Gossip 協(xié)議退化成一個(gè)二叉樹查找，經(jīng)過 LogN 個(gè)周期之后，感染全網(wǎng)，時(shí)間開銷是 O(LogN)。由于每個(gè)周期，每個(gè)節(jié)點(diǎn)都會(huì)至少發(fā)出一次消息，因此，消息復(fù)雜度（消息數(shù)量 = N * N）是 O(N^2) 。注意，這是 Gossip 理論上最優(yōu)的收斂速度，但是在實(shí)際情況中，最優(yōu)的收斂速度是很難達(dá)到的。

假設(shè)某個(gè)節(jié)點(diǎn)在第 i 個(gè)周期被感染的概率為 pi，第 i+1 個(gè)周期被感染的概率為 pi+1 ，

1）則 Pull 的方式:

image

2）Push 方式：

image

顯然 Pull 的收斂速度大于 Push ，而每個(gè)節(jié)點(diǎn)在每個(gè)周期被感染的概率都是固定的 p (0<p<1)，因此 Gossip 算法是基于 p 的平方收斂，也稱為概率收斂，這在眾多的一致性算法中是非常獨(dú)特的。

冪等處理
一、背景

1. 前端重復(fù)提交選中的數(shù)據(jù)，應(yīng)該后臺(tái)只產(chǎn)生對(duì)應(yīng)這個(gè)數(shù)據(jù)的一個(gè)反應(yīng)結(jié)果。
   2. 我們發(fā)起一筆付款請(qǐng)求，應(yīng)該只扣用戶賬戶一次錢，當(dāng)遇到網(wǎng)絡(luò)重發(fā)或系統(tǒng)bug重發(fā)，也應(yīng)該只扣一次錢；
   3. 發(fā)送消息，也應(yīng)該只發(fā)一次，同樣的短信發(fā)給用戶，用戶會(huì)哭的；
   4. 創(chuàng)建業(yè)務(wù)訂單，一次業(yè)務(wù)請(qǐng)求只能創(chuàng)建一個(gè)，創(chuàng)建多個(gè)就會(huì)出大問題。

二、什么事冪等

一個(gè)操作，不論執(zhí)行多少次，產(chǎn)生的效果和返回的結(jié)果都是一樣的

同樣一個(gè)請(qǐng)求連續(xù)發(fā)兩遍（請(qǐng)求的參數(shù)可能有細(xì)微不一樣，比如時(shí)間戳，但是對(duì)后臺(tái)來說這應(yīng)該屬于同一個(gè)請(qǐng)求），想達(dá)到的目的是：兩個(gè)請(qǐng)求同時(shí)到達(dá)的時(shí)候只有一個(gè)請(qǐng)求在執(zhí)行，另外一個(gè)請(qǐng)求等待第一個(gè)請(qǐng)求結(jié)束，并返回相同結(jié)果。這就是冪等的意思。

三、實(shí)現(xiàn)冪等有哪些思路

1. 查詢操作

查詢一次和查詢多次，在數(shù)據(jù)不變的情況下，查詢結(jié)果是一樣的。select是天然的冪等操作

2. 刪除操作

刪除操作也是冪等的，刪除一次和多次刪除都是把數(shù)據(jù)刪除。(注意可能返回結(jié)果不一樣，刪除的數(shù)據(jù)不存在，返回0，刪除的數(shù)據(jù)多條，返回結(jié)果多個(gè))

3.唯一索引，防止新增臟數(shù)據(jù)

比如：支付寶的資金賬戶，支付寶也有用戶賬戶，每個(gè)用戶只能有一個(gè)資金賬戶，怎么防止給用戶創(chuàng)建資金賬戶多個(gè)，那么給資金賬戶表中的用戶ID加唯一索引，所以一個(gè)用戶新增成功一個(gè)資金賬戶記錄

要點(diǎn)：

唯一索引或唯一組合索引來防止新增數(shù)據(jù)存在臟數(shù)據(jù)

（當(dāng)表存在唯一索引，并發(fā)時(shí)新增報(bào)錯(cuò)時(shí)，再查詢一次就可以了，數(shù)據(jù)應(yīng)該已經(jīng)存在了，返回結(jié)果即可）

4. token機(jī)制，防止頁面重復(fù)提交

業(yè)務(wù)要求：

頁面的數(shù)據(jù)只能被點(diǎn)擊提交一次

發(fā)生原因：

由于重復(fù)點(diǎn)擊或者網(wǎng)絡(luò)重發(fā)，或者nginx重發(fā)等情況會(huì)導(dǎo)致數(shù)據(jù)被重復(fù)提交

解決辦法：

集群環(huán)境：采用token加redis（redis單線程的，處理需要排隊(duì)）

單JVM環(huán)境：采用token加redis或token加jvm內(nèi)存

處理流程：

1. 數(shù)據(jù)提交前要向服務(wù)的申請(qǐng)token，token放到redis或jvm內(nèi)存，token有效時(shí)間

2. 提交后后臺(tái)校驗(yàn)token，同時(shí)刪除token，生成新的token返回

token特點(diǎn)：

要申請(qǐng)，一次有效性，可以限流

注意：redis要用刪除操作來判斷token，刪除成功代表token校驗(yàn)通過，如果用select+delete來校驗(yàn)token，存在并發(fā)問題，不建議使用

5. 悲觀鎖

獲取數(shù)據(jù)的時(shí)候加鎖獲取

select * from table_xxx where id='xxx' for update;

注意：id字段一定是主鍵或者唯一索引，不然是鎖表，會(huì)死人的

悲觀鎖使用時(shí)一般伴隨事務(wù)一起使用，數(shù)據(jù)鎖定時(shí)間可能會(huì)很長(zhǎng)，根據(jù)實(shí)際情況選用

6. 樂觀鎖

樂觀鎖只是在更新數(shù)據(jù)那一刻鎖表，其他時(shí)間不鎖表，所以相對(duì)于悲觀鎖，效率更高。

樂觀鎖的實(shí)現(xiàn)方式多種多樣可以通過version或者其他狀態(tài)條件：

1）. 通過版本號(hào)實(shí)現(xiàn)

update table_xxx set name=#name#,version=version+1 where version=#version#

2）. 通過條件限制

update table_xxx set avai_amount=avai_amount-#subAmount# where avai_amount-#subAmount# >= 0

要求：quality-#subQuality# >= ，這個(gè)情景適合不用版本號(hào)，只更新是做數(shù)據(jù)安全校驗(yàn)，適合庫存模型，扣份額和回滾份額，性能更高

注意：樂觀鎖的更新操作，最好用主鍵或者唯一索引來更新,這樣是行鎖，否則更新時(shí)會(huì)鎖表，上面兩個(gè)sql改成下面的兩個(gè)更好

update table_xxx set name=#name#,version=version+1 where id=#id# and version=#version#

update table_xxx set avai_amount=avai_amount-#subAmount# where id=#id# and avai_amount-#subAmount# >= 0

7. 分布式鎖

還是拿插入數(shù)據(jù)的例子，如果是分布是系統(tǒng)，構(gòu)建全局唯一索引比較困難，例如唯一性的字段沒法確定，這時(shí)候可以引入分布式鎖，通過第三方的系統(tǒng)(redis或zookeeper)，在業(yè)務(wù)系統(tǒng)插入數(shù)據(jù)或者更新數(shù)據(jù)，獲取分布式鎖，然后做操作，之后釋放鎖，這樣其實(shí)是把多線程并發(fā)的鎖的思路，引入多多個(gè)系統(tǒng)，也就是分布式系統(tǒng)中得解決思路。

要點(diǎn)：某個(gè)長(zhǎng)流程處理過程要求不能并發(fā)執(zhí)行，可以在流程執(zhí)行之前根據(jù)某個(gè)標(biāo)志(用戶ID+后綴等)獲取分布式鎖，其他流程執(zhí)行時(shí)獲取鎖就會(huì)失敗，也就是同一時(shí)間該流程只能有一個(gè)能執(zhí)行成功，執(zhí)行完成后，釋放分布式鎖(分布式鎖要第三方系統(tǒng)提供)

8. select + insert

并發(fā)不高的后臺(tái)系統(tǒng)，或者一些任務(wù)JOB，為了支持冪等，支持重復(fù)執(zhí)行，簡(jiǎn)單的處理方法是，先查詢下一些關(guān)鍵數(shù)據(jù)，判斷是否已經(jīng)執(zhí)行過，在進(jìn)行業(yè)務(wù)處理，就可以了

注意：核心高并發(fā)流程不要用這種方法

9. 狀態(tài)機(jī)冪等

在設(shè)計(jì)單據(jù)相關(guān)的業(yè)務(wù)，或者是任務(wù)相關(guān)的業(yè)務(wù)，肯定會(huì)涉及到狀態(tài)機(jī)(狀態(tài)變更圖)，就是業(yè)務(wù)單據(jù)上面有個(gè)狀態(tài)，狀態(tài)在不同的情況下會(huì)發(fā)生變更，一般情況下存在有限狀態(tài)機(jī)，這時(shí)候，如果狀態(tài)機(jī)已經(jīng)處于下一個(gè)狀態(tài)，這時(shí)候來了一個(gè)上一個(gè)狀態(tài)的變更，理論上是不能夠變更的，這樣的話，保證了有限狀態(tài)機(jī)的冪等。

注意：訂單等單據(jù)類業(yè)務(wù)，存在很長(zhǎng)的狀態(tài)流轉(zhuǎn)，一定要深刻理解狀態(tài)機(jī)，對(duì)業(yè)務(wù)系統(tǒng)設(shè)計(jì)能力提高有很大幫助

10. 對(duì)外提供接口的api如何保證冪等

如銀聯(lián)提供的付款接口：需要接入商戶提交付款請(qǐng)求時(shí)附帶：source來源，seq序列號(hào)

source+seq在數(shù)據(jù)庫里面做唯一索引，防止多次付款，(并發(fā)時(shí)，只能處理一個(gè)請(qǐng)求
)

轉(zhuǎn)載于:https://www.cnblogs.com/h-c-g/p/10415048.html