本文為演講內(nèi)容的整理。文章主要分為四個部分：第一部分介紹了美團 KV 存儲發(fā)展歷程；第二部分分享了內(nèi)存 KV Squirrel 挑戰(zhàn)和架構(gòu)實踐；第三部分闡述了持久化 KV Cellar 挑戰(zhàn)和架構(gòu)實踐；最后一部分介紹了未來的發(fā)展規(guī)劃。希望這些內(nèi)容能對大家有所幫助或啟發(fā)。

KV 存儲作為美團一項重要的在線存儲服務，承載了在線服務每天萬億級的請求量，并且保持著 99.995% 的服務可用性。在 DataFunSummit 2023 數(shù)據(jù)基礎架構(gòu)峰會上，我們分享了《美團大規(guī)模 KV 存儲挑戰(zhàn)與架構(gòu)實踐》。

1 美團 KV 存儲發(fā)展歷程

2 大規(guī)模 KV 存儲的挑戰(zhàn)

3 內(nèi)存 KV Squirrel 挑戰(zhàn)和架構(gòu)實踐

3.1 Squirrel水平擴展的挑戰(zhàn)

3.2 Gossip優(yōu)化

3.3 Squirrel 垂直擴展的挑戰(zhàn)

3.4 forkless RDB

3.5 工作多線程

3.6 Squirrel可用性的挑戰(zhàn)

3.7 兩機房容災

3.8 跨地域容災

3.9 雙向同步?jīng)_突自動解決

4 持久化 KV Cellar 挑戰(zhàn)和架構(gòu)實踐

4.1 Cellar垂直擴展的挑戰(zhàn)

4.2 Bulkload 數(shù)據(jù)導入

4.3 線程調(diào)度模型優(yōu)化

4.4 線程RTC模型改造

4.5 內(nèi)存引擎無鎖化

4.6 Cellar可用性的挑戰(zhàn)

4.7 雙向同步?jīng)_突自動解決

5 發(fā)展規(guī)劃和業(yè)界趨勢

1 美團 KV 存儲發(fā)展歷程

上圖就是美團第一代的分布式 KV 存儲的架構(gòu)，可能很多公司都經(jīng)歷過這個階段。

在客戶端內(nèi)做一致性哈希，然后在后端部署上很多 Memcached 實例，這樣就實現(xiàn)了最基本的 KV 存儲分布式設計。但這樣的設計存在很明顯的問題：比如在宕機摘除節(jié)點會時丟失數(shù)據(jù)；此外，在緩存空間不夠需要擴容時，一致性哈希也會丟失一些數(shù)據(jù)，這樣會給業(yè)務的開發(fā)帶來很大的困擾。

隨著 Redis 項目的成熟，美團也引入了 Redis 來解決我們上面提到的問題，進而演進出來上圖這樣一個架構(gòu)?？梢钥吹剑蛻舳诉€是一樣，使用一致性哈希算法，在服務器端變成了 Redis 組成的主從結(jié)構(gòu)。當任何一個節(jié)點宕機，我們可以通過 Redis 哨兵完成 failover，實現(xiàn)高可用。但有，還一個問題還是沒有解決，如果擴縮容的話，一致性哈希仍然會丟失數(shù)據(jù)。

這時我們發(fā)現(xiàn)業(yè)界有一個比較成熟的開源 KV 存儲：也就是阿里巴巴的 Tair 。2014年，我們把 Tair 引入到技術(shù)內(nèi)部，去滿足業(yè)務 KV 存儲方面的需求。

Tair 開源版本的架構(gòu)主要是三部分：最下邊的是存儲節(jié)點，存儲節(jié)點會上報心跳到它的中心節(jié)點，中心節(jié)點內(nèi)部設有兩個配置管理節(jié)點，會監(jiān)控所有的存儲節(jié)點。如果有任何存儲節(jié)點宕機或者擴容之類的行為，它會做集群拓撲的重新構(gòu)建?？蛻舳藛拥臅r候，它會直接從中心節(jié)點引入一個路由表，這個路由表簡單來說就是一個集群的數(shù)據(jù)分布圖，客戶端根據(jù)路由表直接去存儲節(jié)點讀寫。之前我們 KV 遇到的擴容丟數(shù)據(jù)問題，它也有數(shù)據(jù)遷移機制來保證數(shù)據(jù)的完整性。

B端究竟需要什么样的产品经理？

B端产品经理都是以提升供应侧的工作效率为目的，所以B端需求主要是以业务问题为导向。 这个是B端产品比较重要的一点，B端产品是服务于一个主体 ...

查看详情 >

但是在使用的過程中，我們還遇到了一些其他問題，比如：它的中心節(jié)點雖然是主備高可用的，但它沒有分布式仲裁之類的機制，所以在網(wǎng)絡分割的情況下，它是有可能發(fā)生“腦裂”的，這種情況也給我們的業(yè)務造成過比較大的影響。在容災擴容的時候，遇到過數(shù)據(jù)遷移影響業(yè)務可用性的問題。

另外，我們之前用過 Redis ，業(yè)務會發(fā)現(xiàn) Redis 的數(shù)據(jù)結(jié)構(gòu)特別豐富，而 Tair 還不支持這些數(shù)據(jù)結(jié)構(gòu)。雖然我們用 Tair 解決了一些問題，但是 Tair 同樣也無法完全滿足我們的業(yè)務需求。于是，我們認識到在美團這樣一個業(yè)務規(guī)模大、復雜度高的場景下，很難有開源系統(tǒng)能很好滿足我們的需求。所以，我們決定在已應用的開源系統(tǒng)之上進行自研。

