DISKANN

In scenari di grandi dimensioni, in cui i set di dati possono includere miliardi o addirittura trilioni di vettori, i metodi standard di indicizzazione in memoria (ad esempio, HNSW, IVF_FLAT) spesso non riescono a tenere il passo a causa dei limiti di memoria. DISKANN offre un approccio basato su disco che affronta queste sfide mantenendo un'elevata precisione e velocità di ricerca quando le dimensioni del set di dati superano la RAM disponibile.

Panoramica

DISKANN combina due tecniche chiave per una ricerca vettoriale efficiente:

• Vamana Graph - Un indice basato su disco e su grafo che collega i punti di dati (o vettori) per una navigazione efficiente durante la ricerca.

• Quantizzazione del prodotto (PQ) - Un metodo di compressione in memoria che riduce le dimensioni dei vettori, consentendo un rapido calcolo approssimativo della distanza tra i vettori.

Costruzione dell'indice

Grafo di Vamana

Il grafo Vamana è il fulcro della strategia basata su disco di DISKANN. Può gestire insiemi di dati molto grandi perché non ha bisogno di risiedere completamente in memoria durante o dopo la costruzione.

La figura seguente mostra come viene costruito un grafo Vamana.

Diskann

1. Connessioni iniziali casuali: Ogni punto di dati (vettore) è rappresentato come un nodo del grafo. Questi nodi sono inizialmente collegati in modo casuale, formando una rete densa. In genere, un nodo inizia con circa 500 bordi (o connessioni) per un'ampia connettività.

2. Raffinamento per l'efficienza: Il grafo casuale iniziale viene sottoposto a un processo di ottimizzazione per renderlo più efficiente per la ricerca. Ciò comporta due fasi fondamentali:

   • Potatura degli spigoli ridondanti: L'algoritmo scarta le connessioni non necessarie in base alle distanze tra i nodi. Questo passaggio dà priorità ai bordi di qualità superiore.

     Il parametro max_degree limita il numero massimo di bordi per nodo. Un valore più alto di max_degree si traduce in un grafo più denso, che potenzialmente può trovare più vicini rilevanti (maggiore richiamo), ma anche aumentare l'uso della memoria e il tempo di ricerca.

   • Aggiunta di scorciatoie strategiche: Vamana introduce bordi a lungo raggio, che collegano punti di dati molto distanti tra loro nello spazio vettoriale. Queste scorciatoie consentono alle ricerche di saltare rapidamente attraverso il grafo, aggirando i nodi intermedi e accelerando notevolmente la navigazione.

     Il parametro search_list_size determina l'ampiezza del processo di raffinamento del grafo. Un valore più alto di search_list_size estende la ricerca dei vicini durante la costruzione e può migliorare l'accuratezza finale, ma aumenta il tempo di costruzione dell'indice.

Per saperne di più sulla regolazione dei parametri, consultare i parametri di DISKANN.

PQ

DISKANN utilizza PQ per comprimere vettori ad alta dimensione in rappresentazioni più piccole(codici PQ), che vengono memorizzate per un rapido calcolo delle distanze approssimate.

Il parametro pq_code_budget_gb_ratio gestisce l'ingombro della memoria dedicata alla memorizzazione di questi codici PQ. Rappresenta un rapporto tra la dimensione totale dei vettori (in gigabyte) e lo spazio allocato per la memorizzazione dei codici PQ. È possibile calcolare il budget effettivo dei codici PQ (in gigabyte) con questa formula:

PQ Code Budget (GB) = vec_field_size_gb * pq_code_budget_gb_ratio

dove:

• vec_field_size_gb è la dimensione totale dei vettori (in gigabyte).

• pq_code_budget_gb_ratio è un rapporto definito dall'utente, che rappresenta la frazione della dimensione totale dei dati riservata ai codici PQ. Questo parametro consente di trovare un compromesso tra la precisione della ricerca e le risorse di memoria. Per ulteriori informazioni sulla regolazione dei parametri, consultare le configurazioni DISKANN.

Per i dettagli tecnici sul metodo PQ sottostante, consultare IVF_PQ.

Processo di ricerca

Una volta costruito l'indice (il grafico Vamana su disco e i codici PQ in memoria), DISKANN esegue le ricerche di RNA come segue:

Diskann 2

1. Query e punto di ingresso: Viene fornito un vettore di query per individuare i suoi vicini più prossimi. DISKANN parte da un punto di ingresso selezionato nel grafo di Vamana, spesso un nodo vicino al centroide globale del dataset. Il centroide globale rappresenta la media di tutti i vettori e aiuta a minimizzare la distanza di attraversamento del grafo per trovare i vicini desiderati.

2. Esplorazione dei vicini: L'algoritmo raccoglie i potenziali vicini candidati (cerchi in rosso nella figura) dai bordi del nodo corrente, sfruttando i codici PQ in memoria per approssimare le distanze tra questi candidati e il vettore di interrogazione. Questi potenziali vicini candidati sono i nodi direttamente connessi al punto di ingresso selezionato attraverso i bordi del grafo di Vamana.

