Meta 开源 Rebalancer：解决资源分配问题的高性能通用库
- Rebalancer，一个在过去九年中一直在 Meta 内部用于解决资源分配问题的分配问题求解器。
- Rebalancer 将几个相关的关注点分离开来：如何指定分配问题、如何在内存中高效存储、如何求解以及如何调试。这种关注点分离对 Rebalancer 的易用性、可扩展性和可维护性至关重要。
- 《Optimizing Resource Allocation in Hyperscale Datacenters: Scalability, Usability, and Experiences》，发表于 OSDI’24。
给定一组对象和一组容器，我们如何将对象分配到容器中，在满足特定约束的同时优化特定目标？
这个问题出现在 Meta 基础设施堆栈的所有层级，例如：
- 硬件放置：机架（对象）需要放置在数据中心（容器）中，以优化机架在电气故障域中的分布，同时满足功率和冷却限制。
- 服务放置：服务器（对象）需要分配给服务（容器），以满足每个服务的需求，同时优化故障容忍度（将服务分配的服务器分散到不同的故障域）和打包效率。
- 任务放置：任务（对象）需要分配到服务器（容器），同时遵守服务器资源限制，并优化故障容忍度和共置需求等目标。
- 流量路由：将来自数十亿用户的流量（对象）路由到地理上分布的数据中心（容器），同时优化网络延迟和数据中心负载。
设计一个可重用的框架来解决此类问题，主要挑战在于其易用性和可扩展性。易用性受到实践者难以将现实生活中的策略转化为正式优化方法所需的精确数学公式的阻碍，而可扩展性则受限于无法通过商业求解器高效解决的 NP-hard 问题。
Rebalancer 通过将问题的描述与求解过程分离，解决了上述两个难题。它提供了一套语言，可以用对象、箱子、约束和目标来描述问题，就像前面的例子那样。问题以这种方式描述后，Rebalancer 会将其转换为一种名为表达式图的有向无环图。其求解算法会利用这张表达式图来设计局部搜索启发式算法，或构建可用商业求解器（FICO Xpress 或 Gurobi）或开源求解器（HiGHS）求解的混合整数规划（MIP）。
描述分配问题
Rebalancer 的描述语言采用三步递进的方式逐步提高抽象层级，以简化使用。
- 第一步，引入核心建模构件，例如维度（对象和箱子的真实世界属性）、分区（对象的分组）、作用域（箱子的分组）和利用率（分配到箱子的对象所做的贡献）。
- 第二步，Rebalancer 提供了一套 API，用于对这些构件以及递归地对其他表达式进行常用转换。例如，可以对多个箱子的利用率使用 SUM/MAX 操作进行聚合，或使用 SQUARE 操作进行变换。
- 第三步，在这些表达式的基础上，Rebalancer 提供了一个高层 spec API，内置了数十种常见的目标和约束。可以把每个 spec 理解为一个预定义的“配方”：它接收若干建模构件和附加参数作为输入，并借助表达式 API 生成数学公式。
在上述示例中，任务被建模为对象，服务器被建模为放置这些任务的容器（bins）。服务器在物理上位于机架（racks）中，这种分组关系被建模为作用域（scope）。任务会消耗一定量 CPU 和存储空间，而服务器在这两个资源上的容量有限，因此将 CPU 和存储建模为维度（dimensions）。
服务器的利用率对应于分配到该服务器的所有任务的资源总和，其利用率上限通过 CapacitySpec 进行定义。如果简单的求和方式不适用于利用率的计算，可以使用表达式 API 来修改计算逻辑。
此外，我们将任务归属于某个作业（job）。像这样的对象分组称为分区（partition），并使用 GroupCountSpec 来确保每个机架仅被分配单一类型的作业（分区）。BalanceSpec 则保证服务器在 CPU 和存储两个维度上的利用率保持均衡。
该示例展示了如何利用 Rebalancer 轻松且自然地构建复杂的指派问题，并说明通过改变维度、作用域或分区，规范（specs）可以以多种不同方式表达可复用的约束和目标。
请在文档中查看 Rebalancer 规范的完整列表。
求解指派问题
一旦通过上述 API 定义好问题，Rebalancer 会将其转换为表达式图（expression graph）。图中叶节点表示利用率表达式；例如，通过对分配到服务器 A 的任务的内存贡献求和，得到服务器 A 的内存利用率。随后，这些利用率值通过 Max、Sum 等聚合节点，或 Square、Abs 等变换节点进行递归组合。需要注意的是，表达式图中每个节点的值都依赖于当前的分配状态，因此每当分配发生变化时，这些值都需要相应更新。
除了目标函数和约束条件，建模者还需向 Rebalancer 提供初始分配方案以及停止条件（例如时间上限）。Rebalancer 将计算出一个优化的分配方案，以最小化目标函数值且不违反任何新约束。对于初始方案中已违反的约束，系统会将其转化为高优先级目标并极力消除违规，理想情况下违规量为零。
Rebalancer 提供两种不同的技术来解决分配问题。
最优求解器。在此模式下，Rebalancer 将表达式图转换为一组表达式，以便输入 MIP 求解器，例如 FICO Xpress、Gurobi 或 HiGHS。在转换过程中，Rebalancer 需要通过二进制决策变量（每个对象对应一个）的加权和来表示箱子的利用率，以指示对象是否被分配到该箱子；这可能导致生成极其庞大的 MIP 模型！Rebalancer 自动采用变量聚合（将相似对象合并为单个整数变量）、可互换性和对称消除等技术来缩减模型规模，但生成的 MIP 模型在最坏情况下的规模仍可能呈二次方增长，即 O(|objects| * |bins|)。我们所考虑的最大问题对于任何 MIP 求解器而言都过于庞大。
Local Search Solver 直接在表达式图上操作，克服了这一局限：它通过将部分对象移动到其他 bin，探索当前分配方案的局部邻域。该邻域在最坏情况下的规模为 O(|objects|+|bins|)，因此 Rebalancer 即使建模超大规模问题也不会触及内存上限。每次移动都会生成一个新的候选分配方案，Rebalancer 会评估其目标和约束的新值。完成所有候选方案评估后，Rebalancer 采用最优的候选方案，即不违反约束且目标值改善最大的那个。这个“评估—采用”的过程会不断重复，直到无法继续改进或满足停止条件。Rebalancer 的局部搜索算法经过高度优化和并行化，单次评估成本很低（每秒可完成数百万次评估），从而能快速探索解空间。此外，Rebalancer 还懂得如何剪枝，从源头上减少所需的评估次数。
选择哪种求解技术取决于实际需求。在 Meta，几乎所有大规模问题都使用局部搜索；求解时间要求适中、规模中小的问题则常用最优求解器。常见的做法是先用最优求解器做原型，在得到高质量基线解后再迁移到局部搜索。在离线场景下，最优求解器还可用于调优局部搜索。
Rebalancer 在 Meta 的应用
过去十年，Rebalancer 在 Meta 持续使用并不断完善，解决大量基础设施优化问题，包括将数据分片分配到服务器（Shard Manager）、服务器分配给服务（RAS）、将全球分布式边缘数据中心的流量路由到主数据中心（Taiji）、分组无服务器函数以提升局部性、平衡跨区域的在线 ML 训练负载（同时考虑 ML 负载的优先级）等。截至本文撰写时，Rebalancer 每天解决约 4000 万个分配问题，涵盖 30 种以上不同的问题形式。对于包含 26.5 万个对象和 3200 个分桶的问题，P99 求解时间为 12 秒。对于包含超过 100 万个对象和 5000 个分桶的问题，平均求解时间为 171 秒，此类求解运行超过 3400 次。
不出所料，Rebalancer 也用于解决非基础设施问题，例如将会议分配到会议室以缩短通勤时间、将支持工单分配给工程师、优化办公桌布局等。在 Meta 之外，分配问题也广泛存在于医疗、能源与公用事业、交通物流、教育和应急响应等领域。虽然我们不具备将这些领域的专业知识应用于 Rebalancer 的条件，但我们期待他人能这样做，并且希望他们能做到。
调试
由于 Rebalancer 让问题建模和求解变得轻松，我们发现建模工程师的大部分工程时间都转到了调试求解器行为上。在没有合适的工具时，这类调试需要对求解器内部机制有深入理解。
随着时间推移，我们梳理了建模工程师常见的疑问和痛点，并构建了一个专门的 UI 工具来回答这些问题：Rebalancer Explorer。
在此次开源发布中，Explorer 作为 Rebalancer 的配套工具一同亮相。这是一个 Docker 化的 Web 界面，旨在帮助用户在利用局部搜索和最优求解器解决实际问题时，实现快速的调试与迭代。它有助于解答诸如哪些约束条件是紧的、若放松某项约束会产生什么影响、以及为何某个对象被分配到一个容器而非另一个容器等问题。
Rebalancer 的未来
我们持续致力于优化 Rebalancer 的性能，增加新功能，并扩展其对更多类型分配问题的支持。Rebalancer 自豪地采用 Apache 2.0 许可证开源。我们诚邀系统专家和运筹学领域的专家尝试使用 Rebalancer，并参与项目贡献：无论是识别性能瓶颈、新增求解技术、扩展以支持新型问题，还是修复 Bug。我们期待看到系统和运筹学社区如何采用、构建并为 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。