時值 2015 年， Redis 社區(qū)正式發(fā)布了它的集群版本 Redis Cluster。所以，我們緊跟社區(qū)步伐，并結(jié)合內(nèi)部需求做了很多自研功能，進而演進出本文要介紹的全內(nèi)存、高吞吐、低延遲的 KV 存儲 Squirrel。另外，我們基于 Tair，加入了很多美團自研的功能，演進出本文要介紹的持久化、大容量、數(shù)據(jù)高可靠的 KV 存儲 Cellar 。

Redis 社區(qū)一直都很活躍，所以，Squirrel 的迭代是自研和社區(qū)并重，自研功能設計上也會盡量與社區(qū)架構(gòu)兼容。Tair 開源版本已經(jīng)多年沒有更新，所以，Cellar 的迭代完全靠自研。后續(xù)內(nèi)容上大家也能看到，因為這方面的不同，Cellar 和 Squirrel 在解決同樣問題時可能會選取不同的方案。

這兩個存儲其實都是 KV 存儲領域的解決方案。實際應用上，如果業(yè)務的數(shù)據(jù)量小，對延遲敏感，建議用 Squirrel ；如果數(shù)據(jù)量大，對延遲不是特別敏感，我們建議用成本更低的 Cellar 。

2 大規(guī)模 KV 存儲的挑戰(zhàn)

大規(guī)模KV 存儲的業(yè)務挑戰(zhàn)主要有兩點：

一個是擴展性。隨著業(yè)務規(guī)模持續(xù)變大，業(yè)務會要求使用容量更大的集群。這個容量包括兩方面，一方面是數(shù)據(jù)量，還有一方面是調(diào)用量。擴展容量，最常見的方法就是把集群水平擴展到更多的節(jié)點，但是當集群節(jié)點數(shù)達到一定規(guī)模后，再想擴展新節(jié)點也會遇到很多困難，這是擴展性上的第一個挑戰(zhàn)。

還有一個問題是有些業(yè)務場景的調(diào)用容量是無法隨著集群水平擴展而擴展的。比如，很多業(yè)務會使用 mget 進行批量讀取。但隨著集群節(jié)點數(shù)的增加，由于“木桶效應”，整個 mget 請求的長尾延遲會越來越高，進而導致服務的請求超時率持續(xù)上升。等集群達到一定規(guī)模之后，長尾延遲造成的可用性降低就超出業(yè)務的承受能力了。所以在水平擴展之外，我們還需要解決好節(jié)點垂直擴展上的挑戰(zhàn)，來支持這種批量操作的業(yè)務場景。

另一個是可用性。隨著集群規(guī)模變大，要保證可用性維持在與小規(guī)模集群同等的水平，其實是很困難的。但業(yè)務服務卻不會因為集群規(guī)模變大而能接受可用性有所降低。所以，美團的挑戰(zhàn)是如何保證集群可用性不會隨著規(guī)模的變大而有所降低。

3 內(nèi)存 KV Squirrel 挑戰(zhàn)和架構(gòu)實踐

上圖是美團的 Squirrel 架構(gòu)。中間部分跟 Redis 社區(qū)集群是一致的。它有主從的結(jié)構(gòu)，Redis 實例之間通過 Gossip 協(xié)議去通信。我們在右邊添加了一個集群調(diào)度平臺，包含調(diào)度服務、擴縮容服務和高可用服務等，它會去管理整個集群，把管理結(jié)果作為元數(shù)據(jù)更新到 ZooKeeper。

我們的客戶端會訂閱 ZooKeeper 上的元數(shù)據(jù)變更，實時獲取到集群的拓撲狀態(tài)，直接對 Redis 集群節(jié)點進行讀寫操作。

3.1 Squirrel水平擴展的挑戰(zhàn)

但是基于 Redis Cluster 架構(gòu)的水平擴展，會有如下問題：

一個是 Gossip 的消息通信量是節(jié)點數(shù)的平方，隨著集群節(jié)點數(shù)的增加，Gossip 通信的消息量會急劇膨脹。比如，我們實測對于一個 900 節(jié)點的集群，Gossip 消息的 CPU 消耗會高達12%，遠高于小集群的 Gossip 資源消耗，這樣會造成極大的資源浪費。

除了資源的浪費以外，Gossip 消息過多，也會更多搶占用戶請求處理線程的資源，進而會導致用戶請求經(jīng)常被 Gossip 消息的處理所阻塞，再導致用戶請求產(chǎn)生更多的超時，影響服務可用性。

3.2 Gossip優(yōu)化

為了解決上述的擴展性問題，我們對社區(qū)的 Gossip 方案進行了優(yōu)化。首先針對 Gossip 傳輸?shù)南?，我們通過 Merkle Tree 對其做了一個摘要，把集群 Gossip 通信的數(shù)據(jù)量減少了90%以上。

服務端節(jié)點僅需要對比 Hash 值即可判斷元數(shù)據(jù)是否有更新，對于存在更新的情況也能快速判斷出更新的部分，并僅對此部分元數(shù)據(jù)進行獲取、更新，大幅降低了 Gossip 消息處理的資源消耗。同時，我們還增加了一個周期性的元數(shù)據(jù)全量同步功能，來解決可能因 Hash 沖突導致元數(shù)據(jù)無法更新的問題。

