Comment j’en suis arrivé à développer ma propre base graphe :

Cet article est un retour d’expèrience plus d’un an après le début du développement.

Disclaimer : troll et subjectivité vous attendent et peut-être quelques informations, qui sait ?

Il était une fois un algorithme de recommandation

L’an dernier, j’ai eu l’occasion de développer une base de données graphe en pur Python dans le cadre du projet que je faisais avec une société Nantaise spécialisée dans la veille de marché publics et la mise en relation d’entreprises : Jurismarchés.

Dans ce projet, il fallait développer un algorithme de recommandation pour proposer des marchés publics similaires à ceux qui avaient été consultés par l’utilisateur, ce qui n’est pas un problème en soi mais qui le devient rapidement lorsque le volume de documents en base de données est important (dans ce projet, il y en avait plusieurs millions).

Les principes de bases étaient simples : extraire les contenus textuels des documents à disposition, tokeniser ces documents, supprimer les tokens sans valeurs ajoutées (par exemple les articles : ‘le’,’la’, ‘les’, etc…), indexer les documents en fonction des tokens, puis identifier des documents similaires grâce à des principes simples, par exemple :

• grand nombre de token communs
• grand nombre de token à forte valeur ajoutée (ceux dont la fréquence dans le document est bien supèrieure à la moyenne des fréquences dans l’ensemble des documents)

Bref, utiliser des principes “classiques” de l’analyse de langage naturel (si vous êtes intéressé par le sujet, je vous recommande chaudement de regarder NLTK).
Il m’a fallu tatonner un peu avant de concevoir un système de recommandation pertinent mais je ne rentrerais pas dans les détails ici.

La question s’est alors posée de sérialiser les données dans une base de donnée pour éviter de charger toutes les données en mémoire à chaque fois que je voulais faire fonctionner l’algorithme, puis d’écrire LA requête qui allait magiquement produire, à partir d’un ou plusieurs documents donnés, une liste de documents à recommander.

Les bases de données relationnelles n’étaient clairement pas adaptées : il aurait fallu, à un moment, faire au moins 5 jointures sur des tables de plusieurs millions de lignes ce qui aurait posé des problèmes importants de performance, le but étant de proposer des recommandations en moins de 100ms.

Passionné par les algorithmes de graphes et les bases graphes depuis la lecture de ce livre, je me suis alors tourné vers les graphes en me disant qu’il devait être possible d’en faire quelque chose d’utile.

Travaillant quasi exclusivement avec Python, je me suis alors tourné vers NetworkX, magnifique librairie de manipulation de graphes, fournie avec un grand nombre d’algorithmes bien implémentés et documentés… heureuse inspiration : en implémentant mes algorithmes de recommandation avec NetworkX, j’obtenais les performances attendues.

Mais, problème, NetworkX fonctionne exclusivement en mémoire (du moins la version officielle, il y a eu des tentatives de fork pour ajouter de la persistence mais qui ne sont pas allés très loin) et il fallait attendre plusieurs minutes pour charger entièrement le graphe en mémoire… hum… difficillement compatible avec une version de production utilisant Django en frontend dont chaque process possèderait sa propre version du graphe en mémoire (qui représentait plusieurs Go de données)

Bref, j’étais arrivé au point où :

• J’avais un algorithme de recommandation qui fonctionnait en s’appuyant sur un graphe
• Je pouvais charger ce graphe en mémoire
• Mais chaque worker web avait sa propre version du graphe, chacune prenant plusieurs Go en mémoire
• Les différentes versions de graphe devenaient rapidement incohérentes (ah oui, j’ai oublié de le préciser : en permanence des nouveaux documents étaient ajoutés et induisait l’ajout de noeuds et de liens)
• Et dernier point, le plus angoissant, pour tout devops : la possibilité d’un crash qui auraient fait perdre le graphe mémoire et aurait nécessité un rechargement complet, bloquant de facto le système de recommandation pendant plusieurs minutes et ce pour chaque worker Web… pas glop

Donc, pas le choix : il fallait trouver un serveur de base de données graphe, idéalement en Python.

A la recherche de la base graphe idéale

Après quelques recherches Google, je me rends à l’évidence :

Si on veut utiliser une base graphe Open Source, on est quasiment obligé d’utiliser une base Java

