Ottimizzazione di NVIDIA CAGRA in Milvus: un approccio ibrido GPU-CPU per un'indicizzazione più rapida e query meno costose

Man mano che i sistemi di intelligenza artificiale passano dagli esperimenti alle infrastrutture di produzione, i database vettoriali non hanno più a che fare con milioni di incorporazioni. Miliardi sono ormai una routine e decine di miliardi sono sempre più comuni. Su questa scala, le scelte algoritmiche non solo influenzano le prestazioni e il richiamo, ma si traducono direttamente nel costo dell'infrastruttura.

Questo porta a una domanda fondamentale per le implementazioni su larga scala: come scegliere l'indice giusto per garantire un richiamo e una latenza accettabili senza che l'utilizzo delle risorse di calcolo vada fuori controllo?

Gli indici basati su grafici come NSW, HNSW, CAGRA e Vamana sono diventati la risposta più diffusa. Navigando in grafi di vicinato precostituiti, questi indici consentono una rapida ricerca del vicinato più vicino su scala miliardaria, evitando la scansione bruta e il confronto di ogni vettore con la query.

Tuttavia, il profilo dei costi di questo approccio non è uniforme. Interrogare un grafo è relativamente economico, ma non lo è costruirlo. La costruzione di un grafo di alta qualità richiede calcoli di distanza su larga scala e un affinamento iterativo sull'intero set di dati, carichi che le risorse CPU tradizionali faticano a gestire in modo efficiente con la crescita dei dati.

NVIDIA CAGRA affronta questo collo di bottiglia utilizzando le GPU per accelerare la costruzione dei grafi grazie a un parallelismo massiccio. Se da un lato questo riduce in modo significativo i tempi di creazione, dall'altro l'affidamento alle GPU sia per la costruzione degli indici che per l'esecuzione delle query introduce costi più elevati e vincoli di scalabilità negli ambienti di produzione.

Per bilanciare questi compromessi, Milvus 2.6.1 adotta un design ibrido per gli indici GPU_CAGRA: Le GPU vengono utilizzate solo per la costruzione dei grafi, mentre l'esecuzione delle query viene eseguita dalle CPU. Questa soluzione preserva i vantaggi qualitativi dei grafi costruiti dalle GPU, pur mantenendo il servizio di query scalabile ed efficiente dal punto di vista dei costi, il che la rende particolarmente adatta ai carichi di lavoro con aggiornamenti dei dati poco frequenti, grandi volumi di query e una forte sensibilità ai costi.

Cos'è CAGRA e come funziona?

Gli indici vettoriali basati su grafi rientrano generalmente in due categorie principali:

• Costruzione iterativa del grafo, rappresentata da CAGRA (già supportato in Milvus).

• Costruzione del grafo basata sull'inserimento, rappresentata da Vamana (attualmente in fase di sviluppo in Milvus).

Questi due approcci differiscono in modo significativo nei loro obiettivi di progettazione e nelle loro basi tecniche, rendendo ciascuno di essi adatto a diverse scale di dati e modelli di carico di lavoro.

NVIDIA CAGRA (CUDA ANN Graph-based) è un algoritmo nativo per GPU per la ricerca approssimata dei vicini (ANN), progettato per costruire e interrogare in modo efficiente grafi di prossimità su larga scala. Sfruttando il parallelismo delle GPU, CAGRA accelera significativamente la costruzione dei grafi e offre prestazioni di interrogazione ad alto rendimento rispetto agli approcci basati su CPU come HNSW.

CAGRA si basa sull'algoritmo NN-Descent (Nearest Neighbor Descent), che costruisce un grafo k-nearest-neighbor (kNN) attraverso un affinamento iterativo. In ogni iterazione, i candidati vicini vengono valutati e aggiornati, convergendo gradualmente verso relazioni di vicinato di qualità superiore in tutto il set di dati.

