Introduction aux algorithmes
MapReduce
Mathieu Dumoulin (GRAAL), 14 Février 2014

Plan Introduction de laproblématique Tutoriel MapReduce Design d’algorithmes
MapReduceTri, somme et calcul demoyenne PageRank en MapReduce Conclusion

mathieu.dumoulin@gmail.com

2014-02-14

« Big Data »Big data is high volume, high velocity, and/or high variety
information assets that require new forms of processing to enableenhanced decision making, insight discovery and process optimization- Gartner, updated definition of big data (2012)

Building new analytic applications based on new types of data, inorder to better serve your customers and drive a better competitive
advantage- David McJannet, Hortonworks

mathieu.dumoulin@gmail.com

2014-02-14

Un outil spécialiséProblèmes où Hadoop est envisageable:
 Trop de données (GB,TB,PB)
 Améliorer des résultats existants
 Obtenir de nouveaux résultats
 Combiner des données hétérogènes Croissance rapide (et constante) des données Temps de traitement lent (minutes, heures) Budgets limités Plusieurs ordinateurs déjà disponibles

mathieu.dumoulin@gmail.com

2014-02-14

Hadoop au cœur du big data

mathieu.dumoulin@gmail.com

2014-02-14

MapReduce au cœur de Hadoop
Hadoop MapReduce is a software framework for easily writing
applications which process vast amounts of data (multi-terabytedata-sets) in-parallel on large clusters (thousands of nodes) ofcommodity hardware in a reliable, fault-tolerant manner.
- Hadoop Tutorial, hadoop.apache.org

mathieu.dumoulin@gmail.com

2014-02-14

Gain d’utiliser Hadoop?
 Tout le travail de distribution, balancement de charge,synchronisation et de gestion d’erreur est géré
automatiquement Il suffit de programmer Map et Reduce(Java, C++,Python, bash, etc.)
 Une grappe Hadoop peut évoluer facilement en ajoutant

des nœuds en tout temps
 Hadoop offre un rapport performance-prix très

compétitif (Amazon EMS, réutilisation de PC existants,aucun coûts de licences ni de matériel spécialisé HPC)
mathieu.dumoulin@gmail.com

2014-02-14

L’exemple WordCountOn veut trouver les k mots les plus fréquents dans unecollection de textes.
def word_count(text, k):counts = defaultdict(int)for word in text.split():counts[word.lower()] += 1
return sorted(counts, key=counts.get, reverse=True)[:k]Mais cette solution est-elle la bonne si le texte est très
grand?
Et s’il est très, très, …, très grand?
mathieu.dumoulin@gmail.com

2014-02-14

La taille en soit peut être un problème

TailleProblème

100M mots• Pas de problèmes• 1000M mots

• Mémoire insuffisante• 100MM mots

• Processeur insuffisant• 1000MM mots

• 1 ordinateur insuffisant• Plus encore!

• Réseau insuffisant,contrôleur surchargé•

mathieu.dumoulin@gmail.com

Solution• Naïve avec 1 seul
ordinateur• Utiliser le disque,Fenêtre glissante• Multithreading,éliminer < N• Distribuer le calcul• MapReduce (ousolution du mêmeordre comme MPI,etc.)
2014-02-14

Tutoriel MapReduce

MapReduce
mathieu.dumoulin@gmail.com

2014-02-14

Map et Reduce: la paire Clef-Valeur
Mapper:Données(HDFS)
Reducer:(K,V) → (K’, V’)(K’, [V’, V’,…]) → (K’’, V’’)
Données’(HDFS)

mathieu.dumoulin@gmail.com

2014-02-14

MapReduce en action: WordCount illustré

mathieu.dumoulin@gmail.com

2014-02-14

Map et Reduce: Shuffle and Sort

Source: Data Intensive Text Processing with MapReduce, Jimmy Lin and Chris Dyer, 2010
mathieu.dumoulin@gmail.com

2014-02-14

Map et Reduce (moins simplifié) Les vrai opérateurs:Mapper Combiner
 Partitioner
 Reducermathieu.dumoulin@gmail.com

2014-02-14

Design d’algorithmes pour MapReduce
1- Il faut reformuler les algorithmes en fonctionnel:

2- La bande passante duréseau est une ressource
limitée à optimiser:mathieu.dumoulin@gmail.com

2014-02-14

