Moteur de recherche [veille]

le

Il est réducteur de considérer une base de données comme une machine à stocker des données. La base de données est responsable de la cohérence de ses éléments, mais permet surtout d'effectuer des recherches. Pour chercher efficacement, il n'y a pas 36 solutions, il faut de beaux index, ainsi que de la dénormalisation, deux notions très proche. Itérer sur l'intégralité du contenu n'est pas une solution viable, même en abusant de RAM, de SSD ou de JavaScript (comme dans Mongodb ou Riak...). Il va bien falloir indexer à un moment ou à un autre si l'on veut pouvoir effectuer des recherches rapidement. Les contraintes matérielles (disques durs à plateaux ou SSD avec leur débit, temps de déplacement de la tête, cycle d'écritures sur un bloc, redondances, les CPUs avec les possibilités de parallélisations...) sont des critères déterminants pour les choix d'implémentations. Il est possible de se contenter d'index simple (sur une ou plusieurs colonnes), de maintenir leur ordonnancement, mais aussi d'utiliser des choses plus complexes comme les coordonnées géographiques ou la recherche full texte.

Un moteur de recherche est donc un bel index, avec des spécificités et des concessions. L'arrangement le plus répandu est d'effectuer une partie du travail de manière asynchrone. La plupart des outils de recherches full text sont un tout petit peu en retard, par rapport à la persistance, mais tout le monde s'en fiche, garantir une cohérence de la réponse est plus important que de s'acharner à vouloir faire tout, tout de suite. Un moteur de recherche prends un peu de temps lors de la phase d'écriture, pour ensuite en gagner beaucoup lors de la recherche.

Certains moteurs sont intégrés à la base de données, comme Postgres, qui veut intégrer TOUT, sur une seule machine, par ce que c'est comme ça que l'on faisait dans les années 70. Riak possède aussi des fonctions intéressantes d'indexation, et vu les volumes qu'il prétend gérer, c'est un choix plutôt sage. Essayez donc de chercher un bouquin à la BNF en les feuilletant un par un. D'autres bases, comme Cassandra, sont conçu à l'envers, comme un gros index pouvant aussi être utilisé pour de la persistance, une approche dites de "base orientée colonnes" (les bases classiques sont dites "orientée lignes").

Il existe aussi des index autonomes, qui accompagnent une solution de stockage. Les plus connus sont Solr et Elastic Search, mais Redis peut aussi être rangé dans cette catégorie d'index annexe. La connexion entre ces deux éléments peut se faire au niveau de l'ORM, qui pousse les informations dans les deux moteurs (persistance et index), sous forme de plug-ins, ou via des astuces, comme le moteur de recherche qui se fait passer pour un esclave du moteur de persistance.

La notion de full text n'est maintenant qu'une des spécialités que peut avoir un moteur de recherche. Sphinx, ou Xapian peut être, restent monotache, faisant confiance à son hôte pour les autres types d'index. La gestion des facettes ou de la recherche géographique font maintenant partie des classiques. La tendance actuelle est d'ailleurs de fournir un produit complet, plutôt qu'un framework sur lequel construire sa propre solution. Lucene est un très beau framework, agréable à lire et à tuner, mais dans la vraie vie, il se révèle être extrêmement chronophage alors que les applications basées sur Lucene, comme Solr et Elastic Search sont simple à mettre en place et apportent des fonctions "inclus dans la boite" bien agréable à utiliser tel quel.

Produits historiques

htdig, mnogosearch, swish-e, sphinx ... sont des produits sympathiques, mais obsolètes. Ils ont servi d'étapes dans l'histoire de l'informatique, ouvrant la voie à des solutions contemporaines. Il faut de toute façon se méfier des solutions de recherches qui passent par un cron pour aspirer la base. On pense gagner du temps lors de la mise en place, puis lorsque l'on commence à atteindre des volumes conséquents de donnée, on commence à avoir des regrets en voyant les temps interminables d'indexation, ou pire, de réindexation ralentissant à l'extrême l'ensemble de l'application.

Produits à base de Lucene

Lucene est écrit en java, cause bien connu d'angoisses et de fantasmes (bien réels il faut le reconnaitre, comme son appétit pour la RAM). Il existe des clones en différents langages, comme python (pyLucene), ruby (ferret), C (clucene) et même C# (lucene.net) mais aucun n'est vraiment fini ni utilisable. Aucun n'est comparable à l'implémentation de référence, en Java. La partie index inversé de Lucene est assez facile à cloner, alors que la partie traitement du langage est extrêmement laborieuse à reproduire.

Solr a trouvé une solution pour apporter la puissance de Lucene hors du monde Java : un serveur REST emballant tout ce que propose Lucene. La conception de Solr a été violente, bien dans l'esprit Java, avec des tonnes de XML et des fichiers de confs ambigus. Au fil du temps, le produit s'est affiné, en intégrant maintenant du JSON et en proposant maintenant un système de réplication décent. Dans sa version précédente, la 3, la réplication entre 2 serveurs se faisait en rsync, avec un gros tas de script shell pour emballer le tout. Il existe même une variante en bitorrent utilisé par Etsy. Dans la version 4, poussé au cul par Elastic Search, Solr sait gérer la réplication au fil de l'eau, avec une communication de serveur à serveur, et propose aussi du sharding (répartition avec redondance des données sur plusieurs serveurs). Il faut reconnaitre que Solr a démocratisé la notion de facettes. La parabole est simple, une recherche est un diamant brut, que l'on affine au fur et à mesure, facette par facette. Les facettes sont beaucoup utilisées pour fouiller dans les catalogues de produits, où l'on affine au fur et à mesure sa sélection, en cliquant pour rajouter des critères : "je veux un pantalon ... taille 42 ... en noir", à chaque étape on voit le nombre de réponses possibles s'amenuiser et les critères disparaitre à chaque fois que l'on précise la recherche. Solr a servi à décoincer Lucene qui s'était empêtré dans Java 1.4, en proposant des extensions et un terrain de jeu pour les expérimentations. Lucene 4 est sorti du laboratoire que lui a offert Solr.

