Meta открыла исходный код Rebalancer — библиотеки на C++ с интерфейсом на Python для решения задач размещения (assignment problems). Солвер определяет, какие объекты попадают в какие контейнеры, с учётом ограничений и целей оптимизации. Согласно публикации Engineering at Meta, библиотека используется внутри компании более девяти лет. Код выложен под лицензией Apache 2.0 вместе с документацией, пакетом на PyPI и отладочным веб-интерфейсом Rebalancer Explorer.
Установить солвер можно одной командой:
pip install rebalancer
Команда ставит версию 1.0.4 для Python 3.12+, с готовыми wheel-пакетами для Linux x86-64 и macOS 14+ ARM64. Также доступны пакеты .deb, .rpm и Homebrew. При этом на PyPI проект пока помечен как Alpha.
Зачем понадобился отдельный солвер
Задачи размещения встречаются по всему стеку Meta: стойки распределяются по дата-центрам, серверы — по сервисам, задачи — по серверам, пользовательский трафик — по дата-центрам. В компании называют две основные проблемы: удобство использования и масштабируемость. Инженерам сложно превращать политики в точные формулы, а многие задачи относятся к классу NP-сложных и слишком велики для коммерческих солверов.
Rebalancer решает это, разделяя то, как задача описывается, и то, как она решается. Архитектура подробно описана в статье OSDI 2024 «Optimizing Resource Allocation in Hyperscale Datacenters».
Три слоя описания задачи
Язык спецификаций состоит из трёх уровней:
- Конструкции моделирования: измерения (атрибуты вроде CPU или объёма хранилища), партиции (группы объектов), области (scopes, группы контейнеров) и утилизация.
- Expression API: агрегация утилизации через SUM или MAX, преобразование операциями вроде SQUARE.
- Spec API: десятки предопределённых целей и ограничений, перечисленных в документации.
В примере Meta задачи моделируются как объекты, серверы — как контейнеры, а стойки — как область. CapacitySpec ограничивает CPU и хранилище на сервер, GroupCountSpec удерживает один тип задачи на стойку, а BalanceSpec балансирует утилизацию каждого сервера по обоим измерениям.
Один граф выражений — два солвера
Rebalancer компилирует спецификацию в направленный ациклический граф выражений. Листовые узлы хранят значения утилизации, а узлы агрегации и преобразования располагаются выше. Пользователь задаёт начальное размещение и условие остановки. Ограничения, которые начальное размещение уже нарушает, становятся целями высокого приоритета.
Оптимальный солвер переводит граф в задачу смешанного целочисленного программирования (MIP) для FICO Xpress, Gurobi или HiGHS. Агрегация переменных и устранение симметрии уменьшают модели. Худший размер модели всё равно остаётся O(объекты × контейнеры). Крупнейшие задачи Meta слишком велики для любого MIP-солвера.
Локальный поиск работает напрямую с графом выражений. Он исследует перемещения объектов в другие контейнеры с худшей окрестностью O(объекты + контейнеры). Затем применяется лучший кандидат, не нарушающий ограничений. Оценка распараллелена и достигает миллионов вычислений в секунду, а пространство поиска сокращается.
Meta использует локальный поиск почти для всех крупных задач, а MIP — для малых и средних, часто сначала прототипируя на MIP.
Цифры из продакшена
- Около 40 млн задач размещения решается в день, более 30 уникальных формулировок.
- P99 времени решения — 12 секунд на 265 тыс. объектов и 3,2 тыс. контейнеров.
- Задачи свыше 1 млн объектов и 5 тыс. контейнеров решаются в среднем за 171 секунду, по более чем 3,4 тыс. запусков.
Где применять
- Размещение шардов, задач или контейнеров на кластере: распределение работы по серверам с учётом лимитов CPU и памяти и разнесением реплик по стойкам. В Meta этот шаблон используют Shard Manager и RAS.
- Балансировка трафика и нагрузки между регионами: маршрутизация пользовательского трафика или задач по дата-центрам с компромиссом между задержкой и нагрузкой. Taiji делает это для edge-трафика, а Meta балансирует обучение ML-моделей по приоритету.
- Операционные задачи вне инфраструктуры: сопоставление тикетов поддержки инженерам, встреч — переговорным, рабочих мест — сотрудникам с учётом правил по вместимости. Все три сценария в Meta уже применяли.
Отладка через Rebalancer Explorer
Моделисты Meta тратили большую часть времени на отладку поведения солвера. Rebalancer Explorer — это веб-интерфейс в Docker, созданный именно для этого. Он показывает связывающие ограничения, эффекты ослабления и объясняет, почему объект попал в тот или иной контейнер.
Чем Rebalancer отличается от альтернатив
Ближайшие открытые аналоги — Google OR-Tools и Timefold Solver (Community). Все три распространяются под Apache 2.0, но OR-Tools написан на C++, а Timefold — на Java. Rebalancer даёт C++ и Python API; OR-Tools — C++, Python, Java и C#; Timefold — Java и Kotlin.
OR-Tools покрывает больше классов задач: CP-SAT, обёртки LP и MIP, маршрутизацию, упаковку, размещение. Timefold нацелен на планирование в JVM: маршрутизацию, составление расписаний, назначение задач. Преимущество Rebalancer — единая спецификация размещения, работающая и на локальном поиске, и на MIP-солвере. Локальный поиск здесь параллельный и работает на графе выражений; MIP-бэкенды — FICO Xpress, Gurobi и открытый HiGHS. Отладочный UI Rebalancer Explorer есть только у Meta; у OR-Tools в README он не указан, у Timefold доступен бенчмаркер и анализ оценок в коммерческих редакциях.
Если вы уже запускаете агентные или инфраструктурные нагрузки в кластере, полезно сравнить подход Rebalancer с тем, как TauGrid от Microsoft раскладывает ИИ-нагрузки по Kubernetes, а при отладке распределённых пайплайнов пригодится Shepherd — Python-рантайм для форка и отката агентных запусков.
Частые вопросы
Что именно открыла Meta?
Библиотеку Rebalancer на C++ с Python-интерфейсом, документацию, пакет на PyPI и отладочный веб-интерфейс Rebalancer Explorer. Лицензия — Apache 2.0.
Как установить Rebalancer?
Командой pip install rebalancer. Она ставит версию 1.0.4 для Python 3.12+ с готовыми wheel-пакетами для Linux x86-64 и macOS 14+ ARM64. Есть также пакеты .deb, .rpm и Homebrew.
Проект стабилен для продакшена?
На PyPI он помечен как Alpha. Использовать его в продакшене или нет — решение команды; сама Meta гоняет через него около 40 млн задач в день.
Какие задачи Rebalancer решает?
Любые задачи размещения: объекты нужно распределить по контейнерам с учётом ограничений и целей. Примеры — серверы по сервисам, задачи по серверам, трафик по дата-центрам, тикеты по инженерам.
Чем локальный поиск отличается от MIP-солвера?
Локальный поиск работает напрямую с графом выражений и подходит для крупных задач: окрестность O(объекты + контейнеры). MIP-солвер переводит граф в задачу смешанного целочисленного программирования и применяется для малых и средних задач, где размер модели остаётся управляемым.
Какие MIP-бэкенды поддерживаются?
FICO Xpress, Gurobi и открытый HiGHS. Для крупнейших задач Meta любой MIP-солвер оказывается слишком медленным, поэтому там используется локальный поиск.
Насколько быстро решаются задачи?
P99 времени решения — 12 секунд на 265 тыс. объектов и 3,2 тыс. контейнеров. Задачи свыше 1 млн объектов и 5 тыс. контейнеров решаются в среднем за 171 секунду.
Чем Rebalancer отличается от Google OR-Tools?
OR-Tools покрывает больше классов задач — CP-SAT, LP, MIP, маршрутизацию, упаковку. Rebalancer сфокусирован на размещении и даёт единую спецификацию, которая работает и на локальном поиске, и на MIP.
Есть ли графический интерфейс для отладки?
Да, Rebalancer Explorer — веб-интерфейс в Docker. Он показывает связывающие ограничения, эффекты ослабления и объясняет, почему объект оказался в конкретном контейнере.
Источник: marktechpost.com