一. 背景

分布式應用編排調度系統(tǒng) Kubernetes 已經(jīng)成為云原生應用基座的事實標準，但是其官方的穩(wěn)定運行規(guī)模僅僅局限在 5,000 節(jié)點。這對于大部分的應用場景已經(jīng)足夠，但是對于百萬規(guī)模機器節(jié)點的超大規(guī)模應用場景， Kubernetes 難以提供穩(wěn)定的支撐。

尤其隨著“數(shù)字化””云原生化”的發(fā)展，全球整體 IT 基礎設施規(guī)模仍在加速增長，對于分布式應用編排調度系統(tǒng)，有兩種方式來適應這種趨勢：

• 水平擴展 ： 即構建管理多個集群的能力，在集群故障隔離、混合云等方面更具優(yōu)勢，主要通過集群聯(lián)邦（Cluster Federation）來實現(xiàn)；
• 垂直擴展 ： 即提高單個集群的規(guī)模，在降低集群運維管理成本、減少資源碎片、提高整體資源利用率方面更具優(yōu)勢。

K8s 采用的是一種中心化的架構，所有組件都與 APIServer 交互，而 APIServer 則需要將集群元數(shù)據(jù)持久化到元信息存儲系統(tǒng)中。當前，etcd 是 APIServer 唯一支持的元信息存儲系統(tǒng)，隨著單個集群規(guī)模的逐漸增大，存儲系統(tǒng)的讀寫吞吐以及總數(shù)據(jù)量都會不斷攀升，etcd 不可避免地會成為整個分布式系統(tǒng)的瓶頸。

1.1 Kubernetes元信息存儲需求

APIServer 并不能直接使用一般的強一致 KV 數(shù)據(jù)庫作為元信息存儲系統(tǒng)，它與元信息存儲系統(tǒng)的交互主要包括數(shù)據(jù)全量和增量同步的 List/Watch，以及單個 KV 讀寫。更近一步來說，它主要包含以下方面：

• 在版本控制方面，存儲系統(tǒng)需要對 APIServer 暴露數(shù)據(jù)的版本信息，APIServer 側依賴于數(shù)據(jù)的版本生成對應的 ResourceVersion；
• 在寫操作方面，存儲系統(tǒng)需要支持 Create/Update/Delete 三種語義的操作，更為重要的是，存儲系統(tǒng)需要支持在寫入或者刪除數(shù)據(jù)時對數(shù)據(jù)的版本信息進行 CAS；
• 在讀操作方面，存儲系統(tǒng)需要支持指定版本進行快照 List 以此從存儲中獲取全量的數(shù)據(jù)，填充APIServer 中的 WatchCache 或供查詢使用，此外也需要支持讀取數(shù)據(jù)的同時獲取對應的數(shù)據(jù)版本信息；
• 在事件監(jiān)聽方面，存儲系統(tǒng)需要支持獲取特定版本之后的有序變更，這樣 APIServer 通過 List 從元信息存儲中獲取了全量的數(shù)據(jù)之后，可以監(jiān)聽快照版本之后的所有變更事件，進而以增量的方式來更新 Watch Cache 以及向其他組件進行變更的分發(fā)，進而保證 K8s 各個組件中數(shù)據(jù)的最終一致性。

1.2 etcd 的實現(xiàn)方式與瓶頸

etcd 本質上是一種主從架構的強一致、高可用分布式 KV 存儲系統(tǒng)：

• 節(jié)點之間，通過 Raft 協(xié)議進行選舉，將操作抽象為 log 基于 Raft 的日志同步機制在多個狀態(tài)機上同步；
• 單節(jié)點上，按順序將 log 應用到狀態(tài)機，基于 boltdb 進行狀態(tài)持久化 。

對于 APIServer 元信息存儲需求，etcd 大致通過以下方式來實現(xiàn):

• 在版本控制方面，etcd 使用 Revision 作為邏輯時鐘，對每一個修改操作，會分配遞增的版本號Revision，以此進行版本控制，并且在內存中通過 TreeIndex 管理 Key 到 Revision 的索引；
• 在寫操作方面，etcd 以串行 Apply Raft Log 的方式實現(xiàn)，以 Revision 為鍵，Key/Value/Lease 等數(shù)據(jù)作為值存入 BoltDB 中，在此基礎上實現(xiàn)了支持對 Revision 進行 CAS 的寫事務；
• 在讀操作方面，etcd 則是通過管理 Key 到 Revision 的 TreeIndex 來查詢 Revision 進而查詢 Value，并在此基礎上實現(xiàn)快照讀；
• 在事件監(jiān)聽方面，歷史事件可以從 BoltDB 中指定 Revision 獲取 KV 數(shù)據(jù)轉換得到，而新事件則由寫操作同步 Notify 得到。

