Meta a mis en open source aujourd’hui Rebalancer, une bibliothèque C++ conçue pour résoudre des problèmes d’affectation à grande échelle. L’annonce vient de Meta elle-même. Le projet arrive avec une interface Python, de la documentation, un outil de débogage appelé Rebalancer Explorer, ainsi que des paquets prêts à l’emploi.
Le groupe explique s’en servir en interne depuis plus de neuf ans. À ce jour, l’outil traiterait autour de 40 millions de problèmes par jour, répartis dans plus de 30 applications. Rebalancer est publié sous licence Apache 2.0 et, d’après sa page PyPI, la version actuelle est la v1.0.4 pour Python 3.12 et versions supérieures. Des wheels précompilées sont proposées pour Linux x86-64 et macOS 14+ ARM64, avec aussi des paquets .deb, .rpm et Homebrew.
Au fond, Rebalancer s’attaque à un problème très classique : répartir des objets dans des « bins », autrement dit des cases ou des ressources disponibles, tout en respectant un ensemble de contraintes et d’objectifs.
Chez Meta, ça recouvre des cas très concrets. L’entreprise cite par exemple le placement de racks dans les datacenters, l’affectation de serveurs à des services, la planification de tâches sur des machines ou encore le routage du trafic utilisateur entre plusieurs centres de données. L’idée, côté Meta, est d’avoir un outil généraliste plutôt qu’un empilement de solutions spécialisées. En interne, Rebalancer aurait déjà été utilisé pour le placement de shards, l’allocation de tickets de support ou l’attribution de salles.
Un des choix de conception les plus marquants tient à la séparation entre la description du problème et sa résolution. Le but est que des ingénieurs qui ne sont pas spécialistes de l’optimisation puissent exprimer des politiques opérationnelles sans avoir à écrire eux-mêmes une formulation mathématique complète, explique Meta.
Le langage de spécification s’organise en trois couches, si l’on suit la documentation publiée par l’entreprise : d’abord des briques de modélisation, avec les dimensions, partitions, scopes et notions d’utilisation ; ensuite une API d’expressions, avec des opérations comme SUM, MAX ou SQUARE ; enfin une API de spécification qui fournit des objectifs et des contraintes prédéfinis. Meta donne notamment un exemple où l’on combine des limites de capacité, le regroupement d’un même job dans un même rack et l’équilibrage de charge sur plusieurs ressources.
Sur le plan technique, Meta indique que Rebalancer compile cette spécification en un graphe d’expressions acyclique orienté, puis suit deux chemins distincts.
Le premier transforme le problème en programme linéaire en nombres entiers mixtes, destiné à des solveurs comme FICO Xpress, Gurobi ou HiGHS. Le second s’appuie sur une recherche locale qui opère directement sur le graphe, explore des déplacements d’objets entre bins, réduit l’espace de recherche et évalue des candidats en parallèle.
Meta présente ce second mode comme une réponse à une limite bien connue : beaucoup de problèmes d’affectation sont NP-difficiles et deviennent trop volumineux pour être absorbés par de simples solveurs commerciaux. L’entreprise précise que la formulation MIP peut grimper, dans le pire des cas, à O(objets × bins), alors que la recherche locale vise un voisinage plus réduit en O(objets + bins).
Côté performances, Meta annonce un temps de résolution P99 de 12 secondes pour un problème comportant 265 000 objets et 3 200 bins. Pour des cas qui dépassent 1 million d’objets, la moyenne avancée est de 171 secondes.
Le système est décrit plus en détail dans l’article OSDI 2024 intitulé « Optimizing Resource Allocation in Hyperscale Datacenters ». Plus surprenant, vu l’échelle d’usage revendiquée en interne, les signes d’adoption à l’extérieur restent encore modestes. La fiche PyPI classe d’ailleurs, pour l’instant, le projet dans la catégorie Alpha. Et puis il y a un point très concret : la qualité du résultat dépend beaucoup de la façon dont le problème est modélisé, tandis que la recherche locale peut favoriser la vitesse plutôt que l’optimum absolu.
Suivez-moi sur Twitter : @pierrevitre
