etcdの限界を突破しましょう！ ByteDanceが自社開発したK8sストレージKubeBrain

背景

分散アプリケーション オーケストレーションおよびスケジューリング システムである Kubernetes は、クラウド ネイティブ アプリケーション基盤の事実上の標準となっていますが、公式の安定した運用規模は 5,000 ノードに制限されています。これはほとんどのアプリケーション シナリオには十分ですが、数百万のマシン ノードを備えた超大規模なアプリケーション シナリオでは、Kubernetes で安定したサポートを提供することは困難です。

特に「デジタル化」や「クラウドネイティブ」の発展により、世界のITインフラの規模はますます拡大しています。分散アプリケーション オーケストレーションおよびスケジューリング システムの場合、この傾向に適応するには 2 つの方法があります。

• 水平拡張: これは、複数のクラスターを構築および管理する機能であり、クラスター障害分離とハイブリッド クラウドの観点からより有利であり、主にクラスター フェデレーションによって実現されます。
• 垂直拡張: つまり、単一クラスターの規模を拡大することで、クラスターの運用および保守コストの削減、リソースの断片化の削減、全体的なリソース使用率の向上に有利になります。

K8s は集中型アーキテクチャを採用しています。すべてのコンポーネントは APIServer と対話し、APIServer はメタデータ ストレージ システムにクラスター メタデータを保持する必要があります。現在、APIServer でサポートされているメタデータ ストレージ システムは etcd のみです。単一クラスターのサイズが徐々に大きくなるにつれて、ストレージシステムの読み取りおよび書き込みスループットと総データ量は増加し続け、etcd は必然的に分散システム全体のボトルネックになります。

1.1 Kubernetes メタ情報ストレージの要件

APIServer は、一般的な強力な整合性を持つ KV データベースをメタデータ ストレージ システムとして直接使用することはできません。メタデータ ストレージ システムとのやり取りには、主に、完全および増分データ同期のリスト/監視、および単一の KV の読み取りと書き込みが含まれます。さらに一歩進んで、主に以下の側面が含まれます。

• バージョン管理に関しては、ストレージ システムはデータ バージョン情報を API サーバーに公開する必要があり、API サーバーはデータ バージョンに基づいて対応する ResourceVersion を生成します。
• 書き込み操作に関しては、ストレージ システムは、作成、更新、削除という 3 つのセマンティクスを持つ操作をサポートする必要があります。さらに重要なのは、ストレージ システムがデータの書き込みまたは削除時にデータ バージョン情報の CAS をサポートする必要があることです。
• 読み取り操作に関しては、ストレージ システムは、APIServer の WatchCache を埋めるため、またはクエリのためにストレージから全量のデータを取得するために、指定されたバージョンのスナップショット リストをサポートする必要があります。さらに、データを読み取る際に対応するデータバージョン情報の取得もサポートする必要があります。
• イベント監視の観点では、ストレージ システムは特定のバージョン以降の秩序ある変更をサポートする必要があります。このように、APIServer はリストを介してメタデータ ストレージから全量のデータを取得した後、スナップショット バージョン以降のすべての変更イベントを監視し、ウォッチ キャッシュを増分的に更新して変更を他のコンポーネントに配布できるため、各 K8s コンポーネントのデータの最終的な一貫性が保証されます。

1.2 etcdの実装とボトルネック

etcd は本質的に、マスター スレーブ アーキテクチャを備えた、一貫性と可用性に優れた分散 KV ストレージ システムです。

• ノードは Raft プロトコルを通じて選出され、操作はログに抽象化されます。 Raft ベースのログ同期メカニズムは、複数のステート マシン上で同期されます。
• 単一ノードでは、ログがステートマシンに順番に適用され、boltdb に基づいて状態の永続化が実行されます。

APIServer メタデータ ストレージ要件については、etcd は通常、次の方法で実装します。

• バージョン管理に関しては、etcd は Revision を論理クロックとして使用します。変更操作ごとに、バージョン管理のために増分バージョン番号 Revision が割り当てられます。さらに、Key から Revision までのインデックスは、TreeIndex を通じてメモリ内で管理されます。
• 書き込み操作に関しては、etcd は、Revision をキーとして、Key/Value/Lease データを BoltDB に保存される値として使用して、シリアル Apply Raft Log 方式で実装します。これに基づいて、CAS for Revision をサポートする書き込みトランザクションを実装します。
• 読み取り操作に関しては、etcd はキーからリビジョンまでの TreeIndex を管理してリビジョンを照会し、次に値を照会し、これに基づいてスナップショットの読み取りを実装します。
• イベント監視に関しては、BoltDB 内の指定されたリビジョンから KV データを変換することで履歴イベントを取得できますが、新しいイベントは書き込み操作と同期して通知によって取得されます。

