Meta AI открыла исходный код Rebalancer: решатель задач на C++, обрабатывающий около 40 миллионов задач размещения в день
Meta открыла исходный код Rebalancer — библиотеки на C++ с интерфейсом Python для решения задач распределения. Она определяет, какие объекты помещать в какие контейнеры с учетом ограничений и целевых показателей. Согласно публикации Engineering at Meta, Rebalancer используется для распределения ресурсов в Meta уже более 9 лет. Релиз распространяется по лицензии 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 выделяет 2 препятствия: удобство использования и масштабируемость. Инженерам сложно переводить политики в точные формулы, а многие задачи являются 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.
Производственные показатели Meta
- Около 40 миллионов задач распределения решается в день, всего используется более 30 уникальных формулировок.
- Время решения на уровне P99 составляет 12 секунд для 265 тысяч объектов и 3,2 тысячи контейнеров.
- Для задач с более чем 1 миллионом объектов и 5 тысячами контейнеров среднее время составляет 171 секунду; показатель рассчитан по более чем 3,4 тысячи запусков.
Лучшие варианты применения Rebalancer
- Размещение шардов, задач или контейнеров в кластере: распределение работы между серверами с ограничениями по CPU и памяти при размещении реплик на разных стойках. Meta использует этот подход в Shard Manager и RAS.
- Балансировка трафика и рабочих нагрузок между регионами: маршрутизация пользовательского трафика или задач в дата-центры с поиском компромисса между задержкой и нагрузкой. Taiji делает это для периферийного трафика, а Meta балансирует обучение ML-моделей по приоритету.
- Операционное распределение за пределами инфраструктуры: назначение обращений в службу поддержки инженерам, встреч — переговорным комнатам или рабочих мест — сотрудникам с учетом ограничений вместимости. Meta использовала все 3 варианта.
Отладка с помощью Rebalancer Explorer
Специалисты по моделированию в Meta тратили большую часть времени на отладку поведения решателя. Rebalancer Explorer — веб-интерфейс в Docker, созданный для этой цели. Он показывает связывающие ограничения, эффекты ослабления и причины, по которым объект оказался в конкретном контейнере.
Интерактивное объяснение
Run local search</button>
<button class="b" id="mtpStep">Step once</button>
<button class="b" id="mtpShuf">Random bad start</button>
<button class="b" id="mtpReset">Reset</button>
</div>
<div class="stats">
<div class="st"><div class="k">Step</div><div class="v" id="mtpS">0</div></div>
<div class="st"><div class="k">Moves evaluated</div><div class="v" id="mtpE">0</div></div>
<div class="st"><div class="k">Capacity overflow</div><div class="v" id="mtpV">0</div></div>
<div class="st"><div class="k">Balance objective</div><div class="v" id="mtpO">0</div></div>
</div>
<div class="racks" id="mtpRacks"></div>
<div class="spark"><div class="k">Objective over steps (lower is better, ideal = 324)</div>
<svg id="mtpSpark" viewBox="0 0 800 70" width="100%" height="70" preserveAspectRatio="none"></svg>
</div>
<div class="log" id="mtpLog">Server S1 starts 4 CPU over capacity. Press Run.</div>
</div>
<!-- PANE 2 -->
<div class="pane" id="mtpP1">
<p class="note">Rebalancer compiles specs into a <b>directed acyclic expression graph</b>. Leaves hold each server's utilization; SQUARE, SUM and MAX nodes sit above them. When one task moves, only the leaves it touches and their ancestors need new values. The graph uses the same live state as tab 1.</p>
<div class="btns">
<button class="b pri" id="mtpGMove">Move a random task</button>
<button class="b" id="mtpGBest">Apply best local-search move</button>
</div>
<div class="gwrap"><svg id="mtpGraph" viewBox="0 0 820 300" width="100%"></svg></div>
<div class="log" id="mtpGLog">Press a button to move a task.</div>
</div>
<!-- PANE 3 -->
<div class="pane" id="mtpP2">
<p class="note">The MIP model needs about one binary variable per object per bin, so it grows as <b>O(objects × bins)</b>. A local-search neighborhood grows as <b>O(objects + bins)</b>. Drag the sliders or load Meta's published sizes.</p>
<div class="btns">
<button class="b" data-o="500" data-bn="20">Small: 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>Objects <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>Bins <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 binary variables, worst case <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">Local-search neighborhood, worst case <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">Bars use a log scale. Size bands in the verdict are illustrative; Meta's stated rule is local search for almost all large problems and MIP for small to mid-size ones.</p>
</div>
<!-- PANE 4 -->
<div class="pane" id="mtpP3">
<p class="note">Production figures published by Meta for Rebalancer (Engineering at Meta, Sep 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">assignment problems solved per day</div></div>
<div class="card"><div class="n"><span data-c="30">0</span><em>+</em></div><div class="d">unique problem formulations</div></div>
<div class="card"><div class="n"><span data-c="12">0</span><em>s</em></div><div class="d">P99 solve time on 265k objects and 3.2k bins</div></div>
<div class="card"><div class="n"><span data-c="171">0</span><em>s</em></div><div class="d">average solve for 1M+ objects and 5k bins</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">runs at that 1M+ object scale</div></div>
<div class="card"><div class="n"><span data-c="9">0</span><em>+ yrs</em></div><div class="d">in use across Meta before open-sourcing</div></div>
</div>
<div class="pills">
<span class="pill">Shard Manager: shards → servers</span>
<span class="pill">RAS: servers → services</span>
<span class="pill">Taiji: edge traffic → datacenters</span>
<span class="pill">Serverless function grouping</span>
<span class="pill">ML training balancing</span>
<span class="pill">Meetings → rooms</span>
</div>
</div>
<div class="ft">
<span>Sources: <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> · Tabs 1 to 3 are simplified simulations</span>
<span class="brand">Built by 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:'move 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:'swap 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">Rack '+(r?'B':'A')+' (scope)</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='Local optimum: no move or swap improves the score ('+evals+' evaluations).';render();return false;}
var old=asg;asg=r.best.a;step++;hist.push(score(asg)[1]);
var moved=r.best.ids;logEl.textContent='Step '+step+': '+r.best.txt+' (checked '+r.n+' candidates)';
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=' Run local search';}
document.getElementById('mtpRun').onclick=function(){if(timer){stop();return;}this.textContent='❚❚ Pause';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(),'Server S1 starts 4 CPU over capacity. Press Run.');};
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,'New random start. Press Run.');};
/* 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 objective</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?' (violated)':' (ok)')+'</text>';
h+='<text x="410" y="292" fill="#93A3BF" font-size="11" text-anchor="middle">Leaves: utilization per server · nodes recomputed this move: '+(any?(live.length*2+2):0)+' of 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='Moved t'+(i+1)+' S'+(old[i]+1)+' → S'+(s+1)+'. Only '+(d.length*2+2)+' of 10 nodes needed new values.';};
document.getElementById('mtpGBest').onclick=function(){stop();var r=bestMove();evals+=r.n;if(!r.best){gLog.textContent='Local optimum reached. Try a random move first.';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='Best of '+r.n+' candidates: '+r.best.txt+'. Recomputed '+(d.length*2+2)+' of 10 nodes.';};
/* 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>Optimal (MIP) solver is a good start.</b> Small model: hand it to HiGHS, Gurobi or FICO Xpress and get a provably optimal assignment.';v.style.borderColor='#2BD99F';}
else if(m<=1e8){t='<b>Prototype with MIP, then move to local search.</b> Meta says this is a common path: find a strong baseline with the optimal solver, then migrate.';v.style.borderColor='#4C9BFF';}
else{t='<b>Local search.</b> The MIP would need ≈ '+fmt(m)+' binary variables in the worst case, while each local-search neighborhood stays near '+fmt(l)+'. Meta runs almost all large problems this way.';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">Rack '+(r?'B':'A')+' (scope)</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='Local optimum: no move or swap improves the score ('+evals+' evaluations).';render();return false;}
var old=asg;asg=r.best.a;step++;hist.push(score(asg)[1]);
var moved=r.best.ids;logEl.textContent='Step '+step+': '+r.best.txt+' (checked '+r.n+' candidates)';
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=' Run local search';}
document.getElementById('mtpRun').onclick=function(){if(timer){stop();return;}this.textContent='❚❚ Pause';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(),'Server S1 starts 4 CPU over capacity. Press Run.');};
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,'New random start. Press Run.');};
/* 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 objective</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?' (violated)':' (ok)')+'</text>';
h+='<text x="410" y="292" fill="#93A3BF" font-size="11" text-anchor="middle">Leaves: utilization per server · nodes recomputed this move: '+(any?(live.length*2+2):0)+' of 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='Moved t'+(i+1)+' S'+(old[i]+1)+' → S'+(s+1)+'. Only '+(d.length*2+2)+' of 10 nodes needed new values.';};
document.getElementById('mtpGBest').onclick=function(){stop();var r=bestMove();evals+=r.n;if(!r.best){gLog.textContent='Local optimum reached. Try a random move first.';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='Best of '+r.n+' candidates: '+r.best.txt+'. Recomputed '+(d.length*2+2)+' of 10 nodes.';};
/* 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>Optimal (MIP) solver is a good start.</b> Small model: hand it to HiGHS, Gurobi or FICO Xpress and get a provably optimal assignment.';v.style.borderColor='#2BD99F';}
else if(m<=1e8){t='<b>Prototype with MIP, then move to local search.</b> Meta says this is a common path: find a strong baseline with the optimal solver, then migrate.';v.style.borderColor='#4C9BFF';}
else{t='<b>Local search.</b> The MIP would need ≈ '+fmt(m)+' binary variables in the worst case, while each local-search neighborhood stays near '+fmt(l)+'. Meta runs almost all large problems this way.';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 и не забудьте присоединиться к нашему сабреддиту о машинном обучении с аудиторией более 150 тысяч человек и подписаться на нашу рассылку. Постойте! Вы есть в Telegram? Теперь к нам можно присоединиться и в Telegram.
Переведено автоматически с английского. Оригинал статьи — по ссылке ниже.