Redis, che botta di Vector!

Abbiamo i Vector Set

Nel mondo dell'Intelligenza Artificiale e del Machine Learning, la capacità di comprendere e ricercare dati basandosi sul loro significato semantico, piuttosto che su corrispondenze esatte di parole chiave, è diventata fondamentale. Questo è il regno dei Vector Database e degli algoritmi di Approximate Nearest Neighbor (ANN).

Recentemente, in Devmy, abbiamo avuto l'eccezionale opportunità di testare in anteprima Redis Vector Sets, un nuovo modulo Redis, in fase di ottimizzazione da parte del suo creatore, Salvatore Sanfilippo aka @antirez. Grazie alla sua disponibilità nel fornirci un binario preliminare per macOS, abbiamo potuto integrare questo nuovo modulo nel nostro sistema RAG (Retrieval-Augmented Generation), sostituendo la nostra soluzione precedente ChromaDB per un confronto diretto e pratico.

In questo articolo, condivideremo le nostre scoperte, partendo dai concetti generali dei vector database e dell'algoritmo HNSW, per poi immergerci nelle specifiche di Redis Vector Sets e raccontare la nostra esperienza.

Cosa sono i Vector Database e perché sono importanti?

Tradizionalmente, i database eccellono nel recuperare dati basati su query esatte o condizioni logiche su campi strutturati. Tuttavia, molte informazioni moderne (testo, immagini, audio) sono intrinsecamente non strutturate. Per gestirle, si utilizzano modelli di Machine Learning (spesso Deep Learning) per trasformare questi dati in vettori numerici ad alta dimensionalità, noti come embeddings. Questi vettori catturano l'essenza semantica del dato originale: dati semanticamente simili avranno vettori vicini nello spazio vettoriale.

Un Vector Database è un sistema progettato specificamente per memorizzare, indicizzare e interrogare efficientemente questi embeddings. L'obiettivo primario è trovare i vettori (e quindi i dati originali associati) più vicini a un dato vettore di query, secondo una metrica di distanza (come la cosine similarity o la distanza euclidea). Questo processo è noto come Nearest Neighbor (NN) search.

Le applicazioni sono vaste:

Sistemi di raccomandazione: trovare prodotti simili a quelli che un utente ha apprezzato.
Ricerca di immagini: trovare immagini simili a un'immagine data.
Elaborazione del linguaggio naturale: trovare documenti o frasi con significato simile.
Sistemi RAG: recuperare contesto pertinente da una base di conoscenza per migliorare le risposte di modelli linguistici generativi).

Algoritmi di Ricerca Vettoriale: il compromesso tra precisione e velocità

Trovare l'esatto vicino più prossimo (Exact Nearest Neighbor) in uno spazio ad alta dimensionalità è computazionalmente molto costoso, spesso richiedendo un confronto con ogni singolo vettore nel database. Per dataset di grandi dimensioni, questo è impraticabile.

Entrano in gioco gli algoritmi di Approximate Nearest Neighbor (ANN). Questi algoritmi sacrificano una piccola percentuale di precisione in cambio di un enorme guadagno in velocità di ricerca. Esistono diverse famiglie di algoritmi ANN, tra cui:

Tree-based: come Annoy, costruiscono alberi per partizionare lo spazio.
Hashing-based: come Locality-Sensitive Hashing (LSH), usano funzioni hash per raggruppare vettori vicini.
Graph-based: come HNSW (Hierarchical Navigable Small World), costruiscono grafi di prossimità multi-livello.

Come funziona HNSW

HNSW è uno degli algoritmi ANN basati su grafo più popolari e performanti, noto per il suo eccellente bilanciamento tra velocità di ricerca, qualità dei risultati (recall) e velocità di costruzione dell'indice. È l'algoritmo alla base di Redis Vector Sets.

L'idea consiste nel creare connessioni tra vettori in modo da consentire sia un rapido traversing globale del grafo sia una ricerca accurata di vettori simili.

Lo fa creando più livelli di vettori, dove ogni livello include un sottoinsieme dei vettori nel livello sottostante. Ciò significa che man mano che si sale di livello, trovare l'area generale corretta del grafo diventa più veloce.

E una volta trovata l'area generale, la ricerca diventa più locale, scendendo di livello, dove sono inclusi più vettori.

