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 ?
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 :
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ù :
Donc, pas le choix : il fallait trouver un serveur de base de données graphe, idéalement en Python.
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 :
Mais rapidement, je déchante :
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 :
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
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 :
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 :
C’est à ce moment là que je prends la décision de tenter d’implémenter une base graphe en pur Python :
Lorsque j’ai commencé la conception de GrapheekDB, j’ai fait les choix suivants :
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 :
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
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 :
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
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
garrigos adrian - il y a 4 ans
Je suis bluffé de voir que tu développes une graphdb seul! Vu l'importance stratégique du truc, tu devrais communiquer plus. J'ai entendu parlé (aujourd'hui) de transTech. Google it! Car tu touches là à un secteur très porteur pour le web-app (i love django 2).
Même si ça reste un open-source (communique +). Et, heu, un projet sur github serait peut plus visible (du moment que le slip est propre...) :-)
En tous cas, je vais parlé de ton projet autour de moi (i love start-up)
Raphaël - il y a 4 ans
Bonjour Adrian,
Merci beaucoup de ton retour :)
J'ai un peu communiqué au moment de la sortie du projet mais étant freelance, j'ai moins le temps de communiquer actuellement. Par ailleurs, je dois trouver du temps pour le faire évoluer : ça fait longtemps que je n'ai pas fait une nouvelle release, ton message donne en tout cas envie de s'y remettre :)
Par ailleurs, je pense que cette base est intéressante pour ceux qui veulent disposer rapidement d'une base graphe dans un environnement Python et pour tester des algos de graphes sur de faibles volumétries de données mais pour de grosses applications ambitieuses, il reste préférable de se tourner vers les poids lourds du secteur, ne serait ce que pour disposer d'un support disponible :)
amz3 - il y a 4 ans
La révolution est en marche. Une autre personne qui fait une graphdb en Python et une autre personne qui aime Gremlin.
Je n'ai jamais réellement accroché aux langage de requêtage de Neo4j à savoir Cypher. La liberté d'expression dans Cypher n'est pas apparente car le rapprochement avec l'API proche du SQL declarative me bloque dans la réflexion sur les problématique métier. Alors qu'avec Gremlin, le rapprochement plus évident à un langage imperatif est mieux. On a vraiment l'impression d'avoir un langage de turing complet à sa disposition. Quand je suis tombé sur Gremlin j'ai vite vue la différence. L'idée de «naviguer» un graphe m'est venu très naturellement. Au debut j'utilisait une API que j'appelle objet très proche de gremlin ``g.V.outV.outgoings("foo", "bar").in_`` mais l’implémentation que j'ai faite était tellement pénible à lire que je me suis rabattu une simple composition de fonction: ``query(graph, vertices, outgoings, filter(lambda x. x.foo == bar), end)`` où chaque argument de ``query`` est un générateur Python. Je n'est pas implémenté de backend lmdb car l'API n'est pas celle dont j'avais besoin à l’époque. Je voulais une intégrité très forte entre les données avec un support strict de l'ACID sur la lecture et l'écriture de plusieurs clef à la fois pour pouvoir faire durer une transaction sur la modification de plusieurs clefs. Le cas d'usage est le suivant, je créer un nœud dans mon wiki pour une nouvelle révision (un nœud plus une arête dans le cas simple sans indexation ce que se traduit dans 2 écritures et zéro lecture dans mon backend actuel) et je veux l'ajouter à la base de donnée plein texte (j'ai pas compté le nombre de lecture/ecriture mais plus de 2), si l'une des opérations ne peux avoir lieu, il faut qu'aucune ne soit appliqués.
Je confirme que dans le WORM que lmdb fait beaucoup sens, c'est à ça que c'est prevu étant donnée que c'est utilisé dans OpenLDAP. Avant que bsddb ne passe à l'AfferoGPL, OpenLDAP utilisait bsddb que j'ai essayé aussi car il remplissait les besoins su-cité. Cela dit je ne recommende pas bsddb. J'ai aussi essayé leveldb mais les performances sont décevantes. J'ai entendu du bien de RocksDB.
Aujourd'hui je me focus principalement sur la phase amont à la mise en production. Celle qui consiste à analyser et créer les algorithmes de graphe qui plus tard seront executé en production. J'espère pouvoir créer la boite outils pandas pour les algorithmes basées sur les graphes.
Ça fait très plaisir à lire!
Carl Chenet - il y a 4 ans
Retour d'expérience très très intéressant. Dès que j'ai un projet pouvant utiliser les graphes, j'essaie GrapheekBD. Heureusement que quelqu'un l'a posté sur le Journal du hacker, je ne l'avais pas vu passer à l'époque :)
2015 © Nidus. Tous droits réservés. En savoir plus