|
この記事では、ByteDance のインフラストラクチャ オーケストレーションおよびスケジューリング チームが世界最高峰のクラウド コンピューティング カンファレンス SOCC 2023 で発表した論文「Gödel: Bytedance における統合大規模リソース管理およびスケジューリング」を解説します。 論文リンク: dl.acm.org/doi/proceedings/10.1145/3620678 本稿では、ByteDanceが提案するKubernetesベースの高スループットタスクスケジューリングシステムを紹介します。このシステムは、オンラインタスクとオフラインタスクの混在展開をサポートします。大規模データセンターにおける各種タスクのリソース割り当て問題を効果的に解決し、データセンターのリソース利用率、弾力性、スケジューリングスループットを向上させることを目指しています。 現在、このスケジューリングシステムは、数万ノード規模の超大規模クラスターの管理をサポートし、マイクロサービス、バッチ処理、ストリーミングタスク、AIなど、様々なタスクタイプに対応するリソースプーリング機能を提供しています。2022年からByteDance内の様々なデータセンターに大規模導入が進められており、Gödelスケジューラはピーク時にCPU使用率60%以上、 GPU使用率95%以上を実現し、ピーク時のスケジューリングスループットは5,000ポッド/秒に迫ることが実証されています。 導入ここ数年、ByteDanceの各事業ラインが急速に発展するにつれ、社内の事業の種類も多様化し、マイクロサービス、プロモーション検索（レコメンデーション/広告/検索）、ビッグデータ、機械学習、ストレージなどの事業が急速に拡大し、それに必要なコンピューティングリソースの量も驚異的な速度で増加しています。 創業当初、ByteDanceのオンライン事業とオフライン事業はそれぞれ独立したリソースプールを持ち、それぞれ個別に管理されていました。主要な祝日やイベント期間中のオンライン事業からのリクエストの爆発的な増加に対応するため、インフラチームは事前にコンティンジェンシープランを準備し、オフライン事業からオンライン事業のリソースプールにリソースの一部を移行する必要がありました。この方法は緊急のニーズに対応できる一方で、異なるプール間のリソース移行プロセスは時間がかかり、複雑で、非効率的でした。さらに、独立したリソースプールでは、オフライン事業間でのリソースの相互展開に高いコストがかかり、リソース利用率の向上には限界がありました。 この課題に対処するため、本論文ではオンラインとオフラインを統合したスケジューラであるGödelを提案します。Gödelは、単一のスケジューラを用いてオンラインとオフラインのサービスを統一的にスケジュール・管理し、リソースプールを実現することを目的としています。これにより、リソースの利用率と弾力性を向上させながら、ビジネスコストとユーザーエクスペリエンスを最適化し、運用負荷を軽減します。KubernetesプラットフォームをベースとするGödelは、Kubernetesのネイティブスケジューラをシームレスに置き換えることができ、Kubernetesネイティブスケジューラだけでなく、コミュニティ内の他のスケジューラよりもパフォーマンスと機能の面で優れています。 エンジンを始動するByteDanceは数十基の大規模なマルチクラスタデータセンターを運用しており、毎日数千万ものコンテナ化されたタスクが作成・削除されています。夜間のピーク時には、単一クラスタの平均タスクスループットが1,000ポッド/秒を超えます。これらのタスクは、ビジネス上の優先度、動作モード、リソース要件がそれぞれ異なります。これらのタスクを効率的かつ合理的にスケジュールし、高優先度タスクのSLAを確保しながら、様々なタスクのリソース要件を満たし、高いリソース利用率と弾力性を維持することは、非常に困難な課題です。 調査の結果、コミュニティで一般的に使用されているクラスタ スケジューラは、ByteDance の要件を十分に満たすことができないことが判明しました。
そのため、ByteDanceはKubernetesとYARNの利点を組み合わせ、リソースプールを接続し、あらゆる業務の管理を統合するスケジューラの開発を目指しています。上記の議論に基づき、このスケジューラには以下の特性が期待されます。
クラスター内のすべてのコンピューティングリソースは可視化され、様々なオンラインおよびオフラインタスクに割り当てることができます。これにより、リソースの断片化が軽減され、クラスターの運用・保守コストも削減されます。
クラスターレベルとノードレベルの両方でさまざまなタイプと優先順位のタスクを調整することで、クラスターリソースの利用率を向上させることができます。
クラスターレベルおよびノードレベルでは、優先度の異なるサービス間でコンピューティングリソースを柔軟かつ迅速に転送できます。リソース利用率を向上させると同時に、高優先度サービスへのリソースの優先割り当てとSLAが常に保証されます。
ネイティブ Kubernetes スケジューラやコミュニティ開発の Volcano スケジューラと比較すると、オンライン アプリケーションとオフライン アプリケーションの両方のスケジューリング スループットが大幅に向上し、1 秒あたり 1,000 ポッドを超えるビジネス要件を満たします。
候補ノードのリソース マイクロトポロジは、kubelet が承認するときではなく、スケジュールの決定を行うときに識別され、ビジネス ニーズに基づいて適切なノードがスケジュール用に選択されます。 ゲーデル入門Gödel Schedulerは、Kubernetesクラスター環境向けの分散スケジューラであり、オンラインサービスとオフラインサービスを均一にスケジュールできます。オフラインサービスの機能要件とパフォーマンス要件を満たしながら、優れたスケーラビリティとスケジューリング品質を提供します。 下の図に示すように、Gödel Scheduler はネイティブ Kubernetes スケジューラと同様の構造を持ち、Dispatcher、Scheduler、Binder の 3 つのコンポーネントで構成されています。Gödel Scheduler との違いは、大規模なクラスターをサポートし、より高いスケジューリングスループットを実現するために、Scheduler コンポーネントは楽観的同時実行スケジューリングを採用し、複数のインスタンスとして実行できるのに対し、Dispatcher と Binder は単一のインスタンスとして実行される点です。 コアコンポーネントディスパッチャはスケジューリングプロセス全体のエントリポイントであり、主にタスクのキューイング、タスクの分配、ノードのパーティショニングを担います。ディスパッチャは主に、ソートポリシーマネージャ、ディスパッチポリシーマネージャ、ノードシャッフラー、スケジューラメンテナーといった複数の部分から構成されます。
スケジューラはディスパッチャからタスクリクエストを受け取り、タスクの具体的なスケジューリングとプリエンプションの決定を行いますが、実際にタスクを実行するわけではありません。ネイティブKubernetesスケジューラと同様に、Gödelのスケジューラも、以下の2つのプラグインを使用して要件を満たすノードを検索するなど、様々な段階で一連のプラグインを通じてスケジューリングの決定を行います。
Kubernetes のネイティブ スケジューラとは異なり、Gödel のスケジューラでは複数のインスタンスにまたがる分散操作が可能です。非常に大規模なクラスターや高スループットが求められるシナリオでは、ニーズに合わせて複数のスケジューラ インスタンスを構成できます。この場合、各スケジューラ インスタンスは独立して並列にスケジューリングを実行します。ノードを選択する際には、所属するパーティションからの選択を優先します。これによりパフォーマンスは向上しますが、ローカルな最適性のみが保証されます。ローカル パーティションに適切なノードがない場合は、他のインスタンスのパーティションからノードを選択します。ただし、これにより複数のスケジューラ インスタンスが同時に同じノードを選択するなど、競合が発生する可能性があります。スケジューラ インスタンスの数が多いほど、競合の可能性が高くなります。したがって、インスタンスの数は適切に設定する必要があります。多ければ多いほど良いとは限りません。 さらに、オンラインタスクとオフラインタスクの両方をサポートするために、Gödel Scheduler は2段階のスケジューリングセマンティクスを採用し、Podグループやレプリカセットなどのビジネスデプロイメントを表すスケジューリングユニットと、Podを表す実行ユニットの両方をサポートします。具体的な使用方法については後ほど説明します。 Binder は主に、楽観的な競合チェック、プリエンプション操作の実行、タスク バインディングの準備 (ストレージ ボリュームの動的作成など)、そして最後にバインディング操作の実行を担当します。一般的に、そのワークフローは Kubernetes の Binder と似ていますが、Gödel では、Binder は複数の Scheduler インスタンスによって発生するより多くの競合を処理します。競合が検出されると、すぐに拒否され、再スケジュールされます。プリエンプション操作の場合、Binder は複数の Scheduler インスタンスが同じインスタンス (つまり、Victim Pod) をプリエンプトしようとしているかどうかを確認します。このような問題が存在する場合、Binder は最初のプリエンプションのみを処理し、残りの Scheduler インスタンスからのプリエンプション要求を拒否します。Gang/Co-scheduling の場合、Binder は Pod グループ内のすべての Pod (存在する場合) の競合を処理する必要があります。すべての Pod の競合が解決され、各 Pod が個別にバインドされるか、Pod グループ全体のスケジュールが拒否されます。 CNRはCustom Node Resourceの略で、ByteDanceがリアルタイムノード情報を補完するために作成したCRDです。Gödel Scheduler自体の一部ではありませんが、Gödelのスケジューリングセマンティクスを強化します。このCRDは、ノードのリソース量と状態だけでなく、デュアルソケットノードの各ソケットのCPU/メモリ消費量や残りリソースといったマイクロトポロジも定義します。これにより、スケジューラはマイクロトポロジのアフィニティ要件を持つタスクをスケジュールする際に、CNRに記述されたノード状態に基づいて適切なノードをフィルタリングできます。 トポロジーマネージャーのみを使用するネイティブKubernetesと比較して、CNRを使用すると、トポロジー制限を満たさないノードにPodをスケジュールする際にkubeletが遭遇するスケジューリングエラーを回避できます。ノード上にPodが正常に作成されると、Katalystに属するノードエージェントによってCNRが更新されます。
2段階スケジューリングByteDanceがGödelを設計した際、主な目標はオンラインサービスとオフラインサービスの両方のスケジューリングニーズを同時に満たすことでした。これを実現するために、Gödelはスケジューリングユニットと実行ユニットという2層のスケジューリングセマンティクスを導入しました。 前者はデプロイされたジョブに対応し、1つ以上の実行ユニットで構成されます。例えば、ユーザーがKubernetes Deploymentを介してジョブをデプロイすると、このジョブはスケジューリングユニットにマッピングされ、タスクを実行している各ポッドは実行ユニットに対応します。ポッドを直接対象とするネイティブKubernetesスケジューリングとは異なり、Gödelの2レベルスケジューリングフレームワークは常にスケジューリングユニットの全体的な状態を承認原則として使用します。スケジューリングユニットがスケジュール可能と判断された場合にのみ、それに含まれる実行ユニット（つまりポッド）が順番にスケジュールされます。 スケジューリングユニットがスケジュール可能かどうかを判断するルールは、実行ユニット数がMin_Member以上でスケジューリング条件を満たすことです。つまり、スケジューラはジョブに必要な数のPodを配置するためのリソース要件を満たすノードを見つけることができるということです。この場合、各Podは指定されたノードに順番にスケジュールされます。そうでない場合、どのPodもスケジュールされず、ジョブのデプロイメント全体が拒否されます。 ご覧のとおり、スケジューリングユニットのMin_Memberは非常に重要なパラメータです。Min_Memberの値を変更することで、さまざまなシナリオのニーズに対応できます。Min_Memberの値の範囲は[1, 実行ユニット数]です。 例えば、マイクロサービス指向のビジネスロジックを扱う場合、Min_Memberは1に設定されます。各スケジューリングユニット内の少なくとも1つの実行ユニット/ポッドのリソース要求が満たされる限り、スケジューリングは続行されます。この場合、GödelスケジューラはネイティブKubernetesスケジューラと基本的に同じように動作します。 バッチ処理やオフライントレーニングなど、ギャングセマンティクスを必要とするオフラインアプリケーションを扱う場合、Min_Memberの値は実行ユニット/ポッドの数と等しくなります（一部のアプリケーションでは、実際のニーズに応じて、1から実行ユニットの数までの値に調整できます）。スケジューリングは、すべてのポッドがリソース要求を満たすことができる場合にのみ開始されます。Min_Memberの値は、アプリケーションのタイプとアプリケーションデプロイメントテンプレートのパラメータに基づいて自動的に設定されます。 パフォーマンスの最適化ByteDance自身のビジネスニーズにより、スケジューリングスループットに対する要件は非常に高くなっています。Gödelの設計目標の一つは、高いスループットを提供することです。このため、Gödelスケジューラは、最も時間のかかるフィルタリングノード部分を、同時実行可能なマルチインスタンススケジューラに配置しています。一方で、複数のインスタンスは競合が発生する可能性があるため、スケジューラインスタンスの数は必ずしも多いほど良いとは限りません。また、複数インスタンスによるパフォーマンス向上だけでは、単一のByteDanceクラスタのピーク時に1000～2000ポッド/秒というスループット要件を満たすには不十分です。スケジューリング効率をさらに向上させるために、Gödelは以下の側面でさらなる最適化を行いました。
ノード選択プロセスにおいて、フィルタリングと優先順位付けは最も時間のかかる2つの部分です。前者はリソース要求に基づいて利用可能なノードをフィルタリングし、後者は候補ノードにスコアを付けて最適なノードを見つけます。これら2つの部分の速度を改善できれば、スケジューリングサイクル全体を大幅に短縮できます。 ByteDance の開発チームは、コンピューティング リソースが異なるビジネス ユニットの異なるアプリケーションによって使用されているにもかかわらず、特定のビジネス ユーザーの特定のアプリケーションの Pod のすべてまたはほとんどには通常、同じリソース要件があることに気付きました。
これらの多数のタスクのうち、ほとんどのPodは、リソース要求、ネットワークセグメント、デバイスアフィニティ要件が類似しています。そのため、フィルタープラグインによって選択された候補ノードのうち、最初のPodの要件を満たすものは、同じタスク内の他のPodの要件も満たす可能性が非常に高くなります。 そのため、Gödelスケジューラは最初のPodをスケジュールした後、候補ノードをキャッシュし、次のスケジュールラウンドでキャッシュから利用可能なノードを優先的に検索します。クラスターの状態が変化した場合（ノードが追加または削除された場合）、またはリソース要件が異なるPodに遭遇した場合を除いて、毎ラウンドクラスター内のノードを再スキャンする必要はありません。スケジュール中に利用可能なリソースがないノードはキャッシュから削除され、その順序はクラスターの状態に応じて調整されます。この最適化により、ノード選択プロセスが大幅に改善されます。理想的には、同じビジネスユーザーのPodグループをスケジュールする場合、時間計算量はO(n)からO(1)に削減されます。
上記の最適化により候補ノードの構築プロセスを削減できますが、クラスターのステータスまたはリソース要求が変更された場合は、クラスター内のすべてのノードを再スキャンする必要があります。 時間オーバーヘッドをさらに削減するために、Gödelは候補リストのスキャン比率を調整し、局所最適解を大域最適解の近似値として用います。スケジューリングプロセスでは、すべての実行ユニット/ポッドに対して十分な候補ノードを見つける必要があるため、Gödelは少なくとも実行ユニット数で指定されたノードをスキャンします。履歴データ分析に基づき、Gödelはデフォルトで実行ユニット数+50ノードをスキャンして候補ノードを見つけます。適切なノードが見つからない場合は、同じ数のノードを再度スキャンします。この手法と候補ノードのキャッシュを組み合わせることで、スケジューラがポッドに適したノードを見つける際の時間オーバーヘッドを大幅に削減します。
上記の 2 つの最適化に加えて、Gödel スケジューラはデータ構造とアルゴリズムも継続的に最適化します。 候補ノードリストを低コストで維持し、ノードリストを頻繁に再構築するオーバーヘッドを回避するために、GödelはネイティブKubernetesスケジューラのNodeListメンテナンス機構をリファクタリングしました。ノードリストを離散化することで、超大規模本番クラスターで発生していたパフォーマンス問題を解決し、より低いオーバーヘッドでより優れたノード離散化結果を実現しました。 ByteDanceは、全体的なリソース利用率を向上させるため、高優先度のオンラインタスクと低優先度のオフラインタスクを混在させて配置しています。ビジネスオペレーションの潮汐特性により、夕方のピーク時には多数のオンラインサービスが復帰するため、低優先度のオフラインサービスを頻繁にプリエンプションする必要が生じます。プリエンプション処理には膨大な検索計算が必要であり、頻繁なプリエンプションはスケジューラ全体の効率に深刻な影響を与えます。この問題に対処するため、Gödelスケジューラはポッドとノードに基づく多次元プルーニング戦略を導入し、プリエンプションスループットを迅速に回復させ、プリエンプションのレイテンシを大幅に削減します。 実験結果この論文では、スケジューリング スループット、クラスター サイズ、その他の側面から Gödel スケジューラのパフォーマンスを評価します。 まず、マイクロサービスビジネスにおいて、ByteDanceはGödel（単一インスタンス）とネイティブKubernetesスケジューラを比較しました。クラスタのスケールに関しては、ネイティブスケジューラの方が… Kubernetesはデフォルトで最大5,000ノードのクラスターをサポートし、最大スケジューリングスループットは200 Pod/s未満です。ByteDanceのオープンソースの高性能キーバリューストアであるKubeBrainを使用することで、ネイティブKubernetesははるかに大規模なクラスターをサポートできるようになり、スケジューリングスループットが大幅に向上します。しかし、Kubernetes + KubeBrainの組み合わせのパフォーマンスは、Gödelには依然として大きく劣ります。Gödelは5,000ノードのクラスターで2,600 Pod/sを達成し、20,000ノードでも約2,000 Pod/sを達成しており、これはネイティブKubernetesスケジューラの10倍以上の速度です。 Gödel は、より高いスケジューリングスループットを実現するために、複数のインスタンスを実行できます。下の右の図は、10,000ノードのクラスターで1～6個のスケジューラインスタンスを順次実行している様子を示しています。最初はスループットが徐々に向上し、ピーク時には約4,600 Pod/sに達します。しかし、インスタンス数が5を超えるとパフォーマンスが低下します。これは、インスタンス数が増えると競合が増加し、スケジューリング効率に影響が出るためです。したがって、スケジューリングインスタンスの数が多いほど必ずしも良いとは限りません。 ギャングセマンティクスを必要とするオフラインタスクについて、この論文ではGödelを、オープンソースコミュニティで広く使用されているYARNおよびKubernetes（K8s-volcano）と比較しています。GödelのパフォーマンスはK8s-volcanoよりも大幅に優れているだけでなく、YARNのほぼ2倍であることが明らかです。Gödelはオンラインタスクとオフラインタスクの同時スケジューリングをサポートしています。この論文では、システムに送信するオフラインタスクの割合を変化させることで、異なるビジネスプロセスが混在するシナリオをシミュレートしています。オフラインタスクの割合に関わらず、Gödelのパフォーマンスは比較的安定しており、スループットは約2,000 Pods/sを維持していることがわかります。 Gödelがなぜこれほど大幅な性能向上を達成したのかを示すため、本論文では2つの主要な最適化、「候補ノードのキャッシュ」と「スキャン率の低減」の寄与に焦点を当てています。下図に示すように、これまでの実験を、Gödelのフルバージョン、ノードキャッシュ最適化のみを有効にしたGödel、そしてスキャン率低減のみを有効にしたGödelを用いて繰り返しました。実験結果によると、これら2つの主要な最適化は、それぞれ約60%と30%の性能向上に貢献しました。 この論文では、ベンチマークを使用して Gödel の卓越したパフォーマンスを評価するだけでなく、ByteDance が実稼働環境で Gödel スケジューラを使用した実際の経験も示し、リソース プーリング、弾力性、フローにおける Gödel の優れた機能を紹介しています。 下の左側の図は、一定期間におけるクラスター内のオンラインタスクとオフラインタスクのリソース割り当てを示しています。当初、オンラインタスクのリソース消費は少なく、大量のコンピューティングリソースが優先度の低いオフラインタスクに割り当てられています。特定のイベント（突発的なイベント、トレンド検索など）によりリソース需要が急増すると、Gödelは即座にオンラインタスクにリソースを割り当て、オフラインタスクへのリソース割り当ては急速に減少します。ピークを過ぎると、オンラインタスクはリソース要求を減らし始め、スケジューラはリソースをオフラインタスクに戻します。オフラインプーリングと動的リソース割り当てにより、ByteDanceは高いリソース使用率を維持しています。夕方のピーク時には、クラスターの平均リソース使用率は60％を超え、日中のオフピーク時でも40％前後を維持しています。 まとめと今後の展望本稿では、ByteDanceのオーケストレーション・スケジューリングチームが設計・開発した、オンラインとオフラインを統合したリソースプールスケジューリングシステム「Gödel」を紹介します。このシステムは、超大規模クラスターにおけるオンラインとオフラインのタスクの同時スケジューリングをサポートし、リソースプーリング、弾力性、リソース転送をサポートし、高いスケジューリングスループットを誇ります。2022年にByteDanceの自社データセンターに大規模導入されて以来、Gödelはほとんどの社内業務の混合導入ニーズを満たし、平均60%を超えるリソース利用率と、ピーク時で約5,000 Pods/sのスケジューリングスループットを達成しています。 今後、オーケストレーションおよびスケジューリングチームは、Gödelスケジューラの拡張と最適化を継続し、スケジューリングセマンティクスのさらなる充実、システム応答性の向上、マルチインスタンスシナリオにおける競合発生確率の低減、システムのリスケジューリング機能の構築と強化を図りながら、初期スケジューリングの最適化、Gödel Reschedulerの設計と開発を進めていきます。GödelスケジューラとReschedulerの連携により、ライフサイクル全体にわたるクラスターリソースの合理的な割り当てが可能になります。 |
