Meta rilascia Rebalancer: un solver che gestisce 40 milioni di problemi di assegnazione al giorno

Meta ha rilasciato Rebalancer, un solver ad alte prestazioni che aiuta a assegnare oggetti a contenitori rispettando vincoli stringenti. Lo strumento è in uso interno da oltre nove anni, risolvendo circa 40 milioni di problemi di collocazione al giorno su oltre 30 applicazioni interne ¹. Ora è disponibile al pubblico con licenza open-source Apache 2.0.

Cosa fa

I problemi di assegnazione pongono una domanda semplice: quale oggetto va in quale contenitore? La risposta dipende da regole — come limiti di CPU o capacità di archiviazione — e obiettivi, come mantenere l'equilibrio. A Meta lo stesso problema si presenta ovunque: collocare rack nei datacenter, assegnare server a servizi, instradare attività su macchine e indirizzare il traffico utente verso regioni.

La sfida è che molti di questi problemi sono NP-hard, ovvero troppo grandi perché i solver commerciali più comuni possano gestirli in modo efficiente ³. Gli ingegneri faticano anche a tradurre le loro politiche in formule precise. Rebalancer cerca di risolvere entrambi i problemi separando la descrizione del problema dalla sua effettiva risoluzione.

Come funziona

Rebalancer utilizza un linguaggio di specifica con tre livelli. Il livello di modellazione definisce dimensioni come CPU o memoria, partizioni di oggetti e scope di contenitori. Il livello di espressione permette di combinare quelle dimensioni usando operazioni come SUM o MAX. Il livello di specifica offre decine di vincoli e obiettivi integrati, come bilanciare il utilizzo tra server o limitare la capacità per rack ³.

Sotto il cofano, la specifica si compila in un grafo di espressioni. Da lì, gli utenti possono scegliere tra due approcci di risoluzione. Il solver di ricerca locale parte da una qualsiasi assegnazione valida e ne migliora ripetutamente i dettagli fino a quando non trova movimenti migliori. Esegue in parallelo e può valutare milioni di possibilità al secondo, risultando adatto a problemi di grande scala. Il solver ottimo traduce il grafo in un programma misto-intero e sfrutta backend commerciali o open-source come FICO Xpress, Gurobi o HiGHS. Trova la risposta migliore possibile ma funziona solo su problemi più piccoli ².

Meta utilizza la ricerca locale per quasi tutti i suoi problemi su larga scala e riserva il solver ottimo per casi più piccoli o prototipi rapidi ³.

Numeri reali

Su larga scala, il sistema è impressionante. Meta riporta un tempo di risoluzione P99 di soli 12 secondi per problemi che coinvolgono 265.000 oggetti e 3.200 contenitori ¹. Problemi ancora più grandi — oltre un milione di oggetti e 5.000 contenitori — impiegano in media circa 171 secondi per essere risolti. Il progetto include uno strumento di debugging in Docker chiamato Rebalancer Explorer, che aiuta gli ingegneri a comprendere perché il solver ha preso determinate decisioni ⁴.

Rebalancer è installabile tramite PyPI come versione 1.0.4 e richiede Python 3.12 o successivo ³. Sul catalogo dei pacchetti mantiene ancora una classificazione Alpha, ma Meta dichiara che è pronto per la produzione.

Why it matters

Altri strumenti open-source come Google OR-Tools e Timefold Solver gestiscono anch'essi problemi di assegnazione e pianificazione. Ma Rebalancer si distingue per la possibilità di definire un problema una volta in una specifica pulita e poi eseguirlo sia su un solver veloce di ricerca locale sia su uno matematicamente ottimo, senza riscrivere nulla ³. Per i team che costruiscono infrastrutture su larga scala, questa flessibilità potrebbe far risparmiare molto tempo di ingegneria.

I fatti principali

• Rebalancer risolve circa 40 milioni di problemi di assegnazione al giorno a Meta
• Il tempo di risoluzione P99 è di 12 secondi per problemi con 265.000 oggetti e 3.200 contenitori
• Disponibile su PyPI come v1.0.4 sotto licenza Apache 2.0
• Utilizza solver sia di ricerca locale sia di programmazione misto-intera
• È usato internamente da Meta da oltre nove anni

Fonti

1. Meta AI Open-Sources Rebalancer: A C++ Assignment Solver That Runs About 40 Million Placement Problems a Day — marktechpost.com
2. GitHub - facebook/rebalancer: Rebalancer is a domain-specific language ...
3. Meta AI Open-Sources Rebalancer: A C++ Assignment Solver That Runs ... — syncai.news
4. Meta Rebalancer is now open source: its C++ solver lands on PyPI — en.softonic.com
5. Open-Sourcing Rebalancer: A Generic, High-Performance Library for ... — engineering.fb.com