Metaが9年間運用してきた割り当て問題ソルバー「Rebalancer」がオープンソース化 — 設計思想を徹底解説

はじめに：割り当て問題はなぜ常に難しいのか

開発をしていると、こんな問いに直面します。

「サーバがN台、タスクがM個ある。障害ドメインは最大限分散させつつ、リソースの無駄は最小化したい。どう配置すべきか？」

これを人手で解くと、結局は「勘」になります。正式に解こうとするとNP困難問題が現れ、商用ソルバーに投入してもモデルサイズがO(|objects| × |bins|)で爆発します。Metaはこの問題を9年間社内ライブラリ一つで解決してきました。それが先日Apache 2.0でオープンソース化されたRebalancerです。

本記事では、Rebalancerがどのような問題をどう分離して解くのか、そしてなぜこれが単なる「ソルバーが一つ増えた」ではなくアーキテクチャ設計の教科書なのかを整理します。根拠資料はMeta Engineeringの原典を参照してください。

核心構造：問題定義と解法を分離する

Rebalancerの設計哲学は一行に集約されます。「問題をどう記述するか(Spec)と、どう解くか(Solve)を分離する」。

3段階の抽象化を実現する仕様言語

例えば「タスクをサーバに配置しつつ、ラックごとに1つのジョブのみ許可し、CPU/ストレージのバランスを取る」という要件は次のように表現できます。

# タスク=object, サーバ=bin, ラック=scope, CPU/ストレージ=dimension
spec = AssignmentSpec(
    objects=tasks,
    bins=servers,
    scopes=racks,
    dimensions=["cpu", "storage"],
    partitions=[job_partition],
)

spec.add(CapacitySpec(dimension="cpu", limit=server_cpu_limit))
spec.add(CapacitySpec(dimension="storage", limit=server_storage_limit))
spec.add(GroupCountSpec(partition=job_partition, scope=racks, max_count=1))
spec.add(BalanceSpec(dimensions=["cpu", "storage"]))

この仕様は内部的に表現グラフ(Expression Graph) というDAGへ変換されます。リーフノードは「サーバAのメモリ使用率」、上位ノードはMax/Sum/Squareなどの演算です。ここで重要なのは、すべてのノードの値が現在の割り当て状態に依存するという点です。配置が変わればグラフ全体を再評価する必要があります。

二つの解法：Local Search vs Optimal Solver

Rebalancerは全く異なる二つの解法を提供します。状況に応じて使い分けるのが実務感覚です。

Optimal Solver (MIPベース)

表現グラフを混合整数計画法(MIP) に変換し、FICO Xpress、Gurobi、HiGHSといった商用/オープンソースソルバーに投入します。問題は、この変換過程で各binの使用率をバイナリ決定変数の重み付き和として表現する必要がある点です。最悪の場合、モデルサイズはO(|objects| × |bins|)に膨張します。

Rebalancerはこれを緩和するため、以下の手法を自動適用します。

• Variable aggregation: 類似オブジェクトを単一の整数変数に圧縮
• Interchangeability: 交換可能なオブジェクトをグループ化
• Symmetry breaking: 対称解の除去

それでも1Mオブジェクト × 5kビンの規模はMIPでは解けません。

Local Search Solver

表現グラフ上で直接動作します。現在の割り当て周辺の近傍(neighborhood)を探索し、オブジェクトを別のbinへ移動させる方式です。近傍サイズがO(|objects| + |bins|)であるため、メモリ爆発なしに超大規模問題を扱えます。

# 概念的擬似コード: Local Searchループ
while not stopping_condition_met():
    candidates = generate_moves(current_assignment)  # 近傍生成
    best = None
    for move in candidates:  # 並列評価、毎秒数百万件が可能
        new_assignment = apply(move)
        if violates_constraint(new_assignment):
            continue
        if best is None or objective(new_assignment) < objective(best):
            best = new_assignment
    if best is None:
        break  # これ以上改善不可
    current_assignment = best

Meta社内では大規模問題はほぼ全てLocal Searchで解き、中小規模で時間的余裕がある場合のみOptimal Solverを使います。一般的なパターンはOptimalでプロトタイピング → Local Searchで本番移行です。

実測値(Meta公開ベース)

• 1日あたり約4,000万件の割り当て問題を30種類以上の異なる問題定義で解決
• 265k objects / 3.2k bins問題でP99解決時間12秒
• 1M+ objects / 5k bins問題の平均解決時間171秒、1日3.4k件以上を実行

この技術の限界と注意点

正直に言えば、Rebalancerは万能ではありません。

1. 問題定義自体の難しさは残ります。 仕様言語が楽になっただけで、現実のポリシーを数式へ翻訳するのは依然として人間の仕事です。むしろ「仕様を誤って書くと」デバッグ地獄が開きます。
2. Local Searchは大域最適解を保証しません。 初期割り当て(initial assignment)に性能が大きく左右されます。初期値をどう与えるかが実務の成否を分けます。
3. MIP経路は拡張性の限界が明確です。 オブジェクト数が数十万単位を超えると、事実上Local Searchへ移行せざるを得ません。
4. デバッグツール(Explorer)への依存。 著者らも明記している通り、モデラーの時間の大半は「ソルバー動作のデバッグ」に消費されます。UIなしで使うと生産性が急落します。

日本開発エコシステムにおける適用文脈

日本国内でRebalancerをそのまま使える場面は、実は多くありません。ハイパースケールデータセンターを運用している企業は限られています。しかし設計の教科書としての価値は、むしろ国内のSI/プラットフォーム組織でこそ大きいと言えます。

• Kubernetesスケジューラのカスタマイズを行うチームにとって、Rebalancerの「Spec → Expression Graph → Solver」という3段分離は優れた参考モデルです。スケジューリングポリシーをコードにハードコードする代わりに、宣言的に分離する感覚を学べます。
• バッチジョブスケジューラ(例: 夜間バッチをどのワーカーに寄せるか)を自前実装するチームにとって、Local SearchアプローチはMIPよりはるかに現実的です。
• 物流/配車最適化を扱うスタートアップにとって、RebalancerのSpec APIが提供する抽象化レベルはそのままベンチマーク対象になります。

次のステップ学習の方向性

1. 論文を先に: OSDI'24に採録された*"Optimizing Resource Allocation in Hyperscale Datacenters"* を読んでください。仕様言語の形式定義が記載されています。
2. PyPIパッケージを試す: pip install rebalancer でインストールし、ドキュメントのチュートリアル問題をローカルで実行してみてください。
3. Explorerを起動: Dockerで立ち上がるWeb UIを起動し、制約条件を一つずつrelaxしながら解がどう変わるかを観察するのが最速の学習法です。
4. 比較対象: Google OR-Tools、OptaPlannerと比較すると、「宣言的仕様 + 二重ソルバー」というRebalancer独自のポジションが明確になります。

まとめ

Rebalancerの真の価値は「高速なソルバー」ではなく、「問題定義と解法を分離する」 というアーキテクチャ原則を9年間本番環境で検証した点にあります。社内ライブラリ一つが1日4,000万件を処理するという事実は、その設計が理論ではなく実戦で生き残ったという証明です。国内でもスケジューリング/バッチ/割り当て問題を扱うチームであれば、この構造を一度は読み解く価値が十分にあります。

あわせて読みたい記事

• CloudflareがDNSキャッシュメモリ100TBを削減したRust最適化5段階
• 11万件の論文検索システムをハイブリッドアーキテクチャで構築する(Hugging Faceインフラ活用)