Meta Rebalancer: Открытый решатель задач размещения для масштаба Meta

В мире распределенных систем и облачных вычислений существует одна фундаментальная проблема, с которой сталкиваются инженеры любого масштаба: как оптимально распределить ограниченные ресурсы среди бесконечного множества задач. Это не просто вопрос «где запустить контейнер». Это сложнейшая математическая головоломка, включающая сотни ограничений, приоритетов и динамически меняющихся условий. Компания Meta, чья инфраструктура является одной из крупнейших в мире, десятилетиями решала эту задачу внутренними инструментами. Теперь же они сделали шаг, который может изменить ландшафт open-source решений для DevOps и SRE-инженеров: они открыли исходный код своей библиотеки Rebalancer.

Rebalancer — это не просто еще одна библиотека для оптимизации. Это специализированный решатель задач назначения (assignment solver), написанный на C++ с удобным интерфейсом на Python. Он предназначен для распределения объектов (например, серверов, задач, данных) по контейнерам (бинам), таким как стойки, дата-центры или узлы кластера, с учетом строгих ограничений и целей. За последние 9 лет эта система обрабатывала распределение ресурсов по всей инфраструктуре Meta, и теперь, под лицензией Apache 2.0, она доступна каждому. В комплекте идет документация, пакет PyPI и уникальный инструмент отладки Rebalancer Explorer.

В этой статье мы подробно разберем, как работает Rebalancer, почему его архитектура выделяется на фоне конкурентов, как он справляется с NP-трудными задачами, которые не под силу коммерческим решателям, и как вы можете начать использовать его в своих проектах, даже находясь в России.

01Почему Meta решила открыть Rebalancer?

Чтобы понять ценность Rebalancer, нужно осознать масштаб проблем, которые он решает. В инфраструктуре Meta задачи назначения встречаются повсюду: от размещения физических серверных стоек в дата-центрах до распределения пользовательского трафика между регионами. Классические коммерческие решатели (MIP-солверы) часто не справляются с такими объемами из-за вычислительной сложности. Многие из этих задач являются NP-трудными, что означает экспоненциальный рост времени решения при увеличении числа переменных.

Meta выделила два главных барьера, которые мешали инженерам эффективно решать эти задачи ранее: удобство использования и масштабируемость. Инженерам было сложно превращать бизнес-политики (например, «не размещать два реплики одного сервиса в одной стойке») в точные математические формулы. Кроме того, многие задачи были слишком велики для стандартных коммерческих пакетов.

Ответ Meta — разделить способ описания проблемы (спецификацию) и способ ее решения (алгоритм). Эта архитектура подробно описана в их научной публикации «Optimizing Resource Allocation in Hyperscale Datacenters», представленной на конференции OSDI 2024. Открытие кода позволяет сообществу проверить, улучшить и адаптировать этот подход под свои нужды, экономя годы разработки собственных оптимизационных движков.

02Архитектура Rebalancer: Три слоя спецификации

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

1. Конструкции моделирования (Modeling Constructs)

Это базовые строительные блоки. Здесь определяются:

• Измерения (Dimensions): Атрибуты, которые нужно оптимизировать, например, использование CPU, памяти или хранилища.
• Разделы (Partitions): Группы объектов, которые нужно распределить (например, все задачи определенного микросервиса).
• Области (Scopes): Группы контейнеров (бинов), таких как стойки или дата-центры.
• Утилизация (Utilization): Текущее состояние ресурсов.

2. Expression API (API выражений)

Этот слой позволяет агрегировать и трансформировать данные. Вы можете суммировать использование ресурсов с помощью SUM, находить максимальное значение с помощью MAX или применять математические операции, такие как возведение в квадрат SQUARE, для создания нелинейных целей оптимизации. Это дает гибкость в формулировании сложных ограничений.

3. Spec API (API спецификаций)

Высший уровень абстракции, содержащий десятки предопределенных целей и ограничений. Например, Meta использует CapacitySpec для ограничения CPU и памяти на сервере, GroupCountSpec для обеспечения того, чтобы в одной стойке находился только один тип задачи (для изоляции сбоев), и BalanceSpec для равномерного распределения нагрузки по всем измерениям на каждом сервере.

03Один граф выражений — два решателя

После того как спецификация описана, Rebalancer компилирует ее в направленный ациклический граф выражений (DAG). Листья этого графа содержат значения утилизации, а узлы выше — операции агрегации и трансформации. Пользователь предоставляет начальное назначение и условие остановки. Если начальное назначение нарушает некоторые ограничения, эти нарушения становятся целями с высоким приоритетом для минимизации.

Главная сила Rebalancer — в наличии двух различных решателей, которые работают с одним и тем же графом:

1. Оптимальный решатель (MIP Solver)

Этот решатель преобразует граф в задачу смешанного целочисленного программирования (Mixed Integer Programming, MIP). Он использует бэкенды, такие как FICO Xpress, Gurobi или открытый HiGHS. Для уменьшения размера модели применяются агрегация переменных и устранение симметрии. Однако, даже с оптимизациями, худший случай размера модели остается O(объекты × бины). Для самых больших задач Meta (миллионы объектов) этот метод слишком медленен.

