Comprendre la quantification scalaire dans Lucene

Souhaitez-vous recevoir une certification Elastic ? Découvrez quand se déroulera la prochaine formation Elasticsearch Engineer ! Vous pouvez lancer un essai gratuit sur le cloud ou essayer Elastic sur votre machine locale dès maintenant.

Quantification automatique des octets dans Lucene

Bien que HNSW soit un moyen puissant et flexible de stocker et de rechercher des vecteurs, il nécessite une quantité importante de mémoire pour fonctionner rapidement. Par exemple, l'interrogation de 1MM float32 vectors de 768 dimensions nécessite environ $1 000 000 * 4 * (768 + 12) = 3120000000 bytes \approx 3GB$ de ram. Dès que vous commencez à rechercher un nombre important de vecteurs, cela devient coûteux. La quantification des octets est un moyen d'utiliser environ $75\%$ moins de mémoire. Lucene et, par conséquent, Elasticsearch prennent en charge l'indexation des vecteurs d'$octets$ depuis un certain temps, mais la construction de ces vecteurs relève de la responsabilité de l'utilisateur. Cela est sur le point de changer, car nous avons introduit la quantification scalaire $int8$ dans Lucene.

Quantification scalaire 101

Toutes les techniques de quantification sont considérées comme des transformations avec perte des données brutes. Cela signifie que certaines informations sont perdues pour des raisons d'espace. Pour une explication approfondie de la quantification scalaire, voir : Quantification scalaire 101. À un niveau élevé, la quantification scalaire est une technique de compression avec perte. Un simple calcul permet de réaliser des économies d'espace significatives avec très peu d'impact sur le rappel.

Explorer l'architecture

Les personnes habituées à travailler avec Elasticsearch sont peut-être déjà familiarisées avec ces concepts, mais voici un aperçu rapide de la distribution des documents pour la recherche.

Chaque index Elasticsearch est composé de plusieurs tiroirs (shards). Bien que chaque nuage ne puisse être affecté qu'à un seul nœud, plusieurs nuages par index permettent un parallélisme de calcul entre les nœuds.

Chaque tesson est composé d'un seul index Lucene. Un index Lucene se compose de plusieurs segments en lecture seule. Pendant l'indexation, les documents sont mis en mémoire tampon et périodiquement vidés dans un segment en lecture seule. Lorsque certaines conditions sont remplies, ces segments peuvent être fusionnés en arrière-plan en un segment plus large. Tout cela est configurable et comporte son lot de complexités. Mais lorsque nous parlons de segments et de fusion, nous parlons de segments Lucene en lecture seule et de la fusion périodique automatique de ces segments. Voici une analyse plus approfondie de la fusion des segments et des décisions en matière de conception.

Quantification par segment dans Lucene

Chaque segment dans Lucene stocke les éléments suivants : les vecteurs individuels, les indices du graphe HNSW, les vecteurs quantifiés et les quantiles calculés. Par souci de concision, nous nous concentrerons sur la manière dont Lucene stocke les vecteurs quantifiés et bruts. Pour chaque segment, nous conservons la trace des $vecteurs$ bruts dans le fichier vec, des vecteurs quantifiés et d'un seul multiplicateur correctif dans le $fichier veq,$ ainsi que les métadonnées relatives à la quantification $dans le$ fichier vemq.

Figure 1 : Présentation simplifiée d'un fichier de stockage de vecteurs bruts. Occupe la $dimension * 4 * numVectors$ de l'espace disque puisque les valeurs $flottantes$ sont de 4 octets. Étant donné que nous quantifions, ces données ne seront pas chargées lors de la recherche HNSW. Ils ne sont utilisés que sur demande expresse (par ex. secondaire par force brute via le rescore), ou pour la re-quantification lors de la fusion de segments.

Figure 2 : Présentation simplifiée du fichier $.veq$ fichier. Occupe un espace de $(dimension + 4)*numVectors$ et sera chargé en mémoire lors de la recherche. Les $+ 4$ octets sont destinés à prendre en compte le multiplicateur de correction, utilisé pour ajuster la notation afin d'améliorer la précision et la mémorisation.

Figure 3 : Présentation simplifiée du fichier de métadonnées. C'est ici que nous gardons trace de la quantification et de la configuration du vecteur, ainsi que des quantiles calculés pour ce segment.

Ainsi, pour chaque segment, nous stockons non seulement les vecteurs quantifiés, mais aussi les quantiles utilisés pour créer ces vecteurs quantifiés et les vecteurs bruts originaux. Mais pourquoi conserver les vecteurs bruts ?

Une quantification qui évolue avec vous

