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

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

Имея набор объектов и набор корзин, как распределить объекты по корзинам так, чтобы оптимизировать определенные целевые функции (критерии) и при этом соблюсти заданные ограничения?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Rebalancer в Meta

Последнее десятилетие Rebalancer непрерывно использовался и совершенствовался в Meta. Он используется для решения широкого спектра задач оптимизации инфраструктуры, включая распределение шардов по серверам (Shard Manager), серверов по сервисам (RAS), маршрутизацию трафика из глобально распределенных пограничных дата-центров в основные дата-центры (Taiji), группировку бессерверных (serverless) функций для улучшения локальности, балансировку рабочих нагрузок онлайн-обучения 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: Пол Маури Руис, Игорь Кабильо, Нирадж Кумар, Виджай Менон, Маянк Пундир, Эндрю Ньюэлл, Лиюань Ван, Ричард Барнс, Сахил Дешпанде, Картик Велакур, Янг Лю, Леарт Гджони, Рави Суруликаму, Тони Чжан, Радж Раджендран, Аравинд Нараянан, Лакшми Ганеш и Саранян Виграхам.