etcd 并不是一個專門為 K8s 設計的元信息存儲系統(tǒng)，其提供的能力是 K8s 所需的能力的超集。在使用過程中，其暴露出來的主要問題有：

• etcd 的網(wǎng)絡接口層限流能力較弱，雪崩時自愈能力差；
• etcd 所采用的是單 raft group，存在單點瓶頸，單個 raft group 增加節(jié)點數(shù)只能提高容錯能力，并不能提高寫性能；
• etcd 的 ExpensiveRead 容易導致 OOM，如果采用分頁讀取的話，延遲相對會提高；
• boltdb 的串行寫入，限制了寫性能，高負載下寫延遲會顯著提高；
• 長期運行容易因為碎片問題導致寫性能發(fā)生一定劣化，線上集群定期通過 defrag 整理碎片，一方面會比較復雜，另一方面也可能會影響可用性。

二. 新的元數(shù)據(jù)存儲

過去面對生產(chǎn)環(huán)境中 etcd 的性能問題，只能通過按 Resource 拆分存儲、etcd 參數(shù)調優(yōu)等手段來進行一定的緩解。但是面對 K8s 更大范圍的應用之后帶來的挑戰(zhàn)，我們迫切的需要一個更高性能的元數(shù)據(jù)存儲系統(tǒng)作為 etcd 的替代方案，從而能對上層業(yè)務有更有力的支撐。

在調研了 K8s 集群的需求以及相關開源項目之后，我們借鑒了 k3s 的開源項目 kine 的思想，設計并實現(xiàn)了基于分布式 KV 存儲引擎的高性能 K8s 元數(shù)據(jù)存儲項目—— KubeBrain 。

KubeBrain 系統(tǒng)實現(xiàn)了 APIServer 所使用的元信息存儲 API ，整體采用主從架構，主節(jié)點負責處理寫操作和事件分發(fā)，從節(jié)點負責處理讀操作，主節(jié)點和從節(jié)點之間共享一個分布式強一致 KV 存儲，在此基礎上進行數(shù)據(jù)讀寫。下面介紹 KubeBrain 的核心模塊。

2.1 存儲引擎

KubeBrain 統(tǒng)一抽象了邏輯層所使用的 KeyValue 存儲引擎接口，以此為基礎，項目實現(xiàn)了核心邏輯與底層存儲引擎的解耦：

• 邏輯層基于存儲引擎接口來操作底層數(shù)據(jù)，不關心底層實現(xiàn)；
• 對接新的存儲引擎只需要實現(xiàn)對應的適配層，以實現(xiàn)存儲接口。

目前項目已經(jīng)實現(xiàn)了對 ByteKV 和 TiKV 的適配，此外還實現(xiàn)了用于測試的適配單機存儲 Badger 的版本。需要注意的是，并非所有 KV 存儲都能作為 KubeBrain 的存儲引擎。當前 KubeBrain 對于存儲引擎有著以下特性要求：

• 支持快照讀
• 支持雙向遍歷
• 支持讀寫事務或者帶有CAS功能的寫事務
• 對外暴露邏輯時鐘

此外，由于 KubeBrain 對于上層提供的一致性保證依賴于存儲引擎的一致性保證， KubeBrain 要求存儲引擎的事務需要達到以下級別（定義參考 HATs ：??http://www.vldb.org/pvldb/vol7/p181-bailis.pdf）：??

• Isolation Guarantee: Snapshot Isolation
• Session Guarantee: Linearizable

在內部生產(chǎn)環(huán)境中， KubeBrain 均以 ByteKV 為存儲引擎提供元信息存儲服務。ByteKV 是一種強一致的分布式 KV 存儲。在 ByteKV 中，數(shù)據(jù)按照 key 的字典序有序存儲。當單個 Partition 數(shù)據(jù)大小超過閾值時， Partition 自動地分裂，然后可以通過 multi-raft group 進行水平擴展，還支持配置分裂的閾值以及分裂邊界選擇的規(guī)則的定制。此外， ByteKV 還對外暴露了全局的時鐘，同時支持寫事務和快照讀，并且提供了極高的讀寫性能以及強一致的保證。

