Elasticsearch sous toutes les coutures, partie 1

Introduction

L'idée est de mieux comprendre ce qu'Elasticsearch, Lucene et, dans une certaine mesure, les moteurs de recherche en général cachent réellement sous leur capot. Même s'il est possible de conduire une voiture simplement en appuyant sur les pédales et en tournant le volant, généralement, les automobilistes aux compétences élevées ont au moins quelques notions de mécanique à propos de leur véhicule. Ce principe est vrai pour les moteurs de recherche. Elasticsearch fournit des API très faciles à utiliser. Cette solution vous permet aisément de vous lancer et d'obtenir de bons résultats. Toutefois, pour en tirer pleinement parti, il est utile d'avoir quelques connaissances sur les structures de données et les algorithmes sous-jacents. Grâce à cette compréhension, vous pouvez pleinement utiliser l'ensemble conséquent des fonctionnalités de la solution. En particulier, vous pouvez améliorer les expériences de recherche de vos internautes tout en garantissant en parallèle les performances, la fiabilité et la mise à jour en (quasi) temps réel de vos systèmes.

Nous allons commencer par la structure de base des index, à savoir l'index inversé. Il s'agit d'une structure de données hautement polyvalente qui est aussi très facile à utiliser et à comprendre. Toutefois, l'implémentation de Lucene est une impressionnante prouesse hautement optimisée en matière d'ingénierie. Nous ne détaillerons pas l'implémentation de Lucene dans cet article afin de nous concentrer sur l'utilisation et la conception de l'index inversé, qui influent sur nos possibilités de recherche et d'indexation.

Après avoir présenté les index inversés à la base des niveaux d'abstraction, nous étudierons :

• la manière dont les recherches simples sont menées ;
• les types de recherches qui peuvent (ou pas) être menés de manière efficace et la raison pour laquelle, à l'aide d'un index inversé, nous transformons les problèmes jusqu'à ce qu'ils ressemblent à des problèmes de préfixe de chaîne ;
• les raisons pour lesquelles le traitement de texte est important ;
• les méthodes d'intégration des index dans les "segments" et la manière dont cela influe sur la recherche et la mise à jour ;
• les éléments constitutifs d'un index Lucene ;
• l'index et la partition Elasticsearch.

À cette étape, nous aurons accumulé beaucoup de connaissances sur le fonctionnement d'un seul nœud Elasticsearch lors des recherches et de l'indexation. Le deuxième article de cette série traitera des aspects distribués d'Elasticsearch.

Index inversés et termes indexés

Imaginons que nous possédons trois documents simples "Winter is coming.", "Ours is the fury." et "The choice is yours.". Après avoir utilisé un traitement de texte simple (qui supprime la ponctuation, divise les mots et les convertit en minuscules), nous pouvons construire l'index inversé représenté dans le schéma ci-dessus.

L'index inversé cartographie les termes en documents (et éventuellement les positions dans les documents) qui contiennent ces termes. Étant donné que les termes contenus dans le dictionnaire sont triés, nous pouvons trouver un mot rapidement, puis ses occurrences dans la structure des postings (affichages). Cela est contraire à un "index transmis", qui répertorie les termes liés à un document spécifique.

Une simple recherche composée de plusieurs mots est ensuite menée en cherchant l'ensemble des termes et leurs occurrences, puis tient compte des croisements entre les ensembles des occurrences (pour les recherches effectuées avec le mot "et") ou de leurs associations (pour les recherches effectuées avec le mot "ou") afin d'obtenir une liste de documents. Des types plus complexes de requêtes sont évidemment plus élaborés. Cependant, l'approche reste la même : tout d'abord, il faut exploiter le dictionnaire pour trouver les termes candidats, puis travailler avec les occurrences correspondantes, les positions, etc.

Par conséquent, un terme indexé est l'unité de recherche. Les termes que nous générons dictent les types de recherches que nous pouvons (ou pas) mener de manière efficace. Par exemple, avec le dictionnaire représenté dans le schéma ci-dessus, nous pouvons trouver en toute efficacité l'ensemble des termes qui commencent par la lettre "c". Or, nous pouvons réaliser de manière efficace une recherche concernant tous les documents contenant le mot "ours". Dans ce but, nous devons passer en revue l'ensemble des termes afin de trouver que "yours" comprend également la sous-chaîne. Une telle tâche représente un coût prohibitif lorsque l'index est loin d'être insignifiant. En matière de complexité, l'opération pour chercher des termes en fonction de leur préfixe est \(\mathcal{O}\left(\mathrm{log}\left(n\right)\right)\), tandis que celle pour trouver des termes selon une sous-chaîne arbitraire est \(\mathcal{O}\left(n\right)\).

