Meta AI відкрила вихідний код Rebalancer: C++-розв’язувача, який обробляє близько 40 мільйонів задач розміщення на день
Meta відкрила Rebalancer з відкритим вихідним кодом — бібліотеку C++ з інтерфейсом Python для розв’язання задач розподілу. Вона визначає, які об’єкти мають потрапити до яких контейнерів за заданих обмежень і цілей. Згідно з публікацією Engineering at Meta, Rebalancer понад 9 років використовується для розподілу ресурсів у Meta. Реліз поширюється за ліцензією Apache 2.0 і містить документацію, пакет PyPI та інтерфейс налагодження під назвою Rebalancer Explorer.
Чи готовий він до розгортання? Так. Команда pip install rebalancer встановлює версію 1.0.4 для Python 3.12+, із попередньо зібраними пакетами для Linux x86-64 і macOS 14+ ARM64. Також доступні пакети .deb, .rpm і Homebrew. PyPI досі класифікує проєкт як Alpha.
Яку проблему розв’язує Rebalancer?
Задачі розподілу виникають у різних компонентах стеку Meta. Стійки розміщуються в дата-центрах, сервери — у сервісах, завдання — на серверах, а користувацький трафік — у дата-центрах. Meta називає дві головні перешкоди: зручність використання та масштабованість. Інженерам складно перетворювати політики на точні формули, а багато задач є NP-складними й надто великими для комерційних розв’язувачів.
Відповідь Rebalancer полягає в розділенні способу задання задачі та способу її розв’язання. Конструкцію докладно описано в статті OSDI 2024 Optimizing Resource Allocation in Hyperscale Datacenters.
Як працює рівень специфікації
Мова специфікацій має 3 рівні:
- Конструкції моделювання: виміри (атрибути, як-от CPU або сховище), секції (групи об’єктів), області (групи контейнерів) і використання ресурсів.
- API виразів: агрегування використання за допомогою SUM або MAX чи його перетворення за допомогою операцій на кшталт SQUARE.
- API специфікацій: десятки заздалегідь визначених цілей і обмежень, перелічених у документації.
У прикладі Meta завдання моделюються як об’єкти, сервери — як контейнери, а стійки — як область. CapacitySpec обмежує CPU та сховище для кожного сервера. GroupCountSpec забезпечує розміщення 1 типу завдань на стійку. BalanceSpec балансує використання кожного сервера за обома вимірами.
Один граф виразів, два розв’язувачі
Rebalancer компілює специфікацію в орієнтований ациклічний граф виразів. Листові вузли містять значення використання ресурсів, а над ними розташовані вузли агрегування та перетворення. Користувачі задають початковий розподіл і умову зупинки. Обмеження, які вже порушує початковий розподіл, стають цілями з високим пріоритетом.
Оптимальний розв’язувач: граф перекладається в задачу змішаного цілочислового програмування для FICO Xpress, Gurobi або HiGHS. Агрегування змінних і усунення симетрії зменшують розмір моделей. У найгіршому випадку розмір моделі все одно становить O(об’єкти × контейнери). Найбільші задачі Meta надто великі для будь-якого MIP-розв’язувача.
Локальний пошук: цей розв’язувач працює безпосередньо з графом виразів. Він досліджує переміщення об’єктів до інших контейнерів, причому в найгіршому випадку розмір околу становить O(об’єкти + контейнери). Потім застосовується найкращий кандидат, який не порушує жодного обмеження. Обчислення виконуються паралельно — досягаються мільйони оцінювань за секунду, а простір пошуку скорочується.
Meta використовує локальний пошук майже для всіх великих задач, а MIP — для задач малого та середнього розміру, часто спочатку створюючи прототип за допомогою MIP.
Показники роботи Rebalancer у Meta
- Близько 40 мільйонів задач розподілу розв’язується щодня у понад 30 унікальних формулюваннях.
- Час розв’язання P99 — 12 секунд для 265 тис. об’єктів і 3,2 тис. контейнерів.
- Задачі з понад 1 мільйоном об’єктів і 5 тис. контейнерів у середньому розв’язуються за 171 секунду — на основі понад 3,4 тис. запусків.
Найкращі сценарії використання Rebalancer
- Розміщення сегментів, завдань або контейнерів у кластері: розподіл роботи між серверами з обмеженнями CPU та пам’яті, одночасно розподіляючи репліки між стійками. Shard Manager і RAS від Meta використовують цей підхід.
- Балансування трафіку та робочих навантажень між регіонами: маршрутизація користувацького трафіку або завдань до дата-центрів із пошуком компромісу між затримкою та навантаженням. Taiji робить це для периферійного трафіку, а Meta балансує навчання ML за пріоритетом.
- Операційний розподіл поза інфраструктурою: призначення заявок до інженерів, зустрічей — до кімнат або столів — до людей із дотриманням правил місткості. Meta використовувала всі 3 сценарії.
Налагодження за допомогою Rebalancer Explorer
Моделісти Meta витрачали більшість часу на налагодження поведінки розв’язувача. Rebalancer Explorer — це вебінтерфейс у Docker, створений для цієї мети. Він показує обмеження, що визначають результат, ефекти послаблення та причини, чому об’єкт потрапив до певного контейнера.
Інтерактивне пояснення
Запустити локальний пошук</button>
<button class="b" id="mtpStep">Зробити один крок</button>
<button class="b" id="mtpShuf">Випадковий невдалий початок</button>
<button class="b" id="mtpReset">Скинути</button>
</div>
<div class="stats">
<div class="st"><div class="k">Крок</div><div class="v" id="mtpS">0</div></div>
<div class="st"><div class="k">Оцінено переміщень</div><div class="v" id="mtpE">0</div></div>
<div class="st"><div class="k">Перевищення місткості</div><div class="v" id="mtpV">0</div></div>
<div class="st"><div class="k">Ціль балансування</div><div class="v" id="mtpO">0</div></div>
</div>
<div class="racks" id="mtpRacks"></div>
<div class="spark"><div class="k">Ціль залежно від кількості кроків (менше — краще, ідеал = 324)</div>
<svg id="mtpSpark" viewBox="0 0 800 70" width="100%" height="70" preserveAspectRatio="none"></svg>
</div>
<div class="log" id="mtpLog">Сервер S1 починає роботу з перевищенням місткості на 4 CPU. Натисніть «Запустити».</div>
</div>
<!-- PANE 2 -->
<div class="pane" id="mtpP1">
<p class="note">Rebalancer компілює специфікації в <b>орієнтований ациклічний граф виразів</b>. Листи містять використання ресурсів кожного сервера; над ними розташовані вузли SQUARE, SUM і MAX. Коли переміщується одне завдання, нові значення потрібні лише для задіяних ним листів та їхніх предків. Граф використовує той самий поточний стан, що й вкладка 1.</p>
<div class="btns">
<button class="b pri" id="mtpGMove">Перемістити випадкове завдання</button>
<button class="b" id="mtpGBest">Застосувати найкраще переміщення локального пошуку</button>
</div>
<div class="gwrap"><svg id="mtpGraph" viewBox="0 0 820 300" width="100%"></svg></div>
<div class="log" id="mtpGLog">Натисніть кнопку, щоб перемістити завдання.</div>
</div>
<!-- PANE 3 -->
<div class="pane" id="mtpP2">
<p class="note">Для MIP-моделі потрібна приблизно одна двійкова змінна на кожен об’єкт і контейнер, тому її розмір зростає як <b>O(об’єкти × контейнери)</b>. Окіл локального пошуку зростає як <b>O(об’єкти + контейнери)</b>. Перетягуйте повзунки або завантажте опубліковані Meta розміри.</p>
<div class="btns">
<button class="b" data-o="500" data-bn="20">Мала: 500 × 20</button>
<button class="b" data-o="265000" data-bn="3200">P99 Meta: 265 тис. × 3,2 тис.</button>
<button class="b" data-o="1000000" data-bn="5000">XL Meta: 1 млн × 5 тис.</button>
</div>
<div class="sl"><label>Об’єкти <b id="mtpOv"></b></label><input type="range" id="mtpOs" min="1" max="6.3" step="0.01" value="2.7"></div>
<div class="sl"><label>Контейнери <b id="mtpBv"></b></label><input type="range" id="mtpBs" min="0.3" max="4" step="0.01" value="1.3"></div>
<div class="cmp">
<div class="row"><div class="t">Двійкові змінні MIP, найгірший випадок <span id="mtpMv"></span></div><div class="track"><i id="mtpMb" style="background:linear-gradient(90deg,#FF8A5A,#FF5A6E)"></i></div></div>
<div class="row"><div class="t">Окіл локального пошуку, найгірший випадок <span id="mtpLv"></span></div><div class="track"><i id="mtpLb" style="background:linear-gradient(90deg,#0866FF,#38D6FF)"></i></div></div>
</div>
<div class="verdict" id="mtpVerdict"></div>
<p class="note" style="margin-top:10px">Смужки використовують логарифмічну шкалу. Діапазони розмірів у висновку є ілюстративними; заявлене Meta правило полягає в застосуванні локального пошуку майже для всіх великих задач, а MIP — для задач малого та середнього розміру.</p>
</div>
<!-- PANE 4 -->
<div class="pane" id="mtpP3">
<p class="note">Показники роботи Rebalancer, опубліковані Meta (Engineering at Meta, 21 вересня 2026 року).</p>
<div class="grid" id="mtpCards">
<div class="card"><div class="n"><span data-c="40">0</span><em>млн</em></div><div class="d">задач розподілу розв’язується щодня</div></div>
<div class="card"><div class="n"><span data-c="30">0</span><em>+</em></div><div class="d">унікальних формулювань задач</div></div>
<div class="card"><div class="n"><span data-c="12">0</span><em>с</em></div><div class="d">час розв’язання P99 для 265 тис. об’єктів і 3,2 тис. контейнерів</div></div>
<div class="card"><div class="n"><span data-c="171">0</span><em>с</em></div><div class="d">середній час розв’язання для понад 1 млн об’єктів і 5 тис. контейнерів</div></div>
<div class="card"><div class="n"><span data-c="3.4" data-d="1">0</span><em>тис.+</em></div><div class="d">запусків для масштабу понад 1 млн об’єктів</div></div>
<div class="card"><div class="n"><span data-c="9">0</span><em>+ років</em></div><div class="d">використання в Meta до відкриття вихідного коду</div></div>
</div>
<div class="pills">
<span class="pill">Shard Manager: сегменти → сервери</span>
<span class="pill">RAS: сервери → сервіси</span>
<span class="pill">Taiji: периферійний трафік → дата-центри</span>
<span class="pill">Групування безсерверних функцій</span>
<span class="pill">Балансування навчання ML</span>
<span class="pill">Зустрічі → кімнати</span>
</div>
</div>
<div class="ft">
<span>Джерела: <a href="https://engineering.fb.com/2026/09/21/open-source/rebalancer-generic-high-performance-library-assignment-problems/" target="_blank" rel="noopener">Engineering at Meta</a> · <a href="https://github.com/facebook/rebalancer" target="_blank" rel="noopener">GitHub</a> · Вкладки 1–3 є спрощеними симуляціями</span>
<span class="brand">Створено Marktechpost</span>
</div>
</div>
<script>
(function(){
var R=document.getElementById('mtp-rebal');
function postH(){try{parent.postMessage({mtpRebalH:R.offsetHeight+40},'*');}catch(e){}}
var SIZES=[6,5,4,4,3,3,3,2,2,2,1,1], CAP=16, NS=4;
var START=[0,0,0,0,1,1,1,2,2,2,0,1];
var asg=START.slice(), step=0, evals=0, hist=[], timer=null, hot=-1;
function util(a){var u=[0,0,0,0];for(var i=0;i<a.length;i++)u[a[i]]+=SIZES[i];return u;}
function score(a){var u=util(a),v=0,o=0;for(var s=0;s<NS;s++){v+=Math.max(0,u[s]-CAP);o+=u[s]*u[s];}return [v,o];}
function better(x,y){return x[0]<y[0]||(x[0]===y[0]&&x[1]<y[1]);}
function bestMove(){
var cur=score(asg),best=null,bs=cur,n=0;
for(var i=0;i<asg.length;i++){for(var s=0;s<NS;s++){if(s===asg[i])continue;var b=asg.slice();b[i]=s;n++;var sc=score(b);if(better(sc,bs)){bs=sc;best={a:b,txt:'перемістити t'+(i+1)+' S'+(asg[i]+1)+' → S'+(s+1),ids:[i]};}}}
for(var i2=0;i2<asg.length;i2++)for(var j=i2+1;j<asg.length;j++){if(asg[i2]===asg[j])continue;var c=asg.slice();c[i2]=asg[j];c[j]=asg[i2];n++;var sc2=score(c);if(better(sc2,bs)){bs=sc2;best={a:c,txt:'поміняти місцями t'+(i2+1)+' 
t'+(j+1),ids:[i2,j]};}}
return {best:best,n:n,sc:bs};
}
var racksEl=document.getElementById('mtpRacks');
function rects(){var m={};racksEl.querySelectorAll('.chip').forEach(function(c){m[c.dataset.id]=c.getBoundingClientRect();});return m;}
function render(ids){
var before=rects(),u=util(asg),h='';
for(var r=0;r<2;r++){h+='<div class="rack"><div class="rl">Стійка '+(r?'B':'A')+' (область)</div><div class="srvs">';
for(var s=r*2;s<r*2+2;s++){var over=u[s]>CAP;
h+='<div class="srv'+(over?' over':'')+'"><div class="sn">S'+(s+1)+'<span>'+u[s]+' / '+CAP+' CPU</span></div><div class="bar"><i style="width:'+Math.min(100,u[s]/24*100)+'%"></i><u style="left:'+(CAP/24*100)+'%"></u></div><div class="chips">';
for(var i=0;i<asg.length;i++)if(asg[i]===s){h+='<div class="chip'+(ids&&ids.indexOf(i)>-1?' hot':'')+'" data-id="'+i+'" style="width:'+(30+SIZES[i]*8)+'px">t'+(i+1)+'·'+SIZES[i]+'</div>';}
h+='</div></div>';}
h+='</div></div>';}
racksEl.innerHTML=h;
racksEl.querySelectorAll('.chip').forEach(function(c){var b=before[c.dataset.id];if(!b)return;var a=c.getBoundingClientRect(),dx=b.left-a.left,dy=b.top-a.top;if(dx||dy){c.style.transition='none';c.style.transform='translate('+dx+'px,'+dy+'px)';requestAnimationFrame(function(){requestAnimationFrame(function(){c.style.transition='transform .55s cubic-bezier(.2,.8,.2,1)';c.style.transform='';});});}});
var sc=score(asg);
document.getElementById('mtpS').textContent=step;
document.getElementById('mtpE').textContent=evals;
var V=document.getElementById('mtpV');V.textContent=sc[0];V.className='v '+(sc[0]?'bad':'good');
var O=document.getElementById('mtpO');O.textContent=sc[1];O.className='v'+(sc[1]===324?' good':'');
spark();drawGraph(null);postH();
}
function spark(){
var s=document.getElementById('mtpSpark'),pts=hist.length?hist:[score(asg)[1]];
var mx=Math.max.apply(null,pts.concat([600])),mn=300,n=Math.max(pts.length-1,12);
var p=pts.map(function(v,i){return (i/n*790+5)+','+(65-(v-mn)/(mx-mn)*58);}).join(' ');
var ideal=65-(324-mn)/(mx-mn)*58;
s.innerHTML='<line x1="0" x2="800" y1="'+ideal+'" y2="'+ideal+'" stroke="#2BD99F" stroke-dasharray="4 4" opacity=".6"/><polyline points="'+p+'" fill="none" stroke="#38D6FF" stroke-width="2.5"/>'+pts.map(function(v,i){return '<circle cx="'+(i/n*790+5)+'" cy="'+(65-(v-mn)/(mx-mn)*58)+'" r="3.5" fill="#0866FF" stroke="#fff" stroke-width="1"/>';}).join('');
}
var logEl=document.getElementById('mtpLog');
function doStep(){
var r=bestMove();evals+=r.n;
if(!r.best){stop();logEl.textContent='Локальний оптимум: жодне переміщення або обмін не покращує результат ('+evals+' оцінювань).';render();return false;}
var old=asg;asg=r.best.a;step++;hist.push(score(asg)[1]);
var moved=r.best.ids;logEl.textContent='Крок '+step+': '+r.best.txt+' (перевірено '+r.n+' кандидатів)';
render(moved);drawGraph(diff(old,asg));return true;
}
function diff(a,b){var s={};for(var i=0;i<a.length;i++)if(a[i]!==b[i]){s[a[i]]=1;s[b[i]]=1;}return Object.keys(s).map(Number);}
function stop(){if(timer){clearInterval(timer);timer=null;}document.getElementById('mtpRun').textContent=' Запустити локальний пошук';}
document.getElementById('mtpRun').onclick=function(){if(timer){stop();return;}this.textContent='❚❚ Пауза';if(!doStep())return;timer=setInterval(function(){if(!doStep())stop();},900);};
document.getElementById('mtpStep').onclick=function(){stop();doStep();};
function resetTo(a,msg){stop();asg=a;step=0;evals=0;hist=[score(asg)[1]];logEl.textContent=msg;render();}
document.getElementById('mtpReset').onclick=function(){resetTo(START.slice(),'Сервер S1 починає роботу з перевищенням місткості на 4 CPU. Натисніть «Запустити».');};
document.getElementById('mtpShuf').onclick=function(){var a=[];for(var i=0;i<12;i++)a.push(Math.random()<.55?Math.floor(Math.random()*2):Math.floor(Math.random()*4));resetTo(a,'Новий випадковий початок. Натисніть «Запустити».');};
/* expression graph */
var G=document.getElementById('mtpGraph'),gLog=document.getElementById('mtpGLog');
var LX=[110,300,490,680];
function drawGraph(live){
live=live||[];var u=util(asg),sc=score(asg),h='';
function on(s){return live.indexOf(s)>-1;}
var any=live.length>0;
for(var s=0;s<4;s++){
h+='<path class="edge'+(on(s)?' live':'')+'" d="M'+LX[s]+',232 L'+LX[s]+',172"/>';
h+='<path class="edge'+(on(s)?' live':'')+'" d="M'+LX[s]+',138 C'+LX[s]+',100 300,110 300,78"/>';
h+='<path class="edge'+(on(s)?' live':'')+'" d="M'+(LX[s]+40)+',233 C'+(LX[s]+60)+',200 650,130 650,78"/>';
}
h+='<path class="edge'+(any?' live':'')+'" d="M300,44 L300,22"/><path class="edge'+(any?' live':'')+'" d="M650,44 L650,22"/>';
function node(x,y,w,label,val,l){return '<g class="node'+(l?' live':'')+'"><rect x="'+(x-w/2)+'" y="'+(y-17)+'" width="'+w+'" height="34" rx="8"/><text x="'+x+'" y="'+(y-2)+'">'+label+'</text><text class="val" x="'+x+'" y="'+(y+11)+'">'+val+'</text></g>';}
for(var k=0;k<4;k++){h+=node(LX[k],250,96,'U(S'+(k+1)+')','= '+u[k],on(k));h+=node(LX[k],155,96,'SQUARE','= '+u[k]*u[k],on(k));}
h+=node(300,61,120,'SUM','= '+sc[1],any);h+=node(650,61,120,'MAX','= '+Math.max.apply(null,u),any);
h+='<text x="300" y="14" fill="#4C9BFF" font-size="11" font-weight="700" text-anchor="middle">Ціль BalanceSpec</text>';
h+='<text x="650" y="14" fill="'+(Math.max.apply(null,u)>CAP?'#FF5A6E':'#2BD99F')+'" font-size="11" font-weight="700" text-anchor="middle">CapacitySpec: MAX ≤ '+CAP+(Math.max.apply(null,u)>CAP?' (порушено)':' (ок)')+'</text>';
h+='<text x="410" y="292" fill="#93A3BF" font-size="11" text-anchor="middle">Листи: використання ресурсів сервера · вузли, перераховані під час цього переміщення: '+(any?(live.length*2+2):0)+' із 10</text>';
G.innerHTML=h;
}
document.getElementById('mtpGMove').onclick=function(){stop();var i=Math.floor(Math.random()*12),s;do{s=Math.floor(Math.random()*4);}while(s===asg[i]);var old=asg;asg=asg.slice();asg[i]=s;evals++;step++;hist.push(score(asg)[1]);render([i]);var d=diff(old,asg);drawGraph(d);gLog.textContent='Переміщено t'+(i+1)+' S'+(old[i]+1)+' → S'+(s+1)+'. Лише '+(d.length*2+2)+' із 10 вузлів потребують нових значень.';};
document.getElementById('mtpGBest').onclick=function(){stop();var r=bestMove();evals+=r.n;if(!r.best){gLog.textContent='Досягнуто локального оптимуму. Спочатку спробуйте випадкове переміщення.';render();return;}var old=asg;asg=r.best.a;step++;hist.push(score(asg)[1]);render(r.best.ids);var d=diff(old,asg);drawGraph(d);gLog.textContent='Найкращий із '+r.n+' кандидатів: '+r.best.txt+'. Перераховано '+(d.length*2+2)+' із 10 вузлів.';};
/* solver picker */
var Os=document.getElementById('mtpOs'),Bs=document.getElementById('mtpBs');
function fmt(n){if(n>=1e9)return (n/1e9).toFixed(n>=1e10?0:1)+'B';if(n>=1e6)return (n/1e6).toFixed(n>=1e7?0:1)+'M';if(n>=1e3)return (n/1e3).toFixed(n>=1e4?0:1)+'k';return Math.round(n)+'';}
function pick(){
var o=exactO||Math.round(Math.pow(10,+Os.value)),b=exactB||Math.round(Math.pow(10,+Bs.value)),m=o*b,l=o+b;exactO=exactB=0;
document.getElementById('mtpOv').textContent=fmt(o);document.getElementById('mtpBv').textContent=fmt(b);
document.getElementById('mtpMv').textContent='≈ '+fmt(m);document.getElementById('mtpLv').textContent='≈ '+fmt(l);
document.getElementById('mtpMb').style.width=Math.min(100,Math.log10(m)/11*100)+'%';
document.getElementById('mtpLb').style.width=Math.min(100,Math.log10(l)/11*100)+'%';
var v=document.getElementById('mtpVerdict'),t;
if(m<=1e6){t='<b>Оптимальний MIP-розв’язувач — хороший початок.</b> Невелику модель можна передати HiGHS, Gurobi або FICO Xpress і отримати гарантовано оптимальний розподіл.';v.style.borderColor='#2BD99F';}
else if(m<=1e8){t='<b>Створіть прототип за допомогою MIP, а потім перейдіть до локального пошуку.</b> Meta зазначає, що це поширений підхід: спочатку отримати сильну базову модель за допомогою оптимального розв’язувача, а потім перейти на локальний пошук.';v.style.borderColor='#4C9BFF';}
else{t='<b>Локальний пошук.</b> У найгіршому випадку MIP потребував би ≈ '+fmt(m)+' двійкових змінних, тоді як кожен окіл локального пошуку залишається близьким до '+fmt(l)+'. Meta використовує цей підхід майже для всіх великих задач.';v.style.borderColor='#38D6FF';}
v.innerHTML=t;postH();
}
var exactO=0,exactB=0;Os.oninput=pick;Bs.oninput=pick;
document.querySelectorAll('#mtpP2 button[data-o]').forEach(function(btn){btn.onclick=function(){exactO=+btn.dataset.o;exactB=+btn.dataset.bn;Os.value=Math.log10(+btn.dataset.o);Bs.value=Math.log10(+btn.dataset.bn);pick();};});
/* stats */
var counted=false;
function count(){
var cards=document.querySelectorAll('#mtpCards .card');
cards.forEach(function(c,i){c.classList.remove('in');setTimeout(function(){c.classList.add('in');},90*i);});
document.querySelectorAll('#mtpCards [data-c]').forEach(function(el){var tgt=+el.dataset.c,dp=+(el.dataset.d||0),t0=null;
function f(ts){if(!t0)t0=ts;var p=Math.min(1,(ts-t0)/1100),e=1-Math.pow(1-p,3);el.textContent=(tgt*e).toFixed(dp);if(p<1)requestAnimationFrame(f);}requestAnimationFrame(f);});
}
/* tabs */
var tabs=R.querySelectorAll('.tab');
tabs.forEach(function(t){t.onclick=function(){tabs.forEach(function(x){x.classList.remove('on');});t.classList.add('on');
R.querySelectorAll('.pane').forEach(function(p){p.classList.remove('on');});document.getElementById('mtpP'+t.dataset.p).classList.add('on');
if(t.dataset.p==='3')count();if(t.dataset.p==='1')drawGraph(null);setTimeout(postH,60);setTimeout(postH,450);};});
hist=[score(asg)[1]];render();pick();
window.addEventListener('load',postH);window.addEventListener('resize',postH);setTimeout(postH,300);
})();
</script>
</body></html>">
t'+(j+1),ids:[i2,j]};}}
return {best:best,n:n,sc:bs};
}
var racksEl=document.getElementById('mtpRacks');
function rects(){var m={};racksEl.querySelectorAll('.chip').forEach(function(c){m[c.dataset.id]=c.getBoundingClientRect();});return m;}
function render(ids){
var before=rects(),u=util(asg),h='';
for(var r=0;r<2;r++){h+='<div class="rack"><div class="rl">Стійка '+(r?'B':'A')+' (область)</div><div class="srvs">';
for(var s=r*2;s<r*2+2;s++){var over=u[s]>CAP;
h+='<div class="srv'+(over?' over':'')+'"><div class="sn">S'+(s+1)+'<span>'+u[s]+' / '+CAP+' CPU</span></div><div class="bar"><i style="width:'+Math.min(100,u[s]/24*100)+'%"></i><u style="left:'+(CAP/24*100)+'%"></u></div><div class="chips">';
for(var i=0;i<asg.length;i++)if(asg[i]===s){h+='<div class="chip'+(ids&&ids.indexOf(i)>-1?' hot':'')+'" data-id="'+i+'" style="width:'+(30+SIZES[i]*8)+'px">t'+(i+1)+'·'+SIZES[i]+'</div>';}
h+='</div></div>';}
h+='</div></div>';}
racksEl.innerHTML=h;
racksEl.querySelectorAll('.chip').forEach(function(c){var b=before[c.dataset.id];if(!b)return;var a=c.getBoundingClientRect(),dx=b.left-a.left,dy=b.top-a.top;if(dx||dy){c.style.transition='none';c.style.transform='translate('+dx+'px,'+dy+'px)';requestAnimationFrame(function(){requestAnimationFrame(function(){c.style.transition='transform .55s cubic-bezier(.2,.8,.2,1)';c.style.transform='';});});}});
var sc=score(asg);
document.getElementById('mtpS').textContent=step;
document.getElementById('mtpE').textContent=evals;
var V=document.getElementById('mtpV');V.textContent=sc[0];V.className='v '+(sc[0]?'bad':'good');
var O=document.getElementById('mtpO');O.textContent=sc[1];O.className='v'+(sc[1]===324?' good':'');
spark();drawGraph(null);postH();
}
function spark(){
var s=document.getElementById('mtpSpark'),pts=hist.length?hist:[score(asg)[1]];
var mx=Math.max.apply(null,pts.concat([600])),mn=300,n=Math.max(pts.length-1,12);
var p=pts.map(function(v,i){return (i/n*790+5)+','+(65-(v-mn)/(mx-mn)*58);}).join(' ');
var ideal=65-(324-mn)/(mx-mn)*58;
s.innerHTML='<line x1="0" x2="800" y1="'+ideal+'" y2="'+ideal+'" stroke="#2BD99F" stroke-dasharray="4 4" opacity=".6"/><polyline points="'+p+'" fill="none" stroke="#38D6FF" stroke-width="2.5"/>'+pts.map(function(v,i){return '<circle cx="'+(i/n*790+5)+'" cy="'+(65-(v-mn)/(mx-mn)*58)+'" r="3.5" fill="#0866FF" stroke="#fff" stroke-width="1"/>';}).join('');
}
var logEl=document.getElementById('mtpLog');
function doStep(){
var r=bestMove();evals+=r.n;
if(!r.best){stop();logEl.textContent='Локальний оптимум: жодне переміщення або обмін не покращує результат ('+evals+' оцінювань).';render();return false;}
var old=asg;asg=r.best.a;step++;hist.push(score(asg)[1]);
var moved=r.best.ids;logEl.textContent='Крок '+step+': '+r.best.txt+' (перевірено '+r.n+' кандидатів)';
render(moved);drawGraph(diff(old,asg));return true;
}
function diff(a,b){var s={};for(var i=0;i<a.length;i++)if(a[i]!==b[i]){s[a[i]]=1;s[b[i]]=1;}return Object.keys(s).map(Number);}
function stop(){if(timer){clearInterval(timer);timer=null;}document.getElementById('mtpRun').textContent=' Запустити локальний пошук';}
document.getElementById('mtpRun').onclick=function(){if(timer){stop();return;}this.textContent='❚❚ Пауза';if(!doStep())return;timer=setInterval(function(){if(!doStep())stop();},900);};
document.getElementById('mtpStep').onclick=function(){stop();doStep();};
function resetTo(a,msg){stop();asg=a;step=0;evals=0;hist=[score(asg)[1]];logEl.textContent=msg;render();}
document.getElementById('mtpReset').onclick=function(){resetTo(START.slice(),'Сервер S1 починає роботу з перевищенням місткості на 4 CPU. Натисніть «Запустити».');};
document.getElementById('mtpShuf').onclick=function(){var a=[];for(var i=0;i<12;i++)a.push(Math.random()<.55?Math.floor(Math.random()*2):Math.floor(Math.random()*4));resetTo(a,'Новий випадковий початок. Натисніть «Запустити».');};
/* expression graph */
var G=document.getElementById('mtpGraph'),gLog=document.getElementById('mtpGLog');
var LX=[110,300,490,680];
function drawGraph(live){
live=live||[];var u=util(asg),sc=score(asg),h='';
function on(s){return live.indexOf(s)>-1;}
var any=live.length>0;
for(var s=0;s<4;s++){
h+='<path class="edge'+(on(s)?' live':'')+'" d="M'+LX[s]+',232 L'+LX[s]+',172"/>';
h+='<path class="edge'+(on(s)?' live':'')+'" d="M'+LX[s]+',138 C'+LX[s]+',100 300,110 300,78"/>';
h+='<path class="edge'+(on(s)?' live':'')+'" d="M'+(LX[s]+40)+',233 C'+(LX[s]+60)+',200 650,130 650,78"/>';
}
h+='<path class="edge'+(any?' live':'')+'" d="M300,44 L300,22"/><path class="edge'+(any?' live':'')+'" d="M650,44 L650,22"/>';
function node(x,y,w,label,val,l){return '<g class="node'+(l?' live':'')+'"><rect x="'+(x-w/2)+'" y="'+(y-17)+'" width="'+w+'" height="34" rx="8"/><text x="'+x+'" y="'+(y-2)+'">'+label+'</text><text class="val" x="'+x+'" y="'+(y+11)+'">'+val+'</text></g>';}
for(var k=0;k<4;k++){h+=node(LX[k],250,96,'U(S'+(k+1)+')','= '+u[k],on(k));h+=node(LX[k],155,96,'SQUARE','= '+u[k]*u[k],on(k));}
h+=node(300,61,120,'SUM','= '+sc[1],any);h+=node(650,61,120,'MAX','= '+Math.max.apply(null,u),any);
h+='<text x="300" y="14" fill="#4C9BFF" font-size="11" font-weight="700" text-anchor="middle">Ціль BalanceSpec</text>';
h+='<text x="650" y="14" fill="'+(Math.max.apply(null,u)>CAP?'#FF5A6E':'#2BD99F')+'" font-size="11" font-weight="700" text-anchor="middle">CapacitySpec: MAX ≤ '+CAP+(Math.max.apply(null,u)>CAP?' (порушено)':' (ок)')+'</text>';
h+='<text x="410" y="292" fill="#93A3BF" font-size="11" text-anchor="middle">Листи: використання ресурсів сервера · вузли, перераховані під час цього переміщення: '+(any?(live.length*2+2):0)+' із 10</text>';
G.innerHTML=h;
}
document.getElementById('mtpGMove').onclick=function(){stop();var i=Math.floor(Math.random()*12),s;do{s=Math.floor(Math.random()*4);}while(s===asg[i]);var old=asg;asg=asg.slice();asg[i]=s;evals++;step++;hist.push(score(asg)[1]);render([i]);var d=diff(old,asg);drawGraph(d);gLog.textContent='Переміщено t'+(i+1)+' S'+(old[i]+1)+' → S'+(s+1)+'. Лише '+(d.length*2+2)+' із 10 вузлів потребують нових значень.';};
document.getElementById('mtpGBest').onclick=function(){stop();var r=bestMove();evals+=r.n;if(!r.best){gLog.textContent='Досягнуто локального оптимуму. Спочатку спробуйте випадкове переміщення.';render();return;}var old=asg;asg=r.best.a;step++;hist.push(score(asg)[1]);render(r.best.ids);var d=diff(old,asg);drawGraph(d);gLog.textContent='Найкращий із '+r.n+' кандидатів: '+r.best.txt+'. Перераховано '+(d.length*2+2)+' із 10 вузлів.';};
/* solver picker */
var Os=document.getElementById('mtpOs'),Bs=document.getElementById('mtpBs');
function fmt(n){if(n>=1e9)return (n/1e9).toFixed(n>=1e10?0:1)+'B';if(n>=1e6)return (n/1e6).toFixed(n>=1e7?0:1)+'M';if(n>=1e3)return (n/1e3).toFixed(n>=1e4?0:1)+'k';return Math.round(n)+'';}
function pick(){
var o=exactO||Math.round(Math.pow(10,+Os.value)),b=exactB||Math.round(Math.pow(10,+Bs.value)),m=o*b,l=o+b;exactO=exactB=0;
document.getElementById('mtpOv').textContent=fmt(o);document.getElementById('mtpBv').textContent=fmt(b);
document.getElementById('mtpMv').textContent='≈ '+fmt(m);document.getElementById('mtpLv').textContent='≈ '+fmt(l);
document.getElementById('mtpMb').style.width=Math.min(100,Math.log10(m)/11*100)+'%';
document.getElementById('mtpLb').style.width=Math.min(100,Math.log10(l)/11*100)+'%';
var v=document.getElementById('mtpVerdict'),t;
if(m<=1e6){t='<b>Оптимальний MIP-розв’язувач — хороший початок.</b> Невелику модель можна передати HiGHS, Gurobi або FICO Xpress і отримати гарантовано оптимальний розподіл.';v.style.borderColor='#2BD99F';}
else if(m<=1e8){t='<b>Створіть прототип за допомогою MIP, а потім перейдіть до локального пошуку.</b> Meta зазначає, що це поширений підхід: спочатку отримати сильну базову модель за допомогою оптимального розв’язувача, а потім перейти на локальний пошук.';v.style.borderColor='#4C9BFF';}
else{t='<b>Локальний пошук.</b> У найгіршому випадку MIP потребував би ≈ '+fmt(m)+' двійкових змінних, тоді як кожен окіл локального пошуку залишається близьким до '+fmt(l)+'. Meta використовує цей підхід майже для всіх великих задач.';v.style.borderColor='#38D6FF';}
v.innerHTML=t;postH();
}
var exactO=0,exactB=0;Os.oninput=pick;Bs.oninput=pick;
document.querySelectorAll('#mtpP2 button[data-o]').forEach(function(btn){btn.onclick=function(){exactO=+btn.dataset.o;exactB=+btn.dataset.bn;Os.value=Math.log10(+btn.dataset.o);Bs.value=Math.log10(+btn.dataset.bn);pick();};});
/* stats */
var counted=false;
function count(){
var cards=document.querySelectorAll('#mtpCards .card');
cards.forEach(function(c,i){c.classList.remove('in');setTimeout(function(){c.classList.add('in');},90*i);});
document.querySelectorAll('#mtpCards [data-c]').forEach(function(el){var tgt=+el.dataset.c,dp=+(el.dataset.d||0),t0=null;
function f(ts){if(!t0)t0=ts;var p=Math.min(1,(ts-t0)/1100),e=1-Math.pow(1-p,3);el.textContent=(tgt*e).toFixed(dp);if(p<1)requestAnimationFrame(f);}requestAnimationFrame(f);});
}
/* tabs */
var tabs=R.querySelectorAll('.tab');
tabs.forEach(function(t){t.onclick=function(){tabs.forEach(function(x){x.classList.remove('on');});t.classList.add('on');
R.querySelectorAll('.pane').forEach(function(p){p.classList.remove('on');});document.getElementById('mtpP'+t.dataset.p).classList.add('on');
if(t.dataset.p==='3')count();if(t.dataset.p==='1')drawGraph(null);setTimeout(postH,60);setTimeout(postH,450);};});
hist=[score(asg)[1]];render();pick();
window.addEventListener('load',postH);window.addEventListener('resize',postH);setTimeout(postH,300);
})();
</script>
</body></html>">
Rebalancer у порівнянні з найближчими альтернативами з відкритим кодом
| Функція | Meta Rebalancer | Google OR-Tools | Timefold Solver (Community) |
|---|---|---|---|
| Ліцензія | Apache 2.0 | Apache 2.0 | Apache 2.0 (корпоративна версія є комерційною) |
| Основна мова | C++ | C++ | Java |
| API | C++, Python | C++, Python, Java, C# | Java, Kotlin |
| Фокус | Загальний розподіл (об’єкти до контейнерів) | Широкий набір: CP-SAT, LP, оболонки MIP, маршрутизація, пакування, розподіл | Планування: маршрутизація, складання розкладів персоналу, планування, призначення завдань |
| Локальний пошук | Так, паралельний, на графі виразів | Так, у розв’язувачі маршрутизації (керований локальний пошук, імітація відпалу, пошук табу) | Так, основний рушій (табу, імітація відпалу, пізнє прийняття) |
| Бекенди MIP | FICO Xpress, Gurobi, HiGHS | Оболонки для комерційних і відкритих MIP-розв’язувачів | Не використовується |
| Інтерфейс налагодження | Rebalancer Explorer (Docker) | Не зазначено у README | Benchmarker; аналіз оцінок у комерційних версіях |
| Встановлення | pip install rebalancer | pip install ortools | Maven, JDK 21+ |
OR-Tools охоплює більше класів задач, а Timefold орієнтований на планування та маршрутизацію у JVM. Перевага Rebalancer — одна специфікація розподілу, яка працює і з локальним пошуком, і з MIP.
Ключові висновки
- Rebalancer моделює будь-яку задачу розподілу як об’єкти, контейнери, обмеження та цілі.
- Специфікації компілюються в граф виразів, який розв’язується за допомогою локального пошуку або MIP-розв’язувача.
- Бекенди MIP включають FICO Xpress, Gurobi та відкритий HiGHS.
- Meta розв’язує близько 40 млн задач на день; P99 становить 12 с для 265 тис. об’єктів і 3,2 тис. контейнерів.
- Apache 2.0, API для C++ і Python, доступний для встановлення з PyPI вже сьогодні.
Ознайомтеся зі статтею, репозиторієм GitHub і технічними деталями. Усі заслуги належать досліднику цього проєкту. Також підписуйтеся на нас у Twitter і не забудьте приєднатися до нашого субреддіту про ML із понад 150 тис. учасників та підписатися на нашу розсилку. Стривайте! Ви користуєтеся Telegram? тепер ви також можете приєднатися до нас у Telegram.
Перекладено автоматично з англійської. Оригінал статті — за посиланням нижче.