A Meta liberou como código aberto o Rebalancer, uma biblioteca escrita em C++ com interface para Python dedicada à resolução de problemas de alocação, aqueles em que é preciso decidir quais objetos entram em quais recipientes respeitando restrições e objetivos. A ferramenta não é um experimento de laboratório: segundo o anúncio publicado no blog Engineering at Meta, ela cuida da alocação de recursos da companhia há mais de nove anos. O lançamento chegou sob licença Apache 2.0, acompanhado de documentação, pacote no PyPI e uma interface de depuração chamada Rebalancer Explorer.
A biblioteca já pode ser usada em produção hoje. O comando de instalação do PyPI entrega a versão 1.0.4 para Python 3.12 ou superior, com pacotes pré-compilados para Linux em x86-64 e macOS 14 ou mais recente em ARM64. Também existem pacotes no formato .deb, .rpm e para o gerenciador Homebrew. Vale registrar que o PyPI ainda classifica o projeto como Alfa, um sinal de que a maturidade oficial do produto está em construção apesar do histórico interno.
Os problemas de alocação aparecem em toda a infraestrutura da Meta: racks distribuídos entre datacenters, servidores atribuídos a serviços, tarefas alocadas a servidores e tráfego de usuários roteado para datacenters. A empresa identificou dois entraves nesse cenário. O primeiro é a usabilidade, já que engenheiros têm dificuldade em converter políticas de negócio em fórmulas matemáticas precisas. O segundo é a escalabilidade, porque muitos desses problemas são classificados como NP-difíceis, ou seja, não existe algoritmo conhecido que os resolva de forma eficiente no pior caso, e o tamanho deles ultrapassa a capacidade de solucionadores comerciais.
A resposta do Rebalancer foi separar como um problema é descrito de como ele é resolvido. Essa arquitetura está detalhada no artigo Optimizing Resource Allocation in Hyperscale Datacenters, apresentado na conferência OSDI 2024. A linguagem de especificação funciona em três camadas: construtos de modelagem, que definem dimensões como CPU ou armazenamento, partições que agrupam objetos, escopos que agrupam recipientes e a utilização; uma API de expressões, que agrega a utilização com operações de soma ou máximo e a transforma com operações como elevar ao quadrado; e a API de especificações, com dezenas de objetivos e restrições pré-definidos listados na documentação.
No exemplo divulgado pela Meta, tarefas são modeladas como objetos, servidores como recipientes e racks como escopo. Uma restrição de capacidade limita CPU e armazenamento por servidor, uma restrição de contagem por grupo mantém apenas um tipo de trabalho por rack e uma restrição de equilíbrio distribui a utilização de cada servidor nas duas dimensões. O repositório no GitHub reúne o código-fonte completo do projeto.
Internamente, o Rebalancer compila essa especificação em um grafo de expressão acíclico dirigido, uma estrutura em que os nós folha guardam valores de utilização e os nós superiores realizam agregações e transformações. O usuário fornece uma alocação inicial e uma condição de parada, e as restrições já violadas na configuração inicial viram metas de alta prioridade. Dessa estrutura saem dois solucionadores. O primeiro traduz o grafo em um programa de inteiro misto, modelo matemático executado por solucionadores como FICO Xpress, Gurobi e HiGHS, com técnicas de agregação de variáveis e quebra de simetria para reduzir o tamanho dos modelos, embora o pior caso continue crescendo na ordem do produto entre objetos e recipientes.
Foi por isso que a Meta criou um segundo caminho, a busca local, que opera diretamente sobre o grafo de expressão. Esse método explora movimentos de objetos para outros recipientes, com vizinhança de pior caso na ordem da soma entre objetos e recipientes, e aplica o melhor candidato que não viole nenhuma restrição. A avaliação é paralelizada a ponto de alcançar milhões de verificações por segundo, com poda do espaço de busca. Na prática, a empresa usa busca local em quase todos os problemas grandes e o solucionador ótimo nos pequenos e médios, muitas vezes criando protótipos com o método exato antes de migrar.
Os números de produção impressionam: cerca de 40 milhões de problemas resolvidos por dia em mais de 30 formulações distintas, com tempo de solução no percentil 99 de 12 segundos em cenários com 265 mil objetos e 3,2 mil recipientes. Em problemas acima de um milhão de objetos e 5 mil recipientes, a média é de 171 segundos, medida sobre mais de 3,4 mil execuções. Entre as aplicações estão a colocação de shards, tarefas e contêineres em clusters, operação do Shard Manager e do sistema RAS, o roteamento de tráfego de borda feito pelo Taiji, o balanceamento de treinamento de aprendizado de máquina por prioridade e até atribuições operacionais como tickets de suporte a engenheiros e reuniões a salas.
Para facilitar o trabalho de quem modela esses problemas, a Meta incluiu o Rebalancer Explorer, uma interface web distribuída em contêiner Docker que mostra quais restrições estão limitando a solução, efeitos de relaxações e por que cada objeto terminou em determinado recipiente. A justificativa é direta: modeladores passavam a maior parte do tempo depurando o comportamento do solucionador.
Diante de alternativas como o Google OR-Tools, que cobre mais classes de problema, e o Timefold Solver, voltado a escalonamento e roteamento em ambientes Java, o diferencial do Rebalancer é permitir uma única especificação de alocação executável tanto em busca local quanto em solucionadores de programação inteira mista. O anúncio completo está disponível no blog Engineering at Meta, e a biblioteca pode ser instalada via pip ou baixada no GitHub da Meta.
