Big Data : Mapreduce

IDSCC 5 ENSAO
 Introduction
MapReduce est un paradigme de programmation qui permet une flexibilité massive à travers des
centaines ou des milliers de serveurs dans un environnement distribué. Le terme MapReduce
trouve son origine dans la programmation fonctionnelle et a été introduit par Google dans un article
intitulé
« MapReduce : Simplified Data Processing on Large Clusters ».

2
Introduction
Une vue simple du processus MapReduce est illustrée à la Figure suivante. Tout simplement,
MapReduce concerne l'évolutivité (scalability). En utilisant le paradigme MapReduce, il est
nécessaire d’écrire deux fonctions :
map() : Filtre et agrège les données
reduce() : Réduit, regroupe et résume par des clés générées par map()

3
Introduction
Figure 1 : le processus d’un
programme Mapreduce

4
Les fonctions map() et reduce ()
La fonction map () ou mappeur
Le nœud maître (masternode) prend l'entrée, la partitionne en morceaux de données, et les
distribue aux nœuds ouvriers (esclaves ou datanodes). Les datanodes appliquent la même
transformation à chaque bloc de données, cette transformation s’appelle la fonction map(), puis
ils transmettent les résultats au masternode. Dans MapReduce, le programmeur définit un
mappeur avec les éléments suivants :

5
Les fonctions map() et reduce ()
La fonction reduce() ou reducer
Le masternode regroupe les résultats reçus en fonction des paires clé-valeur uniques ; puis,
par une autre redistribution aux ouvriers/esclaves (datanodes), ces valeurs sont combinées via un
autre type de fonction de transformation, il s’agit de la fonction reduce(). Dans MapReduce, le
programmeur définit un reducer avec les éléments suivants:

6
 Remarques

❑ Lors de la rédaction des fonctions map() et reduce(), il faut prendre en compte l’évolutivité. L’évolutivité
(scalability) est donc le cœur de MapReduce. Si la solution n'évolue pas, on ne pourra pas l'appeler une
solution MapReduce.
❑MapReduce concerne principalement la mise à l'échelle horizontale. Par exemple, si Le séquençage de
l'ADN prend 60 heures avec 3 serveurs, si on passe à 50 serveurs similaires, on pourrait accomplir le
même séquençage d'ADN en moins de 2 heures.

7
Remarques
❑Le concept de base de mapReduce consiste à mapper votre ensemble de données d'entrée
dans une collection de paires clé-valeur (key/value pars), puis en réduisant tout les paires avec
la même clé. Bien que le concept global est simple, il est en fait assez expressif et puissant
lorsque vous considérer que :
◦ Presque toutes les données peuvent être mappées dans des paires clé-valeur.
◦ Vos clés et valeurs peuvent être de tout type : Strings, Integers, FASTQ (pour DNA séquençage), types
personnalisés définis par l'utilisateur et, bien sûr.

