Meta Open-Sources Rebalancer: A Scalable Assignment Problem Solver
The library has optimized resource allocation across Meta's infrastructure for nearly a decade.
1Core problem addressed
Rebalancer solves assignment problems where objects (like servers or tasks) must be optimally allocated to bins (like datacenters or services) under constraints. It handles diverse use cases including hardware placement, service allocation, task distribution, and traffic routing across Meta's infrastructure. The system separates problem specification from solution, enabling flexible application across domains while maintaining performance at hyperscale.
2Key architectural innovation
The system introduces a three-layer abstraction: modeling constructs (dimensions, partitions), an expression API for transformations, and high-level specs for common constraints. This allows practitioners to describe problems in domain terms while Rebalancer handles the mathematical formalization. The expression graph representation enables both optimal MIP solving and heuristic local search approaches, with automatic optimizations like variable aggregation.
3Dual solving approaches
For smaller problems, Rebalancer generates Mixed Integer Programs solvable by commercial tools like Gurobi. For hyperscale problems, it uses a parallelized local search algorithm evaluating millions of moves per second. The local search works directly on expression graphs with O(|objects|+|bins|) complexity, avoiding memory issues in problems with 265k+ objects. Meta primarily uses local search for production systems.
4Production scale deployment
At Meta, Rebalancer solves ~40 million assignment problems daily across 30+ unique formulations. It handles problems with 1M+ objects and 5k+ bins in ~171 seconds average. Specific deployments include Shard Manager for database shards, RAS for service allocation, and Taiji for global traffic routing. The system maintains 12-second P99 latency for problems with 265k objects.
5Debugging capabilities
Rebalancer Explorer provides visualization tools to analyze solver behavior without deep algorithmic knowledge. It identifies binding constraints, evaluates constraint relaxation impacts, and explains object-bin assignments. The Dockerized web UI accompanies the open-source release, supporting both optimal and local search debugging workflows.
6Cross-domain applicability
While developed for infrastructure, Rebalancer has solved non-technical problems like meeting room assignments and support ticket routing. The team notes potential applications in healthcare, logistics, and emergency response. The Apache 2.0 license encourages external contributions to expand problem domains and solving techniques.
7Performance optimization techniques
The system employs multiple optimizations: variable aggregation reduces MIP model sizes, symmetry breaking cuts redundant computations, and parallelization enables millions of local moves/second. For expression graphs, pruning strategies minimize unnecessary evaluations. These allow solving large problems that exceed commercial solver capabilities.
8Specification language power
Rebalancer's DSL supports complex policies through reusable specs like CapacitySpec for bin limits, GroupCountSpec for partition constraints, and BalanceSpec for multi-dimensional fairness. Practitioners compose these with dimensions (CPU, storage) and scopes (racks) rather than writing raw optimization formulas, lowering the expertise barrier.
9Adoption workflow
Meta teams typically prototype with the optimal solver to establish baselines, then switch to local search for production. The optimal solver remains valuable for tuning heuristics. This hybrid approach balances solution quality with scalability requirements across different problem sizes and runtime constraints.
10Open-source potential
The release includes the core engine, Python package, documentation, and Explorer UI. Meta hopes the optimization community will extend Rebalancer's capabilities, particularly for non-infrastructure domains. Key contribution areas include new specs, solver techniques, and performance optimizations for specialized problem types.