Optimierung von NVIDIA CAGRA in Milvus: Ein hybrider GPU-CPU-Ansatz für schnellere Indizierung und günstigere Abfragen

Mit dem Übergang von KI-Systemen von Experimenten zu Produktionsinfrastrukturen haben Vektordatenbanken nicht mehr mit Millionen von Einbettungen zu tun. Milliarden sind jetzt Routine, und Dutzende von Milliarden sind zunehmend üblich. In dieser Größenordnung wirken sich die Entscheidungen der Algorithmen nicht nur auf die Leistung und den Abruf aus, sondern schlagen sich auch direkt in den Infrastrukturkosten nieder.

Daraus ergibt sich eine zentrale Frage für den Einsatz in großem Maßstab: Wie wählt man den richtigen Index aus, um eine akzeptable Wiederauffindbarkeit und Latenzzeit zu erreichen, ohne dass die Nutzung der Rechenressourcen außer Kontrolle gerät?

Graphenbasierte Indizes wie NSW, HNSW, CAGRA und Vamana sind die am häufigsten verwendete Antwort. Durch die Navigation in vorgefertigten Nachbarschaftsgraphen ermöglichen diese Indizes eine schnelle Suche nach den nächsten Nachbarn im Milliardenmaßstab, ohne dass ein brutales Scannen und ein Vergleich jedes Vektors mit der Abfrage erforderlich ist.

Das Kostenprofil dieses Ansatzes ist jedoch uneinheitlich. Die Abfrage eines Graphen ist relativ billig, seine Erstellung dagegen nicht. Die Erstellung eines qualitativ hochwertigen Graphen erfordert umfangreiche Abstandsberechnungen und iterative Verfeinerungen über den gesamten Datensatz hinweg - Aufgaben, die herkömmliche CPU-Ressourcen bei wachsenden Datenmengen nur schwer bewältigen können.

NVIDIAs CAGRA behebt diesen Engpass, indem es GPUs zur Beschleunigung der Graphenerstellung durch massive Parallelität einsetzt. Dadurch wird zwar die Erstellungszeit erheblich verkürzt, aber der Einsatz von Grafikprozessoren sowohl für die Indexerstellung als auch für das Abfrageservice führt in Produktionsumgebungen zu höheren Kosten und Skalierbarkeitsbeschränkungen.

Um diese Kompromisse auszugleichen, wählt Milvus 2.6.1 ein hybrides Design für GPU_CAGRA-Indizes: GPUs werden nur für die Graphenkonstruktion verwendet, während die Abfrageausführung auf CPUs erfolgt. Dadurch bleiben die Qualitätsvorteile von GPU-erstellten Graphen erhalten, während die Abfrageausführung skalierbar und kosteneffizient bleibt - was sich besonders gut für Arbeitslasten mit seltenen Datenaktualisierungen, großen Abfragevolumina und strikter Kostensensitivität eignet.

Was ist CAGRA und wie funktioniert es?

Graphenbasierte Vektorindizes fallen im Allgemeinen in zwei Hauptkategorien:

• Iterative Graphenkonstruktion, dargestellt durch CAGRA (bereits in Milvus unterstützt).

• Einfügungsbasierte Graphenkonstruktion, repräsentiert durch Vamana (derzeit in der Entwicklung in Milvus).

Diese beiden Ansätze unterscheiden sich erheblich in ihren Designzielen und technischen Grundlagen, so dass sie für unterschiedliche Datenskalen und Arbeitslastmuster geeignet sind.

NVIDIA CAGRA (CUDA ANN Graph-based) ist ein GPU-nativer Algorithmus für die ungefähre Suche nach dem nächsten Nachbarn (ANN), der für die effiziente Erstellung und Abfrage großer Proximity-Graphen entwickelt wurde. Durch die Nutzung der GPU-Parallelität beschleunigt CAGRA den Aufbau von Graphen erheblich und bietet im Vergleich zu CPU-basierten Ansätzen wie HNSW eine hohe Durchsatzleistung bei Abfragen.

CAGRA basiert auf dem NN-Descent (Nearest Neighbor Descent) Algorithmus, der einen k-nearest-neighbor (kNN) Graphen durch iterative Verfeinerung konstruiert. In jeder Iteration werden die Nachbarschaftskandidaten bewertet und aktualisiert, so dass sich allmählich höherwertige Nachbarschaftsbeziehungen im gesamten Datensatz ergeben.

