Chapitre 3: Map-Reduce

MapReduce : Présentation (1/4)

• Pour exécuter un problème large de manière distribuée, il faut pouvoir découper le problème en plusieurs
problèmes de taille réduite à exécuter sur chaque machine du cluster (stratégie algorithmique dite du
divide and conquer
/ diviser pour régner).
• De multiples approches existent et ont existé pour cette division d'un problème en plusieurs « sous-tâches ».

• MapReduce est un paradigme (un modèle) visant à généraliser les approches existantes pour produire une
approche unique applicable à tous les problèmes.

• MapReduce existait déjà depuis longtemps, notamment dans les langages

fonctionnels (Lisp), mais la présentation du paradigme sous une forme
« rigoureuse », généralisable à tous les problèmes et orientée calcul distribué est attribuable à un whitepaper
issu du département de recherche de Google publié en 2004 (« MapReduce: Simplified Data Processing on
Large Clusters »).
C’est quoi Map-Reduce
u Patron d’architecture de développement permettant de traiter des données
volumineuses de manière parallèle et distribuée
u Dean et al., 2004
u Au lieu de parcourir le fichier séquentiellement, il est divisé e
n
morceaux qui sont parcourus en parallèle
u Exemple
u Vous ayez plusieurs magasins que vous gérez à travers le monde
u Un très grand livre de comptes contient TOUTES les ventes 2012-01-01 London Clothes 25.99
2012-01-01 Miami Music 12.15
u Objectif : Calculer le total des ventes par magasin pour l’année en cours 2012-01-02 NYC Toys 3.10
2012-01-02 Miami Clothes 50.00
u Supposons que les lignes du livres aient la forme suivante:
u Jour Ville produit Prix
Méthode traditionnelle

u Possibilité́ :
u Pour chaque entrée, saisir la ville et le prix de vente
u Si on trouve une entrée avec une ville déjà saisie, on les regroupe en
faisant la somme des ventes
u Dans un environnement traditionnel, on fera des Hashtable sous la forme
<clé-valeur>
u Dans ce cas, la clé sera l’adresse du magasin et la valeur le total de ventes

2012-01-01 London Clothes 25.99

2012-01-01 Miami Music 12.15
2012-01-02 NYC Toys 3.10
2012-01-02 Miami Clothes 50.00

London 25.99 London 25.99

Miami 12.15 Miami 62.15
NYC 3.10 NYC 3.10
Méthode traditionnelle

u Si on utilise les hashtables sur 1To, quels sont les problèmes ?

 Ça ne marchera pas ?
2012-01-01 London Clothes 25.99
 Problème de mémoire ? 2012-01-01 Miami Music 12.15
2012-01-02 NYC Toys 3.10
 Temps de traitement long ?
2012-01-02 Miami Clothes 50.00
 Réponses erronées ?

u Le traitement séquentiel peut s’avérer long Clef Valeur

London 25.99
Miami 62.15
u Plus on a de magasins, plus l’ajout des valeurs à la table est long NYC 3.10
u Il est possible de tomber à court de mémoire pour enregistrer
cette table
u Mais cela peut marcher, et le résultat sera correct
Map-Reduce

u Map-Reduce : Moyen plus efficace et rapide de traiter ces données

u Au lieu d’avoir une seule personne qui parcourt le livre, si on en recrutait
plusieurs?
u Appeler un premier groupe les Mappers et
un autre les Reducers Mappers
u Diviser le livre en plusieurs parties, et en
donner une à chaque Mapper
u Les Mappers peuvent travailler en même temps,
chacun sur une partie des données

Reducers
Map-Reduce
Mappers
u Mappers
u Pour chaque entrée, saisir la ville et le total de ventes dans
une fiche
u Rassembler les fiches d’un même magasin dans une pile
N.Y.C. Miami N.Y.C. L. A. Miami N.Y.C
u Reducers L. A.
u Chaque reducer sera responsable d’un ensemble de magasins
u Collectent les fiches associées des différents mappers
u Pour chaque ville, ils parcourent les piles en ordre N.Y.C
alphabétique (Los Angeles avant Miami) et font la somme Miami L. A.
des enregistrements N.Y.C

Miami L. A.
N.Y.C
Reducers $603.768
$300,578 $432.900
Map-Reduce
Mappers
u Un Reducer reçoit des données comme suit :
u L.A 12.34
u L.A 99.07
u NYC 3.14 N.Y.C. Miami N.Y.C. L. A. Miami N.Y.C
u NYC 99.77
L. A.
u NYC 88.99
u Pour chaque entrée, de quoi avons-nous besoin pour calculer
la totalité́ des ventes pour chaque magasin ?
N.Y.C
 Coût précédent
Miami L. A.
N.Y.C
 Coût en cours
Miami L. A.
 Ventes totales par magasin N.Y.C
