Meta відкрила код Rebalancer — бібліотеки для задач призначення

Meta відкриває код Rebalancer

Meta опублікувала у відкритому доступі Rebalancer під ліцензією Apache 2.0. Бібліотека розв'язує задачі призначення: для множини об'єктів і бінів вона знаходить розподіл, який задовольняє обмеження та оптимізує задані цілі. За словами компанії, розв'язувач використовується всередині Meta понад дев'ять років.

Разом із кодом опубліковано репозиторій facebook/rebalancer на GitHub, документацію, Python-пакет на PyPI та Rebalancer Explorer — вебінтерфейс у Docker для налагодження.

Одна бібліотека для багатьох задач

Те саме формулювання застосовується на кількох рівнях інфраструктури Meta: стійки розміщують у дата-центрах, розподіляючи їх між доменами електричних збоїв у межах обмежень на живлення й охолодження; сервери призначають сервісам для відмовостійкості; а трафік користувачів — до розподілених дата-центрів, балансуючи затримку й навантаження.

Rebalancer долає дві перешкоди, які зазвичай блокують багаторазові системи оптимізації: зручність використання та масштабованість. Замість перекладати правила в математичні формули вручну, інженери описують задачу мовою об'єктів, бінів, обмежень і цілей, а вона перетворюється на орієнтований ациклічний граф — expression graph. Готові специфікації, як-от CapacitySpec, GroupCountSpec і BalanceSpec, перетворюють типові цілі на багаторазові рецепти.

Оптимальний розв'язувач і локальний пошук

Оптимальний розв'язувач перетворює задачу на модель змішаного цілочисельного програмування для FICO Xpress, Gurobi або HiGHS, застосовуючи агрегацію змінних і руйнування симетрії. У найгіршому разі розмір моделі зростає як добуток кількості об'єктів і бінів, тож найбільші задачі не під силу жодному MIP-розв'язувачу.

Розв'язувач локального пошуку працює безпосередньо з графом, досліджуючи переміщення об'єктів між бінами. Його окіл зростає лише із сумою об'єктів і бінів, а паралелізація дає мільйони обчислень за секунду, тож у Meta майже всі великомасштабні задачі розв'язують локальним пошуком.

Масштаб у Meta і поза нею

За даними Meta, Rebalancer щодня розв'язує близько 40 мільйонів задач призначення за понад 30 формулюваннями. P99 часу розв'язання — 12 секунд для задачі з 265 тисячами об'єктів і 3,2 тисячами бінів; для задач понад мільйон об'єктів і 5 тисяч бінів середній час становить 171 секунду.

Поза інфраструктурою бібліотеку застосовували для призначення зустрічей на кімнати, розподілу звернень підтримки між інженерами та оптимізації розміщення робочих столів. Meta зазначає, що такі задачі поширені в охороні здоров'я, енергетиці, логістиці та освіті.