3. Selezione dei nodi per il calcolo accurato della distanza: Dai risultati approssimativi, un sottoinsieme dei vicini più promettenti (cerchi in verde nella figura) viene selezionato per una valutazione precisa della distanza utilizzando i loro vettori originali non compressi. Ciò richiede la lettura dei dati dal disco, che può richiedere molto tempo. DISKANN utilizza due parametri per controllare questo delicato equilibrio tra precisione e velocità:

   • beam_width_ratio: Una razione che controlla l'ampiezza della ricerca, determinando quanti candidati vicini vengono selezionati in parallelo per esplorare i loro vicini. Una beam_width_ratio più grande comporta un'esplorazione più ampia, che potenzialmente porta a una maggiore accuratezza, ma aumenta anche il costo computazionale e l'I/O su disco. L'ampiezza del fascio, o il numero di nodi selezionati, è determinata dalla formula: Beam width = Number of CPU cores * beam_width_ratio.

   • search_cache_budget_gb_ratio: La percentuale di memoria allocata per la cache dei dati del disco a cui si accede di frequente. La cache aiuta a ridurre al minimo l'I/O su disco, rendendo le ricerche ripetute più veloci perché i dati sono già in memoria.

   Per saperne di più sulla regolazione dei parametri, consultare le configurazioni di DISKANN.

4. Esplorazione iterativa: La ricerca affina iterativamente l'insieme dei candidati, eseguendo ripetutamente valutazioni approssimative (usando PQ) seguite da controlli precisi (usando i vettori originali dal disco) finché non viene trovato un numero sufficiente di vicini.

Abilitare DISKANN in Milvus

Per impostazione predefinita, DISKANN è disattivato in Milvus per privilegiare la velocità degli indici in memoria per gli insiemi di dati che stanno comodamente nella RAM. Tuttavia, se si lavora con insiemi di dati enormi o si desidera sfruttare la scalabilità di DISKANN e l'ottimizzazione dell'SSD, è possibile attivarlo facilmente.

Ecco come abilitare DISKANN in Milvus:

1. Aggiornare il file di configurazione di Milvus

   1. Individuare il file di configurazione di Milvus. (Per maggiori dettagli su come trovare questo file, consultare la documentazione di Milvus sulla configurazione).

   2. Trovare il parametro queryNode.enableDisk e impostarne il valore su true:

       queryNode:
           enableDisk: true # Enables query nodes to load and search using the on-disk index
      

2. Ottimizzare l'archiviazione per DISKANN

Per garantire le migliori prestazioni con DISKANN, si consiglia di archiviare i dati Milvus su un'unità SSD NVMe veloce. Ecco come fare sia per Milvus Standalone che per il Cluster:

• Milvus Standalone

  • Montate la directory dei dati di Milvus su un'unità SSD NVMe all'interno del contenitore Milvus. È possibile farlo nel file docker-compose.yml o utilizzando altri strumenti di gestione del contenitore.

  • Ad esempio, se l'unità SSD NVMe è montata all'indirizzo /mnt/nvme, si aggiorna la sezione volumesdel file docker-compose.yml in questo modo:

   volumes:
        - /mnt/nvme/volumes/milvus:/var/lib/milvus
  

• Cluster Milvus

  • Montare la directory dei dati Milvus su un'unità SSD NVMe in entrambi i contenitori QueryNode e IndexNode. È possibile ottenere questo risultato attraverso la configurazione dell'orchestrazione dei container.

  • Montando i dati su un'unità SSD NVMe in entrambi i tipi di nodo, si garantisce una velocità di lettura e scrittura elevata per le operazioni di ricerca e indicizzazione.

Una volta apportate queste modifiche, riavviare l'istanza Milvus per rendere effettive le impostazioni. Ora Milvus sfrutterà le capacità di DISKANN per gestire grandi insiemi di dati, offrendo una ricerca vettoriale efficiente e scalabile.

Configurazione di DISKANN

I parametri relativi a DISKANN possono essere configurati solo tramite il file di configurazione di Milvus (milvus.yaml):

# milvus.yaml
common:
  DiskIndex:
    MaxDegree: 56  # Maximum degree of the Vamana graph
    SearchListSize: 100  # Size of the candidate list during building graph
    PQCodeBudgetGBRatio: 0.125  # Size limit on the PQ code (compared with raw data)
    SearchCacheBudgetGBRatio: 0.1 # Ratio of cached node numbers to raw data
    BeamWidthRatio: 4 # Ratio between the maximum number of IO requests per search iteration and CPU number

Per maggiori dettagli sulle descrizioni dei parametri, fare riferimento a DISKANN params.

Parametri DISKANN