langage auquel je suis particulièrement réticent (trop verbeux, trop lourd, pas drôle), fort heureusement, il existe des bindings Python pour la plupart des bases graphes et même une librairie (Bulbs) qui permet de construire des modèles (à la Django) et qui permet de créer des requêtes simples.

Je commence donc par jouer avec Bulbs et Neo4J… bonnes impressions de départ :

• Neo4J semble être un produit bien fait :
  • il est possible de visualiser ses noeuds et ses relations dans un navigateur, le langage de requête est bien fait, on sent qu’il est clairement inspiré par le SQL
  • ça semble faire le taf mais les performances sur mes algos de graphe ne sont pas terribles :de 10 à 100x moins bien que mon implémentation avec NetworkX
• Bulbs est également un beau projet : je peux me connecter rapidement à la base Neo4J, ajouter des noeuds, ajouter des relations, tout ça en pure Python

Mais rapidement, je déchante :

• Les performances ne sont pas au rendez vous
• (Je suis probablement mauvais mais) Je ne trouve pas de moyens de dumper une base dans un fichier avec un format sympa sans provoquer ces exceptions Java qui me font vomir depuis mes premières expèriences avec Tomcat - certes, je pourrais copier la base si un jour, je souhaite la relocaliser sur une autre machine, mais cette solution ne me plait pas (par expèrience, les formats binaires peuvent rapidement être une plaie,spécialement, quand la version qui l’a généré n’est plus disponible)
• Il est assez rapidement nécessaire d’écrire des requêtes avec le langage de requêtes avant de les envoyer par Bulbs <=> assez rapidement, on n’a plus l’impression d’écrire du Python et, a contrario, on se fait envahir par le langage de requête et notre code devient moche : impression de mélanger du HTML avec un langage de prog web populaire si vous voyez ce que je veux dire :p

Après la déception,peut-être le graal ?

Bref, abandon de Neo4J et Bulbs

Attention : Neo4J et Bulbs sont tous les deux des beaux projets, pour Neo4J, il aurait juste fallu que je passe 6 mois à me mettre à niveau en Java et que j’arrive à m’autopersuader de modifier des fichiers de configuration XML, quand à Bulbs, je ne doute pas qu’il aie sa place dans une pile applicative si vous êtes à l’aise avec Neo4J et son langage de requête.

Nouvelle recherche Google : cette fois, je ne cherche pas directement une base graphe mais je regarde les différents DSL qui permettent de l’interroger, avec l’espoir de trouver l’équivalent du SQL dans le monde des bases graphes : un langage de requêtes standardisés.

Et bien, ça n’existe pas mais il existe tout de même un DSL qui semble être une norme de facto : Gremlin, langage conçu par Tinkerpop

Là, grosse claque, belle découverte : un DSL hyper synthétique, bien conçu qui permet d’écrire à la vitesse de la lumière des algorithmes de graphe complexes en quelques lignes, voire en one-liner, quand l’équivalent en base relationnelle nécessiterait des dizaines, voire des centaines de lignes de code SQL…

Si vous ne connaissez ce DSL, je vous invite à le découvrir dans cette vidéo, le conférencier, Marko Rodriguez est simplement bluffant de par sa connaissance des bases graphes mais également par sa vitesse d’élocution et la rapidité avec laquelle il enchaine les différents exemples et algorithmes de graphe.

Autre avantage de Gremlin : il existe des drivers pour la plupart des bases de données Graphes, j’ai pu en particulier l’utiliser avec :

• Neo4J (Java)
• OrientDB (Java)
• Titan (Java)
• ArangoDB (C/C++)

C’est une bonne chose de disposer d’un dialecte commun entre toutes ces bases de données, en particulier en environnement de production puisque cela permet de changer assez facilement de base de données sans avoir à recoder toutes ses requêtes.

A noter que pour les dernières versions de Neo4J, il reste tout de même conseillé d’utiliser le langage de requêtes de Neo4J

Réimplémentation de l’algorithme de recommandation avec Gremlin

Après la découverte de Gremlin, je décide donc de réimplémenter mon algorithme de recommandation : c’est relativement simple, Gremlin s’appuie en effet sur Groovy, un langage dynamique lui-même basé sur Java, qui présente de nombreuses similitudes avec Python, ce qui n’est pas pour me déplaire.

