Optimisation de NVIDIA CAGRA dans Milvus : une approche hybride GPU-CPU pour une indexation plus rapide et des requêtes moins coûteuses

À mesure que les systèmes d'IA passent de l'expérimentation à l'infrastructure de production, les bases de données vectorielles ne traitent plus des millions d'enchâssements. Des milliards sont désormais habituels, et des dizaines de milliards sont de plus en plus courants. À cette échelle, les choix algorithmiques affectent non seulement les performances et la mémorisation, mais se traduisent aussi directement par le coût de l'infrastructure.

Cela conduit à une question centrale pour les déploiements à grande échelle : comment choisir le bon index pour obtenir un rappel et une latence acceptables sans que l'utilisation des ressources de calcul ne devienne incontrôlable ?

Les index basés sur des graphes tels que NSW, HNSW, CAGRA et Vamana sont devenus la réponse la plus largement adoptée. En naviguant dans des graphes de voisinage préconstruits, ces index permettent une recherche rapide du plus proche voisin à l'échelle du milliard, évitant ainsi le balayage brutal et la comparaison de chaque vecteur par rapport à la requête.

Cependant, le profil de coût de cette approche est inégal. L'interrogation d'un graphe est relativement bon marché, ce qui n'est pas le cas de sa construction. La construction d'un graphe de haute qualité nécessite des calculs de distance à grande échelle et un raffinement itératif sur l'ensemble du jeu de données - des charges que les ressources CPU traditionnelles ont du mal à gérer efficacement au fur et à mesure que les données augmentent.

CAGRA de NVIDIA s'attaque à ce goulot d'étranglement en utilisant les GPU pour accélérer la construction des graphes grâce à un parallélisme massif. Bien que cela réduise considérablement le temps de construction, le fait de s'appuyer sur les GPU pour la construction d'index et l'exécution de requêtes introduit des contraintes de coût et d'évolutivité plus élevées dans les environnements de production.

Pour équilibrer ces compromis, Milvus 2.6.1 adopte une conception hybride pour les index GPU_CAGRA: Les GPU sont utilisés uniquement pour la construction des graphes, tandis que l'exécution des requêtes se fait sur les CPU. Cela permet de préserver les avantages qualitatifs des graphes construits par les GPU tout en maintenant l'évolutivité et la rentabilité de l'exécution des requêtes, ce qui est particulièrement bien adapté aux charges de travail avec des mises à jour de données peu fréquentes, des volumes de requêtes importants et une sensibilité stricte aux coûts.

Qu'est-ce que CAGRA et comment fonctionne-t-il ?

Les index vectoriels basés sur des graphes se répartissent généralement en deux grandes catégories :

• Laconstruction itérative de graphes, représentée par CAGRA (déjà pris en charge dans Milvus).

• Laconstruction de graphe basée sur l'insertion, représentée par Vamana (actuellement en cours de développement dans Milvus).

Ces deux approches diffèrent considérablement dans leurs objectifs de conception et leurs fondements techniques, ce qui les rend adaptées à des échelles de données et à des modèles de charge de travail différents.

NVIDIA CAGRA (CUDA ANN Graph-based) est un algorithme natif du GPU pour la recherche approximative du plus proche voisin (ANN), conçu pour construire et interroger efficacement des graphes de proximité à grande échelle. En tirant parti du parallélisme des GPU, CAGRA accélère considérablement la construction des graphes et offre des performances d'interrogation à haut débit par rapport aux approches basées sur le CPU telles que HNSW.

CAGRA repose sur l'algorithme NN-Descent (Nearest Neighbor Descent), qui construit un graphe k-nearest-neighbor (kNN) par raffinement itératif. À chaque itération, les voisins candidats sont évalués et mis à jour, ce qui permet de converger progressivement vers des relations de voisinage de meilleure qualité dans l'ensemble des données.

Après chaque tour d'affinage, CAGRA applique des techniques supplémentaires d'élagage des graphes, telles que l'élagage des détours à deux sauts, afin d'éliminer les arêtes redondantes tout en préservant la qualité de la recherche. Cette combinaison d'affinage et d'élagage itératifs permet d'obtenir un graphe compact, mais bien connecté, qui peut être parcouru efficacement au moment de la requête.

Grâce à l'affinage et à l'élagage répétés, CAGRA produit une structure de graphe qui permet un rappel élevé et une recherche du plus proche voisin à faible latence à grande échelle, ce qui la rend particulièrement bien adaptée aux ensembles de données statiques ou rarement mis à jour.

Étape 1 : Construction du graphe initial avec NN-Descent

L'algorithme NN-Descent repose sur une observation simple mais puissante : si le nœud u est un voisin de v et que le nœud w est un voisin de u, alors w est très probablement un voisin de v également. Cette propriété transitive permet à l'algorithme de découvrir efficacement les vrais voisins les plus proches, sans comparer exhaustivement chaque paire de vecteurs.

