Meta AI публикува с отворен код Rebalancer: C++ решател на задачи за разполагане, който обработва около 40 милиона задачи дневно
Meta пусна с отворен код Rebalancer — C++ библиотека с Python интерфейс за решаване на задачи за разпределение. Тя определя кои обекти в кои контейнери да бъдат поставени при зададени ограничения и цели. Според публикация на Engineering at Meta Rebalancer се използва за разпределение на ресурси в Meta повече от 9 години. Версията се разпространява под лиценз Apache 2.0 и включва документация, пакет за PyPI и потребителски интерфейс за отстраняване на грешки, наречен Rebalancer Explorer.
Може ли да бъде внедрен? Да. pip install rebalancer инсталира v1.0.4 за Python 3.12+, с предварително компилирани пакети за Linux x86-64 и macOS 14+ ARM64. Съществуват и пакети .deb, .rpm и Homebrew. PyPI все още класифицира проекта като Alpha.
Какъв проблем решава Rebalancer?
Задачите за разпределение се срещат в целия стек на Meta. Шкафовете се поставят в центрове за данни, сървърите се разпределят към услуги, задачите — към сървъри, а потребителският трафик — към центрове за данни. Meta посочва 2 основни пречки: използваемост и мащабируемост. Инженерите срещат трудности при превръщането на политиките в точни формули, а много от задачите са NP-трудни и прекалено големи за комерсиалните решатели.
Отговорът на Rebalancer е да раздели начина, по който проблемът се задава, от начина, по който се решава. Дизайнът е описан подробно в публикацията за OSDI 2024, Оптимизиране на разпределението на ресурси в хипермащабни центрове за данни.
Как работи слоят за спецификация
Езикът за спецификации има 3 слоя:
- Конструкции за моделиране: измерения (атрибути като процесор или място за съхранение), дялове (групи от обекти), обхвати (групи от контейнери) и използване.
- Expression API: агрегиране на използването със SUM или MAX или преобразуването му чрез операции като SQUARE.
- Spec API: десетки предварително дефинирани цели и ограничения, изброени в документацията.
Примерът на Meta моделира задачите като обекти, сървърите като контейнери, а шкафовете като обхват. CapacitySpec ограничава процесора и мястото за съхранение на сървър. GroupCountSpec запазва 1 тип задача на шкаф. BalanceSpec балансира използването на всеки сървър и по двете измерения.
Един граф на изразите, два решателя
Rebalancer компилира спецификацията в насочен ацикличен граф на изразите. Листата съдържат стойности за използването, а над тях се намират възлите за агрегиране и преобразуване. Потребителите предоставят първоначално разпределение и условие за спиране. Ограниченията, които първоначалното разпределение вече нарушава, се превръщат в цели с висок приоритет.
Оптимален решател: Графът се преобразува в смесена целочислена програма за FICO Xpress, Gurobi или HiGHS. Агрегирането на променливи и премахването на симетриите намаляват размера на моделите. Най-лошият случай за размера на модела все още е O(обекти × контейнери). Най-големите задачи на Meta са прекалено големи за всеки MIP решател.
Локално търсене: Този решател работи директно върху графа на изразите. Той изследва преместването на обекти към други контейнери, като в най-лошия случай съседството е O(обекти + контейнери). След това прилага най-добрия кандидат, който не нарушава ограничения. Оценяването е паралелизирано и достига милиони оценки в секунда, а пространството за търсене се съкращава.
Meta използва локално търсене за почти всички големи задачи, а MIP — за малки и средни, като често първо създава прототип с MIP.
Производствени показатели в Meta
- Около 40 милиона задачи за разпределение се решават на ден в над 30 уникални формулировки.
- P99 време за решаване от 12 секунди при 265 хил. обекта и 3,2 хил. контейнера.
- Задачите с над 1 милион обекта и 5 хил. контейнера отнемат средно 171 секунди при над 3,4 хил. изпълнения.
Най-подходящи случаи на употреба за Rebalancer
- Поставяне на шарди, задачи или контейнери в клъстер: Разпределяне на работа към сървъри при ограничения за процесора и паметта, като репликите се разпръскват между шкафовете. Shard Manager и RAS на Meta използват този модел.
- Балансиране на трафика и натоварванията между регионите: Насочване на потребителски трафик или задачи към центрове за данни, като се търгува между латентност и натоварване. Taiji прави това за периферния трафик, а Meta балансира обучението на ML модели според приоритета.
- Оперативно разпределение извън инфраструктурата: Съпоставяне на заявки за поддръжка с инженери, срещи със зали или бюра с хора при спазване на ограниченията за капацитет. Meta е използвала и трите подхода.
Отстраняване на грешки с 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">Meta P99: 265k × 3,2k</button>
<button class="b" data-o="1000000" data-bn="5000">Meta XL: 1M × 5k</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">Производствени показатели, публикувани от Meta за Rebalancer (Engineering at Meta, 21 септември 2026 г.).</p>
<div class="grid" id="mtpCards">
<div class="card"><div class="n"><span data-c="40">0</span><em>M</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>s</em></div><div class="d">P99 време за решаване при 265k обекта и 3,2k контейнера</div></div>
<div class="card"><div class="n"><span data-c="171">0</span><em>s</em></div><div class="d">средно време за решаване при над 1M обекта и 5k контейнера</div></div>
<div class="card"><div class="n"><span data-c="3.4" data-d="1">0</span><em>k+</em></div><div class="d">изпълнения при мащаб над 1M обекта</div></div>
<div class="card"><div class="n"><span data-c="9">0</span><em>+ yrs</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 (Enterprise изданието е комерсиално) |
| Основен език | C++ | C++ | Java |
| API | C++, Python | C++, Python, Java, C# | Java, Kotlin |
| Фокус | Общо разпределение (обекти към контейнери) | Широк набор: CP-SAT, LP, MIP обвивки, маршрутизиране, опаковане, разпределение | Планиране: маршрутизиране, графици на смените, планиране, разпределение на задачи |
| Локално търсене | Да, паралелно, върху граф на изразите | Да, в решателя за маршрутизиране (насочено локално търсене, симулирано отгряване, tabu) | Да, основен механизъм (tabu, симулирано отгряване, късно приемане) |
| 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, C++ и Python API, достъпен за инсталиране от PyPI още днес.
Разгледайте публикацията, GitHub хранилището и техническите подробности. Цялата заслуга принадлежи на изследователя на този проект. Също така, не се колебайте да ни последвате в Twitter и не забравяйте да се присъедините към нашия ML SubReddit с над 150 хил. членове и да се абонирате за нашия бюлетин. Чакайте! В Telegram ли сте? вече можете да се присъедините към нас и в Telegram.
Преведено автоматично от английски. Оригиналната статия е на връзката по-долу.