Dopo ogni ciclo di affinamento, CAGRA applica ulteriori tecniche di potatura del grafo, come la potatura delle deviazioni a 2 hop, perrimuovere i bordi ridondanti e preservare la qualità della ricerca. Questa combinazione di affinamento e potatura iterativa produce un grafo compatto ma ben connesso, efficiente da attraversare al momento dell'interrogazione.

Grazie a ripetuti affinamenti e potature, CAGRA produce una struttura a grafo che supporta un elevato richiamo e una ricerca nearest-neighbor a bassa latenza su larga scala, rendendola particolarmente adatta a dataset statici o aggiornati di rado.

Fase 1: costruzione del grafo iniziale con NN-Descent

NN-Descent si basa su una semplice ma potente osservazione: se il nodo u è un vicino di v e il nodo w è un vicino di u, allora è molto probabile che anche w sia un vicino di v. Questa proprietà transitiva permette all'algoritmo di costruire il grafico iniziale con NN-Descent. Questa proprietà transitiva permette all'algoritmo di scoprire in modo efficiente i veri vicini, senza confrontare in modo esaustivo ogni coppia di vettori.

CAGRA utilizza l'NN-Descent come algoritmo di base per la costruzione dei grafi. Il processo funziona come segue:

1. Inizializzazione casuale: Ogni nodo inizia con un piccolo insieme di vicini selezionati a caso, formando un grafo iniziale approssimativo.

2. Espansione dei vicini: In ogni iterazione, un nodo raccoglie i suoi vicini attuali e i loro vicini per formare un elenco di candidati. L'algoritmo calcola le somiglianze tra il nodo e tutti i candidati. Poiché l'elenco dei candidati di ciascun nodo è indipendente, questi calcoli possono essere assegnati a blocchi di thread GPU separati ed eseguiti in parallelo su scala massiva.

3. Aggiornamento dell'elenco dei candidati: se l'algoritmo trova candidati più vicini degli attuali vicini del nodo, scambia i vicini più lontani e aggiorna l'elenco kNN del nodo. Nel corso di più iterazioni, questo processo produce un grafo kNN approssimativo di qualità molto più elevata.

4. Controllo della convergenza: Con l'avanzare delle iterazioni, si verifica un minor numero di aggiornamenti dei vicini. Quando il numero di connessioni aggiornate scende al di sotto di una soglia stabilita, l'algoritmo si ferma, indicando che il grafo si è effettivamente stabilizzato.

Poiché l'espansione dei vicini e il calcolo della similarità per i diversi nodi sono completamente indipendenti, CAGRA mappa il carico di lavoro di NN-Descent di ciascun nodo su un blocco di thread GPU dedicato. Questo design consente un parallelismo massiccio e rende la costruzione del grafo più veloce di ordini di grandezza rispetto ai metodi tradizionali basati sulla CPU.

Fase 2: potatura del grafo con deviazioni a 2 hop

Al termine di NN-Descent, il grafo risultante è accurato ma eccessivamente denso. NN-Descent mantiene intenzionalmente altri candidati vicini e la fase di inizializzazione casuale introduce molti bordi deboli o irrilevanti. Di conseguenza, ogni nodo finisce spesso per avere un grado due volte, o anche più volte, superiore a quello desiderato.

Per produrre un grafo compatto ed efficiente, CAGRA applica la potatura delle deviazioni a 2 hop.

L'idea è semplice: se il nodo A può raggiungere il nodo B indirettamente attraverso un vicino condiviso C (formando un percorso A → C → B), e la distanza di questo percorso indiretto è paragonabile alla distanza diretta tra A e B, allora il bordo diretto A → B è considerato ridondante e può essere rimosso.

Un vantaggio fondamentale di questa strategia di potatura è che la verifica della ridondanza di ogni bordo dipende solo da informazioni locali: le distanze tra i due punti finali e i loro vicini condivisi. Poiché ogni bordo può essere valutato in modo indipendente, la fase di potatura è altamente parallelizzabile e si adatta naturalmente all'esecuzione batch su GPU.

