VT2015 Graph Databases - Revision history

Malek-Hadi.Mammar: /* Synthèse écrite */

2015-10-07T22:21:12Z

Synthèse écrite

Malek-Hadi.Mammar: /* Abstract */

2015-10-07T22:00:52Z

Abstract

← Older revision		Revision as of 22:00, 7 October 2015
Line 15:		Line 15:
	Also we must not forget to point out that social networks spreading contributed a lot to "graph databases" appearance. I think of facebook, twitter, linkedIn who pioneered to this democratization with the development of wrappers for relational database to facilitate the use of graph structures (eg. TAO, FlockDB).		Also we must not forget to point out that social networks spreading contributed a lot to "graph databases" appearance. I think of facebook, twitter, linkedIn who pioneered to this democratization with the development of wrappers for relational database to facilitate the use of graph structures (eg. TAO, FlockDB).
	In this presentation we shall see what is the goal of using graph databases and focus on Neo4j database.		In this presentation we shall see what is the goal of using graph databases and focus on Neo4j database.

			==Résumé==

			La démocratisation des bases de données de graphes vient en continuité au mouvement NoSQL (NotOnlySQL), qui répand l'idée que les bases de données relationnelles ne sont pas le seul moyen de stockage possible.
			Aussi, nous ne devons pas oublier de souligner que l'explosion des réseaux sociaux a également beaucoup contribué à l’émergence des bases de données en graphes. Je pense notamment à aux pionniers de cette démocratisation, de Facebook, Twitter, LinkedIn, ... avec le développement de "wrapper" pour les bases de données relationnelles qui ont pour but de faciliter la manipulation de structures en graphes (ex. Tao, FlockDB).
			Dans cette présentation, nous verrons quel est le but de l'utilisation de bases de données en graphe et se pencher particulièrement Neo4j.

	==Synthèse écrite==		==Synthèse écrite==

Malek-Hadi.Mammar: /* Abstract */

2015-10-07T21:56:23Z

Abstract

← Older revision		Revision as of 21:56, 7 October 2015
Line 12:		Line 12:
	==Abstract==		==Abstract==

			The democratization of graph databases comes in continuity to the NoSQL (NotOnlySQL) fashion, which spreads the idea that relational databases are not the only possible storage.
			Also we must not forget to point out that social networks spreading contributed a lot to "graph databases" appearance. I think of facebook, twitter, linkedIn who pioneered to this democratization with the development of wrappers for relational database to facilitate the use of graph structures (eg. TAO, FlockDB).
			In this presentation we shall see what is the goal of using graph databases and focus on Neo4j database.

	==Synthèse écrite==		==Synthèse écrite==

Malek-Hadi.Mammar: /* Comparatif de performance */

2015-10-06T17:14:36Z

Comparatif de performance

← Older revision		Revision as of 17:14, 6 October 2015
Line 58:		Line 58:
	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.		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.

	[[File:VT2015_Graph_Databases_benchmarking.png\|~~500px~~\|center\|Benchmarking]]		[[File:VT2015_Graph_Databases_benchmarking.png\|700px\|center\|Benchmarking]]

	On peut reconnaître 2 types de BD :		On peut reconnaître 2 types de BD :

Malek-Hadi.Mammar: /* Comparatif de performance */

2015-10-06T17:14:27Z

Comparatif de performance

← Older revision		Revision as of 17:14, 6 October 2015
Line 58:		Line 58:
	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.		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.

	[[File:VT2015_Graph_Databases_benchmarking.png\|~~300px~~\|center\|Benchmarking]]		[[File:VT2015_Graph_Databases_benchmarking.png\|500px\|center\|Benchmarking]]

	On peut reconnaître 2 types de BD :		On peut reconnaître 2 types de BD :

Malek-Hadi.Mammar: /* Comparatif de performance */

2015-10-06T17:14:17Z

Comparatif de performance

← Older revision		Revision as of 17:14, 6 October 2015
Line 58:		Line 58:
	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.		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.

	[[File:VT2015_Graph_Databases_benchmarking.png\|center\|Benchmarking]]		[[File:VT2015_Graph_Databases_benchmarking.png\|300px\|center\|Benchmarking]]

	On peut reconnaître 2 types de BD :		On peut reconnaître 2 types de BD :

Malek-Hadi.Mammar: /* Zoom sur Neo4j */

2015-10-06T17:13:58Z

Zoom sur Neo4j

← Older revision		Revision as of 17:13, 6 October 2015
Line 113:		Line 113:
	===Zoom sur Neo4j===		===Zoom sur Neo4j===

	[[File:VT2015_Graph_Databases_neo4j.png\|~~200px~~\|center\|Wrapper performance]]		[[File:VT2015_Graph_Databases_neo4j.png\|300px\|center\|Wrapper performance]]
	Structure des données dans Neo4j		Structure des données dans Neo4j
	Source : http://fr.slideshare.net/thobe/an-overview-of-neo4j-internals		Source : http://fr.slideshare.net/thobe/an-overview-of-neo4j-internals

Malek-Hadi.Mammar: /* Zoom sur Neo4j */

2015-10-06T17:13:49Z

Zoom sur Neo4j

← Older revision		Revision as of 17:13, 6 October 2015
Line 113:		Line 113:
	===Zoom sur Neo4j===		===Zoom sur Neo4j===

	[[File:VT2015_Graph_Databases_neo4j.png\|~~500px~~\|center\|Wrapper performance]]		[[File:VT2015_Graph_Databases_neo4j.png\|200px\|center\|Wrapper performance]]
	Structure des données dans Neo4j		Structure des données dans Neo4j
	Source : http://fr.slideshare.net/thobe/an-overview-of-neo4j-internals		Source : http://fr.slideshare.net/thobe/an-overview-of-neo4j-internals