Alla fine, la ricerca raggiunge il livello inferiore, che include tutti i vettori disponibili. Qui, viene eseguita una ricerca più approfondita tra i vicini per affinare i risultati.

Questo metodo consente a una ricerca di trovare rapidamente l'area generale giusta del grafo prima di eseguire una ricerca completa del denso livello inferiore.

Intuitivamente, un grafo HNSW può essere considerato come una sorta di skip list multidimensionale, dove i livelli superiori sono usati per la ricerca globale, e i livelli inferiori sono usati per la ricerca locale. HNSW ha alcuni parametri chiave che influenzano le sue prestazioni e l'uso di memoria:

M: definisce il numero massimo di connessioni (vicini) che ogni nodo può avere per livello (ad eccezione del livello 0, che ne ha M*2). Un valore di M più alto crea un grafo più denso, potenzialmente migliorando la qualità della navigazione e la recall (la capacità di trovare i veri vicini più prossimi), ma aumenta significativamente l'uso di memoria, poiché ogni connessione è un puntatore, e il tempo di costruzione dell'indice. Il default in Redis Vector Sets è 16, un buon compromesso.
EF-Construction (Exploration Factor during Construction): controlla quanto “sforzo” viene fatto durante l'inserimento di un nuovo nodo per trovare i suoi migliori vicini a cui connettersi. Un valore più alto porta a un grafo di qualità migliore, migliore recall potenziale, ma rallenta significativamente l'inserimento. Il default in Redis Vector Sets è 200.
EF - Search (Exploration Factor during Search): controlla la dimensione della coda di candidati (la coda di candidati o lista dinamica si riferisce alla lista di nodi che vengono considerati dall'algoritmo) esplorati durante una ricerca. Un valore più alto aumenta la probabilità di trovare i vicini più prossimi, migliore recall, ma aumenta la latenza della query. È un parametro importante da regolare per bilanciare velocità e accuratezza in base all'applicazione.

Redis Vector Sets

Redis Vector Sets introduce un nuovo tipo di dato in Redis, chiamato proprio Vector Set, dove gli elementi stringa sono associati a un vettore. L'obiettivo è permettere l'inserimento di elementi vettoriali e il recupero efficiente dei sottoinsiemi più simili a un vettore di query o a un elemento già presente nel set. Basato su un'implementazione HNSW ottimizzata, offre le prestazioni tipiche di Redis.

Miglioramenti Chiave all'Implementazione HNSW

L'implementazione HNSW in Redis vector sets introduce alcune significative migliorie rispetto all'algoritmo standard, focalizzate in particolare sulla robustezza e la gestione dinamica dei dati. Una differenza fondamentale è che tutte le connessioni tra tutti i nodi del grafo sono bidirezionali: il nodo A è collegato al nodo B, ma anche B è collegato ad A.

Questa caratteristica abilita una delle funzionalità più distintive di Redis vector sets: la cancellazione reale dei nodi (VREM). A differenza di molte implementazioni che usano il tombstoning (marcare un nodo come cancellato per poi rimuoverlo in una fase separata di garbage collection), qui la rimozione è immediata e la memoria viene effettivamente liberata subito. Inoltre, quando un nodo viene cancellato, entra in gioco uno specifico algoritmo di riconciliazione (anch'esso un'estensione non presente nei vari paper) che ricollega i nodi vicini rimasti "orfani", preservando i criteri di qualità del grafo HNSW.

L'implicazione pratica per l'utente è notevole, si può trattare l'indice HNSW come una struttura dati veramente dinamica. È possibile aggiungere e rimuovere elementi liberamente, anche in grandi quantità, senza preoccuparsi di degradare le prestazioni o di dover gestire manualmente la pulizia della memoria. L'indice continua a funzionare correttamente e la memoria viene recuperata in modo trasparente. Questa capacità di gestire indici vettoriali altamente mutabili è un punto di forza specifico di questa implementazione.

Caratteristiche principali

Comandi Intuitivi: fornisce un set di comandi V* (VADD, VSIM, VREM, VEMB, VINFO, VSETATTR , etc.) che si integrano naturalmente con l'ecosistema Redis.
Quantizzazione: supporta la quantizzazione per ridurre drasticamente l'uso di memoria e accelerare i calcoli, con un impatto minimo (INT8) o moderato (BIN) sulla recall.
- NOQUANT: nessuna quantizzazione, vettori a 32 bit floating point. Massima precisione, massimo uso di memoria/CPU.
- Q8 (Default): quantizzazione a interi a 8 bit. Riduce la memoria di almeno 4 volte, riduce i tempi sia di inserimento che di ricerca (x2 o più), l’impatto sull’accuratezza (recall) è minimo. Di solito la scelta migliore.
- BIN: quantizzazione binaria (1 bit per componente). Migliora drasticamente la velocità, riduce la memoria di 32 volte rispetto al NOQUANT e quindi rispetto ai vettori in precisione completa (fp32), ma riduce l’accuratezza. Da valutare come scelta quando la velocità è prioritaria e la perdita di accuratezza è accettabile.
Filtered Search: permette di associare attributi JSON a ciascun elemento e di filtrare i risultati della ricerca vettoriale usando espressioni logico-matematiche semplici su questi attributi (es. .anno > 2020 and .genere == "fantascienza"). Questo combina la ricerca semantica con filtri scalari tradizionali nella stessa operazione. L'opzione FILTER-EF controlla quanto sforzo aggiuntivo dedicare alla ricerca quando molti elementi vengono scartati dal filtro.
Dimensionality Reduction (REDUCE): permette di ridurre la dimensionalità dei vettori tramite random projection durante l'inserimento. Utile per vettori molto grandi se una perdita di precisione è accettabile, riducendo memoria e CPU. Va testato attentamente per valutare l’eventuale impatto sulla recall.
Modello di Threading: le ricerche vengono eseguite di default in thread separati (fino a un massimo configurabile), permettendo a Redis di rimanere reattivo. Anche l'inserimento con VADD ... CAS può eseguire la parte computazionalmente onerosa della ricerca dei candidati come vicini in background mentre il comando è eseguito nel main thread.
Scalabilità Orizzontale (Sharding): è possibile partizionare un grande dataset su più istanze Redis (o chiavi sulla stessa istanza). Le query vengono eseguite su tutte le partizioni e i risultati uniti lato client. Questo scala linearmente le scritture e permette di gestire dataset più grandi della memoria di una singola istanza, anche se le letture richiedono query multiple.

Approfondiamo il FILTER

Quando usi FILTER, Redis non fa prima la ricerca vettoriale e poi filtra i risultati, ma integra il filtro nel processo di ricerca HNSW. Man mano che l'algoritmo HNSW esplora il grafo e identifica nodi candidati, cioè vettori potenzialmente vicini alla tua query, verifica immediatamente se quel candidato supera anche la condizione del tuo FILTER. Solo i candidati che sono sia vettorialmente vicini, sia soddisfano il filtro vengono considerati validi per il risultato finale. Attenzione però! Esiste, però, un potenziale problema, immagina che il tuo filtro sia molto selettivo, cioè è solo una piccola percentuale dei tuoi dati lo soddisfa.

L'algoritmo HNSW potrebbe trovare rapidamente molti vettori vicini alla tua query, ma la maggior parte di essi viene scartata dal filtro perché non soddisfano il filtro. Per riuscire a trovare il numero di risultati che hai chiesto (es. COUNT 10), Redis deve continuare a esplorare il grafo molto più a lungo e considerare molti più candidati rispetto a una ricerca non filtrata. Questo richiede più tempo e risorse CPU. Nel caso peggiore, se gli elementi che soddisfano il filtro sono estremamente rari, Redis potrebbe finire per dover esaminare quasi l'intero grafo, rendendo la ricerca molto lenta.

Per evitare che le query con filtri molto selettivi diventino eccessivamente lente, Redis Vector Sets ha un limite di sforzo predefinito.

Per default, quando si utilizza FILTER, Redis non esaminerà più COUNT * 100 candidati totali per cercare di soddisfare la tua richiesta. Quindi se chiedi COUNT 10, esaminerà al massimo 10 * 100 = 1000 candidati, questo porta un vantaggio che è mantenere le prestazioni prevedibili, anche uno svantaggio e cioè che se entro quei 1000 candidati non trova 10 elementi che passano il filtro, ti restituirà semplicemente meno di 10 risultati, quelli che ha trovato.

Attraverso il parametro FILTER-EF è possibile sovrascrivere quel limite automatico di COUNT * 100.

Se per esempio imposti FILTER-EF 5000, dirai a Redis: "Se necessario, sei autorizzato a esaminare fino a 5000 candidati per trovare i miei COUNT risultati filtrati". Questo aumenta la probabilità di ottenere il numero completo di risultati anche con filtri selettivi, ma può aumentare il tempo di ricerca se i match sono effettivamente rari. Impostando il FILTER-EF a 0 elimini il limite e Redis cercherà senza sosta (potenzialmente scansionando tutto) finché non trova COUNT risultati o esaurisce il grafo. È potente ma potenzialmente molto lento.

Importante da segnalare che anche se imposti un FILTER-EF molto alto (es. 5000), Redis non farà necessariamente tutto quel lavoro! Se gli elementi che soddisfano il filtro sono comuni, l'algoritmo HNSW si fermerà molto prima grazie ai suoi meccanismi di early stopping, non appena avrà trovato COUNT risultati di buona qualità.

Comandi Fondamentali (sintesi)

VADD: Aggiunge un elemento con il suo vettore.
- Opzioni chiave:
  - REDUCE: Riduci Dimensioni: Applica random projection per ridurre la dimensionalità del vettore.
  - FP32/VALUES: Formato Input. Specifica se il vettore è inviato come dati binari (FP32) o stringhe numeriche (VALUES).
  - Q8/BIN/NOQUANT: Quantizzazione: Sceglie il tipo di compressione per il vettore (int8, binaria, o nessuna).
  - EF (build): Sforzo Costruzione: Controlla quanto accuratamente cercare i vicini durante l'inserimento (impatto su qualità indice e tempo VADD).
  - M: Connessioni Grafo. Numero massimo di link per nodo nel grafo HNSW.
SETATTR: Attributi JSON: Associa dati JSON all'elemento, usabili poi per filtrare.
CAS: Threading Parziale. Esegue parte dell'inserimento (ricerca candidati) in un thread separato per ridurre latenza comando.
VSIM: Esegue la ricerca di similarità.
- Opzioni chiave:
  - ELE/FP32/VALUES: Tipo Query: Indica se la query è il nome di un elemento esistente (ELE) o un vettore (FP32/VALUES).
  - WITHSCORES: Mostra Punteggi: Restituisce anche il punteggio di similarità per ogni risultato.
  - COUNT: Numero Risultati. Specifica quanti elementi simili restituire al massimo.
  - EF (search): Sforzo Ricerca: Controlla l'accuratezza (recall) vs velocità della ricerca nel grafo HNSW.
  - FILTER expression: Filtra Risultati: Applica un filtro basato sugli attributi JSON degli elementi.
  - FILTER-EF: Sforzo Ricerca Filtrata: Limite allo sforzo specifico per ricerche che usano FILTER.
  - TRUTH: Ricerca Esatta. Esegue una scansione lineare (lenta) per trovare i risultati perfetti (utile per testare la recall).
  - NOTHREAD: No Thread. Forza l'esecuzione della ricerca nel thread principale di Redis (può causare blocchi).
VREM: Rimuove fisicamente l'elemento e il suo vettore, liberando memoria.
VEMB: Recupera il vettore (approssimato / dequantizzato) di un elemento. RAW restituisce la rappresentazione interna.

1VEMB movie_embeddings "Die Hard"
2   1) "0.5142386555671692"
3   2) "0.09641975164413452"
4   3) "-0.2892592251300812"
5   4) "1.060617208480835"
6   5) "-0.16069957613945007"....