Di conseguenza, CAGRA è in grado di sfoltire il grafo in modo efficiente sulle GPU, riducendo l'overhead di memorizzazione del 40-50%, preservando l'accuratezza della ricerca e migliorando la velocità di attraversamento durante l'esecuzione delle query.

GPU_CAGRA in Milvus: cosa c'è di diverso?

Sebbene le GPU offrano grandi vantaggi in termini di prestazioni per la costruzione di grafi, gli ambienti di produzione devono affrontare una sfida pratica: Le risorse delle GPU sono molto più costose e limitate rispetto alle CPU. Se la costruzione degli indici e l'esecuzione delle query dipendono esclusivamente dalle GPU, emergono rapidamente diversi problemi operativi:

• Basso utilizzo delle risorse: Il traffico di query è spesso irregolare e discontinuo, lasciando le GPU inattive per lunghi periodi e sprecando la costosa capacità di calcolo.

• Elevati costi di implementazione: L'assegnazione di una GPU a ogni istanza di query fa lievitare i costi dell'hardware, anche se la maggior parte delle query non utilizza appieno le prestazioni della GPU.

• Scalabilità limitata: Il numero di GPU disponibili influisce direttamente sul numero di repliche del servizio che è possibile eseguire, limitando la capacità di scalare in base alla domanda.

• Flessibilità ridotta: Quando sia la creazione di indici che l'esecuzione di query dipendono dalle GPU, il sistema diventa vincolato alla disponibilità delle GPU e non può facilmente spostare i carichi di lavoro sulle CPU.

Per risolvere questi vincoli, Milvus 2.6.1 introduce una modalità di implementazione flessibile per l'indice GPU_CAGRA attraverso il parametro adapt_for_cpu. Questa modalità consente un flusso di lavoro ibrido: CAGRA utilizza la GPU per costruire un indice di grafi di alta qualità, mentre l'esecuzione delle query viene eseguita dalla CPU, tipicamente utilizzando HNSW come algoritmo di ricerca.

In questa configurazione, le GPU vengono utilizzate dove offrono il massimo valore - costruzione di indici veloci e di alta precisione - mentre le CPU gestiscono carichi di lavoro di query su larga scala in modo molto più economico e scalabile.

Di conseguenza, questo approccio ibrido è particolarmente adatto per i carichi di lavoro in cui:

• Gli aggiornamenti dei dati sono poco frequenti, quindi le ricostruzioni degli indici sono rare.

• Il volume delle query è elevato e richiede molte repliche poco costose.

• La sensibilità ai costi è elevata e l'uso delle GPU deve essere strettamente controllato.

Comprensione adapt_for_cpu

In Milvus, il parametro adapt_for_cpu controlla il modo in cui un indice CAGRA viene serializzato su disco durante la creazione dell'indice e come viene deserializzato in memoria al momento del caricamento. Modificando questa impostazione al momento della creazione e del caricamento, Milvus può passare in modo flessibile dalla costruzione dell'indice basata sulla GPU all'esecuzione della query basata sulla CPU.

Diverse combinazioni di adapt_for_cpu in fase di compilazione e di caricamento danno luogo a quattro modalità di esecuzione, ciascuna progettata per uno specifico scenario operativo.

Tempo di creazione (adapt_for_cpu)	Tempo di caricamento (adapt_for_cpu)	Logica di esecuzione	Scenario consigliato
vero	vero	Costruire con GPU_CAGRA → serializzare come HNSW → deserializzare come HNSW → interrogare la CPU	Carichi di lavoro sensibili ai costi; servizio di query su larga scala
vero	falso	Costruire con GPU_CAGRA → serializzare come HNSW → deserializzare come HNSW → interrogazione CPU	Le query successive passano alla CPU in caso di mancata corrispondenza dei parametri
falso	vero	Creazione con GPU_CAGRA → serializzazione come CAGRA → deserializzazione come HNSW → interrogazione CPU	Mantenimento dell'indice CAGRA originale per la memorizzazione e abilitazione di una ricerca temporanea da parte della CPU
falso	falso	Creare con GPU_CAGRA → serializzare come CAGRA → deserializzare come CAGRA → interrogazione GPU	Carichi di lavoro critici per le prestazioni in cui il costo è secondario

