INTRODUCTION AU BIG DATA

Instructrice : Dr Abir KHALDI

2021-2022

Dr Abir KHALDI

Chapitre 2

Chapitre 3 : MapRedue

Plan

MapReduce : Pr sentation

MapReduce : Principe

MapReduce : Programmation Fonctionnelle

MapReduce Programmation Fonctionnelle

MapReduce : Application sur des paires(cl , valeur)

MapReduce : Fonctionnalit

MapReduce : Architecture

MapReduce : Avantages

MapReduce : Critiques

MapReduce : Lab

Dr Abir KHALDI

MapReduce : Pr sentation

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

(cid:2)MapReduce, un mod le de programmation qui fournit un

cadre pour automatiser le calcul parall le sur des donn es

massives.

(cid:2)Ce mod le a t propos dans les ann es 2000, par deux

ing nieurs de chez Google, qui ont observ qu'un grand

nombre des traitements massivement parall les, mis en place

pour les besoins de leur moteur de recherche, suivaient une

les besoins de leur moteur de recherche, suivaient

strat gie de parall lisation identique.

(cid:2)De ces observations est n le mod le de programmation

MapReduce, d crit pour la premi re fois en 2004 dans

un article de recherche.

(cid:2)Son principe g n ral est que toute parall lisation de

traitement

s'effectuer

sur des donn es massives peut

uniquement l'aide de deux types d'op rations : une

op ration map et une op ration reduce.

Dr Abir KHALDI

Mapreduce : Principe

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

(cid:2)Lancien paradigmes de conception d'algorithmes est Divisez pou

r gner pour un probl me initial donn , :

(cid:3)Diviser : d couper le probl me initial en sous-probl mes;

(cid:3)R gner : r soudre les sous-probl mes ind pendamment soit de

mani re r cursive, soit directement s'ils sont de petite taille;

(cid:3)Combiner

probl mes

combinant les solutions des diff rents sous-probl mes.

: construire la solution du probl me initial en

(cid:2)MapReduce c'est Divisez pour distribuer pour r gner en ce sens que

la strat gie mise en place pour ex cuter un calcul sur des donn es

massives consiste d couper les donn es en sous-ensembles de plus

petite taille, que nous appellerons des lots ou des fragments dans la

suite, et affecter chaque lot une machine du cluster permettant ainsi

leur traitement en parall le. Il suffira ensuite d'agr ger l'ensemble des

r sultats interm diaires obtenus pour chaque lot pour construire le

r sultat final.

Dr Abir KHALDI

Mapreduce : Programmation Fonctionnelle

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

(cid:3) MapReduce s'inspire tr s largement du paradigme de programmation

et plus particuli rement des op rateurs de listes map et reduce. En

programmation fonctionnelle:

(cid:1) map consiste appliquer une m me fonction tous les l ments de la

liste;

map(f) =

map(*4)[2, 3, 6] = [8, 12, 24]

(cid:1) reduce applique une fonction r cursivement une liste et retourne un

seul r sultat;

reduce(f) = f(x0, f(x1, f(x2, ...)))

reduce(+)[2, 3, 6] = (2 + (3 + 6)) = 11

Map et reduce sont des op rateurs g n riques et leur combinaison

permet donc de mod liser norm ment de probl mes.

Dr Abir KHALDI

MapReduce : Application sur des paires(cl , valeur)

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

(cid:3) Pour rendre le fonctionnement de MapReduce plus concret, nous allons

l'illustrer avec WordCount .

(cid:3)Prenons en entr e une collection de documents textuels :

l'objectif de

Wordcount est de calculer le nombre d'occurrences de chaque mot dans la

collection.

(cid:3)Supposons que vous pouvez stocker l'ensemble de votre collection dans un seul

fichier ; alors, ce n'est vraiment pas un probl me difficile et les quelques lignes de

code ci-dessous peuvent r pondre ce probl me.

(cid:3)On utilise ici un dictionnaire qui est une collection d' l ments de type(cl ,

valeur). La cl correspond au mot et la valeur un entier correspondant son

nombre d'occurrences.

(cid:3)Si votre texte est assez volumineux comme l'image de la collection Wikipedia

qui contient environ 27 milliards de mots (source : Wikipedia), cette solution

s quentielle ne suffira pas et il est n cessaire de r aliser ce comptage de mani re

