Meta Platforms has open-sourced Rebalancer, a high-performance C++ library with a Python interface designed to tackle complex assignment problems. Instrumental in Meta's internal resource allocation for over nine years, this robust system currently processes approximately 40 million placement challenges daily.
Released under the Apache 2.0 license, Rebalancer includes comprehensive documentation, a PyPI package for straightforward installation (supporting Python 3.12+ and various operating systems), and a dedicated debugging UI called Rebalancer Explorer. The project is currently designated as Alpha on PyPI.
Addressing Hyperscale Allocation Challenges
Efficient resource distribution is a persistent challenge in large-scale tech infrastructures. Meta regularly faces this, from allocating servers to services to routing user traffic across data centers. Core difficulties include translating intricate operational policies into precise, solvable formulas and managing the immense scale of many NP-hard problems that often overwhelm traditional commercial solvers.
Rebalancer tackles this by distinctly separating problem specification from its solution method, a methodology detailed in the OSDI 2024 paper, "Optimizing Resource Allocation in Hyperscale Datacenters."
Rebalancer's Core Architecture
The system leverages a flexible specification layer and an intelligent dual-solver strategy.
-
The Specification Layer
This layer allows engineers to define allocation problems using constructs like dimensions (e.g., CPU), partitions, scopes, and utilization. An Expression API supports metric aggregation (SUM, MAX) and transformation (SQUARE), while a Spec API provides predefined objectives and constraints. This enables precise modeling of rules, such as server capacity limits or balanced resource distribution.
-
Dual-Solver Approach
Rebalancer compiles specifications into a directed acyclic expression graph and employs two distinct solvers:
- Optimal Solver: Transforms the graph into a mixed integer program (MIP) for solvers like Gurobi or HiGHS. Effective for small to medium-sized problems, its worst-case scaling (proportional to objects multiplied by bins) limits its use for Meta's largest challenges.
- Local Search Solver: Operating directly on the expression graph, this solver efficiently explores object reassignments. Its favorable scaling (proportional to the sum of objects and bins) makes it ideal for large-scale problems, achieving millions of evaluations per second via parallelization and search space pruning. Meta primarily utilizes local search for its most extensive problems, with MIP for prototyping or smaller tasks.
Proven Performance and Diverse Applications
Rebalancer's impressive performance within Meta's production environment includes:
- Resolving over 40 million assignment problems daily across 30+ unique formulations.
- A 99th percentile solve time of just 12 seconds for problems with 265,000 objects and 3,200 bins.
- An average solve time of 171 seconds for massive problems (over one million objects and 5,000 bins), with thousands of such runs recorded.
Applications include distributing tasks and containers across clusters, balancing network traffic and workloads geographically, and operational assignments like matching support tickets to engineers or meetings to rooms.
Rebalancer Explorer: Enhancing Debugging
To aid developers, Rebalancer Explorer, a Dockerized web UI, is included. This tool provides vital insights into solver behavior, detailing binding constraints, relaxation effects, and clear explanations for object placements.
This article is a rewritten summary based on publicly available reporting. For the original story, visit the source.
Source: MarkTechPost
