Rebalancer をオープンソース化：割り当て問題のための汎用高性能ライブラリ

私たちは Rebalancer をオープンソース化しました。この割り当て問題ソルバーは、Meta 社内で9年以上にわたり、さまざまなリソース割り当て問題の解決に使われてきました。
Rebalancer は、互いに関連しつつも独立したいくつかの事柄を切り離しています。割り当て問題をどう記述するか、それをメモリ上でどう効率よく保持するか、どう解くか、どうデバッグするか。この関心の分離こそが、Rebalancer の使いやすさ、拡張性、そして応用のしやすさを支えています。
より詳細な技術的説明は、OSDI'24 で発表した論文「Optimizing Resource Allocation in Hyperscale Datacenters: Scalability, Usability, and Experiences」を参照してください。

オブジェクトの集合とビンの集合が与えられたとき、いくつかの制約を満たしつつ特定の目的を最適化するには、オブジェクトをどうビンに割り当てればよいでしょうか。

この問題は Meta のインフラスタックのあらゆる層に現れます。たとえば：

ハードウェアの配置： ラック（オブジェクト）をデータセンター（ビン）に配置します。電力と冷却の制約を満たしながら、電源障害ドメイン間でのラックの分散度を最適化します。
サービスのデプロイ： サーバー（オブジェクト）をサービス（ビン）に割り当てます。各サービスの需要を満たしつつ、耐障害性（あるサービスに割り当てたサーバーを異なる障害ドメインに分散させること）やビンパッキング効率といった目的を最適化します。
タスクのスケジューリング： タスク（オブジェクト）をサーバー（ビン）に割り当てます。サーバーのリソース制約を守りながら、耐障害性やコロケーション要件などの目的を最適化します。
トラフィックのルーティング： 数十億ユーザーからのトラフィック（オブジェクト）を地理的に分散したデータセンター（ビン）へルーティングします。ネットワーク遅延とデータセンターの負荷を最適化します。

こうした問題に向けた再利用可能な求解フレームワークを設計するうえでの主な課題は、使いやすさと拡張性にあります。使いやすさを妨げるのは、現実のポリシーを、形式的最適化手法が要求する厳密な数式へと翻訳するのが難しいことです。拡張性を妨げるのは、これらの問題がいずれも NP-hard であり、商用ソルバーでは効率的に解けないことにあります。

Rebalancer は、問題の記述と求解を分離することで、この両方の難題を同時に解決します。Rebalancer は、オブジェクト、ビン、制約、目的で問題を記述するための言語を提供します。冒頭の例で示したとおりです。問題がこのように記述されると、Rebalancer はそれを有向非巡回グラフに変換します。これを式グラフと呼びます。Rebalancer の求解アルゴリズムは式グラフを利用し、局所探索ヒューリスティックを設計するか、あるいは混合整数計画（MIP）を構築して、商用ソルバー（FICO Xpress や Gurobi）またはオープンソースソルバー（HiGHS）で解きます。

割り当て問題を記述する

Rebalancer の記述言語は、使いやすさのために抽象度を段階的に上げる3段階のアプローチをとります。

まず、基本的なモデリング要素を導入します。たとえば次元（オブジェクトとビンの現実世界での属性）、パーティション（オブジェクトのグループ）、スコープ（ビンのグループ）、使用率（あるビンに割り当てられたオブジェクトがもたらす寄与）などです。
次に、Rebalancer はこれらの要素を変換する一般的な式を公開する API を提供します。式は他の式に再帰的に作用させられます。たとえば、複数のビンの使用率は SUM/MAX 操作で集約でき、SQUARE 操作で変換することもできます。
最後に、これらの式を土台として、Rebalancer は数十種類の一般的な目的と制約を実装した高レベルの spec API を公開します。各 spec はあらかじめ定義されたレシピだと考えてください。いくつかのモデリング要素と追加パラメータを入力として受け取り、式 API を使って数式を生成します。

タスク配置問題のモデリング要素と spec の例。

