Rebalancer: A Generic Library for Solving Resource Assignment Problems at Scale
Meta's Rebalancer is an open-source library designed to solve large-scale resource assignment problems across various infrastructure layers. It addresses challenges in usability and scalability by separating problem specification from solution, offering both optimal (MIP-based) and highly optimized local search solvers. This tool has been critical for managing resource allocation for tasks, services, and hardware within Meta's hyperscale datacenters for nearly a decade.
Read original on Meta EngineeringThe Rebalancer library from Meta provides a generic, high-performance solution for assignment problems, which are pervasive in large-scale distributed systems. These problems involve assigning "objects" to "bins" while optimizing objectives and adhering to constraints. Examples include placing servers in racks, tasks on servers, or routing traffic to datacenters. The core challenge is translating real-world policies into mathematical models and solving NP-hard problems efficiently.
Separation of Concerns for Usability and Scalability
Rebalancer tackles usability by offering a high-level language for problem specification using constructs like dimensions, partitions, scopes, and utilization. This abstraction simplifies the process of defining complex constraints and objectives, making it accessible to practitioners without deep optimization expertise. The library provides an API with dozens of predefined "specs" (recipes) for common objectives and constraints, which can be combined to model intricate scenarios.
Solving Assignment Problems: Optimal vs. Local Search
Once a problem is specified, Rebalancer translates it into an expression graph. It offers two primary solving techniques:
- Optimal Solver: Translates the expression graph into a Mixed Integer Program (MIP) solvable by commercial (FICO Xpress, Gurobi) or open-source (HiGHS) solvers. It uses techniques like variable aggregation and symmetry breaking to reduce model size, but still faces scalability limits for very large problems (quadratic worst-case size).
- Local Search Solver: Works directly on the expression graph, exploring local neighborhoods of the current assignment. This method is highly optimized and parallelized, allowing for millions of evaluations per second and efficient handling of massive problems (worst-case size O(|objects|+|bins|)), making it suitable for Meta's largest production workloads.
When to Choose Which Solver
For small to mid-sized problems with moderate solve time requirements, the optimal solver can provide exact solutions. For large-scale problems, especially those in production environments like Meta's, the local search solver is preferred due to its superior scalability and speed, even if it yields near-optimal solutions. It's also common to prototype with optimal solvers and then migrate to local search after establishing a baseline solution.
Debugging with Rebalancer Explorer
To aid in debugging the solver's behavior, Rebalancer includes a specialized UI tool called Rebalancer Explorer. This Dockerized web UI helps modelers understand which constraints are binding, explore the impact of relaxing constraints, and analyze why specific assignments were made, significantly reducing debugging time and effort.