1© OCTO 2012

Hadoop et les graphesHUG France, 17/10/2012

2

Des outils pour traiter des graphes ?

Modèle relationnel et SQL

Neo4j

Hadoop & consortsGénéralités

MapReduce

Hive, Pig

BSP : Hama et Giraph

Conclusion

Liens utiles

AGENDA

3

Des outils pour traiter des graphes ?

RelationnelGraphDB

MapReduce

BSP

4

Faire glisser l'image vers l'espace réservé ou cliquer sur l'icône pour l'ajouter

Modèle relationnel et SQL

5

Modèle relationnel et SQL

FK

FK

Vertex

Edge

6

Modèle relationnel et SQL

-- Recherche des voisins de :source_idselect

vertex.*from

vertexjoin edge on edge.to_id = vertex.id

where edge.from_id = :source_id

Source

Vertex

Vertex

7

-- Recherche des voisins des voisinsselect -- [distinct]

vertex.*from

vertexjoin edge e2 on e2.to_id = vertex.idjoin edge e1 on e1.from_id = e2.to_id

where e1.from_id = :source_id

Modèle relationnel et SQL

Source

Vertex

Vertex

Vertex

Vertex

8

Modèle relationnel et SQL

-- Déductions de niveau arbitraire???

-- Peut-être avec les CTE(*) si supportées !-- (* Common Table Expressions)

Source

Vertex

Vertex

Vertex

Vertex

Vertex

Vertex

Vertex

Vertex

9

Adapté pour des accès TP ciblés sur les nœuds !Grâce à l’ndexation des nœuds

Mais en requêtage le langage SQL a vite des limitesNiveaux de profondeurs multiples, élevés ou non connus à l’avance

Peut-être une piste du côté des Common Table Expressions

Pour les algos de graph processing, il faut faire de l’itératifMais chaque nœud du graphe parcouru induit au moins 1 accès aléatoire sur le disque (lookup de l’index de FK)

La scalabilité du modèle est celle du SGBDQuelques nœuds de stockage/traitement

Quelle clef de partitionnement pour des requêtes optimales ?

Modèle relationnel et SQL

10

Faire glisser l'image vers l'espace réservé ou cliquer sur l'icône pour l'ajouter

Neo4j

11

Graph

Neo4j

Vertex

Vertex

Vertex

Vertex

Vertex

Vertex

Vertex

Vertex

Vertex

Vertex & Edge properties

12

Neo4j

// API Traversal de Neo4j == automatefor ( Path position : Traversal.description() .depthFirst() .relationships( Rels.KNOWS ) .relationships( Rels.LIKES, Direction.INCOMING ) .evaluator( Evaluators.toDepth( 5 ) ) .traverse( node ) ) { // Traitement du chemin ‘position’}

// Alternative : langage Gremlin (TinkerPop)

Construction du traverser

Méthode de parcours

Nœud de départLimite de profondeur

Prédicats d’étapesPrédicats d’étapes

13

Neo4j

// Cypher == DSL de pattern matching (and more...)START me=node:node_auto_index(name = "me")MATCH me-[r1:ATE]->food<-[r2:ATE]-you==== me,count(distinct r1) as H1,count(distinct r2) as H2,you ====MATCH me-[r1:ATE]->food<-[r2:ATE]-youRETURN uneFonctionCompliquée(…) as similarity

Patterns sur les relations & nœuds connectés

Nœud de départ de la recherche

Expression de retour

14

Neo4j

// Recherche de plus court cheminPathFinder algo = GraphAlgoFactory.dijkstra(expander, costEval);Iterable res = algo.findAllPaths(startNode, endNode);

// Algos disponibles// - énumération des chemins (complets ou de longueur L)// - recherche du plus court chemin (A*, Dijkstra)

Fonction de coût des nœuds/liens traversés, à

minimiser

15

Très bonnes perfs en TP (avec ACID) et en mono-serveur

Très bonnes perfs en requêtage (Traversal, DSL) sur des parcours de complexité moyenne

Le TP, le pattern-matching et les algorithmes pré-câblés permettent de traiter bien plus de cas qu’avec un graphe modélisé en SQL

Les algos pré-câblés sont en nombre limité mais les API Traversal et Evaluator permettent d’en implémenter sans limitation

Mais, Neo4j est aujourd’hui mono-serveurIl n’est pas encore capable de sharder un graphe

Il peut tout de même stocker des millions de nœuds sur un seul serveur

Des bases graphes distribuées à surveillerTitan (Aurelius)

Trinity (Microsoft) – non publique

Neo4j

16

Faire glisser l'image vers l'espace réservé ou cliquer sur l'icône pour l'ajouter