針對上述提到的 Gossip 消息處理影響業(yè)務請求的問題，我們把 Gossip 消息處理功能剝離到一個單獨的心跳線程里，并且由心跳線程來更新集群拓撲的元數(shù)據(jù)。對于處理用戶請求的工作線程，僅需要對元數(shù)據(jù)進行讀操作，可以做到無鎖讀。這樣的話，Gossip 請求處理就對業(yè)務請求完全沒有影響了。

3.3 Squirrel 垂直擴展的挑戰(zhàn)

對基于 Redis 研發(fā)的 Squirrel 來說，垂直擴展會存在如下問題：

首先是數(shù)據(jù)容量的問題。對一個內(nèi)存存儲來說，節(jié)點容量過大的話，很容易影響服務的可用性。例如，在主從節(jié)點要做數(shù)據(jù)同步時，Redis 節(jié)點需要通過 fork 產(chǎn)生子進程來生成全量數(shù)據(jù)的 RDB 快照。當一個 8GB 的節(jié)點做 fork 調(diào)用時，會由于頁表項過多，造成進程出現(xiàn) 500 毫秒的阻塞。對于平均耗時只有幾毫秒的 KV 請求來說，這 500 毫秒的阻塞會造成大量的超時。

還有就是處理量的擴展問題。雖然我們可以通過加從庫去擴展集群的讀能力上限，但主庫的寫處理能力卻還是無力擴展的。而且，受限于主庫的處理能力和機器帶寬限制，加從庫來擴展讀能力也是有上限的。

3.4 forkless RDB

針對上述節(jié)點過大，fork 生成 RDB 會導致可用性降低的問題。我們實現(xiàn)了 forkless RDB 方案，這是一個不基于 fork，且不會中斷服務的生成數(shù)據(jù)快照 RDB 的方案。

如上圖所示，forkless RDB 的生成期間，它首先會停止哈希表的 rehash 過程，避免數(shù)據(jù)在哈希表之間的搬遷影響快照的一致性。然后，它會從頭開始對整個哈希表的 key 做迭代，每迭代一個 key 就會把它 dump 一份出來放到復制隊列里邊。在迭代 key 的同時，它會對迭代的位置記錄一個游標。

如果在迭代哈希表的過程中，里面的 KV 有變更的話，在這個游標之前的  KV 變更，也會把它放到復制隊列里邊，確保已經(jīng)復制的 KV 能夠持續(xù)獲得后續(xù)的變更。

如圖所示，RDB 游標在 key 3，它會把之前已經(jīng)迭代過的 key 1 更新、key 2 刪除操作也插入到復制隊列里邊。在游標之后的 key，因為還沒有做數(shù)據(jù)復制，所以等后續(xù)迭代到這個 key 時，把其最新值 dump 到復制隊列就好。通過這樣的方式，就實現(xiàn)了一個不需要 fork 就能獲得一個一致性數(shù)據(jù)快照 RDB 的過程。

這個方案的優(yōu)點很明顯，生成 RDB 的過程不會阻塞服務請求處理，并且因為是實時的發(fā)送一個個 KV 數(shù)據(jù)，所以就不需要等 RDB 生成好就可以向從庫復制數(shù)據(jù)了，大幅提升了數(shù)據(jù)同步的速度。但因為全量數(shù)據(jù)迭代、復制是在工作線程去做的，而不是在子進程內(nèi)。

所以，該方案會占用一部分工作線程的資源。另外，因為是以 KV 為粒度做復制的，所以，如果哈希表里面有大 KV 的話，可能會因為工作線程復制大 KV 耗時過長，造成用戶請求等待耗時的上升。

3.5 工作多線程

對于處理量的擴展，社區(qū)有一個 IO 多線程的解決方案。但這個 IO 多線程只是把網(wǎng)絡收發(fā)部分做了多線程處理，所以，其擴展能力是比較有限的。比如 4個 IO 線程下，它只能把整體的吞吐提升一倍，就到極限了。而且因為此時工作線程已經(jīng)到瓶頸了，再往上去加 IO 線程，不僅無法提升性能，反而會消耗更多的 CPU 資源。對此，我們的解決方案是工作多線程，也就是說把請求處理的過程也多線程化。

如上圖所示，在工作多線程方案下，每個線程都會去處理請求，并且每個線程會完成從收包到請求處理，然后到發(fā)包的整個過程，是一個 Run-to-Completion 線程模型。相比 IO 多線程，它會減少很多線程切換，節(jié)省很多的 CPU 資源。同時對于請求處理的過程，我們也通過細致的梳理，盡量縮小了臨界區(qū)的范圍，以保證大部分的請求處理過程是在臨界區(qū)之外的，來提升處理并發(fā)度。

如果一個工作線程需要加鎖的話，它會先 try lock。如果加鎖成功就繼續(xù)執(zhí)行了，但如果加鎖失敗的話，這個工作線程也不會阻塞等鎖。它會先去注冊一個管道的通知消息，然后就繼續(xù)處理網(wǎng)絡的收發(fā)包，還有非臨界區(qū)的請求了。等到鎖被釋放的時候，這個工作線程會通過 epoll 獲得管道里面的鎖釋放通知，然后去拿到這把鎖。這個時候它就可以去處理臨界區(qū)的請求操作了。

這樣的話，在整個加鎖、解鎖的過程中，工作線程沒有任何阻塞，仍然可以繼續(xù)做網(wǎng)絡收發(fā)、非臨界區(qū)請求的處理，獲得最大限度的處理能力。另外，對于新建 socket、數(shù)據(jù)復制等工作，跟工作線程的耦合很低，我們將其放到了單獨的線程去執(zhí)行，以盡量降低工作線程的負載。

