Meta AI Open-Sources C++ Assignment Solver Rebalancer

Meta AI has open-sourced Rebalancer, a C++ library featuring a Python interface, designed to solve assignment problems. These problems involve determining the optimal allocation of objects into bins while adhering to specific constraints and objectives. Rebalancer has been instrumental in Meta's internal resource allocation processes for over nine years, as detailed in an Engineering at Meta blog post. The library is now publicly available under the Apache 2.0 license, complete with comprehensive documentation, a Python Package Index (PyPI) package, and an integrated debugging tool named Rebalancer Explorer. Installation is straightforward via pip, with version 1.0.4 supporting Python 3.12 and later, offering prebuilt wheels for Linux x86-64 and macOS 14+ ARM64 architectures. Additionally, .deb, .rpm, and Homebrew packages are provided. Despite its robust functionality, the project is currently classified as 'Alpha' on PyPI. Assignment problems are ubiquitous across Meta's infrastructure, encompassing tasks such as assigning racks to datacenters, servers to services, and user traffic to datacenters. Meta identified two primary challenges that Rebalancer addresses: usability and scalability. Engineers previously faced difficulties translating complex policies into precise mathematical formulas, and many assignment problems are NP-hard, exceeding the capabilities of commercial solvers. Rebalancer's architecture tackles these issues by decoupling the problem specification from the solving mechanism. The design principles are further elaborated in the OSDI 2024 paper titled "Optimizing Resource Allocation in Hyperscale Datacenters." The specification layer of Rebalancer is structured into three tiers. The first tier, Modeling constructs, defines fundamental elements like dimensions (e.g., CPU, storage), partitions (groups of objects), scopes (groups of bins), and utilization metrics. The second tier, the Expression API, allows for the aggregation of utilization data using functions like SUM or MAX, and transformations through operations such as SQUARE. The third tier, the Spec API, provides a collection of dozens of predefined objectives and constraints, which are thoroughly documented. For instance, Meta models tasks as objects, servers as bins, and racks as a scope. A CapacitySpec can be used to limit the CPU and storage capacity of each server, while a GroupCountSpec ensures that only one job type is assigned to a particular rack. A BalanceSpec aims to equalize the utilization across both CPU and storage dimensions for each server. Rebalancer compiles these specifications into a directed acyclic expression graph. The leaf nodes of this graph represent utilization values, and aggregation operations are performed as the graph is traversed.