CAGRA utilise NN-Descent comme algorithme principal de construction de graphe. Le processus se déroule comme suit

1. Initialisation aléatoire : Chaque nœud commence avec un petit ensemble de voisins sélectionnés au hasard, formant ainsi un graphe initial approximatif.

2. Expansion des voisins : À chaque itération, un nœud rassemble ses voisins actuels et leurs voisins pour former une liste de candidats. L'algorithme calcule les similitudes entre le nœud et tous les candidats. La liste des candidats de chaque nœud étant indépendante, ces calculs peuvent être assignés à des blocs de threads GPU distincts et exécutés en parallèle à grande échelle.

3. Mise à jour de la liste des candidats : si l'algorithme trouve des candidats plus proches que les voisins actuels du nœud, il remplace les voisins les plus éloignés et met à jour la liste kNN du nœud. Sur plusieurs itérations, ce processus produit un graphe kNN approximatif de bien meilleure qualité.

4. Vérification de la convergence : Au fur et à mesure des itérations, le nombre de mises à jour des voisins diminue. Une fois que le nombre de connexions mises à jour est inférieur à un seuil défini, l'algorithme s'arrête, indiquant que le graphe s'est effectivement stabilisé.

Étant donné que l'expansion des voisins et le calcul de la similarité pour les différents nœuds sont totalement indépendants, CAGRA fait correspondre la charge de travail NN-Descent de chaque nœud à un bloc de threads GPU dédié. Cette conception permet un parallélisme massif et rend la construction de graphes plusieurs fois plus rapide que les méthodes traditionnelles basées sur le CPU.

Étape 2 : Élagage du graphe à l'aide de détours à 2 sauts

Une fois la méthode NN-Descent terminée, le graphe obtenu est précis mais trop dense. NN-Descent conserve intentionnellement des voisins candidats supplémentaires, et la phase d'initialisation aléatoire introduit de nombreuses arêtes faibles ou non pertinentes. Par conséquent, chaque nœud se retrouve souvent avec un degré deux fois, voire plusieurs fois, plus élevé que le degré cible.

Pour produire un graphe compact et efficace, CAGRA applique un élagage des détours de 2 sauts.

L'idée est simple : si le nœud A peut atteindre le nœud B indirectement par l'intermédiaire d'un voisin commun C (formant un chemin A → C → B), et que la distance de ce chemin indirect est comparable à la distance directe entre A et B, alors l'arête directe A → B est considérée comme redondante et peut être supprimée.

L'un des principaux avantages de cette stratégie d'élagage est que la vérification de la redondance de chaque arête ne dépend que d'informations locales, à savoir les distances entre les deux points d'extrémité et leurs voisins communs. Comme chaque arête peut être évaluée indépendamment, l'étape d'élagage est hautement parallélisable et s'adapte naturellement à l'exécution par lots sur GPU.

Par conséquent, CAGRA peut élaguer le graphe efficacement sur les GPU, en réduisant les frais de stockage de 40 à 50 % tout en préservant la précision de la recherche et en améliorant la vitesse de traversée pendant l'exécution de la requête.

GPU_CAGRA dans Milvus : qu'est-ce qui est différent ?

Alors que les GPU offrent des avantages majeurs en termes de performances pour la construction de graphes, les environnements de production sont confrontés à un défi pratique : Les ressources GPU sont beaucoup plus chères et limitées que les CPU. Si la construction d'index et l'exécution de requêtes dépendent uniquement des GPU, plusieurs problèmes opérationnels apparaissent rapidement :

• Faible utilisation des ressources : Le trafic des requêtes est souvent irrégulier et en rafale, ce qui laisse les GPU inactifs pendant de longues périodes et gaspille une capacité de calcul coûteuse.

• Coût de déploiement élevé : L'affectation d'un GPU à chaque instance de service de requête augmente les coûts matériels, même si la plupart des requêtes n'utilisent pas pleinement les performances du GPU.

• Évolutivité limitée : Le nombre de GPU disponibles conditionne directement le nombre de répliques de service que vous pouvez exécuter, ce qui limite votre capacité à évoluer en fonction de la demande.

• Flexibilité réduite : Lorsque la construction d'index et les requêtes dépendent des GPU, le système est lié à la disponibilité des GPU et ne peut pas facilement déplacer les charges de travail vers les CPU.

Pour répondre à ces contraintes, Milvus 2.6.1 introduit un mode de déploiement flexible pour l'index GPU_CAGRA via le paramètre adapt_for_cpu. Ce mode permet un flux de travail hybride : CAGRA utilise le GPU pour construire un index graphique de haute qualité, tandis que l'exécution des requêtes s'effectue sur le CPU, en utilisant généralement HNSW comme algorithme de recherche.