Exemples choisis
 Exemples simples:Tri Somme Moyenne Un exemple complet:

PageRank Bonus:
K-Means (Lloyd’s algorithm)

mathieu.dumoulin@gmail.com

2014-02-14

Trier en MapReduce Propriété du réducteur: les paires sont traitée dansl’ordre (selon la clef), les réducteurs sont aussi dansl’ordreMapper:Émettre l’élément à trier comme nouvelle clef
Reducer:
Aucun (i.e. fonction identité)

mathieu.dumoulin@gmail.com

2014-02-14

Calcul d’une somme (WordCount)mathieu.dumoulin@gmail.com

2014-02-14

Amélioration: le combiner

mathieu.dumoulin@gmail.com

2014-02-14

Calcul de moyenne

Utiliser un combiner est il approprié?

Si on reprend le reducer comme combiner,l’algorithme est-il encore correct?
mathieu.dumoulin@gmail.com 2014-02-14

Comment améliorer ce calcul?

mathieu.dumoulin@gmail.com

2014-02-14

Design d’une solution MapReduce pourl’algorithme PageRankmathieu.dumoulin@gmail.com

2014-02-14

Qu’est-ce que PageRank?
Distribution de probabilité sur les pages web qui
représente la chance qu’un utilisateur naviguant au
hasard arrive à une page web particulière.
Notes:
 Le web est un graphe orienté, une page est un nœudet les hyperliens sont des arcs.
 L’algorithme recalcule la probabilité de toutes les
pages itérativement jusqu’à convergencemathieu.dumoulin@gmail.com

2014-02-14

Comment calculer PageRank (simplifié)
𝑃𝑅 𝑝𝑖 =𝑝𝑖 ∈𝑀(𝑝𝑖 )𝑃𝑅(𝑝𝑗 )
𝐿(𝑝𝑗 )• p1,p2,…,pN sont les pages web (les nœuds dugraphe)• M(pi) est l’ensemble des pages ayant un lien vers pi• L(pj) est le nombre de liens sortant de la page pj• N est le nombre total de pages web
Note: Pour simplifier, on élimine le facteur d’atténuation, paramétrisé parla probabilité que l’utilisateur arrête de naviguer.

Page, Lawrence and Brin, Sergey and Motwani, Rajeev and Winograd, Terry (1999) The
PageRank Citation Ranking: Bringing Order to the Web. Technical Report. Stanford InfoLab.
mathieu.dumoulin@gmail.com

2014-02-14

PageRank par un exemple
Le web a trois pages web: A, B et C

Initialisation: PR(A) = PR(B) = PR(C) = 0.33
Jusqu’à convergence:
𝑃𝑅(𝐵)𝑃𝑅 𝐴 =2
𝑃𝑅(𝐴)𝑃𝑅 𝐵 =
2
𝑃𝑅(𝐴) 𝑃𝑅(𝐵)𝑃𝑅 𝐶 =+22
mathieu.dumoulin@gmail.com

2014-02-14

PageRank en MapReduce
Donnés de départ:collection de pages web (URL, [URLlien])
1.

Bâtir et initialiser le graphe2.

Jusqu’à convergence, recalculer PageRank pour chaquepage web

3.

Retourner les K premières valeurs de PageRank (pasprésenté)
mathieu.dumoulin@gmail.com

2014-02-14

Étape 1: Bâtir le graphe
Mapper:Entrée: une page web
Pour chaque lien de la page, émettre:
clef: URLpage
valeur: URLlien
Reducer:
Entrée:clef: URLpage
valeurs: [URLlien, …]Sortie:clef: URLpage
valeur: «PR;[URLlien]»mathieu.dumoulin@gmail.com

2014-02-14

Étape 2: calculer PageRank - Map
Mapper:Entrée:clef: URLpage
valeur: «PR;[URLlien,…]»Sortie:Pour chaque URLlien, émettre:

clef: URLlien
valeur: «URLpage;PR, nb_urllien»

Où: nb_urllien est le compte de URLlien
mathieu.dumoulin@gmail.com

2014-02-14

Étape 2: calculer PageRank - Reduce

Reducer:
Entrée:clef: URLpage
valeurs: [«URLinverse;PR, nb_urlpage_inverse», …]
Traitement: calculer le PR
Sortie:clef: URLpage
valeurs: « PR;[URLlien]»mathieu.dumoulin@gmail.com

2014-02-14