1VEMB movie_embeddings "Die Hard" RAW
21) int8
32) "\x10\x03\xf7!\xfb\xe7\xe3\xf8\xfd\xfa\x0f\n\x04\x01\x13\...

VSETATTR: Imposta/aggiorna/rimuove gli attributi JSON per il filtering.
VGETATTR: Recupera gli attributi JSON.
VDIM, VCARD: Ottengono dimensione vettori e numero elementi.

1VDIM movie_embeddings
2(integer) 1024
3
4VCARD movie_embeddings
5(integer) 998

VINFO, VLINKS: Comandi di introspezione per debug e analisi.

1VINFO word_embeddings_bin
2 1) quant-type
3 2) int8
4 3) hnsw-m
5 4) (integer) 16
6 5) vector-dim
7 6) (integer) 300
8 7) projection-input-dim
9 8) (integer) 0
10 9) size
1110) (integer) 3000000
1211) max-level
1312) (integer) 11
1413) attributes-count
1514) (integer) 3000000
1615) vset-uid
1716) (integer) 1
1817) hnsw-max-node-uid
1918) (integer) 3000000

VRANDMEMBER: Restituisce elementi casuali si un set.

La nostra esperienza con Redis Vector Sets

Armati della build preliminare fornita da antirez, abbiamo intrapreso l'integrazione di Redis Vector Sets nel nostro sistema RAG esistente. Il nostro obiettivo era duplice: valutare la facilità di integrazione e confrontare le prestazioni con ChromaDB, la nostra soluzione precedente.

