Meta открыла исходный код Rebalancer: C++ библиотека для решения задач распределения

Компания Meta сделала общедоступной библиотеку Rebalancer, написанную на C++ и оснащенную удобным интерфейсом для Python. Инструмент предназначен для решения задач дискретного распределения объектов по контейнерам с учетом заданных ограничений и целевых критериев.

Инструмент с открытым исходным кодом распространяется под лицензией Apache 2.0. Пакет включает в себя всю необходимую документацию, готовые сборки для PyPI, а также специализированный отладочный веб-интерфейс Rebalancer Explorer, предназначенный для визуализации и анализа работы алгоритмов.

Какие проблемы решает Rebalancer

Задачи размещения и распределения ресурсов регулярно возникают на различных уровнях инфраструктуры компании Meta. Сюда относится распределение стоек по дата-центрам, закрепление серверов за конкретными сервисами, привязка задач к вычислительным узлам, а также балансировка пользовательского трафика между дата-центрами. Главными препятствиями при решении таких задач традиционно выступают масштабируемость и сложность формализации. Инженерам бывает непросто перевести внутренние корпоративные политики в строгие математические формулы, а многие подобные задачи относятся к классу NP-трудных и оказываются слишком масштабными для стандартных коммерческих солверов.

Подход Rebalancer строится на разделении процесса описания проблемы и метода ее непосредственного решения. Такая архитектура подробно описана в исследовательском труде по оптимизации распределения ресурсов в гипермасштабируемых дата-центрах.

Как работает спецификация в Rebalancer

Язык описания спецификаций в библиотеке состоит из трех ключевых уровней. Первый уровень включает моделирующие конструкции: числовые измерения вроде процессора или памяти, разделы для группировки объектов, области видимости для контейнеров и параметры утилизации. Второй уровень представляет собой API выражений, позволяющее агрегировать показатели с помощью операторов суммирования или поиска максимума, а также применять различные трансформации. Третий уровень содержит API спецификаций с набором готовых целей и ограничений.

В типовых примерах задачи задачи моделируются как объекты, серверы выступают в роли контейнеров, а стойки образуют область видимости. Специальные параметры ограничивают вычислительную мощность и хранилище на каждом сервере, следят за тем, чтобы на одной стойке не скапливалось слишком много однотипных заданий, и равномерно распределяют нагрузку.

Один граф выражений и два типа солверов

Полученная спецификация компилируется в направленный ациклический граф выражений. Листовые узлы этого графа содержат значения утилизации, а выше располагаются узлы агрегации и преобразования. Пользователь должен предоставить начальное распределение объектов и условие остановки поиска. Ограничения, которые исходное назначение нарушает с самого начала, превращаются в приоритетные цели оптимизации.

Оптимальный солвер

На первом этапе граф может быть переведен в задачу смешанно-целочисленного программирования для таких решателей, как FICO Xpress, Gurobi или открытый HiGHS. Модель оптимизируется за счет агрегации переменных и разрушения симметрии. Тем не менее, для крупнейших проектов Meta размер моделей остается избыточным для классических MIP-солверов.

Локальный поиск

Альтернативный солвер работает напрямую с графом выражений, исследуя варианты перемещения объектов между контейнерами. Он перебирает кандидатов, не нарушающих действующие ограничения, а оценка вариантов распараллеливается для достижения высокой скорости обработки.

Производительность в производственной среде Meta

В инфраструктуре Meta данная библиотека ежедневно обрабатывает порядка 40 миллионов задач распределения, задействуя более тридцати уникальных конфигураций. Показатель P99 времени решения для систем из 265 тысяч объектов и 3,2 тысячи контейнеров составляет около 12 секунд. Для сверхкрупных задач, включающих свыше миллиона объектов и пять тысяч контейнеров, среднее время выполнения достигает 171 секунды.

Сценарии применения инструмента

Библиотека эффективно справляется с размещением контейнеров, задач и цифровых шардов на кластерах, распределяя нагрузку с учетом ограничений памяти и процессорного времени при одновременном разнесении реплик по разным стойкам. Аналогичным образом инструмент задействуется для балансировки сетевого трафика и рабочих процессов между различными регионами.

Помимо чистой инфраструктуры, инструмент находит применение в операционных задачах: при распределении обращений в службу поддержки между инженерами, привязке переговорных комнат к встречам или закреплении рабочих мест за сотрудниками на основе заданных правил вместимости.

Инструмент отладки Rebalancer Explorer

Поскольку разработчики тратят значительную часть времени на анализ поведения алгоритмов оптимизации, в состав проекта вошел специализированный графический интерфейс Rebalancer Explorer. Приложение упаковано в виде Docker-образа и наглядно демонстрирует действующие ограничения, последствия ослабления условий и причины, по которым конкретный объект занял определенный контейнер.

Сравнение с аналогами с открытым исходным кодом

По сравнению с другими популярными инструментами, такими как Google OR-Tools или Timefold Solver, ориентированными на более широкий спектр задач планирования и маршрутизации, библиотека Rebalancer сосредоточена на универсальных задачах распределения объектов по контейнерам. Ее главным преимуществом является единая спецификация, которая может исполняться как через механизмы локального поиска, так и через MIP-решатели.

Главные выводы

Инструмент позволяет моделировать практически любые задачи распределения через объекты, контейнеры, ограничения и целевые функции. Спецификации компилируются в граф выражений и обрабатываются локальным поиском либо MIP-солверами вроде Gurobi и HiGHS. Открытый код распространяется под лицензией Apache 2.0 с поддержкой Python и C++, что позволяет легко развернуть библиотеку из репозитория PyPI.