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

我们正在开源 Rebalancer。这款分配问题求解器已在 Meta 用于解决各类资源分配问题，时间超过九年。

Rebalancer 将几个相关关注点分离：如何描述分配问题、如何在内存中高效存储问题、如何求解，以及如何调试。这种分离对 Rebalancer 的易用性、可扩展性和扩充能力至关重要。

更详细的技术说明见 OSDI’24 论文《超大规模数据中心资源分配优化：可扩展性、易用性与实践经验》。

观看原文视频介绍

给定一组对象和一组容器，如何将对象分配到容器，使指定目标最优，同时满足约束？

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

• 硬件放置：机架是对象、数据中心是容器。在遵守供电与散热限制的同时，优化机架在电气故障域之间的分布。
• 服务放置：将服务器（对象）分配给服务（容器），满足各项服务的需求，同时优化容错——将某服务分配到的服务器分散在不同故障域——以及装箱效率等目标。
• 任务放置：把任务（对象）分配到服务器（容器），遵守服务器资源限制，同时优化容错和共同放置要求等目标。
• 流量路由：将数十亿用户的流量（对象）路由到地理上分散的数据中心（容器），同时优化网络延迟和数据中心负载。

为这类问题设计可复用框架，主要难点是易用性和可扩展性。实践者难以把现实策略转化为形式化优化方法所需的精确数学公式，妨碍了易用性；商业求解器无法高效解决 NP-hard 问题，则限制了可扩展性。

Rebalancer 通过分离问题描述与求解应对这两项挑战。它提供一种语言，使用对象、容器、约束和目标描述问题。随后，它把问题转化为一个称为表达式图的有向无环图。求解算法利用表达式图构建局部搜索启发式方法，或生成混合整数规划（MIP），交给商业求解器 FICO Xpress、Gurobi 或开源求解器 HiGHS 求解。

描述分配问题

Rebalancer 的描述语言通过三步逐渐提高抽象层级，以改善易用性：

1. 首先引入基本建模构件：维度（对象和容器的现实属性）、分区（对象的分组）、范围（容器的分组），以及利用量（分配到某容器的对象产生的贡献）。
2. 然后提供 API，用常见表达式变换这些构件，也可递归地变换其他表达式。例如，可用 SUM/MAX 聚合多个容器的利用量，或用 SQUARE 进行变换。
3. 最后基于这些表达式提供高级 spec API，实现数十种常见目标和约束。每个 spec 都可以看作预定义配方：接收建模构件和额外参数，通过表达式 API 创建数学公式。

上例把任务建模为对象，服务器建模为放置任务的容器。服务器实际位于机架内，这种分组被建模为范围。任务需要一定量的 CPU 与存储，而服务器各自的容量有限；CPU 与存储被建模为维度。服务器的 CPU 和存储利用量，等于分配给该服务器的所有任务贡献之和；利用量上限通过 CapacitySpec 建模。如果简单求和不适合，也可以用表达式 API 改变利用量的计算方式。

此外，任务属于作业。这类对象分组称为分区。我们使用 GroupCountSpec 确保每个机架只分配一种作业类型（分区），再用 BalanceSpec 确保各服务器在 CPU 和存储两个维度上的利用量保持均衡。

这个例子展示了如何用 Rebalancer 轻松、自然地构建复杂分配问题；改变维度、范围或分区，就能以不同方式复用 spec 表达的约束和目标。

完整 spec 列表见Rebalancer 文档。

求解分配问题

问题通过上述 API 描述后，Rebalancer 将其转化为表达式图。叶节点代表利用量表达式，例如服务器 A 的内存利用量：把分配到 A 的任务的内存贡献相加所得。随后通过 Max、Sum 等聚合节点，或 Square、Abs 等变换节点，递归组合这些值。每个节点的值依赖当前分配；分配改变时，节点值必须更新。

建模者除了提供目标和约束，还要给出初始分配及停止条件，例如时间限制。Rebalancer 计算一个优化后的分配，使目标值最小且不违反任何新的约束。初始分配已经违反的约束会变成高优先级目标，其违反程度会尽量减小，理想情况下减到零。

Rebalancer 提供两种不同求解技术。

最优求解器