distribu e. C'est l qu'intervient MapReduce.

Dr Abir KHALDI

MapReduce :Application sur des paires(cl , valeur)

Nous allons travailler sur deux extraits du texte de la chanson "Le

Jour se l ve" de Grand Corps Malade.

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

Dr Abir KHALDI

MapReduce :Application sur des paires(cl , valeur)

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

(cid:3)Nous allons donc supposer que nos donn es d'entr e ont t

fragments et qu'une op ration de

d coup es en diff rents

simplification a t appliqu e sur chaque fragment pour supprimer

les caract res de ponctuation, transformer chaque mot en son

singulier ("nos" devient "notre") et ne garder que les mots de plus de

3 caract res.

(cid:3)Nous pouvons repr senter tr s facilement ces fragments sous la

forme de paires(cl , valeur), en prenant comme cl le nom du fichier

et comme valeur la cha ne de caract res correspondant au contenu

textuel du fichier.

Dr Abir KHALDI

MapReduce :Application sur des paires(cl , valeur)

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

(cid:3) Il nous faut maintenant d terminer la cl utiliser pour l'op ration

map. La mani re dont nous avons r pondu au probl me en

s quentiel nous oriente tout naturellement vers le choix de prendre

comme cl s les mots du texte.

L' tape suivante est d' crire le code de l'op ration map selon le

sch ma impos par MapReduce, c'est- -dire qu'elle doit retourner

une liste de paires(cl , valeur). Dans le cas de WordCount, l'op ration

map va donc d composer le texte du fragment fourni en entr e et

elle va g n rer pour chaque mot une paire(mot, 1). Nous pouvons

crire tout cela tr s simplement en python.

Dr Abir KHALDI

MapReduce :Application sur des paires(cl , valeur)

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

Nous avons donc maintenant tout ce qu'il faut pour l' tape MAP de

MapReduce qui consiste appliquer l'op ration map chaque

fragment en parall le comme l'illustre la figure ci-dessous.

Dr Abir KHALDI

MapReduce :Application sur des paires(cl , valeur)

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

A la fin de l' tape MAP, nous avons donc plusieurs listes de paires(cl ,

valeur).

Nous sommes maintenant capables de regrouper et de trier, par cl

commune, les r sultats interm diaires fournis par l' tape MAP. Cela

correspond l' tape SHUFFLE and SORT.

Dr Abir KHALDI

MapReduce :Application sur des paires(cl , valeur)

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

avons maintenant

paires(cl ,

ensemble

Il nous reste maintenant crire le code de

(cid:3) Nous

liste_de_valeurs).

l'op ration reduce, selon le sch ma impos par MapReduce.

(cid:3) Pour WordCount, l'op ration reduce consiste sommer toutes les

valeurs de la liste associ e une cl . Nous pouvons nouveau crire

cela tr s simplement en python.

(cid:3)L' tape REDUCE de MapReduce peut donc tre appliqu e. Elle

paire(cl ,

l'op ration reduce

consiste

liste_de_valeurs)en parall le.

appliquer

chaque

Dr Abir KHALDI

MapReduce :Application sur des paires(cl , valeur)

Le sch ma ci-dessous illustre l'application des diff rentes tapes de

MapReduce notre exemple.

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

Dr Abir KHALDI

Mapreduce : Fonctionnalit s

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

fonctions

paradigme

conception

g n ralisation

(cid:3)La

d'algorithmes diviser pour r gner au cadre distribu .

(cid:3)Un mod le de programmation reposant sur la combinaison de

deux

inspir es de la

programmation fonctionnelle.

(cid:3)Un Framework d'ex cution prenant en charge le d ploiement et

la distribution des calculs sur un cluster.

(cid:3)Le r le des d veloppeurs d'applications distribu es, c'est donc de

penser en MapReduce :

simples, map et

reduce,

(cid:4)Choisir une mani re de d couper les donn es afin que

l'op ration MAP soit parall lisable.

(cid:4)Choisir la cl utiliser pour le probl me cibl .

(cid:4) crire le code de la fonction pour l'op ration MAP.

(cid:4) crire le code de la fonction pour l'op ration REDUCE.

Dr Abir KHALDI

Mapreduce : Architecture

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

Hadoop s'occupe du traitement de donn es grace MapReduce, nouveau avec

une architecture de type ma tre-esclave. Dans cette architecture :