En d'autres termes, nous pouvons trouver des informations de manière efficace en fonction de préfixes de termes donnés. Lorsque nous disposons seulement d'un index inversé, nous voulons que tout ressemble à un problème de préfixe de chaîne. Voici quelques exemples de ce type de transformations. Certaines sont simples. La dernière est proche de la magie.

• Pour trouver tous les termes qui se terminent par "tastic", nous pouvons indexer l'orthographe inverse (par exemple, "fantastic" est converti en "citsatnaf"), puis chercher tous les mots commençant par "citsat".
• Pour trouver les sous-chaînes, il faut souvent diviser les termes en éléments plus petits appelés "n-grammes". Par exemple, le mot "yours" peut être divisé en "^yo", "you", "our", "urs" et "rs$". Ainsi, nous obtenons des occurrences de "ours" lorsque nous cherchons "our" et "urs".
• En ce qui concerne les langues avec des mots composés, à l'instar du norvégien et de l'allemand, nous devons "décomposer" des mots comme "Donaudampfschiff", par exemple en {"donau", "dampf", "schiff"}, afin de les trouver lorsque nous recherchons "schiff".
• Les coordonnées géographiques, comme (60.6384, 6.5017), peuvent être converties en "hachages géographiques", dans ce cas "u4u8gyykk". Plus la chaîne est longue, plus la précision est grande.
• Pour activer les correspondances phonétiques, qui sont très utiles pour les noms de personnes par exemple, il existe des algorithmes, comme Metaphone, convertissant "Smith" en {"SM0", "XMT"} et "Schmidt" en {"XMT", "SMT"}.
• Lorsque vous gérez des données numériques (et des horodatages), Lucene génère automatiquement plusieurs termes avec différents niveaux de précision dans une arborescence. Ainsi, il est possible de mener des recherches de plages efficaces¹. Schématiquement, le nombre 123 peut être stocké en tant que "1"-centaines, "12"-dizaines et "123". Par conséquent, une recherche de toutes les données de la plage [100, 199] revient à chercher toutes les occurrences correspondant à "1"-centaines. Bien entendu, cette technique est différente d'une recherche de toutes les données commençant par "1", car elle comprendrait également "1234", et ainsi de suite.
• Afin de mener des recherches correspondant à des corrections de requêtes et de trouver des orthographes proches du texte saisi, il est possible de concevoir un automate "Levenshtein" pour explorer le dictionnaire. Cette tâche est exceptionnellement complexe. Voici un compte rendu fascinant de la manière dont cela s'est passé dans Lucene.

Une étude technique en profondeur du traitement de texte peut alimenter de nombreux futurs articles. Or, nous avons insisté sur la raison pour laquelle il est important de générer des termes indexés avec minutie afin d'obtenir des recherches pouvant être menées de manière efficace.

Conception d'index

Lors de la conception d'index inversés, plusieurs éléments doivent être envisagés en priorité, à savoir la vitesse de recherche, le caractère compact des index, la vitesse d'indexation et le temps requis pour que les nouveaux changements deviennent visibles.

La vitesse de recherche et le caractère compact des index sont liés : lors d'une recherche dans un index plus petit, moins de données doivent être traitées et une plus grande quantité sera mise en mémoire. Ces deux éléments, en particulier le caractère compact, influent sur la vitesse d'indexation, comme nous allons le voir plus loin.

