Skip to content

Open-Sourcing Rebalancer: A Generic, High-Performance Library for Solving Assignment Problems

Summary

Meta open-sourced Rebalancer (Apache 2.0), the assignment-problem solver it has used to allocate resources across its infrastructure for over nine years. Rebalancer answers one recurring question that shows up at every layer of Meta's stack: given a set of objects and a set of bins, how do we assign objects to bins to optimize objectives while meeting constraints? Instances include hardware placement (racks → data centers, spread across electrical fault domains under power/cooling limits), service placement (servers → services, spread across failure domains for fault tolerance + packing efficiency), task placement (tasks → servers under resource limits + co-location rules), and traffic routing (user traffic → geo-distributed data centers under latency + load). The two design challenges are usability (practitioners struggle to translate real-world policy into the precise math formal optimization requires) and scalability (these are NP-hard problems commercial solvers can't handle at Meta's sizes). Rebalancer's central bet is separating a problem's specification from its solution: modelers describe a problem with objects, bins, constraints, and objectives in a declarative spec language; Rebalancer compiles that spec into an expression graph (a DAG of utilization/aggregation/transform nodes); and a solver then either builds a mixed-integer program (MIP) (fed to FICO Xpress, Gurobi, or open-source HiGHS) or runs a parallelized local-search heuristic directly over the expression graph. At Meta scale, "almost all large-scale problems use local search" — it explores a neighborhood of size O(|objects|+|bins|) versus the MIP's worst-case O(|objects|·|bins|) model — while the optimal MIP solver is used for small/mid-size problems and to prototype or offline-tune local search. Rebalancer solves roughly 40 million assignment problems/day across 30+ distinct problem formulations (Shard Manager, RAS, Taiji, serverless grouping, ML-training rebalancing, and more). Shipped alongside it is Rebalancer Explorer, a Dockerized web UI for debugging why the solver placed an object where it did.

