Открытый исходный код Rebalancer: универсальная высокопроизводительная библиотека для решения задач распределения21.09.2026 16:00

Мы открываем исходный код Rebalancer — средства решения задач распределения, которое уже более девяти лет используется для решения задач выделения ресурсов в компании Meta.
Rebalancer разделяет несколько связанных задач: как задать задачу распределения, как эффективно хранить ее в памяти, как ее решить и как ее отлаживать. Такое разделение ответственности имеет решающее значение для удобства использования, масштабируемости и расширяемости Rebalancer.
Более подробное техническое описание см. в сопутствующей статье «Оптимизация распределения ресурсов в гипермасштабируемых дата-центрах: масштабируемость, удобство использования и опыт» («Optimizing Resource Allocation in Hyperscale Datacenters: Scalability, Usability, and Experiences»), опубликованной на конференции OSDI»24.

Учитывая набор объектов и набор контейнеров, как распределить объекты по контейнерам таким образом, чтобы оптимизировать определенные цели и одновременно соблюсти заданные ограничения?

Этот вопрос возникает на всех уровнях инфраструктурного стека Meta, в том числе в следующих областях:

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

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

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

Спецификация задач распределения

Язык спецификации Rebalancer использует трехэтапный подход для постепенного повышения уровня абстракции в целях удобства использования.

Сначала он представляет основные концепции моделирования, такие как размерности (атрибуты объектов и контейнеров из реального мира), разделы (группировки объектов), области видимости (группировки контейнеров) и использование (вклад объектов, назначенных контейнеру).
Затем Rebalancer предоставляет API для демонстрации часто используемых выражений для преобразований этих конструкций, а также рекурсивно для других выражений. Например, степень использования нескольких контейнеров может быть агрегирована с помощью операции SUM/MAX или преобразована с помощью операции SQUARE.
Наконец, используя эти выражения, Rebalancer предоставляет высокоуровневый API spec (спецификаций), реализующий десятки общих целей и ограничений. Каждую спецификацию можно рассматривать как предопределенный рецепт, который принимает в качестве входных данных некоторые конструкций моделирования и дополнительные параметры и создает математическую формулу с использованием API выражений.

Пример конструкций моделирования и спецификаций для задачи размещения задач.

В приведенном выше примере задачи моделируются как объекты, а серверы — как контейнеры, в которые должны быть помещены задачи. Серверы физически расположены в стойках; эта группировка моделируется как область видимости (scope). Задачи требуют определенного объема ЦП и хранилища, а серверы имеют ограниченный объем каждого ресурса. ЦП и хранилище моделируются как размерности (dimensions). Использование ЦП и хранилища сервера соответствует сумме всех задач, назначенных этому серверу, а пределы использования сервера моделируются с помощью CapacitySpec. API выражений может использоваться для изменения того, как рассчитывается использование, если простое суммирование не подходит.

Кроме того, мы моделируем задачи как принадлежащие заданиям. Подобная группировка объектов называется разделом (partition), и мы используем GroupCountSpec, чтобы гарантировать, что каждой стойке назначен только один тип заданий (раздел). BalanceSpec гарантирует, что использование каждого сервера сбалансировано как по ЦП, так и по размерностям хранилища.

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

Ознакомьтесь с исчерпывающим списком спецификаций Rebalancer в документации.

Решение задач распределения

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

Наряду с целями и ограничениями задачи, специалисты по моделированию также предоставляют Rebalancer начальное назначение и условие останова, такое как ограничение по времени. Rebalancer вычислит оптимизированное назначение, которое минимизирует целевое значение и не нарушает никаких новых ограничений. Ограничения, которые были нарушены исходным назначением, становятся целями с высоким приоритетом, и их нарушение сводится к минимуму, в идеале — к нулю.

Rebalancer предлагает два различных метода решения задачи распределения.