Nota: il meccanismo adapt_for_cpu supporta solo la conversione unidirezionale. Un indice CAGRA può essere convertito in HNSW perché la struttura del grafo CAGRA conserva tutte le relazioni di vicinato di cui HNSW ha bisogno. Tuttavia, un indice HNSW non può essere riconvertito in CAGRA, poiché manca delle informazioni strutturali aggiuntive necessarie per l'interrogazione basata su GPU. Di conseguenza, le impostazioni del tempo di compilazione devono essere scelte con attenzione, tenendo conto dei requisiti di distribuzione e interrogazione a lungo termine.

Mettere GPU_CAGRA alla prova

Per valutare l'efficacia del modello di esecuzione ibrido - che utilizza le GPU per la costruzione degli indici e le CPU per l'esecuzione delle query - abbiamo condotto una serie di esperimenti controllati in un ambiente standardizzato. La valutazione si concentra su tre dimensioni: prestazioni di costruzione dell'indice, prestazioni delle query e precisione di richiamo.

Setup sperimentale

Gli esperimenti sono stati eseguiti su hardware ampiamente adottato e standard del settore per garantire che i risultati rimangano affidabili e ampiamente applicabili.

• CPU: Processore MD EPYC 7R13 (16 cpu)

• GPU: NVIDIA L4

1. Prestazioni della costruzione dell'indice

Confrontiamo CAGRA costruito sulla GPU con HNSW costruito sulla CPU, con lo stesso grado di grafo target di 64.

Risultati principali

• CAGRA su GPU costruisce indici 12-15 volte più velocemente di HNSW su CPU. Sia su Cohere1M che su Gist1M, CAGRA basato su GPU supera significativamente HNSW basato su CPU, evidenziando l'efficienza del parallelismo GPU durante la costruzione del grafo.

• Il tempo di costruzione aumenta linearmente con le iterazioni di NN-Descent. All'aumentare del numero di iterazioni, il tempo di costruzione cresce in modo quasi lineare, riflettendo la natura di raffinamento iterativo di NN-Descent e fornendo un compromesso prevedibile tra costo di costruzione e qualità del grafo.

2. Prestazioni della query

In questo esperimento, il grafo CAGRA viene costruito una volta sulla GPU e poi interrogato utilizzando due diversi percorsi di esecuzione:

• Interrogazione su CPU: l'indice viene deserializzato in formato HNSW e ricercato sulla CPU.

• Interrogazione su GPU: la ricerca viene eseguita direttamente sul grafo CAGRA utilizzando una traversale basata su GPU.

Risultati principali

• Il throughput della ricerca su GPU è 5-6 volte superiore a quello della ricerca su CPU. Sia in Cohere1M che in Gist1M, l'attraversamento basato su GPU offre un QPS sostanzialmente superiore, evidenziando l'efficienza della navigazione parallela dei grafi su GPU.

• Il richiamo aumenta con le iterazioni di NN-Descent, per poi raggiungere un plateau. Con l'aumento del numero di iterazioni di costruzione, il richiamo migliora sia per le interrogazioni su CPU che su GPU. Tuttavia, oltre un certo punto, ulteriori iterazioni producono guadagni decrescenti, indicando che la qualità del grafo è ampiamente convergente.

3. Accuratezza del richiamo

In questo esperimento, sia CAGRA che HNSW sono stati interrogati sulla CPU per confrontare il richiamo in condizioni di interrogazione identiche.

Risultati principali