En fait, la partie la plus complexe reste toujours l’interfaçage avec la base de données : si, sur le papier, de nombreuses bases graphes sont supportées par Gremlin, l’installation des pilotes est toujours un peu laborieuse (sauf Titan, mais c’est normal, cette base a été lancée par des développeurs de Gremlin) et il faut souvent chercher une version de base de données compatibles avec un driver fourni.

Mais bref, je peux donc tester la performance de l’algorithme avec les bases mentionnées plus haut (Neo4J/OrientDB/Titan/ArangoDB) et c’est une nouvelle déception : il faut entre 300ms (Titan) et 1s (Neo4J) pour obtenir les résultats de l’algorithme de recommandation, ce n’est pas acceptable (au maximum, il fallait avoir des résultats au bout de 100ms)

Je lance un profiling et constate qu’une partie du temps est forcément consacrée au passage à travers les différentes couches d’interfaçage, un aller/retour requête/réponse ressemblant à cela :

• Implémentation de la requête en Python
• Lancement via bulbs de la requête qui l’envoie à rexster (un serveur défini par Tinkerpop qui permet d’exposer des endpoints et in fine d’executer des requêtes Gremlin)
• Lancement de la requête Gremlin (avec passage de Groovy à Java) sur la base de données graphes
• Récupération de la réponse
• Et on repasse les couches dans le sens inverse

Bref, trop de couches à passer, même avec des algorithmes simples et des graphes de taille réduite, on a toujours des latences trop importantes.

Il ne semble alors rester qu’une seule alternative : préparer les requêtes et les enregistrer dans les bases de données pour les executer à la demande

Mais :

• le gain de performance n’est toujours pas suffisant
• une partie du code est dans la base elle-même ce qui est toujours un problème
• le code Python ne ressemble plus à du code Python

C’est à ce moment là que je prends la décision de tenter d’implémenter une base graphe en pur Python :

• Les performances avec NetworkX étaient bonnes
• Or, NetworkX s’appuie en grande partie sur des dictionnaires Python
• Il manque “juste” :
  • La persistence des données
  • Un langage aussi agréable à utiliser que Gremlin pour faire du ”path traversal”
• Pour la persistance des données, utiliser un KVS (Key Value Store) est une option logique : un KVS n’est jamais, conceptuellement, qu’un gros dictionnaire persistant.

GrapheekDB : choix techniques initiaux

Lorsque j’ai commencé la conception de GrapheekDB, j’ai fait les choix suivants :

• Création d’une couche d’abstraction pour communiquer avec les KVS ou les dictionnaires Python
• Sélection de KVS présentant les caractéristiques suivantes :
  • Existence de transactions : pour garantir la cohérence des données stockées (pour avoir des performances acceptables malgré la lenteur intrinsèque du Python, je savais que j’aurais à dénormaliser massivement et que cette dénormalisation ne devait pas induire d’incohérences)
  • Capacité à utiliser l’ensemble de l’espace disque disponible <=> il ne fallait pas que la taille de la base graphe soit limitée par la mémoire vive disponible ou que les performances se dégradent quand la taille des données stockées dépassent celle de la mémoire vive (ce que l’on constate avec Redis par exemple)
  • Bonnes performances a minima en lecture, idéalement en écriture : c’est un choix très subjectif, je savais que pour mes besoins, le nombre de lectures seraient de plusieurs ordres supèrieurs au nombre d’écritures.
• Développement d’un serveur autonome pour autoriser plusieurs process à accèder à la base graphe centrale
• Tout en conservant la possibilité de travailler directement avec les données sous-jacentes
• En garantissant une API unifiée que l’on travaille en direct avec les données ou que l’on passe par un serveur, autrement dit, coder un “proxy” qui présente exactement la même API que si l’on passe en “direct”
• L’API devait être un mélange entre Gremlin et Django et rester “pythonesque” :
  • Gremlin, car c’est un magnifique DSL, extrèmement expressif
  • Django, car le premier projet dans lequel était utilisé la base graphe est un projet Django et qu’il était préférable d’avoir une API “familière”

Accessoirement, comme je me connais et que j’ai toujours tendance à privilégier la vitesse dans l’équation bien connue des chefs de projets (temps/fonctionnalités/qualité/coûts), j’ajoute les éléments et contraintes suivants :

• Grand nombre de tests : GrapheekDB est mon premier projet Open Source et comme dit l’un de mes amis, l’open source, c’est comme les slips, quand on le montre, il faut que ce soit propre
• Haut niveau de couverture du code par les tests, idéalement 100% (magré toutes les réserves que l’on peut faire sur la signification de 100% de taux de couverture…)