上の例では、タスクをオブジェクトとして、サーバーをタスクを入れるビンとしてモデリングしています。サーバーは物理的にはラックに収まっており、このグループをスコープとしてモデリングします。タスクは一定量の CPU とストレージを消費し、サーバーはそれぞれに上限を持ちます。CPU とストレージは次元としてモデリングします。あるサーバーの CPU とストレージの使用率は、そのサーバーに割り当てられた全タスクの合計に等しく、サーバーの使用率上限は CapacitySpec でモデリングします。単純な総和が適切でない場合は、式 API で使用率の計算方法を変えられます。

さらに、タスクはジョブに属するものとしてモデリングします。このようにオブジェクトをグループ化したものを partition と呼び、GroupCountSpec を使って各ラックに1種類のジョブ（つまり1つのパーティション）だけが割り当てられるようにします。BalanceSpec は、各サーバーの使用率が CPU とストレージの2つの次元で均衡を保つようにします。

この例は、Rebalancer で複雑な割り当て問題をいかに簡単かつ自然に組み立てられるかを示しています。また、spec が制約と目的をどう表現するかも示しています。次元、スコープ、パーティションを変えるだけで、同じ spec の組をさまざまな形で再利用できます。

Rebalancer の spec の全リストはドキュメントを参照。

割り当て問題を解く

問題を上述の API で記述すると、Rebalancer はそれを式グラフに変換する。グラフの葉ノードは利用率の式を表す。たとえばサーバ A のメモリ利用率は、A に割り当てられた各タスクのメモリ使用量を合計して得られる。これらの利用率の値は、集約ノード（Max、Sum など）や変換ノード（Square、Abs など）を通じて再帰的に組み合わされる。式グラフの各ノードの値は現在の割り当てに依存するため、割り当てが変われば必ず更新が必要になる。

問題の目的と制約に加えて、モデリング担当者は Rebalancer に初期割り当てと停止条件（時間上限など）を渡す。Rebalancer は目的値を最小化し、かつ新しい制約に違反しない最適化された割り当てを計算する。初期割り当てが違反している制約は優先度の高い目的となり、その違反量はできる限り小さく抑えられ、理想的にはゼロまで下がる。

Rebalancer は割り当て問題を解くために 2 つの異なる技術を提供する。

最適ソルバー。 このモードでは、Rebalancer は式グラフを一連の式に変換し、FICO Xpress、Gurobi、HiGHS などの MIP ソルバーに渡す。変換の過程で、Rebalancer は bin の利用率をバイナリ決定変数（オブジェクトごとに 1 つ）の加重和で表す必要がある。これらの変数は、そのオブジェクトがその bin に割り当てられているかどうかを示す。これにより MIP モデルは非常に巨大になる。Rebalancer は変数の集約（類似したオブジェクトを 1 つの整数変数にまとめる）、交換可能性、対称性の除去といった技術を自動的に適用してモデルを縮小するが、生成される MIP モデルは最悪の場合でも二乗オーダー、すなわち O(|objects| * |bins|) になりうる。私たちが扱う最大規模の問題は、どの MIP ソルバーにとっても大きすぎる。

Local Search Solver は式グラフ上で直接動作し、この制限を回避する。現在の割り当ての周囲の局所近傍を探索し、一部のオブジェクトを別の bin に移す。この近傍の最悪の場合のサイズは O(|objects|+|bins|) であるため、Rebalancer は非常に大きな問題でもメモリ上限に達しない。各 move は新しい候補割り当てを生成し、Rebalancer はその割り当ての下での各目的と制約の新しい値を evaluate する。すべての候補を評価した後、Rebalancer はその中で最良のもの、つまりどの制約にも違反せず、目的の改善幅が最大のものを apply する。move を評価して適用するプロセスは、改善が続かなくなるか停止条件が発動するまで繰り返される。Rebalancer の局所探索アルゴリズムは大幅に最適化され並列化されており、1 回の評価のコストが低い（毎秒数百万回の評価が可能）ため、探索空間を高速に探索できる。さらに Rebalancer は枝刈りを理解しており、必要な評価回数を最初から減らす。