Reducers $603.768
 Magasin précédent $300,578 $432.900

 Magasin en cours
MapReduce : Présentation (2/4)

MapReduce définit deux opérations distinctes à effectuer sur les données

d'entrée:

• La première, MAP, va transformer les données d'entrée en une série de couples clef/valeur. Elle va
regrouper les données en les associant à des clefs, choisies de telle sorte que les couples clef/valeur aient
un sens par rapport au problème à résoudre. Par ailleurs, cette opération doit être parallélisable: on doit
pouvoir découper les données d'entrée en plusieurs fragments, et faire exécuter l'opération MAP à
chaque machine du cluster sur un fragment distinct.

• La seconde, REDUCE, va appliquer un traitement à toutes les valeurs de chacune des clefs distinctes
produite par l'opération MAP. Au terme de l'opération REDUCE, on aura un résultat pour chacune des
clefs distinctes. Ici, on attribuera à chacune des machines du cluster une des clefs uniques produites par
MAP, en lui donnant la liste des valeurs associées à la clef. Chacune des machines effectuera alors
l'opération REDUCE pour cette clef.
MapReduce : Présentation (3/4)
On distingue donc 4 étapes distinctes dans un traitement MapReduce:

• Découper (split) les données d'entrée en plusieurs fragments.

• Mapper chacun de ces fragments pour obtenir des couples (clef ; valeur).

• Grouper (shuffle) ces couples (clef ; valeur) par clef.

• Réduire (reduce) les groupes indexés par clef en une forme finale, avec une valeur pour chacune des
clefs distinctes.

En modélisant le problème à résoudre de la sorte, on le rend parallélisable – chacune de ces tâches à

l'exception de la première seront effectuées de manière distribuée.
MapReduce : Présentation (4/4)

Pour résoudre un problème via la méthodologie MapReduce avec Hadoop, on

devra donc:

• Choisir une manière de découper les données d'entrée de telle sorte que l'opération MAP soit
parallélisable.

• Définir quelle CLEF utiliser pour notre problème.

• Écrire le programme pour l'opération MAP.

• Écrire le programme pour l'opération REDUCE..

… et Hadoop se chargera du reste (problématiques calcul distribué, groupement par clef

distincte entre MAP et REDUCE, etc.).
MapReduce : Exemple concret (1/8)

• Imaginons qu'on nous donne un texte écrit en langue Française. On souhaite

déterminer pour un travail de recherche quels sont les mots les plus utilisés au sein de
ce texte (exemple Hadoop très répandu).

• Ici, nos données d'entrée sont constituées du contenu du texte.

• Première étape: déterminer une manière de découper (split) les données d'entrée pour
que chacune des machines puisse travailler sur une partie du texte.

• Notre problème est ici très simple – on peut par exemple décider de découper les
données d'entrée ligne par ligne. Chacune des lignes du texte sera un fragment de nos
données d'entrée.
 MapReduce : Exemple concret (2/8)
• Nos données d'entrée (le texte):

Celui qui croyait au ciel

Celui qui n'y croyait pas (Louis Aragon, La rose etle
[…] Réséda, 1943, fragment)
Fou qui fait le délicat
Fou qui songe à ses querelles

• Pour simplifier les choses, on va avant le découpage supprimer toute

ponctuation et tous les caractères accentués. On va également passer
l'intégralité du texte en minuscules.
MapReduce : Exemple concret (3/8)

• Nos données d'entrée (le texte):

celui qui croyait auciel

celui qui ny croyait pas

fou qui fait ledelicat

fou qui songe a sesquerelles

• … on obtient 4 fragments depuis nos données d'entrée.

MapReduce : Exemple concret (4/8)
• On doit désormais déterminer la clef à utiliser pour notre opération
MAP, et écrire le code de l'opération MAP elle-même.

• Puisqu'on s'intéresse aux occurrences des mots dans le texte, et qu'à terme on aura
après l'opération REDUCE un résultat pour chacune des clefs distinctes, la clef qui
s'impose logiquement dans notre cas est: le mot-lui même.

• Quand à notre opération MAP, elle sera elle aussi très simple: on va simplement
parcourir le fragment qui nous est fourni et, pour chacun des mots, générer le couple
clef/valeur: (MOT ; 1). La valeur indique ici l’occurrence pour cette clef - puisqu'on a
croisé le mot une fois, on donne la valeur « 1 ».
MapReduce : Exemple concret (5/8)
• Le code de notre opération MAP sera donc (ici en pseudo code):
POUR MOT dans LIGNE,
FAIRE : GENERER
COUPLE (MOT; 1)

• Pour chacun de nos fragments, les couples (clef; valeur) générés seront
donc:

celui qui croyait auciel (celui;1) (qui;1) (croyait;1) (au;1)(ciel;1)