Solr est bien revigoré dans sa version 4, mais il conserve quelques points pénibles, comme les tartines de configuration pour définir ses mappings, mais il bénéficie de son expérience, sa documentation existe, et on peut le mettre en place sans trop de difficultés (à part peut-être la mutualisation) pour ensuite tourner sans trop de surprises. Son véritable atout et sa très belle intégration dans des CMS comme Drupal.

Depuis la sortie d'Elastic Search, l'autre application basée sur Lucene, la compétition est très agressive entre l'ancien et le challenger, les innovations de l'un se retrouvent dans la version suivante de l'autre, avec un avantage pour Elastic Search qui profite de son cycle de release très court.

Il existe une excellente comparaison, point à point sur le blog de Sematex une très belle comparaison en 5 tomes, écrit petit, par l'un des spécialistes Lucene.

Elastic Search est le fruit d'un seul homme, Kimchi. Il a débuté sous la forme d'un framework, Compass, emballant de manière fort élégante Lucene (exposant une interface Java 5 s'appuyant sur une bibliothèque Java 1.4) et proposant surtout une belle intégration à Hibernate, le magnifique ORM qui sauva Java des EJB. Compass a évolué en proposant d'indexer directement des données en JSON, puis finalement muta pour devenir Elastic Search, une application REST, complètement dans l'esprit web 2.0 toutes options (cluster, cloud, json, yaml, auto réparation, sharding...). Elastic Search est maintenant, tout en restant open source, une entreprise : Elasticsearch.com. Il commence à collectionner de belles références : Mozilla, Stack Overflow et maintenant Github.

Une attention toute particulière est apportée à la documentation (avec des exemples en curl, gage de neutralité), et à l'innovation. Elastic Search apporte des notions un peu étranges telles que la percolation ou les rivières qui permettent de se connecter à un flux de données.

Elastic Search est une application (qui s'occupe tout seul de beaucoup de chose, dont le sharding et la distribution du travail) mais s'utilise comme un framework. Ses différents bindings ont chaque fois de fortes personnalités et portent une attention toute particulière aux spécificités du langage. Tire propose une très belle interface à Ruby, proche d'un DSL, pyES propose quelque chose de plus traditionnel à Python. En nodejs, node-elasticsearch-client propose quelque chose de plus, euh, évènementiel.

La vraie force d'Elastic Search est d'exposer toute la puissance de Lucene dans le langage que l'on aime, tout en s'occupant de l'arrière-cuisine. J'avais fait des essais pour gérer les spécificités du français, par exemple, ou l'autocomplétion.

Parmi les fils de Lucene, il existe aussi Nutch, qui a maintenant plus un intérêt historique. Ce projet avait la volonté de proposer une alternative open source à Google, rien que ça. Hadoop, implémentation libre de référence du pattern map/reduce, est issu de cet ambitieux projet. Nutch propose aussi un aspirateur, enfin, un web scrapper.

Produits indépendantistes

Tirer Java comme dépendance n'amuse pas tout le monde. Utiliser une grosse application Java quand on n'a pas assez de mémoire et de processeur n'est pas raisonnable, comme dans le cadre d'une application embarquée ou bureautique par exemple.

Sqlite propose un index full text tout à fait décent : fts et python a son moteur natif, Whoosh. Pour des besoins un peu plus conséquents, il existe Xapian et le tout nouveau Groonga.

Je reproche à tous les produits non Lucene leur anglocentrisme. Groonga sait bien découper du japonais, mais bon, pour un produit japonais, arriver à découper les mots est juste un prérequis, pas un effort d'internationalisation.

Groonga est un nouveau venu, se présentant comme un index inversé, une base orientée colonne, sachant indexer en full text et gérer des coordonnés géographiques. Une solution d'index ultime. Groonga est particulièrement inventif dans sa façon de se brancher dans à peu près tout et n'importe quoi. Il peut être un moteur de stockage pour mysql et postgres, une bibliothèque en C avec un binding ruby, un serveur TCP avec son propre protocole, un serveur REST, un serveur Memcache (utilisant la variante binaire de son protocole), ainsi qu'un serveur zeromq. Le tout en LGPL.

Conclusion

La recherche est un domaine complexe, qui peut se transformer en puits sans fond. Ce domaine fréquente le traitement du langage, la linguistique, la sémantique, les statistiques, l'apprentissage machine, et plein d'autres choses tout aussi passionnantes.

La mode est aux big datas et donc à la big recherche.

Dans un moteur de recherche, il y a plein de petites finesses pouvant faire la différence, comme l'ergonomie, la pertinence des résultats, ou l'intégration à l'application, ainsi que la personnalisation des réponses, qui est la tendance actuelle. Un moteur de recherche permet de faire bien plus de choses que de proposer, un simple champ libre pour y taper quelques mots comme faisait Google à son début. Ce genre de moteur permet aussi de faire des analyses, des suggestions, du rangement, établir des relations, bref, c'est une brique parmi d'autres à assembler pour construire quelque chose correspondant à son besoin.

Se contenter de rechercher avec un moteur de recherche c'est tellement an 2000.


Partager cet article :