Open-Sourcing Rebalancer: A Generic, High-Performance Library for Solving Assignment Problems

开源 Rebalancer：一个用于解决分配问题的通用、高性能库 - Meta 工程技术

发布日期

2026年9月21日

分类

开源

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

.entry-meta

.entry-header

作者

Richard Barnes

,

Neeraj Kumar

Pol Mauri Ruiz

• 我们正在开源 Rebalancer，这是一个已用于解决 Meta 内部资源分配问题超过九年的分配问题求解器。

• Rebalancer 将多个相关问题分离：如何定义分配问题、如何高效地在内存中存储问题、如何求解问题以及如何调试问题。这种关注点分离对 Rebalancer 的可用性、可扩展性和可扩展性至关重要。

• 如需更详细的的技术说明，请参阅配套论文《在超大规模数据中心中优化资源分配：可扩展性、可用性和经验》，发表于 OSDI’24。

给定一组对象和一组容器，我们如何以优化特定目标并满足某些约束的方式将对象分配到容器中？

这个问题出现在 Meta 基础设施堆栈的所有层级，包括：

• 硬件部署：机架（对象）需要在数据中心（容器）中定位，以优化机架在电力故障域中的分布，同时遵守电力和冷却限制。

• 服务部署：服务器（对象）需要分配给服务（容器），以满足每个服务的需求，同时优化容错性（将服务分配的服务器分布在故障域中）和打包效率。

• 任务部署：任务（对象）需要分配给服务器（容器），同时遵守服务器资源限制，并优化容错性和共置需求等目标。

• 流量路由：将数十亿用户的流量（对象）路由到地理分布的数据中心（容器），同时优化网络延迟和数据中心负载。

设计一个可重复使用的框架来解决此类问题的主要挑战是其可用性和可扩展性。可用性受到从业者难以将现实政策转化为正式优化方法所需的精确数学公式的影响，而可扩展性则受到商业求解器无法高效解决的 NP 难问题的阻碍。

Rebalancer 通过将问题的定义与其解决方案分离来解决这两个挑战。Rebalancer 提供了一种使用对象、容器、约束和目标来描述问题的语言，如上面的示例所示。一旦以这种方式描述问题，Rebalancer 就会将问题转换为称为表达图的有向无环图。Rebalancer 的求解算法使用表达图来设计局部搜索启发式方法，或构建混合整数规划（MIP）问题，该问题可以使用商业求解器（如 FICO Xpress 或 Gurobi）或开源求解器（如 HiGHS）求解。

定义分配问题

Rebalancer 的定义语言采用三步方法逐步提高抽象级别以提高易用性。

• 首先，它引入了基本的建模构造，如维度（对象和容器的实际世界属性）、分区（对象的分组）、作用域（容器的分组）和利用率（分配到容器的对象的贡献）。

• 接下来，Rebalancer 提供了一个 API，用于公开对这些结构进行转换的常用表达式，同时也可以递归地应用于其他表达式。例如，多个容器的使用情况可以通过 SUM/MAX 操作进行聚合，或通过 SQUARE 操作进行转换。

• 最后，利用这些表达式，Rebalancer 提供了一个高级的 spec API，实现了数十种常见的目标和约束条件。可以将每个 spec 视为一个预定义的配方，它接受一些建模结构和附加参数作为输入，并通过表达式 API 创建数学公式。

任务分配问题的建模结构和 spec 示例。

在上述示例中，任务被建模为对象，服务器被建模为用于放置任务的容器。服务器物理上位于机架中；这种分组通过 scope 进行建模。任务需要一定量的 CPU 和存储空间，而服务器对这两种资源有使用限制。CPU 和存储被建模为维度。服务器的 CPU 和存储使用情况对应于分配给该服务器的所有任务的总和，服务器的使用限制通过 CapacitySpec 进行建模。如果简单的求和方式不适用，可以使用表达式 API 修改使用情况的计算方式。

此外，我们将任务建模为属于作业。这种对象分组称为 partition，我们使用 GroupCountSpec 来确保每个机架仅分配一种作业类型（partition）。BalanceSpec 确保每个服务器的 CPU 和存储维度的使用情况保持平衡。

这个示例展示了如何通过 Rebalancer 轻松自然地构建复杂的分配问题，以及 spec 如何提供一种通过调整维度、作用域或分区来表达约束和目标的方式，这些约束和目标可以在许多不同场景中重复使用。

请查阅文档中详尽的 Rebalancer spec 清单。

解决分配问题

一旦使用上述 API 定义了问题，Rebalancer 会将其转换为表达式图。该图的叶节点表示利用率表达式；例如，通过将分配给服务器 A 的任务的内存贡献相加，得到服务器 A 的内存利用率。这些利用率值随后通过聚合节点（如 Max 和 Sum）或转换节点（如 Square 和 Abs）递归组合。请注意，表达式图中每个节点的值取决于当前分配情况，并且每次分配变化时都需要更新。

