Build1 publisher3 min readPublished
Meta open-sources Rebalancer, the assignment solver it has run on placement problems for over nine years
Meta has been running this assignment solver in production for more than nine years, and the price of adopting it is restating your placement policy as objects, bins, dimensions and scopes before anything solves.
The Engineer · Build desk
What happened
- Meta has open-sourced Rebalancer, an assignment-problem solver it says has been used for resource allocation problems throughout its infrastructure for over nine years.
- A problem is described in objects, bins, constraints and objectives, and Rebalancer transforms that description into a directed-acyclic graph it calls an expression graph.
- From that graph the solving algorithm either designs a local search heuristic or builds a mixed integer program for FICO Xpress, Gurobi or the open source HiGHS.
- The four allocation problems Meta names are rack placement in datacenters, server-to-service assignment, task placement on servers, and routing user traffic to datacenters.
Compiled by The EngineerSomething wrong?How this is made
Why it matters
- cost Adopting this means re-expressing a working placement policy in someone else's nouns before a single solve runs, and the team that owns the policy is the team that spends that week.
- decision Anyone taking the mixed integer program path has to decide whether to buy a commercial solver licence or accept what HiGHS returns at their instance sizes.
- capability Constraints that currently live inside greedy loops and hand-tuned spread rules can be declared once and handed to two different solving strategies without a rewrite.
- constraint Meta's own framing bounds what to expect: the heuristic path exists because the exact formulation will not always finish on these problems.
The adoption cost is the vocabulary. You declare dimensions, which are the real-world attributes of objects and bins; partitions, which group objects; scopes, which group bins; and utilization, the contribution an assigned object makes to a bin [11]. Above those sits an expression API for transforming the constructs and, recursively, other expressions: SUM or MAX to aggregate the utilization of several bins, SQUARE to reshape one [12]. The spec API sits above that, with dozens of prebuilt objectives and constraints, each one a recipe that takes modeling constructs plus parameters and writes the formula in the expression API for you [13].
Meta's worked example is task placement. Tasks are the objects, servers are the bins, and because servers sit in racks, racks are modeled as a scope; CPU and storage are dimensions, a server's utilization is the sum of the tasks assigned to it, and CapacitySpec holds that sum under the server's limits [14]. Tasks belong to jobs, jobs are a partition, and GroupCountSpec is the thing that keeps each rack to a single job type [15]. If a plain sum is the wrong utilization model, you drop into the expression API and compute it differently [18]. GroupCountSpec is also a better line to re-read six months later than the nested loop that used to enforce the same rule.
Roles are not attached to entity types here. Servers are the objects in service placement, where the services are the bins [5]. In task placement those same servers are the bins [6]. The constructs are therefore named for roles, not for hardware [16].
The two solving paths differ in what they can tell you afterwards. I would take the mixed integer program wherever the instance fits, because a MIP solver reports its optimality gap and a local search returns an assignment and nothing about its distance from the bound [10]. Meta's stated reason for having the heuristic at all is that these problems are NP-hard and cannot be solved efficiently by commercial solvers [8].
Whether nine years of production use transfers to your cluster depends on whether your policy fits utilization over dimensions. Meta's own diagnosis of why formal optimization does not get adopted is that practitioners struggle to translate real-life policies into the precise mathematical formulas the methods require [8], and the spec API is the direct answer to that complaint [13]. If your requirement is spreading racks across electrical fault domains subject to power and cooling limits, you are inside the problem this was built for [4]. If your placement is a first-fit loop nobody complains about, the modeling exercise will cost more than the assignment quality it returns.
One structural note in the release worth more than the solver talk: the library separates how a problem is specified, how it is stored in memory, how it is solved, and how it is debugged, and Meta calls that separation crucial to usability, scalability and extensibility [2]. That is also what makes the traffic routing case and the rack case the same code, with user traffic as objects and geographically distributed datacenters as bins, optimized for network latency and datacenter load [7]. For the detailed technical exposition Meta points to the OSDI'24 paper, "Optimizing Resource Allocation in Hyperscale Datacenters: Scalability, Usability, and Experiences" [3].
What to watch
- Whether the solve times and instance sizes in the OSDI'24 paper come from populations anyone outside a hyperscaler actually runs.
- Whether the released code ships the full spec API library or a trimmed subset of the dozens of objectives and constraints Meta describes.
- Whether teams that cannot licence Xpress or Gurobi get usable MIP results out of HiGHS on production-sized instances.