Dans cette configuration, les GPU sont utilisés là où ils apportent le plus de valeur - construction rapide et très précise de l'index - tandis que les CPU gèrent les charges de travail des requêtes à grande échelle d'une manière beaucoup plus rentable et évolutive.

Par conséquent, cette approche hybride est particulièrement bien adaptée aux charges de travail dans les cas suivants

• les mises à jour de données sont peu fréquentes, de sorte que les reconstructions d'index sont rares

• Le volume des requêtes est élevé, ce qui nécessite de nombreuses répliques peu coûteuses.

• La sensibilité aux coûts est élevée et l'utilisation des GPU doit être étroitement contrôlée.

Comprendre adapt_for_cpu

Dans Milvus, le paramètre adapt_for_cpu contrôle la manière dont un index CAGRA est sérialisé sur le disque pendant la construction de l'index et la manière dont il est désérialisé en mémoire au moment du chargement. En modifiant ce paramètre au moment de la construction et du chargement, Milvus peut basculer de manière flexible entre la construction d'index basée sur le GPU et l'exécution de requêtes basée sur le CPU.

Différentes combinaisons de adapt_for_cpu au moment de la construction et du chargement donnent lieu à quatre modes d'exécution, chacun conçu pour un scénario opérationnel spécifique.

Temps de construction (adapt_for_cpu)	Temps de chargement (adapt_for_cpu)	Logique d'exécution	Scénario recommandé
vrai	vrai	Construction avec GPU_CAGRA → sérialisation en HNSW → désérialisation en HNSW → interrogation CPU	Charges de travail sensibles aux coûts ; service de requêtes à grande échelle
vrai	faux	Construire avec GPU_CAGRA → sérialiser en HNSW → désérialiser en HNSW → interrogation CPU	Les requêtes suivantes sont renvoyées à l'unité centrale en cas de non-concordance des paramètres.
faux	vrai	Construire avec GPU_CAGRA → sérialiser en CAGRA → désérialiser en HNSW → interrogation CPU	Conserver l'index CAGRA original pour le stockage tout en permettant une recherche temporaire par l'unité centrale.
faux	faux	Construire avec GPU_CAGRA → sérialiser en CAGRA → désérialiser en CAGRA → interrogation GPU	Charges de travail critiques en termes de performances où le coût est secondaire

Remarque : le mécanisme adapt_for_cpu ne prend en charge que les conversions à sens unique. Un index CAGRA peut être converti en HNSW car la structure du graphe CAGRA préserve toutes les relations de voisinage dont HNSW a besoin. Toutefois, un index HNSW ne peut pas être reconverti en CAGRA, car il ne dispose pas des informations structurelles supplémentaires nécessaires pour les requêtes basées sur le GPU. Par conséquent, les paramètres du temps de construction doivent être sélectionnés avec soin, en tenant compte des exigences de déploiement et d'interrogation à long terme.

Mise à l'épreuve de GPU_CAGRA

Pour évaluer l'efficacité du modèle d'exécution hybride - utilisant les GPU pour la construction de l'index et les CPU pour l'exécution des requêtes - nous avons mené une série d'expériences contrôlées dans un environnement standardisé. L'évaluation se concentre sur trois dimensions : la performance de la construction de l'index, la performance des requêtes et la précision du rappel.

Configuration expérimentale

Les expériences ont été réalisées sur du matériel standard largement adopté par l'industrie afin de s'assurer que les résultats restent fiables et largement applicables.

• CPU : Processeur MD EPYC 7R13 (16 cpus)

• GPU : NVIDIA L4

1. Performance de la construction de l'index

Nous comparons CAGRA construit sur le GPU avec HNSW construit sur le CPU, avec le même degré de graphe cible de 64.

Principales conclusions

• GPU CAGRA construit des index 12-15× plus rapidement que CPU HNSW. Sur Cohere1M et Gist1M, CAGRA basé sur le GPU surpasse de manière significative HNSW basé sur le CPU, soulignant l'efficacité du parallélisme du GPU pendant la construction du graphe.

• Le temps de construction augmente linéairement avec les itérations NN-Descent. Au fur et à mesure que le nombre d'itérations augmente, le temps de construction croît de manière quasi-linéaire, reflétant la nature itérative du raffinement de la NN-Descent et fournissant un compromis prévisible entre le coût de construction et la qualité du graphe.

2. Performance des requêtes

Dans cette expérience, le graphe CAGRA est construit une fois sur le GPU et ensuite interrogé en utilisant deux chemins d'exécution différents :

• Requête CPU: l'index est désérialisé au format HNSW et recherché sur le CPU.

• Interrogation par le GPU: la recherche s'exécute directement sur le graphe CAGRA à l'aide d'un parcours basé sur le GPU.

Principales conclusions

