Skip to content

SYSTEM Cited by 1 source

Rebalancer (Meta)

Rebalancer is Meta's generic, high-performance library for solving assignment problems — "given a set of objects and a set of bins, how do we assign objects to bins to optimize objectives while meeting constraints?" It has been used to solve resource-allocation problems across Meta's infrastructure for over nine years and was open-sourced (Apache 2.0) in September 2026, accompanied by the OSDI'24 paper "Optimizing Resource Allocation in Hyperscale Datacenters: Scalability, Usability, and Experiences" (Source: sources/2026-09-21-meta-open-sourcing-rebalancer-a-generic-high-performance-library).

The problem it solves

Assignment problems recur at every layer of Meta's stack:

  • Hardware placement — racks (objects) → data centers (bins), spread across electrical fault domains under power/cooling limits.
  • Service placement — servers (objects) → services (bins), meeting demand while spreading across failure domains and maximizing packing efficiency.
  • Task placement — tasks (objects) → servers (bins) under resource limits and co-location rules.
  • Traffic routing — user traffic (objects) → geo-distributed data centers (bins) optimizing network latency + DC load.

The two hard design challenges are usability (translating real-world policy into precise optimization math) and scalability (these problems are NP-hard and too large for commercial solvers). Rebalancer's answer to both is to separate a problem's specification from its solution.

Architecture: specify → compile → solve

1. Specification language (three levels).

  • Modeling constructs: dimensions (real-world attributes of objects/bins, e.g. CPU, storage), partitions (groupings of objects, e.g. tasks belonging to a job), scopes (groupings of bins, e.g. servers in a rack), and utilization (an object's contribution to a bin).
  • Expression API: composable/recursive transforms on those constructs — SUM, MAX to aggregate utilization; SQUARE, ABS to transform it.
  • Spec API: dozens of prebuilt objectives/constraints — each a "predefined recipe" that turns modeling constructs + parameters into a formula via the expression API. Named examples: CapacitySpec (bin utilization limits), GroupCountSpec (e.g. one job type per rack), BalanceSpec (balance a server's utilization across CPU + storage dimensions).

2. Expression graph. A specified problem compiles into a directed acyclic graph: leaf nodes are utilization expressions; interior nodes aggregate (Max, Sum) or transform (Square, Abs). Each node's value depends on the current assignment and is recomputed as the assignment changes. This DAG is the shared intermediate representation both solvers consume.

3. Two solver backends.

Solver Mechanism Neighborhood / model size Used for
Optimal Solver Translates the expression graph into a MIP for FICO Xpress / Gurobi / HiGHS; shrinks models via variable aggregation, interchangeability, symmetry breaking worst-case O(|objects|·|bins|) (quadratic) — too big for the largest problems small/mid-size problems; prototyping; offline tuning of local search
Local Search Solver Works directly on the expression graph; moves relocate objects to another bin, evaluate candidates, apply the best feasible improving one, repeat until a stopping condition O(|objects|+|bins|) — scales to very large problems "almost all large-scale problems at Meta"

Modelers supply an initial assignment and a stopping condition; constraints violated by the initial assignment become high-priority objectives whose violation is minimized "ideally to zero." Local search is heavily parallelized ("millions of evaluations per second") and prunes the search space to reduce the number of evaluations. A common workflow: prototype with the optimal solver, migrate to local search once a high-quality baseline exists.

Where it's used at Meta

Rebalancer solves "roughly 40 million assignment problems every day with more than 30 unique problem formulations," including:

  • Shard Manager — assigning shards to servers.
  • RAS (Region-wide datacenter resource Allocation Service) — assigning servers to services, continuously optimized region-wide.
  • Taiji — routing traffic from globally distributed edge data centers to main data centers.
  • Grouping serverless functions for locality; balancing online ML-training workloads across regions by workload priority; and beyond infra — meeting-room assignment, support-ticket routing, desk placement.

Operational numbers

  • 9+ years in production; ~40M assignment problems/day; 30+ formulations.
  • P99 solve time = 12s on a 265k-object / 3.2k-bin problem.
  • Avg solve time = 171s for problems with >1M objects / 5k bins; >3,400 such runs.
Last updated · 766 distilled / 2,225 read