2. Решатель локального поиска (Local Search)

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

Meta рекомендует гибридный подход: использовать MIP для прототипирования небольших и средних задач, чтобы найти оптимальное решение, а затем переключаться на локальный поиск для масштабирования на миллионы объектов.

04Производственные показатели Meta

Цифры из инженерного блога Meta впечатляют и демонстрируют зрелость системы. Rebalancer не является экспериментальным прототипом; это критически важная часть инфраструктуры, работающая в продакшене.

• Масштаб: Около 40 миллионов задач назначения решается ежедневно. Это охватывает более 30 уникальных формулировок задач.
• Скорость (P99): Для задач с 265 000 объектов и 3 200 бинами 99-й процентиль времени решения составляет всего 12 секунд.
• Большие задачи: Для задач, превышающих 1 миллион объектов и 5 000 бинов, среднее время решения составляет 171 секунду, что является выдающимся результатом для таких объемов данных.

Эти цифры подчеркивают важность выбора правильного алгоритма. Если бы Meta использовала только MIP-солверы, такие задачи либо не решались бы вовсе, либо занимали бы часы, что неприемлемо для динамической инфраструктуры.

05Практические кейсы использования

Rebalancer не ограничивается только распределением серверов. Его универсальная модель «объект-бин-ограничение» применима к широкому спектру задач.

1. Размещение шардов и контейнеров

Это классический случай использования. При распределении шардов данных или контейнеров Kubernetes по кластеру необходимо соблюдать ограничения по CPU и памяти, а также распределять реплики по разным стойкам для отказоустойчивости. Системы Meta, такие как Shard Manager и RAS, используют именно этот паттерн.

2. Балансировка трафика и рабочих нагрузок

Rebalancer помогает маршрутизировать пользовательский трафик или задачи между дата-центрами, находя баланс между задержкой (latency) и нагрузкой. Например, система Taiji использует его для управления трафиком на периферийных узлах (edge), а также для балансировки задач машинного обучения в зависимости от их приоритета.

3. Операционные задачи вне инфраструктуры

Интересно, что Meta применяет Rebalancer даже для нетехнических задач. Например, распределение тикетов поддержки между инженерами, назначение встреч в переговорные комнаты или распределение рабочих мест среди сотрудников — все это задачи назначения, которые можно решить с помощью той же библиотеки, если правильно задать ограничения (например, «у инженера А есть навыки для тикета Б» или «в комнате В есть проектор»).

06Отладка с Rebalancer Explorer

Одной из самых больших проблем при работе с оптимизационными решателями является «черный ящик». Инженеры часто не понимают, почему решатель принял то или иное решение, особенно если оно кажется неоптимальным. Для решения этой проблемы Meta разработала Rebalancer Explorer — веб-интерфейс, упакованный в Docker.

Explorer позволяет визуализировать:

• Какие ограничения являются связывающими (binding constraints), то есть именно они ограничивают решение.
• Эффекты релаксации ограничений (что произойдет, если ослабить правило).
• Почему конкретный объект оказался в конкретном бине.

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

07Сравнение с альтернативами: OR-Tools и Timefold

На рынке есть несколько популярных open-source решений. Давайте сравним Rebalancer с Google OR-Tools и Timefold Solver.

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

08Что это значит на практике

Открытие Rebalancer — это значимое событие для сообщества open-source и инженерии инфраструктуры. Вот как это можно применить на практике, особенно для команд из России:

1. Локальный запуск и независимость: Поскольку Rebalancer поддерживает open-source бэкенд HiGHS, вы можете запускать его полностью автономно, без необходимости покупать лицензии на коммерческие MIP-решатели, такие как Gurobi или FICO Xpress. Это критически важно в условиях текущих ограничений на доступ к зарубежным сервисам.
2. Упрощение архитектуры: Вместо того чтобы писать кастомные эвристики для распределения ресурсов, вы можете использовать готовую, проверенную на масштабах Meta систему. Это экономит месяцы разработки и отладки.
3. Гибридный подход: Вы можете использовать MIP (HiGHS) для тестирования и валидации ваших моделей на малых данных, а затем переключаться на локальный поиск для работы с реальными объемами данных, получая баланс между скоростью и качеством решения.
4. Отладка: Наличие Rebalancer Explorer позволяет не гадать, почему решение получилось таким, а видеть причины, что ускоряет итерации по улучшению политик распределения.

Для начала работы достаточно выполнить простую команду:

pip install rebalancer

Это установит версию 1.0.4 для Python 3.12+, с предварительно собранными wheel-пакетами для Linux x86-64 и macOS 14+ ARM64. Документация и примеры доступны на GitHub и в официальных материалах Meta. Это отличный шанс взять в руки инструмент, который держит в порядке одну из самых сложных инфраструктур в мире, и применить его к своим задачам.

Источник: MarkTechPost ↗