August 12, 2009

Nouveau moteur de recherche pour Le Monde en Tique

Il y a quelques semaines nous avions améliorer la pertinence des résultats pour le moteur de recherche de la Librairie Le Monde en Tique en mettant en place un scoring des résultats.

Il restait encore un petit problème de lenteur sur des requêtes comportant beaucoup de mots (notament des mots se trouvant dans beaucoup d'ouvrages).

La casse tête était intéressant: comment trouver les ouvrages comportants une série de mots (avec un nombre de mots recherchés pouvant être important) quand on attaque une base Postgresql qui comporte 325 000 ouvrages. Cela représente un peu plus de 1 million de mots différents et 27 Millions d'occurrences. Et en les classant par score descendant bien sur. Certains mots ont plus de 100 000 occurences !

On avait laissé tombé il y a quelques mois Lucene en version GNUstep: après avoir corrigés tous les bugs et problèmes de mémoire on n'a finallement jamais dépassé les 20 000 ouvrages indexés....

Du coup on avait finit par mettre l'indexation dans Postgres. Mais le nombre d'ouvrage à triplé en moins de 6 mois du fait de l'importation automatisé (merci Onix !) de plusieurs grands éditeurs et distributeurs (etranger pour beaucoup, les éditeurs francais capables de fournir des fichiers Onix étant pour le moins limité).

Bref, la problématique à la base est simple: on a par exemple 10 mots présents respectivement dans 100 000, 25 000, 40 000, 5 000, 75 000, 8 000, 7 000, 12 000, 60 000, 55 000 ouvrages et il faut trouver les ouvrages communs.
On a 1 enregistrement code mot/code ouvrage.
la methode basique c'est de prendre les ouvrages du 1er mots, d'enlever ceux qui ne sont pas présent dans le 2eme puis dans ceux restant ceux qui ne sont pas dans le 3eme et ainsi de suite. C'est la fonction "intersect" du sql.

Un moyen d'aider un peu le process est de commencer par le mot présent dans le moins d'ouvrages, puis d'aller en nombre d'ouvrages croissant. Encore faut il pouvoir déterminerrapidement quel mot à le moins d'ouvrages ce qui n'est pas forcement pratique.

On a commencé par essayer d'optimiser Postgresql en lui allouant plus de mémoire; Sur le coup cela n'a pas changé grand chose mais 2 ou trois semaines après, son planneur a du prendre en compte les dernières statistiques et cela a quand même bien améliorer la rapidité.

Mais bon, on pouvait arriver à 30s sur une expression comme "information needs of engineers involved the development and improvement of this extremely important and rapidly changing technology" et 28s sur "Éditions de la Maison des sciences de l'homme - Paris"

Un peu long :-(

Le principe de memcached est attrayant: on met l'ensemble de la base des occurences en ram et ca devrait être plus rapide. Hélas memcached ne fait pas la reduction (le "intersect"). Par contre un autre outil du même type le fait: redis. Eureka !

Telechargement, compilation, corrections, compilation, installation et... tests.
Fonctionnellement c'est nickel: on le renseigne avec les occurences et il fait les reductions très bien et vite sur quelques 10aines de milliers d'occurences.
Mais il y a un hic (la vie d'un informaticien est truffé de hic hélas): en extrapolant le nombre d'occurences utilisées pour le test pour le nombre d'occurences necessaires en réalité (27 Millions) on voit vite qu'on dépasse les 10Go de RAM notament parceque redis ne traite que des chaines de caractères.

Retour à la case départ.

Enfin pas vraiment: si on conserve l'idée de base (monter la base des occurences en RAM), organisée de la façon la plus adaptée pour notre besoin tout en gérant la mémoire avec parcimonie ca peut peut-être coller.

La base du probème étant en gros la comparaisons de nombres entiers, voyons déjà la lenteur ou la rapidité de cette opération (en C pas en PHP, hein :-)

Et hop un petit test qui montre qu'une boucle sur plusieurs millions d'entiers se fait en une fraction de seconde (c'était juste pour être sur: quand on veut bosser sur des millions d'enregistrements autant ne pas partir sur de mauvaises idées).

Bon ensuite on a 2 nombres importants: le nombre de mots différents et le nombre d'occurences.
Le nombre de mots différents pese au final assez peu: même 2 millions d'entiers 32 bits ca ne fait que 8Mo et c'est notre clef primaire. Même en rajoutant mettons 4 pointeurs par mot on a au plus, en 32 bits, 40Mo de données c'est jouable; D'autant plus que le nombre de mots n'augmentera pas autant que le nombre d'occurences.

Par contre sur les occurences il faut faire au plus juste: avec 30 Millions d'occurences, ajouter un int32 ou un pointeur sur chaque c'est tout de suite 120Mo de RAM en plus.

Dernier paramètre: faut-il prévoir une mise à jour de cette base en mémoire ?
Pour: pas besoin de recharger la base régulièrement (plusieurs 10aines d'ouvrages arrivant chaque jours) et base toujours up-to-date.

Contre: ca complexifie, il faut ajouter des locks, prévoir une gestion de la mémoire plus fine pour notament éviter la fragmentation, cela aura un impact sur la recherche quand une mise à jour ce fait....

Question: en combien de temps charge t on la base ? Si ca met 5mn ca va, on peut batcher ca la nuit; si ca met 24h c'est plus problématique.

Bref encore un test à faire.

Résultat: ca devrait prendre au plus une 15aine de minutes. Donc exit la mise à jour. D'autant plus que la complexitée induite aurait signifiée un développement et une validation plus longue.

A partir de la on peut creuser plus avant la methode de stockage en ram.

Pour récapituler:
- le stockage des mots peut-être évolué vu l'impact mémoire et il doit l'être vu que c'est quand même notre clef primaire, si on peut éviter une boucle de 1M d'occurences c'est deja ca de gagné.
- le stockage des occurences par mot doit être plat (ou quasiment vu le volume).
- on doit pouvoir déterminer rapidement le nombre d'occurences pour un mot afin de déterminer par quel mot commencer (celui qui a le moins d'occurences).
- faire simple et robuste: c'est un serveur qui ne doit pas crasher

Donc on opte pour une hash table en limitant quand même la taille de la table (compromis taille mémoire/temps de recherche) qui est un nombre premier (si on prend une taille de 100 663 319 pour pour une utilisation relle de 52 000 000 on perd tout de suite quelque chose comme 700Mo...
On récupere d'abord le nombre de mots différents histoire de figer la structure afin d'éviter du code de rebalancement de la table et de fragmenter la mémoire (il n'y a pas de petit profit)

Chaque entrée va comporter le code mot (notre clef de hashage; d'ailleurs on gagne tout de suite 4 octets par mot vu qu'on n'a pas besoin de stocker le hashage), un tableau des occurences associées (un int4 pour le code ouvrage, un int4 pour la propriété et un in4 pour le score), le nombre des occurences et un pointer vers le next node. Soit 16 octets par mot + 16 octets (avec l'alignement) pour chaque occurence (plus les le tableau de hashage de 1572869*4 octets pour le million de mots.

On accede au nombre d'occurence d'un mot et aux occurences de ce mot de facon quasi immédiate (en gros une division pou trouver l'entrée correspondant au hash pui au pire quelques comparaisons).
Histoire de limiter la casse sur la recherche des occurences ensuite, celles-ci sont triées par code ouvrage comme ca dès qu'on a atteint un code ouvrage supérieur au code recherché on peut s'arreter (bon, on pourrait proceder en plus par dichotomie, c'est un joker a garder sous le coude si besoin est).

Et voila, le choeur de la bête est là.
Ca tient sur 1.4 Go en ram et la recherche est ultra-rapide.
Faudrait creuser d'ailleurs: pourquoi 1.4Go alors qu'on devrait être autours de 600Mo...

Reste ensuite à faire l'interface de communication.
3 choix:
- redévelopper un truc ex-nihilo
- se servir de l'interface de memcached ou redis
- autre

Finallement j'ai opté pour une interface testée, connue et standard: XML-RPC avec les composants GNUstep (vu que le client visé est GNUstep et que de toute facon il y a des librairies XML-RPC pour la plupart des language).

Ca fait un peu bizarre de pinailler pour un millieme de seconde et 2 octets sur le coeur et d'utiliser du haut niveau pour l'interface mais bon, la partie interface peut
être changée sans trop de problème si le coût est trop grand.

Derriere ca un petit coup de valgrind histoire de vérifier qu'on a pas de fuite de mémoire ou de bug trop visible. Quelques corrections, évidement.

Puis des tests (genre des 10aines de milliers de requetes sur des mots au hasard et en nombre differents).
Re corrections (et oui, c'est la dure vie du développeur).

On vérifdie que la mémoire ne bouge pas d'un octet.

Et hop c'est prêt !

Après tout ca, la réalisation de la partie client est triviale (merci GNUstep) et sont intégration à eCommStep le moteur du site du Monde en Tique est assez vite faite.
On prévoit quand même un fallback sur la recherche direct en base si le serveur ne répond pas (crash, rechargement de la base, intervention démonique ou autre)

Re-test et comparaison (histoire de valider le tout, ce serait bête d'être ultra-rapide mais de retourner des résultats érronés ou incomplets) et ca roule !

Résultats:

Mise en mémoire de la base: 7mn91 (ca charge un peu Postgres mais batché à 4 ou 5h du matin c'est indolore.

Recherche sur:
"information needs of engineers involved the development and improvement of this extremely important and rapidly changing technology"
Avant: 30.2601 s
Apres: 0.0260 s

Recherche sur: "programmation en java"
Avant: 3.2589 s
Apres: 0.0579 s

Recherche sur "Éditions de la Maison des sciences de l'homme - Paris"
Avant: 28.3312 s
Apres: 0.7767 s


(en temps de recherche brut une fois qu'on a récupéré les enregistrements correspondants à chacun des mots mais cette opération ne prend qu'une fraction de secondes).

Après quelques heures, on peut voir que toutes les requetes sont restées en dessous de 1s.


Et voila; Next job please !

Et merci à Jean Demetrau pour le challenge, Dolaur Crozon Cazin et Nicolas Guillouet pour nos discussions sur le sujet.
Posted 8 years, 6 months ago on August 12, 2009
The trackback url for this post is http://mguesdon.oxymium.net/blog/bblog/trackback.php/143/

Re: Nouveau moteur de recherche pour Le Monde en Tique
Réponse au "Faudrait creuser d'ailleurs: pourquoi 1.4Go alors qu'on devrait être autours de 600Mo...": c'est simple au final: c'est la ram temporairement prise par les resultat des requetes postgresql; ram qui n'est libérée qu'à la fin de l'application...
Posted 4 years, 9 months ago by Manuel Guesdon • • • Reply
Comment Trackback URL : http://mguesdon.oxymium.net/blog/bblog/trackback.php/143/6089/

Comments have now been turned off for this post