VT2015 Graph Databases

Présentation

Enseignants : D. Donsez, GP. Bonneau

Sujet : Graph databases

Document

File:VT2015 Graph Databases.pdf

Synthèse écrite

Introduction

La démocratisation des bases de données en graphe viens en continuation au mouvement NoSQL(NotOnlySQL) qui à prône l'idée que les BD relationnelles ne sont pas le seul moyen de stockage. Aussi on ne peut oublier de souligner, l'explosion des réseaux sociaux qui à tout aussi favorisé leur apparition. Je pense notamment à facebook, twitter, linkedIn qui furent les pionniers vers cette démocratisation avec l'élaboration de "wrappers" de BD relationnelle facilitant l'usage de structures en graphe (eg. TAO, FlockDB). On est en droit de se demander quelle est l'utilité des BD en graphe.

Motivations

Pour faire court, 2 raisons motivent l'utilisation de BD en graphe :

• posséder une structure de donnée qui reflète l'architecture de l'application à coder. C'est typique de l'application à consonance *networking* : facebook, etc...
• une syntaxe de requête plus *graph-friendly*

Les cas d'utilisations des BD en graphe sont multiples :

• centralisation des logs issues d'applications hétérogènes mais dont les interactions sont complexes.
• un gestionnaire de modules, ou bibliothèques (NPM, ...) nécessitant un graphe de dépendances.

Bref, il y a autant de cas d'utilisations qu'il y a de problème de graphe nécessitant une persistance des données dans le temps.

Analyse de marché

On peut répertorier les bases de données sous 3 catégories. Et dans chacune des distinctions sont possibles. L'ordre ressemble a celui-ci :

• les relationnelles : basées sur une structure en tables
  • orientée colonne (eg. Vertica)
  • orientée ligne (eg. MySQL)

• les NotOnlySQL : basées sur différents systèmes
  • clé-valeur (eg. Redis)
  • document (eg. MongoDB)
  • ...

• les structures en graphe : basées sur différents systèmes
  • une structure en graphe (eg. Neo4j, LDAP)
  • *wrapper* d'une BD relationnelle (eg. TAO, FlockDB)

Ce qui différencie une BD relationnelle orientée colonne et à une autre orientée ligne est la façon dont la sérialisation des données est effectuée sur le disque dur. En *orientée-colonne* les colonnes d'une table sont écrites sur disque successivement de manière contiguë. En *orientée-ligne* les lignes sont cette fois-ci écrites successivement.

Comparatif de performance

Pour ce donner une idée de performance, je reprend l'exemple d'un benchmark réalisé par Alekh Jindal, un post doctorant dans le groupe Data base Group du laboratoire MIT CAIL.

On peut reconnaître 2 types de BD :

• Neo4j (en graphe)
• les autres (en relationnelle). Plus précisément,
  • Vertica est orientée colonne
  • MySQL est orientée ligne
  • VoltDB est orientée stockage en RAM

Deux bases de données permettent l'évaluation des performances :

• une constituée de 4K noeuds
• une seconde constituée de 81K noeuds

Deux types de requêtes sont élaborées :

• *pageRank* qui consiste en un noeud avec potentiellement des jointures. Les BD relationnelle sont très optimisées la-dessus. D'ailleurs cela se constate par le fait que Neo4j se fait dépassé en terme de performance.
• *shortestPath* qui consiste à démarrer d'un noeud source, et de successivement visiter ses noeuds voisins. Contre toute attente, là encore Neo4j se fait devancer en terme de performances par ses homologues relationnels.

Quelles est donc l'intérêt de Neo4j ? Et bien, c'est d'offrir une API facilitant la manipulation de structure en graphe. Sur les dernière slides de ma présentation une preuve à l'appui d'un exemple de requête ayant pour but de contraster une calcul de plus court chamin entre une syntaxe Cypher (utilisée par Neo4j) et une syntaxe SQL.

Avantages/Inconvénients

Pour récapituler plusieurs avantages et inconvénients sont à souligner :

Pour les BD en graphe :

• Avantages :
  • une interface de requête plus adaptée aux structures en graphe
• Inconvénients:
  • perte en performance en raison de l’implémentation sous-jacente (voir Zoom sur Neo4j)

Pour les BD relationnelles :

• Avantages :
  • performance (quel que soit le type de requêtes)
• Inconvénients :
  • complexification des requêtes de type graphe
  • perte en temps de développement
  • risque d’erreurs

Solution

Une solution mixte liant la performance des BD relationnelle à la facilité de manipulation de structures en rgaphe, consiste à élaborer une interface plus "graph-friendly" qui se mappe au moteur SQL (eg. Giraph, Pregel, ...)

Le principale avantage est l'abstraction de la syntaxe SQL. Et l'unique inconvénient est l'ajout d'un temps de traitement supplémentaire. Sur le tableau ci-dessous on met en évidence l'impact d'un "wrapper" au dessus de la BD relationnelle voltDB (mentionné plus haut). On peut clairement remarquer un temps de calcul plus ou moins proportionnel à la taille des données manipulées. Sur une petite base de donnée ~4K noeuds (Facebook) la perte s'évalue à 10 secondes tandis que sur une taille plus importante (de 81K noeuds), la perte s'élève à 140 secondes. Ce qui est non négligeable !

Comparaison des interfaces SQL - Vertex-centric (= similaire à Giraph) Source : http://istc-bigdata.org/index.php/benchmarking-graph-databases/

Enfin je citerai quelques exemples de “wrapper” MySQL : FlockDB (Twitter), TAO (Facebook).

En m'intérrogeant sur l'origine de ce manque de performance, je me suis penché sur la structure de Neo4j.

Zoom sur Neo4j

Structure des données dans Neo4j Source : http://fr.slideshare.net/thobe/an-overview-of-neo4j-internals

Ce que l'on peut clairement observer c'est la structure d'un noeud, contenant une liste chaînée de propriétés de type clé-valeur, et de relation trié par type, puis par catégorie In si l'arc (équivalent à une relation) est incident, Out s'il est sortant. Un noeud contient uniquement une référence vers une liste chaînée de relations. Une relation est elle même une structure contenant un type, une liste chaînée de propriétés ainsi que son noeud de départ (start) et d'arrivée (end). Un graphe est donc stocké sous forme d'une liste chaînée de noeuds contenant chacun toute l'information nécessaire sur les arcs entrants et sortants du noeud. La redondance du terme *liste chaînée* à un impact fondamentale sur les performances de Neo4j. Le principale inconvénient d'une structure en liste chaînée est le coût en temps et en nombre d'accès mémoire I/O. Contrairement au BD relationnelle il n'y a là pas possibilité de cache, à localité spatial du moins, au niveau matériel. Et ce, pour la simple raison que les données ne sont pas contiguës en mémoire mais éparpillées sur le disque. Il y a sans doute possibilité de constituer un cache logique, mais sans possibilité d'égaler les performances d'un cache matériel.

Conclusion

En conclusion l'application à développer déterminera le choix de la BD. Selon que l'on recherche :

• performances et scalabilité, on partira sur du NoSQL
• des propriétés ACID, cruciales dans les domaines de transactions (eg. bancaires, ...), on choisira une bonne vielle BD relationnelle.
• une facilité de syntaxe des requêtes, pour un développement plus rapide d'une application impliquant la manipulation de structure en graphe, on partira sur
  • l'utilisation de “wrapper” de requêtes SQL (Giraph, Pegasus, …)
  • l'utilisation des BD dédiés graphe : Neo4j (Cypher)