前言
隨著近年來(lái)微服務(wù)理論越來(lái)越流行份乒，其基礎(chǔ)之一的服務(wù)發(fā)現(xiàn)也越來(lái)越受到人們的重視半沽。傳統(tǒng)的單點(diǎn)服務(wù)倉(cāng)庫(kù)受限于不易擴(kuò)展砂代、容災(zāi)麻煩等缺點(diǎn)的考慮已不再適用于復(fù)雜的集群系統(tǒng)。目前來(lái)說(shuō)，大多數(shù)的成熟服務(wù)發(fā)現(xiàn)系統(tǒng)采用的是zookeeper琳拭、etcd或是consul作為服務(wù)存儲(chǔ)倉(cāng)庫(kù)训堆，如kubernetes用的就是etcd。雖然以上三種組件內(nèi)部協(xié)議和功能側(cè)重點(diǎn)各不相同白嘁，但最終都實(shí)現(xiàn)了一個(gè)具有強(qiáng)一致性坑鱼、高可用性、分布式的存儲(chǔ)系統(tǒng)絮缅。對(duì)于這樣的存儲(chǔ)系統(tǒng)鲁沥，分布式支持服務(wù)發(fā)現(xiàn)可用水平擴(kuò)展、高可用性可以保證了服務(wù)發(fā)現(xiàn)的穩(wěn)定性耕魄，KV系統(tǒng)存儲(chǔ)了服務(wù)數(shù)據(jù)黍析，而唯一有質(zhì)疑的是強(qiáng)一致性。下面我們要探討一個(gè)問題屎开，究竟服務(wù)發(fā)現(xiàn)是否真的需要強(qiáng)一致性？網(wǎng)上有一篇文章《為什么不要把ZooKeeper用于服務(wù)發(fā)現(xiàn)》探討了這個(gè)問題马靠。有興趣的同學(xué)可以看一下奄抽。
其實(shí)強(qiáng)一致性有兩個(gè)方面限制了服務(wù)發(fā)現(xiàn)：
- zookeeper這類組件的強(qiáng)一致性是有代價(jià)的：即在一個(gè)2n+1個(gè)節(jié)點(diǎn)組成的集群中，一旦少于n+1個(gè)節(jié)點(diǎn)工作甩鳄，就不可用逞度。假設(shè)一個(gè)服務(wù)發(fā)現(xiàn)集群有5個(gè)節(jié)點(diǎn)，當(dāng)3個(gè)以上節(jié)點(diǎn)出現(xiàn)故障時(shí)妙啃，整個(gè)集群也就無(wú)法提供服務(wù)了档泽。拿CAP理論來(lái)說(shuō)，就是犧牲了A（可用性）換取了C（一致性）揖赴，但對(duì)于服務(wù)發(fā)現(xiàn)系統(tǒng)馆匿，一般可以接受返回幾次錯(cuò)誤數(shù)據(jù)，但是決不能容忍服務(wù)停擺的燥滑。
- zookeeper這類組件雖然可以支持?jǐn)U展渐北，但受自身實(shí)現(xiàn)一致性協(xié)議的限制，擴(kuò)展節(jié)點(diǎn)數(shù)目越多铭拧，為達(dá)到半數(shù)的通信成本也越高赃蛛，因此是無(wú)法實(shí)現(xiàn)無(wú)限擴(kuò)展的。
本文介紹了一種基于流言協(xié)議的KV存儲(chǔ)系統(tǒng)搀菩，該系統(tǒng)具有最終一致性呕臂、分布式、高可用的特點(diǎn)肪跋，可以有效的運(yùn)用與服務(wù)發(fā)現(xiàn)系統(tǒng)歧蒋。
流言協(xié)議
流言協(xié)議是一個(gè)去中心化的通信協(xié)議，當(dāng)某節(jié)點(diǎn)收到一個(gè)新事件時(shí)會(huì)有以下的操作：
- 隨機(jī)的選擇其他n個(gè)節(jié)點(diǎn)作為傳輸對(duì)象。
- 若其他節(jié)點(diǎn)第一次收到該事件疏尿，則隨機(jī)選擇n個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)瘟芝。
- 每個(gè)收到事件信息的節(jié)點(diǎn)重復(fù)完成上述工作。
流言協(xié)議主要實(shí)現(xiàn)了兩個(gè)功能：節(jié)點(diǎn)存活檢查和消息傳遞褥琐。常用的檢測(cè)節(jié)點(diǎn)存活技術(shù)是心跳協(xié)議锌俱，即定時(shí)發(fā)出心跳包來(lái)證明自己存活。但這樣的心跳協(xié)議有很多缺點(diǎn)敌呈，首先如何是確保心跳包準(zhǔn)確送達(dá)目標(biāo)節(jié)點(diǎn)贸宏，如果網(wǎng)絡(luò)問題導(dǎo)致心跳包沒有正確送達(dá)，會(huì)不會(huì)誤傷健康的節(jié)點(diǎn)磕洪？這個(gè)雖然可以通過(guò)協(xié)議來(lái)解決但同時(shí)導(dǎo)致了協(xié)議的復(fù)雜度吭练。其次心跳協(xié)議是一個(gè)端到端的協(xié)議，如何應(yīng)用與大規(guī)模的集群中析显？采用星型拓?fù)浣Y(jié)構(gòu)會(huì)帶來(lái)單點(diǎn)問題鲫咽；采用多對(duì)多拓?fù)潆S著節(jié)點(diǎn)數(shù)目過(guò)多帶來(lái)通訊成本急劇上升；采用環(huán)狀拓?fù)鋾?huì)因?yàn)橥瑫r(shí)兩處節(jié)點(diǎn)故障導(dǎo)致不可用谷异。消息傳遞同樣面臨這存活檢測(cè)遇到上述問題分尸，如何保證數(shù)據(jù)準(zhǔn)確傳達(dá)和選擇通訊拓?fù)浣Y(jié)構(gòu)？對(duì)此流言協(xié)議可以很好的解決這些問題歹嘹。
"SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol"箩绍。這篇論文詳細(xì)描述了流言協(xié)議實(shí)現(xiàn)方式：
- 采用兩次檢查的存活協(xié)議，節(jié)點(diǎn)定時(shí)ping已知任一節(jié)點(diǎn)尺上，如果沒有收到ack材蛛，則轉(zhuǎn)發(fā)請(qǐng)求給k個(gè)節(jié)點(diǎn)，讓這些節(jié)點(diǎn)發(fā)送ping給被檢測(cè)節(jié)點(diǎn)怎抛，若這些節(jié)點(diǎn)都沒有收到ack就認(rèn)為被檢測(cè)節(jié)點(diǎn)有問題卑吭。
- 需要傳輸?shù)臄?shù)據(jù)作為ping和ack包的附帶數(shù)據(jù)一起傳輸，有效減少傳輸次數(shù)马绝。
此文章同時(shí)也論證了流言協(xié)議兩個(gè)特點(diǎn)：
- 對(duì)于每個(gè)節(jié)點(diǎn)來(lái)說(shuō)陨簇，存活檢查需要的時(shí)間和數(shù)據(jù)載荷大小與集群規(guī)模無(wú)關(guān)。（成本固定）
- 對(duì)于一個(gè)n個(gè)節(jié)點(diǎn)的集群迹淌，消息傳遞到全部節(jié)點(diǎn)的時(shí)間是K*log(n)河绽。（快速收斂）
服務(wù)發(fā)現(xiàn)的KV存儲(chǔ)系統(tǒng)
現(xiàn)在我們需要設(shè)計(jì)一個(gè)用于服務(wù)發(fā)現(xiàn)的KV存儲(chǔ)系統(tǒng)，考慮到實(shí)踐運(yùn)用場(chǎng)合唉窃，該系統(tǒng)應(yīng)該具備：
- 分布式：存儲(chǔ)系統(tǒng)由多個(gè)節(jié)點(diǎn)構(gòu)成耙饰。
- 高可用：每個(gè)存活的節(jié)點(diǎn)都能提供服務(wù)。
- 最終一致性：任一節(jié)點(diǎn)上的數(shù)據(jù)變化最終體現(xiàn)在各個(gè)節(jié)點(diǎn)上纹份。由于服務(wù)啟停是個(gè)頻率較低的過(guò)程苟跪，服務(wù)發(fā)現(xiàn)系統(tǒng)可以忍受幾秒的數(shù)據(jù)的不一致廷痘，但要求最終提供的服務(wù)數(shù)據(jù)是一致的。
- 狀態(tài)檢測(cè)：新增或是移除節(jié)點(diǎn)件已，亦或是節(jié)點(diǎn)故障笋额，其他節(jié)點(diǎn)必須知悉，并對(duì)應(yīng)新增或刪減數(shù)據(jù)篷扩。
我們不難發(fā)現(xiàn)分布式兄猩、高可用和狀態(tài)檢測(cè)這些特性流言協(xié)議已經(jīng)實(shí)現(xiàn)了。無(wú)論集群的節(jié)點(diǎn)數(shù)目有多少鉴未，每個(gè)節(jié)點(diǎn)只要付出固定的成本就可以實(shí)現(xiàn)快速的存活檢測(cè)和數(shù)據(jù)傳輸枢冤。這樣我們可以構(gòu)建這樣的模型：
- 集群中的每個(gè)節(jié)點(diǎn)各自維護(hù)一個(gè)KV存儲(chǔ)齐佳。
- 對(duì)節(jié)點(diǎn)KV數(shù)據(jù)的修改都會(huì)通過(guò)流言協(xié)議擴(kuò)散到集群其他節(jié)點(diǎn)宏怔。
- 節(jié)點(diǎn)收到其他節(jié)點(diǎn)數(shù)據(jù)增減消息后會(huì)對(duì)自身的KV存儲(chǔ)進(jìn)行增減操作并擴(kuò)散疹启。
- 新增節(jié)點(diǎn)在加入集群后立刻將本節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)通過(guò)流言協(xié)議同步給集群其他節(jié)點(diǎn)贝奇。
但是這樣模型還是有些問題。假設(shè)兩個(gè)不同節(jié)點(diǎn)同時(shí)對(duì)一個(gè)Key值的數(shù)據(jù)進(jìn)行修改放祟，那對(duì)于集群的其他節(jié)點(diǎn)來(lái)說(shuō)叔收，究竟應(yīng)該采用哪個(gè)節(jié)點(diǎn)的數(shù)據(jù)尝江？這種情況會(huì)導(dǎo)致喪失最終一致性啸驯。我們發(fā)現(xiàn)僅僅依靠流言協(xié)議是無(wú)法實(shí)現(xiàn)服務(wù)發(fā)現(xiàn)的客扎，還要做一些其他的工作。
針對(duì)服務(wù)發(fā)現(xiàn)這個(gè)特殊場(chǎng)合坯汤，我們不難發(fā)現(xiàn)一個(gè)特點(diǎn)：每個(gè)節(jié)點(diǎn)只會(huì)主動(dòng)增減和自己相關(guān)的數(shù)據(jù)。也就是說(shuō)A節(jié)點(diǎn)上服務(wù)發(fā)生變化只會(huì)讓A節(jié)點(diǎn)增減數(shù)據(jù)搀愧，其他節(jié)點(diǎn)只是被動(dòng)的接收A節(jié)點(diǎn)的數(shù)據(jù)變化惰聂。A節(jié)點(diǎn)上的數(shù)據(jù)，A節(jié)點(diǎn)具有最終的發(fā)言權(quán)咱筛！為了解決不同節(jié)點(diǎn)同時(shí)寫帶來(lái)的數(shù)據(jù)不一致問題搓幌，我們加上兩條規(guī)定：
- 每個(gè)節(jié)點(diǎn)只能修改屬于自己的數(shù)據(jù)，然后再將數(shù)據(jù)同步給集群其他節(jié)點(diǎn)迅箩。
-
當(dāng)某個(gè)節(jié)點(diǎn)故障或脫離集群時(shí)溉愁，其他的節(jié)點(diǎn)刪除與此節(jié)點(diǎn)相關(guān)數(shù)據(jù)。
數(shù)據(jù)同步模型
但這并不能完全解決最終一致性的問題饲趋。流言協(xié)議不能保證傳輸?shù)捻樞蛐怨战遥簿褪钦f(shuō)假設(shè)A節(jié)點(diǎn)先發(fā)送了消息a=1，再發(fā)送a=2奕塑。B節(jié)點(diǎn)可能會(huì)先收到a=2再收到a=1堂污。消息傳輸完畢后，我們發(fā)現(xiàn)A節(jié)點(diǎn)中a=2龄砰，B節(jié)點(diǎn)a=1盟猖，失去了最終一致性讨衣。其實(shí)解決這種只有唯一寫者的順序不一致問題很簡(jiǎn)單，只需要對(duì)每個(gè)消息添加一個(gè)版本號(hào)就可以式镐。只有收到的消息比當(dāng)前數(shù)據(jù)版本號(hào)新才修改數(shù)據(jù)反镇。在這新增兩條規(guī)則：
- 每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)版本號(hào)，當(dāng)修改數(shù)據(jù)時(shí)增加此版本號(hào)娘汞。其他節(jié)點(diǎn)收到同步消息時(shí)對(duì)比消息的版本號(hào)和自身數(shù)據(jù)的版本號(hào)歹茶，只有發(fā)現(xiàn)消息版本號(hào)大于數(shù)據(jù)版本號(hào)才對(duì)數(shù)據(jù)進(jìn)行修改。
- 刪除數(shù)據(jù)時(shí)并不直接刪除數(shù)據(jù)价说，而是記錄下此時(shí)的版本號(hào)辆亏，標(biāo)記此數(shù)據(jù)刪除，防止過(guò)時(shí)消息污染數(shù)據(jù)鳖目。經(jīng)過(guò)一段時(shí)間才回收被刪除數(shù)據(jù)扮叨。
到這里看起來(lái)已經(jīng)解決了最終一致性的問題，但是在實(shí)踐運(yùn)用場(chǎng)合我們發(fā)現(xiàn)這樣的問題领迈。如圖在T3時(shí)刻彻磁，A節(jié)點(diǎn)發(fā)生崩潰重啟再加入集群，由于重啟時(shí)間較短狸捅，集群其他節(jié)點(diǎn)不認(rèn)為此節(jié)點(diǎn)失活因此保留A節(jié)點(diǎn)相關(guān)數(shù)據(jù)衷蜓。但新啟動(dòng)的A節(jié)點(diǎn)并不知道崩潰前的最新版本號(hào)，還是從版本號(hào)1開始同步數(shù)據(jù)尘喝。這個(gè)同步消息自然遭到目前版本是3的B節(jié)點(diǎn)的拒絕磁浇，至此最終一致性喪失。
解決這個(gè)問題有兩個(gè)思路朽褪，一個(gè)是實(shí)時(shí)將節(jié)點(diǎn)最新的版本號(hào)記錄在本地文件或是外部存儲(chǔ)器中置吓，這樣即使崩潰重啟也能恢復(fù)最新版本號(hào)。另一種方法比較簡(jiǎn)單缔赠，按照之前的原則”節(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ù)版本號(hào)竟然比自己當(dāng)前版本號(hào)還大時(shí)，就立即明白本節(jié)點(diǎn)的版本號(hào)已經(jīng)過(guò)時(shí)了嗤堰。這樣將本節(jié)點(diǎn)版本號(hào)置為數(shù)據(jù)版本號(hào)+1戴质，再同步數(shù)據(jù)，就解決了這個(gè)問題踢匣。如圖雖然T4時(shí)刻同步失敗了告匠，當(dāng)T5時(shí)刻收到B節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)后，A節(jié)點(diǎn)更新了自己的版本號(hào)离唬，只后同步數(shù)據(jù)就OK了凫海。在此新增一條規(guī)則：
-
節(jié)點(diǎn)收到屬于自己的數(shù)據(jù)消息且發(fā)現(xiàn)版本號(hào)比自己版本號(hào)大時(shí)，更新自己的版本號(hào)男娄。
更新過(guò)時(shí)版本號(hào)
通過(guò)以上的幾條規(guī)則行贪，我們成功的在流言協(xié)議的基礎(chǔ)上實(shí)現(xiàn)了最終數(shù)據(jù)一致性漾稀，從而完成了基于服務(wù)發(fā)現(xiàn)KV存儲(chǔ)的設(shè)計(jì)。在實(shí)際使用過(guò)程中建瘫，服務(wù)端嵌入KV存儲(chǔ)來(lái)實(shí)時(shí)更新集群可用服務(wù)崭捍，客戶端既可以通過(guò)嵌入KV存儲(chǔ)也可以通過(guò)查詢嵌入KV存儲(chǔ)的DNS服務(wù)器來(lái)查詢服務(wù)。
代碼實(shí)現(xiàn)
實(shí)現(xiàn)流言協(xié)議并不是一件輕松的事情啰脚，幸好hashicorp的memberlist組件已經(jīng)幫我們實(shí)現(xiàn)了流言協(xié)議主要功能殷蛇。memberlist的流言傳播用的是udp協(xié)議。這帶來(lái)一個(gè)問題橄浓，眾所周知udp是一個(gè)一個(gè)包傳輸?shù)牧Ｃ危瑪?shù)據(jù)信息作為ping或ack的附加載荷受限與udp包的大小，這限制了包的信息的傳播速度荸实。幸好服務(wù)發(fā)現(xiàn)數(shù)據(jù)量不是很大匀们，udp包也完全滿足。但只有一種情況除外准给，那就是新節(jié)點(diǎn)加入集群時(shí)需要同步自己全部的數(shù)據(jù)泄朴，此時(shí)數(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