Nach jeder Verfeinerungsrunde wendet CAGRA zusätzliche Graph Pruning-Techniken an, wie z. B. 2-Hop Detour Pruning, umredundante Kanten zu entfernen und gleichzeitig die Suchqualität zu erhalten. Diese Kombination aus iterativer Verfeinerung und Beschneidung führt zu einem kompakten, aber gut vernetzten Graphen, der zur Abfragezeit effizient durchlaufen werden kann.

Durch wiederholtes Verfeinern und Beschneiden erzeugt CAGRA eine Graphenstruktur, die eine hohe Wiederauffindbarkeit und eine Nearest-Neighbor-Suche mit geringer Latenzzeit in großem Maßstab unterstützt, wodurch sie sich besonders gut für statische oder selten aktualisierte Datensätze eignet.

Schritt 1: Aufbau des Ausgangsgraphen mit NN-Descent

NN-Descent basiert auf einer einfachen, aber aussagekräftigen Beobachtung: Wenn Knoten u ein Nachbar von v und Knoten w ein Nachbar von u ist, dann ist w mit hoher Wahrscheinlichkeit auch ein Nachbar von v. Diese transitive Eigenschaft ermöglicht es dem Algorithmus, echte nächste Nachbarn effizient zu entdecken, ohne jedes Vektorpaar erschöpfend zu vergleichen.

CAGRA verwendet NN-Descent als Kernalgorithmus für die Graphkonstruktion. Der Prozess funktioniert wie folgt:

1. Zufällige Initialisierung: Jeder Knoten beginnt mit einer kleinen Menge zufällig ausgewählter Nachbarn, die einen groben Anfangsgraphen bilden.

2. Erweiterung der Nachbarschaft: In jeder Iteration sammelt ein Knoten seine aktuellen Nachbarn und deren Nachbarn, um eine Kandidatenliste zu erstellen. Der Algorithmus berechnet die Ähnlichkeiten zwischen dem Knoten und allen Kandidaten. Da die Kandidatenliste eines jeden Knotens unabhängig ist, können diese Berechnungen separaten GPU-Thread-Blöcken zugewiesen und in großem Umfang parallel ausgeführt werden.

3. Aktualisierung der Kandidatenliste: Wenn der Algorithmus Kandidaten findet, die näher liegen als die aktuellen Nachbarn des Knotens, tauscht er die weiter entfernten Nachbarn aus und aktualisiert die kNN-Liste des Knotens. Über mehrere Iterationen hinweg führt dieser Prozess zu einem wesentlich hochwertigeren approximativen kNN-Graphen.

4. Konvergenzprüfung: Je weiter die Iterationen fortschreiten, desto weniger Nachbarschaftsaktualisierungen finden statt. Sobald die Anzahl der aktualisierten Verbindungen unter einen bestimmten Schwellenwert fällt, stoppt der Algorithmus und zeigt damit an, dass sich der Graph tatsächlich stabilisiert hat.

Da die Nachbarschaftsexpansion und die Ähnlichkeitsberechnung für verschiedene Knoten völlig unabhängig sind, ordnet CAGRA die NN-Descent-Arbeitslast jedes Knotens einem speziellen GPU-Thread-Block zu. Dieses Design ermöglicht massive Parallelität und macht die Graphenkonstruktion um Größenordnungen schneller als herkömmliche CPU-basierte Methoden.

Schritt 2: Beschneidung des Graphen mit 2-Hop-Umwegen

Nach Abschluss des NN-Descent ist der resultierende Graph zwar genau, aber übermäßig dicht. NN-Descent behält absichtlich zusätzliche Nachbarschaftskandidaten, und die zufällige Initialisierungsphase führt viele schwache oder irrelevante Kanten ein. Infolgedessen hat jeder Knoten am Ende oft einen Grad, der doppelt oder sogar mehrfach so hoch ist wie der Zielgrad.

Um einen kompakten und effizienten Graphen zu erzeugen, wendet CAGRA das 2-Hop Detour Pruning an.

Die Idee ist einfach: Wenn der Knoten A den Knoten B indirekt über einen gemeinsamen Nachbarn C erreichen kann (indem er einen Pfad A → C → B bildet) und die Entfernung dieses indirekten Pfades mit der direkten Entfernung zwischen A und B vergleichbar ist, dann wird die direkte Kante A → B als überflüssig betrachtet und kann entfernt werden.

Ein entscheidender Vorteil dieser Pruning-Strategie ist, dass die Redundanzprüfung jeder Kante nur von lokalen Informationen abhängt - den Entfernungen zwischen den beiden Endpunkten und ihren gemeinsamen Nachbarn. Da jede Kante unabhängig ausgewertet werden kann, ist der Pruning-Schritt hochgradig parallelisierbar und passt natürlich in die GPU-Stapelverarbeitung.

