Meta Rebalancer: Separate Policy, Search, and Debugging

Meta Rebalancer shows how assignment systems improve when policy, mathematical expression, solving, and debugging share a stable contract. The reusable lesson reaches beyond datacenters: define objects, containers, objectives, constraints, and acceptance rules before choosing an algorithm. Solver performance matters after the organization can state what a valid assignment means and explain why the system produced one.

Reading time: 9 minutes · About 1,800 words

TL;DR

• Keep business policy in a solver-neutral specification instead of embedding it in one algorithm.
• Model hard constraints separately from objectives so feasible and preferable remain distinct concepts.
• Compile the specification into a shared expression graph that multiple solvers and debuggers can consume.
• Use MIP for optimality and baselines where scale permits; use local search when scale and solve time dominate.
• Treat initial constraint violations as an explicit repair problem and verify the final assignment independently.

Rebalancer is an architecture, not one clever algorithm

Meta open-sourced Rebalancer on September 21, 2026 after using and developing it internally for more than nine years. The system addresses a recurring assignment problem: place objects into bins while satisfying constraints and optimizing objectives.

At Meta, the same shape appears in hardware placement, service placement, task placement, traffic routing, migrations, and machine-learning workload placement. The vocabulary changes, while the control problem remains recognizable.

The central design decision is separation of concerns. Rebalancer distinguishes:

1. the domain specification;
2. its compact representation in memory;
3. the solving method;
4. the tools used to understand solver behavior.

The accompanying OSDI 2024 paper presents usability and scalability as the two main obstacles to a reusable allocation framework. Domain engineers struggle to translate policy into mathematics, while large NP-hard instances exceed the practical reach of general optimal solvers. A useful system has to address both without fusing policy to one implementation.

Start with a solver-neutral policy model

Rebalancer's model begins with objects and bins, then adds a small domain vocabulary:

Reusable specs express common goals and rules on top of these constructs. A capacity constraint can cap memory per host. A balance objective can reduce utilization skew. A group-count rule can limit how many job types appear in one rack.

This structure prevents an expensive coupling. If the business policy exists only as procedural code inside a local-search loop, changing the algorithm risks changing the meaning of the policy. New reviewers also have to reverse-engineer intent from move logic.

A solver-neutral contract lets the team ask two separate questions:

• Did we model the intended policy?
• Did the chosen solver produce an acceptable answer for that model?

The first question belongs to domain owners. The second belongs to optimization and systems engineering. Both can evolve while sharing test cases.

Separate constraints from objectives

Constraints define assignments the system may accept. Objectives rank acceptable assignments. Mixing them creates a system that can trade away safety or capacity rules for a better score.

Suppose a scheduler places tasks on hosts:

• Host memory capacity is a constraint.
• Spreading replicas across racks may be a constraint.
• Balancing CPU can be an objective.
• Minimizing migration cost can be another objective.

The distinction needs an explicit conflict policy. If two hard constraints cannot be satisfied together, the solver should return an infeasibility or repair state with evidence. Quietly converting one into a soft penalty hides a policy decision inside the optimizer.

Rebalancer accepts an initial assignment. Meta's description says new constraints may not be violated by the optimized assignment. Constraints already violated in the initial state become high-priority goals whose violation is minimized, ideally to zero. This behavior is a useful repair mode, but it requires careful reporting.

A repaired assignment should expose:

• which violations existed before the run;
• which were removed;
• which remain and by how much;
• which objective quality was sacrificed during repair;
• whether the final result is valid for production use.

This is the precise version of separating objectives, constraints, and repair. Repair is a state transition and evidence record, rather than a third kind of policy silently mixed into the score.

Compile once into an expression graph

Rebalancer translates the specification into a directed acyclic expression graph. Leaf nodes represent utilization values. Higher nodes compose them through operations such as sum, maximum, square, and absolute value. The graph's values change as objects move between bins.

The expression graph serves as an intermediate representation. It gives different consumers one stable semantic layer:

• local search can evaluate how a move changes constraints and objectives;
• a mixed-integer programming translator can generate a model for external solvers;
• pruning and equivalence analysis can reduce work;
• debugging tools can explain which expressions dominate a result.

This resembles a compiler architecture. Domain policy is the source language. The expression graph is the intermediate representation. Local search and MIP are backends. Explorer is an inspection surface.

The analogy also identifies a test strategy. Validate the specification before optimization, test expression-graph evaluation on small assignments, compare solver backends on tractable instances, and check the emitted assignment against constraints with an independent validator.

Choose the solver after stating the trade-off

Rebalancer exposes two main approaches.