Оптимальный решатель. В этом режиме Rebalancer преобразует граф выражений в набор выражений, которые могут быть переданы в решатели MIP, такие как FICO Xpress, Gurobi или HiGHS. Во время этого преобразования Rebalancer должен представлять использование контейнера взвешенной суммой бинарных переменных решения (по одной на объект), которые указывают, назначен ли объект контейнеру; это может привести к созданию очень больших моделей MIP! Rebalancer автоматически использует такие методы, как агрегирование переменных (упаковка похожих объектов в одну целочисленную переменную), взаимозаменяемость и нарушение симметрии для уменьшения размеров моделей, но размер сгенерированной модели MIP в худшем случае все равно может быть квадратичным, то есть O (|objects| * |bins|). Самые большие рассматриваемые нами задачи слишком велики для любого решателя MIP.

Решатель локального поиска преодолевает это ограничение, работая непосредственно с графом выражений и исследуя локальную окрестность вокруг текущего назначения путем перемещения некоторых объектов в другой контейнер. Размер этой окрестности в худшем случае составляет O (|objects|+|bins|), что позволяет Rebalancer моделировать даже очень большие задачи без достижения ограничений памяти. Каждое перемещение создает новое кандидатное назначение, для которого Rebalancer оценивает новые значения целей и ограничений. После оценки всех кандидатов Rebalancer применяет лучшее кандидатное назначение; то есть то, которое не нарушает ограничение и улучшает цель на максимальную величину. Этот процесс оценки и применения перемещений повторяется до тех пор, пока не перестанет наблюдаться прогресс или не будет достигнуто условие останова. Алгоритм локального поиска Rebalancer сильно оптимизирован и распараллелен, поэтому каждая оценка относительно недорога (возможны миллионы оценок в секунду), что позволяет нам быстро исследовать пространство поиска. Кроме того, Rebalancer умеет отсекать пространство поиска, сокращая количество необходимых оценок с самого начала.

Правильный метод решения будет зависеть от ваших потребностей. В Meta почти все крупномасштабные задачи используют локальный поиск. Задачи малого и среднего размера с умеренными требованиями к времени решения часто используют оптимальный решатель. Также распространено создание прототипов с помощью оптимального решателя с последующим переходом к локальному поиску после того, как будет определено высококачественное базовое решение. В автономном режиме (offline) оптимальный решатель может использоваться для настройки локального поиска.

Rebalancer в Meta

За последнее десятилетие Rebalancer постоянно использовался и совершенствовался в Meta. Он используется для решения широкого спектра задач оптимизации инфраструктуры, включая назначение шардов серверам (Shard Manager), серверов — сервисам (RAS), маршрутизацию трафика от глобально распределенных граничных дата-центров к основным дата-центрам (Taiji), группировку бессерверных функций для улучшения локальности, балансировку рабочих нагрузок онлайн-обучения ML по регионам с учетом приоритета рабочих нагрузок ML и т. д. На момент написания этой статьи Rebalancer используется для решения примерно 40 миллионов задач распределения каждый день с более чем 30 уникальными формулировками задач. Время решения на уровне P99 составляет 12 секунд для задачи с 265 тыс. объектов и 3,2 тыс. контейнеров. Для задач с количеством объектов более 1 млн и контейнеров более 5 тыс. среднее время решения составляет 171 секунду, и насчитывается более 3,4 тыс. таких запусков.

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

Отладка

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

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

Будущее Rebalancer

Мы всегда стремимся оптимизировать производительность Rebalancer, добавлять новые возможности и расширять его для поддержки более широкого спектра задач распределения. Rebalancer с гордостью имеет открытый исходный код (лицензия Apache 2.0), и мы приглашаем как экспертов по системам, так и специалистов по оптимизации попробовать Rebalancer и внести свой вклад в проект, выявив узкие места производительности, добавив новые методы решения, расширив его для поддержки новых видов задач или просто исправив ошибки. Мы с нетерпением ждем возможности увидеть, как сообщества разработчиков систем и оптимизации будут принимать, развивать Rebalancer и вносить в него свой вклад.

Благодарности

Rebalancer был разработан прошлыми и нынешними членами команды алгоритмической оптимизации в Meta: Пол Маури Руис, Игорь Кабильо, Нирадж Кумар, Виджай Менон, Маянк Пундир, Эндрю Ньюэлл, Лиюань Ван, Ричард Барнс, Сахил Дешпанде, Картик Велакур, Янг Лю, Леарт Гджони, Рави Суруликаму, Тони Чжан, Радж Раджендран, Аравинд Нараянан, Лакшми Ганеш и Саранян Виграхам.