Dadurch kann CAGRA den Graphen auf GPUs effizient beschneiden und den Speicheraufwand um 40-50% reduzieren, während die Suchgenauigkeit erhalten bleibt und die Traversalgeschwindigkeit bei der Abfrageausführung verbessert wird.

GPU_CAGRA in Milvus: Was ist anders?

Während GPUs große Leistungsvorteile für die Graphenkonstruktion bieten, stehen Produktionsumgebungen vor einer praktischen Herausforderung: GPU-Ressourcen sind viel teurer und begrenzter als CPUs. Wenn sowohl die Indexerstellung als auch die Abfrageausführung ausschließlich von GPUs abhängen, treten schnell mehrere betriebliche Probleme auf:

• Geringe Ressourcenauslastung: Der Abfrageverkehr ist oft unregelmäßig und stoßweise, so dass die GPUs über lange Zeiträume ungenutzt bleiben und teure Rechenkapazität vergeuden.

• Hohe Bereitstellungskosten: Die Zuweisung eines Grafikprozessors für jede Abfrageinstanz treibt die Hardwarekosten in die Höhe, obwohl die meisten Abfragen die Leistung des Grafikprozessors nicht voll ausschöpfen.

• Begrenzte Skalierbarkeit: Die Anzahl der verfügbaren GPUs begrenzt direkt die Anzahl der Service-Replikate, die Sie ausführen können, und schränkt damit Ihre Fähigkeit ein, mit der Nachfrage zu skalieren.

• Geringere Flexibilität: Wenn sowohl die Indexerstellung als auch die Abfragen von GPUs abhängen, ist das System an die GPU-Verfügbarkeit gebunden und kann Arbeitslasten nicht einfach auf CPUs verlagern.

Um diesen Einschränkungen zu begegnen, führt Milvus 2.6.1 einen flexiblen Bereitstellungsmodus für den GPU_CAGRA-Index über den Parameter adapt_for_cpu ein. Dieser Modus ermöglicht einen hybriden Arbeitsablauf: CAGRA verwendet die GPU, um einen hochwertigen Graph-Index zu erstellen, während die Ausführung der Abfrage auf der CPU erfolgt - typischerweise mit HNSW als Suchalgorithmus.

In diesem Setup werden GPUs dort eingesetzt, wo sie den größten Nutzen bringen - bei der schnellen, hochpräzisen Indexerstellung -, während CPUs große Abfrage-Workloads weitaus kostengünstiger und skalierbarer bewältigen.

Daher ist dieser hybride Ansatz besonders gut für Arbeitslasten geeignet, bei denen:

• Datenaktualisierungen sind selten, so dass der Index nur selten neu aufgebaut werden muss

• das Abfragevolumen hoch ist und viele kostengünstige Replikate benötigt werden

• die Kostensensibilität hoch ist und die GPU-Nutzung streng kontrolliert werden muss

Verständnis von adapt_for_cpu

In Milvus steuert der Parameter adapt_for_cpu, wie ein CAGRA-Index während der Indexerstellung auf die Festplatte serialisiert und wie er zur Ladezeit in den Speicher deserialisiert wird. Durch Ändern dieser Einstellung zur Erstellungszeit und zur Ladezeit kann Milvus flexibel zwischen GPU-basierter Indexerstellung und CPU-basierter Abfrageausführung wechseln.

Unterschiedliche Kombinationen von adapt_for_cpu zur Erstellungs- und Ladezeit führen zu vier Ausführungsmodi, die jeweils für ein bestimmtes Einsatzszenario konzipiert sind.

Erstellungszeit (adapt_for_cpu)	Ladezeit (adapt_for_cpu)	Ausführungslogik	Empfohlenes Szenario
wahr	wahr	Erstellung mit GPU_CAGRA → Serialisierung als HNSW → Deserialisierung als HNSW → CPU-Abfrage	Kostensensitive Workloads; Abfragen in großem Umfang
wahr	falsch	Erstellen mit GPU_CAGRA → Serialisieren als HNSW → Deserialisieren als HNSW → CPU-Abfragen	Nachfolgende Abfragen werden an die CPU zurückgegeben, wenn die Parameter nicht übereinstimmen
falsch	true	Erstellen mit GPU_CAGRA → Serialisieren als CAGRA → Deserialisieren als HNSW → CPU-Abfragen	Beibehaltung des ursprünglichen CAGRA-Index für die Speicherung bei gleichzeitiger Aktivierung einer temporären CPU-Suche
falsch	false	Erstellen mit GPU_CAGRA → Serialisieren als CAGRA → Deserialisieren als CAGRA → GPU-Abfragen	Leistungskritische Workloads, bei denen die Kosten zweitrangig sind