Prime impressioni

Le prestazioni di Redis si sono fatte sentire immediatamente. Sia durante le fase di inserimento che in fase di query. Le query VSIM, sia su un dataset contenuti, come quello del nostro caso d’uso, sia su dataset di test significativi, erano estremamente rapide. Abbiamo anche provato dataset con quantizzazione binaria per sperimentare le prestazioni spinte.

Abbiamo provato le varie opzioni sia per il comando di inserimento (VADD) che per il comando di query (VSIM) per sperimentare i vari comportamenti e la scelta finale è stata la seguente:

Inserimento: VADD FP32 [BLOB…] ID M 16 EF 200
Query: VSIM FP32 [BLOB…] COUNT 5 WITHSCORES EF 500

Durante i test, molti dei quali svolti insieme ad antirez, ci siamo imbattuti in un aspetto cruciale: la modalità di invio dei vettori dal client a Redis. Inizialmente, utilizzavamo l'opzione VALUES, che prevede l'invio del vettore come una lista di stringhe rappresentanti numeri float (es. VALUES 3 0.145 0.2345 0.3234).

Abbiamo notato che:

La serializzazione di grandi vettori in questo formato stringa lato client può essere sorprendentemente lenta e consumare CPU sul client stesso.
Il payload risultante è molto verboso, aumentando l'uso di banda e la latenza di rete rispetto ai comandi Redis tipici.