8
L’évolutivité et la propriérté shared-
nothing
La propriété : « non partagée » (ou shared-nothing) signifie que tous les mappeurs peuvent
travailler indépendamment, et lorsque les mappeurs terminent leurs tâches, les réducteurs
commencent à fonctionner de manière indépendante (aucune donnée ou région critique n'est
partagée entre les mappeurs ou les réducteurs.
Ce paradigme sans partage nous permet de rédiger des fonctions map() et reduce() qui
fonctionnent facilement et qui améliore le parallélisme efficacement et sans effort,

9
Une analogie simple pour comprendre
mapreduce
Considérons le problème de compter le nombre de livres dans une bibliothèque de 1 000 étagères
et rapporter le résultat final au bibliothécaire. Voici deux solutions MapReduce possibles :
Solution #1 (en utilisant map() et reduce()):
◦ — map() : embaucher 1 000 employés ; chaque ouvrier compte une étagère.
◦ — reduce() : tous les travailleurs se réunissent et additionnent leurs comptes individuels (pour rapporter
les résultats au bibliothécaire).

10
Une analogie simple pour comprendre
mapreduce
Solution n°2 (en utilisant map(), combiner() et reduce()) :
◦ — map() : Embaucher 1 110 employés (1 000 employés, 100 managers, 10 superviseurs— chaque
superviseur gère 10 managers, et chaque manager gère 10 travailleurs); chaque travailleur compte une
étagère et rapporte son compte à son responsable.
◦ — combiner() : tous les 10 managers additionnent leurs comptes individuels et rapportent les total à un
superviseur.
◦ — reduce() : Tous les superviseurs se réunissent et additionnent leurs décomptes individuels (par
rapporter les résultats au bibliothécaire).

11
Quand est ce qu’on utilise mapreduce ?
MapReduce est-il utilisable pour touts les problème de big data ? La réponse simple est non.
Voici d'autres scénarios où MapReduce ne doit pas être utilisé :
◦ Si le calcul d'une valeur dépend de valeurs précédemment calculées.
◦ Si l'ensemble de données est suffisamment petit pour être calculé sur une seule machine
◦ Si toutes vos données d'entrée tiennent dans la mémoire

12
Les mythes autour mapreduce
MapReduce est une technologie révolutionnaire pour l'informatique distribuée, mais il faut
éclaircir les points suivants :

❑ MapReduce n'est pas un langage de programmation, mais plutôt un framework pour développer des
applications distribuées en utilisant Java, R ou Python.

❑ Le système de fichiers distribué de MapReduce ne remplace pas une base de données(comme MySQL
ou Oracle). Typiquement, l'entrée de MapReduce sont des fichiers en texte brut (un enregistrement
d'entrée de mappeur peut comporter une ou plusieurs lignes).

13
Les mythes autour mapreduce

❑Le framework MapReduce est conçu principalement pour le traitement en batch, donc on ne devrait pas
s'attendre à obtenir les résultats en moins de deux secondes; cependant, avec une bonne utilisation de
clusters, on peut obtenir une réponse en temps quasi réel.

❑MapReduce n'est pas une solution à tous les problèmes logiciels.

14
En résumé, MapReduce offre les avantages suivants :
❑ Modèle de programmation + infrastructure
❑ La possibilité d'écrire des programmes qui s'exécutent sur des centaines/milliers de nœuds, d’où
la parallélisassions et la distribution automatiques
❑ Tolérance aux pannes (si un serveur meurt, le travail sera terminé par la planification des
programmes/tâches, la vérification de l'état et la surveillance.

15
 Les étapes d’un Job Mapreduce
En général, il y a deux phases pour l'exécution d'une tâche MR, phase de mappage et phase de réduction.
La phase de mappage : exécute un ensemble de tâches (mappers) pour lire les données à partir de disques
sous forme de paires clé-valeur et produisent un nombre de paires clé-valeur intermédiaires en fonction des
mappers définie par l'utilisateur.
La phase de réduction : exécute un ensemble de tâches de réduction (redcuers), qui collectent la sortie de
toutes les tâches de mappage, les fusionne, les tris en se basant sur la clé, la liste des groupes de valeurs qui
appartiennent à la même clé et produit la sortie finale basée sur la fonction de réduction définie par l'utilisateur.

16
 Exemple 1 (wordcount): nous allons expliquer en détail ce que fait un programme mapreduce
pour compter les mots dans un document, considérons le texte suivant

IS 1 𝑲𝟏 , 𝑽𝟏 =(0, I wish to wish )

I wish to wish I wish to wish 𝑲𝟐 , 𝑽𝟐 =(14, the wish you )
the wish you the wish you 𝑲𝟑 , 𝑽𝟑 =(26, wish to )
wish to wish to Création des clés
wish, but if valeurs à l’aide
2 bloc
you wish the de
wish the wish, but if IS 2 𝑲𝟏 , 𝑽𝟏 =(0, wish, but if) InputFileFormat
you wish the 𝑲𝟐 , 𝑽𝟐 =(12, you wish the)
wish the 𝑲𝟑 , 𝑽𝟑 =(24, wish the )

17
Exemple 2 : produit d’une matrice 𝑀 de dimension 𝑛 × 𝑛 et un vecteur 𝑉 de dimension 𝑛.
◦ Cas 1 : 𝑉 peut être traité en mémoire du nœud
◦ Cas 2 : 𝑉 ne peut pas être traité en mémoire du nœud.

18
 Les étapes d’un Job Mapreduce
1. La phase de mappage
HDFS divise physiquement le fichier d'entrée soumis en blocs de taille égale et les stockent dans différents DN
en fonction de la connaissance du rack (Rack Awarness). Les blocs de données requis sont mis en mémoire
pour l'exécution de la phase de mappage.
La phase de mappage commence à partir de FileInputFormat et se termine lorsque toutes les tâches mappage
sont terminées. Le nœud de mappage exécute une séquence de: Input Split, Record Reader, Mapper,
Partitioner et Combiner.

19
 Les étapes d’un Job Mapreduce
Étape 1: FileInputFormat et Input Split (IS)
◦ Format d'entrée de fichier (file input format)

Le format d'entrée du fichier est responsable de la formation de l’IS et de la préparation des

enregistrements à partir du contenu des blocs. Chaque format d'entrée de fichier définit ce qui doit être
le type de données pour la clé et la valeur.

20
 Les étapes d’un Job Mapreduce
paires clé-valeur
Dans l'environnement de programmation MR, aucune donnée ne peut être autonome. Chaque donnée est
associé à une clé. Une paire clé-valeur est appelée un enregistrement. IS et l’enregistrements sont des
entités logiques utilisées au moment de l'exécution du travail. Ils n'affectent pas les blocs. Chaque étape de la
séquence d'exécution MR prend un paire valeur-clé comme entrée et un autre clé valeur comme sorties.

21
 Les étapes d’un Job Mapreduce
Tableau qui nous explique quelques différentes classes de InputFormat et la clé/valeurs qui sont passé au
mapper dans chaque cas :
InputFormat Description
TextInputFormat Chaque ligne des fichiers texte est un enregistrement. La clé est l'octet offset de la
ligne, et la valeur est le contenu de la ligne.
clé: LongWritable
valeur : Texte
KeyValueTextInputFormat Chaque ligne des fichiers textes est un enregistrement. Le premier caractère
séparateur divise chaque ligne. Ce qui est avant le séparateur est la clé, et tout ce qui
suit est la valeur. Le séparateur est défini par [Link]. line, et la
valeur par défaut est le caractère de tabulation (\t).
clé : Texte
valeur : Texte

22
Les étapes d’un Job Mapreduce
InputFormat Description
SequenceFileInputFormat<K,V> Un InputFormat pour la lecture dans les fichiers de séquence. Clé et valeur sont
définis par l'utilisateur. Le fichier de séquence est un format de fichier binaire
compressé spécifique à Hadoop. Il est optimisé pour transmettre des
données entre la sortie d'un job MapReduce à l'entrée d'un autre job
MapReduce.
clé : K (définie par l'utilisateur)valeur : V (définie par l'utilisateur)
NLineInputFormat Identique à TextInputFormat, mais chaque division est garantie avoir
exactement N lignes. La propriété [Link], qui est
par défaut à un, définit N.
clé: LongWritable
valeur : Texte

23
Les étapes d’un Job Mapreduce
Exemple 1 (TextInputFormat) : calcul de la température maximale et de l’année de cette
température :

24
 Les étapes d’un Job Mapreduce

Key (clé) Value (valeurs)

25
Les étapes d’un Job Mapreduce
Exemple 2 (KeyValueTextInputFormat) :prenons les données suivantes:

La première clé sera : 17:16:18 et la première valeurs sera : f

“[Link] [Link]”

26
 Les étapes d’un Job Mapreduce
◦ Input split

Un IS représente un ensemble de blocs à traiter par une seule tâche de mappage. Le concept du bloc de
données est un concept HDFS alors que IS est un concept MR. IS est le groupement logique d'un ou plusieurs
blocs physiques. IS fera référence à au moins un bloc. Par défaut, La taille IS est la même que la taille de bloc
par défaut (128 Mo).
Comme le montre la figure suivante, le fichier d'entrée de 512 Mo est divisé 4 blocs physiques de 128 Mo et
stockées dans différents DN. Si la taille IS est de 256 Mo, alors chaque IS regroupe logiquement deux blocs
physiques. Chaque IS est traité par une tâche map unique. Veuillez noter que IS ne contient pas de copie des
blocs physiques. Il contient juste leurs emplacement sous forme de métadonnées.

27
 Les étapes d’un Job Mapreduce
Exemple d’illustration de la différence entre
les blocs et IS

28
 Les étapes d’un Job Mapreduce
Une tâche de mappage ne peut traiter qu'un seul IS à la fois. Le nombre de mappers d‘une tâche est déterminé
par le nombre d'IS. Le nombre de tâches map lancé est égal au nombre d'IS formés. D'autre part, ce nombre peut
être personnalisé en définissant la taille du bloc.
Figure : calcul des tâches de mappage En fonction du taille de IS

29
30
 Les étapes d’un Job Mapreduce
Quelle est la taille IS ?
Par défaut, la taille du bloc elle-même est la taille IS
Remarques
❑ Que faire si un IS contient plusieurs blocs de données ? Si un IS contient plus d'un bloc de données,
la localité des données est sacrifiée
❑ Considérons un IS composé de deux blocs :
Bloc 1 : aa bb cc dd ee ff gg hh ii jj
Bloc 2 : ww ee yy uu oo ii pp kk ll

31
 Les étapes d’un Job Mapreduce
Remarque :
La tâche de mappage lit les données bloc 1 de aa à jj et ne sait pas comment et d'où lire le bloc 2. C'est-à-dire que
la tâche de mappage ne sait pas comment traiter les blocs différents car ils sont physiquement séparés.
C’est pour cela qu’on a besoin des IS, car ils considèrent bloc 1et bloc 2 comme étant un seul bloc logique
en formant un enregistrement basé sur le l’input file format du fichier.

32
 Les étapes d’un Job Mapreduce
IS prépare des paires clé:valeur (enregistrements) à partir du contenu des blocs en fonction du format d'entrée
du fichier. Que ce passe t il quand un enregistrement s'étend sur la limite du bloc, comme le montre la figure ci-
dessous?
Exemple 1

33
Exemple 2 :
Supposons que nous avons un fichier de 400 Mo, et FileInputFormat a crée 4 enregistrements :

34
Mais dans HDFS nous avons le fichier sous la forme suivantes :

35
Et puisque l’IS doit avoir des enregistrements complets voici le résultat :

36
 Les étapes d’un Job Mapreduce
Remarque
HDFS ne sait pas si un enregistrement se trouve à l'intérieur du bloc ou s'étend jusqu'au bloc suivant.
IS dispose de l’information où commence le premier enregistrement d'un bloc et où le dernier
enregistrement se termine. Si le dernier enregistrement d'un bloc est incomplet, IS inclut les
informations d'emplacement du bloc suivant et le décalage d'octet du données nécessaires pour
compléter le dossier.

37
 Les étapes d’un Job Mapreduce
Étape 2 : Lecteur d'enregistrements (Record Reader)
Les pairs clé /valeur sont déclarés avec un type de données spécifique à chaque option de l’inputfileformat.
La tâche de mappage ne sait pas comment lire ces enregistrements depuis IS.
Par conséquent, RR est utilisé pour lire les paires <clé, valeur> de IS et convertit ces enregistrements
vers les types de données Hadoop, puis alimente la fonction map.
Exemple : pour TextInputFormat, IS forme le décalage d'octet comme clé et la ligne entière comme valeur.
RR convertira la clé (octet offset) à LongWritable et valeur (ligne entière) à Text.

38
Les étapes d’un Job Mapreduce
Types de données Hadoop

39
 Les étapes d’un Job Mapreduce
Exemple : les données suivantes sont par défaut convertit en clé valeurs :

Key (clé) Value (valeurs)

LongWritable Text

40
 Les étapes d’un Job Mapreduce
Étape 3 : la fonction map
Le mappeur ou la tâche de map est une fonction définie par l'utilisateur. RR alimente la fonction map
par les paires clé/valeur, et la sortie de la tâche de mappage est sous formes des paires clé-valeur
intermédiaires.
Le type de données pour la clé et la valeur de sortie de la fonction map peut être personnalisé. Lorsqu'une
fonction prend une entrée et produit une sortie, elle est appelée tâche.
La phase de map se termine une fois toutes les tâches de mappage ont terminé. La latence de chaque
tâche de map peut varier en raison d'autres activités simultanées dans le système.

41
 Les étapes d’un Job Mapreduce
Étape 4 : Partitionneur (équilibrage de l'entrée de la tâche de réduction )
Dans le cas ou on a plusieurs réducteurs lancés, le partitioner décide à laquelle des tâches de réduction
un enregistrement de sortie map doit aller. Le partitioner est une fonction qui fait une balance de la taille
d'entrée des tâches de toutes les mappeurs. Le partitioner n'a de sens que lorsque nous lançons plus qu'une
tâche de réduction. Partitionerr divise la sortie d'une tâche map en plusieurs partitions. Une partition est
une partie de sortie de map qui va à un réducteur particulier.
Le nombre de partitions est égal au nombre de tâches de réduction. L'objectif du partitionnement est
d’amener la même clé de différentes tâches map dans un seul réducteur.

42
 Les étapes d’un Job Mapreduce
Étape 5 : Combiner (optimisation des E/S réseau et disque)
La tâche de combinaison minimise le trafic réseau, le transfert d'E/S de disque et le nombre des
enregistrements traités par la tâche de réduction. Si la tâche de map génère une sortie énorme, cela conduit
à plus de trafic sur le réseau local pour les transférer afin de réduire la tâche.
Deuxièmement, jusqu'à ce que la sortie map soit transférée sur le réseau, elle est stockée dans un tampon en
mémoire (memory buffer).

43
 Les étapes d’un Job Mapreduce
La fonction de combinaison peut être définie par l'utilisateur ou peut être la même que le réducteur.
Cependant, il existent des applications qui ne peuvent pas utiliser la tâche de réduction en tant que
combineurs.
Une application qui satisfait la propriété d’associativité et commutativité peut utiliser le réducteur en tant
que « combiner ». Exemple : somme, max, min.
Commutatif : a + b = b + a
Associatif : a + (b + c) = (a + b) + c

44
 Les étapes d’un Job Mapreduce
Exemple
La fonction Max satisfait :
max (max(a,b), max(c,d,e)) == max(a,b,c,d,e)
La fonction moyenne ne satisfait pas :
moyenne(moyenne(a,b), moyenne(c,d,e)) != moyenne(a,b,c,d,e)
Pour la fonction moyenne, la propriété d’associativité ne tient pas. Ainsi, le réducteur ne peut pas être utilisé
comme fonction de combinaison pour un travail MR pour trouver la moyenne.

45
 Les étapes d’un Job Mapreduce
2. La phase de réduction
La phase de réduction comprend également une séquence d'étapes à effectuer après que la phase de mappage est
terminée. Les étapes sont : mélanger , fusionner, trier, grouper, réduire, OutputFileFormat et Record Writer.
Remarque
Veuillez noter que mélanger, fusionner, trier et regrouper sont des opérations logiques, et elles ne modifient pas la
sortie d'origine des mappeurs.
La phase de réduction commence lorsqu’un pourcentage ([Link])
des tâches de mappage est complété.
Cependant la tâche de réduction ne commence qu’après la fin de toutes la tâches de mappage.

46
 Les étapes d’un Job Mapreduce
Étape 1 : Mélanger (Shuffle)
Shuffle est le processus par lequel la sortie partitionnée du mappeur/combinateur est transférée sur le
réseau vers un ou plusieurs NM où la tâche de réduction sera exécutée. Chaque nœud réducteur
reçoit une ou plusieurs partitions de toutes les tâches de map. Si la tâche de réduction sera exécutée dans
le même nœud où la tâche de mappage est terminée, shuffle n'a pas de rôle.
Étape 2 : Fusionner et trier
Les partitions de sortie de mappage respectives sont copiées dans le Java Virtual Machine (JVM) du
réducteur. Si la mémoire n'est pas suffisante, ils sont déversés sur le disque local.
Dès que les partitions de toutes les tâches de mappage sont arrivées ou nœuds du réduction, les
partitions doivent être fusionnés en un seul fichier pour un traitement ultérieur.

47
 Les étapes d’un Job Mapreduce
Étape 3 : Grouper
L’ensemble de valeurs appartenant à la même clé est regroupé pour éliminer la redondance des clés. Le
nombre de fois que la fonction de réduction a été exécutée est égal au nombre des paires clé:liste(valeurs) après le
regroupement.
Étape 4 : La tâche de réduction (reduce)
La fonction de réduction traite une liste de valeurs pour chaque clé et produit zéro ou plus d'enregistrements de
sortie. Le nombre de fois que la fonction de réduction est exécutée est égal au nombre d'enregistrements (clé :
liste de valeurs) après regroupement.
La fonction map est principalement utilisée pour le pré-traitement des enregistrements. Cependant, l'algorithme
de base est implémenté dans la fonction de réduction. Opérations d'agrégation et de jointure sont exécutés ici.
La sortie du mappage est supprimée après l'achèvement réussi de tous réducteurs.

48
 Les étapes d’un Job Mapreduce
Exemple du code du wordcount sous
Mrjob :
 Les étapes d’un Job Mapreduce
Remarques
❑ Le RM décide dans quel nœud les tâches de réduction doivent être exécutées. Ce pourrait être le même
nœud où les tâches de mappage ont été exécutées ou un autre nœud dans le même rack ou un nœud dans un
autre rack. Cela dépend de la disponibilité des créneaux et de la charge du réseau local.
❑ Les tâches de réduction n'ont pas l’avantage de la localité des données, contrairement aux tâches de
mappage, car il doivent recevoir des partitions de divers mappeurs s'exécutant dans différents nœuds.
❑ La sortie de la tâche de réduction est généralement stockée dans HDFS par défaut avec réplication
contrairement à la sortie de map stockée en mémoire ou déversée (spilled) dans le système local des
fichiers.
❑La première copie est stockée localement où la tâche de réduction est en cours d'exécution, la
deuxième copie est stockée dans n'importe quel nœud du même rack, et la troisième copie est stockée dans
n'importe quel nœud d'un autre rack du cluster.

50
 Les étapes d’un Job Mapreduce
Étape 10 : graveur d'enregistrements (Record Writer)
La fonction de réduction alimente la clé de sortie et la valeur de sortie à RW, qui les stocke sur HDFS
avec séparation de tabulation par défaut (basée sur TextOutputFormat).
Chaque réducteur écrit un fichier de sortie sur HDFS en respectant le facteur de réplication.
RW ouvre un fichier de sortie et écrit les enregistrements de sortie réduits.

51
 Les étapes d’un Job Mapreduce

Figure illustrant en détail les

différentes étapes d’une tâche
Mapreduce.

52
Quelques application du mapreduce :
Opérations de l’algèbre relationnelle

Un bon point de départ pour voir les applications de Mapreduce est de considérer les opérations sur
les relations. Une relation est un tableau avec des en-têtes de colonnes appelés attributs. Les lignes de la
relation sont appelées tuples. L'ensemble des attributs d'une relation est appelé son schéma. On écrit
souvent une expression comme R(A1, A2, . . . , An) pour dire que le nom de la relation est R et ses
attributs sont A1, A2, . . . , An.

53
 Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
Exemple
Dans la figure suivante, on voit une partie de la relation : Liens qui
décrit la structure du Web. Il y a deux attributs: De et À (From, to).
Une ligne, de la relation est un paire d'URL, de sorte qu'il y ait au moins
un lien du premier URL au deuxième. Par exemple, la première ligne de
la figure est le paire (url1, url2) qui dit que la page Web url1 a un lien
vers la page url2. Alors que nous n'ont montré que quatre tuples, la vraie
relation du Web, ou la partie de celui-ci qui serait stocké par un moteur
de recherche typique, a des milliards de tuples.

54
Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
Il existe plusieurs opérations standard sur les relations, souvent appelées algèbre relationnelle, qui
sont utilisées pour implémenter des requêtes. Les requêtes elles-mêmes sont généralement écrites
en SQL. Les opérations d'algèbre relationnelle dont nous allons parler sont :
La Sélection : il s’agit d’appliquer une condition C à chaque tuple de la relation et produire en
sortie uniquement les tuples qui satisfont la condition C. Le résultat de cette sélection est
noté 𝜎𝐶 (𝑅)

55
Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
La Projection : Pour un sous-ensemble S des attributs de la relation, produire de chaque tuple
uniquement les composants pour les attributs dans S. Le résultat de cette projection est noté
𝜋𝑆 (𝑅).
Union, intersection et différence : ces opérations ensemblistes bien connues s'appliquent aux
ensembles de tuples dans deux relations qui ont le même schéma (mêmes attributs).

56
 Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
Jointure naturelle : étant donné deux relations, la jointure naturelle fait la comparaison de chaque paire de tuples des
deux relations. Si les tuples ont les mêmes éléments sur tous les attributs communs aux deux relations, on
produit un tuple contenant les attributs des deux relations. Si les tuples les ne sont pas identiques sur les attributs en
commun, alors on ne produit rien à partir de ce paire de tuples. La jointure naturelle des relations R et S est noté:
𝑅 ⋈𝑆.

57
 Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
Regroupement et opération : Étant donné une relation R, on partitionne ses tuples selon leurs
valeurs dans un attributs G, appelé l’attribut de groupement. Ensuite, pour chaque groupe,
on effectue des opérations. Les opérations normalement autorisées sont SUM, COUNT, AVG,
MIN et MAX, avec les significations évidentes. Notez que MIN et MAX exigent que les attributs
agrégés aient un type qui puisse être comparé par exemple, des nombres ou des chaînes de
caractère, tandis que SUM et AVG exigent que le type soit numérique.

58
 Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
On note une opération de regroupement et d'agrégation sur une relation R par 𝛾𝑋 (𝑅), où X est une liste
d'éléments qui sont soit:
❑ Un attribut de regroupement
❑Une expression θ(A), où est l'une des cinq opérations d'agrégation telles que SUM, et A est un attribut ne
faisant pas partie du des attributs de groupement.
Le résultat de cette opération est un tuple pour chaque groupe. Ce tuple a un composant pour chacun des
attributs de regroupement, avec la valeur commune aux tuples de ce groupe, et un composant pour chaque
agrégation, avec la valeur agrégée pour ce groupe.

59
Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
Exemple 1: relation entre les liens web
Essayons de trouver les chemins de longueur deux dans le Web, en utilisant la relation « Liens »
de la Figures suivante. C'est-à-dire que nous voulons trouver les triplets d'URL (𝑢, 𝑣, 𝑤) tel qu'il
existe un lien de 𝑢 vers 𝑣 et un lien de 𝑣 vers 𝑤

60
Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
Exemple 2 : relation des réseaux sociaux
Imaginez qu'un réseau social a une relation :
Amis(utilisateur, ami)
Cette relation a des tuples qui sont des paires (𝑎, 𝑏) telles que 𝑏 est un ami de 𝑎. Le but est
d’extraire des statistiques sur le nombre d'amis d’un certain membre. La première étape serait le
calcul du nombre des amis de chaque utilisateur. Cette opération se fait à l’aide du regroupement
et opération, notamment:

𝛾𝑢𝑡𝑖𝑙𝑖𝑠𝑎𝑡𝑒𝑢𝑟,𝑐𝑜𝑢𝑛𝑡 𝑎𝑚𝑖𝑠 (𝐴𝑚𝑖𝑠)

61
Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
Cette opération regroupe tous les tuples par la valeur de leur premier composant, donc il y a un
groupe pour chaque utilisateur. Ensuite, pour chaque groupe, le décompte du nombre d'amis de
cet utilisateur est effectué. Le résultat sera un tuple pour chaque groupe, et un tuple typique
ressemblerait à (Nabil, 300), si l'utilisateur « Nabil » a 300 amis.

62
Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
1. Algorithmes mapreduce pour l’algèbre relationnelle
1. La sélection

Les sélections n'ont pas vraiment besoin de la puissance de mapreduce. Ils

peuvent être effectuées dans la phase de mapper() seule, bien qu'ils puissent
également être effectués dans la phase reduce() seulement. Voici une
implémentation mapreduce de la sélection 𝜎𝐶 (𝑅).
La fonction Map : pour chaque tuple 𝑡 dans R, on teste s’il satisfait C. Si c'est le
cas, on produit le paire clé-valeur (𝑡, 𝑡). C'est-à-dire que la clé et la valeur sont 𝑡.

63
Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
La fonction Reduce : La fonction reduce est l'identité. Notez que la sortie n'est pas exactement
une relation, car elle contient des paires clé-valeur. Cependant, une relation peut être obtenue en
utilisant uniquement les composantes de valeur (ou uniquement les composants clés) de la sortie.

64
 Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
2. La projection
La projection est effectuée de la même manière que la sélection, car la projection peut entraîner le même tuple
qui va apparaître plusieurs fois.
La fonction Reduce() doit éliminer les répétitions. Nous pouvons calculer 𝜋𝑆 (𝑅). Comme suit.
La fonction Map : Pour chaque tuple t dans R, on construit un tuple t′ en éliminant à partir de t les composants
dont les attributs ne sont pas dans S. La sortie est le pair valeur-clé (𝑡′, 𝑡′).
La fonction de Reduce() : pour chaque clé t′ produite par l'une des tâches de la fonction map(), il y aura un ou
plusieurs paires clé-valeur (t′, t′). La fonction Reduce() donne comme sortie:
(𝑡′, [𝑡′, 𝑡′, . . . , 𝑡′]) dans (𝑡′, 𝑡′), donc il produit exactement une paire (𝑡′, 𝑡′) pour cette clé t′.

65
Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
Remarque (diminuer le workload de Reduce() par un combiner dans la projection)
Notez que l'opération de réduction est une élimination en double. Cette opération est associatif et
commutatif, donc un combiner() associé à chaque tâche Map peut éliminer les répétitions
localement.
Cependant, la phase reduce() est encore nécessaire pour éliminer les tuples identiques provenant
de différents Mapper.

66
 Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
3. Union, Intersection, and Difference by Map-Reduce

L’union : Considérons d'abord l'union de deux relations. Supposons que les relations R et S aient la même
structure . Les tâches de map() vont recevoir comme input des morceaux de R ou de S (peut importe lequel).
Les tâches de map() ne font rien d'autre que transmettre leur entrée en tant que paires clé-valeur pour les
tâches reduce(). Ce dernier élimine les répétitions.
La fonction Map() : Transforme chaque tuple d'entrée t en un paire clé-valeur (t, t).
La fonction Reduce(): Pour chaque clé t il y aura une ou deux valeurs t associée. La fonction va produire
une sortie (t, t) dans les deux cas.

67
Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
L’intresection :
Pour calculer l'intersection, nous pouvons utiliser la même fonction Map. Cependant, la fonction
Reduce ne doit produire un tuple que si les deux relations ont le tuple en commun. Si la clé t a
deux valeurs [𝑡, 𝑡] qui lui sont associées, alors la tâche Redcue pour t devrait produire (t, t).
Cependant, si la valeur associée à la clé t est juste [𝑡], alors l'un de R et S ne contient pas t, donc
rien n’est produit pour l’intersection. On doit produire une valeur qui indique « pas de tuple »,
comme la Valeur SQL NULL.

68
Quelques application du mapreduce :
Opérations de l’algèbre relationnelle
La fonction Map() : Transforme chaque tuple d'entrée t en un paire clé-valeur (t, t).
La fonction Redcue(): Si la clé t a la liste de valeurs [𝑡, 𝑡], alors on on produit (t, t) ie t appartient
à l’intersection. Sinon, produire (t, NULL).
La relation différence et jointure naturelle seront des exercices td à résoudre

69
 Autre modèles de traitement
MapReduce
Systèmes de Workflow
Un système Workflow comporte des tâches, de sorte que le flux de données est acyclique et aucune
tâche ne doit fournir des données avant que son entrée ne soit disponible. Par exemple, la fonction h
prend comme entrée un fichier du système distribué. Chacun des éléments de h de sortie sont passés à au
moins une des fonctions i et j:

70
 Autre modèles de traitement
MapReduce
Par analogie avec les fonctions Map et Reduce, chaque fonction d'un workflow peut être exécuté par de
nombreuses tâches, dont chacune se voit attribuer une partie des données d’entrée. Un contrôleur
principal est chargé de répartir le travail entre les tâches qui implémentent une fonction.

71
 Autre modèles de traitement
MapReduce
Extensions récursives de Mapreduce
De nombreux calculs à grande échelle sont en réalité récursifs. Un exemple important est PageRank. Ce calcul
est, en termes simples, le calcul de la distribution stationnaire d’une chaine de Markov.
Il est calculé sous des systèmes map-reduce par l'application itérée de l’algorithme de multiplication matrice-
vecteur décrit précédemment.
L'itération se poursuit généralement pour un nombre inconnu d'étapes, chaque étape étant un job map-
reduce, jusqu'à ce que les résultats de deux itérations consécutives soient suffisamment proches pour assurer
la convergence.

72
 Autre modèles de traitement
MapReduce
Exemple d’un Job récursif
Supposons que nous ayons un graphe orienté dont les arcs sont représentés par la relation E(X, Y ), signifiant
qu'il y a un arc du nœud X au nœud Y. Nous souhaitons calculer la relation de chemins P(X, Y ), ce qui
signifie qu’il existe un chemin de longueur 1 ou plus du nœud X au nœud Y. Un algorithme récursif simple pour
ce faire :
◦ Commencer par P(X, Y ) = E(X, Y )
◦ Pendant que des changements se produisent dans la relation P, ajoutez à P tous les tuples dans:
𝜋𝑋,𝑌 (𝑃 𝑋, 𝑍 ⋈ 𝑃 𝑍, 𝑌 )

73
 Autre modèles de traitement
MapReduce
Modèles de traitement des graphes
Un graphe contient un ensemble de sommets et d'arcs. Les données sous forme graphique sont divisées et
stockées dans plusieurs nœuds et traitées en parallèle. Les graphes impliquent d'importants dépendances de
calcul et plusieurs itérations.
Il nécessite une synchronisation globale. Un traitement des données sous forme de graphes en utilisant
MapReduce nécessite généralement un Job par itération.
. S'il y a 100 itérations pour traiter l'ensemble du graphe, 100 jobs MapReduce sont exécutés, ce qui entraîne une
latence énorme.

74
Autre modèles de traitement
MapReduce
Par conséquent, il existe des outils spécialisés pour travailler avec des données graphiques
colossales. Exemple : Pregel (2010), Apache Hama (2010), Apache Giraph (2012).

75
 Autre modèles de traitement
MapReduce
DAG (directed acyclic graphs)
Le DAG contient un nombre fini de sommets et d'arcs dirigées qui forment pas de cycle. Chaque arc du
graphe avance. Pour les applications basées sur des graphes, nous devrons écrire plus d'un Job
MapReduce et coordonner leurs exécutions. Ainsi, le modèle MapReduce n'est pas adapté pour les
applications des graphes car cela implique de grandes E/S. Cependant, certains outils fournissent un support
pour les applications basées sur des graphes et donnent une réponse interactive en temps réel

76
Autre modèles de traitement
MapReduce
Différence entre un système Workflow et un DAG

77
 Autre modèles de traitement
MapReduce
Système Pregel pour traitement des graphes
Ce système affiche ses données sous forme graphique. Chaque sommet du graphe correspond
approximativement à une tâche (bien qu'en pratique, de nombreux sommets d'un grand graphe soient
regroupés dans une tâche unique).
Chaque sommet du graphe génère des messages de sortie qui sont destinés à d'autres sommet du
même graphe, et chacun d’eux traite les entrées qu'il reçoit des autres sommets.

78
 Autre modèles de traitement
MapReduce
Exemple
Supposons que nos données soient une collection d'arcs pondérés d'un graphe, et on veut trouver, pour
chaque nœud du graphe, la longueur du plus court chemin vers chacun des autres nœuds.
Initialement, chaque nœud de graphe stocke l'ensemble des paires (b, w) telles qu'il existe un arc de a à b de
poids w. Ces informations sont initialement envoyé à tous les autres nœuds, sous forme de triplets (a, b, w).
Lorsque le nœud a reçoit un triple (c, d, w), il recherche sa distance actuelle à c ; c'est-à-dire qu'il trouve la
paire (c, v) stockés localement, s'il y en a un. Il trouve également le paire (d, u) s'il y en a un.
Si w + v < u, alors le paire (d, u) est remplacé par (d, w + v), et s'il y avait pas de paire (d, u), alors le paire (d,
w + v) est stocké au nœud a. Les autres nœuds reçoivent également le message (a, d, w + v).

79
 Autre modèles de traitement
MapReduce
Les calculs dans Pregel sont organisés en super-étapes. En une super étape, tout les messages qui ont été reçus
par l'un des sommets du super-étape précédent (ou initialement, s'il s'agit de la première super étape) sont
traités, puis tous les messages générés par ces sommets sont envoyés à leur destination.
En cas de défaillance d'un nœud (contenant un ou plusieurs sommets), il n'y a aucune tentative de
redémarrage des tâches sur ce nœud de calcul. Au lieu de cela, Pregel contrôle l'intégralité de son calcul
après quelques super-étapes. Un point de contrôle consiste à faire une copie de l'état complet de chaque
tâche, afin qu'elle puisse être redémarrée à partir de ce point si nécessaire.
Si un nœud de calcul échoue, l'intégralité de la tâche est redémarrée à partir du plus récent point de contrôle.

80
 Autre modèles de traitement
MapReduce
Ainsi, il est seulement nécessaire que Pregel contrôle son calcul après un certain nombre de super-étapes
telles que la probabilité d'un échec pendant ce nombre de supersteps est faible.

Exemple
Supposons qu’on a le graphe suivant sur deux nœuds :
Un échec est arrivé au super pas 12, le nœuds 𝑁1 est
Tombé en panne. Le dernier pointage a été effectué
Après la fin du super-pas 10.

81