Hadoop & consorts

17

Deux bénéfices attendus avec Hadoop & consortsRépartir et traiter des graphes très gros (≥ 1B nœuds, au-delà de Neo4j sur du commodity)

Paralléliser les traitements… si l’algorithme s’y prête

Le tout au prix d’une approche exclusivement batch

Représentation typique d’un graphe dirigé en fichier HDFS : liste d’adjacence

Hadoop & consorts

V1 V2

V3

V4

V1 V2V2 V3,V4V3 V4,V5...

V5

18

Exploration depth-first : difficile à paralléliser

Exploration breadth-first : parallélisable !

Hadoop & consorts

Src

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Src

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx Vtx

Vtx

VtxVtx Vtx

Vtx

Vtx

Vtx Vtx

Vtx

VtxVtx Vtx

Vtx

Vtx

Computation nodes

19

Exploration breadth-first avec MapReduce

Oozie ou while() {…}

Job JobJobJob

Hadoop & consorts

Src

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx Vtx

Vtx

VtxVtx Vtx

Vtx

Vtx

20

Hadoop & consorts

-- Requête Hive, un air de déjà vu :)select

vertex.*from

vertexjoin edge on edge.to_id = vertex.id

where edge.from_id = :source_id

Source

Vertex

Vertex

Un script Pig fait aussi le job !

21

Algorithme BSP adapté aux graphes : le modèle de Google PregelAPI « vertex-centric » reposant sur du passage de messages entre les sommets

… typiquement le long des arcs

Hadoop & consorts

Vertex

Compute()Inbox Outbox

Coordinateur

22

BSP en pratique – Superstep 1

Hadoop & consorts

Src

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

23

BSP en pratique – Superstep 2

Hadoop & consorts

Src

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

24

BSP en pratique – Superstep 3

Hadoop & consorts

Src

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

25

BSP en pratique – Superstep 4

Hadoop & consorts

Src

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

26

BSP en pratique – Superstep 5

Hadoop & consorts

Src

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

27

BSP en pratique – Fin du job

Hadoop & consorts

Src

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

28

Autre exemple

Hadoop & consorts

Src

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Vtx

Src

29

Hadoop et consorts

// Code vertex-centric avec Hama 0.5.0public static class ShortestPathVertex extends Vertex<Text, IntWritable, IntWritable> { @Override public void compute(Iterator<IntWritable> messages) throws IOException { int minDist = isStartVertex() ? 0 : Integer.MAX_VALUE;

while (messages.hasNext()) { IntWritable msg = messages.next(); if (msg.get() < minDist) { minDist = msg.get(); } }

if (minDist < this.getValue().get()) { this.setValue(new IntWritable(minDist)); for (Edge<Text, IntWritable> e : this.getEdges()) { sendMessage(e, new IntWritable(minDist + e.getValue().get())); } } else { voteToHalt(); } }}

30

ApplicationsRecherche de chemins

Calcul d’indicateurs sur les nœuds (centralité, …)

… tout ce qui nécessite une exploration complète d’un gros graphe

… du moment que l’algorithme peut se traiter avec du passage de messages

HAMA 0.5.0Top-level project Apache

Framework « BSP pur » avec une surcouche pour les graphes

Repose sur YARN

Giraph 0.1-alphaEn incubation chez Apache

Framework calqué sur le papier Google Pregel : « BSP pour les graphes »

Twitter, Facebook, Yahoo! … committers sur le projet

Repose sur MapReduce (les mappers bouclent sur les supersteps, pas de reducer)

Hadoop & consorts

31

Faire glisser l'image vers l'espace réservé ou cliquer sur l'icône pour l'ajouter

Conclusion

32

Les critères qui différencient les outils sontDistribué vs non (ou peu) distribué

Traitement local vs global de la topologie du graphe

Conclusion

Top. locale Top. globalePe

u di

strib

uéD

istrib

ué

Neo4j et équivalents

MapReduceHive, Pig

(BSP)HAMAGiraph

SQL

Titan, Trinity ?

33

Le papier de Google décrivant Pregelhttp://portal.acm.org/citation.cfm?id=1807167.1807184

Les sites Apache de Hama & Giraphhttp://hama.apache.org/

http://incubator.apache.org/giraph/

Le site de Titanhttps://github.com/thinkaurelius/titan/wiki

Des articles du blog OCTO traitant de grapheshttp://blog.octo.com/bases-de-donnees-graphes-un-tour-dhorizon/

http://blog.octo.com/introduction-aux-graphes-avec-neo4j-et-gephi/

http://blog.octo.com/en/introduction-to-large-scale-graph-processing/

Quelques liens pour finir