开源 Rebalancer：解决分配问题的通用高性能库

我们开源了 Rebalancer——这个分配问题求解器在 Meta 内部用于解决各类资源分配问题已有九年多。
Rebalancer 把几件相关但彼此独立的事情拆开了：如何描述一个分配问题、如何高效地在内存中存储它、如何求解它、如何调试它。正是这种关注点分离，成就了 Rebalancer 的易用性、可扩展性和可延伸性。
更详细的技术阐述见配套论文《Optimizing Resource Allocation in Hyperscale Datacenters: Scalability, Usability, and Experiences》，发表于 OSDI'24。

给定一组对象和一组箱子，如何把对象分配到箱子中，在满足若干约束的同时优化特定的目标？

这个问题出现在 Meta 基础设施栈的各个层面，包括：

硬件摆放： 机架（对象）需要放置到数据中心（箱子）中，在满足供电和散热限制的前提下，优化机架在电力故障域上的分散程度。
服务部署： 服务器（对象）需要分配给服务（箱子），以满足每个服务的需求，同时优化容错（把一个服务分到的服务器分散到不同故障域）和装箱效率等目标。
任务调度： 任务（对象）需要分配到服务器（箱子）上，在遵守服务器资源限制的同时，优化容错、同置要求等目标。
流量路由： 把来自数十亿用户的流量（对象）路由到地理上分散的数据中心（箱子），同时优化网络时延和数据中心负载。

为这类问题设计一个可复用的求解框架，主要挑战在于易用性和可扩展性。易用性的障碍在于，从业者很难把现实中的策略翻译成形式化优化方法所要求的那种精确数学公式；可扩展性的障碍则在于这些问题都是 NP-hard，商业求解器无法高效求解。

Rebalancer 通过将问题的描述与求解分离，同时解决了这两个难题。Rebalancer 提供了一套语言，用对象、箱子、约束和目标来描述问题，如上文示例所示。问题一旦以这种方式描述出来，Rebalancer 就会把它转换为一张有向无环图，称为表达式图。Rebalancer 的求解算法利用表达式图，要么设计出局部搜索启发式，要么构建一个混合整数规划（MIP），用商业求解器（FICO Xpress 或 Gurobi）或开源求解器（HiGHS）求解。

描述分配问题

Rebalancer 的描述语言采用三步走的方式，逐步提升抽象层级，以便使用。

首先，它引入基本的建模构件，例如维度（对象和箱子在现实世界中的属性）、分区（对象的分组）、作用域（箱子的分组）以及利用率（分配到某个箱子的对象所做的贡献）。
接着，Rebalancer 提供一套 API，用于暴露对这些构件做变换的常用表达式，并且可以递归地作用于其他表达式。例如，多个箱子的利用率可以用 SUM/MAX 操作聚合，也可以用 SQUARE 操作变换。
最后，基于这些表达式，Rebalancer 暴露出一套高层的 spec API，实现了数十种常见的目标和约束。可以把每个 spec 看作一份预定义的配方：它接受若干建模构件和额外参数作为输入，用表达式 API 生成一个数学公式。

一个任务放置问题的建模构件与 spec 示例。

在上面的示例中，任务被建模为对象，服务器被建模为待放入任务的箱子。服务器物理上位于机架中，这种分组被建模为作用域。任务占用一定量的 CPU 和存储，服务器对二者各有上限。CPU 和存储被建模为维度。一台服务器的 CPU 和存储利用率，等于分配给该服务器的所有任务之和，服务器的利用率上限则用 CapacitySpec 建模。如果简单的求和并不合适，可以用表达式 API 改变利用率的计算方式。

此外，我们将任务建模为从属于作业。像这样把对象分组称为 partition，我们用一个 GroupCountSpec 来确保每个机架只分配一种作业类型（即一个分区）。BalanceSpec 则确保每台服务器在 CPU 和存储两个维度上的利用率保持均衡。