通過實測，工作多線程方案的吞吐比社區(qū) IO 多線程提升了 70%，相對于社區(qū)單線程提升 3 倍多。

3.6 Squirrel可用性的挑戰(zhàn)

基于 Redis Cluster 的大規(guī)模集群可用性挑戰(zhàn)主要是維持機房容災部署很困難。如上圖所示，由于 Redis Cluster 是去中心化的架構(gòu)，所以部署上要求至少是三機房分布，以此來保證任何一個機房掛掉的時候，剩余的兩個機房仍然能有過半的節(jié)點來選出新的主節(jié)點。比如一個上千節(jié)點的集群要擴容的話，可能需要幾百個分布在三個機房的節(jié)點，一時之間其實很難湊齊這么多機房的資源。而當業(yè)務大促容量需求很急時，我們有時候只能犧牲機房容災能力來滿足業(yè)務的容量需求。

還有在成本方面，對于一些數(shù)據(jù)可靠性要求較低的業(yè)務，只需要兩副本冗余就夠了，極端情況下丟一點數(shù)據(jù)也是可以接受的。但受限于容災要求，這些業(yè)務也只能使用三機房三副本部署，從成本角度考量很不劃算。

3.7 兩機房容災

受 Google Spanner 的見證者節(jié)點啟發(fā)，我們在 Squirrel 集群也引入了見證者節(jié)點角色。同 Spanner 一樣，Squirrel 見證者節(jié)點也不會存儲數(shù)據(jù)，所以，它無法作為正常的主從庫提供請求處理能力，也不能發(fā)起選主投票。但見證者節(jié)點可以在集群選主時參與投票，幫助存活的機房節(jié)點完成過半選主過程。

見證者節(jié)點還可以設置權(quán)重，這樣只需要一個或幾個高權(quán)重見證者節(jié)點，就能滿足一個大規(guī)模集群的容災部署需求了。由于見證者節(jié)點不存儲數(shù)據(jù)，且節(jié)點數(shù)很少，雖然集群還是三機房部署，但實際幾乎只需要兩機房的資源就能滿足機房容災部署需求了，這樣就大幅降低了集群維持容災部署的難度，從而節(jié)省大量的機器成本。

3.8 跨地域容災

Squirrel 跨地域容災的架構(gòu)如上圖所示，它通過一個集群間同步服務在兩個不同地域的集群之間做數(shù)據(jù)同步。這個同步服務首先偽裝為上游集群節(jié)點的 slave 把它的 RDB 和增量 log 拉取過來，然后再把拉取到的數(shù)據(jù)轉(zhuǎn)化成寫請求發(fā)到下游的集群，從而實現(xiàn)了一個集群間的數(shù)據(jù)同步。

通過這樣的架構(gòu)，我們解決了服務的跨地域容災問題。并且，通過在集群間搭建正反兩個方向的兩個同步任務，就能實現(xiàn)集群間的雙向同步。

這樣的話，用戶服務就可以只在本地域?qū)?，但同時能讀到兩個地域分別寫入的數(shù)據(jù)，解決了單向同步需要跨地域?qū)懙膯栴}。

雙向同步有兩個經(jīng)典問題需要解決：

一個是循環(huán)復制問題。我們?yōu)槊總€ Squirrel 集群標記了不同的 cluster id，并且記錄了每個 KV 的初始寫入 cluster id，同步服務會過濾掉與目標集群 cluster id 相同的數(shù)據(jù)，以避免發(fā)生循環(huán)復制。

還有一個是數(shù)據(jù)沖突問題。我們一開始是通過業(yè)務層面保證在每個地域?qū)懖煌?Key 來解決的。但是在雙向同步的運行過程中，還是會有一些極端場景可能會出現(xiàn)兩個地域并發(fā)寫同一個 Key。比如像機房網(wǎng)絡故障場景，業(yè)務會把故障機房的所有寫入都切到正常機房。

但由于我們的集群間復制是異步的，可能故障機房有一些最新的 Key 變更還沒有復制到正常機房的集群。而如果在業(yè)務將寫切換到正常機房后，又寫入了相同 Key 的不同變更，就會產(chǎn)生兩個同步集群的數(shù)據(jù)沖突。在機房網(wǎng)絡恢復之后，業(yè)務還是要把一部分流量切回到之前故障的集群上，恢復到跨地域容災的架構(gòu)。但由于兩個集群可能已經(jīng)有數(shù)據(jù)沖突了，所以，在業(yè)務切回之前，就需要對數(shù)據(jù)做沖突校驗和修復。但是對大數(shù)據(jù)量集群來說，數(shù)據(jù)校驗和修復的耗時可能會長達數(shù)天。在這樣長的時間內(nèi)，只有一個單地域集群來支撐業(yè)務，無論是從容災還是容量的角度來看，都是有較大風險的。

3.9 雙向同步?jīng)_突自動解決

為了解決上述的雙向同步數(shù)據(jù)沖突問題，我們實現(xiàn)了一個基于數(shù)據(jù)寫入本地時間的 last write win 沖突自動解決功能。