どちらの求解技術を使うかは要件次第だ。Meta では、ほぼすべての大規模問題を局所探索で解いている。中小規模で、求解時間にある程度の余裕がある問題には、通常は最適ソルバーを使う。よくある進め方として、まず最適ソルバーでプロトタイプを作り、高品質なベースラインを得てから局所探索に移行するという方法もある。オフラインのシナリオでは、最適ソルバーを使って局所探索をチューニングできる。

Meta における Rebalancer の活用

過去 10 年間、Rebalancer は Meta で継続的に使われ、改良され続けてきた。さまざまなインフラ最適化問題の解決に使われている。たとえば、shard をサーバに割り当てる（Shard Manager）、サーバをサービスに割り当てる（RAS）、世界に分散したエッジデータセンターからメインデータセンターへトラフィックをルーティングする（Taiji）、serverless 関数をグループ化して局所性を高める、ML ワークロードの優先度を考慮しながらオンライン ML トレーニングの負荷をリージョン間で分散する、などだ。本稿執筆時点で、Rebalancer は 1 日あたり約 4000 万件の割り当て問題を、30 種類以上の異なる問題モデリングにわたって解いている。26.5 万個のオブジェクトと 3200 個の bin を含む問題では、P99 の求解時間は 12 秒。オブジェクトが 100 万を超え、bin が 5000 を超える問題では、平均求解時間は 171 秒で、こうした実行は 3400 回を超える。

当然ながら、Rebalancer はインフラ以外の問題にも使われている。たとえば、移動時間を最小化するように会議を会議室に割り当てる、サポートチケットをエンジニアに割り当てる、オフィスの座席レイアウトを最適化する、といった用途だ。Meta の外では、割り当て問題は医療、エネルギー・公益事業、交通・物流、教育、緊急対応など、多くの領域に現れる。私たち自身がこれらの領域に Rebalancer を適用することはできないが、誰かがやってくれることを願っている。そして、ぜひ実際にやってほしい。

デバッグ

Rebalancer が問題のモデリングと求解を容易にした結果、モデリング担当者の時間の大半はソルバーの挙動のデバッグに移ったことがわかった。適切なツールがなければ、このデバッグにはソルバーの内部機構への深い理解が必要になる。

時間をかけて、モデリング担当者がよく尋ねる質問とよくある悩みを洗い出し、そのために専用の UI ツールを作った。Rebalancer Explorer である。

https://facebook.github.io/rebalancer/videos/rebalancer-explorer-demo.mp4

Explorer は Rebalancer とともに今回のオープンソース化で公開された。Docker 化された Web UI で、局所探索や最適化ソルバーで問題を解く際のデバッグと反復作業を素早くこなせる。どの制約がタイトなのか、ある制約を緩めたらどうなるのか、なぜあるオブジェクトが別の bin ではなくこの bin に入ったのか——こうした問いに答える手助けになる。

Rebalancer の今後

私たちは Rebalancer の性能最適化、機能追加、そしてより多様な割り当て問題を扱えるよう拡張する方法を模索し続けてきた。Rebalancer はオープンソース（Apache 2.0 ライセンス）として公開しており、システムと最適化の両分野の専門家に試用とプロジェクトへの貢献を呼びかけている。性能のボトルネックを見つける、新しい求解技術を組み込む、新しい種類の問題に対応できるよう拡張する、あるいはただバグを直す——どんな形でも構わない。システムと最適化のコミュニティが Rebalancer をどう採用し、育て、還元していくのか楽しみにしている。

コード：Rebalancer GitHub リポジトリ
ドキュメント：Rebalancer 入門
PyPI：Rebalancer Python パッケージ
論文：Optimizing Resource Allocation in Hyperscale Datacenters: Scalability, Usability, and Experiences — OSDI 2024

謝辞

Rebalancer は Meta アルゴリズム最適化チームの現メンバーと元メンバーが共同で開発した：Pol Mauri Ruiz、Igor Kabiljo、Neeraj Kumar、Vijay Menon、Mayank Pundir、Andrew Newell、Liyuan Wang、Richard Barnes、Sahil Deshpande、Karthik Velakur、Yang Liu、Leart Gjoni、Ravi Surulikamu、Tony Zhang、Raj Rajendran、Aravind Narayanan、Lakshmi Ganesh、Saranyan Vigraham。