celui qui ny croyait pas (celui;1) (qui;1) (ny;1) (croyait;1) (pas;1)

fou qui fait ledelicat (fou;1) (qui;1) (fait;1) (le;1)(delicat;1)

(fou;1) (qui;1) (songe;1) (a;1)(ses;1)
fou qui songe a sesquerelles
(querelles;1)
28
MapReduce : Exemple concret (6/8)
Une fois notre opération MAP effectuée (de manière distribuée),

• Hadoop groupera (shuffle) tous les couples par clef commune.

Cette opération est effectuée automatiquement par Hadoop. Elle est, là aussi,
effectuée de manière distribuée en utilisant un algorithme de tri distribué, de
manière récursive. Après son exécution, on obtiendra les 15 groupes suivants:

(celui;1) (celui;1) (fou;1) (fou;1) (fait;1) (le;1)

(qui;1) (qui;1) (qui;1) (qui;1) (delicat;1) (songe;1)

(croyait;1) (croyait;1) (a;1) (ses;1)

(au;1) (ciel;1) (ny;1) (pas;1) (querelles;1)

MapReduce : Exemple concret (7/8)
• Il nous reste à créer notre opération REDUCE, qui sera appelée pour
chacun des groupes/clef distincte.

• Dans notre cas, elle va simplement consister à additionner toutes les

valeurs liées à la clef spécifiée:

TOTAL=0
POUR COUPLE dans GROUPE, FAIRE:
TOTAL=TOTAL+1
RENVOYER TOTAL
MapReduce : Exemple concret (8/8)
• Une fois l'opération REDUCE effectuée, on obtiendra donc une valeur
unique pour chaque clef distincte. En l’occurrence, notre résultat sera:

qui : 4
celui : 2
croyait : 2 •On constate que le mot le plus utilisé dans notre texte est
fou : 2 « qui », avec 4 occurrences, suivi de « celui », « croyait » et
au : 1 « fou », avec 2 occurrences chacun.
ciel : 1
ny : 1
pas : 1
fait :1
[…]
MapReduce : Exemple concret - Conclusion

• Notre exemple est évidemment trivial, et son exécution aurait été instantanée même
sur une machine unique, mais il est d'ores et déjà utile: on pourrait tout à fait utiliser
les mêmes implémentations de MAP et REDUCE sur l'intégralité des textes d'une
bibliothèque Française, et obtenir ainsi un bon échantillon des mots les plus utilisés
dans la langue Française.

• L’intérêt du modèle MapReduce est qu'il nous suffit de développer les deux
opérations réellement importantes du traitement: MAP et REDUCE, et de bénéficier
automatiquement de la possibilité d'effectuer le traitement sur un nombre variable
de machines de manière distribuée.
MapReduce : Schéma général
 MapReduce : Exemple – Statistiques web

• Un autre exemple: on souhaite compter le nombre de visiteurs sur chacune des pages
d'un site Internet. On dispose des fichiers de logs sous la forme suivante:

/[Link] [19/05/[Link]+0200]
/[Link] [19/05/[Link] +0200]
/[Link]?id=5 [24/05/[Link] +0200]
/[Link]?id=4 [24/05/[Link] +0200]
/[Link]?id=18 [24/05/[Link] +0200]
...etc...

• Ici, notre clef sera par exemple l'URL d’accès à la page, et nos opérations MAP et
REDUCE seront exactement les mêmes que celles qui viennent d'être présentées: on
obtiendra ainsi le nombre de vue pour chaque page distincte du site.
 MapReduce : Exemple – Graphe social (1/8)

• Un autre exemple: on administre un réseau social comportant

des millions d'utilisateurs.
• Pour chaque utilisateur, on a dans notre base de données la liste des
utilisateurs qui sont ses amis sur le réseau (via une requête SQL).

• On souhaite afficher quand un utilisateur va sur la page d'un autre

utilisateur une indication « Vous avez N amis en commun ».

• On ne peut pas se permettre d'effectuer une série de requêtes SQL à chaque fois que la
page est accédée (trop lourd en traitement). On va donc développer des programmes
MAP et REDUCE pour cette opération et exécuter le traitement toutes les nuits sur
notre base de données, en stockant le résultat dans une nouvelle table.
MapReduce : Exemple – Graphe social (2/8)
• Ici, nos données d'entrée sous la forme Utilisateur =>Amis:
A => B, C, D
B => A, C, D, E
C=> A, B, D, E
D => A, B, C, E
E=>B, C, D

• Puisqu'on est intéressé par l'information « amis en commun entre deux

utilisateurs » et qu'on aura à terme une valeur par clef, on va choisir pour clef la
concaténation entre deux utilisateurs. Par exemple, la clef « A-B » désignera « les
amis en communs des utilisateurs A et B ».

• On peut segmenter les données d'entrée là aussi par ligne.

MapReduce : Exemple – Graphe social (3/8)
• Notre opération MAP va se contenter de prendre la liste des amis fournie en entrée, et
va générer toutes les clefs distinctes possibles à partir de cette liste. La valeur sera
simplement la liste d'amis, telle quelle.

• On fait également en sorte que la clef soit toujours triée par ordre alphabétique (clef «
B-A » sera exprimée sous la forme « A-B »).

• Ce traitement peut paraître contre-intuitif, mais il va à terme nous permettre

d'obtenir, pour chaque clef distincte, deux couples (clef;valeur): les deux listes d'amis
de chacun des utilisateurs qui composent la clef.
MapReduce : Exemple – Graphe social (4/8)
• Le pseudo code de notre opération MAP:

UTILISATEUR = [PREMIERE PARTIE DE LA LIGNE]

POUR AMI dans [RESTE DE LA LIGNE], FAIRE:
SI UTILISATEUR < AMI:
CLEF = UTILISATEUR+"-"+AMI
SINON:
CLEF = AMI+"-"+UTILISATEUR
GENERER COUPLE (CLEF; [RESTE DE LA LIGNE])

• Par exemple, pour la première ligne: A => B, C, D

 On obtiendra les couples (clef;valeur):

("A-B"; "B CD") ("A-C"; "B CD") ("A-D"; "B CD")
MapReduce : Exemple – Graphe social (5/8)

• Pour la seconde ligne : B=> A, C, D, E

 On obtiendra ainsi :

("A-B"; "A CDE") ("B-C"; "A CDE") ("B-D"; "A CDE") ("B-E"; " A CDE")

• Pour la troisième ligne : C=> A, B, D, E

 On aura :
("A-C"; "A B D E") ("B-C"; "A BD E") ("C-D"; "A B DE") ("C-E"; " A B DE")

• ...et ainsi de suite pour nos 5 lignes d'entrée.

MapReduce : Exemple – Graphe social (6/8)

• Une fois l'opération MAP effectuée, Hadoop va récupérer les couples

(clef;valeur) de tous les fragments et les grouper par clef distincte. Le
résultat sur la base de nos données d'entrée :

Pour la clef "A-B " : valeurs "A CD E" et "B CD"

Pour la clef "A-C " : valeurs "A BD E" et "B CD"
Pour la clef "A-D " : valeurs "A BCE" et "B CD"
Pour la clef "B-C " : valeurs "A BD E" et "A CD E"
Pour la clef "B-D " : valeurs "A BCE" et "A CD E"
Pour la clef "B-E " : valeurs "A CD E" et "B CD"
Pour la clef "C-D " : valeurs "A BCE" et "A BD E"
Pour la clef "C-E " : valeurs "A BD E" et "B CD"
Pour la clef "D-E " : valeurs "A BCE" et "B CD"

• … on obtient bien, pour chaque clef « USER1-USER2 », deux listes

d'amis: les amis de USER1 et ceux de USER2.
MapReduce : Exemple – Graphe social (7/8)
Il nous faut enfin écrire notre programme REDUCE. Il va recevoir en entrée
toutes les valeurs associées à une clef. Son rôle va être très simple: déterminer
quels sont les amis qui apparaissent dans les listes (les valeurs) qui nous sont
fournies. Pseudo-code:

LISTE_AMIS_COMMUNS=[] // Liste vide au départ.

SI LONGUEUR(VALEURS)!=2, ALORS: // Ne devrait pas se produire.
RENVOYER
ERREUR
SINON :
POUR AMI DANS VALEURS[0], FAIRE :
SI AMI EGALEMENT PRESENT DANS VALEURS[1], ALORS :
// Présent dans les deux listes d'amis, on l'ajoute.
LISTE_AMIS_COMMUNS+=AMI
RENVOYER LISTE_AMIS_COMMUNS
 MapReduce : Exemple – Graphe social (8/8)
• Après exécution de l'opération REDUCE pour les valeurs de chaque clef
unique, on obtiendra donc, pour une clef « A-B », les utilisateurs qui
apparaissent dans la liste des amis de A et dans la liste des amis de B.
Autrement dit, on obtiendra la liste des amis en commun des utilisateurs
A et B. Le résultat:

"A-B " : "C, D"

"A-C " : "B, D"
"A-D " : "B,C" • On sait ainsi que A et B ont pour amis
"B-C " : "A, D, E" communs les utilisateurs C et D, ou encore
"B-D " : "A, C,E" que B et C ont pour amis communs les
"B-E " : "C, D" utilisateurs A, D et E.
"C-D " : "A, B, E"
"C-E" : "B,D"
"D-E " : "B, C"
MapReduce
• A cause du paradigme de programmation MapReduce, tous les traitements ne sont pas
forcément possibles. Ainsi pour utiliser MapReduce, il faut que:
• Les calculs soient parallélisables: si certaines opérations dépendent l’une de l’autre, il n’y
aura pas d’intérêt à utiliser Hadoop et un job MapReduce.
• Traiter de grands volumes de données: la mise en place des tâches d’exécution de
l’opération Map peuvent prendre à elles-seule s 1 min. Donc pour que l’exécution
d’un jobMapReduce soit efficace, il faut que le traitement soit effectué sur un grand nombre
de données.
• Le résultat final soit plus petit que l’ensemble de données de départ: dans le cas contraire,
un job MapReduce n’est pas forcément pertinent. En effet un part du job consiste à agréger
des valeurs donc s’il n’y a pas d’agrégation, une part de l’exécution de ce job est inutile.
• Etre capable de convertir les données en liste de paire clé/valeur: cette contrainte peut être
difficile à mettre en place mais est primordiale pour l’exécution du job MapReduce car la clé
est la seule façon d’avoir un élément permettant, d’abord de séparer différentes valeurs pour
permettre un traitement parallélisable (durant les étapes Map) et ensuite la clé est encore
utilisée pour agréger les valeurs (durant la ou les étapes Reduce).
 MapReduce : Conclusion

• En utilisant le modèle MapReduce, on a ainsi pu créer deux

programmes très simples (nos programmes MAP et REDUCE) de
quelques lignes de code seulement, qui permettent d'effectuer un
traitement somme toute assez complexe.

• Mieux encore, notre traitement est parallélisable: même avec des

dizaines de millions d'utilisateurs, du moment qu'on a assez de
machines au sein du cluster Hadoop, le traitement sera effectué
rapidement. Pour aller plus vite, il nous suffit de rajouter plus de
machines.

• Pour notre réseau social, il suffira d'effectuer ce traitement toutes les

nuits à heure fixe, et de stocker les résultats dans une table. Ainsi,
lorsqu'un utilisateur visitera la page d'un autre utilisateur, un seul
SELECT dans la base de données suffira pour obtenir la liste des amis
en commun – avec un poids en traitement très faible pour le serveur.
Architecture Hadoop: Présentation (1/3)

Comme pour HDFS, la gestion des tâches de Hadoop se base sur deux
serveurs (des daemons):

• Le JobTracker, qui va directement recevoir la tâche à exécuter (un .jar Java), ainsi
que les données d'entrées (nom des fichiers stockés sur HDFS) et le répertoire où
stocker les données de sortie (toujours sur HDFS). Il y a un seul JobTracker sur une
seule machine du cluster Hadoop. Le JobTracker est en communication avec le
NameNode de HDFS et sait donc où sont les données.

• Le TaskTracker, qui est en communication constante avec le JobTracker et va recevoir

les opérations simples à effectuer (MAP/REDUCE) ainsi que les blocs de données
correspondants (stockés sur HDFS). Il y a un TaskTracker sur chaque machine du
cluster.
Architecture Hadoop: Présentation (2/3)
• Comme le JobTracker est conscient de la position des données (grâce au
NameNode), il peut facilement déterminer les meilleures machines auxquelles
attribuer les sous-tâches (celles où les blocs de données correspondants sont
stockés).

• Pour effectuer un traitement Hadoop, on va donc stocker nos données d'entrée sur
HDFS, créer un répertoire où Hadoop stockera les résultats sur HDFS, et compiler
nos programmes MAP et REDUCE au sein d'un
.jar Java.

• On soumettra alors le nom des fichiers d'entrée, le nom du répertoire des résultats,
et le .jar lui-même au JobTracker: il s'occupera du reste (et notamment de
transmettre les programmes MAP et REDUCE aux serveurs TaskTracker des
machines du cluster).
Architecture Hadoop: Présentation (3/3)
Architecture Hadoop: Le JobTracker (1/3)
Le déroulement de l'exécution d'une tâche Hadoop suit les étapes suivantes du point
de vue du JobTracker :

1. Le client (un outil Hadoop console) va soumettre le travail à effectuer au JobTracker : une archive java .jar
implémentant les opérations Map et Reduce. Il va également soumettre le nom des fichiers d'entrée et
l'endroit où stocker les résultats.

2. Le JobTracker communique avec le NameNode HDFS pour savoir où se trouvent les blocs correspondant
aux noms de fichiers donnés par le client.

3. Le JobTracker, à partir de ces informations, détermine quels sont les noeuds TaskTracker les plus appropriés,
c'est à dire ceux qui contiennent les données sur lesquelles travailler sur la même machine, ou le plus proche
possible (même rack/rack proche).

4. Pour chaque « morceau » des données d'entrée, le JobTracker envoie au TaskTracker sélectionné le travail à
effectuer (MAP/REDUCE, code Java) et les blocs de données correspondants.
Architecture Hadoop: Le JobTracker (2/3)
5. Pour chaque « morceau » des données d'entrée, le JobTracker envoie au TaskTracker sélectionné le travail à
effectuer (MAP/REDUCE, code Java) et les blocs de données correspondants.

6. Le JobTracker communique avec les noeuds TaskTracker en train d'exécuter les tâches. Ils envoient
régulièrement un « heartbeat », un message signalant qu'ils travaillent toujours sur la sous-tâche reçue. Si
aucun heartbeat n'est reçu dans une période donnée, le JobTracker considère la tâche comme ayant échouée et
donne le même travail à effectuer à un autre TaskTracker.

7. Si par hasard une tâche échoue (erreur java, données incorrectes, etc.), le TaskTracker va signaler au
JobTracker que la tâche n'a pas pu être exécutée.
Le JobTracker va alors décider de la conduite à adopter :
- Demander au même TaskTracker de ré-essayer.
- Redonner la sous-tâche à un autre TaskTracker.
- Marquer les données concernées comme invalides, etc.
Il pourra même blacklister le TaskTracker concerné comme non-fiable dans certains cas.
49
Architecture Hadoop: Le JobTracker (3/3)
7. Une fois que toutes les opérations envoyées aux TaskTracker (MAP + REDUCE) ont été
effectuées et confirmées comme effectuées par tous les noeuds, le JobTracker marque la
tâche comme « effectuée ». Des informations détaillées sont disponibles (statistiques,
TaskTracker ayant posé problème, etc.).

Remarques

• Par ailleurs, on peut également obtenir à tout moment de la part du JobTracker des informations sur
les tâches en train d'être effectuées: étape actuelle (MAP, SHUFFLE, REDUCE), pourcentage de
complétion, etc.

• La soumission du .jar, l'obtention de ces informations, et d'une manière générale toutes les opérations
liées à Hadoop s'effectuent avec le même unique client console vu précédemment: hadoop (avec
d'autres options que l'option fs vu précédemment).
 Architecture Hadoop: Le TaskTracker

• Le TaskTracker dispose d'un nombre de « slots » d'exécution. A chaque « slot » correspond une tâche
exécutable (configurable).

• Lorsqu'il reçoit une nouvelle tâche à effectuer (MAP, REDUCE, SHUFFLE) depuis le JobTracker, le
TaskTracker va démarrer une nouvelle instance de Java avec le fichier .jar fourni par le JobTracker, en
appelant l'opération correspondante.

• Une fois la tâche démarrée, il enverra régulièrement au JobTracker ses messages heartbeats. En dehors
d'informer le JobTracker qu'il est toujours fonctionnels, ces messages indiquent également le nombre de
slots disponibles sur le TaskTracker concerné.

• Lorsqu'une sous-tâche est terminée, le TaskTracker envoie un message au JobTracker pour l'en
informer, que la tâche se soit bien déroulée ou non (il indique évidemment le résultat au JobTracker).
Architecture Hadoop: Remarques (1/2)

• De manière similaire au NameNode de HDFS, il n'y a qu'un seul

JobTracker et s'il tombe en panne, le cluster tout entier ne peut plus
effectuer de tâches. Là aussi, des résolutions aux problèmes sont ajoutées
dans la version 2 de Hadoop (explication dans la section suivante).

• Généralement, on place le JobTracker et le NameNode HDFS sur la

même machine (une machine plus puissante que les autres), sans y
placer de TaskTracker/DataNode HDFS pour limiter la charge. Cette
machine particulière au sein du cluster (qui contient les deux « gestionnaires
», de tâches et de fichiers) est communément appelée le noeud maître («
Master Node »). Les autres noeuds (contenant TaskTracker + DataNode)
sont communément appelés noeuds esclaves (« slave node »).
Architecture Hadoop: Remarques (2/2)

• Même si le JobTracker est situé sur une seule machine, le « client » qui
envoie la tâche au JobTracker initialement peut être exécuté sur n'importe
quelle machine du cluster – comme les TaskTracker sont présents sur la
machine, ils indiquent au client comment joindre le JobTracker.

• La même remarque est valable pour l'accès au système de fichiers: les

DataNodes indiquent au client comment accéder au NameNode.

• Enfin, tout changement de configuration Hadoop peut s'effectuer

facilement simplement en changeant la configuration sur la machine où
sont situés les serveurs NameNode et JobTracker: ils répliquent les
changements de configuration sur tout le cluster automatiquement.
Architecture Hadoop: Architecture générale
YARN (MapReduce 2) : Présentation
• YARN (Yet-Another-Resource-Negotiator) est aussi appelé MRv2
(MapReduce 2). Ce n’est pas une refonte mais une évolution du
framework MapReduce.

• YARN répond aux problématiques suivantes du Map Reduce :

– Problème de limite de “Scalability” notamment par une meilleure
séparation de la gestion de l’état du cluster et des ressources.
 ~ 4000 Noeuds, 40 000 Tâches concourantes.

– Problème d’allocation des ressources.

YARN (MapReduce 2) : Architecture (1/7)
Le JobTracker a trop de responsabilités.
• Gérer les ressources du cluster.
• Gérer tous les jobs
JobTracker – Allouer les tâches et les ordonnancer.
– Monitorer l'exécution des tâches.
– Gérer le fail-over.

Re-penser l’architecture du Job Tracker.

• Séparer la gestion des ressources du cluster de la
coordination des jobs.
• Utiliser les noeuds esclaves pour gérer les jobs.

ResourceManager et ApplicationMaster.
RessourceManager • ResourceManager remplace le JobTracker et ne
gère que les ressources du Cluster.
• Une entité ApplicationMaster est allouée par
ApplicationMaster AM AM Application pour gérer les tâches.
• ApplicationMaster est déployée sur les noeuds
esclaves.
YARN (MapReduce 2) : Architecture (2/7)
• Cette nouvelle version contient aussi un autre composant :
Le NodeManager (NM)
– Permet d’exécuter plus de tâches qui ont du sens pour l’Application
Master, pas seulement du Map et du Reduce.
– La taille des ressources est variable (RAM, CPU, network….). Il y aura
plus de valeurs codées en dur qui nécessitent un redémarrage.

RessourceManager

AM AM ApplicationMaster NodeManager NM NM
 YARN (MapReduce 2) : Architecture (3/7)
• Le JobTracker a disparu de l’architecture, ou plus précisément, ses
rôles ont été répartis différemment.

• L’architecture est maintenant organisée autour d’un ResourceManager dont le

périmètre d’action est global au cluster et à des ApplicationMaster locaux dont le
périmètre est celui d’un job ou d’un groupe de jobs.

• En terme de responsabilités, on peut donc dire que :

JobTracker = ResourceManager +ApplicationMaster.

• La différence, de part le découplage, se trouve dans la multiplicité. En effet, Un

ResourceManager gère n ApplicationMaster, lesquels gèrent chacun n jobs.
 YARN (MapReduce 2) : Architecture (4/7)
D’une façon générale, YARN organise
l’exécution d’un job MapReduce dans
un cluster en minimisant le déplacement
des données et l’utilisation de
ressources pour que les performances
soient maximisées.

Les données nécessaires à

l’exécution d’un job ne se trouvent
pas forcément dans le nœud où
l’exécution sera effectuée.
Ainsi, le traitement se fait en priorité où
les données se trouvent.
 YARN (MapReduce 2) : Architecture (5/7)
1. ResourceManager
• Le ResourceManager est le remplaçant du JobTracker du point de vue du client qui soumet des jobs (ou
plutôt des applications en Hadoop 2) à un cluster Hadoop.
• Il n’a maintenant plus que deux tâches bien distinctes à accomplir :
– Scheduler
– ApplicationsManager

a. Scheduler
• Le Scheduler est responsable de l’allocation des ressources des applications tournant sur le cluster.
• Il s’agit uniquement d’ordonnancement et d’allocation de ressources.
• Les ressources allouées aux applications par le Scheduler pour leur permettre de s’exécuter sont appelées des
Containers.
YARN (MapReduce 2) : Architecture (6/7)
 Container
• Un Container désigne un regroupement de mémoire, de cpu, d’espace disque, de
bande passante réseau, …
b. ApplicationsManager
• L’ApplicationsManager accepte les soumissions d’applications.
• Une application n’étant pas gérée par le ResourceManager, la partie
ApplicationsManager ne s’occupe que de négocier le premier Container que le
Scheduler allouera sur un noeud du cluster. La particularité de ce premier
Container est qu’il contient l’ApplicationMaster (diapo suivant).

2. NodeManager
• Les NodeManager sont des agents tournant sur chaque nœud et tenant le
Scheduler au fait de l’évolution des ressources disponibles. Ce dernier peut ainsi
prendre ses décisions d’allocation des Containers en prenant en compte des
demandes de ressources cpu, disque, réseau, mémoire, …
61
 YARN (MapReduce 2) : Architecture (7/7)
3. ApplicationMaster
• L’ApplicationMaster est le composant spécifique à chaque application, il est en charge des jobs qui y
sont associés.
– Lancer et au besoin relancer des jobs
– Négocier les Containers nécessaires auprès du Scheduler
– Superviser l’état et la progression des jobs.
• Un ApplicationMaster gère donc un ou plusieurs jobs tournant sur un framework donné. Dans le cas de
base, c’est donc un ApplicationMaster qui lance un job MapReduce. De ce point de vue, il remplit un
rôle de TaskTracker.

 L’ApplicationsManager est l’autorité qui gère les ApplicationMaster du

cluster. A ce titre, c’est donc via l’ApplicationsManager que l’on peut
– Superviser l’état des ApplicationMaster
– Relancer des ApplicationMaster
 YARN (MapR2): Déroulement de l’exécution
• Le déroulement de l'exécution d'une tâche Hadoop suit les étapes suivantes:

1. Le client (un outil Hadoop console) va soumettre le travail à

effectuer au ResourceManager: une archive java .jar implémentant les opérations Map et Reduce, et
également une classe driver (qu’on peut considérer comme le « main » du programme).

2. Le ResourceManager alloue un container, « Application Master », sur le cluster et y lance la classe « driver »
du programme.

3. Cet « application master » va se lancer et confirmer au ResourceManager qu’il tourne correctement.

4. Pour chacun des fragments des données d’entrée sur lesquelles travailler, l’Application Master va demander
au Resource Manager d’allouer aun container en lui indiquant les données sur lesquelles celui-ci va travailler
et le code à exécuter.
 YARN (MapR2): Déroulement de l’exécution
5. L’Application Master va alors lancer le code en question (une classe Java, générallement map ou reduce)
sur le container alloué. Il communiquera avec la tâche directement (via un protocole potentiellement
propre au programme lancé), sans passer par le ResourceManager.

6. Ces tâches vont régulièrement contacter l’Application Master du programme pour transmettre des
informations de progression, de statut, etc. parallèlement, chacun des NodeManager communique en
permanence avec le ResourceManager pour lui indiquer son statut en terme de ressources (containers
lancés, RAM, CPU), mais sans information spécifique aux tâches exécutées.

7. Pendant l’exécution du programme, le client peut à tout moment contacter le programme en cours
d’exécution; pour ce faire, il communique directement avec l’Application Master du programme en
contactant le container correspondant sans passer par le ResourceManager du cluster.

8. A l’issue de l’exécution du programme, l’Application Master s’arrète; son container est libéré et est à
nouveau disponible pour de futures tâches.
YARN (MapR2) : Lancement d’une Application
dans un Cluster Yarn
YARN (MapR2) : Lancement d’une Application
dans un Cluster Yarn
YARN (MapR2) : Lancement d’une Application
dans un Cluster Yarn
YARN (MapR2) : Lancement d’une Application
dans un Cluster Yarn
YARN (MapR2) : Lancement d’une Application
dans un Cluster Yarn
YARN (MapR2) : Exécution d’un Job MR
YARN (MapR2) : Exécution d’un Job MR
YARN (MapR2) : Exécution d’un Job MR
YARN (MapR2) : Exécution d’un Job MR
YARN (MapR2) : Exécution d’un Job MR
 Hadoop 2: HDFS - Remarques
• De la même façon que l’évolution de MapReduce 2, nous trouvons quelques améliorations de HDFS
dans la 2ème version de Hadoop. Ces améliorations ont été déjà expliqué dans la partie consacrée à HDFS.

1. Le SPOF du Namenode a disparu

• L’ancienne architecture d’Hadoop imposait l’utilisation d’un seul namenode, composant central contenant les métadonnées
du cluster HDFS. Ce namenode était un SPOF (Single Point Of Failure).
• Dans Hadoop 2, on peut mettre deux namenodes en mode actif/attente. Si le Namenode
principal est indisponible, le Namenode secondaire prend sa place.

2. La fédération HDFS
• Dans un cluster HDFS, un namenode correspond à un espace de nommage (namespace). Dans L’ancienne architecture
d’Hadoop, on ne pouvait utiliser qu’un namenode par cluster. La fédération HDFS permet de supporter plusieurs namenodes
et donc plusieurs namespace sur un même cluster. (Exemple : un NameNode pourrait gérer tous les fichiers sous /user, et un
second NameNode peut gérer les fichiers sous /share.)
Hadoop 2: Architecture générale
Sources
• Cours
 Big Data Analytics – Lesson 1: What is Big Data , IBM, Big Data University,
 Intro to Hadoop and MapReduce , Coursera, Udacity
 Hadoop / Big Data – MBDS, Benjamin Renaut (avec quelques modifications).

• Articles
 “Data scientist : The sexiest Job of the 21th Century” T.H. Davenport, DJ. Patil, Harvard Business
Review.
 Bernard Marr, “Big Data: The 5 Vs Everyone Must Know”, LinkedIn
 « Hadoop et le "Big Data », LaTechnologie Hadoop au coeur des projets "Big Data" - Stéphane
Goumard – Tech day Hadoop, Spark - Arrow- Institute.
 Comparison Between Hadoop 2.x vs Hadoop 3.x – Data Flair.

• Livres
 Hadoop: The Definitive Guide, Tom White, O'Reilly Media.

52