如上圖所示，在 T1 時刻 Key money 的值在 A、B 兩個集群都是 100。T2 時刻，money 的值在 A 集群更新成了 120。但是在 A 集群的新值還沒復制到 B 集群的時候，B 集群在 T3 時刻把 money 的值更新成了 130。這時候 A、B 集群會互相向?qū)Ψ綇椭聘髯詫懭氲男轮?，A 集群收到 B 集群的值 130 后，會發(fā)現(xiàn) B 集群 money 的更新時間大于自己（T3 > T2），它就會更新自己的 money 值為 130；B 集群也會收到 A 集群復制過來的 money 值 120，但它會發(fā)現(xiàn)這個值的更新時間小于自己本地值的更新時間（T2 < T3），就會忽略這個復制請求。通過這樣一個基于更新時間的 last write win 策略，就可以達到最終一致性。

上述方案看起來簡單，但是在復雜、大規(guī)模的業(yè)務場景下，還有很多問題要處理，所以，我們還做了以下的工作：保存最近更新的時間戳：當發(fā)生時鐘回退時，我們會繼續(xù)使用自己保存的時間戳，避免使用本地回退的時間導致數(shù)據(jù)也跟著發(fā)生了回退。

（PS：對于時鐘回退問題，我們調(diào)研過最新的 NTP 時鐘同步不會像以前一樣造成本地時鐘的回退或跳變，現(xiàn)在它通過把時鐘 tick 調(diào)快或調(diào)慢來完成類似的調(diào)整，所以，前述關(guān)于時鐘回退的解決方案在最新的 NTP 同步機制下就不是必要的了。

不過，為了保證我們的服務在任何系統(tǒng)下都能正常運行，我們最終還是實現(xiàn)了這個功能。）記錄寫入數(shù)據(jù)的集群 id：我們會為所有寫入的 Key 保存寫入的集群 id。當兩個值的更新時間相同時，我們會比較集群 id，如果也相同，我們就知道是同一個集群先后寫入但獲取到相同本地時間的數(shù)據(jù)，會允許其寫入；如果不同，我們僅會讓集群 id 更大的值寫入，來保證數(shù)據(jù)最終一致性。由復制操作改為復制變更后的數(shù)據(jù)：像 INCR 類接口，A 集群的 money T1 時刻通過 INCRBY money 20 變成了 120，然后 B 集群 T2 時刻通過 INCRBY money 30 變成了 130。

A 集群收到 B 集群的復制時，因為時間戳比自己的本地值大，它會執(zhí)行 INCRBY money 30 變成 150；然后 B 集群收到 A 集群的復制時，因為時間戳比自己的本地值小，它會把這個復制請求給忽略掉，就造成了數(shù)據(jù)沖突。

針對這個問題，我們將所有操作的數(shù)據(jù)復制都改成了復制操作后的數(shù)據(jù)，而不是這個操作本身，來解決類似 INCRBY 這種接口的數(shù)據(jù)沖突問題。保存最近刪除的 Key：像刪除類接口，A 集群 T2 時刻寫入了 money：120，然后 B 集群在 T3 時刻刪除了 money 這個 Key。

A 集群收到 B 集群的復制時，由于其時間戳比本地值大，A 會把數(shù)據(jù)刪了；但 B 集群收到 A 集群的復制時，由于本地已經(jīng)不存在 money 這個 Key 了，它就會把 money 當做一個新 Key 進行寫入，就造成了數(shù)據(jù)最終不一致。針對這個問題，我們通過保存最近一段時間刪除掉的 Key 及刪除時間戳，以便在刪除集群收到對端復制過來的舊 Key 時進行甄別。

4 持久化 KV Cellar 挑戰(zhàn)和架構(gòu)實踐

上圖是我們最新的 Cellar 架構(gòu)圖，它跟阿里開源的 Tair 主要有兩個層面的不同。

第一個是 OB，第二個是 ZooKeeper。我們的 OB 跟 ZooKeeper 的 Observer 是類似的作用，提供 Cellar 中心節(jié)點元數(shù)據(jù)的查詢服務。它實時的與中心節(jié)點的 Master 同步最新的路由表，客戶端的路由表都是從 OB 去拿。

這樣做的好處主要有兩點：

第一，把大量的業(yè)務客戶端跟集群的大腦 Master 做了隔離，防止路由表請求影響集群的管理；

第二，因為 OB 只提供路由表查詢服務，不參與集群的管理，所以它可以水平擴展，極大地提升了路由表的查詢能力。

第二個是我們引入了 ZooKeeper 做分布式仲裁，解決了上述提到的 Master、Slave 在網(wǎng)絡分割情況下的“腦裂”問題。并且通過把集群的元數(shù)據(jù)存儲到 ZooKeeper，從而提升了元數(shù)據(jù)的可靠性。

4.1 Cellar垂直擴展的挑戰(zhàn)

在 Cellar 架構(gòu)下，不存在水平擴展的問題，但與 Squirrel 一樣，它也有垂直擴展方面的挑戰(zhàn)。而由于 Cellar 是持久存儲，它也很少遇到單機數(shù)據(jù)容量的問題，而要解決的問題主要是處理容量的垂直擴展。

而且，由于 Cellar 是持久化引擎、多線程模型，它要解決的處理容量擴展問題也是不一樣的，具體如下：

• 引擎讀寫能力的不均衡性：Cellar 是基于 LSM-Tree 引擎模型的持久化存儲，這種引擎的多 Level compaction 會導致寫放大問題，進而會造成其寫處理能力比讀低很多。所以，在一些寫相對較多的場景，機器資源雖然還有空閑，但寫處理能力卻已經(jīng)到瓶頸了。
• 線程間同步的開銷：想要提升處理容量，就需要增加線程數(shù)。而隨著線程數(shù)的增加，線程間同步的開銷在整個服務的 CPU 使用占比也會越來越高。

