开源Rebalancer：一个用于解决分配问题的通用高性能库
内容提要
Meta开源了通用高性能资源分配库Rebalancer，已在内部使用超九年。它分离问题描述与求解，支持最优求解器和局部搜索求解器，每天解决约4000万个分配问题，并附带调试工具Rebalancer Explorer，采用Apache 2.0许可证。
延伸解读
两种求解器的适用场景
Rebalancer提供最优求解器和局部搜索求解器。最优求解器将问题转化为混合整数规划，适合中小规模问题，但模型规模最坏可达O(|objects|*|bins|)，超大问题无法求解。局部搜索直接在图结构上操作，邻域规模为O(|objects|+|bins|)，能处理超大规模问题。Meta内部几乎所有大规模问题都使用局部搜索，中小规模且对求解时间要求不苛刻的问题则用最优求解器。常见做法是先用最优求解器原型验证，再迁移到局部搜索。
性能数据揭示的规模边界
文章给出了具体性能指标：每天解决约4000万个分配问题，超过30种问题形式。对于26.5万对象、3200个箱的问题，P99求解时间为12秒；对于超过100万对象、5000个箱的问题，平均求解时间为171秒，此类运行超过3400次。这些数据表明Rebalancer能处理千万级对象的大规模问题，但求解时间随规模增长明显。读者可据此评估自身问题是否在适用范围内，并注意局部搜索在超大问题上的优势。
调试工具Rebalancer Explorer的价值
随着问题建模和求解变得容易，工程师的大部分时间转移到了调试求解器行为上。Rebalancer Explorer是一个Docker化的Web UI，随开源版本一同发布，帮助回答哪些约束是绑定的、放宽约束会有什么影响、为什么某个对象被分配到某个箱而非其他箱等问题。它降低了调试对求解器内部理解的依赖，能加速迭代。对于采用Rebalancer的团队，Explorer是减少调试成本的关键工具，建议在开发流程中尽早引入。
Q&A
Rebalancer是什么？它主要用来解决什么问题？
Rebalancer是Meta开源的一个通用高性能库，用于解决分配问题。它可以将一组对象分配到一组箱子中，在满足约束的同时优化特定目标。
Rebalancer支持哪些求解方法？它们分别适用于什么场景？
Rebalancer支持最优求解器和局部搜索求解器。最优求解器将问题转化为混合整数规划（MIP），适用于中小规模问题；局部搜索求解器直接在表达式图上工作，适用于大规模问题。在Meta，几乎所有大规模问题都使用局部搜索，中小规模问题常用最优求解器，也常先用最优求解器原型验证再迁移到局部搜索。
Rebalancer在Meta内部有哪些实际应用？
Rebalancer在Meta内部用于解决多种基础设施优化问题，包括：将分片分配到服务器（Shard Manager）、将服务器分配到服务（RAS）、将流量从边缘数据中心路由到主数据中心（Taiji）、对无服务器函数进行分组以提高局部性、平衡跨区域的在线ML训练工作负载等。此外，还用于非基础设施问题，如分配会议室、分配支持工单、优化办公桌摆放等。
Rebalancer的规格语言是如何工作的？
Rebalancer的规格语言采用三步法逐步提升抽象级别：首先引入基本建模构造，如维度、分区、作用域和利用率；然后提供API暴露常用表达式，支持对构造进行转换和递归组合；最后提供高级规格API，实现数十种常见目标和约束。每个规格可视为预定义配方，接受建模构造和参数，生成数学公式。
Rebalancer的局部搜索求解器是如何工作的？
局部搜索求解器直接在表达式图上工作，通过将一些对象移动到另一个箱子来探索当前分配的局部邻域。每个移动生成一个新的候选分配，Rebalancer评估所有候选的目标和约束值，然后应用最佳候选（不违反约束且最大程度改进目标）。重复此过程直到无法改进或达到停止条件。该算法高度优化和并行化，每秒可进行数百万次评估，并能修剪搜索空间。
Rebalancer Explorer是什么？它有什么作用？
Rebalancer Explorer是一个Docker化的Web UI工具，随Rebalancer一起开源，用于快速调试和迭代。它帮助回答诸如哪些约束是绑定的、如果放松约束会发生什么、为什么某个对象被放在某个箱子而不是另一个等问题。
Rebalancer的许可证是什么？如何获取代码和文档？
Rebalancer采用Apache 2.0许可证。代码可在Rebalancer GitHub仓库获取，文档有“Introducing to Rebalancer”和PyPI上的Rebalancer Python包，相关论文发表于OSDI 2024。
