Apache giraph

Apache GiraphMRINI YOUSSEFBOUHILA BILAL

Introduction

Apache Giraph est un projet qui performe des calculs sur les graphes,

Apache Giraph utilise le service MapReduce de Hadoop.

Apache Giraph a été inspiré par le Framework Pregel de Google

Giraph est utilisé par Facebook et Paypal

Pourquoi on n’en a besoin ?

Giraph fait éviter des dépenses onéreuses en mémoire et en réseau pour des opérations mandataires en MapReude,

Chaque cycle d’une itération de calcule sur Hadoop signifie l’execution d’un Job MapReduce

Le Web

Le World Wide Web peut être structuré comme un énorme graphe:

Les pages sont des sommets connectées par des arcs qui représentent les hyperliens .

Ce Web Graphe a des billions de sommets et d’arcs.

Le succès des plus grandes sociétés comme Google se résume à son habilité à opérer de grands calculs sur ces graphes

Google PageRank

Le succès de moteur de recherche Google est par son habilité à gérer le classement des résultats.

Le classement basé sur l’algorithme PageRank qui est un algorithme orienté graphe très important:

Les pages importantes ont beaucoup de Lien provenant d’autres pages

Social Networks

Sur Facebook, Twitter, Linkedin, les utilisateurs et leurs interactions forment une Social Graph:

Les utilisateurs sont les sommets connectés par des arcs qui représentent une interaction comme Friendship ou Following

Google Pregel Un système distribué développé pour le traitement des graphes à

grands echelles «  Think like a vertex » Il prend le Bulk Synchronous parallel comme execution Tres tolerant aux pannes by checkpointing

Pourrais je utiliser Pregel ? Pregel est la propriété de Google, comme alternative il existe

Apache Giraph qui est une implémentation de Pregel Elle tourne sous une infrastructure Hadoop Les calculs s’executent en mémoire

Bulk synchronous parellel SuperSteps

Communication: Les processus d’échanges de données entre eux afin de faciliter le controle des données stockées Barrier synchronisationQuand un processus atteind le point ( Barrière), il doit attendre que les autres processus atteignent la meme barrière. Les calcules finissent quand tous les composants finissent.

Pourquoi ne pas implémenter Giraph avec des MapReduce Jobs

Trop de disques, pas assez de mémoire, a superstep become a Job

Qui fait quoi ?

Master: Responsable de la coordinationAssigne les partitions aux WorkersCoordonne la synchronisation

Worker : Responsable des sommetsInvoque les sommets activesEnvoie, reçoit et assigne les messages

Super Steps Chaque sommet a un id, une valeur et une liste de voisins adjacents et leurs arcs

correspondants. Chaque sommet est invoqué dans chaque super Step et peut recalculer sa valeur

et renvoyer des messages aux autres nœuds Des combinaisons, agrégations et les mutations de toplogies

Architecture maitre-esclave

Les sommets sont partitionnés et assignés à des Workers Les maitres assignent et coordonnent alors que les Workers

executent les sommets et communiquent entre eux.

Les matrices

Installé Giraph sur UbuntuTaper les commandes suivantes:sudo apt-get install gitsudo apt-get install maven

cd /usr/localsudo git close https://github.com/apache/giraph.gitsudo chown –R user : hadoop giraph

Il faut modifier le fichier bashrcgedit $HOME/.bashrcIl faut ajouter la ligne suivanteexport GIRAPH_HOME=/usr/local/giraph

Installé Giraph sur Ubuntu

source $HOME/.bashrc cd $GIRAPH_HOME mvn package –DskipTests

DskipTests permet de sauter la phase de teste, cela va prendre du temps

Installé Giraph sur Cloudera

Il faut modifier le bashrc.Export GIRAPH_HOME=/usr/local/giraphExport GV=1.0.0Export PRO= Hadoop_2.0.0

Il faut charger les variablesSource ~/.bashrc

Installé Giraph sur Cloudera

sudo mkdir /usr/local/giraph cd $GIRAPH_HOME cd .. sudo git clone https://github.com/apache/giraph.git sudo chown -R user:hadoop giraph cd $GIRAPH_HOME $ git checkout release-$GV $ mvn package -DskipTests -Dhadoop=non_secure -P $PRO

Installé Giraph sur Cloudera

Prépation de la donnée

La premiere etape est de mettre notre graphe sur le hdfs sous le nom de Tiny_graph.txt

[0,0,[[1,1],[3,3]]][1,0,[[0,1],[2,2],[3,1]]][2,0,[[1,2],[4,4]]][3,0,[[0,3],[1,1],[4,4]]][4,0,[[3,4],[2,4]]]

On va créer le fichier input et output sur le HDFS

Hdfs dfs –mkdir ginputHdfs dfs –mkdir goutput

Ensuite on va copier notre tiny_graph dans le HDFS

Hdfs dfs –put tiny_graph.txt ginput

Ensuite on va télécharger un exemple ( ShortestPathsInputGraph)sudo yum install wgetwget http://ece.northwestern.edu/~aching/shortestPathsInputGraph.tar.gztar zxvf shortestPathsInputGraph.tar.gzhdfs dfs -put shortestPathsInputGraph ginput

Executer le Giraph Job

hadoop jar giraph-ex.jar org.apache.giraph.GiraphRunner \-Dgiraph.zkList=127.0.0.1:2181 -libjars giraph-core.jar \org.apache.giraph.examples.SimpleShortestPathsVertex \-vif org.apache.giraph.io.formats.JsonLongDoubleFloatDoubleVertexInputFormat \-vip /user/training/ginput/tiny_graph.txt \-of org.apache.giraph.io.formats.IdWithValueTextOutputFormat \-op /user/training/goutput/shortestpathsC2 \-ca SimpleShortestPathsVertex

org.apache.giraph.GiraphRunner Classe utilisé pour démarrer les exemplesorg.apache.giraph.examples.SimpleShortestPathsComputation Dans ce cas il va calculer le chemin le plus court-ca mapred.job.tracker=headnodehost:9010 Nœud principale du Cluster-vif org.apache.giraph.io;formats.JsonLongDoubleFloatDoubleVertexInputFormat Fomat d’entrée à utiliser pour les données en entrée-vip /tiny_Graph,Text Fichier de donnée en entrée-vof org.apache.io.formats.IdWithValueTextOutPutFomart Format de sortie-op /example/outpout/.shortestspaths Emplacement de sortie-w 2 Le nombre de Worker

Une fois la tache terminée il faut visualiser ces fichiers hdfs dfs -text /example/output/shortestpaths/

On aura le résultat suivant 0 1.0 4 5.0 2 2 .0 1 0.0 3 1.0

Vous pourrez visualisé l’éxecution de tous ces services plus en

détails sur notre prochain exposé qui portera sur l’utilisation de HD

Insights sur Azure.