这个例子展示了用 Rebalancer 构造复杂分配问题可以多么简单自然，也展示了 spec 如何表达约束和目标——只要改变维度、作用域或分区，同一套 spec 就能以多种方式复用。

Rebalancer 的 spec 完整列表见文档。

求解分配问题

问题用上述 API 描述好之后，Rebalancer 会把它转换成一个表达式图。图中的叶节点表示利用率表达式，例如服务器 A 的内存利用率，它由分配给 A 的各任务的内存占用求和得到。这些利用率值再通过聚合节点（如 Max、Sum）或变换节点（如 Square、Abs）递归组合。注意，表达式图中每个节点的值都取决于当前分配方案，分配一变就必须更新。

除了问题的目标和约束，建模者还要向 Rebalancer 提供初始分配和一个停止条件，比如时间上限。Rebalancer 会计算出一个优化后的分配方案，使目标值最小，且不违反任何新约束。初始分配所违反的约束会成为高优先级目标，其违反程度被尽量压低，理想情况下降到零。

Rebalancer 提供两种不同的技术来求解分配问题。

最优求解器。 在这种模式下，Rebalancer 把表达式图转换成一组表达式，送入 FICO Xpress、Gurobi 或 HiGHS 之类的 MIP 求解器。转换过程中，Rebalancer 需要用二元决策变量（每个对象一个）的加权和来表示一个 bin 的利用率，这些变量指示该对象是否被分配到该 bin；这会导致 MIP 模型非常庞大！Rebalancer 会自动采用变量聚合（把相似对象合并成一个整数变量）、可互换性和对称性破除等技术来缩小模型规模，但生成的 MIP 模型最坏情况下仍可能是平方级的，即 O(|objects| * |bins|)。我们考虑的最大规模问题，对任何 MIP 求解器来说都太大了。

Local Search Solver 直接在表达式图上工作，绕开了这一限制：它围绕当前分配方案探索局部邻域，把部分对象移到另一个 bin。这个邻域的最坏情况规模是 O(|objects|+|bins|)，因此 Rebalancer 即使面对非常大的问题也不会触及内存上限。每一次 move 都会产生一个新的候选分配方案，Rebalancer 会 evaluate 该方案下各个目标和约束的新取值。所有候选方案评估完毕后，Rebalancer 会 apply 其中最优的一个，即不违反任何约束、且目标改善幅度最大的那个。评估并应用 move 的过程反复进行，直到无法继续改进或触发停止条件。Rebalancer 的局部搜索算法经过大量优化和并行化，单次评估的开销很低（每秒可完成数百万次评估），因此能快速探索搜索空间。此外，Rebalancer 还懂得剪枝，从一开始就减少所需的评估次数。

该用哪种求解技术取决于你的需求。在 Meta，几乎所有大规模问题都用局部搜索。中小规模、对求解时间要求适中的问题，通常用最优求解器。常见的做法还有：先用最优求解器做原型，得到高质量的基线方案后再迁移到局部搜索。离线场景下，最优求解器可以用来调优局部搜索。

Rebalancer 在 Meta 的应用

过去十年间，Rebalancer 在 Meta 持续使用并不断改进。它被用于解决各类基础设施优化问题，包括把 shard 分配到服务器（Shard Manager）、把服务器分配给服务（RAS）、把流量从全球分布的边缘数据中心路由到主数据中心（Taiji）、对 serverless 函数分组以提升局部性、在考虑 ML 工作负载优先级的前提下跨区域平衡在线 ML 训练负载，等等。撰写本文时，Rebalancer 每天解决约 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 而不是另一个。

Rebalancer 的未来

我们一直在设法优化 Rebalancer 的性能、增加新能力，并扩展它去支持更多种类的分配问题。Rebalancer 很自豪地采用开源方式（Apache 2.0 许可证），我们邀请系统和优化两方面的专家来试用 Rebalancer 并为项目做贡献：找出性能瓶颈、加入新的求解技术、扩展它去支持新类型的问题，或者只是修修 bug。我们期待看到系统和优化社区如何采用、构建并回馈 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。