Meta has open-sourced Rebalancer, its solver for the assignment problem: given a set of objects and a set of bins, how do you distribute the objects to optimize objectives while satisfying constraints? Rebalancer has been in production inside Meta for more than nine years, and its design rests on separating four concerns that are usually tangled together — how an assignment problem is specified, how it is stored in memory, how it is solved, and how it is debugged. That separation is what makes it usable, scalable, and extensible. A full technical treatment appears in the OSDI'24 paper "Optimizing Resource Allocation in Hyperscale Datacenters: Scalability, Usability, and Experiences."
The same question shows up at every layer of Meta's infrastructure: racks placed into datacenters to spread electrical fault domains under power and cooling limits; servers assigned to services to meet demand while spreading across failure domains and packing efficiently; tasks allocated to servers under resource limits with co-location goals; and traffic from billions of users routed to geographically distributed datacenters to balance latency and load.
Two properties decide whether a reusable framework can cover these cases. Usability suffers because practitioners must translate real policies into the precise mathematical form formal optimization demands. Scalability suffers because the problems are NP-hard and defeat commercial solvers at scale. Rebalancer answers both by splitting specification from solution. Problems are described with objects, bins, constraints, and objectives; Rebalancer turns that description into a directed acyclic graph called an expression graph, which its solving algorithm uses either to design a local search heuristic or to build a mixed integer program (MIP) for a commercial solver (FICO Xpress, Gurobi) or an open-source one (HiGHS).
Deferring mathematical form
The specification language raises abstraction in three steps.
- Core modeling constructs: dimensions (real-world attributes of objects and bins), partitions (groupings of objects), scopes (groupings of bins), and utilization (what objects assigned to a bin contribute).
- An expression API of common transformations over those constructs, applicable recursively to other expressions — aggregating utilization across bins with SUM/MAX, or transforming it with SQUARE.
- A high-level spec API with dozens of standard objectives and constraints. Each spec is a predefined recipe that takes modeling constructs and parameters and emits a mathematical formula through the expression API.
Tasks are items on elastic hardware. Tasks are objects, servers are bins; the racks the servers sit in define a scope. Tasks consume CPU and storage, which are dimensions, and each server has finite amounts of both. A server's CPU and storage utilization is the sum of the tasks placed on it, with capacity limits expressed through a CapacitySpec. Where a plain sum is inappropriate, the expression API can redefine how utilization is computed.
Tasks also belong to jobs, a grouping of objects modeled as a partition. A GroupCountSpec keeps each rack to a single job type, and a BalanceSpec balances each server's utilization across CPU and storage. The example shows how a fairly involved assignment problem falls out of the vocabulary naturally, and how one spec can be reused across different dimensions, scopes, and partitions. The docs enumerate the available specs.
Expression graphs and two solvers
Translation proceeds by turning the specification into an expression graph. Leaf nodes are utilization expressions, such as the memory utilization of server A obtained by summing the memory contributions of the tasks assigned to it. From there, aggregation nodes (Max, Sum) and transformation nodes (Square, Abs) compose them recursively. Every node's value depends on the current assignment, so all of them must be updated whenever the assignment changes.
Modelers supply an initial assignment and a stopping condition, such as a time limit; Rebalancer produces an optimized assignment that minimizes the objective without introducing new constraint violations. Constraints broken by the initial assignment become high-priority goals whose violation is minimized, ideally to zero. Two techniques are available for the solve itself.
Optimal solver
Here the expression graph is translated into expressions for a MIP solver — FICO Xpress, Gurobi, or HiGHS. A bin's utilization must be represented as a weighted sum of binary decision variables, one per object, indicating whether that object lands in that bin, which makes for very large models. Rebalancer applies variable aggregation (collapsing similar objects into a single integer variable), interchangeability, and symmetry breaking to shrink the model, but the worst case remains quadratic, O(|objects| * |bins|). The largest problems under consideration are too big for any MIP solver.
Local search solver
Local search avoids the translation entirely and works on the expression graph, exploring the neighborhood around the current assignment by moving objects between bins. That neighborhood has a worst-case size of O(|objects|+|bins|), so even very large problems fit in memory. Each move yields a candidate assignment whose objective and constraint values are evaluated; once all candidates are evaluated, the best one is applied — the assignment that violates no constraint and improves the objective the most. Evaluate-and-apply repeats until no progress is possible or the stopping condition trips. The local search is heavily optimized and parallelized, making individual evaluations cheap enough for millions per second and fast exploration of the space, and Rebalancer prunes the space to reduce the number of evaluations required.
Which technique to use depends on the problem. Nearly all of Meta's large-scale problems run local search; small and mid-size problems with moderate solve-time budgets tend to use the optimal solver. A common pattern is to prototype with the optimal solver, establish a high-quality baseline, then migrate to local search. Offline, the optimal solver serves to tune local search.
Production footprint
A decade of continuous use and improvement has put Rebalancer behind a broad set of infrastructure problems: assigning shards to servers (Shard Manager), servers to services (RAS), routing traffic from globally distributed edge datacenters to main datacenters (Taiji), grouping serverless functions for locality, and balancing online ML training workloads across regions while accounting for workload priority. Currently it solves roughly 40 million assignment problems per day across more than 30 distinct formulations. P99 solve time is 12 seconds on a problem with 265k objects and 3.2k bins, and for problems exceeding 1 million objects and 5k bins the average solve time is 171 seconds, with more than 3.4k such runs.
Non-infrastructure uses have appeared too: meetings to rooms to minimize travel time, support tickets to engineers, desk placement. Assignment problems are widespread in healthcare, energy and utilities, transportation and logistics, education, and emergency response, but lacking domain expertise, Meta is leaving those applications to others.
Debugging as a first-class concern
Once formulation and solving get easy, engineering time shifts to debugging the solver's behavior, which previously demanded a deep knowledge of its internals. Rebalancer Explorer, included in this release as a Dockerized web UI, was built out of the questions modelers kept asking, and works with both local search and the optimal solvers. It surfaces which constraints are binding, what a relaxed constraint would change, and why a given object landed in one bin rather than another.
Open source and what comes next
Rebalancer is released under the Apache 2.0 license. Work continues on performance, new capabilities, and broader problem coverage, and systems and optimization experts are invited to contribute — whether by finding performance bottlenecks, adding solve techniques, extending it to new problem types, or fixing bugs.
- Code: Rebalancer GitHub repo
- Docs: Introduction to Rebalancer
- PyPI: Rebalancer Python package
- Paper: Optimizing Resource Allocation in Hyperscale Datacenters: Scalability, Usability, and Experiences — OSDI 2024
Rebalancer was developed by past and present members of the Algorithmic Optimization team at Meta: Pol Mauri Ruiz, Igor Kabiljo, Neeraj Kumar, Vijay Menon, Mayank Pundir, Andrew Newell, Liyuan Wang, Richard Barnes, Sahil Deshpande, Karthik Velakur, Yang Liu, Leart Gjoni, Ravi Surulikamu, Tony Zhang, Raj Rajendran, Aravind Narayanan, Lakshmi Ganesh, and Saranyan Vigraham.
