Faceted SeSQL : la navigation par facettes pour Django

La navigation par facettes ?

Selon Wikipedia :

La recherche à facettes (ou recherche facettée, ou navigation à facettes) est une technique en recherche d'information correspondant à une méthodologie d'accès à l'information basée sur une classification à facettes. Elle donne aux utilisateurs les moyens de filtrer une collection de données en choisissant un ou plusieurs critères (les facettes). Il n'est donc pas tant question de recherche que de filtrage (une recherche brute, taxonomique, pouvant être utilisée en complément). Une classification à facettes associe à chaque donnée de l'espace de recherche un certain nombre d'axes explicites de filtrage, par exemple des mots clés issus d'une analyse texte, des métadonnées stockées dans une base de données, etc. On trouve par exemple des recherches à facettes basées sur des catégories sur de nombreux sites de e-commerce.

Il s'agit donc d'associer différents critères à une collection d'objets, et ensuite de laisser l'utilisateur choisir les critères qui l'intéressent. Par exemple pour une base de données d'appareils photos numériques, on aurait comme critère le type d'appareil (compact, bridge, reflex), le niveau de zoom optique, le nombre de mégapixel, la sensibilité ISO maximale, la surface des capteurs, le type de capteurs, le poids, le prix, la marque, ...

Un peu d'histoire

Pilot Systems avait déjà réalisé un produit de recherche par facettes pour Plone : Faceted Navigation, avec une démonstration en ligne : les burgers.

SeSQL en back-end

Les facettes correspondent souvent à des attributs des objets, mais dans certains cas le calcul des facettes peut être plus compliqué. Par exemple, si nous avons des objets vendus par différents magasins, et des horaires d'ouverture liées aux magasins, on peut vouloir les horaires d'ouverture comme une facette possible sur les objets.

De plus, les facettes peuvent souvent être multi-valuées (par exemple, les ingrédients d'une pizza), et les bases de données SQL classiques sont peu optimales dans le traitement des champs multi-valués.

Par chance, il existe un produit Django gérant ces subtilités et bien d'autres : SeSQL, le moteur de recherche développé par Pilot Systems pour Libération (et utilisé sur de nombreux autres de nos projets).

SeSQL gère déjà une couche d'indexation, permettant de stocker des valeurs calculées dynamiquement, gérant les champs multi-valués via des arrays PostgreSQL et prenant en charge la réindexation asynchrone des dépendances (si les horaires d'ouverture d'un magasin sont modifiées, tous les objets vendus par ce magasin doit être réindexés).

La décision a donc été prise de construire le produit de navigation par facette au-dessus de SeSQL, réutilisant donc tout sa partie moteur d'indexation.

Un graphe en mémoire

Le deuxième choix d'architecture est plus bas niveau. Pour obtenir des performances optimales, il a été décidé de garder un graphe en mémoire des objets et des facettes, et de n'utiliser la base de données que de manière exceptionnelle.

Ce mode de fonctionnement permet de très grandes performances, mais possède deux inconvénients :

1. Il est nécessaire de stocker tous les objets en mémoire, ou plus exactement, toutes les facettes des objets (les informations lourdes, comme la description ou les images associées, ne sont elles pas chargées en mémoire). Cependant, même en contant 1ko par objet, une base de données d'un million d'objets ne nécessite que 1Go de mémoire, ce qui est parfaitement raisonnable de nos jours, surtout vu le volume (un million d'objets dans le catalogue).
2. Il est nécessaire de recharger les données lorsque des modifications sont effectuées. Ce mode de fonctionnement est donc l'idéal pour les configurations "read many, write few" qui sont typiques des sites grand public, mais ne l'est pas pour des situations où les écritures sont nombreuses, ce qui peut être le cas des intranets ou sites communautaires.

Pour pouvoir s'adapter à d'autres situations, il est envisageable de modifier Faceted SeSQL pour lui permettre d'utiliser différents back-end, un basé sur les graphes en mémoire comme actuellement, et un autre basé sur les recherches SeSQL (donc via la base de données). Le développement n'a pas encore été effectué, mais Faceted SeSQL est conçu pour que cette modification soit possible sans modifier l'API.

Décompte des résultats

Une fonctionnalité agréable pour l'utilisateur dans une navigation par facettes est le décompte des résultats par critère, en prenant en compte les autres critères sélectionnés. Le meilleur moyen de comprendre est d'aller sur le site de démonstration et de regarder comment les nombres entre parenthèses évoluent quand on choisit certains critères.

Cette fonctionnalité est cependant assez délicate à calculer, car elle nécessite de calculer pour chaque facette la liste des résultats disponibles si on avait choisi tous les autres critères à l'identique, sauf cette facette là. Implémenté de manière "bourrine", si on choisit des critères dans 5 facettes, il faut faire 5 recherches avec 4 facettes de renseignées à chaque fois.

L'astuce pour effectuer ce décompte de manière efficace consiste à utiliser les sets Python et de faire un comptage incrémental : initialement, on crée une liste d'objets valides par facette O(F) contenant tous les objets. Puis on traite les facettes une à une, pour chaque facette F :

1. On calcule la liste des objets qui sont exclus par les valeurs choisies pour la facette F. Cette liste ce nomme E(F).
2. On enlève de tous les O(F') pour F' != F le contenu de E(F).

Cet algorithme permet de ne calculer E(F) (la liste des objets exclus par une facette) qu'une seule fois par facette, et c'est ce calcul qui est le plus long.

Faceted SeSQL implémente une variation de cet algorithme afin d'avoir des performances optimales.

Synchronisation des modifications

Le deuxième soucis concerne la synchronisation des modifications entre plusieurs instances. Rappelons-nous : le graphe est construit en mémoire, et lorsqu'un objet est modifié, il est alors mis à jour. Mais que se passe-t-il si plusieurs processus utilisent la même base de données (quelque soit la méthode de déploiement choisie) ?

La solution consiste à utiliser memcached pour s'assurer de la cohésion du graphe en mémoire : un numéro de version est stocké dans un serveur memcached, et incrémenté à chaque modification des données. Lors de l'utilisation du graphe en mémoire, la numéro de version est comparé avec le numéro de version utilisé pour générer le graphe, et s'il ne s'agit pas du même, le graphe est reconstruit.

Afin d'éviter une race condition si deux modifications sont faites au même moment, l'incrémentation du numéro de version est fait de manière atomatique via la primitive memcached incr.

Ajax et non-Ajax

Facetted SeSQL fournit deux interfaces, utilisables dans les templates du site : une interface classique, avec un bouton pour soumettre le formulaire et recalculer les résultats, et une interface en Ajax où tous les résultats sont mis à jour en temps réel à chaque clic d'un nouveau critère.

La version Ajax s'appuie sur JQuery.

Centralisation des données

Actuellement, le memcached n'est utilisé que pour vérifier que le graphe est bien à jour. Il serait envisageable, dans une version future, de l'utiliser aussi pour permettre d'éviter d'avoir à calculer le graphe une fois par processus.

Cache de requêtes fréquentes

Une fonctionnalité prévue pour une version future mais non encore implémentée est un cache des requêtes fréquentes. Ce cache est particulièrement intéressant car Facetted SeSQL est capable de gérer des recherches incrémentales. Avec un algorithme intelligemment conçu, il pourrait donc localiser la recherche la plus proche de la recherche demandée qui est présente dans le cache, et compléter à partir de ce point.