5 problèmes de recherche de vecteurs difficiles et comment nous les avons résolus dans Apache Cassandra

La recherche de vecteurs est un élément essentiel des outils d'IA générative en raison de la façon dont la génération augmentée de récupération (RAG) comme ÉCLATER aide les LLM à intégrer des informations à jour et personnalisées tout en évitant les hallucinations . Dans le même temps, la recherche de vecteurs est une fonctionnalité, pas un produit : vous devez interroger les vecteurs en fonction de leur relation avec le reste de vos données, et non de manière isolée, et vous ne devriez pas avoir besoin de créer un pipeline pour synchroniser le reste de vos données. données avec un magasin vectoriel pour ce faire.

L’année 2023 a vu une explosion des produits et des projets de recherche vectorielle, ce qui rend la sélection parmi eux un effort sérieux. Pendant que vous recherchez les options, vous devrez prendre en compte les problèmes difficiles suivants et les différentes approches pour les résoudre. Ici, je vais vous expliquer ces défis et décrire comment DataStax les a relevés pour notre implémentation de la recherche vectorielle pour DataStax Astra DB et Apache Cassandra.

Aperçu du contenu

• La malédiction de la dimensionnalité
• Problème 1 : évolutivité
• Problème 2 : Collecte efficace des déchets
• Encadré : Charges de travail des applications cloud
• Problème 3 : Concurrence
• Problème 4 : Utilisation efficace du disque
• Problème 5 : composabilité
• Conclure

La malédiction de la dimensionnalité

Au cœur de ces problèmes difficiles se trouve ce que les chercheurs appellent « la malédiction de la dimensionnalité .» En pratique, cela signifie que les algorithmes qui fonctionnent pour la recherche de vecteurs exacts dans des espaces 2D ou 3D, comme arbres kd , s'effondre lorsque vous atteignez des dizaines, des centaines ou des milliers de dimensions dans vos vecteurs. Le résultat est qu’il n’existe aucun raccourci pour une recherche de similarité exacte avec des vecteurs de grande dimension ; pour obtenir des résultats en temps logarithmique, nous devons utiliser des algorithmes du voisin le plus proche (ANN), qui posent des défis dans les domaines suivants.

Problème 1 : évolutivité

De nombreux algorithmes de recherche vectorielle ont été conçus pour des ensembles de données qui tiennent en mémoire sur une seule machine, et c'est toujours le seul scénario testé par ann-benchmarks . (Ann-benchmarks limite encore davantage ses tests à un seul cœur !) Cela peut convenir pour un travail académique comportant un million de documents ou de lignes, mais cela fait de nombreuses années que cela ne peut pas être considéré comme représentatif des charges de travail du monde réel.

Comme pour tout autre domaine, la mise à l'échelle nécessite à la fois une réplication et un partitionnement, ainsi que des sous-systèmes pour gérer le remplacement des réplicas morts, leur réparation après une partition réseau, etc.