Étant donné que Lucene se concentre périodiquement sur les segments en lecture seule, chaque segment n'a qu'une vue partielle de l'ensemble des données. Cela signifie que les quantiles calculés ne s'appliquent directement qu'à cet échantillon de l'ensemble de vos données. Ce n'est pas très grave si votre échantillon représente correctement l'ensemble de votre corpus. Mais Lucene vous permet de trier votre index de différentes manières. Ainsi, vous pourriez indexer des données triées d'une manière qui ajoute un biais pour les calculs de quantile par segment. De plus, vous pouvez effacer les données quand vous le souhaitez ! Votre échantillon peut être minuscule, ne serait-ce qu'un seul vecteur. Un autre avantage est que vous avez le contrôle sur le moment où les fusions ont lieu. Bien qu'Elasticsearch ait configuré des valeurs par défaut et une fusion périodique, vous pouvez demander une fusion quand vous le souhaitez via l'API _force_merge. Alors, comment permettre cette flexibilité tout en assurant une bonne quantification et un bon rappel ?

La quantification vectorielle de Lucene s'adaptera automatiquement au fil du temps. Lucene étant conçu avec une architecture de segments en lecture seule, nous avons la garantie que les données de chaque segment n'ont pas changé et des démarcations claires dans le code pour savoir quand les choses peuvent être mises à jour. Cela signifie que lors de la fusion des segments, nous pouvons ajuster les quantiles si nécessaire et éventuellement ré-équantifier les vecteurs.

Figure 4 : Trois exemples de segments avec différents quantiles.

Mais la requantification n'est-elle pas coûteuse ? Il y a un certain surcoût, mais Lucene gère les quantiles intelligemment et ne les quantifie complètement que lorsque c'est nécessaire. Prenons l'exemple des segments de la figure 4. Donnons aux segments $A$ et $B$ $1 000$ documents chacun et au segment $C$ seulement $100$ documents. Lucene prend une moyenne pondérée des quantiles et si le quantile fusionné qui en résulte est suffisamment proche des quantiles originaux du segment, nous n'avons pas besoin de quantifier à nouveau ce segment et nous utiliserons les quantiles nouvellement fusionnés.

Figure 5 : Exemple de quantiles fusionnés lorsque les segments $A$ et $B$ ont $1000$ documents et que le segment $C$ n'en a que $100$.

Dans la situation représentée à la figure 5, nous pouvons voir que les quantiles fusionnés qui en résultent sont très similaires aux quantiles originaux en $A$ et $B.$ Ils ne justifient donc pas la quantification des vecteurs. Le segment $C$ semble s'écarter trop de la réalité. Par conséquent, les vecteurs de $C$ seront quantifiés à nouveau avec les valeurs de quantile nouvellement fusionnées.

Il existe en effet des cas extrêmes où les quantiles fusionnés diffèrent considérablement des quantiles initiaux. Dans ce cas, nous prendrons un échantillon de chaque segment et recalculerons entièrement les quantiles.

Performance de quantification & numbers

Est-il rapide et offre-t-il toujours un bon rappel ? Les chiffres suivants ont été recueillis lors de l'exécution de l'expérience sur une instance GCP c3-standard-8. Pour garantir une comparaison équitable avec $float32$, nous avons utilisé une instance suffisamment grande pour contenir des vecteurs bruts en mémoire. Nous avons indexé $400 000$ vecteurs Cohere Wiki en utilisant le produit intérieur maximal.

Figure 6 : Rappel@10 pour les vecteurs quantifiés par rapport aux vecteurs bruts. La performance de recherche des vecteurs quantifiés est nettement plus rapide que celle des vecteurs bruts, et le rappel est rapidement récupérable en rassemblant seulement 5 vecteurs supplémentaires ; visible par $quantized@15$.

La figure 6 illustre l'histoire. Bien qu'il y ait une différence de rappel, comme on peut s'y attendre, elle n'est pas significative. Et la différence de rappel disparaît en rassemblant seulement 5 vecteurs supplémentaires. Tout cela avec des fusions de segments $2 fois plus$ rapides et 1/4 de la mémoire des vecteurs $float32$.

Conclusion

Lucene apporte une solution unique à un problème difficile. La quantification ne nécessite aucune étape de "formation" ou d'"optimisation". Dans Lucene, cela fonctionnera simplement. Il n'y a pas d'inquiétude à avoir quant à la nécessité de "ré-entraîner" votre index vectoriel si vos données changent. Lucene détectera les changements significatifs et s'en chargera automatiquement pendant toute la durée de vie de vos données. Nous attendons avec impatience le moment où nous intégrerons cette fonctionnalité dans Elasticsearch !

Questions fréquentes