Как использовать Rebalancer от Meta для размещения и оптимизации задач

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

Мы устанавливаем rebalancer 1.0.4 и выводим версию Python и сведения об оборудовании, поскольку от них зависит каждое измерение времени. Привязка отклоняет имена перечислений и молча игнорирует неизвестные ключи спецификации, поэтому в ноутбуке используются целые числа из одной таблицы, а перед решением проверяется каждая спецификация. Затем контрольный тест решает модель с двумя задачами обоими решателями; каждый переносит одну задачу: локальный поиск за 0,8 мс, а HiGHS — за 0,9 мс. Ячейка также подтверждает, что эта сборка не принимает решатель XPRESS по умолчанию и пакет Gurobi.

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

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

Мы проверяем исправимое начальное состояние F и невозможное состояние I при каждой политике ограничений и с обоими решателями, пересчитывая каждый результат. HARD в локальном поиске оставляет оба состояния без изменений, сообщает OPTIMAL и solved=True, тогда как HiGHS исправляет F и выдаёт ошибку о невыполнимости для I. Из 24 решений в 14 случаях solved имел значение True, хотя память всё ещё превышала ёмкость. Значение 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 перемещений повторный подсчёт обнаруживает превышение CPU на 4 единицы, памяти на 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, но возвращают три разных распределения, поэтому следует сравнивать целевые значения, а не сами распределения.