PageRank en MapReduce: Résultats

Notes:
Source: PageRank Calculation using Map Reduce - The Cornell Web Lab (2008)
Résultats obtenus sur une grappe Hadoop de 50 nœuds (Intel Xeon 2.66GHz 16GB ram)
Mon implémentation: https://bitbucket.org/mathieu_dumoulin/pagerank-mr
mathieu.dumoulin@gmail.com

2014-02-14

MapReduce PageRank: Résultats(8 fois plus de pages que Cornell)mathieu.dumoulin@gmail.com

2014-02-14

MapReduce PageRank: Résultats

mathieu.dumoulin@gmail.com

2014-02-14

Conclusion (malheureuse) MapReduce est une solution puissante au problème deprogrammation distribuée La plate-forme fait toute la distribution et la gestion deserreurs
 Le travail de programmation commence par laformulation d’un algorithme MapReduce
Ce n’est pas toujours facile Trouver et formuler un algorithme performant est relativement
difficile Le travail réel de programmation demande une maîtrise (très)avancée de Javamathieu.dumoulin@gmail.com

2014-02-14

Conclusion

mathieu.dumoulin@gmail.com

2014-02-14

Conclusion
On n’est pas prisonnier de MapReduce pour utiliser une
grappe Hadoop!

Apache Pig: optimiser les tâches de ETL
Apache Hive: analyser ses données façon SQL
Cascading et Apache Crunch: librairies Java qui simplifientles opérations difficiles en MapReduce
Apache Mahout: librarie de machine learning qui peututiliser une grappe Hadoop « automatiquement »mathieu.dumoulin@gmail.com

2014-02-14

Questions et commentaires
Hadoop est de plus en plus une composanted’infrastructure « standard » pour le traitement dedonnée à grande échelle et est promis à un bel avenir!

mathieu.dumoulin@gmail.com

2014-02-14

Partie Bonus MapReduce et Machine Learning

Exemple Algorithme K-Meansmathieu.dumoulin@gmail.com

2014-02-14

Map et Reduce et le machine learning?
Problématique exemple: recherche de paramètres optimauxYasser Ganjisaffar, Thomas Debeauvais, Sara Javanmardi, Rich Caruana, and Cristina Videira Lopes. 2011. Distributed tuning ofmachine learning algorithms using MapReduce Clusters. In Proceedings of the Third Workshop on Large Scale Data Mining:Theory andApplications(LDMTA '11). ACM, New York, NY, USA, , Article 2 , 8 pages. DOI=10.1145/2002945.2002947
http://doi.acm.org/10.1145/2002945.2002947

mathieu.dumoulin@gmail.com

2014-02-14

Bonus:Algorithme K-means clustering Problème: regrouper des données en K groupes

mathieu.dumoulin@gmail.com

2014-02-14

Algorithme K-means(Lloyd’s Algorithm)

Initialiser les K centroïdes (d’une certaine façon)
Pour chacune de plusieurs d’itérations:
Pour chaque point:
Assigner au centroïde le plus proche
Selon une mesure de distance (ex: distance Euclidienne)

Pour chaque centroïde:Recalculer sa position en faisant la moyenne
des membres de son groupe
mathieu.dumoulin@gmail.com

2014-02-14

K-means en MapReduce Driver: lancer les itérations
 Combien d’étapes map-reduce?

Une seule!

mathieu.dumoulin@gmail.com

2014-02-14

K-means MapReduce Driver: le “main” qui lance les tâches (Job) MapReduce et qui

itère jusqu’à convergence Mapper: Assigner chaque point au cluster le plus proche (enparallèle!)Entrée: Key: Null value: vecteur
 Sortie: Key: index du centroïde le plus proche, value: vecteur Reducer: Calculer la moyenne des points membre du cluster(en parallèle!)Key: Information partagée: les vecteurs des centroïdes
mathieu.dumoulin@gmail.com

2014-02-14

K-Means et MapReduce: État de l’art
Bahman Bahmani, Benjamin Moseley, Andrea Vattani, RaviKumar, and Sergei Vassilvitskii. 2012. Scalable kmeans++. Proc.VLDB Endow. 5, 7 (March 2012), 622-633.
http://theory.stanford.edu/~sergei/papers/vldb12-kmpar.pdf

Implémenté dans la librairie Apache Mahout

mathieu.dumoulin@gmail.com

2014-02-14