Meta open-sources Rebalancer for large-scale assignment problems

Meta has open-sourced Rebalancer, the assignment library it has used internally for more than nine years to place hardware, schedule tasks, allocate services, and route traffic. The Apache 2.0 project is available on GitHub and PyPI with Rebalancer Explorer, a companion interface for debugging models and solver runs. Meta describes the release in its engineering post.

The library targets a recurring infrastructure problem: assigning many objects to a set of bins while satisfying resource limits, placement policies, and optimization goals. Its shared modeling layer can feed an exact mixed-integer programming solver or a parallel local-search engine, allowing teams to validate smaller models and then apply the same formulation to larger workloads.

Millions of choices, one assignment

An assignment model chooses where each object belongs. A task may need a server with enough CPU and memory; a rack may need an electrical fault domain with sufficient power and cooling; user traffic may need a datacenter with available capacity and low network latency. Constraints define valid placements, while objectives rank the feasible results.

Many useful assignment formulations are NP-hard, so the cost of exact solving rises quickly with the number of objects, bins, and constraints. Translating operational policies into mathematical expressions creates another obstacle, particularly for engineers without an operations-research background. Rebalancer addresses both issues by separating policy specification from model representation, solving, and debugging.

Meta uses the library for several classes of infrastructure work:

• Hardware placement: Distributing racks across electrical fault domains while respecting power and cooling limits.
• Service placement: Assigning servers to services for fault tolerance and packing efficiency.
• Task placement: Scheduling tasks on servers under CPU, memory, and co-location constraints.
• Traffic routing: Directing traffic from billions of users to geographically distributed datacenters while managing latency and load.

A compact vocabulary for policy

Rebalancer gives model authors a small set of concepts for describing objects, bins, resources, and groupings:

High-level specifications encode common policies. CapacitySpec applies capacity limits, GroupCountSpec controls how groups are distributed, and BalanceSpec expresses balancing objectives. These building blocks reduce the amount of solver-specific mathematics that application developers must write.

Rebalancer converts the completed specification into a directed acyclic graph called an expression graph. The graph captures the calculations behind constraints and objectives, then serves as the common input for both solver paths.

One graph feeds two solvers

A mixed-integer program combines linear constraints with variables restricted to integer values. In Rebalancer's assignment model, a binary variable can indicate whether a particular object occupies a particular bin. Hundreds of thousands of objects spread across thousands of bins can therefore produce an enormous model.

The MIP backend reduces that model through variable aggregation, interchangeability analysis, and symmetry breaking. Aggregation combines similar objects into fewer integer variables, while the other techniques prevent the solver from repeatedly exploring equivalent assignments. Rebalancer supports the open-source HiGHS solver as well as Gurobi and FICO Xpress, which require separate commercial licenses.

The local-search engine operates directly on the expression graph. It evaluates candidate moves in parallel and incrementally recomputes only the nodes affected by each move. Meta reports that the implementation can process millions of evaluations per second, making it the primary choice for the company's largest assignment workloads.

Meta's production envelope

Meta reports that Rebalancer solves about 40 million assignment problems each day across more than 30 distinct formulations. Its deployments include Shard Manager, the RAS region-wide resource allocator, and Taiji, which routes edge traffic.

These figures come from Meta's production workloads rather than a standardized benchmark. Hardware, constraint density, objective design, starting assignments, and solver settings will affect performance in other environments.

From a small model to production scale

A practical evaluation can use the exact backend to check a reduced model before shifting larger instances to local search:

1. Define the assignment: Identify the objects, candidate bins, resource dimensions, groupings, hard constraints, and optimization goals.
2. Encode common policies: Use specifications such as CapacitySpec, GroupCountSpec, and BalanceSpec.
3. Validate a reduced case: Run the MIP backend on a tractable instance and inspect whether the resulting assignment matches the intended policy.
4. Scale with local search: Apply the expression model to production-sized inputs and measure runtime, feasibility, and objective quality.
5. Inspect difficult runs: Use Explorer documentation to investigate constraints, expressions, and solver behavior.

The exact backend can also generate reference solutions for tuning local-search heuristics offline. This workflow preserves a single policy model while allowing the solving strategy to change with workload size and latency requirements.

Rebalancer's niche

Open-source optimization already offers modeling systems such as Pyomo, OR-Tools, and PuLP, along with capable general-purpose solvers. Rebalancer focuses more narrowly on assignment workloads with huge decision spaces, short time budgets, recurring infrastructure policies, and model authors who may lack specialized optimization training.

The framework still requires careful policy design. Developers must translate operational rules into dimensions, partitions, scopes, constraints, and objectives, then evaluate the quality of heuristic results. Rebalancer Explorer provides visibility into that process, while the team's OSDI 2024 paper explains the architecture and optimization techniques behind the library.

The same primitives can represent assignments outside datacenters, including meeting rooms, support tickets, logistics jobs, and energy dispatch. Rebalancer is most relevant when those workloads combine repeated placement decisions, complex grouping rules, and a scale that strains conventional exact solvers.