2.2 選主機制

KubeBrain 基于底層強一致的分布式 KV 存儲引擎，封裝實現(xiàn)了一種 ResourceLock，在存儲引擎中指向一組特定的 KeyValue。ResourceLock 中包含主節(jié)點的地址以及租約的時長等信息。

KubeBrain 進程啟動后均以從節(jié)點的身份對自己進行初始化，并且會自動在后臺進行競選。競選時，首先嘗試讀取當前的 ResourceLock。如果發(fā)現(xiàn)當前 ResourceLock 為空，或者 ResourceLock 中的租約已經(jīng)過期，節(jié)點會嘗試將自己的地址以及租約時長以 CAS 的方式寫入 ResourceLock，如果寫入成功，則晉升為主節(jié)點。

從節(jié)點可以通過 ResourceLock 讀取主節(jié)點的地址，從而和主節(jié)點建立連接，并進行必要的通信，但是主節(jié)點并不感知從節(jié)點的存在。即使沒有從節(jié)點，單個 KubeBrain 主節(jié)點也可以提供完成的 APIServer 所需的 API，但是主節(jié)點宕機后可用性會受損。

2.3 邏輯時鐘

KubeBrain 與 etcd 類似，都引入了 Revision 的概念進行版本控制。KubeBrain 集群的發(fā)號器僅在主節(jié)點上啟動。當從節(jié)點晉升為主節(jié)點時，會基于存儲引擎提供的邏輯時鐘接口來進行初始化，發(fā)號器的Revision 初始值會被賦值成存儲引擎中獲取到的邏輯時間戳。

單個 Leader 的任期內，發(fā)號器發(fā)出的整數(shù)號碼是單調連續(xù)遞增的。主節(jié)點發(fā)生故障時，從節(jié)點搶到主，就會再次重復一個初始化的流程。由于主節(jié)點的發(fā)號是連續(xù)遞增的，而存儲引擎的邏輯時間戳可能是非連續(xù)的，其增長速度是遠快于連續(xù)發(fā)號的發(fā)號器，因此能夠保證切主之后， Revision 依然是遞增的一個趨勢，舊主節(jié)點上發(fā)號器所分配的最大的 Revision 會小于新主節(jié)點上發(fā)號器所分配的最小的Revision。

KubeBrain 主節(jié)點上的發(fā)號是一個純內存操作，具備極高的性能。由于 KubeBrain 的寫操作在主節(jié)點上完成，為寫操作分配 Revision 時并不需要進行網(wǎng)絡傳輸，因此這種高性能的發(fā)號器對于優(yōu)化寫操作性能也有很大的幫助。

2.4 數(shù)據(jù)模型

KubeBrain 對于 API Server 讀寫請求參數(shù)中的 Raw Key，會進行編碼出兩類 Internal Key寫入存儲引擎索引和數(shù)據(jù)。對于每個 Raw Key，索引 Revision Key 記錄只有一條，記錄當前 Raw Key 的最新版本號， Revision Key 同時也是一把鎖，每次對 Raw Key 的更新操作需要對索引進行 CAS。數(shù)據(jù)記錄Object Key 有一到多條，每條數(shù)據(jù)記錄了 Raw Key 的歷史版本與版本對應的 Value。Object Key 的編碼方式為magic+raw_key+split_key+revision，其中：

• magic為\x57\xfb\x80\x8b；
• raw_key為實際 API Server 輸入到存儲系統(tǒng)中的 Key ；
• split_key為$；
• revision為邏輯時鐘對寫操作分配的邏輯操作序號通過 BigEndian 編碼成的 Bytes 。

• 根據(jù) Kubernetes 的校驗規(guī)則，raw_key 只能包含小寫字母、數(shù)字，以及'-' 和 '.'，所以目前選擇 split_key 為 $ 符號。

特別的，Revision Key 的編碼方式和 Object Key 相同，revision取長度為 8 的空 Bytes 。這種編碼方案保證編碼前和編碼后的比較關系不變。

在存儲引擎中，同一個 Raw Key 生成的所有 Internal Key 落在一個連續(xù)區(qū)間內 。

這種編碼方式有以下優(yōu)點：