• Le débit de recherche du GPU est 5 à 6 fois plus élevé que celui du CPU. Dans Cohere1M et Gist1M, la traversée basée sur le GPU fournit un QPS substantiellement plus élevé, soulignant l'efficacité de la navigation parallèle dans les graphes sur les GPU.

• Le rappel augmente avec les itérations de NN-Descent, puis plafonne. Au fur et à mesure que le nombre d'itérations de construction augmente, le rappel s'améliore à la fois pour les requêtes CPU et GPU. Cependant, au-delà d'un certain point, les itérations supplémentaires produisent des gains décroissants, ce qui indique que la qualité du graphe a largement convergé.

3. Précision du rappel

Dans cette expérience, CAGRA et HNSW sont interrogés sur le CPU afin de comparer le rappel dans des conditions d'interrogation identiques.

Principales conclusions

CAGRAobtient un rappel plus élevé que HNSW sur les deux ensembles de données, ce qui montre que même lorsqu'un index CAGRA est construit sur le GPU et désérialisé pour la recherche sur le CPU, la qualité du graphe est bien préservée.

Prochaines étapes : Mise à l'échelle de la construction d'index avec Vamana

L'approche hybride GPU-CPU de Milvus offre une solution pratique et rentable pour les charges de travail actuelles de recherche vectorielle à grande échelle. En construisant des graphes CAGRA de haute qualité sur les GPU et en servant les requêtes sur les CPU, elle combine une construction d'index rapide avec une exécution de requêtes évolutive et abordable, particulièrementbien adaptée aux charges de travail avec des mises à jour peu fréquentes, des volumes de requêtes élevés et des contraintes de coûts strictes.

À des échelles encore plus grandes - des dizainesou des centaines de milliards de vecteurs -la construction d'indexdevient elle-même un goulot d'étranglement. Lorsque l'ensemble des données ne tient plus dans la mémoire du GPU, l'industrie se tourne généralement vers des méthodes de construction de graphe basées sur l'insertion, telles que Vamana. Au lieu de construire le graphe en une seule fois, Vamana traite les données par lots, en insérant progressivement de nouveaux vecteurs tout en maintenant la connectivité globale.

Son pipeline de construction suit trois étapes clés :

1. Croissance géométrique des lots - en commençant par de petits lots pour former un squelette de graphe, puis en augmentant la taille des lots pour maximiser le parallélisme, et enfin en utilisant de grands lots pour affiner les détails.

2. Insertion gourmande - chaque nouveau nœud est inséré en naviguant à partir d'un point d'entrée central, en affinant itérativement son ensemble de voisins.

3. Mise à jour des arêtes rétrogrades - ajout de connexions inverses pour préserver la symétrie et assurer une navigation efficace dans le graphe.

L'élagage est intégré directement dans le processus de construction en utilisant le critère α-RNG : si un voisin candidat v est déjà couvert par un voisin existant p′ (c'est-à-dire, d(p′, v) < α × d(p, v)), alors v est élagué. Le paramètre α permet un contrôle précis de l'éparpillement et de la précision. L'accélération GPU est obtenue grâce au parallélisme in-batch et à la mise à l'échelle géométrique des lots, ce qui permet de trouver un équilibre entre la qualité de l'index et le débit.

Ensemble, ces techniques permettent aux équipes de gérer la croissance rapide des données et les mises à jour d'index à grande échelle sans se heurter aux limites de la mémoire du GPU.

L'équipe Milvus développe activement la prise en charge de Vamana, avec une sortie prévue au premier semestre 2026. Restez à l'écoute.

Vous avez des questions ou souhaitez approfondir l'une des fonctionnalités de la dernière version de Milvus ? Rejoignez notre canal Discord ou déposez des questions sur GitHub. Vous pouvez également réserver une session individuelle de 20 minutes pour obtenir des informations, des conseils et des réponses à vos questions dans le cadre des Milvus Office Hours.

En savoir plus sur les fonctionnalités de Milvus 2.6

• Présentation de Milvus 2.6 : recherche vectorielle abordable à l'échelle du milliard

• Présentation de la fonction d'intégration : Comment Milvus 2.6 rationalise la vectorisation et la recherche sémantique

• Déchiquetage JSON dans Milvus : filtrage JSON 88,9 fois plus rapide et flexible

• Déverrouiller la véritable recherche au niveau de l'entité : Nouvelles fonctionnalités Array-of-Structs et MAX_SIM dans Milvus

• MinHash LSH dans Milvus : l'arme secrète pour lutter contre les doublons dans les données de formation LLM

• La compression vectorielle à l'extrême : comment Milvus répond à 3× plus de requêtes avec RaBitQ

• Les benchmarks mentent - les bases de données vectorielles méritent un vrai test

• Nous avons remplacé Kafka/Pulsar par un Woodpecker pour Milvus