Cela a été facile pour nous : la réplication évolutive est le pain quotidien de Cassandra, et en combinant cela avec le nouveau Cassandra-5.0 SAI (Storage-Attached Indexing – voir CPE-7 pour comment ça marche, et la documentation ISC pour savoir comment l'utiliser) a donné à notre implémentation de recherche vectorielle de puissantes capacités d'évolution efficacement et gratuitement.

Problème 2 : Collecte efficace des déchets

Par « garbage collection », j'entends supprimer les informations obsolètes de l'index – nettoyer les lignes supprimées et traiter les lignes dont la valeur vectorielle indexée a changé. Cela ne vaut peut-être pas la peine d'être mentionné – c'est un problème plus ou moins résolu depuis quarante ans dans le monde des bases de données relationnelles – mais les index vectoriels sont uniques.

Le problème clé est que tous les algorithmes que nous connaissons et qui fournissent à la fois des recherches à faible latence et des résultats à rappel élevé sont basés sur des graphiques. Il existe de nombreux autres algorithmes d’indexation vectorielle disponibles – FAISS en implémente beaucoup – mais tous sont soit trop lents à construire, soit trop lents à rechercher, soit offrent un rappel trop faible (et parfois les trois !) pour être une solution à usage général. C'est pourquoi chaque base de données de vecteurs de production que je connais utilise un index basé sur des graphiques, dont le plus simple est HNSW. Les graphiques hiérarchiques navigables du petit monde ont été introduit par Yury Malkov et al en 2016 ; le document est assez lisible et je le recommande vivement. En savoir plus sur HNSW ci-dessous.

Le défi avec les index graphiques est que vous ne pouvez pas simplement supprimer l'ancien nœud (associé au vecteur) lorsqu'une ligne ou un document change ; si vous faites cela plus d'une poignée de fois, votre graphique ne sera plus en mesure de remplir son objectif de diriger BFS (recherche en largeur) vers des zones plus similaires à un vecteur de requête.

Vous devrez donc reconstruire vos index à un moment donné pour effectuer ce garbage collection, mais quand et comment l'organiser ? Si vous reconstruisez toujours tout lorsque des modifications sont apportées, vous augmenterez massivement les écritures physiques effectuées ; c'est ce qu'on appelle l'amplification en écriture. D'un autre côté, si vous ne reconstruisez jamais, vous effectuerez un travail supplémentaire en filtrant les lignes obsolètes au moment de la requête (« amplification de lecture »).

Il s’agit d’un autre problème sur lequel Cassandra travaille depuis des années. Puisque les index SAI sont attachés au cycle de vie du stockage principal, ils participent également à Cassandra compactage , qui augmente de manière logarithmique les unités de stockage pour fournir un équilibre sain entre les lectures et les écritures.

Encadré : Charges de travail des applications cloud

DataStax Astra DB s'appuie sur Apache Cassandra pour fournir une plate-forme pour les charges de travail des applications cloud.

Cela signifie des charges de travail qui sont :

• Des milliers, voire des millions de requêtes simultanées en masse par seconde, généralement pour récupérer seulement quelques lignes chacune. C'est pourquoi vous ne pourriez pas exécuter Netflix sur Snowflake, même si vous en aviez les moyens : Snowflake et les systèmes analytiques similaires sont conçus pour gérer seulement quelques requêtes simultanées qui s'exécutent chacune pendant plusieurs secondes, voire plusieurs minutes, voire plus.

  
  

• Plus grand que la mémoire Si votre ensemble de données tient en mémoire sur une seule machine, les outils que vous utilisez n'ont presque pas d'importance. SQLite, MongoDB, MySQL – ils fonctionneront tous correctement. Les choses deviennent plus difficiles lorsque ce n'est pas le cas - et la mauvaise nouvelle est que les intégrations vectorielles font généralement plusieurs Ko, soit environ un ordre de grandeur plus grand que les documents de base de données classiques, vous obtiendrez donc relativement rapidement une taille plus grande que la mémoire.

  
  

• Cœur de l'application Si vous ne vous souciez pas de perdre vos données, soit parce que ce n'est pas si important, soit parce que vous pouvez les reconstruire à partir de la source d'enregistrement réelle, là encore, les outils que vous utilisez n'ont pas d'importance. Les bases de données comme Cassandra et Astra DB sont conçues pour garder vos données disponibles et durables quoi qu'il arrive.

Problème 3 : Concurrence

J'ai mentionné plus haut que le célèbre ann-benchmarks la comparaison limite tous les algorithmes à un seul cœur. Même si cela uniformise les règles du jeu, cela handicape également ceux qui peuvent profiter de la principale source d'amélioration matérielle au cours des deux dernières décennies.

Un problème connexe est qu'ann-benchmarks n'effectue qu'un seul type d'opération à la fois : d'abord, il construit l'index, puis il l'interroge. Gérer les mises à jour entrelacées de recherches est facultatif – et probablement même un handicap ; si vous savez que vous n'avez pas besoin de gérer les mises à jour, vous pouvez faire de nombreuses hypothèses simplificatrices qui semblent bonnes sur des références artificielles.

Si vous souhaitez pouvoir effectuer plusieurs opérations simultanées avec votre index ou le mettre à jour après sa construction, vous devez alors approfondir un peu pour comprendre son fonctionnement et les compromis impliqués.

Premièrement, toutes les bases de données vectorielles à usage général que je connais utilisent des index basés sur des graphiques. En effet, vous pouvez commencer à interroger un index de graphique dès que le premier vecteur est inséré. La plupart des autres options nécessitent que vous construisiez l'intégralité de l'index avant de l'interroger ou au moins que vous effectuiez une analyse préliminaire des données pour connaître certaines propriétés statistiques.

Cependant, il existe encore des détails d'implémentation importants, même dans la catégorie des index graphiques. Par exemple, nous avons d'abord pensé que nous pourrions gagner du temps en utilisant l'implémentation de l'index HNSW de Lucene, comme le font MongoDB Elastic et Solr. Mais nous avons rapidement appris que Lucene propose uniquement une construction d'index monothread et non simultanée. Autrement dit, vous ne pouvez ni l'interroger pendant sa construction (ce qui devrait être l'une des principales raisons d'utiliser cette structure de données !) ni autoriser plusieurs threads à la construire simultanément.

L'article du HNSW suggère qu'une approche de verrouillage à granularité fine peut fonctionner, mais nous avons fait mieux et avons construit un index non bloquant. Ceci est open source dans JVecteur .

JVector adapte les mises à jour simultanées de manière linéaire à au moins 32 threads. Ce graphique est à l'échelle logarithmique sur les axes x et y, montrant que doubler le nombre de threads réduit de moitié le temps de construction.

Plus important encore, la concurrence non bloquante de JVector profite à des charges de travail plus réalistes en mélangeant recherches et mises à jour. Voici une comparaison des performances d'Astra DB (en utilisant JVector) par rapport à Pinecone sur différents ensembles de données. Alors qu'Astra DB est environ 10 % plus rapide que Pinecone pour un ensemble de données statiques, il est 8 à 15 fois plus rapide tout en indexant également de nouvelles données. Nous avons sélectionné le meilleur niveau de pods disponible avec Pinecone (Type de pod : p2 et Taille du pod : x8, avec 2 pods par réplique) en fonction de leurs recommandations pour un débit plus élevé et une latence plus faible. Pinecone ne divulgue pas à quelles ressources physiques cela correspond. Du côté d'Astra DB, nous avons choisi le modèle de déploiement PAYG par défaut et n'avons pas eu à nous soucier du choix des ressources car il est sans serveur. Les tests ont été effectués à l'aide NoSQLBench .

Astra DB le fait tout en conservant un rappel et une précision plus élevés ( La F1 est une combinaison de rappel et de précision ) :

Problème 4 : Utilisation efficace du disque

Nous avons commencé avec le Algorithme d'indexation de graphiques HNSW car il est rapide à créer l'index, rapide à interroger, très précis et simple à mettre en œuvre. Cependant, il présente un inconvénient bien connu : il nécessite beaucoup de mémoire.

Un indice HNSW est une série de couches, où chaque couche au-dessus de la couche de base contient environ 10 % de nœuds en plus que la précédente. Cela permet aux couches supérieures d'agir comme une liste de sauts, permettant à la recherche de se concentrer sur le voisinage droit de la couche inférieure qui contient tous les vecteurs.

Cependant, cette conception signifie que (comme pour tous les index de graphes), vous ne pouvez pas vous contenter de dire « Le cache disque nous sauvera », car, contrairement aux charges de travail normales de requêtes de base de données, chaque vecteur du graphique a une chance presque égale d'être exécuté. être pertinent pour une recherche. (L'exception concerne les couches supérieures, que nous pouvons et mettons en cache.)