Hinweis: Der Mechanismus adapt_for_cpu unterstützt nur eine einseitige Konvertierung. Ein CAGRA-Index kann in einen HNSW-Index konvertiert werden, da die CAGRA-Graphenstruktur alle Nachbarschaftsbeziehungen beibehält, die HNSW benötigt. Ein HNSW-Index kann jedoch nicht zurück nach CAGRA konvertiert werden, da ihm die zusätzlichen Strukturinformationen fehlen, die für GPU-basierte Abfragen benötigt werden. Daher sollten die Einstellungen für die Erstellungszeit sorgfältig ausgewählt werden, wobei die langfristige Bereitstellung und die Abfrageanforderungen zu berücksichtigen sind.

GPU_CAGRA auf dem Prüfstand

Zur Bewertung der Effektivität des hybriden Ausführungsmodells - Verwendung von GPUs für die Indexerstellung und CPUs für die Abfrageausführung - haben wir eine Reihe von kontrollierten Experimenten in einer standardisierten Umgebung durchgeführt. Die Bewertung konzentriert sich auf drei Dimensionen: Indexaufbauleistung, Abfrageleistung und Abrufgenauigkeit.

Versuchsaufbau

Die Experimente wurden auf weit verbreiteter, branchenüblicher Hardware durchgeführt, um sicherzustellen, dass die Ergebnisse zuverlässig und allgemein anwendbar sind.

• CPU: MD EPYC 7R13-Prozessor (16 CPUs)

• GPU: NVIDIA L4

1. Leistung des Indexaufbaus

Wir vergleichen CAGRA, das auf dem Grafikprozessor erstellt wurde, mit HNSW, das auf der CPU erstellt wurde, mit demselben Zielgraphengrad von 64.

Wichtigste Ergebnisse

• GPU CAGRA baut Indizes 12-15x schneller auf als CPU HNSW. Sowohl bei Cohere1M als auch bei Gist1M übertrifft GPU-basiertes CAGRA das CPU-basierte HNSW deutlich, was die Effizienz der GPU-Parallelität während der Graphenerstellung unterstreicht.

• Die Erstellungszeit steigt linear mit den NN-Descent-Iterationen. Mit steigender Iterationszahl wächst die Erstellungszeit nahezu linear, was die iterative Verfeinerung des NN-Descent widerspiegelt und einen vorhersehbaren Kompromiss zwischen Erstellungskosten und Graphenqualität bietet.

2. Abfrageleistung

In diesem Experiment wird der CAGRA-Graph einmal auf der GPU erstellt und dann über zwei verschiedene Ausführungspfade abgefragt:

• CPU-Abfrage: Der Index wird in das HNSW-Format deserialisiert und auf der CPU durchsucht.

• GPU-Abfrage: Die Suche läuft direkt auf dem CAGRA-Graphen unter Verwendung eines GPU-basierten Traversals

Wichtigste Ergebnisse

• Der Durchsatz der GPU-Suche ist 5-6x höher als der der CPU-Suche. Sowohl bei Cohere1M als auch bei Gist1M liefert das GPU-basierte Traversal wesentlich höhere QPS, was die Effizienz der parallelen Graphnavigation auf GPUs unterstreicht.

• Der Wiedererkennungswert steigt mit den NN-Descent-Iterationen und erreicht dann ein Plateau. Mit zunehmender Anzahl der Build-Iterationen verbessert sich die Wiederauffindung sowohl bei CPU- als auch bei GPU-Abfragen. Über einen bestimmten Punkt hinaus führen zusätzliche Iterationen jedoch zu abnehmenden Gewinnen, was darauf hindeutet, dass die Qualität des Graphen weitgehend konvergiert hat.

3. Abrufgenauigkeit

In diesem Experiment werden sowohl CAGRA als auch HNSW auf der CPU abgefragt, um die Auffindbarkeit unter identischen Abfragebedingungen zu vergleichen.

Wichtigste Ergebnisse

CAGRA erreicht bei beiden Datensätzen eine höhere Wiederauffindbarkeit als HNSW. Dies zeigt, dass die Qualität des Graphen auch dann gut erhalten bleibt, wenn ein CAGRA-Index auf der GPU erstellt und für die CPU-Suche deserialisiert wird.

