Meta Open-Sources Rebalancer: A Scalable Assignment Problem Solver
The library optimizes resource allocation across Meta's infrastructure with 40M daily solves.
1Core problem abstraction
Rebalancer addresses the fundamental challenge of assigning objects to bins while optimizing specific objectives under constraints. This abstraction applies to hardware placement (racks to datacenters), service placement (servers to services), task allocation (tasks to servers), and traffic routing (users to datacenters). The framework separates problem specification from solution, enabling practitioners to model real-world policies without deep optimization expertise.
2Three-layer specification language
Rebalancer's API elevates abstraction through dimensions (attributes of objects/bins), partitions (object groupings), and scopes (bin groupings). It exposes common expressions like SUM/MAX operations and higher-level specs for constraints like CapacitySpec (resource limits) and BalanceSpec (multi-dimensional balancing). This allows complex problems to be composed from reusable components without requiring mathematical formulation from scratch.
3Expression graph transformation
Problems are compiled into directed-acyclic expression graphs where leaf nodes represent utilization metrics (e.g., server memory usage). Intermediate nodes apply transformations (Square, Abs) or aggregations (Max, Sum). The graph dynamically updates with assignment changes, enabling efficient evaluation of constraint violations and objective improvements during optimization.
4Dual solving approaches
Rebalancer offers both MIP-based optimal solving (using FICO Xpress/Gurobi/HiGHS) and heuristic local search. The optimal solver handles smaller problems (O(|objects|*|bins|) complexity) while local search scales to massive instances (O(|objects|+|bins|)) by evaluating millions of moves per second. Meta primarily uses local search for production-scale problems, reserving MIP for prototyping and tuning.
5Production-scale adoption
At Meta, Rebalancer solves ~40M problems daily across 30+ unique formulations. It handles problems with 265K objects in 12 seconds (P99) and million-object instances in ~171 seconds on average. Key applications include Shard Manager (database sharding), RAS (service allocation), and Taiji (global traffic routing), demonstrating versatility across infrastructure layers.
6Debugging innovations
Rebalancer Explorer provides specialized tooling for solver behavior analysis, answering questions about binding constraints, relaxation impacts, and placement rationales. This Dockerized web UI reduces debugging time by eliminating the need for deep solver internals knowledge, addressing a major pain point in optimization workflows.
7Cross-domain applicability
While developed for infrastructure optimization, Rebalancer's generic approach applies to healthcare resource allocation, logistics routing, emergency response planning, and other domains with assignment challenges. The open-source release (Apache 2.0) invites extensions for new problem types and solver improvements.
8Performance optimizations
Key innovations include variable aggregation (compressing similar objects), symmetry breaking, and parallelized local search with intelligent pruning. These allow Rebalancer to handle hyperscale problems commercial solvers can't address, while maintaining usability through high-level abstractions.
9Evolutionary development
Over nine years of production use at Meta, Rebalancer evolved through iterative improvements to its specification language, solving algorithms, and debugging tools. This long-term refinement process yielded both technical robustness and practical usability for infrastructure engineers.
10Open-source potential
By open-sourcing Rebalancer, Meta enables broader innovation in optimization techniques while benefiting from community contributions. The accompanying paper (OSDI'24) provides implementation insights, and the PyPI package lowers adoption barriers for Python-based optimization workflows.