背景
Gossip protocol 也叫 Epidemic Protocol （流行病協(xié)議），實際上它還有很多別名翠忠，比如：“流言算法”鞠苟、“疫情傳播算法”等。
這個協(xié)議的作用就像其名字表示的意思一樣秽之，非常容易理解当娱，它的方式其實在我們日常生活中也很常見，比如電腦病毒的傳播考榨，森林大火趾访，細胞擴散等等。
Gossip protocol 最早是在 1987 年發(fā)表在 ACM 上的論文 《Epidemic Algorithms for Replicated Database Maintenance》中被提出董虱。主要用在分布式數據庫系統(tǒng)中各個副本節(jié)點同步數據之用扼鞋，這種場景的一個最大特點就是組成的網絡的節(jié)點都是對等節(jié)點，是非結構化網絡愤诱，這區(qū)別與之前介紹的用于結構化網絡中的 DHT 算法 Kadmelia云头。
我們知道，很多知名的 P2P 網絡或區(qū)塊鏈項目淫半，比如 IPFS溃槐，Ethereum 等，都使用了 Kadmelia 算法科吭，而大名鼎鼎的 Bitcoin 則是使用了 Gossip 協(xié)議來傳播交易和區(qū)塊信息昏滴。
實際上，只要仔細分析一下場景就知道对人，Ethereum 使用 DHT 算法并不是很合理谣殊，因為它使用節(jié)點保存整個鏈數據，不像 IPFS 那樣分片保存數據牺弄，因此 Ethereum 真正適合的協(xié)議應該像 Bitcoin 那樣姻几，是 Gossip 協(xié)議。
這里先簡單介紹一下 Gossip 協(xié)議的執(zhí)行過程：
Gossip 過程是由種子節(jié)點發(fā)起势告，當一個種子節(jié)點有狀態(tài)需要更新到網絡中的其他節(jié)點時蛇捌，它會隨機的選擇周圍幾個節(jié)點散播消息，收到消息的節(jié)點也會重復該過程咱台，直至最終網絡中所有的節(jié)點都收到了消息络拌。這個過程可能需要一定的時間，由于不能保證某個時刻所有節(jié)點都收到消息回溺，但是理論上最終所有節(jié)點都會收到消息春贸，因此它是一個最終一致性協(xié)議混萝。
Gossip 演示
現(xiàn)在，我們通過一個具體的實例來深入體會一下 Gossip 傳播的完整過程
為了表述清楚祥诽，我們先做一些前提設定
1、Gossip 是周期性的散播消息瓮恭，把周期限定為 1 秒
2雄坪、被感染節(jié)點隨機選擇 k 個鄰接節(jié)點（fan-out）散播消息，這里把 fan-out 設置為 3屯蹦，每次最多往 3 個節(jié)點散播维哈。
3、每次散播消息都選擇尚未發(fā)送過的節(jié)點進行散播
4登澜、收到消息的節(jié)點不再往發(fā)送節(jié)點散播阔挠，比如 A -> B，那么 B 進行散播的時候脑蠕，不再發(fā)給 A购撼。
注意：Gossip 過程是異步的，也就是說發(fā)消息的節(jié)點不會關注對方是否收到谴仙，即不等待響應迂求；不管對方有沒有收到，它都會每隔 1 秒向周圍節(jié)點發(fā)消息晃跺。異步是它的優(yōu)點揩局，而消息冗余則是它的缺點。
這里一共有 16 個節(jié)點掀虎，節(jié)點 1 為初始被感染節(jié)點凌盯，通過 Gossip 過程，最終所有節(jié)點都被感染：
Gossip 的特點（優(yōu)勢）
1）擴展性
網絡可以允許節(jié)點的任意增加和減少烹玉，新增加的節(jié)點的狀態(tài)最終會與其他節(jié)點一致驰怎。
2）容錯
網絡中任何節(jié)點的宕機和重啟都不會影響 Gossip 消息的傳播，Gossip 協(xié)議具有天然的分布式系統(tǒng)容錯特性二打。
3）去中心化
Gossip 協(xié)議不要求任何中心節(jié)點砸西，所有節(jié)點都可以是對等的，任何一個節(jié)點無需知道整個網絡狀況址儒，只要網絡是連通的芹枷，任意一個節(jié)點就可以把消息散播到全網。
4）一致性收斂
Gossip 協(xié)議中的消息會以一傳十莲趣、十傳百一樣的指數級速度在網絡中快速傳播鸳慈，因此系統(tǒng)狀態(tài)的不一致可以在很快的時間內收斂到一致。消息傳播速度達到了 logN喧伞。
5）簡單
Gossip 協(xié)議的過程極其簡單走芋，實現(xiàn)起來幾乎沒有太多復雜性绩郎。
Márk Jelasity 在它的 Gossip一書中對其進行了歸納：
Gossip 的缺陷
分布式網絡中，沒有一種完美的解決方案翁逞，Gossip 協(xié)議跟其他協(xié)議一樣肋杖，也有一些不可避免的缺陷，主要是兩個：
1）消息的延遲
由于 Gossip 協(xié)議中挖函，節(jié)點只會隨機向少數幾個節(jié)點發(fā)送消息状植，消息最終是通過多個輪次的散播而到達全網的，因此使用 Gossip 協(xié)議會造成不可避免的消息延遲怨喘。不適合用在對實時性要求較高的場景下津畸。
2）消息冗余
Gossip 協(xié)議規(guī)定，節(jié)點會定期隨機選擇周圍節(jié)點發(fā)送消息必怜，而收到消息的節(jié)點也會重復該步驟肉拓，因此就不可避免的存在消息重復發(fā)送給同一節(jié)點的情況，造成了消息的冗余梳庆，同時也增加了收到消息的節(jié)點的處理壓力暖途。而且，由于是定期發(fā)送膏执，因此丧肴，即使收到了消息的節(jié)點還會反復收到重復消息，加重了消息的冗余胧后。
Gossip 類型
Gossip 有兩種類型：
- Anti-Entropy（反熵）：以固定的概率傳播所有的數據
- Rumor-Mongering（謠言傳播）：僅傳播新到達的數據
Anti-Entropy 是 SI model芋浮，節(jié)點只有兩種狀態(tài)，Suspective 和 Infective壳快，叫做 simple epidemics纸巷。
Rumor-Mongering 是 SIR model，節(jié)點有三種狀態(tài)眶痰，Suspective瘤旨，Infective 和 Removed，叫做 complex epidemics竖伯。
其實存哲，Anti-entropy 反熵是一個很奇怪的名詞，之所以定義成這樣七婴，Jelasity 進行了解釋祟偷，因為 entropy 是指混亂程度（disorder），而在這種模式下可以消除不同節(jié)點中數據的 disorder打厘，因此 Anti-entropy 就是 anti-disorder修肠。換句話說，它可以提高系統(tǒng)中節(jié)點之間的 similarity户盯。
在 SI model 下嵌施，一個節(jié)點會把所有的數據都跟其他節(jié)點共享饲化，以便消除節(jié)點之間數據的任何不一致，它可以保證最終吗伤、完全的一致吃靠。
由于在 SI model 下消息會不斷反復的交換，因此消息數量是非常龐大的足淆，無限制的（unbounded）巢块，這對一個系統(tǒng)來說是一個巨大的開銷。
但是在 Rumor Mongering（SIR Model） 模型下缸浦，消息可以發(fā)送得更頻繁夕冲，因為消息只包含最新 update氮兵，體積更小裂逐。而且，一個 Rumor 消息在某個時間點之后會被標記為 removed泣栈，并且不再被傳播卜高，因此，SIR model 下南片，系統(tǒng)有一定的概率會不一致掺涛。
而由于，SIR Model 下某個時間點之后消息不再傳播疼进，因此消息是有限的薪缆，系統(tǒng)開銷小。
Gossip 中的通信模式
在 Gossip 協(xié)議下伞广，網絡中兩個節(jié)點之間有三種通信方式:
- Push: 節(jié)點 A 將數據 (key,value,version) 及對應的版本號推送給 B 節(jié)點拣帽，B 節(jié)點更新 A 中比自己新的數據
- Pull：A 僅將數據 key, version 推送給 B，B 將本地比 A 新的數據（Key, value, version）推送給 A嚼锄，A 更新本地
- Push/Pull：與 Pull 類似减拭，只是多了一步，A 再將本地比 B 新的數據推送給 B区丑，B 則更新本地
如果把兩個節(jié)點數據同步一次定義為一個周期拧粪，則在一個周期內，Push 需通信 1 次沧侥，Pull 需 2 次可霎，Push/Pull 則需 3 次。雖然消息數增加了宴杀，但從效果上來講啥纸，Push/Pull 最好，理論上一個周期內可以使兩個節(jié)點完全一致婴氮。直觀上斯棒，Push/Pull 的收斂速度也是最快的盾致。
復雜度分析
對于一個節(jié)點數為 N 的網絡來說，假設每個 Gossip 周期荣暮，新感染的節(jié)點都能再感染至少一個新節(jié)點庭惜，那么 Gossip 協(xié)議退化成一個二叉樹查找，經過 LogN 個周期之后穗酥，感染全網护赊，時間開銷是 O(LogN)。由于每個周期砾跃，每個節(jié)點都會至少發(fā)出一次消息骏啰，因此，消息復雜度（消息數量 = N * N）是 O(N^2) 抽高。注意判耕，這是 Gossip 理論上最優(yōu)的收斂速度，但是在實際情況中翘骂，最優(yōu)的收斂速度是很難達到的壁熄。
假設某個節(jié)點在第 i 個周期被感染的概率為 pi，第 i+1 個周期被感染的概率為 pi+1 碳竟，
1）則 Pull 的方式:
2）Push 方式：
顯然 Pull 的收斂速度大于 Push 草丧，而每個節(jié)點在每個周期被感染的概率都是固定的 p (0<p<1)，因此 Gossip 算法是基于 p 的平方收斂莹桅，也稱為概率收斂昌执，這在眾多的一致性算法中是非常獨特的。
冪等處理
一诈泼、背景
-
前端重復提交選中的數據懂拾，應該后臺只產生對應這個數據的一個反應結果。
2. 我們發(fā)起一筆付款請求厂汗，應該只扣用戶賬戶一次錢委粉，當遇到網絡重發(fā)或系統(tǒng)bug重發(fā)，也應該只扣一次錢娶桦；
3. 發(fā)送消息贾节，也應該只發(fā)一次，同樣的短信發(fā)給用戶衷畦，用戶會哭的栗涂；
4. 創(chuàng)建業(yè)務訂單，一次業(yè)務請求只能創(chuàng)建一個祈争，創(chuàng)建多個就會出大問題斤程。
二、什么事冪等
一個操作，不論執(zhí)行多少次忿墅，產生的效果和返回的結果都是一樣的
同樣一個請求連續(xù)發(fā)兩遍（請求的參數可能有細微不一樣扁藕，比如時間戳，但是對后臺來說這應該屬于同一個請求）疚脐，想達到的目的是：兩個請求同時到達的時候只有一個請求在執(zhí)行亿柑，另外一個請求等待第一個請求結束，并返回相同結果棍弄。這就是冪等的意思望薄。
三、實現(xiàn)冪等有哪些思路
1. 查詢操作
查詢一次和查詢多次呼畸，在數據不變的情況下痕支，查詢結果是一樣的。select是天然的冪等操作
2. 刪除操作
刪除操作也是冪等的蛮原，刪除一次和多次刪除都是把數據刪除卧须。(注意可能返回結果不一樣，刪除的數據不存在瞬痘，返回0故慈，刪除的數據多條板熊，返回結果多個)
3.唯一索引框全，防止新增臟數據
比如：支付寶的資金賬戶，支付寶也有用戶賬戶干签，每個用戶只能有一個資金賬戶津辩，怎么防止給用戶創(chuàng)建資金賬戶多個，那么給資金賬戶表中的用戶ID加唯一索引容劳，所以一個用戶新增成功一個資金賬戶記錄
要點：
唯一索引或唯一組合索引來防止新增數據存在臟數據
（當表存在唯一索引喘沿，并發(fā)時新增報錯時，再查詢一次就可以了竭贩，數據應該已經存在了蚜印，返回結果即可）
4. token機制，防止頁面重復提交
業(yè)務要求：
頁面的數據只能被點擊提交一次
發(fā)生原因：
由于重復點擊或者網絡重發(fā)留量，或者nginx重發(fā)等情況會導致數據被重復提交
解決辦法：
集群環(huán)境：采用token加redis（redis單線程的窄赋，處理需要排隊）
單JVM環(huán)境：采用token加redis或token加jvm內存
處理流程：
1. 數據提交前要向服務的申請token，token放到redis或jvm內存楼熄，token有效時間
2. 提交后后臺校驗token忆绰，同時刪除token，生成新的token返回
token特點：
要申請可岂，一次有效性错敢，可以限流
注意：redis要用刪除操作來判斷token，刪除成功代表token校驗通過缕粹，如果用select+delete來校驗token稚茅，存在并發(fā)問題纸淮，不建議使用
5. 悲觀鎖
獲取數據的時候加鎖獲取
select * from table_xxx where id='xxx' for update;
注意：id字段一定是主鍵或者唯一索引，不然是鎖表亚享，會死人的
悲觀鎖使用時一般伴隨事務一起使用萎馅，數據鎖定時間可能會很長，根據實際情況選用
6. 樂觀鎖
樂觀鎖只是在更新數據那一刻鎖表虹蒋，其他時間不鎖表糜芳，所以相對于悲觀鎖，效率更高魄衅。
樂觀鎖的實現(xiàn)方式多種多樣可以通過version或者其他狀態(tài)條件：
1）. 通過版本號實現(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# >= 峭竣，這個情景適合不用版本號，只更新是做數據安全校驗晃虫，適合庫存模型皆撩，扣份額和回滾份額，性能更高
注意：樂觀鎖的更新操作哲银，最好用主鍵或者唯一索引來更新,這樣是行鎖扛吞，否則更新時會鎖表，上面兩個sql改成下面的兩個更好
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. 分布式鎖
還是拿插入數據的例子荆责，如果是分布是系統(tǒng)滥比，構建全局唯一索引比較困難，例如唯一性的字段沒法確定做院，這時候可以引入分布式鎖盲泛，通過第三方的系統(tǒng)(redis或zookeeper)，在業(yè)務系統(tǒng)插入數據或者更新數據键耕，獲取分布式鎖寺滚，然后做操作，之后釋放鎖屈雄，這樣其實是把多線程并發(fā)的鎖的思路村视，引入多多個系統(tǒng)，也就是分布式系統(tǒng)中得解決思路酒奶。
要點：某個長流程處理過程要求不能并發(fā)執(zhí)行蚁孔，可以在流程執(zhí)行之前根據某個標志(用戶ID+后綴等)獲取分布式鎖，其他流程執(zhí)行時獲取鎖就會失敗讥蟆，也就是同一時間該流程只能有一個能執(zhí)行成功勒虾，執(zhí)行完成后，釋放分布式鎖(分布式鎖要第三方系統(tǒng)提供)
8. select + insert
并發(fā)不高的后臺系統(tǒng)瘸彤，或者一些任務JOB修然，為了支持冪等，支持重復執(zhí)行，簡單的處理方法是愕宋，先查詢下一些關鍵數據玻靡，判斷是否已經執(zhí)行過，在進行業(yè)務處理中贝，就可以了
注意：核心高并發(fā)流程不要用這種方法
9. 狀態(tài)機冪等
在設計單據相關的業(yè)務囤捻，或者是任務相關的業(yè)務，肯定會涉及到狀態(tài)機(狀態(tài)變更圖)邻寿，就是業(yè)務單據上面有個狀態(tài)蝎土，狀態(tài)在不同的情況下會發(fā)生變更，一般情況下存在有限狀態(tài)機绣否，這時候誊涯，如果狀態(tài)機已經處于下一個狀態(tài)，這時候來了一個上一個狀態(tài)的變更蒜撮，理論上是不能夠變更的暴构，這樣的話，保證了有限狀態(tài)機的冪等段磨。
注意：訂單等單據類業(yè)務取逾，存在很長的狀態(tài)流轉，一定要深刻理解狀態(tài)機苹支，對業(yè)務系統(tǒng)設計能力提高有很大幫助
10. 對外提供接口的api如何保證冪等
如銀聯(lián)提供的付款接口：需要接入商戶提交付款請求時附帶：source來源砾隅，seq序列號
source+seq在數據庫里面做唯一索引，防止多次付款沐序，(并發(fā)時琉用，只能處理一個請求
)