Voici à quoi ressemblait un profil de diffusion d'un ensemble de données vectorielles de 100 millions de morceaux d'articles Wikipédia (environ 120 Go sur le disque) sur mon bureau avec 64 Go de RAM, à l'époque où nous utilisions Lucene :

Cassandra passe presque tout son temps à attendre de lire les vecteurs du disque.

Pour résoudre ce problème, nous avons implémenté un algorithme plus avancé appelé DiskANN et l'avons ouvert en tant que moteur de recherche vectoriel intégré autonome, JVecteur . (Plus précisément, JVector implémente la version incrémentielle de DiskANN décrite dans le FreshDiskANN papier.) En bref, DiskANN utilise un graphe à un seul niveau avec des bords plus longs que HNSW et une disposition optimisée des vecteurs et des voisins pour réduire les IOPS du disque et conserve une représentation compressée des vecteurs en mémoire pour accélérer les calculs de similarité. Cela permet de tripler le débit de la charge de travail Wikipédia.

Voici à quoi ressemble HNSW par rapport à DiskANN dans un scénario purement intégré sans composants client/serveur. Cela mesure la vitesse de recherche dans l'ensemble de données Deep100M sous Lucene (HNSW) et JVector (DiskANN). L'index Lucene est de 55 Go, y compris l'index et les vecteurs bruts. L'index JVector est de 64 Go. La recherche a été effectuée sur mon MacBook de 24 Go, qui dispose d'environ un tiers de la mémoire nécessaire pour conserver l'index dans la RAM.