• 編碼可逆，即可以通過Encode(RawKey,Revision)得到InternalKey，相對應的可以通過Decode(InternalKey)得到Rawkey與Revision；
• 將 Kubernetes 的對象數(shù)據(jù)都轉換為存儲引擎內部的 Key-Value 數(shù)據(jù)，且每個對象數(shù)據(jù)都是有唯一的索引記錄最新的版本號，通過索引實現(xiàn)鎖操作；
• 可以很容易地構造出某行、某條索引所對應的 Key，或者是某一塊相鄰的行、相鄰的索引值所對應的 Key 范圍；
• 由于 Key 的格式非單調遞增，可以避免存儲引擎中的遞增 Key 帶來的熱點寫問題

2.5 數(shù)據(jù)寫入

每一個寫操作都會由發(fā)號器分配一個唯一的寫入 revision ，然后并發(fā)地對存儲引擎進行寫入。在 創(chuàng)建、更新 和 刪除 Kubernetes 對象數(shù)據(jù)的時候，需要同時操作對象對應的索引和數(shù)據(jù)。由于索引和數(shù)據(jù)在底層存儲引擎中是不同的 Key-Value 對，需要使用 寫事務 保證更新過程的 原子性，并且要求至少達到 Snapshot Isolation 。

同時 KubeBrain 依賴索引實現(xiàn)了樂觀鎖進行并發(fā)控制。KubeBrain 寫入時，會先根據(jù) APIServer 輸入的 RawKey 以及被發(fā)號器分配的 Revision 構造出實際需要到存儲引擎中的 Revision Key 和 Object Key，以及希望寫入到 Revision Key 中的 Revision Bytes。在寫事務過程中，先進行索引 Revision Key 的檢查，檢查成功后更新索引 Revision Key，在操作成功后進行數(shù)據(jù) Object Key 的插入操作。

• 執(zhí)行 Create 請求時，當 Revision Key 不存在時，才將 Revision Bytes 寫入 Revision Key 中，隨后將 API Server 寫入的 Value 寫到 Object Key 中；
• 執(zhí)行 Update 請求時，當 Revision Key 中存放的舊 Revision Bytes 符合預期時，才將新 Revision Bytes 寫入，隨后將 API Server 寫入的 Value 寫到 Object Key 中；
• 執(zhí)行 Delete 請求時，當 Revision Key 中存放的舊 Revision Bytes 符合預期時，才將新 Revision Bytes 附帶上刪除標記寫入，隨后將 tombstone 寫到 Object Key 中。

由于寫入數(shù)據(jù)時基于遞增的 Revision 不斷寫入新的 KeyValue ， KubeBrain 會進行后臺的垃圾回收操作，將 Revision 過舊的數(shù)據(jù)進行刪除，避免數(shù)據(jù)量無限增長。

2.6 數(shù)據(jù)讀取

數(shù)據(jù)讀取分成點讀和范圍查詢查詢操作，分別對應 API Server 的 Get 和 List 操作。

Get 需要指定讀操作的ReadRevision，需要讀最新值時則將 ReadRevision 置為最大值MaxUint64， 構造 Iterator ，起始點為Encode(RawKey, ReadRevision)，向Encode( RawKey, 0)遍歷，取第一個。

范圍查詢需要指定讀操作的ReadRevision 。對于范圍查找的 RawKey 邊界[RawKeyStart, RawKeyEnd)區(qū)間， KubeBrain 構造存儲引擎的 Iterator 快照讀，通過編碼將 RawKey 的區(qū)間映射到存儲引擎中 InternalKey 的數(shù)據(jù)區(qū)間

• InternalKey 上界InternalKeyStart為Encode(RawKeyStart, 0)
• InternalKey 的下界為InternalKeyEnd為Encode(RawKeyEnd, MaxRevision)

對于存儲引擎中[InternalKeyStart, InternalKeyEnd)內的所有數(shù)據(jù)按序遍歷，通過Decode(InternalKey)得到RawKey與Revision，對于一個RawKey 相同的所有ObjectKey，在滿足條件Revision<=ReadRevision的子集中取Revision最大的，對外返回。 2.7 事件機制

