Як використовувати Rebalancer від Meta для розміщення та оптимізації завдань

У цьому посібнику ми реалізуємо Rebalancer — розв’язувач задач призначення від Meta — із ядром на C++ і прив’язкою до Python. Ми опишемо об’єкти, контейнери, виміри, області та секції, додамо обмеження й цілі, а потім оберемо локальний пошук або точний змішано-цілочисловий розв’язувач HiGHS. Ми побудуємо невеликий дата-центр, виведемо з експлуатації завантажений хост і порівняємо два розв’язувачі на тестових моделях, взаємно виключних хостах, синтетичних кластерах і 60 опублікованих екземплярах OR-Library. Кожен план ми оцінюємо, повторно підраховуючи повернуте призначення, а не покладаючись на прапорці розв’язувача. У цій збірці в 24 розв’язаннях прапорець solved мав значення True у 14 розв’язаннях, у яких пам’ять усе ще перевищувала місткість. HARD у режимі локального пошуку повертав початковий стан із порушенням, не генеруючи помилки; ключі специфікації з друкарськими помилками мовчки ігнорувалися, а назви enum відхилялися. Часові показники отримано на Apple M4 із wheel-пакетом для macOS; Linux wheel-пакет у Colab може показувати інший час.

Ми встановлюємо rebalancer 1.0.4 і виводимо версію Python та апаратне забезпечення, оскільки кожен часовий показник залежить від них. Прив’язка відхиляє назви enum і мовчки ігнорує невідомі ключі специфікації, тому notebook передає цілі числа з однієї таблиці та перевіряє кожну специфікацію перед розв’язанням. Потім gate розв’язує модель із двома задачами обома розв’язувачами; кожен переміщує одну задачу — за 0,8 мс локальним пошуком і за 0,9 мс за допомогою HiGHS. Комірка також підтверджує, що ця збірка відмовляється від розв’язувача XPRESS за замовчуванням і пакета Gurobi.

Ми розв’язуємо приклад із README: чотири задачі по 10 ГБ на двох хостах по 20 ГБ, причому три задачі розміщено на одному хості, і повторно підраховуємо результат замість того, щоб довіряти розв’язувачу. Локальний пошук переміщує одну задачу за 0,3 мс, а повторний підрахунок зменшує перевищення місткості з 10 ГБ до 0. Власний brokenCount розв’язувача також зменшується з 1 до 0, а endReason має значення OPTIMAL. Контрольний приклад демонструє важливість прапорця: за solveTime=0 розв’язувач нічого не переміщує, залишає перевищення місткості на 10 ГБ і повідомляє solved=True.

Ми будуємо вісім хостів у чотирьох стійках, чотири завдання по чотири задачі в кожному та починаємо з використанням 200% CPU на host0 і 12 дублікатами в стійках. Ми додаємо обмеження місткості CPU і пам’яті, правило «не більше однієї задачі кожного завдання на стійку» та ціль балансування CPU. Розв’язувач переміщує 13 задач, залишаючи по дві на кожному хості без порушень; медіанний час розв’язання для трьох нових побудов становить 2,5 мс. Без правила стійки повторний підрахунок виявляє 5 дублікатів у стійках, а відносне обмеження для цього правила також завершується з 5 дублікати, тобто тут воно нічого не обмежує.

Ми тестуємо початковий стан, який можна виправити (F), і неможливий початковий стан (I) за кожної політики обмежень і з обома розв’язувачами, повторно підраховуючи кожен результат. HARD із локальним пошуком повертає обидва стани без змін, із OPTIMAL і solved=True, тоді як HiGHS виправляє F і генерує помилку infeasible для I. У 24 розв’язаннях solved мав значення True у 14 випадках, де пам’ять усе ще перевищувала місткість. Значення brokenVal розв’язувача в усіх 15 зразках дорівнює загальному перевищенню, поділеному на середню місткість хостів. Слід читати brokenCount або виконувати повторний підрахунок, а не довіряти OPTIMAL.

Нижча цільова секція завжди має перевагу, а ваги дають змогу обмінюватися пріоритетами лише всередині однієї секції. Коли обидві цілі перебувають у секції 0, вага 1 для спорідненості програє вазі 1000 для переміщення, а після зміни ваг t0 переміщується. Якщо спорідненість розміщено в секції 0, а переміщення — у секції 1, t0 усе одно переміщується. Ціль виправлення в пізнішій секції, ніж ціль переміщення, залишає перевищення 10 ГБ без переміщення, тоді як у зворотному порядку воно усувається одним переміщенням. Значення цілі виправлення дорівнює 10000 плюс 100, помножене на brokenVal; це перевірено для двох початкових станів.

Ми виводимо з експлуатації host1 за допомогою обмеження ToFree, залишаючи host0 самотнім у rack0 із використанням 16 із 16 одиниць CPU. Без обмеження локальний пошук спорожнює host1 за 13 переміщень без порушень, і три нові побудови дають однаковий результат. Обмеження stopAfterMoves створює частковий план, а не помилку: після 12 переміщень одна задача все ще залишається на host1, а після 6 переміщень повторний підрахунок виявляє перевищення на 4 CPU і 16 ГБ пам’яті та 6 дублікатів у стійках, хоча solved має значення True. Ключ із друкарською помилкою stopAfterMove мовчки ігнорується, і розв’язання виконує всі 13 переміщень.

Ми порівнюємо HiGHS із локальним пошуком для балансування, оцінюючи його за повторно підрахованим розкидом CPU, оскільки цілі різних формул непорівнювані. За формулою LINEAR обидва розв’язувачі досягають нульового розкиду, але локальний пошук переміщує 13 задач за медіанні 1,8 мс, тоді як HiGHS переміщує 16 задач за 7,8 мс. IDEAL забезпечує балансування під час локального пошуку, але генерує помилку HiGHS. Для трьох взаємно виключних хостів локальний пошук зупиняється, коли всі три хости використовуються, а кожна конфліктна пара все ще порушує обмеження, оскільки жодне окреме переміщення не зменшує brokenVal. HiGHS усуває конфлікти за 5,9 мс.

Ми запускаємо синтетичні кластери з обмеженням часу, кожен в окремому новому процесі. Кластер із 1000 об’єктів і 100 контейнерів виконувався за 1,22, 1,27 і 1,35 с у трьох процесах, щоразу повертав однакове призначення та усунув усі 13 перевантажених контейнерів. Кластер 1000 × 1000 виконувався 3,55 с. Для 10 000 об’єктів і 100 контейнерів досягається обмеження 25 с із HIT_TIME_LIMIT, тому endReason і повторний підрахунок дають змогу відрізнити завершені плани від часткових. Три запуски HiGHS для дата-центру досягають цільового значення 0, але повертають три різні призначення, тому ми порівнюємо цілі, а не призначення.

Ми порівнюємо 60 екземплярів узагальненої задачі призначення з опублікованими оптимальними значеннями OR-Library, завантажуючи та перевіряючи всі вхідні дані. Для кожного екземпляра оцінюємо загальний прибуток і переконуємося, що жоден агент не перевищує місткість, а кожна задача призначена рівно одному агенту. Точний розв’язувач HiGHS порівнюється з локальним пошуком за досягнутим прибутком, часом і відповідністю обмеженням.