如何使用 Meta 的 Rebalancer 进行任务放置与优化

In this tutorial, we implement the Rebalancer, Meta’s assignment solver, with a C++ core and a Python binding. We describe objects, containers, dimensions, scopes, and partitions, add constraints and goals, then choose local search or the exact mixed-integer solver HiGHS. We build a small datacenter, drain a busy host, and compare the two solvers on toy models, mutually exclusive hosts, synthetic clusters, and 60 published OR-Library instances. We judge every plan by recounting the returned assignment rather than by the solver’s flags. In this build, across 24 solves, the solved flag read True in 14 solves that still left memory over capacity. HARD under local search returned a violating start without raising; misspelled spec keys were ignored silently, and enum names are rejected. The timings come from an Apple M4 with the macOS wheel, and Colab’s Linux wheel may time differently.

We install rebalancer 1.0.4 and print the Python version and hardware, because every timing depends on them. The binding rejects enum names and silently ignores unknown spec keys, so the notebook passes integers from one table and checks each spec before solving. A gate then solves a two-task model with both solvers, each moving one task, in 0.8 ms with local search and 0.9 ms with HiGHS. The cell also confirms that this build refuses the default XPRESS solver and the Gurobi package.

We solve the README example, four 10 GB tasks on two 20 GB hosts with three tasks on one host, and recount the result instead of trusting the solver. Local search moves one task in 0.3 ms, and the recount drops the excess from 10 GB to 0. The solver’s own brokenCount also falls from 1 to 0 and endReason reads OPTIMAL. A control makes the point about the flag: with solveTime=0 the solver moves nothing, still leaves 10 GB over capacity, and reports solved=True.

We test a fixable start F and an impossible start I under each constraint policy and both solvers, recounting every result. HARD with local search returns both starts untouched, with OPTIMAL and solved=True, while HiGHS fixes F and raises an infeasible error on I. Across the 24 solves, solved read True in 14 solves that still left memory over capacity. The solver’s brokenVal equals total excess divided by mean host capacity in all 15 samples. Read brokenCount or recount rather than trusting OPTIMAL.

A lower goal tuple always decides first, and weights trade off only within one tuple. With both in tuple 0, weight 1 for affinity loses to weight 1000 for movement, and swapping the weights moves t0. With the affinity in tuple 0 and movement in tuple 1, t0 still moves. A fix-it goal in a later tuple than movement leaves 10 GB over with no move, while the reverse order repairs it with one move. The fix-it value is 10000 plus 100 times brokenVal, checked on two starts.

We drain host1 under a ToFree constraint, leaving host0 alone in rack0 at 16 of 16 CPU. Unbudgeted, local search empties host1 in 13 moves with no violations, and three fresh builds agree. A stopAfterMoves budget gives a partial plan, not an error: at 12 moves one task still sits on host1, and at 6 moves the recount finds 4 CPU and 16 GB excess and 6 rack duplicates, yet solved is True. A misspelled key, stopAfterMove, is silently ignored, and the solve runs all 13 moves.

We compare HiGHS with local search on balance, judged by recounted CPU spread, since objectives across formulas are not comparable. With the LINEAR formula, both reach zero spread, but local search moved 13 tasks in a median of 1.8 ms, while HiGHS moved 16 in 7.8 ms. IDEAL balances under local search but raises a HiGHS error. On three mutually exclusive hosts, local search stops with all three hosts in use and every conflicting pair still broken, because no single move lowers brokenVal. HiGHS clears the conflicts in 5.9 ms.

We run synthetic clusters under a time cap, each in a fresh process. The 1,000-object, 100-container cluster took 1.22, 1.27 and 1.35 s across three processes, returned the same assignment each time and cleared all 13 overloaded containers. A 1,000-by-1,000 cluster took 3.55 s. At 10,000 objects on 100 containers, the 25 s cap is reached with HIT_TIME_LIMIT, so endReason and a recount tell finished plans from partial ones. Three HiGHS runs of the datacenter reach objective 0 with three different assignments, so we compare objectives, not assignments.

We check the solvers against 60 OR-Library generalized-assignment instances with published optima, downloaded and checksum-checked at run time. HiGHS matches all 60 optima, every answer feasible, the slowest at 1.31 s. Local search from a first-fit start reaches the optimum on 4 of 60 even with the best of three seeds, and its best answer per instance falls 7.7 profit units (1.07%) short on average. Across nine runs, the mean shortfall ranged from 7.6 to 8.1, and even fixed seeds vary between runs, for a cause we did not isolate.

We test bin packing with MinimizeContainers on two OR-Library instances and measure against the L1 lower bound, which equals their best-known bin counts of 48 and 20. Local search from first-fit decreasing removes no bin on either. Asking for exactly L1 bins with capacity alone packs u120_00 in 0.02 s, which meets the bound and so is optimal. On t60_00, local search finds no 20-bin packing, and HiGHS finds none within 10 s on either instance, which is a timeout, not a proof of infeasibility.

The summary lists every claim with how it was checked, by recount, endReason or raised error, and solver seconds per step. In this run all 28 claims held and no step failed, with 90.1 s spent inside the solver. Not tested here are production scale, the paper’s or Meta’s latency and volume figures, and the XPRESS and Gurobi backends.

Rebalancer turns placement into a readable model, solved by local search or the exact HiGHS solver. On these models it rebalanced an eight-host cluster across racks, drained a busy host, matched all 60 published OR-Library optima through HiGHS, and repaired a 1,000-object, 100-container cluster in about 1.3 s on the M4. The run also showed traps: solved and OPTIMAL can sit beside a violated constraint, HARD differs by solver, misspelled keys are ignored, enum names are rejected, IDEAL fails under HiGHS, and goal-tuple order decides whether a broken constraint gets fixed. Pass enums as integers, check spec keys, recount every result, and compare objectives rather than assignments.

Sana Hassan

Sana Hassan, a consulting intern at Marktechpost and dual-degree student at IIT Madras, is passionate about applying technology and AI to address real-world challenges. With a keen interest in solving practical problems, he brings a fresh perspective to the intersection of AI and real-life solutions.