Malek-Hadi.Mammar: /* Zoom sur Neo4j */

2015-10-06T17:13:30Z

Zoom sur Neo4j

← Older revision		Revision as of 17:13, 6 October 2015
Line 113:		Line 113:
	===Zoom sur Neo4j===		===Zoom sur Neo4j===

	[[File:~~VT2015_Graph_Databases_demo~~.png\|500px\|center\|Wrapper performance]]		[[File:VT2015_Graph_Databases_neo4j.png\|500px\|center\|Wrapper performance]]
	Structure des données dans Neo4j		Structure des données dans Neo4j
	Source : http://fr.slideshare.net/thobe/an-overview-of-neo4j-internals		Source : http://fr.slideshare.net/thobe/an-overview-of-neo4j-internals

Malek-Hadi.Mammar: /* Zoom sur Neo4j */

2015-10-06T17:13:10Z

Zoom sur Neo4j

← Older revision		Revision as of 17:13, 6 October 2015
Line 113:		Line 113:
	===Zoom sur Neo4j===		===Zoom sur Neo4j===

			[[File:VT2015_Graph_Databases_demo.png\|500px\|center\|Wrapper performance]]
	<<add file neo4j structure>>
	Structure des données dans Neo4j		Structure des données dans Neo4j
	Source : http://fr.slideshare.net/thobe/an-overview-of-neo4j-internals		Source : http://fr.slideshare.net/thobe/an-overview-of-neo4j-internals

← Older revision		Revision as of 22:21, 7 October 2015
Line 26:		Line 26:
	====Introduction====		====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.		La démocratisation des bases de données en graphe vient en continuation au mouvement NoSQL(NotOnlySQL) qui prône l'idée que les BD relationnelles ne sont pas les seuls moyens 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).		Aussi on ne peut oublier de souligner, l'explosion des réseaux sociaux qui a 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.		On est en droit de se demander quelle est l'utilité des BD en graphe.

Line 34:		Line 34:

	Pour faire court, 2 raisons motivent l'utilisation de BD en graphe :		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...		* posséder une structure de données 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		* une syntaxe de requête plus graph-friendly

	Les cas d'~~utilisations~~ des BD en graphe sont multiples :		Les cas d'utilisation des BD en graphe sont multiples :
	* centralisation des logs ~~issues~~ d'applications hétérogènes mais dont les interactions sont complexes.		* centralisation des logs issus 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.		* 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.		Bref, il y a autant de cas d'utilisation qu'il y a de problème de graphe nécessitant une persistance des données dans le temps.

	====Analyse de marché====		====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 :		On peut répertorier les bases de données sous 3 catégories. Et dans chacune des distinctions sont possibles. L'ordre ressemble à celui-ci :
	* les relationnelles : basées sur une structure en tables		* les relationnelles : basées sur une structure en tables
	** orientée colonne (eg. Vertica)		** orientée colonne (eg. Vertica)
Line 65:		Line 65:


	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.		Pour se donner une idée de performance, je reprends l'exemple d'un benchmark réalisé par Alekh Jindal, un post doctorant dans le groupe Data base Group du laboratoire MIT CAIL.

	[[File:VT2015_Graph_Databases_benchmarking.png\|700px\|center\|Benchmarking]]		[[File:VT2015_Graph_Databases_benchmarking.png\|700px\|center\|Benchmarking]]
Line 81:		Line 81:

	Deux types de requêtes sont élaborées :		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.		* pageRank qui consiste en un noeud avec potentiellement des jointures. Les BD relationnelle sont très optimisées là-dessus. D'ailleurs cela se constate par le fait que Neo4j se fait dépasser 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.		* 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 matière 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.		Quel est donc l'intérêt de Neo4j ? Eh bien, c'est d'offrir une API facilitant la manipulation de structure en graphe. Sur les dernières slides de ma présentation une preuve à l'appui d'un exemple de requête ayant pour but de contraster un calcul de plus court chemin entre une syntaxe Cypher (utilisée par Neo4j) et une syntaxe SQL.

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


Line 109:		Line 109:
	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, ...)		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.		Le principal 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 !		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ées ~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 !

	[[File:VT2015_Graph_Databases_SQL_VERTEX.png\|500px\|center\|Wrapper performance]]		[[File:VT2015_Graph_Databases_SQL_VERTEX.png\|500px\|center\|Wrapper performance]]
Line 118:		Line 118:
	Enfin je citerai quelques exemples de “wrapper” MySQL : FlockDB (Twitter), TAO (Facebook).		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.		En m’interrogeant sur l'origine de ce manque de performance, je me suis penché sur la structure de Neo4j.

	===Zoom sur Neo4j===		===Zoom sur Neo4j===
Line 127:		Line 127:

	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.		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).		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.		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.		La redondance du terme liste chaînée a un impact fondamental sur les performances de Neo4j. Le principal 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é spatiale 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és d'égaler les performances d'un cache matériel.

	===Conclusion===		===Conclusion===
Line 135:		Line 135:
	En conclusion l'application à développer déterminera le choix de la BD. Selon que l'on recherche :		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		* 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.		* des propriétés ACID, cruciales dans les domaines de transactions (eg. bancaires, ...), on choisira une bonne vieille 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		* 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 de “wrapper” de requêtes SQL (Giraph, Pegasus, …)