前言

隨著近年來微服務(wù)理論越來越流行，其基礎(chǔ)之一的服務(wù)發(fā)現(xiàn)也越來越受到人們的重視。傳統(tǒng)的單點(diǎn)服務(wù)倉庫受限于不易擴(kuò)展、容災(zāi)麻煩等缺點(diǎn)的考慮已不再適用于復(fù)雜的集群系統(tǒng)。目前來說，大多數(shù)的成熟服務(wù)發(fā)現(xiàn)系統(tǒng)采用的是zookeeper、etcd或是consul作為服務(wù)存儲倉庫，如kubernetes用的就是etcd。雖然以上三種組件內(nèi)部協(xié)議和功能側(cè)重點(diǎn)各不相同，但最終都實(shí)現(xiàn)了一個具有強(qiáng)一致性、高可用性、分布式的存儲系統(tǒng)。對于這樣的存儲系統(tǒng)，分布式支持服務(wù)發(fā)現(xiàn)可用水平擴(kuò)展、高可用性可以保證了服務(wù)發(fā)現(xiàn)的穩(wěn)定性，KV系統(tǒng)存儲了服務(wù)數(shù)據(jù)，而唯一有質(zhì)疑的是強(qiáng)一致性。下面我們要探討一個問題，究竟服務(wù)發(fā)現(xiàn)是否真的需要強(qiáng)一致性？網(wǎng)上有一篇文章《為什么不要把ZooKeeper用于服務(wù)發(fā)現(xiàn)》探討了這個問題。有興趣的同學(xué)可以看一下。
　其實(shí)強(qiáng)一致性有兩個方面限制了服務(wù)發(fā)現(xiàn)：

• zookeeper這類組件的強(qiáng)一致性是有代價(jià)的：即在一個2n+1個節(jié)點(diǎn)組成的集群中，一旦少于n+1個節(jié)點(diǎn)工作，就不可用。假設(shè)一個服務(wù)發(fā)現(xiàn)集群有5個節(jié)點(diǎn)，當(dāng)3個以上節(jié)點(diǎn)出現(xiàn)故障時，整個集群也就無法提供服務(wù)了。拿CAP理論來說，就是犧牲了A（可用性）換取了C（一致性），但對于服務(wù)發(fā)現(xiàn)系統(tǒng)，一般可以接受返回幾次錯誤數(shù)據(jù)，但是決不能容忍服務(wù)停擺的。
• zookeeper這類組件雖然可以支持?jǐn)U展，但受自身實(shí)現(xiàn)一致性協(xié)議的限制，擴(kuò)展節(jié)點(diǎn)數(shù)目越多，為達(dá)到半數(shù)的通信成本也越高，因此是無法實(shí)現(xiàn)無限擴(kuò)展的。

本文介紹了一種基于流言協(xié)議的KV存儲系統(tǒng)，該系統(tǒng)具有最終一致性、分布式、高可用的特點(diǎn)，可以有效的運(yùn)用與服務(wù)發(fā)現(xiàn)系統(tǒng)。

服務(wù)倉庫工作示意圖

流言協(xié)議

流言協(xié)議是一個去中心化的通信協(xié)議，當(dāng)某節(jié)點(diǎn)收到一個新事件時會有以下的操作：

• 隨機(jī)的選擇其他n個節(jié)點(diǎn)作為傳輸對象。
• 若其他節(jié)點(diǎn)第一次收到該事件，則隨機(jī)選擇n個節(jié)點(diǎn)轉(zhuǎn)發(fā)。
• 每個收到事件信息的節(jié)點(diǎn)重復(fù)完成上述工作。