所以，如果解決不好線程間同步的問題，想單純地增加線程數(shù)來提升處理容量行不通。

4.2 Bulkload 數(shù)據(jù)導入

對于上述提到引擎寫壓力達到瓶頸的集群，我們調(diào)研后發(fā)現(xiàn)其在線的實時寫入一般都是比較少的，高寫入量主要是用戶從離線批量寫數(shù)據(jù)到線上 Cellar 集群帶來的。

基于此，我們開發(fā)了 Bulkload 數(shù)據(jù)導入能力來解決這個問題。

Bulkload 整體架構(gòu)如上圖所示，它在普通寫入流涉及的客戶端和存儲節(jié)點之外，還引入了 S3 對象存儲來做導入數(shù)據(jù)的中轉(zhuǎn)。下面我們看下 Bulkload 具體的寫入流程：Bulkload 首先會在客戶端進程內(nèi)生成分片內(nèi)有序的數(shù)據(jù)文件并寫到本地硬盤上。等客戶端的數(shù)據(jù)文件寫好之后，它會上傳到對象存儲，利用對象存儲做數(shù)據(jù)文件的中轉(zhuǎn)，解決了客戶端與服務端之間直傳大文件容易失敗的問題。

分片 1 的數(shù)據(jù)文件寫入到對象存儲之后，客戶端會將數(shù)據(jù)文件的存儲地址告訴分片 1 的主所在的存儲節(jié)點 DS1。然后 DS1 就會從對象存儲下載分片 1 的數(shù)據(jù)文件，并把它直接插入到 LSM-Tree 引擎里面。因為這是一個完整的文件插入，所以，它可以消除引擎在普通寫入時的內(nèi)存排序和刷盤壓力。同時，因為這個文件的數(shù)據(jù)是分片內(nèi)有序的，所以，它在參與 Level 間 Compaction 時會與其他的引擎文件交叉很少，可以大幅減少多 Level compaction 的壓力。

然后 DS1 會把分片 1 數(shù)據(jù)文件的對象存儲地址復制發(fā)送到分片 1 的從所在的存儲節(jié)點 DS2 。因為存儲節(jié)點的復制只是傳輸數(shù)據(jù)文件的地址，所以復制速度是特別快的，也節(jié)省了很多傳輸?shù)膸挕S2 收到了分片 1 的地址后同樣會從對象存儲下載數(shù)據(jù)文件，并插入到引擎里面。

通過 Bulkload 解決方案，我們整體把數(shù)據(jù)離線導入的性能提升到舊版的 5 倍。

比如我們的一個存儲廣告特征的客戶使用 KV 方式從離線導數(shù)據(jù)到在線需要 14 小時，受限于在線高峰期無法導數(shù)據(jù)，如果需要繼續(xù)增加特征數(shù)據(jù)，就需要擴容集群了。而擴容集群一方面會因為“木桶效應”導致請求長尾延遲問題，另一方面 Cellar 成本的上升也會抵消一部分廣告收益。而在 Bulkload 功能加持下，該客戶導入相同規(guī)模數(shù)據(jù)僅需不到 3 小時，它可以在不增加 Cellar 資源的情況下，將廣告特征規(guī)模增加數(shù)倍，大幅提升了廣告的效果。

4.3 線程調(diào)度模型優(yōu)化

我們最初的線程模型與開源版 Tair 一樣，網(wǎng)絡線程池做收發(fā)包，收到的包經(jīng)過一個隊列轉(zhuǎn)出到一個大的工作線程池做請求處理。

這樣的線程模型，很容易發(fā)生請求間的互相影響。比如用戶有離線數(shù)據(jù)導入到 Cellar 的時候，就很容易導致在線讀請求的超時。

又比如當有大 Value 讀寫的時候，工作線程處理會比較慢、占用線程的時間會很長，導致正常 Value 讀寫的快請求只能在隊列等待，進而導致大量超時。

所以，為了隔離在離線請求、快慢請求的處理，讓服務資源優(yōu)先保證核心流量的處理，我們后來把線程模型改造成如上圖所示的 4 個隊列 + 4 個線程池的結(jié)構(gòu)，將請求分成 4 類（讀快、讀慢、寫快、寫慢）分別放到不同的隊列和線程池去處理，進而來提升服務核心流量的可用性。

但是，工作線程池按照請求類型分離之后帶來一個問題，就是不同業(yè)務場景、甚至同一業(yè)務的不同時段，不同類型請求量的占比是不一樣的。所以，給每個線程池分配多少線程是一個很棘手的問題。針對這個問題，我們增加了一個線程動態(tài)調(diào)度的邏輯：每個線程池都有一部分線程被設定為可共享線程，如果線程池比較空閑，共享線程就會去輪詢其他的隊列，處理一些繁忙線程池的請求，這樣就達到了自適應調(diào)整各線程池資源的效果。但是在這樣的架構(gòu)下，雖然解決好了請求隔離性和不同請求類型線程資源的動態(tài)分配問題，但我們發(fā)現(xiàn)隨著節(jié)點流量的上漲，共享線程對于其他隊列的輪詢會消耗越來越多的 CPU 資源，而且集群業(yè)務的負載分布與默認的線程數(shù)設置差異越大，這個消耗的占比也會越高。

為了解決上述線程池資源自適應調(diào)度帶來的 CPU 消耗問題，我們對分離后的線程、隊列模型做出了如上圖的改造。改進后的線程模型最主要的特點是引入了一個調(diào)度線程和一個空閑線程池，這個調(diào)度線程會實時統(tǒng)計每個線程池的負載，來評估每個線程池是否需要增加或減少線程并做出調(diào)度動作，空閑線程池用來存放當前空閑的可用于調(diào)配的線程資源。