" Le job tracker est un processus ma tre qui va se charger de l'ordonnancement

des traitements et de la gestion de l'ensemble des ressources du syst me. Il re oit

(du client) la ou les t ches MapReduce ex cuter (un .jar Java) ainsi que les

donn es d'entr e et le r pertoire o stocker les donn es de sorties.

Il est pour cela en communication avec le name node d'HDFS. Le job tracker est

en charge de planifier l'ex cution des t ches et de les distribuer sur des task

trackers Comme il sait o trackers. sont situ s les blocs de donn es, il peut

peut

optimiser la colocalisation traitements/donn es

" Un task tracker est une unit de calcul du cluster. Il assure, en lan ant une

nouvelle machine virtuelle java (JVM), l'ex cution et le suivi des t ches MAP ou

REDUCE s'ex cutant sur son noeud et qu'il re oit du job tracker. Il dispose d'un

nombre limit de slots d'ex cution et donc un nombre limit de t ches MAP,

REDUCE ou SHUFFLE pouvant s' x cuter simultan ment sur le noeud. Il est aussi

en communication constante avec le job tracker pour l'informer de l' tat

d'avancement des t ches (heartbeat call).

" le probl me de la tol rance aux pannes persiste car en cas de d faillance, le job

inform ou sans nouvelle du task tracker, doit pouvoir ordonner la

tracker,

r ex cution de la t che.

donn es,

Dr Abir KHALDI

Mapreduce : Architecture

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

Dr Abir KHALDI

Mapreduce : Avantages

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

(cid:2)MapReduce fonctionne sur un large cluster de machines et est

hautement scalable. Il peut tre impl ment sous plusieurs formes gr ce

aux diff rents langages de programmation comme Java, C# et C++.

(cid:2) Pour les d veloppeurs d butants, le Framework est pratique car les

routines de biblioth ques peuvent tre utilis es pour cr er des

programmes parall les sans se soucier des communications infra-cluster,

de la surveillance de t ches ou de la gestion derreurs.

de la surveillance de t ches ou de la gestion derreurs

(cid:2)Les programmeurs sans exp rience dans le domaine des syst mes

parall les et distribu s peuvent facilement utiliser des ressources de

larges syst mes distribu s.

(cid:2)Afin de distribuer les donn es entr es et de souder les r sultats,

il op re en parall le sur des clusters massifs. La taille dun cluster na pas

dimpact sur le traitement des donn es. De fait, les t ches peuvent etre

r parties sur nimporte quelle quantit de serveurs.

Dr Abir KHALDI

Mapreduce : Avantages

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

(cid:2)MapReduce et Hadoop simplifient le d veloppement de logiciels. Il

est disponible dans plusieurs langages dont C, C++, Java, Ruby, Pearl

et Python. Les programmeurs peuvent utiliser les biblioth ques

MapReduce notamment bas sur Java 8 pour cr er des t ches sans

se soucier de la communication ou de la coordination entre les

nSuds.

(cid:2)Le principal avantage de ce framework est

sa tol rance

aux erreurs. Une t che est transf r e dun nSud lautre, et si le

nSud principal remarque quun nSud a t silencieux pendant un

intervalle de temps plus long que pr vu, le nSud principal assigne

nouveau la t che un autre nSud. Ceci cr e une r silience et facilite

le lancement de cette structure logicielle sur des serveurs peu

co teux.

Dr Abir KHALDI

Mapreduce : Critiques

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

(cid:2)MapReduce ne permet de r soudre quun faible nombre de

probl mes.

(cid:2)MapReduce utilise des entr es de fichiers et ne prenne pas en

charge suffisamment de sch mas ceci emp chent laugmentation

des performances propos es par la plupart des bases de

donn es les plus communes.

Dr Abir KHALDI

Mapreduce : Lab

(cid:2) Voir Lab1 . Hadoop MapReduce

(cid:2) Voir Lab1 Hadoop MapReduce

Dr Abir KHALDI

(cid:1)Pr sentation

(cid:1)Principe

(cid:1)Programmation

Fonctionnelle

(cid:1)Application sur

des paires(cl ,

valeur)

(cid:1)Fonctionnalit

(cid:1)Architecture

(cid:1)Avantages

(cid:1)Critiques

(cid:1)Lab

Questions ?

[email protected]

Dr Abir KHALDI