流言協(xié)議主要實(shí)現(xiàn)了兩個功能：節(jié)點(diǎn)存活檢查和消息傳遞。常用的檢測節(jié)點(diǎn)存活技術(shù)是心跳協(xié)議，即定時發(fā)出心跳包來證明自己存活。但這樣的心跳協(xié)議有很多缺點(diǎn)，首先如何是確保心跳包準(zhǔn)確送達(dá)目標(biāo)節(jié)點(diǎn)，如果網(wǎng)絡(luò)問題導(dǎo)致心跳包沒有正確送達(dá)，會不會誤傷健康的節(jié)點(diǎn)？這個雖然可以通過協(xié)議來解決但同時導(dǎo)致了協(xié)議的復(fù)雜度。其次心跳協(xié)議是一個端到端的協(xié)議，如何應(yīng)用與大規(guī)模的集群中？采用星型拓?fù)浣Y(jié)構(gòu)會帶來單點(diǎn)問題；采用多對多拓?fù)潆S著節(jié)點(diǎn)數(shù)目過多帶來通訊成本急劇上升；采用環(huán)狀拓?fù)鋾驗(yàn)橥瑫r兩處節(jié)點(diǎn)故障導(dǎo)致不可用。消息傳遞同樣面臨這存活檢測遇到上述問題，如何保證數(shù)據(jù)準(zhǔn)確傳達(dá)和選擇通訊拓?fù)浣Y(jié)構(gòu)？對此流言協(xié)議可以很好的解決這些問題。

不靠譜的拓?fù)浣Y(jié)構(gòu)

"SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol"。這篇論文詳細(xì)描述了流言協(xié)議實(shí)現(xiàn)方式：

• 采用兩次檢查的存活協(xié)議，節(jié)點(diǎn)定時ping已知任一節(jié)點(diǎn)，如果沒有收到ack，則轉(zhuǎn)發(fā)請求給k個節(jié)點(diǎn)，讓這些節(jié)點(diǎn)發(fā)送ping給被檢測節(jié)點(diǎn)，若這些節(jié)點(diǎn)都沒有收到ack就認(rèn)為被檢測節(jié)點(diǎn)有問題。
• 需要傳輸?shù)臄?shù)據(jù)作為ping和ack包的附帶數(shù)據(jù)一起傳輸，有效減少傳輸次數(shù)。

此文章同時也論證了流言協(xié)議兩個特點(diǎn)：

• 對于每個節(jié)點(diǎn)來說，存活檢查需要的時間和數(shù)據(jù)載荷大小與集群規(guī)模無關(guān)。（成本固定）
• 對于一個n個節(jié)點(diǎn)的集群，消息傳遞到全部節(jié)點(diǎn)的時間是K*log(n)。（快速收斂）

流言協(xié)議的傳播速度

服務(wù)發(fā)現(xiàn)的KV存儲系統(tǒng)

現(xiàn)在我們需要設(shè)計(jì)一個用于服務(wù)發(fā)現(xiàn)的KV存儲系統(tǒng)，考慮到實(shí)踐運(yùn)用場合，該系統(tǒng)應(yīng)該具備：

• 分布式：存儲系統(tǒng)由多個節(jié)點(diǎn)構(gòu)成。
• 高可用：每個存活的節(jié)點(diǎn)都能提供服務(wù)。
• 最終一致性：任一節(jié)點(diǎn)上的數(shù)據(jù)變化最終體現(xiàn)在各個節(jié)點(diǎn)上。由于服務(wù)啟停是個頻率較低的過程，服務(wù)發(fā)現(xiàn)系統(tǒng)可以忍受幾秒的數(shù)據(jù)的不一致，但要求最終提供的服務(wù)數(shù)據(jù)是一致的。
• 狀態(tài)檢測：新增或是移除節(jié)點(diǎn)，亦或是節(jié)點(diǎn)故障，其他節(jié)點(diǎn)必須知悉，并對應(yīng)新增或刪減數(shù)據(jù)。

我們不難發(fā)現(xiàn)分布式、高可用和狀態(tài)檢測這些特性流言協(xié)議已經(jīng)實(shí)現(xiàn)了。無論集群的節(jié)點(diǎn)數(shù)目有多少，每個節(jié)點(diǎn)只要付出固定的成本就可以實(shí)現(xiàn)快速的存活檢測和數(shù)據(jù)傳輸。這樣我們可以構(gòu)建這樣的模型：