Mixed-integer programming (MIP) translates the graph into expressions consumed by FICO Xpress, Gurobi, or the open-source HiGHS solver. It can provide an optimal solution given enough time. Its model can become very large because object-bin choices create many decision variables. Meta applies aggregation, interchangeability, and symmetry breaking, while the largest instances remain impractical for MIP.

Local search starts from an assignment and explores nearby moves such as moving one object or swapping objects. It accepts improving valid moves until progress stops or a time or move limit is reached. Meta's open-source repository states the crucial boundary: local search scales well but does not guarantee a globally optimal answer.

The right question is therefore not which solver is best. It is which evidence the current decision needs:

The OSDI paper and Meta's release describe this mixed use: optimal solving can establish a baseline or tune local search, while large production workloads usually rely on local search.

Debugging becomes the next bottleneck

Once a framework makes problems easy to formulate and solve, engineering time moves to understanding behavior. The OSDI paper reports that much of model setup work goes into questions such as objective ranking and conflicting constraints.

Meta built Rebalancer Explorer for this layer. The open-source UI helps modelers inspect objects, containers, constraints, and goals, and ask why an object landed in one bin or what would happen if a constraint were relaxed.

This is a predictable bottleneck shift. Faster search produces answers sooner, which increases the number of policies teams can try. The limiting factor becomes the ability to distinguish a solver bug, a specification bug, an infeasible policy, and an acceptable trade-off.

Every production assignment system should answer five questions:

1. Which constraints are binding?
2. Which objectives dominate the score?
3. Why did this object move to this bin?
4. What prevented the expected assignment?
5. How sensitive is the result to one policy or data change?

Logs alone rarely answer them because they record execution detail rather than model meaning. An explanation tool should operate on the same policy and expression representation as the solver.

A minimal implementation and validation pattern

The repository exposes C++ and Python interfaces. The following framework-neutral pseudocode keeps the four stages visible:

solver = ProblemSolver(service_name="scheduler", service_scope="prod")

solver.set_assignment(current_assignment)
solver.add_object_dimension("memory", task_memory)
solver.add_container_dimension("memory", host_capacity)
solver.add_constraint(memory_capacity_spec)
solver.add_objective(cpu_balance_spec)
solver.add_solver(local_search_spec)

solution = solver.solve()

Keep policy construction separate from the call to solve(). Then validate the result with code that does not reuse the solver's internal evaluation path:

assert every_object_assigned_once(solution)
assert all_capacity_limits_hold(solution, host_capacity, task_memory)
assert required_failure_domain_spread_holds(solution)
assert objective_score(solution) <= production_threshold

Before production rollout, use this checklist:

1. Freeze a representative corpus of valid, infeasible, and repair-needed assignments.
2. Define every hard constraint, objective priority, stopping condition, and allowed residual violation.
3. Verify expression values on hand-computed small cases.
4. Compare local search with MIP on instances where MIP is tractable.
5. Validate final assignments through an independent checker.
6. Record initial and final violations separately.
7. Test determinism requirements or report result variance across seeds and thread counts.
8. Set rollback rules for quality, solve time, and unexplained behavior.

The production gate should require validity, bounded quality, bounded latency, and an explanation path. A fast assignment that violates policy and an optimal assignment that arrives after its decision window both fail the system requirement.

FAQ

What problem does Meta Rebalancer solve?

It models how objects should be assigned to containers while satisfying constraints and optimizing goals. Meta applies this shape to infrastructure placement, traffic, migrations, and other allocation tasks.

Is Rebalancer a mixed-integer programming solver?

It is a broader specification and solving framework. It can translate models to MIP solvers or solve them through its local-search implementation.

Does local search find the optimal assignment?

Local search finds improving valid moves efficiently but offers no general global-optimality guarantee. Compare it with optimal baselines on smaller instances and enforce production quality thresholds.

How should hard constraints and soft goals be represented?

Keep them as different model concepts. Hard constraints define acceptable assignments. Objectives rank the acceptable set. Any relaxation should be explicit, authorized, and reported.

What should a solver return when the initial state is invalid?

Return both the repaired assignment and a violation report covering the before state, after state, remaining violations, and production eligibility.

Design the contract before tuning the solver

Rebalancer's lasting lesson is architectural. A reusable assignment system gives domain policy a stable language, gives algorithms a shared intermediate representation, and gives operators an explanation surface. That structure lets teams change the solver without silently changing the meaning of a valid result.

Take one current allocation service and write its objects, bins, hard constraints, objectives, stopping condition, and independent acceptance checks on one page. Any item that lives only inside algorithm code identifies the first coupling to remove.

References

• Meta Engineering: Open-Sourcing Rebalancer
• GitHub: facebook/rebalancer
• OSDI 2024: Optimizing Resource Allocation in Hyperscale Datacenters
• OSDI 2024 paper PDF