Meta, atama problemleri kitaplığı Rebalancer'ı açık kaynak yaptı

Meta, Rebalancer'ı açık kaynak yaptı

Meta, Rebalancer'ı Apache 2.0 lisansıyla açık kaynak olarak yayımladı. Kitaplık atama problemlerini çözüyor: verilen nesne ve kutu kümeleri için kısıtları sağlayan ve belirli hedefleri optimize eden yerleşimi buluyor. Şirkete göre bu çözücü, dokuz yıldan uzun süredir Meta'nın altyapısında kullanılıyor.

Sürümle birlikte facebook/rebalancer GitHub deposu, dokümantasyon, PyPI'daki Python paketi ve Docker'da çalışan Rebalancer Explorer arayüzü yayımlandı.

Tek kitaplık, birçok atama problemi

Aynı formülasyon Meta altyapısının birçok katmanında kullanılıyor: raflar, güç ve soğutma sınırlarına uyarak elektrik arıza alanlarına dağıtılmak üzere veri merkezlerine yerleştiriliyor; sunucular hata toleransı için hizmetlere atanıyor; kullanıcı trafiği ise gecikme ve yükü dengelemek için dağıtılmış veri merkezlerine yönlendiriliyor.

Rebalancer, yeniden kullanılabilir optimizasyon çatılarının önündeki iki engeli aşıyor: kullanım kolaylığı ve ölçeklenebilirlik. Politikaları elle formüllere çevirmek yerine mühendisler problemi nesneler, kutular, kısıtlar ve hedeflerle tanımlıyor; Rebalancer bunu ifade grafiği (expression graph) adı verilen yönlü çevrimsiz bir grafa dönüştürüyor. CapacitySpec, GroupCountSpec ve BalanceSpec gibi şartnameler yaygın hedefleri yeniden kullanılabilir tariflere dönüştürüyor.

Optimal çözücü ve yerel arama

Optimal çözücü grafiği FICO Xpress, Gurobi veya HiGHS için karma tam sayılı programlama modeline dönüştürüyor ve modeli değişken birleştirme ve simetri kırma ile küçültüyor. En kötü durumda model boyutu nesne sayısı ile kutu sayısının çarpımı kadar büyüyor; en büyük problemler hiçbir MIP çözücüsüne sığmıyor.

Yerel arama çözücüsü doğrudan grafik üzerinde çalışıyor ve nesnelerin kutular arasında taşınmasını inceliyor. Komşuluk boyutu nesne ve kutu sayılarının toplamıyla büyüyor, paralelleştirme saniyede milyonlarca değerlendirmeye izin veriyor; bu yüzden Meta'da büyük ölçekli problemlerin neredeyse tamamı yerel aramayla çözülüyor.

Meta'daki ölçek ve ötesi

Meta'ya göre Rebalancer günde yaklaşık 40 milyon atama problemini 30'dan fazla formülasyonla çözüyor. 265 bin nesne ve 3.200 kutudan oluşan bir problemde P99 çözüm süresi 12 saniye; 1 milyondan fazla nesne ve 5.000 kutu içeren problemlerde ortalama süre 171 saniye.

Kitaplık altyapı dışında toplantıları odalara atamak, destek taleplerini mühendislere yönlendirmek ve masa yerleşimlerini optimize etmek için de kullanıldı. Meta benzer problemlerin sağlık, enerji ve lojistikte yaygın olduğunu belirtiyor.