开源Rebalancer：一个用于解决分配问题的通用高性能库
内容提要
Meta开源了Rebalancer，一个已内部使用九年的高性能资源分配库。它分离问题描述与求解，支持最优求解器和局部搜索，每天处理约4000万个分配问题，并附带调试工具Explorer。
延伸解读
分离问题描述与求解：降低建模门槛
Rebalancer 的核心设计是将问题描述与求解过程分离。用户只需用对象、箱、约束和目标等概念描述问题，无需深入数学优化细节。这种分离让工程师能更自然地表达业务规则，同时库内部通过表达式图统一处理，既提升了可用性，也便于扩展和调试。
两种求解策略：最优求解与局部搜索的取舍
Rebalancer 提供最优求解器和局部搜索两种模式。最优求解器将问题转化为混合整数规划，适合中小规模问题，但模型规模可能达到对象数乘以箱数的量级。局部搜索直接在图上游走，邻域大小仅为对象数与箱数之和，能处理超大规模问题。实践中，大规模问题多用局部搜索，中小规模用最优求解器，也可先用最优求解器调优局部搜索。
大规模生产验证：性能与规模数据
Rebalancer 在 Meta 内部已使用九年，每天处理约 4000 万个分配问题，涵盖 30 多种问题形式。对于 26.5 万对象、3200 个箱的问题，P99 求解时间为 12 秒；对于超过 100 万对象、5000 个箱的问题，平均求解时间为 171 秒，此类运行超过 3400 次。这些数据表明其在大规模场景下的稳定性和性能。
调试工具 Explorer：加速问题排查
随着建模变得容易，工程师的时间更多花在调试求解器行为上。Rebalancer 附带 Explorer，一个 Docker 化的 Web UI，帮助回答哪些约束是紧的、放宽约束会怎样、为何某对象被分配到某箱等问题。它支持局部搜索和最优求解器，能显著降低调试门槛，加快迭代速度。
Q&A
Rebalancer是什么？它主要用来解决什么问题？
Rebalancer是Meta开源的一个高性能资源分配库，用于解决分配问题：给定一组对象和一组箱子，如何将对象分配到箱子中，以优化特定目标并满足约束。它已内部使用超过九年，每天处理约4000万个分配问题。
Rebalancer如何解决分配问题？它支持哪些求解方法？
Rebalancer将问题描述转化为表达式图，然后提供两种求解技术：最优求解器（将表达式图转化为混合整数规划，使用FICO Xpress、Gurobi或HiGHS求解）和局部搜索求解器（直接在表达式图上探索邻域，通过移动对象来改进分配）。
Rebalancer在Meta内部有哪些实际应用案例？
Rebalancer在Meta用于多种基础设施优化问题，包括：将分片分配到服务器（Shard Manager）、将服务器分配到服务（RAS）、将流量从边缘数据中心路由到主数据中心（Taiji）、分组无服务器函数以提高局部性、平衡在线ML训练工作负载等。此外还用于非基础设施问题，如分配会议室、分配支持工单、优化办公桌摆放。
Rebalancer的局部搜索求解器有什么优势？
局部搜索求解器直接在表达式图上工作，探索当前分配附近的邻域，最坏情况下的邻域大小为O(|objects|+|bins|)，远小于最优求解器可能产生的O(|objects|*|bins|)的MIP模型。这使得Rebalancer能够处理非常大的问题而不受内存限制。局部搜索算法经过高度优化和并行化，每秒可进行数百万次评估，并能修剪搜索空间。
Rebalancer Explorer是什么？它有什么作用？
Rebalancer Explorer是一个随Rebalancer开源的Docker化Web UI工具，用于帮助模型开发者快速调试和迭代求解过程。它可以回答诸如哪些约束是绑定的、如果放松约束会怎样、为什么某个对象被放在某个箱子而不是另一个等问题。
Rebalancer的规格语言如何描述分配问题？
Rebalancer的规格语言采用三步法逐步提升抽象级别：首先引入基本建模构造，如维度（对象和箱子的属性）、分区（对象分组）、作用域（箱子分组）和利用率（对象对箱子的贡献）；然后提供表达式API，用于对这些构造进行转换和递归组合；最后暴露高级规格API，实现数十种常见目标和约束，每个规格可视为预定义配方，接受建模构造和参数，生成数学公式。
Rebalancer的性能如何？能处理多大规模的问题？
Rebalancer每天解决约4000万个分配问题，有超过30种独特的问题形式。对于26.5万个对象和3200个箱子的问题，P99求解时间为12秒；对于超过100万个对象和5000个箱子的问题，平均求解时间为171秒，此类运行超过3400次。