etcd は、K8s 専用に設計されたメタデータ ストレージ システムではありません。提供される機能は、K8s に必要な機能のスーパーセットです。使用中に発生する主な問題は次のとおりです。

• etcd のネットワーク インターフェイス層は電流制限機能が弱く、雪崩が発生した場合の自己修復機能も不十分です。
• etcd は単一の raft グループを使用しますが、これにはボトルネックのポイントが 1 つあります。単一のラフト グループ内のノード数を増やすと、フォールト トレランスは向上しますが、書き込みパフォーマンスは向上しません。
• etcd の ExpensiveRead は簡単に OOM を引き起こす可能性があります。ページング読み取りを使用すると、レイテンシが相対的に増加します。
• BoltDB のシリアル書き込みは書き込みパフォーマンスを制限し、高負荷時には書き込みレイテンシが大幅に増加します。
• 長期運用では、断片化の問題により書き込みパフォーマンスが低下する傾向があります。オンライン クラスターはデフラグによって定期的にデータを最適化しますが、これはより複雑であり、可用性にも影響する可能性があります。

2. 新しいメタデータストレージ

これまで、実稼働環境での etcd のパフォーマンスの問題は、ストレージをリソースごとに分割し、etcd パラメータを最適化することによってのみ、ある程度軽減できました。しかし、K8s の適用範囲が広がることで生じる課題に直面し、上位レベルのビジネスをより強力にサポートするために、etcd に代わるより高性能なメタデータ ストレージ システムが緊急に必要になっています。

K8s クラスターと関連するオープンソース プロジェクトのニーズを調査した後、k3s のオープンソース プロジェクト kine のアイデアを借用し、分散 KV ストレージ エンジンである KubeBrain に基づく高性能 K8s メタデータ ストレージ プロジェクトを設計および実装しました。

KubeBrain システムは、APIServer で使用されるメタデータ ストレージ API を実装します。全体的にマスタースレーブアーキテクチャを採用しています。マスターノードは書き込み操作とイベント配信の処理を担当し、スレーブノードは読み取り操作の処理を担当します。マスター ノードとスレーブ ノードは、データの読み取りと書き込みが行われる分散型の強力な一貫性のある KV ストレージを共有します。以下では、KubeBrain のコア モジュールを紹介します。

2.1 ストレージエンジン

KubeBrain は、ロジック層で使用される KeyValue ストレージ エンジン インターフェイスを均一に抽象化します。これに基づいて、プロジェクトはコアロジックと基礎となるストレージエンジンの分離を実現します。

• ロジック層は、ストレージ エンジン インターフェイスに基づいて基礎となるデータを操作し、基礎となる実装については考慮しません。
• 新しいストレージ エンジンに接続するには、対応する適応レイヤーを実装してストレージ インターフェイスを実現するだけです。

現在、プロジェクトでは ByteKV と TiKV への適応を実装しています。さらに、テスト用にスタンドアロン ストレージ Badger に適合したバージョンも実装されています。すべての KV ストレージが KubeBrain のストレージ エンジンとして使用できるわけではないことに注意してください。現在、KubeBrain のストレージ エンジンには次の機能要件があります。

• スナップショット読み取りをサポート
• 双方向トラバーサルをサポート
• CAS機能による読み取り/書き込みトランザクションまたは書き込みトランザクションをサポート
• 論理クロックを外部に公開する

