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

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

By Richard Barnes, Neeraj Kumar, Pol Mauri Ruiz 作者：Richard Barnes, Neeraj Kumar, Pol Mauri Ruiz

We’re open-sourcing Rebalancer, the assignment-problem solver that has been used to solve resource allocation problems throughout Meta for over nine years. Rebalancer separates several related concerns: how to specify an assignment problem, how to store it efficiently in memory, how to solve it, and how to debug it. This separation of concerns is crucial to Rebalancer’s usability, scalability, and extensibility. For a more detailed technical exposition, see the accompanying paper, “Optimizing Resource Allocation in Hyperscale Datacenters: Scalability, Usability, and Experiences,” published at OSDI’24. 我们正在开源 Rebalancer，这是一个在 Meta 内部使用了九年多，用于解决资源分配问题的分配问题求解器。Rebalancer 将几个相关的问题分离开来：如何定义分配问题、如何将其高效地存储在内存中、如何求解以及如何调试。这种关注点分离对于 Rebalancer 的易用性、可扩展性和可扩展性至关重要。如需更详细的技术说明，请参阅在 OSDI’24 上发表的配套论文《Optimizing Resource Allocation in Hyperscale Datacenters: Scalability, Usability, and Experiences》。

Given a set of objects and a set of bins, how do we assign objects to bins in a way that optimizes specific objectives while meeting certain constraints? This question arises at all layers of Meta’s infrastructure stack including in: 给定一组对象和一组容器，我们如何将对象分配给容器，从而在满足特定约束的同时优化目标？这个问题出现在 Meta 基础设施堆栈的各个层面，包括：

Hardware placement: racks (objects) need to be positioned in datacenters (bins) to optimize the spread of racks across electrical fault domains while honoring power and cooling limitations.
硬件放置： 需要将机架（对象）放置在数据中心（容器）中，以优化机架在电力故障域中的分布，同时遵守电力和冷却限制。
Service placement: servers (objects) need to be assigned to services (bins) in order to meet each service’s demand while optimizing for goals such as fault tolerance (spread a service’s allocated servers across failure domains) and packing efficiency.
服务放置： 需要将服务器（对象）分配给服务（容器），以满足每个服务的需求，同时优化容错（将服务分配的服务器分散在故障域中）和打包效率等目标。
Task placement: tasks (objects) need to be allocated to servers (bins) while honoring server resource limits and optimizing for goals such as fault tolerance and co-location requirements.
任务放置： 需要将任务（对象）分配给服务器（容器），同时遵守服务器资源限制，并优化容错和共置要求等目标。
Traffic routing: Route traffic (objects) from billions of users to geographically distributed datacenters (bins) while optimizing network latency and datacenter load.
流量路由： 将来自数十亿用户的流量（对象）路由到地理分布的数据中心（容器），同时优化网络延迟和数据中心负载。

The main challenges to designing a reusable framework for solving problems like these are its usability and scalability. Usability is impeded by practitioners struggling to translate real-life policies into the precise mathematical formulas required by formal optimization methods, while scalability is hampered by NP-hard problems that cannot be solved efficiently by commercial solvers. Rebalancer addresses both of these challenges by separating a problem’s specification from its solution. 设计一个用于解决此类问题的可重用框架，其主要挑战在于易用性和可扩展性。易用性受到阻碍，因为从业者难以将现实生活中的策略转化为形式化优化方法所需的精确数学公式；而可扩展性则受到 NP-hard 问题的限制，这些问题无法通过商业求解器高效解决。Rebalancer 通过将问题的定义与求解过程分离，解决了这两个挑战。

Rebalancer provides a language for describing problems using objects, bins, constraints, and objectives, as in the examples above. Once a problem is described in this way, Rebalancer transforms the problem into a directed-acyclic graph called an expression graph. Rebalancer’s solving algorithm uses the expression graph to either design a local search heuristic or to build a mixed integer program (MIP) solvable with either a commercial (FICO Xpress or Gurobi) or open source solver (HiGHS). Rebalancer 提供了一种语言，可以使用上述示例中的对象、容器、约束和目标来描述问题。一旦以这种方式描述了问题，Rebalancer 就会将问题转换为一个称为“表达式图”的有向无环图。Rebalancer 的求解算法利用表达式图来设计局部搜索启发式算法，或者构建一个可以通过商业求解器（FICO Xpress 或 Gurobi）或开源求解器（HiGHS）求解的混合整数规划（MIP）。

Specifying Assignment Problems

定义分配问题

Rebalancer’s specification language employs a three-step approach to incrementally elevate the level of abstraction for ease of use. First, it introduces essential modeling constructs, such as dimensions (the real-world attributes of objects and bins), partitions (groupings of objects), scopes (groupings of bins), and utilization (contribution of objects assigned to a bin). Rebalancer 的定义语言采用三步法，逐步提高抽象级别以方便使用。首先，它引入了基本的建模结构，例如维度（对象和容器的现实世界属性）、分区（对象的组合）、作用域（容器的组合）以及利用率（分配给容器的对象的贡献）。