除了问题目标和约束条件外，建模者还会向 Rebalancer 提供初始分配和停止条件（如时间限制）。Rebalancer 将计算一个优化分配方案，使目标值最小化且不违反任何新约束。初始分配违反的约束将被设为高优先级目标，其违反程度将被最小化，理想情况下降至零。

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

最优求解器。在此模式下，Rebalancer 将表达式图转换为可输入 MIP 求解器（如 FICO Xpress、Gurobi 或 HiGHS）的一组表达式。在转换过程中，Rebalancer 需要通过加权二进制决策变量（每个对象对应一个变量）的求和来表示某个箱子的利用率，这些变量用于指示对象是否被分配到该箱子；这种转换可能导致非常庞大的 MIP 模型！Rebalancer 会自动使用变量聚合（将相似对象合并为单个整数变量）、可替换性以及对称性破坏等技术来减少模型规模，但生成的 MIP 模型最坏情况下的规模仍可能是二次的，即 O(|objects| * |bins|)。我们考虑的最复杂问题规模已超出任何 MIP 求解器的处理能力。

局部搜索求解器通过直接在表达式图上运行克服了这一限制，通过将某些对象移动到其他箱子来探索当前分配的局部邻域。该邻域的最坏情况规模为 O(|objects|+|bins|)，这使得 Rebalancer 能够在不触及内存限制的情况下建模非常大的问题。每次移动都会生成一个新的候选分配方案，Rebalancer 会评估该方案下目标函数和约束条件的新值。在所有候选方案评估完成后，Rebalancer 会应用最优的候选分配方案，即不违反约束且使目标函数提升最大的方案。评估和应用移动的操作会持续进行，直到无法取得进展或达到停止条件。Rebalancer 的局部搜索算法经过高度优化和并行化处理，每次评估的计算成本相对较低（每秒可进行数百万次评估），这使我们能够快速探索搜索空间。此外，Rebalancer 还具备搜索空间剪枝能力，从根本上减少所需的评估次数。

合适的技术方案取决于具体需求。在 Meta，几乎所有大规模问题都采用局部搜索。对于解决时间要求适中的中小型问题，通常使用最优求解器。实践中也常见先用最优求解器进行原型开发，待找到高质量的基准解后迁移至局部搜索。离线场景中，最优求解器可用于调优局部搜索。

Meta 的 Rebalancer 应用

过去十年间，Rebalancer 在 Meta 持续被使用并不断优化。它被用于解决各种基础设施优化问题，包括将分片分配到服务器（Shard Manager）、将服务器分配到服务（RAS）、将全球分布的边缘数据中心流量路由到主数据中心（Taiji）、通过分组无服务器函数提升局部性、在考虑机器学习工作负载优先级的同时平衡各区域的在线机器学习训练负载等。截至本文撰写时，Rebalancer 每天处理约 4000 万个分配问题，涉及 30 多种独特的建模方式。在包含 265,000 个对象和 3,200 个箱子的问题上，第 99 百分位的求解时间为 12 秒。对于包含超过 100 万个对象和 5,000 个箱子的问题，平均求解时间为 171 秒，这类问题每天的运行次数超过 3,400 次。

不出所料，Rebalancer 也被用于解决非基础设施类问题，例如通过分配会议室来最小化差旅时间、将支持工单分配给工程师、优化办公桌布局等。在 Meta 之外，分配问题也广泛存在于医疗、能源与公用事业、交通运输与物流、教育以及应急响应等多个领域。虽然我们自身不具备将 Rebalancer 应用于这些领域的专业知识，但我们希望其他人能够做到这一点。

调试

由于 Rebalancer 让问题建模和求解变得简单，我们发现建模者将大部分工程时间转移到了调试求解器行为上。在没有适当工具的情况下，此类调试需要深入理解求解器的内部机制。随着时间推移，我们识别出建模者常见的疑问和痛点，并构建了专门的 UI 工具来解决这些问题：Rebalancer Explorer。

https://facebook.github.io/rebalancer/videos/rebalancer-explorer-demo.mp4

Explorer 作为 Docker 化的 Web 界面，随 Rebalancer 的开源发布一同推出，它能够帮助用户在使用本地搜索和最优求解器解决分配问题时，快速进行调试和迭代。它能够回答诸如哪些约束条件是起决定性作用的、如果放松某个约束会发生什么、为什么某个对象被放入一个箱子而没有放入另一个箱子等问题。

Rebalancer 的未来

我们一直在努力优化 Rebalancer 的性能，增加新功能，并扩展其对更广泛分配问题的支持。我们很自豪 Rebalancer 是开源项目（Apache 2.0 许可证），我们邀请系统优化领域的专家尝试使用 Rebalancer，并通过识别性能瓶颈、添加新的求解技术、扩展对新问题类型的支持或修复漏洞等方式为项目做贡献。我们期待看到系统和优化社区如何采用、构建和为 Rebalancer 做贡献。

• 代码：Rebalancer GitHub 仓库

• 文档：Rebalancer 介绍

• PyPI：Rebalancer Python 包

• 论文：在超大规模数据中心中优化资源分配：可扩展性、可用性与经验 —— 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。