Суть решения: разделение спецификации и поиска
Rebalancer — это C++ библиотека с интерфейсом Python, предназначенная для решения NP-трудных задач распределения объектов по контейнерам (бингам) с учетом ограничений и целей. Ключевая архитектурная особенность — разделение слоя спецификации (как описать задачу) и слоя решения (как найти ответ). Пользователь задает модель через язык спецификаций, который компилируется в направленный ациклический граф выражений (DAG). Листья графа содержат значения утилизации, а узлы выше — агрегацию (SUM, MAX) и трансформации (SQUARE).
Два движка: MIP для малых задач, Local Search для масштабных
Система использует гибридный подход. Для задач среднего размера граф транслируется в смешанно-целочисленное программирование (MIP) с использованием бэкендов FICO Xpress, Gurobi или HiGHS. Однако для гиперскейловых задач, где размер модели достигает O(объекты × бинги), Meta применяет собственный параллельный алгоритм локального поиска. Он работает непосредственно с графом выражений, исследуя перемещения объектов с худшей сложностью O(объекты + бинги), что позволяет достигать миллионов оценок в секунду.
Производственные метрики Meta
Библиотека обрабатывает около 40 миллионов задач размещения ежедневно. Вот ключевые показатели производительности на реальных нагрузках:
| Метрика | Значение | Контекст |
|---|---|---|
| Объем обработки | ~40 млн задач/день | Более 30 уникальных формулировок задач |
| P99 время решения | 12 секунд | 265k объектов, 3.2k бингов |
| Среднее время (тяжелые) | 171 секунда | >1 млн объектов, >5k бингов (3.4k+ запусков) |
Сравнение с аналогами: OR-Tools и Timefold
В отличие от Google OR-Tools, который предлагает широкий спектр инструментов (CP-SAT, LP, MIP, маршрутизация), Rebalancer сфокусирован именно на задачах назначения (assignment). Его преимущество — единая спецификация, работающая как на локальном поиске, так и на MIP-решателях. В таблице ниже приведено сравнение ключевых характеристик:
| Характеристика | Meta Rebalancer | Google OR-Tools | Timefold Solver |
|---|---|---|---|
| Ядро | C++ | C++ | Java |
| Локальный поиск | Да, параллельный, на графе | Да (в маршрутизации) | Да (tabu, simulated annealing) |
| MIP бэкенды | Xpress, Gurobi, HiGHS | Обертки для коммерческих/OS | Не используется |
| Отладка | Rebalancer Explorer (UI) | Нет в open-source | Бенчмаркер (в Enterprise) |
Установка и доступность
Проект доступен в PyPI как пакет rebalancer (версия 1.0.4, статус Alpha). Поддерживаются Python 3.12+, Linux x86-64 и macOS 14+ ARM64. Для отладки моделей предусмотрен Rebalancer Explorer — Dockerized веб-интерфейс, показывающий, почему объект попал в конкретный бин, и как релаксация ограничений влияет на решение. Основные сценарии использования: размещение шардов и контейнеров, балансировка трафика между дата-центрами и операционные задачи (распределение тикетов, встреч).
Источник: MarkTechPost ↗