Problème 5 : composabilité

La composabilité dans le contexte des systèmes de bases de données fait référence à la capacité d'intégrer de manière transparente diverses fonctionnalités et capacités de manière cohérente. Ceci est particulièrement important lorsqu’il s’agit de l’intégration d’une nouvelle catégorie de fonctionnalités, comme la recherche vectorielle. Les applications non liées aux jouets nécessiteront toujours à la fois des jeux classiques CRUD fonctionnalités de base de données ainsi que la nouvelle recherche vectorielle.

Considérez le simple Chatbot IA exemple d'application pour Astra DB. Il s'agit d'une application RAG aussi pure que possible, utilisant la recherche vectorielle pour présenter la documentation appropriée au LLM afin de répondre aux questions des utilisateurs. Cependant, même une simple démo comme celle-ci doit encore effectuer des requêtes « normales » non vectorielles vers Astra DB pour récupérer l'historique des conversations, qui doit également être inclus avec chaque requête adressée au LLM afin qu'il puisse « se souvenir » de ce qui a déjà été fait. eu lieu. Ainsi, les requêtes clés incluent :

1. Rechercher les documents (ou fragments de documents) les plus pertinents pour la question de l'utilisateur
2. Récupérer les vingt derniers messages de la conversation de l'utilisateur

Dans un cas d'utilisation plus réaliste, l'un de nos ingénieurs solutions travaillait récemment avec une entreprise en Asie qui souhaitait ajouter la recherche sémantique à son catalogue de produits, mais souhaitait également permettre une correspondance basée sur les termes. Par exemple, si l'utilisateur recherche [robinet à bille « rouge »], il souhaite limiter la recherche aux éléments dont la description correspond au terme « rouge », quelle que soit la similitude sémantique des représentations vectorielles. La nouvelle requête clé (en plus des fonctionnalités classiques comme la gestion des sessions, l'historique des commandes et les mises à jour du panier) est donc la suivante : restreindre les produits à ceux qui contiennent tous les termes cités, puis trouver le plus similaire à la recherche de l'utilisateur.

Ce deuxième exemple montre clairement que non seulement les applications ont besoin à la fois de fonctionnalités de requête classiques et de recherche vectorielle, mais qu'elles doivent souvent pouvoir utiliser des éléments de chacune dans la même requête.

L'état actuel de la technique dans ce jeune domaine est d'essayer de faire ce que j'appelle des requêtes classiques dans une base de données « normale », des requêtes vectorielles dans une base de données vectorielle, puis d'assembler les deux de manière ad hoc lorsque les deux sont requis en même temps. C'est sujet aux erreurs, lent et coûteux ; sa seule vertu est que vous pouvez le faire fonctionner jusqu'à ce que vous ayez une meilleure solution.

Dans Astra DB, nous avons construit (et open source) cette meilleure solution, en plus de Cassandra SAI. Étant donné que SAI permet de créer des types d'index personnalisés qui sont tous liés au cycle de vie stable et de compactage de Cassandra, il est simple pour Astra DB de permettre aux développeurs de mélanger et de faire correspondre des prédicats booléens, des recherches basées sur des termes et des recherches vectorielles, sans frais généraux. gérer et synchroniser des systèmes distincts. Cela donne aux développeurs qui créent des applications d’IA générative des capacités de requête plus sophistiquées qui génèrent une plus grande productivité et une mise sur le marché plus rapide.

Conclure

Les moteurs de recherche vectorielles constituent une nouvelle fonctionnalité importante de base de données qui présente de multiples défis architecturaux, notamment la mise à l'échelle, le garbage collection, la concurrence, l'utilisation efficace du disque et la composabilité. Je pense qu'en créant la recherche vectorielle pour Astra DB, nous avons pu tirer parti des capacités de Cassandra pour offrir une expérience de premier ordre aux développeurs d'applications d'IA générative. En savoir plus sur Astra DB ici , ou si vous souhaitez vous familiariser avec les algorithmes de recherche vectorielle, consultez JVecteur .

- Par Jonathan Ellis, DataStax