當調(diào)度線程評估后決定做線程資源調(diào)配時，它就會發(fā)送調(diào)度指令到相應隊列中，當線程池里的線程獲取并執(zhí)行了這個指令后，就實現(xiàn)了線程資源的調(diào)配。比如，它想給讀快線程池增加線程，就會給空閑線程池的隊列發(fā)送一個調(diào)度指令，空閑線程池的線程取到這個指令后，就會將自己加入到讀快隊列的線程池里面，去處理讀快隊列的請求。

當調(diào)度線程想對讀慢線程池調(diào)減線程時，它會向讀慢隊列發(fā)送一個調(diào)度指令，讀慢隊列的線程獲取到這個指令后，就會離開讀慢線程池加入到空閑線程池。通過調(diào)度線程準實時的毫秒級負載統(tǒng)計、調(diào)度，我們實現(xiàn)了線程池資源的快速動態(tài)分配。對于每一個線程池的共享線程，也不再需要去輪詢其他線程池的隊列了，只需要專心處理自己隊列的請求即可，大幅降低了線程池資源調(diào)度的 CPU 消耗。通過上述的線程隊列模型優(yōu)化，服務在高負載場景下可以提高 30% 以上的吞吐量。

4.4 線程RTC模型改造

上圖左側(cè)畫的是我們服務請求的 IO 處理路徑：一個請求的處理流程會經(jīng)過網(wǎng)絡線程、請求隊列、工作線程、內(nèi)存和硬盤引擎。這個設計的問題是，請求在不同線程之間流轉(zhuǎn)會造成大量的 CPU 切換以及 CPU 高速緩存的 Cache Miss，進而造成大量的 CPU 資源消耗。在大流量場景下，這樣的 CPU 消耗也是很可觀的一筆資源。

針對這個問題，我們對線程隊列模型又做了如上圖右側(cè)所示的改造。

新的模型下，我們讓網(wǎng)絡線程直接去做讀請求的處理，對于能夠命中內(nèi)存引擎的讀請求，其處理模型就是一個 RTC（Run-to-Completion）模型。

具體來講，當網(wǎng)絡線程收到一個請求之后，會先判斷是否為一個讀請求，如果是，就會直接去讀內(nèi)存引擎。我們服務的內(nèi)存引擎會緩存硬盤引擎上的熱點數(shù)據(jù)，如果內(nèi)存引擎命中的話，網(wǎng)絡線程就可以直接返回結(jié)果給客戶端。

這樣在網(wǎng)絡線程內(nèi)就實現(xiàn)了請求的閉環(huán)處理，相比原來的模型可以去除所有因請求流轉(zhuǎn)造成的 CPU 資源消耗。而對于寫和讀未命中內(nèi)存引擎的請求，仍然需要經(jīng)過原來的請求處理路徑，去硬盤引擎讀或者寫數(shù)據(jù)。

新的線程模型，經(jīng)實測在 80% 內(nèi)存引擎命中率場景下，服務讀吞吐可以提升 30%+。

雖然新的線程隊列模型只實現(xiàn)了讀緩存命中請求的 RTC，但其實在線流量大多都是讀多寫少且熱點數(shù)據(jù)明顯、內(nèi)存引擎命中率比較高的場景，所以，新模型上線后在大多數(shù)的業(yè)務集群都取得了明顯的性能提升。

4.5 內(nèi)存引擎無鎖化

當單機請求量達到了一定規(guī)模之后，我們發(fā)現(xiàn)服務內(nèi)的鎖操作會占用很多的 CPU 資源。經(jīng)分析發(fā)現(xiàn)，大多數(shù)的鎖操作都發(fā)生在上節(jié)內(nèi)容提到的內(nèi)存緩存引擎上。

如上節(jié)所述，所有請求都會經(jīng)過內(nèi)存引擎，且大部分請求都會在內(nèi)存引擎命中并返回結(jié)果給客戶端。

所以，大部分請求都是純內(nèi)存處理，這個過程中的鎖操作就很容易成為瓶頸。

針對這個問題，我們對內(nèi)存引擎做了無鎖化改造，其改造后的結(jié)構(gòu)如下圖所示：

整體改造主要跟上圖的 HashMap 和 SlabManager 兩個數(shù)據(jù)結(jié)構(gòu)有關(guān)（其他數(shù)據(jù)結(jié)構(gòu)在圖中已略掉）。HashMap 是存儲 KV 數(shù)據(jù)的核心結(jié)構(gòu)，它把 Key 通過 Hash 算法散列到不同的 Slot 槽位上，并利用鏈表處理 Hash 沖突；SlabManager管理不同尺寸內(nèi)存頁的申請和釋放，它利用鏈表把相同尺寸的內(nèi)存頁放到一起管理。

對于 HashMap，我們做了單寫多讀的無鎖鏈表改造。同時，通過引入 RCU 機制實現(xiàn)了異步的內(nèi)存回收，解決了讀請求與寫請求內(nèi)存釋放操作的沖突，實現(xiàn)了讀請求處理全程的無鎖化。