CAGRA ottiene un richiamo superiore a quello di HNSW su entrambi i set di dati, dimostrando che anche quando un indice CAGRA viene costruito sulla GPU e deserializzato per la ricerca sulla CPU, la qualità del grafo è ben conservata.

Il prossimo passo: Scalare la costruzione degli indici con Vamana

L'approccio ibrido GPU-CPU di Milvus offre una soluzione pratica e conveniente per gli attuali carichi di lavoro di ricerca vettoriale su larga scala. Costruendo grafi CAGRA di alta qualità sulle GPU e servendo le query sulle CPU, Milvus combina una rapida costruzione dell'indice con un'esecuzione delle query scalabile e conveniente, particolarmenteadatta a carichi di lavoro con aggiornamenti poco frequenti, volumi di query elevati e vincoli di costo stringenti.

Su scale ancora più grandi - decineo centinaia di miliardi di vettori - lacostruzionedell'indicestesso diventa il collo di bottiglia. Quando l'intero set di dati non può più essere inserito nella memoria della GPU, il settore si rivolge tipicamente a metodi di costruzione del grafo basati su inserti, come Vamana. Invece di costruire il grafo tutto in una volta, Vamana elabora i dati in batch, inserendo in modo incrementale nuovi vettori e mantenendo la connettività globale.

La sua pipeline di costruzione segue tre fasi fondamentali:

1. Crescita geometrica dei lotti: si inizia con piccoli lotti per formare un grafo scheletrico, poi si aumentano le dimensioni dei lotti per massimizzare il parallelismo e infine si usano grandi lotti per perfezionare i dettagli.

2. Inserimento avido - ogni nuovo nodo viene inserito navigando da un punto di ingresso centrale, affinando iterativamente il suo insieme di vicini.

3. Aggiornamenti dei bordi all'indietro - aggiunta di connessioni inverse per preservare la simmetria e garantire una navigazione efficiente del grafo.

La potatura è integrata direttamente nel processo di costruzione utilizzando il criterio α-RNG: se un candidato vicino v è già coperto da un vicino esistente p′ (cioè, d(p′, v) < α × d(p, v)), allora v viene potato. Il parametro α consente un controllo preciso della spazialità e dell'accuratezza. L'accelerazione su GPU è ottenuta attraverso il parallelismo in-batch e il batch scaling geometrico, trovando un equilibrio tra qualità dell'indice e throughput.

Insieme, queste tecniche consentono ai team di gestire la rapida crescita dei dati e gli aggiornamenti degli indici su larga scala senza incorrere in limiti di memoria della GPU.

Il team di Milvus sta sviluppando attivamente il supporto per Vamana, con un rilascio previsto per la prima metà del 2026. Restate sintonizzati.

Avete domande o volete un approfondimento su una qualsiasi funzionalità dell'ultima versione di Milvus? Unitevi al nostro canale Discord o inviate problemi su GitHub. È anche possibile prenotare una sessione individuale di 20 minuti per ottenere approfondimenti, indicazioni e risposte alle vostre domande tramite Milvus Office Hours.

Per saperne di più sulle caratteristiche di Milvus 2.6

• Presentazione di Milvus 2.6: ricerca vettoriale accessibile su scala miliardaria

• Introduzione alla funzione Embedding: Come Milvus 2.6 semplifica la vettorializzazione e la ricerca semantica

• Triturazione JSON in Milvus: filtraggio JSON 88,9 volte più veloce e flessibile

• Il vero recupero a livello di entità: Nuove funzionalità Array-of-Structs e MAX_SIM in Milvus

• MinHash LSH in Milvus: l'arma segreta per combattere i duplicati nei dati di addestramento LLM

• Portare la compressione vettoriale all'estremo: come Milvus serve 3 volte di più le query con RaBitQ

• I benchmark mentono: i DB vettoriali meritano un test reale

• Abbiamo sostituito Kafka/Pulsar con un Picchio per Milvus