在这一模式下，表达式图被转换为可交给 FICO Xpress、Gurobi 或 HiGHS 等 MIP 求解器的表达式集合。转换时，容器利用量必须表示为二元决策变量的加权和：每个对象对应一个变量，表示它是否被分配到该容器。这可能产生非常大的 MIP 模型。

Rebalancer 自动使用变量聚合——将相似对象压缩为一个整数变量——以及可互换性和对称性破除等技术缩减模型。但生成的 MIP 模型在最坏情况下仍可能是二次规模，即 O(|objects| * |bins|)。我们所处理的最大问题，超过了任何 MIP 求解器的承受范围。

局部搜索求解器

局部搜索直接在表达式图上工作，通过把部分对象移动到其他容器来探索当前分配的局部邻域，从而克服这一限制。邻域在最坏情况下的规模是 O(|objects|+|bins|)，使 Rebalancer 能在不触及内存限制的情况下建立极大问题的模型。

每次移动都会产生一个新的候选分配，Rebalancer 对其重新计算目标与约束值。评估完所有候选后，应用最好的候选：不违反约束，并使目标改善最多的那一个。这个评估与应用移动的过程会持续重复，直到无法继续改善或达到停止条件。局部搜索算法经过大量优化和并行化，使每次评估开销较低，每秒可进行数百万次评估，因而能快速探索搜索空间。此外，它还会剪枝，首先减少所需评估次数。

选择哪种技术取决于需求。在 Meta，几乎所有大规模问题都使用局部搜索。求解时间要求适中的小型到中型问题，通常使用最优求解器。常见做法是先用最优求解器制作原型，找到高质量基线后再迁移到局部搜索；离线时还可用最优求解器调优局部搜索。

Meta 中的 Rebalancer

过去十年，Meta 一直持续使用和改进 Rebalancer。它解决了广泛的基础设施优化问题，包括将分片分配到服务器（Shard Manager）、将服务器分配给服务（RAS）、把全球分布式边缘数据中心的流量路由到主数据中心（Taiji）、将无服务器函数分组以改善局部性，以及考虑机器学习工作负载优先级来平衡跨区域在线训练负载等。

截至原文撰写时，Rebalancer 每天求解约4000万个分配问题，涉及超过30种不同问题表述。对于包含26.5万个对象和3200个容器的问题，P99求解时间为12秒。对于超过100万个对象和5000个容器的问题，平均求解时间为171秒，此类运行超过3400次。这些数字对应原文的 Meta 内部问题与实验条件。

Rebalancer 也用于非基础设施问题，例如将会议分配到会议室以缩短路程、将支持工单分配给工程师，以及优化工位放置。在 Meta 之外，医疗、能源与公用事业、交通与物流、教育、应急响应等许多领域都存在分配问题。虽然我们没有专业知识亲自将 Rebalancer 应用于这些领域，但希望其他人有这样的能力，并付诸实践。

调试

当 Rebalancer 让问题建模和求解更容易后，我们发现建模者的大部分工程时间转移到了调试求解器行为上。没有适当工具，这类调试需要深入理解求解器内部。

我们逐步识别了建模者常见的问题与痛点，并为回答这些问题构建了专门的界面工具：Rebalancer Explorer。

观看 Rebalancer Explorer 演示视频

Explorer 与 Rebalancer 一同开源，是一个 Docker 化的 Web 界面，支持使用局部搜索和最优求解器时快速调试与迭代。它能帮助回答哪些约束正在起限制作用、放宽某项约束会发生什么，以及为什么某对象被放入这个容器而不是另一个容器等问题。

Rebalancer 的未来

我们一直在优化性能、添加新能力，并扩展对更多分配问题的支持。Rebalancer 以 Apache 2.0 许可证开源。欢迎系统与优化专家试用并贡献：识别性能瓶颈、加入新求解技术、支持新类型问题，或修复缺陷。我们期待系统与优化社区采用、构建和贡献 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。

来源：开源 Rebalancer：用于求解分配问题的通用高性能库。作者：Richard Barnes、Neeraj Kumar、Pol Mauri Ruiz（2026年9月21日）。本文为中文译文，文中的“我们”指原作者所在的 Meta 团队。文章版权归 Meta 及原作者所有。文中所述 Rebalancer 软件以 Apache 2.0 许可证开源；此软件许可不自动等同于本文或配图许可。