• 集群中的每個節(jié)點(diǎn)各自維護(hù)一個KV存儲。
• 對節(jié)點(diǎn)KV數(shù)據(jù)的修改都會通過流言協(xié)議擴(kuò)散到集群其他節(jié)點(diǎn)。
• 節(jié)點(diǎn)收到其他節(jié)點(diǎn)數(shù)據(jù)增減消息后會對自身的KV存儲進(jìn)行增減操作并擴(kuò)散。
• 新增節(jié)點(diǎn)在加入集群后立刻將本節(jié)點(diǎn)存儲的數(shù)據(jù)通過流言協(xié)議同步給集群其他節(jié)點(diǎn)。

但是這樣模型還是有些問題。假設(shè)兩個不同節(jié)點(diǎn)同時對一個Key值的數(shù)據(jù)進(jìn)行修改，那對于集群的其他節(jié)點(diǎn)來說，究竟應(yīng)該采用哪個節(jié)點(diǎn)的數(shù)據(jù)？這種情況會導(dǎo)致喪失最終一致性。我們發(fā)現(xiàn)僅僅依靠流言協(xié)議是無法實(shí)現(xiàn)服務(wù)發(fā)現(xiàn)的，還要做一些其他的工作。
　針對服務(wù)發(fā)現(xiàn)這個特殊場合，我們不難發(fā)現(xiàn)一個特點(diǎn)：每個節(jié)點(diǎn)只會主動增減和自己相關(guān)的數(shù)據(jù)。也就是說A節(jié)點(diǎn)上服務(wù)發(fā)生變化只會讓A節(jié)點(diǎn)增減數(shù)據(jù)，其他節(jié)點(diǎn)只是被動的接收A節(jié)點(diǎn)的數(shù)據(jù)變化。A節(jié)點(diǎn)上的數(shù)據(jù)，A節(jié)點(diǎn)具有最終的發(fā)言權(quán)！為了解決不同節(jié)點(diǎn)同時寫帶來的數(shù)據(jù)不一致問題，我們加上兩條規(guī)定：

• 每個節(jié)點(diǎn)只能修改屬于自己的數(shù)據(jù)，然后再將數(shù)據(jù)同步給集群其他節(jié)點(diǎn)。

• 當(dāng)某個節(jié)點(diǎn)故障或脫離集群時，其他的節(jié)點(diǎn)刪除與此節(jié)點(diǎn)相關(guān)數(shù)據(jù)。

  
  
  數(shù)據(jù)同步模型

但這并不能完全解決最終一致性的問題。流言協(xié)議不能保證傳輸?shù)捻樞蛐?，也就是說假設(shè)A節(jié)點(diǎn)先發(fā)送了消息a=1，再發(fā)送a=2。B節(jié)點(diǎn)可能會先收到a=2再收到a=1。消息傳輸完畢后，我們發(fā)現(xiàn)A節(jié)點(diǎn)中a=2，B節(jié)點(diǎn)a=1，失去了最終一致性。其實(shí)解決這種只有唯一寫者的順序不一致問題很簡單，只需要對每個消息添加一個版本號就可以。只有收到的消息比當(dāng)前數(shù)據(jù)版本號新才修改數(shù)據(jù)。在這新增兩條規(guī)則：

• 每個節(jié)點(diǎn)維護(hù)一個版本號，當(dāng)修改數(shù)據(jù)時增加此版本號。其他節(jié)點(diǎn)收到同步消息時對比消息的版本號和自身數(shù)據(jù)的版本號，只有發(fā)現(xiàn)消息版本號大于數(shù)據(jù)版本號才對數(shù)據(jù)進(jìn)行修改。
• 刪除數(shù)據(jù)時并不直接刪除數(shù)據(jù)，而是記錄下此時的版本號，標(biāo)記此數(shù)據(jù)刪除，防止過時消息污染數(shù)據(jù)。經(jīng)過一段時間才回收被刪除數(shù)據(jù)。