Next, Rebalancer provides an API to expose commonly used expressions for transformations on these constructs, as well as recursively on other expressions. For example, the utilization of several bins can be aggregated using a SUM/MAX operation, or transformed using a SQUARE operation. Finally, leveraging these expressions, Rebalancer exposes a high-level spec API implementing dozens of common objectives and constraints. One can think of each spec as a predefined recipe which accepts some modeling constructs and additional parameters as input, and creates a mathematical formula using the expression API. 接下来，Rebalancer 提供了一个 API，用于公开对这些结构进行转换的常用表达式，并可递归地应用于其他表达式。例如，可以使用 SUM/MAX 操作聚合多个容器的利用率，或者使用 SQUARE 操作进行转换。最后，利用这些表达式，Rebalancer 公开了一个高级规范 API，实现了数十种常见的目标和约束。可以将每个规范视为一个预定义的配方，它接受一些建模结构和附加参数作为输入，并使用表达式 API 创建数学公式。

An example of modeling constructs and specs for a task placement problem. In the example above, tasks are modeled as objects and servers are modeled as bins into which tasks are to be placed. Servers are physically situated in racks; this grouping is modeled as a scope. Tasks take a certain amount of CPU and storage and servers have a limited amount of each. CPU and storage are modeled as dimensions. The CPU and storage utilization of a server corresponds to the sum of all of the tasks assigned to that server and the server’s utilization limits are modeled using a CapacitySpec. The expression API could be used to change how the utilization is calculated if a simple sum isn’t appropriate. 这是一个任务放置问题的建模结构和规范示例。在上面的示例中，任务被建模为对象，服务器被建模为放置任务的容器。服务器物理上位于机架中；这种分组被建模为作用域。任务占用一定量的 CPU 和存储空间，而服务器对每种资源都有一定的限制。CPU 和存储被建模为维度。服务器的 CPU 和存储利用率对应于分配给该服务器的所有任务的总和，服务器的利用率限制使用 CapacitySpec 进行建模。如果简单的求和不合适，可以使用表达式 API 来更改利用率的计算方式。

Further, we model tasks as belonging to jobs. A grouping of objects like this is called a partition and we use a GroupCountSpec to ensure that each rack has only a single job type (partition) assigned to it. A BalanceSpec ensures that each server’s utilization is balanced across both its CPU and storage dimensions. This example demonstrates how complex assignment problems can be easily and naturally constructed using Rebalancer and how specs provide a way of expressing constraints and goals that can be re-used in many different ways by varying dimensions, scopes, or partitions. Please check out an exhaustive list of Rebalancer specs in the docs. 此外，我们将任务建模为属于作业。这种对象分组称为分区，我们使用 GroupCountSpec 来确保每个机架只分配有一种作业类型（分区）。BalanceSpec 确保每个服务器的利用率在其 CPU 和存储维度之间保持平衡。这个例子展示了如何使用 Rebalancer 轻松自然地构建复杂的分配问题，以及规范如何提供一种表达约束和目标的方法，这些约束和目标可以通过改变维度、作用域或分区以多种不同的方式重用。请在文档中查看 Rebalancer 规范的完整列表。

Solving Assignment Problems

求解分配问题

Once a problem is specified using the API described above, Rebalancer translates it into an expression graph. The leaf nodes in this graph represent utilization expressions; for example, the memory utilization of server A, as obtained by summing the memory contribution of tasks assigned to server A. These utilization values are then recursively composed using aggregation nodes such as Max and Sum, or transformation nodes such as Square and Abs. Note that the value of each node in the expression graph depends on the current assignment and needs to be updated every time the assignment changes. Along with the problem objectives and constraints, modelers also provide Rebalancer with an initial assignment and a stopping condition, such as a time limit. Rebalancer will compute an optimized assignment that minimizes the objective value and does not violate any new constraints. 一旦使用上述 API 定义了问题，Rebalancer 就会将其转换为表达式图。该图中的叶节点代表利用率表达式；例如，服务器 A 的内存利用率，通过对分配给服务器 A 的任务的内存贡献求和获得。然后，这些利用率值使用聚合节点（如 Max 和 Sum）或转换节点（如 Square 和 Abs）进行递归组合。请注意，表达式图中每个节点的值取决于当前的分配，并且每次分配更改时都需要更新。除了问题目标和约束外，建模者还向 Rebalancer 提供初始分配和停止条件（例如时间限制）。Rebalancer 将计算出一个优化的分配方案，该方案在最小化目标值的同时，不会违反任何新的约束。