Meta открыла Rebalancer: C++-решатель задач распределения, обрабатывающий 40 млн задач в день

Meta открыла исходный код Rebalancer — C++-библиотеки с Python-интерфейсом для решения задач назначения (assignment problems). Инструмент определяет, какие объекты попадают в какие контейнеры с учётом ограничений и целей. По данным инженерного блога Meta, Rebalancer уже более 9 лет используется для распределения ресурсов внутри компании. Релиз опубликован под лицензией Apache 2.0, включает документацию, PyPI-пакет и отладочный веб-интерфейс Rebalancer Explorer.

Rebalancer решает задачи, которые возникают по всему стеку Meta: размещение стоек в дата-центрах, серверов для сервисов, задач на серверах и пользовательского трафика. Два главных препятствия — сложность формализации политик и NP-трудность многих задач, слишком масштабных для коммерческих решателей. Rebalancer разделяет описание проблемы и способ её решения: спецификация компилируется в направленный ациклический граф выражений, а затем обрабатывается одним из двух солверов — оптимальным (MIP через FICO Xpress, Gurobi или HiGHS) или локальным поиском, который работает напрямую с графом и достигает миллионов оценок в секунду.

В продакшене Meta Rebalancer решает около 40 млн задач в день по 30+ уникальным формулировкам. P99 время решения — 12 секунд для 265 тыс. объектов и 3,2 тыс. контейнеров; задачи с более чем 1 млн объектов и 5 тыс. контейнеров в среднем решаются за 171 секунду. Инструмент подходит для размещения шардов, задач и контейнеров в кластерах, балансировки трафика между регионами и операционных задач вроде назначения тикетов инженерам. Rebalancer Explorer помогает отлаживать поведение решателя, показывая ограничения, эффекты релаксации и причины попадания объекта в конкретный контейнер.