KV 存儲作爲美團一項重要的在線存儲服務，承載了在線服務每天萬億級的請求量，並且保持著 99.995% 的服務可用性。在 DataFunSummit 2023 數據基礎架構峰會上，我們分享了《美團大規模 KV 存儲挑戰與架構實踐》，本文爲演講內容的整理。文章主要分爲四個部分：第一部分介紹了美團 KV 存儲發展曆程；第二部分分享了內存 KV Squirrel 挑戰和架構實踐；第三部分闡述了持久化 KV Cellar 挑戰和架構實踐；最後一部分介紹了未來的發展規劃。希望這些內容能對大家有所幫助或啓發。
1 美團 KV 存儲發展曆程
2 大規模 KV 存儲的挑戰
3 內存 KV Squirrel 挑戰和架構實踐
3.1 Squirrel水平擴展的挑戰
3.2 Gossip優化
3.3 Squirrel 垂直擴展的挑戰
3.4 forkless RDB
3.5 工作多線程
3.6 Squirrel可用性的挑戰
3.7 兩機房容災
3.8 跨地域容災
3.9 雙向同步沖突自動解決
4 持久化 KV Cellar 挑戰和架構實踐
4.1 Cellar垂直擴展的挑戰
4.2 Bulkload 數據導入
4.3 線程調度模型優化
4.4 線程RTC模型改造
4.5 內存引擎無鎖化
4.6 Cellar可用性的挑戰
4.7 雙向同步沖突自動解決
5 發展規劃和業界趨勢
1 美團 KV 存儲發展曆程
上圖就是美團第一代的分布式 KV 存儲的架構，可能很多公司都經曆過這個階段。在客戶端內做一致性哈希，然後在後端部署上很多 Memcached 實例，這樣就實現了最基本的 KV 存儲分布式設計。但這樣的設計存在很明顯的問題：比如在宕機摘除節點會時丟失數據；此外，在緩存空間不夠需要擴容時，一致性哈希也會丟失一些數據，這樣會給業務的開發帶來很大的困擾。
隨著 Redis 項目的成熟，美團也引入了 Redis 來解決我們上面提到的問題，進而演進出來上圖這樣一個架構。可以看到，客戶端還是一樣，使用一致性哈希算法，在服務器端變成了 Redis 組成的主從結構。當任何一個節點宕機，我們可以通過 Redis 哨兵完成 failover，實現高可用。但有，還一個問題還是沒有解決，如果擴縮容的話，一致性哈希仍然會丟失數據。
這時我們發現業界有一個比較成熟的開源 KV 存儲：也就是阿裏巴巴的 Tair 。2014年，我們把 Tair 引入到技術內部，去滿足業務 KV 存儲方面的需求。Tair 開源版本的架構主要是三部分：最下邊的是存儲節點，存儲節點會上報心跳到它的中心節點，中心節點內部設有兩個配置管理節點，會監控所有的存儲節點。如果有任何存儲節點宕機或者擴容之類的行爲，它會做集群拓撲的重新構建。客戶端啓動的時候，它會直接從中心節點引入一個路由表，這個路由表簡單來說就是一個集群的數據分布圖，客戶端根據路由表直接去存儲節點讀寫。之前我們 KV 遇到的擴容丟數據問題，它也有數據遷移機制來保證數據的完整性。
但是在使用的過程中，我們還遇到了一些其他問題，比如：它的中心節點雖然是主備高可用的，但它沒有分布式仲裁之類的機制，所以在網絡分割的情況下，它是有可能發生“腦裂”的，這種情況也給我們的業務造成過比較大的影響。在容災擴容的時候，遇到過數據遷移影響業務可用性的問題。
另外，我們之前用過 Redis ，業務會發現 Redis 的數據結構特別豐富，而 Tair 還不支持這些數據結構。雖然我們用 Tair 解決了一些問題，但是 Tair 同樣也無法完全滿足我們的業務需求。于是，我們認識到在美團這樣一個業務規模大、複雜度高的場景下，很難有開源系統能很好滿足我們的需求。所以，我們決定在已應用的開源系統之上進行自研。
時值 2015 年， Redis 社區正式發布了它的集群版本 Redis Cluster。所以，我們緊跟社區步伐，並結合內部需求做了很多自研功能，進而演進出本文要介紹的全內存、高吞吐、低延遲的 KV 存儲 Squirrel。另外，我們基于 Tair，加入了很多美團自研的功能，演進出本文要介紹的持久化、大容量、數據高可靠的 KV 存儲 Cellar 。
Redis 社區一直都很活躍，所以，Squirrel 的叠代是自研和社區並重，自研功能設計上也會盡量與社區架構兼容。Tair 開源版本已經多年沒有更新，所以，Cellar 的叠代完全靠自研。後續內容上大家也能看到，因爲這方面的不同，Cellar 和 Squirrel 在解決同樣問題時可能會選取不同的方案。
這兩個存儲其實都是 KV 存儲領域的解決方案。實際應用上，如果業務的數據量小，對延遲敏感，建議用 Squirrel ；如果數據量大，對延遲不是特別敏感，我們建議用成本更低的 Cellar 。
2 大規模 KV 存儲的挑戰大規模KV 存儲的業務挑戰主要有兩點：一個是擴展性。隨著業務規模持續變大，業務會要求使用容量更大的集群。這個容量包括兩方面，一方面是數據量，還有一方面是調用量。擴展容量，最常見的方法就是把集群水平擴展到更多的節點，但是當集群節點數達到一定規模後，再想擴展新節點也會遇到很多困難，這是擴展性上的第一個挑戰。
還有一個問題是有些業務場景的調用容量是無法隨著集群水平擴展而擴展的。比如，很多業務會使用 mget 進行批量讀取。但隨著集群節點數的增加，由于“木桶效應”，整個 mget 請求的長尾延遲會越來越高，進而導致服務的請求超時率持續上升。等集群達到一定規模之後，長尾延遲造成的可用性降低就超出業務的承受能力了。所以在水平擴展之外，我們還需要解決好節點垂直擴展上的挑戰，來支持這種批量操作的業務場景。
另一個是可用性。隨著集群規模變大，要保證可用性維持在與小規模集群同等的水平，其實是很困難的。但業務服務卻不會因爲集群規模變大而能接受可用性有所降低。所以，美團的挑戰是如何保證集群可用性不會隨著規模的變大而有所降低。3 內存 KV Squirrel 挑戰和架構實踐
上圖是美團的 Squirrel 架構。中間部分跟 Redis 社區集群是一致的。它有主從的結構，Redis 實例之間通過 Gossip 協議去通信。我們在右邊添加了一個集群調度平台，包含調度服務、擴縮容服務和高可用服務等，它會去管理整個集群，把管理結果作爲元數據更新到 ZooKeeper。我們的客戶端會訂閱 ZooKeeper 上的元數據變更，實時獲取到集群的拓撲狀態，直接對 Redis 集群節點進行讀寫操作。
| 3.1 Squirrel水平擴展的挑戰但是基于 Redis Cluster 架構的水平擴展，會有如下問題：
一個是 Gossip 的消息通信量是節點數的平方，隨著集群節點數的增加，Gossip 通信的消息量會急劇膨脹。比如，我們實測對于一個 900 節點的集群，Gossip 消息的 CPU 消耗會高達12%，遠高于小集群的 Gossip 資源消耗，這樣會造成極大的資源浪費。
除了資源的浪費以外，Gossip 消息過多，也會更多搶占用戶請求處理線程的資源，進而會導致用戶請求經常被 Gossip 消息的處理所阻塞，再導致用戶請求産生更多的超時，影響服務可用性。| 3.2 Gossip優化
爲了解決上述的擴展性問題，我們對社區的 Gossip 方案進行了優化。首先針對 Gossip 傳輸的消息，我們通過 Merkle Tree 對其做了一個摘要，把集群 Gossip 通信的數據量減少了90%以上。服務端節點僅需要對比 Hash 值即可判斷元數據是否有更新，對于存在更新的情況也能快速判斷出更新的部分，並僅對此部分元數據進行獲取、更新，大幅降低了 Gossip 消息處理的資源消耗。同時，我們還增加了一個周期性的元數據全量同步功能，來解決可能因 Hash 沖突導致元數據無法更新的問題。
對基于 Redis 研發的 Squirrel 來說，垂直擴展會存在如下問題：
首先是數據容量的問題。對一個內存存儲來說，節點容量過大的話，很容易影響服務的可用性。例如，在主從節點要做數據同步時，Redis 節點需要通過 fork 産生子進程來生成全量數據的 RDB 快照。當一個 8GB 的節點做 fork 調用時，會由于頁表項過多，造成進程出現 500 毫秒的阻塞。對于平均耗時只有幾毫秒的 KV 請求來說，這 500 毫秒的阻塞會造成大量的超時。
還有就是處理量的擴展問題。雖然我們可以通過加從庫去擴展集群的讀能力上限，但主庫的寫處理能力卻還是無力擴展的。而且，受限于主庫的處理能力和機器帶寬限制，加從庫來擴展讀能力也是有上限的。
| 3.4 forkless RDB
針對上述節點過大，fork 生成 RDB 會導致可用性降低的問題。我們實現了 forkless RDB 方案，這是一個不基于 fork，且不會中斷服務的生成數據快照 RDB 的方案。
如上圖所示，forkless RDB 的生成期間，它首先會停止哈希表的 rehash 過程，避免數據在哈希表之間的搬遷影響快照的一致性。然後，它會從頭開始對整個哈希表的 key 做叠代，每叠代一個 key 就會把它 dump 一份出來放到複制隊列裏邊。在叠代 key 的同時，它會對叠代的位置記錄一個遊標。
如果在叠代哈希表的過程中，裏面的 KV 有變更的話，在這個遊標之前的 KV 變更，也會把它放到複制隊列裏邊，確保已經複制的 KV 能夠持續獲得後續的變更。如圖所示，RDB 遊標在 key 3，它會把之前已經叠代過的 key 1 更新、key 2 刪除操作也插入到複制隊列裏邊。在遊標之後的 key，因爲還沒有做數據複制，所以等後續叠代到這個 key 時，把其最新值 dump 到複制隊列就好。通過這樣的方式，就實現了一個不需要 fork 就能獲得一個一致性數據快照 RDB 的過程。
這個方案的優點很明顯，生成 RDB 的過程不會阻塞服務請求處理，並且因爲是實時的發送一個個 KV 數據，所以就不需要等 RDB 生成好就可以向從庫複制數據了，大幅提升了數據同步的速度。但因爲全量數據叠代、複制是在工作線程去做的，而不是在子進程內。所以，該方案會占用一部分工作線程的資源。另外，因爲是以 KV 爲粒度做複制的，所以，如果哈希表裏面有大 KV 的話，可能會因爲工作線程複制大 KV 耗時過長，造成用戶請求等待耗時的上升。| 3.5 工作多線程對于處理量的擴展，社區有一個 IO 多線程的解決方案。但這個 IO 多線程只是把網絡收發部分做了多線程處理，所以，其擴展能力是比較有限的。比如 4個 IO 線程下，它只能把整體的吞吐提升一倍，就到極限了。而且因爲此時工作線程已經到瓶頸了，再往上去加 IO 線程，不僅無法提升性能，反而會消耗更多的 CPU 資源。對此，我們的解決方案是工作多線程，也就是說把請求處理的過程也多線程化。
如上圖所示，在工作多線程方案下，每個線程都會去處理請求，並且每個線程會完成從收包到請求處理，然後到發包的整個過程，是一個 Run-to-Completion 線程模型。相比 IO 多線程，它會減少很多線程切換，節省很多的 CPU 資源。同時對于請求處理的過程，我們也通過細致的梳理，盡量縮小了臨界區的範圍，以保證大部分的請求處理過程是在臨界區之外的，來提升處理並發度。
如果一個工作線程需要加鎖的話，它會先 try lock。如果加鎖成功就繼續執行了，但如果加鎖失敗的話，這個工作線程也不會阻塞等鎖。它會先去注冊一個管道的通知消息，然後就繼續處理網絡的收發包，還有非臨界區的請求了。等到鎖被釋放的時候，這個工作線程會通過 epoll 獲得管道裏面的鎖釋放通知，然後去拿到這把鎖。這個時候它就可以去處理臨界區的請求操作了。
這樣的話，在整個加鎖、解鎖的過程中，工作線程沒有任何阻塞，仍然可以繼續做網絡收發、非臨界區請求的處理，獲得最大限度的處理能力。另外，對于新建 socket、數據複制等工作，跟工作線程的耦合很低，我們將其放到了單獨的線程去執行，以盡量降低工作線程的負載。
通過實測，工作多線程方案的吞吐比社區 IO 多線程提升了 70%，相對于社區單線程提升 3 倍多。
| 3.6 Squirrel可用性的挑戰
基于 Redis Cluster 的大規模集群可用性挑戰主要是維持機房容災部署很困難。如上圖所示，由于 Redis Cluster 是去中心化的架構，所以部署上要求至少是三機房分布，以此來保證任何一個機房挂掉的時候，剩余的兩個機房仍然能有過半的節點來選出新的主節點。比如一個上千節點的集群要擴容的話，可能需要幾百個分布在三個機房的節點，一時之間其實很難湊齊這麽多機房的資源。而當業務大促容量需求很急時，我們有時候只能犧牲機房容災能力來滿足業務的容量需求。
還有在成本方面，對于一些數據可靠性要求較低的業務，只需要兩副本冗余就夠了，極端情況下丟一點數據也是可以接受的。但受限于容災要求，這些業務也只能使用三機房三副本部署，從成本角度考量很不劃算。
| 3.7 兩機房容災
受 Google Spanner 的見證者節點啓發，我們在 Squirrel 集群也引入了見證者節點角色。同 Spanner 一樣，Squirrel 見證者節點也不會存儲數據，所以，它無法作爲正常的主從庫提供請求處理能力，也不能發起選主投票。但見證者節點可以在集群選主時參與投票，幫助存活的機房節點完成過半選主過程。
見證者節點還可以設置權重，這樣只需要一個或幾個高權重見證者節點，就能滿足一個大規模集群的容災部署需求了。由于見證者節點不存儲數據，且節點數很少，雖然集群還是三機房部署，但實際幾乎只需要兩機房的資源就能滿足機房容災部署需求了，這樣就大幅降低了集群維持容災部署的難度，從而節省大量的機器成本。
| 3.8 跨地域容災
Squirrel 跨地域容災的架構如上圖所示，它通過一個集群間同步服務在兩個不同地域的集群之間做數據同步。這個同步服務首先僞裝爲上遊集群節點的 slave 把它的 RDB 和增量 log 拉取過來，然後再把拉取到的數據轉化成寫請求發到下遊的集群，從而實現了一個集群間的數據同步。通過這樣的架構，我們解決了服務的跨地域容災問題。並且，通過在集群間搭建正反兩個方向的兩個同步任務，就能實現集群間的雙向同步。這樣的話，用戶服務就可以只在本地域寫，但同時能讀到兩個地域分別寫入的數據，解決了單向同步需要跨地域寫的問題。雙向同步有兩個經典問題需要解決：
一個是循環複制問題。我們爲每個 Squirrel 集群標記了不同的 cluster id，並且記錄了每個 KV 的初始寫入 cluster id，同步服務會過濾掉與目標集群 cluster id 相同的數據，以避免發生循環複制。
還有一個是數據沖突問題。我們一開始是通過業務層面保證在每個地域寫不同的 Key 來解決的。但是在雙向同步的運行過程中，還是會有一些極端場景可能會出現兩個地域並發寫同一個 Key。比如像機房網絡故障場景，業務會把故障機房的所有寫入都切到正常機房。
但由于我們的集群間複制是異步的，可能故障機房有一些最新的 Key 變更還沒有複制到正常機房的集群。而如果在業務將寫切換到正常機房後，又寫入了相同 Key 的不同變更，就會産生兩個同步集群的數據沖突。在機房網絡恢複之後，業務還是要把一部分流量切回到之前故障的集群上，恢複到跨地域容災的架構。
但由于兩個集群可能已經有數據沖突了，所以，在業務切回之前，就需要對數據做沖突校驗和修複。但是對大數據量集群來說，數據校驗和修複的耗時可能會長達數天。在這樣長的時間內，只有一個單地域集群來支撐業務，無論是從容災還是容量的角度來看，都是有較大風險的。| 3.9 雙向同步沖突自動解決
爲了解決上述的雙向同步數據沖突問題，我們實現了一個基于數據寫入本地時間的 last write win 沖突自動解決功能。如上圖所示，在 T1 時刻 Key money 的值在 A、B 兩個集群都是 100。T2 時刻，money 的值在 A 集群更新成了 120。但是在 A 集群的新值還沒複制到 B 集群的時候，B 集群在 T3 時刻把 money 的值更新成了 130。這時候 A、B 集群會互相向對方複制各自寫入的新值，A 集群收到 B 集群的值 130 後，會發現 B 集群 money 的更新時間大于自己（T3 > T2），它就會更新自己的 money 值爲 130；B 集群也會收到 A 集群複制過來的 money 值 120，但它會發現這個值的更新時間小于自己本地值的更新時間（T2 < T3），就會忽略這個複制請求。通過這樣一個基于更新時間的 last write win 策略，就可以達到最終一致性。
上述方案看起來簡單，但是在複雜、大規模的業務場景下，還有很多問題要處理，所以，我們還做了以下的工作：保存最近更新的時間戳：當發生時鍾回退時，我們會繼續使用自己保存的時間戳，避免使用本地回退的時間導致數據也跟著發生了回退。（PS：對于時鍾回退問題，我們調研過最新的 NTP 時鍾同步不會像以前一樣造成本地時鍾的回退或跳變，現在它通過把時鍾 tick 調快或調慢來完成類似的調整，所以，前述關于時鍾回退的解決方案在最新的 NTP 同步機制下就不是必要的了。不過，爲了保證我們的服務在任何系統下都能正常運行，我們最終還是實現了這個功能。）記錄寫入數據的集群 id：我們會爲所有寫入的 Key 保存寫入的集群 id。當兩個值的更新時間相同時，我們會比較集群 id，如果也相同，我們就知道是同一個集群先後寫入但獲取到相同本地時間的數據，會允許其寫入；如果不同，我們僅會讓集群 id 更大的值寫入，來保證數據最終一致性。由複制操作改爲複制變更後的數據：像 INCR 類接口，A 集群的 money T1 時刻通過 INCRBY money 20 變成了 120，然後 B 集群 T2 時刻通過 INCRBY money 30 變成了 130。A 集群收到 B 集群的複制時，因爲時間戳比自己的本地值大，它會執行 INCRBY money 30 變成 150；然後 B 集群收到 A 集群的複制時，因爲時間戳比自己的本地值小，它會把這個複制請求給忽略掉，就造成了數據沖突。針對這個問題，我們將所有操作的數據複制都改成了複制操作後的數據，而不是這個操作本身，來解決類似 INCRBY 這種接口的數據沖突問題。保存最近刪除的 Key：像刪除類接口，A 集群 T2 時刻寫入了 money：120，然後 B 集群在 T3 時刻刪除了 money 這個 Key。A 集群收到 B 集群的複制時，由于其時間戳比本地值大，A 會把數據刪了；但 B 集群收到 A 集群的複制時，由于本地已經不存在 money 這個 Key 了，它就會把 money 當做一個新 Key 進行寫入，就造成了數據最終不一致。針對這個問題，我們通過保存最近一段時間刪除掉的 Key 及刪除時間戳，以便在刪除集群收到對端複制過來的舊 Key 時進行甄別。4 持久化 KV Cellar 挑戰和架構實踐
上圖是我們最新的 Cellar 架構圖，它跟阿裏開源的 Tair 主要有兩個層面的不同。第一個是 OB，第二個是 ZooKeeper。我們的 OB 跟 ZooKeeper 的 Observer 是類似的作用，提供 Cellar 中心節點元數據的查詢服務。它實時的與中心節點的 Master 同步最新的路由表，客戶端的路由表都是從 OB 去拿。這樣做的好處主要有兩點：第一，把大量的業務客戶端跟集群的大腦 Master 做了隔離，防止路由表請求影響集群的管理；第二，因爲 OB 只提供路由表查詢服務，不參與集群的管理，所以它可以水平擴展，極大地提升了路由表的查詢能力。
第二個是我們引入了 ZooKeeper 做分布式仲裁，解決了上述提到的 Master、Slave 在網絡分割情況下的“腦裂”問題。並且通過把集群的元數據存儲到 ZooKeeper，從而提升了元數據的可靠性。
| 4.1 Cellar垂直擴展的挑戰在 Cellar 架構下，不存在水平擴展的問題，但與 Squirrel 一樣，它也有垂直擴展方面的挑戰。而由于 Cellar 是持久存儲，它也很少遇到單機數據容量的問題，而要解決的問題主要是處理容量的垂直擴展。而且，由于 Cellar 是持久化引擎、多線程模型，它要解決的處理容量擴展問題也是不一樣的，具體如下：
引擎讀寫能力的不均衡性：Cellar 是基于 LSM-Tree 引擎模型的持久化存儲，這種引擎的多 Level compaction 會導致寫放大問題，進而會造成其寫處理能力比讀低很多。所以，在一些寫相對較多的場景，機器資源雖然還有空閑，但寫處理能力卻已經到瓶頸了。線程間同步的開銷：想要提升處理容量，就需要增加線程數。而隨著線程數的增加，線程間同步的開銷在整個服務的 CPU 使用占比也會越來越高。所以，如果解決不好線程間同步的問題，想單純地增加線程數來提升處理容量行不通。| 4.2 Bulkload 數據導入對于上述提到引擎寫壓力達到瓶頸的集群，我們調研後發現其在線的實時寫入一般都是比較少的，高寫入量主要是用戶從離線批量寫數據到線上 Cellar 集群帶來的。基于此，我們開發了 Bulkload 數據導入能力來解決這個問題。
Bulkload 整體架構如上圖所示，它在普通寫入流涉及的客戶端和存儲節點之外，還引入了 S3 對象存儲來做導入數據的中轉。下面我們看下 Bulkload 具體的寫入流程：Bulkload 首先會在客戶端進程內生成分片內有序的數據文件並寫到本地硬盤上。等客戶端的數據文件寫好之後，它會上傳到對象存儲，利用對象存儲做數據文件的中轉，解決了客戶端與服務端之間直傳大文件容易失敗的問題。分片 1 的數據文件寫入到對象存儲之後，客戶端會將數據文件的存儲地址告訴分片 1 的主所在的存儲節點 DS1。然後 DS1 就會從對象存儲下載分片 1 的數據文件，並把它直接插入到 LSM-Tree 引擎裏面。因爲這是一個完整的文件插入，所以，它可以消除引擎在普通寫入時的內存排序和刷盤壓力。同時，因爲這個文件的數據是分片內有序的，所以，它在參與 Level 間 Compaction 時會與其他的引擎文件交叉很少，可以大幅減少多 Level compaction 的壓力。
然後 DS1 會把分片 1 數據文件的對象存儲地址複制發送到分片 1 的從所在的存儲節點 DS2 。因爲存儲節點的複制只是傳輸數據文件的地址，所以複制速度是特別快的，也節省了很多傳輸的帶寬。DS2 收到了分片 1 的地址後同樣會從對象存儲下載數據文件，並插入到引擎裏面。
通過 Bulkload 解決方案，我們整體把數據離線導入的性能提升到舊版的 5 倍。比如我們的一個存儲廣告特征的客戶使用 KV 方式從離線導數據到在線需要 14 小時，受限于在線高峰期無法導數據，如果需要繼續增加特征數據，就需要擴容集群了。而擴容集群一方面會因爲“木桶效應”導致請求長尾延遲問題，另一方面 Cellar 成本的上升也會抵消一部分廣告收益。而在 Bulkload 功能加持下，該客戶導入相同規模數據僅需不到 3 小時，它可以在不增加 Cellar 資源的情況下，將廣告特征規模增加數倍，大幅提升了廣告的效果。
| 4.3 線程調度模型優化我們最初的線程模型與開源版 Tair 一樣，網絡線程池做收發包，收到的包經過一個隊列轉出到一個大的工作線程池做請求處理。這樣的線程模型，很容易發生請求間的互相影響。比如用戶有離線數據導入到 Cellar 的時候，就很容易導致在線讀請求的超時。又比如當有大 Value 讀寫的時候，工作線程處理會比較慢、占用線程的時間會很長，導致正常 Value 讀寫的快請求只能在隊列等待，進而導致大量超時。
所以，爲了隔離在離線請求、快慢請求的處理，讓服務資源優先保證核心流量的處理，我們後來把線程模型改造成如上圖所示的 4 個隊列 + 4 個線程池的結構，將請求分成 4 類（讀快、讀慢、寫快、寫慢）分別放到不同的隊列和線程池去處理，進而來提升服務核心流量的可用性。
但是，工作線程池按照請求類型分離之後帶來一個問題，就是不同業務場景、甚至同一業務的不同時段，不同類型請求量的占比是不一樣的。所以，給每個線程池分配多少線程是一個很棘手的問題。
針對這個問題，我們增加了一個線程動態調度的邏輯：每個線程池都有一部分線程被設定爲可共享線程，如果線程池比較空閑，共享線程就會去輪詢其他的隊列，處理一些繁忙線程池的請求，這樣就達到了自適應調整各線程池資源的效果。但是在這樣的架構下，雖然解決好了請求隔離性和不同請求類型線程資源的動態分配問題，但我們發現隨著節點流量的上漲，共享線程對于其他隊列的輪詢會消耗越來越多的 CPU 資源，而且集群業務的負載分布與默認的線程數設置差異越大，這個消耗的占比也會越高。
爲了解決上述線程池資源自適應調度帶來的 CPU 消耗問題，我們對分離後的線程、隊列模型做出了如上圖的改造。改進後的線程模型最主要的特點是引入了一個調度線程和一個空閑線程池，這個調度線程會實時統計每個線程池的負載，來評估每個線程池是否需要增加或減少線程並做出調度動作，空閑線程池用來存放當前空閑的可用于調配的線程資源。當調度線程評估後決定做線程資源調配時，它就會發送調度指令到相應隊列中，當線程池裏的線程獲取並執行了這個指令後，就實現了線程資源的調配。比如，它想給讀快線程池增加線程，就會給空閑線程池的隊列發送一個調度指令，空閑線程池的線程取到這個指令後，就會將自己加入到讀快隊列的線程池裏面，去處理讀快隊列的請求。
當調度線程想對讀慢線程池調減線程時，它會向讀慢隊列發送一個調度指令，讀慢隊列的線程獲取到這個指令後，就會離開讀慢線程池加入到空閑線程池。通過調度線程准實時的毫秒級負載統計、調度，我們實現了線程池資源的快速動態分配。對于每一個線程池的共享線程，也不再需要去輪詢其他線程池的隊列了，只需要專心處理自己隊列的請求即可，大幅降低了線程池資源調度的 CPU 消耗。
通過上述的線程隊列模型優化，服務在高負載場景下可以提高 30% 以上的吞吐量。| 4.4 線程RTC模型改造
上圖左側畫的是我們服務請求的 IO 處理路徑：一個請求的處理流程會經過網絡線程、請求隊列、工作線程、內存和硬盤引擎。這個設計的問題是，請求在不同線程之間流轉會造成大量的 CPU 切換以及 CPU 高速緩存的 Cache Miss，進而造成大量的 CPU 資源消耗。在大流量場景下，這樣的 CPU 消耗也是很可觀的一筆資源。針對這個問題，我們對線程隊列模型又做了如上圖右側所示的改造。新的模型下，我們讓網絡線程直接去做讀請求的處理，對于能夠命中內存引擎的讀請求，其處理模型就是一個 RTC（Run-to-Completion）模型。
具體來講，當網絡線程收到一個請求之後，會先判斷是否爲一個讀請求，如果是，就會直接去讀內存引擎。我們服務的內存引擎會緩存硬盤引擎上的熱點數據，如果內存引擎命中的話，網絡線程就可以直接返回結果給客戶端。這樣在網絡線程內就實現了請求的閉環處理，相比原來的模型可以去除所有因請求流轉造成的 CPU 資源消耗。而對于寫和讀未命中內存引擎的請求，仍然需要經過原來的請求處理路徑，去硬盤引擎讀或者寫數據。
新的線程模型，經實測在 80% 內存引擎命中率場景下，服務讀吞吐可以提升 30%+。雖然新的線程隊列模型只實現了讀緩存命中請求的 RTC，但其實在線流量大多都是讀多寫少且熱點數據明顯、內存引擎命中率比較高的場景，所以，新模型上線後在大多數的業務集群都取得了明顯的性能提升。| 4.5 內存引擎無鎖化當單機請求量達到了一定規模之後，我們發現服務內的鎖操作會占用很多的 CPU 資源。經分析發現，大多數的鎖操作都發生在上節內容提到的內存緩存引擎上。如上節所述，所有請求都會經過內存引擎，且大部分請求都會在內存引擎命中並返回結果給客戶端。所以，大部分請求都是純內存處理，這個過程中的鎖操作就很容易成爲瓶頸。針對這個問題，我們對內存引擎做了無鎖化改造，其改造後的結構如下圖所示：
整體改造主要跟上圖的 HashMap 和 SlabManager 兩個數據結構有關（其他數據結構在圖中已略掉）。HashMap 是存儲 KV 數據的核心結構，它把 Key 通過 Hash 算法散列到不同的 Slot 槽位上，並利用鏈表處理 Hash 沖突；SlabManager管理不同尺寸內存頁的申請和釋放，它利用鏈表把相同尺寸的內存頁放到一起管理。對于 HashMap，我們做了單寫多讀的無鎖鏈表改造。同時，通過引入 RCU 機制實現了異步的內存回收，解決了讀請求與寫請求內存釋放操作的沖突，實現了讀請求處理全程的無鎖化。寫請求雖仍需要加鎖，但我們對寫做了鎖粒度的優化，可以大幅提升並發度。比如我們把 SlabManager 的訪問由一把大鎖改成每個內存尺寸的管理鏈表單獨一把鎖，這樣在分配和釋放不同尺寸內存頁的時候就可以實現並發。同時 RCU 機制下的內存異步回收，也解決了寫線程回收內存時可能被阻塞的問題，進一步提升了寫性能。
內存引擎通過無鎖化加 RCU 技術的改造，讀處理能力提升了 30% 以上。| 4.6 Cellar可用性的挑戰
同 Squirrel 一樣，Cellar 也通過建設集群間數據同步能力，實現了跨地域的容災架構。不同的是，Cellar 因爲是自研，無需考慮與社區版本的兼容性，同時爲了簡化部署結構、降低運維成本，它把集群間數據同步功能做到了存儲節點內部。如上圖示例的北京集群 A 節點、上海集群 H 節點，在接收到寫入之後，除了要做集群內的數據同步以外，還需要把寫入數據同步到跨地域的另一個集群上。Cellar 也可以通過配置兩個方向的跨集群數據同步鏈路，實現完全的本地域讀寫。Cellar 由于采用了存儲節點內建的方案，它的集群間複制通過使用定制的複制包來甄別客戶寫入和複制寫入，並只爲客戶寫入生成複制 log 來避免循環複制，相對Squirrel 會簡單一點。但同樣的，這種架構也會遇到極端情況下，雙向同步導致的數據沖突問題。| 4.7 雙向同步沖突自動解決
如上圖所示，Cellar 也實現了類似 Squirrel 的基于數據寫入本地時間的 last write win 沖突自動解決方案。但 Cellar 的方案有一點區別是，它沒有通過在每條數據記錄 cluster id 的方式解決時鍾回退、兩次變更寫入的本地時間相同的問題，而是引入了 HLC（Hybrid Logic Clock）時鍾來解決這個問題。因爲 HLC 可以保證每個集群寫入數據的時鍾是單調遞增的。所以，接收端是不用擔心對端複制過來的數據有時間戳相同的問題。而對于兩個集群分別寫入，時間戳相同且 HLC 的邏輯時鍾剛好也相同的情況，可以通過比較集群配置的 cluster id（不會存儲到每條 KV 數據內）來決定最終哪個數據可以寫入。5 發展規劃和業界趨勢未來，根據技術棧自上而下來看，我們的規劃主要覆蓋服務、系統、硬件三個層次。
首先，在服務層主要包括三點：
第一，Squirrel && Cellar 去 ZK 依賴。如前所述，Squirrel 集群變更到客戶端的通知是依賴 ZK 來實現的，Cellar 的中心節點選主和元數據存儲也是依賴 ZK 實現的。但 ZK 在大規模變更、通知場景下，它的處理能力是無法滿足我們的需求的，很容易引發故障。所以，Squirrel 會去掉對 ZK 的依賴，改爲使用公司內的配置管理、通知組件來實現集群變更到客戶端的通知。Cellar 會通過在中心節點間使用 Raft 協議組成 Raft 組，來實現選主和元數據多副本強一致存儲（注：本文整理自 DatafunSummit 2023 演講，此工作當前已完成開發，處于灰度落地階段）。第二，向量引擎。大模型訓練、推理場景有很多向量數據存儲和檢索需求，業界很多 NoSQL、SQL 數據庫都支持了向量引擎能力。KV 存儲作爲高性能的存儲服務，如果支持了向量引擎，可大幅提升大模型訓練、推理的效率。第三，雲原生。當前美團的 KV 服務規模很大，相應的運維成本也比較高。所以，我們計劃做一些服務雲原生部署、調度方面的探索，向更高運維自動化水平邁進。其次是系統層，計劃對 Kernel Bypass 技術做一些探索和研發落地，比如新版內核支持的 io_uring、英特爾的 DPDK、SPDK 技術等。由于 KV 存儲是典型的高吞吐服務，它的網絡 IO、硬盤 IO 壓力都很大，Kernel Bypass 技術可以大幅提升服務的 IO 能力，降低訪問延遲和成本。
最後是硬件層，計劃對計算型硬件的應用做一些探索，比如配備了壓縮卡的 SSD，可以將服務引擎層使用 CPU 做的數據壓縮工作卸載到壓縮卡上，釋放出 CPU 資源做更高價值的計算工作。KV 服務是典型的低延遲、高網絡負載的服務。所以，我們也計劃對 RDMA 網絡做一些探索，以期進一步降低服務訪問延遲、提升網絡處理能力。6 本文作者
澤斌，來自美團基礎研發平台/基礎技術部。
---------- END ----------
本文由高可用架構轉載。技術原創及架構實踐文章，歡迎通過公衆號菜單「聯系我們」進行投稿