Key takeaways

  1. Assignment problems are one primitive that recurs at every layer of hyperscale infra. Hardware placement, service placement, task placement, and traffic routing are all "assign objects to bins to optimize objectives while meeting constraints" — Rebalancer is a single reusable engine for all of them (Source: sources/2026-09-21-meta-open-sourcing-rebalancer-a-generic-high-performance-library).

  2. The core design idea is separating specification from solution. Rebalancer provides a language to describe a problem (objects / bins / constraints / objectives) and only then decides how to solve it. This separation of concerns is "crucial to Rebalancer's usability, scalability, and extensibility" — the same spec can be solved by different backends without rewriting the model.

  3. A three-level spec language raises the abstraction incrementally. (1) Modeling constructs — dimensions (real-world attributes of objects/bins), partitions (groupings of objects), scopes (groupings of bins), and utilization (an object's contribution to a bin). (2) An expression API composing/transforming these (SUM, MAX, SQUARE, ABS, recursive on other expressions). (3) A high-level spec API of dozens of prebuilt objectives and constraints (e.g. CapacitySpec, GroupCountSpec, BalanceSpec) — "a predefined recipe which accepts modeling constructs and parameters and creates a mathematical formula using the expression API."

  4. Specs are compiled into an expression graph — a DAG the solver walks. Leaf nodes are utilization expressions (e.g. memory used on server A = sum of tasks assigned to A); interior nodes aggregate (Max, Sum) or transform (Square, Abs). Every node's value depends on the current assignment and is recomputed as the assignment changes. The expression graph is the shared intermediate representation both solvers consume.

  5. Two solver backends, chosen by problem size. The Optimal Solver translates the expression graph into a MIP for FICO Xpress / Gurobi / HiGHS, using variable aggregation (compact similar objects into one integer variable), interchangeability, and symmetry breaking to shrink models — but the worst-case MIP is still O(|objects|·|bins|), too big for the largest problems. The Local Search Solver works directly on the expression graph, exploring moves (relocate objects to another bin) in an O(|objects|+|bins|) neighborhood, so it scales to very large problems without hitting memory limits.

  6. Local search is the workhorse; the MIP solver is the prototyper/tuner. "At Meta, almost all large-scale problems use local search." Small-to-mid problems with moderate solve-time budgets use the optimal solver; a common workflow is to prototype with the optimal solver, then migrate to local search once a high-quality baseline exists — and use the optimal solver offline to tune local search.

  7. Constraint violations in the initial assignment become high-priority goals. Modelers hand Rebalancer an initial assignment + a stopping condition (e.g. a time limit). Constraints violated by the initial assignment are turned into objectives whose violation is minimized "ideally to zero" — so Rebalancer degrades gracefully from an infeasible start rather than failing.

  8. Local search is heavily parallelized and prunes the search space. Each move creates a candidate assignment that is evaluated; after all candidates are evaluated, the best feasible improving one is applied; repeat until no progress or the stopping condition. Evaluation is cheap enough for "millions of evaluations per second," and Rebalancer prunes to cut the number of evaluations needed in the first place.

  9. Debugging shifted from solving to explaining — so Meta built Explorer. With formulation/solving made easy, "the majority of engineering time for modelers shifted to debugging the solver's behavior." Rebalancer Explorer is a Dockerized web UI answering which constraints are binding, what if a constraint were relaxed, and why was an object placed in one bin and not another.

Systems, concepts, and patterns extracted

  • Systems: Rebalancer (the open-source assignment solver + spec language + dual solver backends); Rebalancer Explorer (the debugging UI). Named consumers at Meta: Shard Manager (shards → servers), RAS (servers → services, region-wide resource allocation), Taiji (edge → main-DC traffic routing) — RAS and Taiji recorded as prose mentions, not dedicated pages. External MIP backends FICO Xpress, Gurobi, and HiGHS named as prose.
  • Concepts: Assignment problem — the central, canonical combinatorial-optimization primitive (objects → bins under objectives + constraints), of which bin-packing is a special case; Separation of concerns — extended here into the specify-then-solve / declarative-spec-compiled-to-solver shape. Mixed-integer programming (MIP), local search, expression graph, variable aggregation, and symmetry breaking are recorded as tags/prose (single-source here, implementation-specific or below the page-creation bar).
  • Patterns: none minted. The declarative-specification-compiled-to-a-solver idea (spec → expression-graph IR → MIP or local search) is a single-source design that maps into concepts/separation-of-concerns (specification vs solution) — recorded there as prose rather than a new pattern page. The dual-solver (exact MIP + heuristic local search) with prototype-on-exact, migrate-to-heuristic workflow is likewise a Rebalancer-specific practice, left as prose per "when unsure, tag — don't mint."

Operational numbers

Metric Value
Years in production at Meta 9+ ("over nine years")
Assignment problems solved / day ~40 million
Distinct problem formulations 30+
Local-search neighborhood size O(|objects|+|bins|)
Worst-case MIP model size O(|objects|·|bins|) (quadratic)
Local-search evaluation rate millions of evaluations / second
P99 solve time (265k objects, 3.2k bins) 12 seconds
Avg solve time (>1M objects, 5k bins) 171 seconds
Runs at >1M objects / 5k bins >3,400
License Apache 2.0
Paper OSDI'24 — Optimizing Resource Allocation in Hyperscale Datacenters

Caveats

  • Rebalancer solves general assignment problems; the article is a design + open-source-launch overview, not an internals paper — the OSDI'24 paper ("Optimizing Resource Allocation in Hyperscale Datacenters: Scalability, Usability, and Experiences") carries the deep exposition.
  • The specific local-search move-generation, pruning, and parallelization schemes are described qualitatively; no per-formulation quality/optimality gaps are disclosed beyond the aggregate solve-time percentiles.
  • Non-infrastructure uses (meeting-room assignment, ticket routing, desk placement) are cited as anecdotes; Meta explicitly disclaims expertise to apply Rebalancer to healthcare/energy/logistics itself and invites the community to.

Source

Last updated · 766 distilled / 2,225 read