寫請求雖仍需要加鎖，但我們對寫做了鎖粒度的優(yōu)化，可以大幅提升并發(fā)度。比如我們把 SlabManager 的訪問由一把大鎖改成每個內(nèi)存尺寸的管理鏈表單獨一把鎖，這樣在分配和釋放不同尺寸內(nèi)存頁的時候就可以實現(xiàn)并發(fā)。同時 RCU 機制下的內(nèi)存異步回收，也解決了寫線程回收內(nèi)存時可能被阻塞的問題，進一步提升了寫性能。內(nèi)存引擎通過無鎖化加 RCU 技術(shù)的改造，讀處理能力提升了 30% 以上。

4.6 Cellar可用性的挑戰(zhàn)

同 Squirrel 一樣，Cellar 也通過建設集群間數(shù)據(jù)同步能力，實現(xiàn)了跨地域的容災架構(gòu)。不同的是，Cellar 因為是自研，無需考慮與社區(qū)版本的兼容性，同時為了簡化部署結(jié)構(gòu)、降低運維成本，它把集群間數(shù)據(jù)同步功能做到了存儲節(jié)點內(nèi)部。

如上圖示例的北京集群 A 節(jié)點、上海集群 H 節(jié)點，在接收到寫入之后，除了要做集群內(nèi)的數(shù)據(jù)同步以外，還需要把寫入數(shù)據(jù)同步到跨地域的另一個集群上。

Cellar 也可以通過配置兩個方向的跨集群數(shù)據(jù)同步鏈路，實現(xiàn)完全的本地域讀寫。Cellar 由于采用了存儲節(jié)點內(nèi)建的方案，它的集群間復制通過使用定制的復制包來甄別客戶寫入和復制寫入，并只為客戶寫入生成復制 log 來避免循環(huán)復制，相對Squirrel 會簡單一點。但同樣的，這種架構(gòu)也會遇到極端情況下，雙向同步導致的數(shù)據(jù)沖突問題。

4.7 雙向同步?jīng)_突自動解決

如上圖所示，Cellar 也實現(xiàn)了類似 Squirrel 的基于數(shù)據(jù)寫入本地時間的 last write win 沖突自動解決方案。

但 Cellar 的方案有一點區(qū)別是，它沒有通過在每條數(shù)據(jù)記錄 cluster id 的方式解決時鐘回退、兩次變更寫入的本地時間相同的問題，而是引入了 HLC（Hybrid Logic Clock）時鐘來解決這個問題。因為 HLC 可以保證每個集群寫入數(shù)據(jù)的時鐘是單調(diào)遞增的。

所以，接收端是不用擔心對端復制過來的數(shù)據(jù)有時間戳相同的問題。

而對于兩個集群分別寫入，時間戳相同且 HLC 的邏輯時鐘剛好也相同的情況，可以通過比較集群配置的 cluster id（不會存儲到每條 KV 數(shù)據(jù)內(nèi)）來決定最終哪個數(shù)據(jù)可以寫入。

5 發(fā)展規(guī)劃和業(yè)界趨勢

未來，根據(jù)技術(shù)棧自上而下來看，我們的規(guī)劃主要覆蓋服務、系統(tǒng)、硬件三個層次。

首先，在服務層主要包括三點：

第一，Squirrel && Cellar 去 ZK 依賴。如前所述，Squirrel 集群變更到客戶端的通知是依賴 ZK 來實現(xiàn)的，Cellar 的中心節(jié)點選主和元數(shù)據(jù)存儲也是依賴 ZK 實現(xiàn)的。但 ZK 在大規(guī)模變更、通知場景下，它的處理能力是無法滿足我們的需求的，很容易引發(fā)故障。

所以，Squirrel 會去掉對 ZK 的依賴，改為使用公司內(nèi)的配置管理、通知組件來實現(xiàn)集群變更到客戶端的通知。Cellar 會通過在中心節(jié)點間使用 Raft 協(xié)議組成 Raft 組，來實現(xiàn)選主和元數(shù)據(jù)多副本強一致存儲（注：本文整理自 DatafunSummit 2023 演講，此工作當前已完成開發(fā)，處于灰度落地階段）。

第二，向量引擎。大模型訓練、推理場景有很多向量數(shù)據(jù)存儲和檢索需求，業(yè)界很多 NoSQL、SQL 數(shù)據(jù)庫都支持了向量引擎能力。KV 存儲作為高性能的存儲服務，如果支持了向量引擎，可大幅提升大模型訓練、推理的效率。

第三，云原生。當前美團的 KV 服務規(guī)模很大，相應的運維成本也比較高。所以，我們計劃做一些服務云原生部署、調(diào)度方面的探索，向更高運維自動化水平邁進。

其次是系統(tǒng)層，計劃對 Kernel Bypass 技術(shù)做一些探索和研發(fā)落地，比如新版內(nèi)核支持的 io_uring、英特爾的 DPDK、SPDK 技術(shù)等。由于 KV 存儲是典型的高吞吐服務，它的網(wǎng)絡 IO、硬盤 IO 壓力都很大，Kernel Bypass 技術(shù)可以大幅提升服務的 IO 能力，降低訪問延遲和成本。

最后是硬件層，計劃對計算型硬件的應用做一些探索，比如配備了壓縮卡的 SSD，可以將服務引擎層使用 CPU 做的數(shù)據(jù)壓縮工作卸載到壓縮卡上，釋放出 CPU 資源做更高價值的計算工作。KV 服務是典型的低延遲、高網(wǎng)絡負載的服務。

所以，我們也計劃對 RDMA 網(wǎng)絡做一些探索，以期進一步降低服務訪問延遲、提升網(wǎng)絡處理能力。

6 本文作者

澤斌，來自美團基礎研發(fā)平臺/基礎技術(shù)部。