Was kommt als Nächstes? Skalierung der Indexerstellung mit Vamana

Der hybride GPU-CPU-Ansatz von Milvus bietet eine praktische und kosteneffiziente Lösung für die heutigen umfangreichen Vektorsuch-Workloads. Durch die Erstellung qualitativ hochwertiger CAGRA-Graphen auf GPUs und die Bereitstellung von Abfragen auf CPUs wird eine schnelle Indexerstellung mit einer skalierbaren, kostengünstigen Abfrageausführung kombiniert - besondersgeeignet für Arbeitslasten mit seltenen Aktualisierungen, hohem Abfragevolumen und strengen Kostenbeschränkungen.

Bei noch größeren Skalen - zehnoder hundert Milliarden Vektoren -wird dieIndexerstellungselbst zum Engpass. Wenn der gesamte Datensatz nicht mehr in den GPU-Speicher passt, wendet sich die Branche in der Regel einfügungsbasierten Graphkonstruktionsmethoden wie Vamana zu. Anstatt den Graphen auf einmal zu erstellen, verarbeitet Vamana die Daten stapelweise und fügt schrittweise neue Vektoren ein, während die globale Konnektivität erhalten bleibt.

Die Konstruktionspipeline folgt drei Schlüsselphasen:

1. Geometrisches Batch-Wachstum - beginnend mit kleinen Batches zur Bildung eines Skelettgraphen, dann Erhöhung der Batch-Größe zur Maximierung der Parallelität und schließlich Verwendung großer Batches zur Verfeinerung von Details.

2. Greedy Insertion - jeder neue Knoten wird durch Navigation von einem zentralen Einstiegspunkt aus eingefügt, wobei seine Nachbarn iterativ verfeinert werden.

3. Rückwärts gerichtete Kantenaktualisierungen - Hinzufügen von Rückwärtsverbindungen, um die Symmetrie zu erhalten und eine effiziente Graphnavigation zu gewährleisten.

Das Pruning wird direkt in den Konstruktionsprozess integriert, indem das α-RNG-Kriterium verwendet wird: Wenn ein Nachbarschaftskandidat v bereits von einem bestehenden Nachbarn p′ abgedeckt wird (d.h. d(p′, v) < α × d(p, v)), wird v beschnitten. Der Parameter α ermöglicht eine genaue Kontrolle über die Sparsamkeit und Genauigkeit. Die GPU-Beschleunigung wird durch In-Batch-Parallelität und geometrische Batch-Skalierung erreicht, wodurch ein Gleichgewicht zwischen Indexqualität und Durchsatz erreicht wird.

Zusammen ermöglichen diese Techniken den Teams, ein schnelles Datenwachstum und umfangreiche Indexaktualisierungen zu bewältigen, ohne an die Grenzen des GPU-Speichers zu stoßen.

Das Milvus-Team arbeitet aktiv an der Vamana-Unterstützung und plant eine Veröffentlichung in der ersten Hälfte des Jahres 2026. Bleiben Sie dran.

Haben Sie Fragen oder möchten Sie eine Funktion des neuesten Milvus näher kennenlernen? Treten Sie unserem Discord-Kanal bei oder melden Sie Probleme auf GitHub. Sie können auch eine 20-minütige Einzelsitzung buchen, um Einblicke, Anleitung und Antworten auf Ihre Fragen über die Milvus Office Hours zu erhalten.

Erfahren Sie mehr über die Funktionen von Milvus 2.6

• Einführung in Milvus 2.6: Erschwingliche Vektorsuche im Milliardenmaßstab

• Einführung in die Einbettungsfunktion: Wie Milvus 2.6 die Vektorisierung und semantische Suche rationalisiert

• JSON Shredding in Milvus: 88,9x schnellere JSON-Filterung mit Flexibilität

• Echte Suche auf Entity-Ebene ermöglichen: Neue Array-of-Structs und MAX_SIM-Fähigkeiten in Milvus

• MinHash LSH in Milvus: Die Geheimwaffe zur Bekämpfung von Duplikaten in LLM-Trainingsdaten

• Vektorkomprimierung auf die Spitze getrieben: Wie Milvus mit RaBitQ 3× mehr Abfragen bedient

• Benchmarks lügen - Vektor-DBs verdienen einen echten Test

• Wir haben Kafka/Pulsar durch einen Woodpecker für Milvus ersetzt