Meta开源Rebalancer：日解4000万分配问题的C++求解器
Meta正式开源Rebalancer——一款高性能C++编写的资源分配求解库，支持Python接口，已在其生产环境稳定运行9年。该工具每日处理超4000万个分配问题，覆盖服务器调度、流量路由、工单分派等场景，并配套可视化调试工具Rebalancer Explorer。
开源即生产：Meta发布工业级分配求解器
Meta近日开源Rebalancer，一个面向大规模资源分配问题的C++求解库，提供Python绑定接口。该项目已在Meta内部支撑资源调度系统逾9年，现以Apache 2.0许可证发布，包含完整文档、PyPI包（v1.0.4，支持Python 3.12+）、预编译wheel（Linux x86-64 / macOS 14+ ARM64），以及.deb、.rpm和Homebrew安装包。尽管PyPI仍标记为Alpha阶段，但其已在生产环境中全面部署。
解决什么问题？从机架到工单的通用分配建模
Rebalancer聚焦于“分配问题”（assignment problem）：在约束条件下，将对象（如任务、服务器、用户请求）分配至容器（如服务器、机架、数据中心、工程师）。Meta指出，此类问题遍布其技术栈——机架入数据中心、服务部署至服务器、计算任务调度至物理节点、用户流量路由至边缘集群。传统方案面临两大瓶颈：一是工程师难以将业务策略精确转化为数学公式；二是多数实际问题属NP-hard，规模远超商用求解器（如Gurobi、Xpress）处理能力。Rebalancer的核心设计哲学是“分离建模与求解”：通过声明式规范语言描述问题，再由底层引擎自动选择最优算法路径。
三层建模语言：让策略可写、可读、可验
Rebalancer的规范语言分为三层：
- 建模构件层：定义维度（CPU、内存等属性）、分区（对象分组）、作用域（容器分组）与利用率；
- 表达式API层：支持SUM、MAX聚合及SQUARE等变换操作；
- 规范API层：提供数十种预置目标函数与约束类型（如CapacitySpec限制单节点资源上限，GroupCountSpec确保每机架仅含一类作业，BalanceSpec均衡多维利用率）。
Meta示例中，将“任务”建模为对象、“服务器”为容器、“机架”为作用域，即可组合出符合真实运维逻辑的分配策略。
一图双解：混合整数规划与局部搜索协同求解
所有规范被编译为有向无环表达式图（DAG）：叶节点存储利用率值，中间节点执行聚合或变换。用户输入初始分配与终止条件后，违反约束项自动升为高优先级优化目标。
- 最优求解器：将DAG转译为混合整数规划（MIP）模型，交由FICO Xpress、Gurobi或HiGHS求解；通过变量聚合与对称性破除压缩模型规模，但最坏复杂度仍为O(对象数×容器数)；
- 局部搜索求解器：直接在表达式图上迭代探索对象迁移操作，邻域规模仅为O(对象数+容器数)，并行评估可达百万次/秒，辅以剪枝策略加速收敛。Meta在绝大多数大规模问题中采用局部搜索，仅对中小规模问题（常用于原型验证）启用MIP。
生产实绩与典型用例
Meta当前每日运行超4000万个分配问题，涉及30余种不同建模配方。P99求解耗时为12秒（26.5万对象、3200容器）；超百万对象+5000容器的问题平均耗时171秒（样本量3400+）。典型落地场景包括：
- 集群内调度：如Shard Manager与RAS系统，将分片/容器按CPU/内存上限分配至服务器，并跨机架分散副本；
- 跨区域负载均衡：如Taiji系统调度边缘流量，或按优先级平衡ML训练任务在数据中心间的分布；
- 非基础设施运营：将客服工单分配给工程师、会议室预约、办公座位规划等，均遵循容量与公平性规则。
可视化调试：Rebalancer Explorer降低建模门槛
为应对建模调试耗时长的痛点，Meta同步推出Docker化Web UI——Rebalancer Explorer。该工具可交互式展示关键约束触发原因、松弛效果、单个对象落位逻辑，并支持步进执行、随机劣质初值注入等调试操作，实时呈现目标函数演化曲线与容量溢出状态，显著提升策略迭代效率。