Mon objectif principal était le suivant :

Obtenir des performances, pour l’algorithme de recommandation, supèrieures à celles obtenues avec des bases graphes existantes (en Java)

Cet objectif conditionnant la mise à disposition du code (en Open Source).

A ceux qui ne manqueront pas de me rétorquer qu’il aurait peut-être été préférable de chercher à tuner une base Java existante, je réponds : certes, mais je n’ai qu’une vie et puis oh, GrapheekDB, c’est opensource et gratos ! ;)

(Ca, c’est une vraie réponse argumentée, hum !!)

Bref, vous l’aurez compris, j’ai atteint mon objectif : au final, les performances étaient bonnes, j’obtenais des recommandations au bout de 10 à 50ms

Si vous voulez voir à quoi ressemble GrapheekDB, vous pourrez retrouver les slides de la présentation faite à l’école 42

Il y a également une vidéo

L’heure du bilan

• La base est stable (j’ai une instance qui tourne depuis plus d’un an et qui compte une centaine de milliers de noeuds).
• Le projet semble intéresser les développeurs Python puisqu’il y a généralement entre 50 et 100 téléchargements quotidiens.

A titre personnel :

• A l’heure actuelle, le résultat me satisfait, dans le sens où il répond à mes besoins.
• Je considère ce projet Open Source comme un accomplissement et un juste retour des choses envers la communauté OpenSource après deux décennies d’utilisation d’outils Open Source et des contributions limitées (à Django)
• J’en suis d’autant plus heureux que cet outil permet rapidement à tous les développeurs Python de jouer avec une base graphe et un DSL proche de Gremlin
• Mon code n’est définitivement pas le plus pur du monde (dégonflement des chevilles)
• Mais je code toujours aussi vite :p (reglonflement des chevilles), parfois trop (pchhhhhh....)
• Heureusement que sur le conseil d’Adrien, j’ai mis en place Coverage, cela m’a permis de vraiment tester en profondeur, de détecter des bugs bien vicieux et d’obtenir un résultat très stable.

Ce que j’aimerais améliorer :

• La documentation :
  • je suis relativement content du tutorial
  • mais le code est très peu documenté
  • il manque clairement une documentation utilisateur, ce qui est d’autant plus dommage que des fonctions intéressantes ont été ajoutées depuis l’écriture du tutorial
• La performance en écriture, même si mes besoins en base graphe sont plutôt WORM (Write Once Read Many), parfois WFRM (Write Few Read Many), il est clair que GrapheekDB pêche sur ce point :(
• Le système d’index : il manque clairement des index permettant d’accélerer les filtres de type intervalle

Pour aller plus loin :

On me demande souvent si je considère que GrapheekDB est suffisamment stable pour être utilisé en production : la réponse pour moi est oui car ayant créé le code, je saurais corriger les éventuels bugs, mais pour les autres, c’est plutôt : je pense qu’il faut tenter (et normalement, là, on a tendance à entendre “non” ;))

Le fait est, qu’actuellement :

• GrapheekDB est déployé en production.
• Je fais en sorte de conserver un très haut niveau de tests (>2000) et de couverture (~100%)
• Je corrige rapidement les bugs qui sont notés sur Bitbucket
• J’ajoute des fonctionnalités lorsqu’elles me semblent avoir un intérêt pour l’ensemble des utilisateurs

Bref :

Si tu es développeur Python et que tu as envie de jouer avec des bases graphes ça m’intéresse aussi, je ne peux que te conseiller de jouer avec GrapheekDB, c’est une vraie base graphe, avec un dialecte inspiré de Gremlin et des filtres inspirés de Django

Pour aller voir ailleurs

Si vous cherchez une base graphe plus mûre, plus puissante et un bon DSL qui va avec, je ne peux que vous conseiller d’aller voir Titan, bon, c’est en Java, on ne peut pas tout avoir…

Les liens

• Package Python de GrapheekDB : https://pypi.python.org/pypi/grapheekdb
• Repository du projet : https://bitbucket.org/nidusfr/grapheekdb
• Slides : http://slides.com/nidus_fr/grapheekdb#/
• Vidéo de la présentation faite à l’école 42 : http://www.dailymotion.com/video/x1ql18e_conf-42-meetup-paris-py-4_tech