Meta təyinat məsələləri üçün Rebalancer kitabxanasını açıq mənbə etdi

Meta Rebalancer-ı açıq mənbə kimi yayımladı

Meta Rebalancer-ı Apache 2.0 lisenziyası ilə açıq mənbə kimi yayımlayıb. Kitabxana təyinat məsələlərini həll edir: verilmiş obyektlər və binlər üçün məhdudiyyətlərə uyğun, müəyyən məqsədləri optimallaşdıran yerləşdirməni tapır. Şirkətin məlumatına görə, həlledici doqquz ildən artıqdır Meta-nın infrastrukturunda istifadə olunur.

Buraxılışla birlikdə facebook/rebalancer GitHub repozitoriyası, sənədləşmə, PyPI paketi və Rebalancer Explorer interfeysi təqdim olunub.

Bir kitabxana, çoxlu təyinat məsələsi

Eyni formulasiya Meta infrastrukturunun bir neçə qatında istifadə olunur: server rəfləri enerji və soyutma məhdudiyyətləri daxilində elektrik nasazlıq domenlərinə bərabər paylanmaq üçün verilənlər mərkəzlərində yerləşdirilir; serverlər nasazlığa davamlılıq üçün xidmətlərə təyin edilir; istifadəçi trafiki isə gecikmə və yükü balanslaşdırmaq üçün paylanmış mərkəzlərə yönləndirilir.

Rebalancer təkrar istifadə oluna bilən optimallaşdırma sistemlərinin iki maneəsini aradan qaldırır: istifadə rahatlığı və miqyaslana bilmə. Siyasətləri əl ilə formulalara çevirmək əvəzinə, mühəndislər məsələni obyektlər, binlər, məhdudiyyətlər və məqsədlərlə təsvir edir; Rebalancer bunu istiqamətlənmiş asiklik qrafa (expression graph) çevirir. CapacitySpec, GroupCountSpec və BalanceSpec kimi spesifikasiyalar geniş yayılmış məqsədləri təkrar istifadə oluna bilən reseptlərə çevirir.

Optimal həlledici və lokal axtarış

Optimal həlledici qrafı FICO Xpress, Gurobi və ya HiGHS üçün qarışıq tam ədədli proqramlaşdırma modelinə çevirir və modeli dəyişənlərin birləşdirilməsi və simmetriyanın pozulması ilə kiçildir. Ən pis halda modelin ölçüsü obyektlərin və binlərin sayının hasilinə bərabərdir, ona görə ən böyük məsələlər heç bir MIP həlledicisinə sığmır.

Lokal axtarış həlledicisi birbaşa qraf üzərində işləyir və obyektlərin binlər arasında köçürülməsini öyrənir. Qonşuluq yalnız obyekt və bin saylarının cəmi ilə böyüyür, paralelləşdirmə saniyədə milyonlarla qiymətləndirməyə imkan verir; buna görə Meta-da böyük miqyaslı məsələlərin demək olar hamısı lokal axtarışla həll olunur.

Meta-da miqyas və ondan kənarda

Meta-nın məlumatına görə, Rebalancer gündə təxminən 40 milyon təyinat məsələsini 30-dan artıq formulasiya ilə həll edir. 265 min obyekt və 3 200 bindən ibarət məsələdə P99 həll vaxtı 12 saniyədir; 1 milyondan çox obyekt və 5 000 bin olan məsələlərdə orta həll vaxtı 171 saniyədir.

Kitabxana infrastrukturdan kənar da görüşlərin otaqlara təyin edilməsi, dəstək müraciətlərinin mühəndislər arasında bölünməsi üçün istifadə olunub.