La regolazione fine dei parametri di DISKANN consente di adattare il suo comportamento al dataset specifico e al carico di lavoro della ricerca, trovando il giusto equilibrio tra velocità, precisione e utilizzo della memoria.

Parametri di costruzione dell'indice

Questi parametri influenzano il modo in cui viene costruito l'indice DISKANN. La loro regolazione può influenzare le dimensioni dell'indice, il tempo di costruzione e la qualità della ricerca.

	Parametro	Descrizione	Valore Intervallo	Suggerimento per la messa a punto
Vamana	MaxDegree	Controlla il numero massimo di connessioni (bordi) che ogni punto di dati può avere nel grafico Vamana.	Tipo: Intero Intervallo: [1, 512] Valore predefinito: 56	Valori più alti creano grafici più densi, aumentando potenzialmente il richiamo (trovando risultati più rilevanti) ma anche l'utilizzo della memoria e il tempo di costruzione. Nella maggior parte dei casi, si consiglia di impostare un valore compreso in questo intervallo: [10, 100].
	SearchListSize	Durante la costruzione dell'indice, questo parametro definisce la dimensione del pool di candidati utilizzato per la ricerca dei vicini più prossimi per ogni nodo. Per ogni nodo aggiunto al grafo, l'algoritmo mantiene un elenco dei search_list_size migliori candidati trovati finora. La ricerca dei vicini si ferma quando questo elenco non può più essere migliorato. Da questa lista finale di candidati, i migliori max_degree nodi vengono selezionati per formare i bordi finali.	Tipo: Intero Intervallo: [1, int_max] Valore predefinito: 100	Un valore maggiore di search_list_size aumenta la probabilità di trovare i veri vicini per ogni nodo, il che può portare a un grafo di qualità superiore e a migliori prestazioni di ricerca (recall). Tuttavia, ciò comporta un tempo di creazione dell'indice significativamente più lungo. Deve essere sempre impostato a un valore maggiore o uguale a max_degree.
	SearchCacheBudgetGBRatio	Controlla la quantità di memoria allocata per la cache delle parti del grafo a cui si accede di frequente durante la costruzione dell'indice.	Tipo: Variabile Intervallo: [0.0, 0.3) Valore predefinito: 0.10	Un valore più alto alloca più memoria per la cache, riducendo significativamente l'I/O su disco ma consumando più memoria di sistema. Un valore inferiore utilizza meno memoria per la cache, aumentando potenzialmente la necessità di accesso al disco. Nella maggior parte dei casi, si consiglia di impostare un valore compreso in questo intervallo: [0.0, 0.3).
PQ	PQCodeBudgetGBRatio	Controlla la dimensione dei codici PQ (rappresentazioni compresse dei punti di dati) rispetto alla dimensione dei dati non compressi.	Tipo: Variabile Intervallo: (0,0, 0,25] Valore predefinito: 0.125	Un rapporto più alto porta a risultati di ricerca più accurati, allocando una percentuale maggiore di memoria per i codici PQ, memorizzando di fatto più informazioni sui vettori originali. Un rapporto più basso riduce l'uso della memoria, ma potenzialmente sacrifica l'accuratezza, poiché i codici PQ più piccoli conservano meno informazioni. Questo approccio è adatto a scenari in cui i vincoli di memoria sono un problema, consentendo potenzialmente l'indicizzazione di insiemi di dati più grandi. Nella maggior parte dei casi, si consiglia di impostare un valore all'interno di questo intervallo: (0,0625, 0,25].

Parametri di ricerca specifici per l'indice

Questi parametri influenzano il modo in cui DISKANN esegue le ricerche. La loro regolazione può influire sulla velocità di ricerca, sulla latenza e sull'utilizzo delle risorse.

	Parametro	Descrizione	Valore Intervallo	Suggerimento per la messa a punto
Vamana	BeamWidthRatio	Controlla il grado di parallelismo durante la ricerca, determinando il numero massimo di richieste di I/O su disco in parallelo rispetto al numero di core CPU disponibili.	Tipo: Variabile Intervallo: [1, max(128/numero di CPU, 16)]. Valore predefinito: 4.0	Valori più alti aumentano il parallelismo, accelerando la ricerca su sistemi con CPU e SSD potenti. Tuttavia, un valore troppo alto potrebbe causare un'eccessiva contestazione delle risorse. Nella maggior parte dei casi, si consiglia di impostare un valore compreso in questo intervallo: [1.0, 4.0].
	search_list	Durante un'operazione di ricerca, questo parametro determina la dimensione del pool di candidati che l'algoritmo mantiene durante l'attraversamento del grafo. Un valore maggiore aumenta le possibilità di trovare i veri vicini (richiamo più elevato), ma aumenta anche la latenza della ricerca.	Tipo: Intero Intervallo: [1, int_max] Valore predefinito: 100	Per un buon equilibrio tra prestazioni e accuratezza, si consiglia di impostare questo valore come uguale o leggermente superiore al numero di risultati che si desidera recuperare (top_k).