Meta AI Open-Sources Rebalancer: A C++ Assignment Solver That Runs About 40 Million Placement Problems a Day
https://www.marktechpost.com/2026/10/06/meta-ai-open-sources-rebalancer-a-c-assignment-solver-that-runs-about-40-million-placement-problems-a-day/📌 Meta 開源九年內部驗證的分配求解器 Rebalancer
TL;DR：Rebalancer 是 Meta 內部用了 9 年多的 C++ 組合最佳化函式庫，如今以 Apache 2.0 開源並上架 PyPI，號稱每天處理約 4000 萬個配置問題。
機架要塞進哪個資料中心、伺服器要跑哪個服務、任務要分給哪臺機器、使用者流量要導到哪個機房——這些看似簡單的「分配」決策，背後都是 NP-hard 問題。Meta 把內部用了 9 年的解法開源了。
🤔 機架、伺服器、流量，每天 4000 萬次的分配決策
根據 Meta 工程部落格，Rebalancer 用來解決 Meta 內部大量的 assignment problem：在特定限制與目標下，決定哪些物件要放進哪些容器。Meta 指出推廣這類系統有兩大障礙：一是可用性，工程師很難把營運政策轉成精確的數學公式；二是規模，許多問題本質是 NP-hard，規模大到一般商用求解器無法負荷。
🧩 先定義問題，再選怎麼解
Rebalancer 的設計理念，是把「問題怎麼描述」與「問題怎麼求解」分開，這套做法詳述於 OSDI 2024 論文《Optimizing Resource Allocation in Hyperscale Datacenters》。其規格語言分為三層，以 Meta 自己的範例來說：任務是物件（object）、伺服器是容器（bin）、機架是範圍（scope）；CapacitySpec 限制每臺伺服器的 CPU 與儲存容量上限，GroupCountSpec 確保每個機架只容納一種工作類型，BalanceSpec 則讓每臺伺服器在兩個維度上的使用率保持平衡。Rebalancer 會把這份規格編譯成一張有向無環的運算式圖：葉節點存放使用率數值，聚合與轉換節點則建構在其上；使用者只需提供初始配置與停止條件，而初始配置中已違反的限制會自動被標記為高優先目標。
求解端提供兩種引擎：精確解（Optimal solver） 把運算式圖轉譯成混合整數規劃（MIP），交給 FICO Xpress、Gurobi 或 HiGHS 求解，並透過變數聚合與對稱性消除縮小模型規模，但最差情況下模型大小仍是物件數乘以容器數的量級；區域搜尋（Local search） 則直接在運算式圖上操作，嘗試把物件搬到其他容器，最差情況下的搜尋鄰域只跟物件數加容器數成正比，評估過程經過平行化，每秒可達數百萬次評估，並對搜尋空間做剪枝。Meta 對絕大多數大型問題使用區域搜尋，中小型問題則用 MIP，且常先用 MIP 做原型驗證。
為了解決模型除錯耗時的問題，Meta 也一併開源了 Rebalancer Explorer——一套 Docker 化的網頁介面，可以顯示哪些限制正在生效、放寬限制會有什麼影響，以及某個物件為何被分配到特定容器。
📊 現在就能裝：pip install rebalancer
套件以 Apache 2.0 授權釋出，附完整文件；pip install rebalancer 可安裝 v1.0.4，支援 Python 3.12 以上，提供 Linux x86-64 與 macOS 14+ ARM64 的預建 wheel，另有 .deb、.rpm 與 Homebrew 套件可選。不過 PyPI 上目前仍將此專案標示為 Alpha 版本。
與同類工具相比，OR-Tools 涵蓋的問題類型更廣，Timefold 則專攻 JVM 上的排程與路徑規劃；Rebalancer 的差異化在於同一套 assignment spec 可以同時餵給區域搜尋與 MIP 兩種引擎求解，不需為不同求解器重寫問題定義。
🎯 實務啟示
如果團隊正面對大規模資源分配問題（排程、裝箱、負載平衡），Rebalancer 提供了一條經過 Meta 近十年生產環境驗證的路徑，且開源授權寬鬆、可直接自架。但考量 PyPI 仍標示 Alpha，導入正式生產前建議先用現有的 MIP 原型路徑做小規模驗證。
🔗 來源
- 標題：Meta AI Open-Sources Rebalancer: A C++ Assignment Solver That Runs About 40 Million Placement Problems a Day
- 作者／機構：Asif Razzaq（MarkTechPost）
- 連結：https://www.marktechpost.com/2026/10/06/meta-ai-open-sources-rebalancer-a-c-assignment-solver-that-runs-about-40-million-placement-problems-a-day/
#OpenSource #CombinatorialOptimization #AssignmentProblem #MetaAI #CPlusPlus #ResourceAllocation #OperationsResearch #MIP #LocalSearch #DatacenterEngineering
原始資料 MarkTechPost · 收集於 2026-10-07
摘要原文
Meta has open-sourced Rebalancer , a C++ library with a Python interface for solving assignment problems. It decides which objects go into which bins under constraints and objectives. According to the Engineering at Meta’s post , Rebalancer has handled resource allocation across Meta for over 9 years. The release ships under Apache 2.0 with documentation , a PyPI package and a debugging UI called Rebalancer Explorer. Is it deployable? Yes. pip install rebalancer installs v1.0.4 for Python 3.12+, with prebuilt wheels for Linux x86-64 and macOS 14+ ARM64. .deb, .rpm and Homebrew packages also exist. PyPI still classifies the project as Alpha. Assignment problems show up across Meta’s stack. Racks go into datacenters, servers go to services, tasks go to servers, and user traffic goes to datacenters. Meta names 2 blockers: usability and scalability. Engineers struggle to turn policies into precise formulas, and many problems are NP-hard and too large for commercial solvers. Rebalancer’s answer is to separate how a problem is specified from how it is solved. The design is detailed in the OSDI 2024 paper , Optimizing Resource Allocation in Hyperscale Datacenters . The spec language has 3 layers: Meta’s example models tasks as objects, servers as bins and racks as a scope. A CapacitySpec caps CPU and storage per server. A GroupCountSpec keeps 1 job type per rack. A BalanceSpec balances each server’s utilization across both dimensions. Rebalancer compiles the spec into a directed acyclic expression graph. Leaf nodes hold utilization values; aggregation and transformation nodes sit above them. Users supply an initial assignment and a stopping condition. Constraints that the initial assignment already violates become high-priority goals. Optimal solver : The graph is translated into a mixed integer program for FICO Xpress , Gurobi or HiGHS . Variable aggregation and symmetry breaking shrink models. The worst-case model size is still O(objects × bins). Meta’s largest problems are too big for any MIP solver. Local search : This solver works directly on the expression graph. It explores moves of objects to other bins, with a worst-case neighborhood of O(objects + bins). It then applies the best candidate that breaks no constraint. Evaluation is parallelized, reaching millions of evaluations per second, and the search space is pruned. Meta uses local search for almost all large problems and MIP for small to mid-size ones, often prototyping with MIP first. Modelers at Meta spent most of their time debugging solver behavior. Rebalancer Explorer is a Dockerized web UI built for this. It shows binding constraints, relaxation effects, and why an object landed in a bin. OR-Tools covers more problem classes, and Timefold targets JVM scheduling and routing. Rebalancer’s edge is one assignment spec that runs on both local search and MIP. Check out the Paper , GitHub Repo and Technical details . All credit goes to the researcher of this project. Also, feel free to follow us on Twitter and don’t forget to join our 150k+ML SubReddit and Subscribe to our Newsletter . Wait! are you on telegram? now you can join us on telegram as well. [Sponsored] The web is the one API most agents are missing. Databases, calendars and repos have APIs. The open web mostly doesn’t. The TinyFish MCP server gives any MCP client four tools: TinySearch, TinyFetch (full pages as markdown, JavaScript included), TinyBrowser for logins and forms, and TinyAgent for multi-step jobs. Search and Fetch are free. The post Meta AI Open-Sources Rebalancer: A C++ Assignment Solver That Runs About 40 Million Placement Problems a Day appeared first on MarkTechPost .
由 claude-code/sonnet 自動生成