Abbiamo quindi provato ad utilizzare l'opzione FP32. Questa opzione permette di inviare il vettore come un blob binario compatto di float a 32 bit. Il miglioramento è stato drastico: abbiamo osservato speedup nell'ordine di 10-20x nel tempo complessivo di invio del comando VADD o VSIM (quando la query è un vettore), semplicemente cambiando il formato di trasmissione. Questo è un punto importante da considerare per chiunque implementi un'applicazione che interagisce con Redis Vector Sets: privilegiare FP32 rispetto a VALUES per l'invio di vettori. Troverete queste queste indicazioni nella documentazione ufficiale! Siamo ansiosi di vedere la versione stabile di Redis Vector Sets e di continuare a esplorare le sue potenzialità.

Conclusioni

La nostra esperienza con Redis Vector Sets, sebbene basata su una versione preliminare, è stata estremamente positiva. La combinazione delle prestazioni in-memory di Redis, un'implementazione HNSW ottimizzata, funzionalità avanzate come la filtered search e la quantizzazione, e la possibilità di consolidare l'infrastruttura dati, lo rendono una soluzione molto promettente.

I punti di forza principali che abbiamo riscontrato sono:

Velocità: le ricerche sono estremamente rapide, specialmente sfruttando la quantizzazione.
Filtered Search Integrata: una funzionalità potente molto utile in molti contesti.
Efficienza di Memoria: la quantizzazione (specialmente Q8) offre un eccellente compromesso tra uso di memoria e accuratezza.

L'importanza di usare il formato binario FP32 per la trasmissione dei vettori non può essere sottovalutata per ottenere le massime prestazioni lato client. Ringraziamo Salvatore Sanfilippo per l'opportunità di testare in anteprima questo entusiasmante sviluppo nel mondo Redis e della ricerca vettoriale e di aver dato anche se involontariamente un piccolo contributo.