到這里看起來已經(jīng)解決了最終一致性的問題，但是在實(shí)踐運(yùn)用場合我們發(fā)現(xiàn)這樣的問題。如圖在T3時刻，A節(jié)點(diǎn)發(fā)生崩潰重啟再加入集群，由于重啟時間較短，集群其他節(jié)點(diǎn)不認(rèn)為此節(jié)點(diǎn)失活因此保留A節(jié)點(diǎn)相關(guān)數(shù)據(jù)。但新啟動的A節(jié)點(diǎn)并不知道崩潰前的最新版本號，還是從版本號1開始同步數(shù)據(jù)。這個同步消息自然遭到目前版本是3的B節(jié)點(diǎn)的拒絕，至此最終一致性喪失。

節(jié)點(diǎn)崩潰導(dǎo)致最終一致性喪失

　解決這個問題有兩個思路，一個是實(shí)時將節(jié)點(diǎn)最新的版本號記錄在本地文件或是外部存儲器中，這樣即使崩潰重啟也能恢復(fù)最新版本號。另一種方法比較簡單，按照之前的原則”節(jié)點(diǎn)具有本節(jié)點(diǎn)數(shù)據(jù)的最終發(fā)言權(quán)“，當(dāng)A節(jié)點(diǎn)發(fā)現(xiàn)屬于自己節(jié)點(diǎn)的數(shù)據(jù)版本號竟然比自己當(dāng)前版本號還大時，就立即明白本節(jié)點(diǎn)的版本號已經(jīng)過時了。這樣將本節(jié)點(diǎn)版本號置為數(shù)據(jù)版本號+1，再同步數(shù)據(jù)，就解決了這個問題。如圖雖然T4時刻同步失敗了，當(dāng)T5時刻收到B節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)后，A節(jié)點(diǎn)更新了自己的版本號，只后同步數(shù)據(jù)就OK了。在此新增一條規(guī)則：

• 節(jié)點(diǎn)收到屬于自己的數(shù)據(jù)消息且發(fā)現(xiàn)版本號比自己版本號大時，更新自己的版本號。

  
  
  更新過時版本號

通過以上的幾條規(guī)則，我們成功的在流言協(xié)議的基礎(chǔ)上實(shí)現(xiàn)了最終數(shù)據(jù)一致性，從而完成了基于服務(wù)發(fā)現(xiàn)KV存儲的設(shè)計(jì)。在實(shí)際使用過程中，服務(wù)端嵌入KV存儲來實(shí)時更新集群可用服務(wù)，客戶端既可以通過嵌入KV存儲也可以通過查詢嵌入KV存儲的DNS服務(wù)器來查詢服務(wù)。

基于流言協(xié)議的服務(wù)發(fā)現(xiàn)框架

代碼實(shí)現(xiàn)

實(shí)現(xiàn)流言協(xié)議并不是一件輕松的事情，幸好hashicorp的memberlist組件已經(jīng)幫我們實(shí)現(xiàn)了流言協(xié)議主要功能。memberlist的流言傳播用的是udp協(xié)議。這帶來一個問題，眾所周知udp是一個一個包傳輸?shù)?，?shù)據(jù)信息作為ping或ack的附加載荷受限與udp包的大小，這限制了包的信息的傳播速度。幸好服務(wù)發(fā)現(xiàn)數(shù)據(jù)量不是很大，udp包也完全滿足。但只有一種情況除外，那就是新節(jié)點(diǎn)加入集群時需要同步自己全部的數(shù)據(jù)，此時數(shù)據(jù)量就可能比較大了。如果只用udp傳輸協(xié)議，可能導(dǎo)致數(shù)據(jù)同步比較慢。memberlist為此新增了tcp同步的功能，我們可以利用tcp同步的接口一次傳輸大量數(shù)據(jù)，加速數(shù)據(jù)收斂速度。

參考

https://github.com/hashicorp/memberlist
https://github.com/docker/libnetwork
Gossip Protocol
SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol