DISKANN

Dans les scénarios à grande échelle, où les ensembles de données peuvent comprendre des milliards, voire des trillions de vecteurs, les méthodes d'indexation en mémoire standard (par exemple, HNSW, IVF_FLAT) ne parviennent souvent pas à suivre le rythme en raison des limites de la mémoire. DISKANN propose une approche basée sur le disque qui relève ces défis en maintenant une précision et une vitesse de recherche élevées lorsque la taille de l'ensemble de données dépasse la RAM disponible.

Vue d'ensemble

DISKANN combine deux techniques clés pour une recherche vectorielle efficace :

• Graphique de Vamana - Un index basé sur un disque et un graphique qui relie les points de données (ou vecteurs) pour une navigation efficace pendant la recherche.

• Quantification des produits (PQ ) - Une méthode de compression en mémoire qui réduit la taille des vecteurs, permettant des calculs rapides de la distance approximative entre les vecteurs.

Construction de l'index

Graphe de Vamana

Le graphe de Vamana est au cœur de la stratégie de DISKANN basée sur les disques. Il peut gérer de très grands ensembles de données car il n'a pas besoin de résider entièrement dans la mémoire pendant ou après sa construction.

La figure suivante montre comment un graphe de Vamana est construit.

Diskann

1. Connexions aléatoires initiales : Chaque point de données (vecteur) est représenté par un nœud dans le graphe. Ces nœuds sont initialement connectés de manière aléatoire, formant un réseau dense. Généralement, un nœud commence avec environ 500 arêtes (ou connexions) pour une large connectivité.

2. Affinage pour plus d'efficacité : Le graphe aléatoire initial est soumis à un processus d'optimisation afin de le rendre plus efficace pour la recherche. Ce processus comprend deux étapes clés :

   • L'élagage des arêtes redondantes : L'algorithme élimine les connexions inutiles en se basant sur les distances entre les nœuds. Cette étape donne la priorité aux arêtes de meilleure qualité.

     Le paramètre max_degree limite le nombre maximal d'arêtes par nœud. Une valeur plus élevée de max_degree se traduit par un graphe plus dense, ce qui permet de trouver des voisins plus pertinents (rappel plus élevé), mais augmente également l'utilisation de la mémoire et le temps de recherche.

   • Ajout de raccourcis stratégiques : Vamana introduit des arêtes à longue portée, reliant des points de données très éloignés les uns des autres dans l'espace vectoriel. Ces raccourcis permettent aux recherches de sauter rapidement à travers le graphe, en contournant les nœuds intermédiaires et en accélérant considérablement la navigation.

     Le paramètre search_list_size détermine l'ampleur du processus d'affinage du graphe. Une valeur plus élevée de search_list_size étend la recherche de voisins pendant la construction et peut améliorer la précision finale, mais augmente le temps de construction de l'index.

Pour en savoir plus sur le réglage des paramètres, reportez-vous à DISKANN params.

PQ

DISKANN utilise PQ pour compresser les vecteurs à haute dimension en représentations plus petites(codes PQ), qui sont stockées en mémoire pour des calculs rapides de distance approximative.

Le paramètre pq_code_budget_gb_ratio gère l'empreinte mémoire dédiée au stockage de ces codes PQ. Il représente un rapport entre la taille totale des vecteurs (en gigaoctets) et l'espace alloué au stockage des codes PQ. Vous pouvez calculer le budget réel des codes PQ (en gigaoctets) à l'aide de la formule suivante :

PQ Code Budget (GB) = vec_field_size_gb * pq_code_budget_gb_ratio

où :

• vec_field_size_gb est la taille totale des vecteurs (en gigaoctets).

• pq_code_budget_gb_ratio est un ratio défini par l'utilisateur, représentant la fraction de la taille totale des données réservée aux codes PQ. Ce paramètre permet de trouver un compromis entre la précision de la recherche et les ressources mémoire. Pour plus d'informations sur le réglage des paramètres, reportez-vous à DISKANN configs.

Pour plus de détails techniques sur la méthode PQ sous-jacente, voir IVF_PQ.

Processus de recherche

Une fois que l'index (le graphe de Vamana sur le disque et les codes PQ en mémoire) est construit, DISKANN effectue les recherches ANN comme suit :

Diskann 2

1. Requête et point d'entrée : Un vecteur de requête est fourni pour localiser les voisins les plus proches. DISKANN démarre à partir d'un point d'entrée sélectionné dans le graphe de Vamana, souvent un nœud proche du centroïde global de l'ensemble de données. Le centroïde global représente la moyenne de tous les vecteurs, ce qui permet de minimiser la distance à parcourir dans le graphe pour trouver les voisins souhaités.

2. Exploration du voisinage : L'algorithme rassemble les voisins candidats potentiels (cercles en rouge sur la figure) à partir des bords du nœud actuel, en s'appuyant sur les codes PQ en mémoire pour estimer les distances entre ces candidats et le vecteur de la requête. Ces voisins potentiels sont les nœuds directement connectés au point d'entrée sélectionné par des arêtes dans le graphe de Vamana.

3. Sélection des nœuds pour un calcul précis de la distance : À partir des résultats approximatifs, un sous-ensemble des voisins les plus prometteurs (cercles en vert sur la figure) est sélectionné pour des évaluations précises de la distance en utilisant leurs vecteurs originaux non compressés. Cette opération nécessite la lecture des données à partir du disque, ce qui peut prendre beaucoup de temps. DISKANN utilise deux paramètres pour contrôler cet équilibre délicat entre précision et rapidité :

   • beam_width_ratio: Un ration qui contrôle l'étendue de la recherche, déterminant le nombre de voisins candidats sélectionnés en parallèle pour explorer leurs voisins. Une valeur plus élevée de beam_width_ratio entraîne une exploration plus large, ce qui peut conduire à une plus grande précision, mais aussi à une augmentation des coûts de calcul et des entrées/sorties sur disque. La largeur du faisceau, ou le nombre de nœuds sélectionnés, est déterminée à l'aide de la formule suivante : Beam width = Number of CPU cores * beam_width_ratio.

   • search_cache_budget_gb_ratio: La proportion de mémoire allouée à la mise en cache des données du disque fréquemment consultées. Cette mise en cache permet de minimiser les entrées/sorties sur disque et d'accélérer les recherches répétées, car les données sont déjà en mémoire.

   Pour en savoir plus sur le réglage des paramètres, reportez-vous à DISKANN configs.

4. Exploration itérative : La recherche affine de manière itérative l'ensemble des candidats, en effectuant à plusieurs reprises des évaluations approximatives (à l'aide de PQ) suivies de vérifications précises (à l'aide des vecteurs originaux du disque) jusqu'à ce qu'un nombre suffisant de voisins soit trouvé.

Activer DISKANN dans Milvus

Par défaut, DISKANN est désactivé dans Milvus afin de donner la priorité à la vitesse des index en mémoire pour les ensembles de données qui tiennent aisément dans la RAM. Toutefois, si vous travaillez avec des ensembles de données volumineux ou si vous souhaitez profiter de l'évolutivité de DISKANN et de l'optimisation SSD, vous pouvez facilement l'activer.

Voici comment activer DISKANN dans Milvus :

1. Mise à jour du fichier de configuration Milvus

   1. Localisez votre fichier de configuration Milvus. (Reportez-vous à la documentation Milvus sur la configuration pour plus de détails sur la recherche de ce fichier).

   2. Recherchez le paramètre queryNode.enableDisk et définissez sa valeur sur true:

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

2. Optimiser le stockage pour DISKANN

Pour garantir les meilleures performances avec DISKANN, il est recommandé de stocker vos données Milvus sur un SSD NVMe rapide. Voici comment procéder pour les déploiements Milvus autonome et en cluster :

• Milvus autonome

  • Monter le répertoire de données Milvus sur un SSD NVMe dans le conteneur Milvus. Vous pouvez le faire dans le fichier docker-compose.yml ou à l'aide d'autres outils de gestion de conteneurs.

  • Par exemple, si votre SSD NVMe est monté sur /mnt/nvme, vous devez mettre à jour la section volumesde votre docker-compose.yml comme suit :

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

• Cluster Milvus

  • Monter le répertoire de données Milvus sur un disque SSD NVMe dans les conteneurs QueryNode et IndexNode. Vous pouvez y parvenir par le biais de votre configuration d'orchestration de conteneurs.

  • En montant les données sur un SSD NVMe dans les deux types de nœuds, vous garantissez des vitesses de lecture et d'écriture rapides pour les opérations de recherche et d'indexation.

Une fois ces modifications effectuées, redémarrez votre instance Milvus pour que les paramètres prennent effet. Désormais, Milvus exploitera les capacités de DISKANN pour traiter des ensembles de données volumineux et fournir une recherche vectorielle efficace et évolutive.

Configuration de DISKANN

Les paramètres relatifs à DISKANN ne peuvent être configurés que via votre fichier de configuration 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

Pour plus de détails sur les descriptions des paramètres, reportez-vous à DISKANN params.

Paramètres DISKANN

Le réglage fin des paramètres de DISKANN vous permet d'adapter son comportement à votre ensemble de données spécifique et à votre charge de travail de recherche, en trouvant le bon équilibre entre la vitesse, la précision et l'utilisation de la mémoire.

Paramètres de construction d'index

Ces paramètres influencent la façon dont l'index DISKANN est construit. Leur ajustement peut affecter la taille de l'index, le temps de construction et la qualité de la recherche.

	Paramètre	Description du paramètre	Plage de valeurs	Suggestion de réglage
Vamana	MaxDegree	Contrôle le nombre maximal de connexions (arêtes) que chaque point de données peut avoir dans le graphique Vamana.	Type: Entier Plage: [1, 512] Valeur par défaut: 56	Des valeurs plus élevées créent des graphiques plus denses, ce qui peut augmenter la mémorisation (trouver des résultats plus pertinents), mais aussi l'utilisation de la mémoire et le temps de construction. Dans la plupart des cas, nous vous recommandons de définir une valeur comprise dans cette fourchette : [10, 100].
	SearchListSize	Lors de la construction de l'index, ce paramètre définit la taille du groupe de candidats utilisé lors de la recherche des voisins les plus proches pour chaque nœud. Pour chaque nœud ajouté au graphe, l'algorithme conserve une liste des search_list_size meilleurs candidats trouvés jusqu'à présent. La recherche de voisins s'arrête lorsque cette liste ne peut plus être améliorée. À partir de cette liste finale de candidats, les meilleurs max_degree nœuds sont sélectionnés pour former les arêtes finales.	Type: Integer (nombre entier) Plage: [1, int_max] Valeur par défaut: 100	Une valeur plus élevée de search_list_size augmente la probabilité de trouver les vrais voisins les plus proches pour chaque nœud, ce qui peut conduire à un graphe de meilleure qualité et à de meilleures performances de recherche (rappel). Cependant, cela se fait au prix d'un temps de construction de l'index beaucoup plus long. Il doit toujours être fixé à une valeur supérieure ou égale à max_degree.
	SearchCacheBudgetGBRatio	Contrôle la quantité de mémoire allouée à la mise en cache des parties du graphe fréquemment consultées lors de la construction de l'index.	Type: Flottant Plage: [0.0, 0.3) Valeur par défaut: 0.10	Une valeur élevée alloue plus de mémoire pour la mise en cache, ce qui réduit considérablement les entrées/sorties sur disque mais consomme plus de mémoire système. Dans la plupart des cas, nous vous recommandons de définir une valeur comprise dans cette fourchette : [0.0, 0.3).
PQ	PQCodeBudgetGBRatio	Contrôle la taille des codes PQ (représentations compressées des points de données) par rapport à la taille des données non compressées.	Type: Flottant Plage: (0,0, 0,25) Valeur par défaut: 0.125	Un ratio plus élevé permet d'obtenir des résultats de recherche plus précis en allouant une plus grande proportion de la mémoire aux codes PQ, ce qui permet de stocker davantage d'informations sur les vecteurs d'origine. Un ratio plus faible réduit l'utilisation de la mémoire, mais sacrifie potentiellement la précision, car les codes PQ plus petits conservent moins d'informations. Cette approche convient aux scénarios dans lesquels les contraintes de mémoire sont importantes, et permet éventuellement d'indexer des ensembles de données plus importants. Dans la plupart des cas, nous vous recommandons de définir une valeur comprise dans cette fourchette : (0.0625, 0.25)

Paramètres de recherche spécifiques à l'index

Ces paramètres influencent la manière dont DISKANN effectue les recherches. Leur réglage peut avoir un impact sur la vitesse de recherche, la latence et l'utilisation des ressources.

	Paramètre	Paramètre Description	Plage de valeurs	Suggestion de réglage
Vamana	BeamWidthRatio	Contrôle le degré de parallélisme pendant la recherche en déterminant le nombre maximum de demandes d'E/S de disque parallèles par rapport au nombre de cœurs de CPU disponibles.	Type: Flottant Plage: [1, max(128 / nombre de CPU, 16)] Valeur par défaut: 4.0	Des valeurs plus élevées augmentent le parallélisme, ce qui peut accélérer la recherche sur les systèmes dotés de CPU et de SSD puissants. Dans la plupart des cas, nous vous recommandons de définir une valeur comprise dans cette fourchette : [1.0, 4.0].
	search_list	Au cours d'une opération de recherche, ce paramètre détermine la taille du groupe de candidats que l'algorithme maintient lorsqu'il parcourt le graphe. Une valeur plus élevée augmente les chances de trouver les vrais voisins les plus proches (rappel plus élevé), mais augmente également la latence de la recherche.	Type: Entier Plage: [1, int_max] Valeur par défaut: 100	Pour un bon équilibre entre performance et précision, il est recommandé de fixer cette valeur à un niveau égal ou légèrement supérieur au nombre de résultats que vous souhaitez récupérer (top_k).