對于所有變更操作，會由 TSO 分配一個連續(xù)且唯一的 revision ，然后并發(fā)地寫入存儲引擎中。變更操作寫入存儲引擎之后，不論寫入成功或失敗，都會按照 revision 從小到大的順序，將變更結果提交到滑動窗口中，變更結果包括變更的類型、版本、鍵、值、寫入成功與否 。在記錄變更結果的滑動窗口中，從起點到終點，所有變更數(shù)據(jù)中的 revision 嚴格遞增，相鄰 revision 差為 1。

記錄變更結果的滑動窗口由事件生成器統(tǒng)一從起點開始消費，取出的變更結果后會根據(jù)變更的 revision更新發(fā)號器的 commit index ，如果變更執(zhí)行成功，則還會構造出對應的修改事件，將并行地寫入事件緩存和分發(fā)到所有監(jiān)聽所創(chuàng)建出的通知隊列。

在元數(shù)據(jù)存儲系統(tǒng)中，需要監(jiān)聽指定邏輯時鐘即指定 revision 之后發(fā)生的所有修改事件，用于下游的緩存更新等操作，從而保證分布式系統(tǒng)的數(shù)據(jù)最終一致性。注冊監(jiān)聽時，需要傳入起始 revision 和過濾參數(shù)，過濾參數(shù)包括 key 前綴等等。

當客戶端發(fā)起監(jiān)聽時，服務端在建立事件流之后的處理，分成以下幾個主要步驟：

1. 處理監(jiān)聽注冊請求時首先創(chuàng)建通知隊列，將通知隊列注冊到事件生成組件中，獲取下發(fā)的新增事件；
2. 從事件緩存中拉取事件的 revision 大于等于給定要求 revision 所有事件到事件隊列中，并放到輸出隊列中，以此獲取歷史事件；
3. 將通知隊列中的事件取出，添加到輸出隊列中， revision 去重之后添加到輸出隊列；
4. 按照 revision 從小到大的順序，依次使用過濾器進行過濾；
5. 將過濾后符合客戶端要求的事件，通過事件流推送到元數(shù)據(jù)存儲系統(tǒng)外部的客戶端。

三. 落地效果

• 在 Benchmark 環(huán)境下，基于 ByteKV 的 KubeBrain 對比于 etcd 純寫場景吞吐提升 10 倍左右，延遲大幅度降低， PCT 50 降低至 1/6 ，PCT 90 降低至 1/20 ，PCT 99降低至 1/4 ；讀寫混合場景吞吐提升 4 倍左右；事件吞吐大約提升5倍；
• 在模擬 K8s Workload 的壓測環(huán)境中，配合 APIServer 側的優(yōu)化和調優(yōu)，支持 K8s 集群規(guī)模達到 5w Node 和 200w Pod；
• 在生產(chǎn)環(huán)境中，穩(wěn)定上量至 2.1w Node ，高峰期寫入超過 1.2w QPS，讀寫負載合計超過 1.8w QPS。

四. 未來演進

項目未來的演進計劃主要包括四個方面的工作：

• 探索實現(xiàn)多點寫入的方案以支持水平擴展 現(xiàn)在 KubeBrain 本質上還是一個單主寫入的系統(tǒng)，KubeBrain 后續(xù)會在水平擴展方面做進一步的探索，后續(xù)也會在社區(qū)中討論；
• 提升切主的恢復速度 當前切主會觸發(fā) API Server 側的 Re-list ，數(shù)據(jù)同步的開銷較大，我們會在這方面進一步做優(yōu)化；
• 實現(xiàn)內置存儲引擎 實現(xiàn)兩層存儲融合，由于現(xiàn)在在存儲引擎、KubeBrain 中存在兩層 MVCC 設計，整體讀寫放大較多，實現(xiàn)融合有助于降低讀寫放大，更進一步提高性能；
• 完善周邊組件 包括數(shù)據(jù)遷移工具、備份工具等等，幫助用戶更好地使用 KubeBrain 。

五. 關于我們

字節(jié)基礎架構編排調度團隊，負責構建字節(jié)跳動內部的容器云平臺，為產(chǎn)品線提供運行基石；以超大容器集群規(guī)模整體支撐了字節(jié)內產(chǎn)品線，涵蓋今日頭條、抖音、西瓜視頻等。

團隊支持業(yè)務同時覆蓋在線、離線機器學習，推薦/廣告/搜索等多種應用場景；在持續(xù)多年的超高速增長中，積累了豐富的 Kubernetes/容器超大規(guī)模應用經(jīng)驗，旨在打造覆蓋多場景，多地域的千萬級容器的大平臺。