さらに、KubeBrain が上位層に提供する一貫性の保証はストレージ エンジンの一貫性の保証に依存するため、KubeBrain では、ストレージ エンジンのトランザクションが次のレベルに到達する必要があります (HAT で定義されています: http://www.vldb.org/pvldb/vol7/p181-bailis.pdf)。

• 分離保証: スナップショット分離
• セッション保証: 線形化可能

内部の運用環境では、KubeBrain はメタデータ ストレージ サービスを提供するためにストレージ エンジンとして ByteKV を使用します。 ByteKV は、強力な一貫性を備えた分散 KV ストレージです。 ByteKV では、データはキーに従って辞書順に保存されます。単一のパーティションのデータ サイズがしきい値を超えると、パーティションは自動的に分割され、マルチ ラフト グループを通じて水平方向に拡張できるようになります。また、分割しきい値の構成と分割境界選択ルールのカスタマイズもサポートしています。さらに、ByteKV はグローバル クロックを公開し、書き込みトランザクションとスナップショット読み取りをサポートし、非常に高い読み取りおよび書き込みパフォーマンスと強力な一貫性保証を提供します。

2.2 リーダー選出メカニズム

KubeBrain は、基盤となる強力な一貫性を備えた分散 KV ストレージ エンジンに基づいており、ストレージ エンジン内の特定の KeyValue セットを指す ResourceLock をカプセル化して実装します。 ResourceLock には、マスター ノードのアドレスやリースの期間などの情報が含まれています。

KubeBrain プロセスが開始されると、プロセスはスレーブ ノードとして初期化され、バックグラウンドで自動的に選挙を実行します。キャンペーンを行うときは、まず現在の ResourceLock を読み取ってみてください。現在の ResourceLock が空であることが判明した場合、または ResourceLock のリースが期限切れになっている場合、ノードは CAS モードで自身のアドレスとリース期間を ResourceLock に書き込もうとします。書き込みが成功すると、マスター ノードに昇格されます。

スレーブノードは、ResourceLock を通じてマスターノードのアドレスを読み取ることで、マスターノードとの接続を確立し、必要な通信を実行できますが、マスターノードはスレーブノードの存在を認識しません。スレーブ ノードがなくても、単一の KubeBrain マスター ノードで完全な APIServer に必要な API を提供できますが、マスター ノードがダウンすると可用性が低下します。

2.3 論理クロック

KubeBrain は、バージョン管理にリビジョンの概念を導入している点で etcd に似ています。 KubeBrain クラスターの ID はマスター ノードでのみ起動されます。スレーブ ノードがマスター ノードに昇格すると、ストレージ エンジンによって提供される論理クロック インターフェイスに基づいて初期化され、ジェネレーターのリビジョンの初期値がストレージ エンジンから取得された論理タイムスタンプに割り当てられます。

単一のリーダーの任期中、数値ジェネレータによって発行される整数は単調かつ継続的に増加します。マスターノードに障害が発生すると、スレーブノードが引き継いで初期化プロセスを繰り返します。マスター ノードの番号は継続的に増加し、ストレージ エンジンの論理タイムスタンプは不連続になる可能性があるため、その増加率は連続番号ジェネレーターの増加率よりもはるかに速くなります。したがって、マスター ノードが切り替えられた後も、リビジョンが引き続き増加することが保証されます。古いマスター ノードのジェネレータによって割り当てられる最大リビジョンは、新しいマスター ノードのジェネレータによって割り当てられる最小リビジョンよりも小さくなります。

KubeBrain マスター ノードで番号を発行することは、非常に高いパフォーマンスを備えた純粋なメモリ操作です。 KubeBrain の書き込み操作はマスター ノード上で完了するため、書き込み操作のリビジョンを割り当てるときにネットワーク転送は必要ありません。したがって、この高性能な発行者は、書き込み操作のパフォーマンスを最適化するのにも非常に役立ちます。

2.4 データモデル

KubeBrain は、API サーバーの読み取りおよび書き込み要求パラメータ内の Raw Key を 2 種類の内部キーにエンコードし、ストレージ エンジンのインデックスとデータに書き込みます。各 Raw Key に対して、インデックス リビジョン キー レコードには 1 つのレコードのみがあり、現在の Raw Key の最新バージョン番号が記録されます。リビジョン キーもロックです。 Raw Key に対する各更新操作には、インデックスに対する CAS が必要です。データ レコード オブジェクト キーには 1 つ以上のレコードがあり、各レコードには Raw キーの履歴バージョンとバージョンに対応する値が記録されます。オブジェクト キーのエンコード方法は、magic+raw_key+split_key+revision です。ここで、

• マジック値は \x57\xfb\x80\x8b です。
• raw_key は、API サーバーが実際にストレージ システムに入力するキーです。
• split_key は $ です。
• リビジョンは、論理クロックによって書き込み操作に割り当てられる論理操作シーケンス番号であり、BigEndian を使用してバイトにエンコードされます。

• Kubernetes の検証ルールによると、raw_key には小文字、数字、'-'、'.' のみを含めることができるため、現在は $ 記号として split_key が選択されています。

特に、リビジョン キーのエンコード方法はオブジェクト キーと同じであり、リビジョンは長さ 8 の空のバイトです。このエンコード方式により、エンコード前後の比較関係が変更されないことが保証されます。

ストレージ エンジンでは、同じ Raw キーから生成されたすべての内部キーが連続した範囲内に収まります。

このエンコード方法には次の利点があります。

• エンコードは可逆的です。つまり、InternalKey は Encode(RawKey,Revision) で取得でき、Rawkey と Revision は Decode(InternalKey) で取得できます。
• ストレージ エンジン内ですべての Kubernetes オブジェクト データをキー値データに変換します。各オブジェクト データには、最新のバージョン番号を記録するための一意のインデックスがあり、インデックスを通じてロック操作を実装します。
• 行またはインデックスに対応するキー、または隣接する行または隣接するインデックス値のブロックに対応するキー範囲を簡単に構築できます。
• キーの形式は非単調増加であるため、ストレージ エンジン内のキーの増加によって発生するホットスポット書き込みの問題を回避できます。

2.5 データの書き込み

各書き込み操作には発行者によって一意の書き込みリビジョンが割り当てられ、同時にストレージ エンジンに書き込まれます。 Kubernetes オブジェクトデータを作成、更新、削除する場合、オブジェクトに対応するインデックスとデータを同時に操作する必要があります。インデックスとデータは基礎となるストレージ エンジン内で異なるキーと値のペアであるため、更新プロセスのアトミック性を保証するには書き込みトランザクションが必要であり、少なくともスナップショット分離が必要です。

同時に、KubeBrain は同時実行制御のための楽観的ロックを実装するためにインデックスに依存しています。書き込み時に、KubeBrain はまず、APIServer によって入力された RawKey と発行者によって割り当てられたリビジョンに基づいて、ストレージ エンジンで実際に必要なリビジョン キーとオブジェクト キー、およびリビジョン キーに書き込むリビジョン バイトを構築します。書き込みトランザクション中は、まずインデックス リビジョン キーがチェックされます。チェックが成功すると、インデックス リビジョン キーが更新されます。操作が成功すると、データ オブジェクト キーが挿入されます。

• 作成リクエストを実行するときに、リビジョン キーが存在しない場合は、リビジョン バイトがリビジョン キーに書き込まれ、次に API サーバーによって書き込まれた値がオブジェクト キーに書き込まれます。
• 更新リクエストを実行すると、リビジョン キーに格納されている古いリビジョン バイトが期待どおりである場合にのみ新しいリビジョン バイトが書き込まれ、その後、API サーバーによって書き込まれた値がオブジェクト キーに書き込まれます。
• 削除要求を実行すると、リビジョン キーに保存されている古いリビジョン バイトが期待どおりであれば、新しいリビジョン バイトに削除マーカーが書き込まれ、その後、オブジェクト キーにトゥームストーンが書き込まれます。

データの書き込み時に増分リビジョンに基づいて新しい KeyValue が継続的に書き込まれるため、KubeBrain はバックグラウンドのガベージ コレクション操作を実行して古いリビジョンのデータを削除し、データ量の無制限な増加を回避します。

2.6 データの読み取り

データの読み取りは、ポイント読み取り操作と範囲クエリ操作に分かれており、それぞれ API サーバーの Get 操作と List 操作に対応します。

Get では、読み取り操作の ReadRevision を指定する必要があります。最新の値を読み取る必要がある場合は、ReadRevision を最大値 MaxUint64 に設定します。開始点が Encode(RawKey, ReadRevision) である Iterator を構築し、Encode(RawKey, 0) まで走査して最初のものを取得します。

範囲クエリでは、読み取り操作の ReadRevision を指定する必要があります。範囲検索の RawKey 境界 [RawKeyStart、RawKeyEnd) 間隔については、KubeBrain はストレージ エンジンの Iterator スナップショット読み取りを構築し、エンコードを通じて RawKey 間隔をストレージ エンジンの InternalKey データ間隔にマッピングします。

• InternalKeyの上限InternalKeyStartはEncode(RawKeyStart, 0)です
• InternalKeyの下限はInternalKeyEndで、Encode(RawKeyEnd, MaxRevision)です。

ストレージ エンジン内の [InternalKeyStart、InternalKeyEnd) 内のすべてのデータが順番に走査され、Decode(InternalKey) を通じて RawKey と Revision が取得されます。同じ RawKey を持つすべての ObjectKey について、条件 Revision<=ReadRevision を満たすサブセットから Revision が最大のものが取得され、パブリックに返されます。 2.7 イベントメカニズム

すべての変更操作では、TSO によって連続した一意のリビジョンが割り当てられ、同時にストレージ エンジンに書き込まれます。変更操作がストレージ エンジンに書き込まれた後、書き込みが成功したか失敗したかに関係なく、変更結果は小さいリビジョンから大きいリビジョンの順にスライディング ウィンドウに送信されます。変更結果には、変更タイプ、バージョン、キー、値、および書き込みが成功したかどうかが含まれます。変更結果を記録するスライディング ウィンドウでは、開始点から終了点まで、すべての変更データのリビジョンが厳密に増加し、隣接するリビジョン間の差は 1 です。

変更結果を記録するスライディング ウィンドウは、開始点からイベント ジェネレーターによって均一に消費されます。変更結果が取り出された後、変更されたリビジョンに応じて発行者のコミットインデックスが更新されます。変更が正常に実行されると、対応する変更イベントが構築され、イベント キャッシュに書き込まれ、すべてのリスナーによって作成された通知キューに並列に配信されます。

メタデータ ストレージ システムでは、分散システム内のデータの最終的な一貫性を確保するために、下流のキャッシュ更新やその他の操作について、指定された論理クロック (指定されたリビジョン) 以降に発生するすべての変更イベントを監視する必要があります。リスナーを登録するときは、キープレフィックスなどを含む開始リビジョンとフィルターパラメータを渡す必要があります。

クライアントが監視を開始すると、イベント ストリームを確立した後のサーバーの処理は、次の主なステップに分かれます。

1. リスナー登録要求を処理するときは、まず通知キューを作成し、その通知キューをイベント生成コンポーネントに登録して、新しく発行されたイベントを取得します。
2. 指定されたリビジョン以上のリビジョンを持つすべてのイベントをイベント キャッシュからイベント キューにプルし、出力キューに入れて履歴イベントを取得します。
3. 通知キュー内のイベントを取り出し、出力キューに追加します。リビジョンを削除し、出力キューに追加します。
4. フィルターを使用して、リビジョンの小さい順から大きい順にフィルターします。
5. クライアントの要件を満たすフィルタリングされたイベントは、イベント ストリームを通じてメタデータ ストレージ システムの外部のクライアントにプッシュされます。

3. 着陸効果

• ベンチマーク環境では、ByteKV ベースの KubeBrain のスループットは、純粋な書き込みシナリオでは etcd と比較して約 10 倍向上し、レイテンシが大幅に削減されています。 PCT 50 は 1/6 に、PCT 90 は 1/20 に、PCT 99 は 1/4 に削減されます。読み取りと書き込みが混在するシナリオのスループットが約 4 倍に増加します。イベントのスループットが約 5 倍に増加します。
• K8s ワークロードをシミュレートするストレス テスト環境では、APIServer 側の最適化とチューニングにより、K8s クラスターの規模は 50,000 ノードと 200 万ポッドに達する可能性があります。
• 実稼働環境では、容量は着実に 21,000 ノードまで増加し、ピーク時の書き込みは 12,000 QPS を超え、読み取りと書き込みを合わせた負荷は 18,000 QPS を超えています。

IV.将来の進化

プロジェクトの将来の発展計画には、主に次の 4 つの作業側面が含まれます。

• 水平方向の拡張をサポートするためにマルチポイント書き込みを実装するためのソリューションを検討します。現在、KubeBrain は基本的に単一マスターの書き込みシステムです。 KubeBrain は水平方向の拡張をさらに検討し、後ほどコミュニティで議論する予定です。
• マスター切り替えの回復速度を向上します。現在、マスターの切り替えにより API サーバー側で再リストがトリガーされ、大きなデータ同期オーバーヘッドが発生します。この点についてはさらに最適化していきます。
• 内蔵ストレージ エンジンを使用して 2 層ストレージ フュージョンを実装します。ストレージ エンジンと KubeBrain には 2 層の MVCC 設計があるため、全体的な読み取り/書き込み増幅が高くなります。 Fusion は、読み取り/書き込み増幅を削減し、パフォーマンスをさらに向上させます。
• データ移行ツール、バックアップ ツールなどの周辺コンポーネントを改善し、ユーザーが KubeBrain をより使いやすくします。

V. 当社について

ByteDance のインフラストラクチャ オーケストレーションおよびスケジューリング チームは、ByteDance の内部コンテナ クラウド プラットフォームの構築を担当し、製品ラインの運用基盤を提供します。超大規模なコンテナ クラスター スケールを使用して、Toutiao、Douyin、Xigua Video などを含む ByteDance の製品ライン全体をサポートします。

チームは、オンラインおよびオフラインの機械学習、推奨/広​​告/検索、その他のアプリケーション シナリオをカバーするビジネスをサポートします。超高速成長の数年間で、Kubernetes/コンテナの大規模アプリケーションにおける豊富な経験を蓄積し、複数のシナリオとリージョンをカバーする数千万のコンテナを備えた大規模プラットフォームの構築を目指しています。