Pour réduire les tailles des index, plusieurs techniques de compression sont utilisées. Par exemple, lors du stockage des affichages (qui peuvent devenir relativement grands), Lucene utilise des astuces, comme l'encodage delta (par exemple, [42, 100, 666] est stocké en tant que [42, 58, 566]), à l'aide d'un nombre variable d'octets (ce qui permet d'enregistrer de petits chiffres à l'aide d'un seul octet), et ainsi de suite.

Pour conserver de petites structures de données compactes, il faut sacrifier la possibilité de les mettre à jour de manière efficace. En fait, Lucene ne les met pas du tout à jour : les fichiers d'index écrits par Lucene sont immuables, c'est-à-dire qu'ils ne sont jamais mis à jour. La situation est différente pour les arbres binaires, par exemple, qui peuvent être mis à jour et vous permettent souvent de préciser un taux de remplissage afin d'indiquer le nombre de mises à jour souhaitées.

Les suppressions sont l'exception. Lorsque vous supprimez un document d'un index, ce document est marqué en tant que tel dans un fichier de suppression spécial, qui est, en réalité, une matrice de bits dont la mise à jour est peu coûteuse. Les structures des index elles-mêmes ne sont pas mises à jour.

Par conséquent, pour mettre à jour un document précédemment indexé, il faut supprimer, puis réintégrer le document. Cela signifie que la mise à jour d'un document est encore plus chère que son ajout initial. Ainsi, ce n'est pas une bonne idée, en règle générale, de stocker des éléments, comme des compteurs à l'évolution rapide, dans un index Lucene, car aucune mise à jour des valeurs n'est prévue.

Lorsque de nouveaux documents sont ajoutés (peut-être lors d'une mise à jour), les changements apportés à l'index sont tout d'abord enregistrés dans la mémoire tampon. En fin de compte, les fichiers d'index sont entièrement vidés sur le disque. Il convient de noter que le terme "vidés" a ici le sens conféré par Lucene. Les opérations de vidage d'Elasticsearch impliquent une validation Lucene au minimum. Nous expliquons cela dans la section consacrée aux logs de transaction.

Le moment où il faut vider les fichiers dépend de différents facteurs, notamment la vitesse à laquelle les changements doivent être visibles, la mémoire tampon disponible ainsi que la saturation des entrées et des sorties. En règle générale, en ce qui concerne la vitesse d'indexation, des mémoires tampons plus grandes sont plus appropriées, tant qu'elles sont suffisamment petites pour que vos entrées et vos sorties ne soient pas dépassées². Nous évoquons ce point plus en détail dans la section suivante.

Les fichiers écrits constituent un segment d'index.

Segments d'index

Un index Lucene est composé d'un ou de plusieurs segments d'index immuables, qui sont essentiellement des "mini-index". Lorsque vous effectuez une recherche, Lucene l'exécute dans chaque segment, exclut toute suppression et fusionne les résultats obtenus de l'ensemble des segments. Bien entendu, cette tâche est de plus en plus pénible à mesure que le nombre de segments augmente. Pour conserver un nombre de segments gérable, Lucene fusionne occasionnellement des segments, selon la politique de fusion lors de l'ajout de segments. Le pirate informatique spécialiste de Lucene Michael McCandless a rédigé un excellent article expliquant et visualisant la fusion des segments³. Lorsque des segments sont fusionnés, les documents marqués comme supprimés sont enfin éliminés. C'est la raison pour laquelle l'ajout de documents supplémentaires peut effectivement diminuer la taille d'un index, car cette opération peut lancer une fusion.

En règle générale, Elasticsearch et Lucene fusionnent les segments au moment approprié. Les politiques d'Elasticsearch peuvent être adaptées en configurant des paramètres de fusion. Vous pouvez également utiliser l'API d'optimisation pour forcer les fusions.

Avant que les segments soient vidés sur le disque, les changements doivent être enregistrés dans la mémoire tampon. Dans le passé (avec les versions antérieures à Lucene 2.3), chaque document ajouté existait en tant que petit segment⁴, et tout était fusionné lorsque les documents étaient vidés. Désormais, un DocumentsWriter peut créer de plus grands segments en mémoire à partir d'un lot de documents. Avec Lucene 4, chaque fil peut comprendre un de ces lots, ce qui améliore les performances d'indexation en autorisant les vidages simultanés. (Auparavant, il fallait attendre la fin du vidage pour lancer l'indexation.)

Au fur et à mesure de la création de segments (suite à un vidage ou à une fusion), certains caches pouvaient être annulés, ce qui altérait les performances de recherche. Les caches comme ceux des filtres et des champs sont créés par segment. Elasticsearch comprend une API Warmer⁵. Ainsi, les caches nécessaires peuvent passer à un niveau warm avant que des recherches puissent être menées dans le nouveau segment.

La cause la plus courante de vidage avec Elasticsearch est probablement l'actualisation continue des index, qui a lieu une fois par seconde par défaut. Lorsque de nouveaux segments sont vidés, des recherches peuvent y être menées, ce qui autorise la recherche en (quasi) temps réel. Bien qu'un vidage ne coûte pas aussi cher qu'une validation (car il n'est pas nécessaire d'attendre pour la confirmation d'une écriture), il engendre bien la création d'un segment, ce qui annule certains caches et éventuellement lance une fusion.

Si le débit de l'indexation est important, par exemple lors de la (ré)indexation des lots, il n'est pas très productif de passer beaucoup de temps à vider et à fusionner de petits segments. Par conséquent, dans certains cas, il est, en règle générale, judicieux d'augmenter temporairement le paramètre refresh_interval, voire de désactiver complètement l'actualisation automatique. Il est toujours possible de procéder à une actualisation manuellement ou de la réactiver une fois l'indexation terminée.

Index Elasticsearch

"En informatique, tous les problèmes peuvent être résolus par un autre niveau d'indétermination." – David J. Wheeler

Un index Elasticsearch est composé d'une ou de plusieurs partitions, qui peuvent avoir des répliques, voire aucune. Toutes sont des index Lucene. En d'autres termes, un index Elasticsearch est composé de nombreux index Lucene, qui eux-mêmes sont composés de segments d'index. Lorsque vous menez une recherche dans un index Elasticsearch, celle-ci est exécutée dans l'ensemble des partitions, puis dans l'ensemble des segments avant leur fusion. Cela vaut également pour les recherches dans plusieurs index Elasticsearch. Plus précisément, mener une recherche dans deux index Elasticsearch comprenant chacun une partition revient peu ou prou à mener une recherche dans un index composé de deux partitions. Dans les deux cas, la recherche est exécutée dans deux index Lucene sous-jacents.

À partir de maintenant, le mot "index" désigne un index Elasticsearch dans cet article.

Une "partition" est l'unité de scaling de base pour Elasticsearch. Lorsque les documents sont ajoutés à l'index, il est acheminé vers une partition. Par défaut, cette opération s'effectue en alternance, selon le hachage de l'identifiant du document. Dans la deuxième partie de cette série d'articles, nous expliquerons plus en détail pourquoi les partitions sont déplacées. Toutefois, il est important de savoir que le nombre de partitions est précisé lors de la création de l'index et ne peut plus être modifié ultérieurement. Une première présentation d'Elasticsearch par Shay Banon explique très bien pourquoi une partition est en réalité un index Lucene complet, mais aussi présente ses différents avantages et compromis par rapport à d'autres méthodes.

Il est possible de personnaliser de nombreuses façons les index d'Elasticsearch, mais aussi les partitions (et les répliques) auxquelles les requêtes de recherche sont envoyées. En associant les modèles d'indexation, les alias des index, ainsi que le routage des recherches et des documents, de nombreuses stratégies de flux de données et de division en partitions peuvent être implémentées. Nous ne les détaillerons pas dans cet article. Toutefois, nous vous recommandons de lire l'article de Zachary Tong consacré à la personnalisation du routage des documents et de regarder la présentation de Shay Banon sur le big data, la recherche et l'analyse. Voici quelques exemples qui peuvent vous donner des idées :

• De nombreuses données sont temporelles, notamment les logs et les tweets. En créant un index chaque jour (ou chaque semaine ou mois), nous pouvons limiter les recherches en toute efficacité à certaines périodes et supprimer les anciennes données. N'oubliez pas qu'il nous est impossible d'effectuer des suppressions efficaces depuis un index existant. Cependant, la suppression d'un index entier ne coûte pas cher.
• Lorsque les recherches doivent être limitées à un ou une internaute spécifique (par exemple la recherche de messages personnels), il peut être utile d'acheminer l'ensemble des documents de cette personne dans la même partition afin de réduire le nombre d'index où la recherche doit être exécutée.

Transactions

Lucene comprend un concept de transactions, contrairement à Elasticsearch. Toutes les opérations menées dans Elasticsearch s'inscrivent dans le même échéancier, qui n'est pas toujours entièrement cohérent au sein de tous les nœuds, car le vidage repose sur une chronologie précise.

Il est très difficile de gérer l'isolation et la visibilité des différents segments, caches et autres éléments dans les index contenus au sein des nœuds d'un système distribué. Au lieu de cela, la vitesse est privilégiée.

Elasticsearch est doté d'un "log de transaction" dans lequel les documents à indexer sont ajoutés. Ajouter un fichier de log coûte bien moins cher que créer des segments. Par conséquent, Elasticsearch peut écrire des documents à indexer dans un emplacement durable, en plus de la mémoire tampon qui échappe aux pannes. Vous pouvez également préciser le niveau de cohérence requis lors de l'indexation. Par exemple, vous pouvez exiger que chaque réplique indexe le document avant l'opération d'indexation.

Résumé

En résumé, voici les importantes propriétés à connaître quant à la manière dont Lucene conçoit des index sur un seul nœud, les met à jour et y mène des recherches :

• La recherche que nous pouvons mener dépend de la méthode de traitement du texte que nous indexons. Il est important d'analyser le texte de manière appropriée.
• Les index sont tout d'abord créés dans la mémoire, puis vidés occasionnellement dans les segments sur le disque.
• Les segments d'index sont immuables. Les documents supprimés sont marqués en tant que tels.
• Un index est composé de plusieurs segments. Une recherche est menée dans chaque segment, puis les résultats sont fusionnés.
• Les segments sont fusionnés occasionnellement.
• Les caches des filtres et des champs sont créés par segment.
• Elasticsearch ne comprend pas de transaction.

Dans le prochain article de cette série, nous expliquerons comment mener une recherche et effectuer une indexation dans un cluster.