介紹
查詢是后臺(tái)領(lǐng)域經(jīng)常使用的一種數(shù)據(jù)同步方式。但是在一些場景，需求方需要針對一些數(shù)據(jù)變化做出響應(yīng)。雖然定期輪詢也可以滿足部分的需求，但在以下場景中就不太合適了。
- 存活檢測：為了檢測低于%1異常。輪詢會(huì)一直耗費(fèi)查詢資源。
- 實(shí)時(shí)響應(yīng)：變化響應(yīng)時(shí)間要盡可能小，但是輪詢周期越小，消耗的資源也越多。
因此數(shù)據(jù)層往往在“增刪改查”這4種基本接口之外還會(huì)提供一個(gè)watch接口用來實(shí)時(shí)推送數(shù)據(jù)變化事件。
Watch機(jī)制設(shè)計(jì)
watch機(jī)制是一個(gè)典型的CS架構(gòu)，其中數(shù)據(jù)需求方作為client，數(shù)據(jù)提供方作為server。由client向server發(fā)起請求，server端推送數(shù)據(jù)給client。
版本號(hào)
帶有watch機(jī)制的存儲(chǔ)系統(tǒng)往往都是具有版本功能的。具備版本功能的系統(tǒng)可以實(shí)現(xiàn)以下兩個(gè)功能：
- 因?yàn)槟承┰颍ū罎?、重啟）client可能錯(cuò)失部分歷史事件?；謴?fù)之后client可以利用版本號(hào)重新接收這些事件。
- client可以在請求參數(shù)中附帶版本號(hào)表示該版本號(hào)之前的歷史數(shù)據(jù)已經(jīng)接收。server可以過濾掉過時(shí)事件只發(fā)送新的事件給client。具體如下圖所示。
連接層
連接層討論的是client和server之間通信的協(xié)議。相較于單機(jī)程序之間的IPC通信，分布式系統(tǒng)網(wǎng)絡(luò)通信的IO成本是非常大的。下面就連接層實(shí)現(xiàn)方式、性能和開發(fā)成本展開具體分析。
http長輪詢
http長輪詢是一種非常容易實(shí)現(xiàn)的watch手段，因此也是使用最廣泛的。比如etcd v2、consul等都使用了http長輪詢技術(shù)來watch事件。具體實(shí)現(xiàn)原理如下圖。
http長輪詢的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單、兼容性好，不需要額外開發(fā)客戶端程序。但是這樣的實(shí)現(xiàn)意味每接收一個(gè)event都需要至少走完一個(gè)http請求應(yīng)答流程。這對于watch key非常多的系統(tǒng)，負(fù)荷是相當(dāng)大的。假設(shè)某個(gè)后臺(tái)系統(tǒng)需要watch 10W個(gè)key，每個(gè)http輪詢超時(shí)時(shí)間為100s。計(jì)算下來即使在空閑的時(shí)候系統(tǒng)需要承受并發(fā)10W個(gè)連接和1K/QSP的請求量。
長連接
長連接模式是對http長輪詢的一種優(yōu)化。不同于http長輪詢每個(gè)連接都只能處理一個(gè)事件，長連接模式一個(gè)連接可以接收多個(gè)事件，通過減少了tcp三次握手的開銷，提高了資源利用率。
但相對而言長連接模式開發(fā)成本要比http長輪詢高，主要體現(xiàn)在：
- 需要定義事件流的序列化和反序列化協(xié)議。目前沒有公認(rèn)的標(biāo)準(zhǔn)，只能私有定制應(yīng)用于內(nèi)部系統(tǒng)。
- 沒有成熟的反向代理組件。需要考慮在大規(guī)模部署下的負(fù)載均衡問題。
長連接模式雖然減少了tcp握手的開銷，但每個(gè)watch key都需要一個(gè)連接。假設(shè)某個(gè)后臺(tái)系統(tǒng)需要watch 10w個(gè)key，就需要建立10W個(gè)連接，這很容易消耗光server的socket和內(nèi)存資源。
多路復(fù)用
多路復(fù)用是通信工程上的概念，指的是將多個(gè)低速信道整合到一個(gè)高速信道進(jìn)行傳輸，從而有效地利用了高速信道。通過使用多路復(fù)用，可以避免維護(hù)多條線路，從而有效地節(jié)約運(yùn)營成本。
網(wǎng)絡(luò)工程上有很多方面借鑒了多路復(fù)用的思想。比如L4層的TCP、UDP就是復(fù)用了L3層的IP層的通道。同理我們也可以在tcp上層定義更高層協(xié)議來復(fù)用tcp連接。如下圖，雖然端到端之間只有一個(gè)tcp連接。但在邏輯層上可以抽象出多個(gè)雙工的session stream。每個(gè)session stream負(fù)責(zé)一個(gè)watch任務(wù)。假設(shè)一個(gè)客戶端需要watch 1k個(gè)key，原先按照需要1k個(gè)連接，但現(xiàn)在只需要一個(gè)連接即可。
多路復(fù)用核心就是在tcp連接上構(gòu)建一個(gè)邏輯層。該邏輯層負(fù)責(zé)處理一下內(nèi)容：
- 建立、關(guān)閉stream需要的控制幀。
- 接收時(shí)將tcp連接里的數(shù)據(jù)流，拆分為一個(gè)個(gè)frame，再按照協(xié)議封裝到對于的stream中。
- 發(fā)送時(shí)將stream里的數(shù)據(jù)流分割成frame，再通過tcp層發(fā)送出去。
- 為了防止stream之間相互干擾搶占帶寬資源，需要設(shè)計(jì)流控機(jī)制公平調(diào)度。
- 空閑stream?；钔ㄐ牛S持session會(huì)話心跳。
- 封裝好類似socket的Read和Write的接口，方便業(yè)務(wù)調(diào)用。
可以看出，多路復(fù)用技術(shù)是開發(fā)是比較復(fù)雜的。但值得慶幸的是，業(yè)內(nèi)已經(jīng)有了成熟可靠的工具和標(biāo)準(zhǔn)。HTTP/2定義了多路復(fù)用的協(xié)議，grpc實(shí)現(xiàn)多語言版本的接口。我們完全可以秉著拿來主義的思想直接來用，比如etcd v3版本就是使用grpc stream模式來處理watch的。
The etcd3 API multiplexes watches on a single connection. Instead of opening a new connection, a client registers
a watcher on a bidirectional gRPC stream. The stream delivers events tagged with a watcher’s registered ID. Multiple
watch streams can even share the same TCP connection. Multiplexing and stream connection sharing reduce etcd3’s
memory footprint by at least an order of magnitude.
consul的watch也采用了多路復(fù)用技術(shù)。它自己實(shí)現(xiàn)了一個(gè)多路復(fù)用庫yamux，雖然沒有http/2和grpc那么完備，但是還是可以供愿意自己練手的同學(xué)參考學(xué)習(xí)。
watch gateway
對于一般的場合，多路復(fù)用已經(jīng)有很好的性能表現(xiàn)了。但是etd v3.2版本提出一個(gè)進(jìn)一步提高watch性能的優(yōu)化方案watch gateway。
考慮到k8s使用場合可能存在有上萬個(gè)watcher。一旦事件觸發(fā)etcd需要廣播給所有的watcher，就會(huì)帶來相當(dāng)大的性能消耗，甚至?xí)绊懙淖x寫性能。但在實(shí)際場景，這些watcher很有可能監(jiān)聽的資源是重復(fù)的，比如每個(gè)api-server監(jiān)聽的資源都是一樣的。為了優(yōu)化這種大量重復(fù)監(jiān)聽watcher的場景，etcd v3.2版本設(shè)計(jì)了gateway組件。gateway可以聚合watch相同范圍key的watcher。舉例說明如下圖，client1、client2、client3都對事件a感興趣，如果直接請求server，server需要負(fù)擔(dān)3個(gè)watcher。但如果通過gateway聚合，可以合并3個(gè)watch變成1個(gè)，這樣可以降低server的壓力
本質(zhì)上來說，gateway只是將廣播的壓力從server轉(zhuǎn)移到自己身上去了。但是server作為存儲(chǔ)服務(wù)器，一般都是有狀態(tài)的。無論是擴(kuò)容還是遷移都是有一定成本的。但是gateway是一個(gè)無狀態(tài)的服務(wù)，完全可以根據(jù)實(shí)際需求橫向部署gateway服務(wù)器來降低存儲(chǔ)層的壓力。
下圖是etcd v3.2使用watch-gateway性能提升的對比圖。在不使用gateway時(shí)，隨著watcher的增多，寫和watch速率下降。但是使用了gateway之后，watch數(shù)量增加對性能沒有影響。詳細(xì)文檔見(https://coreos.com/blog/etcd-3.2-announcement)
存儲(chǔ)
watch機(jī)制實(shí)現(xiàn)的另一個(gè)核心問題就是如何存儲(chǔ)數(shù)據(jù)。按照存儲(chǔ)類型來分，可以分為內(nèi)存和硬盤里兩大類。下面會(huì)根據(jù)具體場景來討論這兩種類型的數(shù)據(jù)格式的設(shè)計(jì)。
歷史數(shù)據(jù)存儲(chǔ)
watch機(jī)制的特點(diǎn)決定了存儲(chǔ)系統(tǒng)需要保存歷史數(shù)據(jù)。舉例說明，如下圖一個(gè)數(shù)據(jù)同步場景。client向server watch同步數(shù)據(jù)，歷史同步數(shù)據(jù)已經(jīng)達(dá)到1G。某個(gè)時(shí)間點(diǎn)網(wǎng)絡(luò)異常導(dǎo)致client和server之間通信中斷，watch被迫停止。在網(wǎng)絡(luò)中斷時(shí)間內(nèi)，server的數(shù)據(jù)發(fā)生了變更。當(dāng)網(wǎng)絡(luò)恢復(fù)的時(shí)候，client重新發(fā)送watch請求，希望能夠從version=10001繼續(xù)獲取事件。但此時(shí)server端的version=10010，并且沒有保存歷史數(shù)據(jù)?？蛻舳税l(fā)現(xiàn)數(shù)據(jù)丟失，只好作廢之前同步的數(shù)據(jù)，重新同步高達(dá)1G的數(shù)據(jù)，等追上之后再繼續(xù)watch。
保留歷史數(shù)據(jù)可以簡化客戶端的工作，但是這也給存儲(chǔ)方帶來了極大的壓力。
滑動(dòng)事件窗口
內(nèi)存型數(shù)據(jù)庫一個(gè)缺點(diǎn)是容量相對有限。如果在數(shù)據(jù)更改頻繁的情況下保留歷史數(shù)據(jù)的話，有可能導(dǎo)致內(nèi)存溢出。因此內(nèi)存型數(shù)據(jù)庫往往采用滑動(dòng)事件窗口來作為妥協(xié)方案。
滑動(dòng)事件窗口就是一個(gè)簡單的回環(huán)數(shù)組。不斷的插入新事件、淘汰掉超過大小的舊事件。因?yàn)榇翱诘拇笮∈枪潭ǖ?，因此不?huì)出現(xiàn)內(nèi)存溢出。
如果watch的版本命中了滑動(dòng)事件窗口里的事件版本，就可以返回給client。
滑動(dòng)事件窗口的缺點(diǎn)是顯而易見的。對于修改頻繁的系統(tǒng)，滑動(dòng)事件窗口可以保存的事件時(shí)間非常短，很有可能丟失事件。這個(gè)是內(nèi)存型存儲(chǔ)系統(tǒng)的硬傷，沒辦法根本解決。目前etcd v2、consul和k8s api server都是采用這樣的機(jī)制。
多版本存儲(chǔ)
相較于受限容量的內(nèi)存型數(shù)據(jù)庫，磁盤數(shù)據(jù)庫的空間就大很多了。有能力存儲(chǔ)足夠舊的歷史版本數(shù)據(jù)。比如etcd v3就是存儲(chǔ)了多個(gè)版本的數(shù)據(jù)。
簡單來說，etcd v3在內(nèi)存里維護(hù)一個(gè)B樹，存儲(chǔ)的是Key和這個(gè)Key所有的版本列表。磁盤里維護(hù)了一個(gè)B+樹，存儲(chǔ)的是版本和KV的實(shí)際內(nèi)容。磁盤B+樹是實(shí)際的數(shù)據(jù)，內(nèi)存B數(shù)一個(gè)二級索引。查找某個(gè)Key某個(gè)版本的數(shù)據(jù)可以分為以下兩步：
- 通過內(nèi)存B數(shù)查找到Key對應(yīng)的版本列表。再從版本列表中找到里查詢版本參數(shù)最近的一個(gè)版本號(hào)Version。
- 再到磁盤B+樹中查找Version對應(yīng)的數(shù)據(jù)信息。
因?yàn)樾枰獙ey存儲(chǔ)在內(nèi)存中，etcd的實(shí)際存儲(chǔ)量也是非常有限的。按照etcd文檔，默認(rèn)存儲(chǔ)是2G、最大可配置到8G。當(dāng)然這個(gè)比內(nèi)存型的consul容量還是大的多了。
事件觸發(fā)
和其他的存儲(chǔ)系統(tǒng)不一樣的是，watch存儲(chǔ)系統(tǒng)需要在某個(gè)key變更的時(shí)候通知到client。這就需要設(shè)計(jì)對應(yīng)的觸發(fā)響應(yīng)機(jī)制。watcher往往不僅僅監(jiān)聽單個(gè)的key，還可能是監(jiān)聽某個(gè)前綴或是范圍key，只要其中之一有變化，就需要觸發(fā)事件。
事件觸發(fā)最簡單的實(shí)現(xiàn)方式就是采用遍歷的方法：當(dāng)某個(gè)Key發(fā)生變化時(shí)，逐個(gè)遍歷watcher，一旦發(fā)現(xiàn)滿足條件的watcher就發(fā)送數(shù)據(jù)。這種O(n)復(fù)雜度的處理方式固然簡單，但隨著watcher數(shù)量的增多，帶來的性能損失也是越來越大的。下面介紹兩種應(yīng)用于工程的數(shù)據(jù)結(jié)構(gòu)。
radix樹
說到前綴匹配，很容易想到和前綴匹配相關(guān)的數(shù)據(jù)結(jié)構(gòu)radix樹。在計(jì)算機(jī)科學(xué)中，基數(shù)樹，或稱Patricia trie/tree，或crit bit tree，壓縮前綴樹，是一種更節(jié)省空間的Trie（前綴樹）。對于基數(shù)樹的每個(gè)節(jié)點(diǎn)，如果該節(jié)點(diǎn)是唯一的子樹的話，就和父節(jié)點(diǎn)合并。
如圖當(dāng)前綴匹配watch ro的時(shí)候，可以通過radix樹找到om節(jié)點(diǎn)。之后切割o、m節(jié)點(diǎn)并將watcher掛載在o節(jié)點(diǎn)上。如果o下面的節(jié)點(diǎn)有任何的變化，都會(huì)通過回調(diào)通知watcher觸發(fā)事件。
consul就是采用radix樹來存儲(chǔ)KV數(shù)據(jù)的。但是radix樹只能解決前綴匹配的問題，無法解決范圍Key的問題。因此consul是不支持范圍key watch的。
區(qū)間樹
radix作為一個(gè)樹的問題在于它太長了，需要大量使用間接指針。對于內(nèi)存型存儲(chǔ)結(jié)構(gòu)還算好，但對于磁盤數(shù)據(jù)結(jié)構(gòu)而言，多次間接查找是非常消耗性能的。目前B+樹還是最適合查找的磁盤數(shù)據(jù)結(jié)構(gòu)。但B+樹沒法反向查找某個(gè)Key是否在某個(gè)watcher范圍內(nèi)。為了解決這個(gè)問題，etcd v3采用了區(qū)間樹。
區(qū)間樹是在紅黑樹基礎(chǔ)上進(jìn)行擴(kuò)展得到的支持以區(qū)間為元素的動(dòng)態(tài)集合的操作，其中每個(gè)節(jié)點(diǎn)的關(guān)鍵值是區(qū)間的左端點(diǎn)。通過建立這種特定的結(jié)構(gòu)，可是使區(qū)間的元素的查找和插入都可以在O(lgn)的時(shí)間內(nèi)完成。
關(guān)于區(qū)間樹原理本文不再贅述，感興趣的同學(xué)可以查閱算法導(dǎo)論。簡而言之，每個(gè)watcher將自己的監(jiān)聽范圍[start,end]封裝成一個(gè)節(jié)點(diǎn)插入?yún)^(qū)間樹。當(dāng)某個(gè)Key發(fā)生變化需要查找對應(yīng)watcher的時(shí)候，就可以利用區(qū)間樹快速查找到重疊的watcher。
應(yīng)用場景
之前說的是watch的實(shí)現(xiàn)機(jī)制。下面談?wù)剋atch的應(yīng)用場景。利用（list watch機(jī)制）的方式解決以下場景的讀性能瓶頸問題：
- 讀多寫少
- 可以接受最終一致性
- 數(shù)據(jù)量不大，可以存儲(chǔ)在內(nèi)存中
服務(wù)發(fā)現(xiàn)
服務(wù)發(fā)現(xiàn)場景恰好滿足了上述的3個(gè)條件，因此非常適合采用watch同步機(jī)制來減緩服務(wù)發(fā)現(xiàn)服務(wù)器的讀壓力。每個(gè)客戶端可以利用list watch緩存一份同步數(shù)據(jù)到本地，程序直接查詢本地緩存，性能非常優(yōu)異。
k8s api-server
k8s api 每個(gè)server利用list watch機(jī)制保留一份和etcd數(shù)據(jù)同步的緩存。當(dāng)接收到查詢請求時(shí)，直接讀取緩存數(shù)據(jù)返回給客戶端。對于新增、修改和刪除請求直接透傳給etcd。
需要注意的是，在服務(wù)發(fā)現(xiàn)場景里客戶端不會(huì)修改緩存數(shù)據(jù)，但api-server是可以修改數(shù)據(jù)的。一旦涉及數(shù)據(jù)修改，就會(huì)有數(shù)據(jù)一致性的問題。假設(shè)原先數(shù)據(jù)a=1,之后客戶端寫入a=2。寫入成功后讓客戶端讀取另外一個(gè)server的數(shù)據(jù)，有可能讀取到a=1（watch有時(shí)間差）。這就產(chǎn)生了讀寫不一致的問題。
當(dāng)然實(shí)際情況k8s是不會(huì)出現(xiàn)上述讀寫不一致的現(xiàn)象的。解決方法是ResourceVersion管理。k8s里每個(gè)Object都有對應(yīng)的ResourceVersion，其實(shí)這個(gè)就是etcd的revision，也就是watch的版本號(hào)。這個(gè)版本號(hào)是自增的，對于每個(gè)請求k8s都要求客戶端在請求里帶上特點(diǎn)的版本號(hào)。api-server在收到客戶端請求后會(huì)對比自身緩存里的版本信息，如果小于客戶端的版本信息則需要阻塞等待新數(shù)據(jù)同步。只有緩存數(shù)據(jù)版本大于等于客戶端請求的版本信息才可以返回?cái)?shù)據(jù)給客戶端。
總結(jié)
本文主要討論了watch機(jī)制的具體實(shí)現(xiàn)和一些應(yīng)用場景。雖然要實(shí)現(xiàn)一個(gè)簡易的watch機(jī)制很容易，但隨著業(yè)務(wù)發(fā)展，數(shù)據(jù)量和請求量逐步上升，就不得不就各個(gè)環(huán)節(jié)進(jìn)行優(yōu)化。雖然etcd和consul都是基于raft的KV數(shù)據(jù)庫，但兩者發(fā)展的方向已經(jīng)越來越不相同。etcd是伴隨著k8s不斷成長，在性能優(yōu)化上一步步改進(jìn)。consul則是向著服務(wù)發(fā)現(xiàn)場景不斷進(jìn)步。當(dāng)從watch機(jī)制實(shí)現(xiàn)上來看，consul做的確不如etcd做的好，但在實(shí)際應(yīng)用上，很難找到一個(gè)像k8s一樣對性能要求如此嚴(yán)苛的場景?？梢哉fk8s采用了etcd，也是etcd的幸運(yùn)。
