THEME : MapReduce
Fait par : KAZOUNE BOUBA Israël
[email protected]
+237 692-636-908/+237 683-532-517
19A0338P
Sous la coordination de : M. GAZiSSOU
Introduction
A l’heure actuelle, la science vit une révolution qui conduit à nouveau
paradigme selon lequel la science est dans les données, autrement dit la
connaissance émerge du traitement des données.
L’extraction de connaissances à partir de grands volumes de données (en
particulier quand le nombre de données est bien plus grand que la taille
de l’échantillon) , l’apprentissage statistique, l’agrégation de données
hétérogènes, la visualisation et la navigation dans de grands espaces de
données et de connaissances sont autant d’instruments qui permettent
d’observer des phénomènes, de valider des hypothèses, d’élaborer de
Introduction
nouveaux modèles ou de prendre des décisions en situation critique.
Un des enjeux concerne le traitement de grandes quantités de données.
Ce traitement ne peut être réalisé avec les paradigmes classiques de
traitement de données et nécessite l’utilisation de plateformes
distribuées de calcul.
MapReduce est un modèle de programmation pour écrire des
applications capables de traiter le Big Data en parallèle sur plusieurs
nœuds. MapReduce fournit des capacités analytiques pour analyser
d'énormes volumes de données complexes.
Sources de données
Concept du Big Data
Le Big Data est une collection de grands ensembles de données qui ne
peuvent pas être traités à l'aide de techniques informatiques
traditionnelles.
Par exemple, le volume de données que Facebook, Youtube, Twitter
doivent collecter et gérer au quotidien peut relever de la catégorie du
Big Data. Cependant, le Big Data n'est pas seulement une question
d'échelle et de volume, il implique également un ou plusieurs des
aspects suivants : vitesse, variété, volume et complexité donnant
naissance ainsi à ses caractéristiques 3V ou 5V.
Illustration de l’évolution de données
Croissance des volumes de données générées par les appareils
mobiles en France de 2009 à 2013
64% d’augmentation
C’est quoi MapReduce?
MapReduce a été introduit par Google en 2004
▪ MapReduce est un:
▪ Un modèle de programmation
▪ avec un schéma très contraint, qui permet:
▪ parallélisation automatique
▪ de l’équilibrage de charge
▪ des optimisations sur les transferts disques et réseaux.
En gros, MapReduce est un paradigme de programmation parallèle visant à
généraliser les approches existantes pour produire une approche unique
applicable à tous les problèmes.
Intérêt de MapReduce
MapReduce est une application utilisée pour le traitement d'énormes
ensembles de données. Ces jeux de données peuvent être traités en
parallèle. MapReduce peut potentiellement créer de grands ensembles de
données et un grand nombre de nœuds. Ces grands ensembles de données
sont stockés sur HDFS, ce qui facilite l'analyse des données. Il peut
traiter tout type de données telles que structurées, non structurées ou
semi-structurées.
Les systèmes de bases de données relationnelles disposent d'un serveur
centralisé qui aide au stockage et au traitement des données. Il s'agissait
généralement de systèmes centralisés.
Intérêt de MapReduce
MapReduce est une application utilisée pour le traitement d'énormes
ensembles de données. Ces jeux de données peuvent être traités en
parallèle. MapReduce peut potentiellement créer de grands ensembles de
données et un grand nombre de nœuds. Ces grands ensembles de données
sont stockés sur HDFS, ce qui facilite l'analyse des données. Il peut
traiter tout type de données telles que structurées, non structurées ou
semi-structurées.
Les systèmes de bases de données relationnelles disposent d'un serveur
centralisé qui aide au stockage et au traitement des données. Il s'agissait
généralement de systèmes centralisés.
Intérêt de MapReduce
Lorsque plusieurs fichiers apparaissent dans l'image, le traitement est
fastidieux et crée un goulot d'étranglement lors du traitement de plusieurs
fichiers. MapReduce mappe l'ensemble de données et convertit
l'ensemble de données où toutes les données sont divisées en tuples et la
tâche de réduction prendra la sortie de cette étape et combinera ces tuples
de données dans les ensembles plus petits. Il fonctionne en différentes
phases et crée des paires clé-valeur qui peuvent être réparties sur
différents systèmes.
Intérêt de MapReduce
Les systèmes d'entreprise traditionnels disposent normalement d'un
serveur centralisé pour stocker et traiter les données. L'illustration
suivante représente une vue schématique d'un système d'entreprise
traditionnel. Le modèle traditionnel n'est certainement pas adapté pour
traiter d'énormes volumes de données évolutives et ne peut pas être pris
en charge par des serveurs de base de données standard. De plus, le
système centralisé crée trop de goulots d'étranglement lors du traitement
simultané de plusieurs fichiers.
Intérêt de MapReduce
C’est ainsi que Google a pu résoudre ce problème de goulot
d'étranglement en utilisant un algorithme appelé MapReduce.
MapReduce divise une tâche en petites parties et les affecte à plusieurs
ordinateurs. Plus tard, les résultats sont collectés à un endroit et intégrés
pour former l'ensemble de données de résultats.
Principe de fonctionnement de MapReduce
L'algorithme MapReduce contient deux tâches importantes, à savoir Map
et Reduce.
❖Map : la tâche Map prend un ensemble de données et le convertit en un
autre ensemble de données, où les éléments individuels sont
décomposés en tuples pour chaque donnée d’entrée lue;
❖Reduce : la tâche Reduce prend la sortie de Map comme entrée et
combine ces tuples de données (paires clé-valeur) en un ensemble plus
petit de tuples.
Principe de fonctionnement de MapReduce
❖ Phase d''entrée - Ici, nous avons un lecteur d'enregistrements qui
traduit chaque enregistrement dans un fichier d'entrée et envoie les
données analysées au mappeur sous la forme de paires clé-valeur.
❖ Map - Map est une fonction définie par l'utilisateur, qui prend une
série de paires clé-valeur et traite chacune d'elles pour générer zéro ou
plusieurs paires clé-valeur.
❖ Clés intermédiaires - Les paires clé-valeur générées par le mappeur
sont appelées clés intermédiaires.
Principe de fonctionnement de MapReduce
❖ Combinateur : Un combinateur est un type de réducteur local qui
regroupe des données similaires de la phase de carte dans des
ensembles identifiables. Il prend les clés intermédiaires du mappeur
en entrée et applique un code défini par l'utilisateur pour agréger les
valeurs dans une petite portée d'un mappeur. Il ne fait pas partie de
l'algorithme MapReduce principal ; c'est facultatif.
Principe de fonctionnement de MapReduce
❖ Mélanger et trier - La tâche du réducteur commence par l'étape
Mélanger et trier. Il télécharge les paires clé-valeur groupées sur la
machine locale, sur laquelle le réducteur est en cours d'exécution.
Les paires clé-valeur individuelles sont triées par clé dans une liste
de données plus grande. La liste de données regroupe les clés
équivalentes afin que leurs valeurs puissent être itérées facilement
dans la tâche Reducer.
Principe de fonction de MapReduce
❖ Réducteur - Le Réducteur prend en entrée les données paires clé-
valeur groupées et exécute une fonction Réducteur sur chacune
d'entre elles. Ici, les données peuvent être agrégées, filtrées et
combinées de plusieurs façons, et cela nécessite un large éventail de
traitements. Une fois l'exécution terminée, il donne zéro ou plusieurs
paires clé-valeur à l'étape finale.
Principe de fonction de MapReduce
❖ Phase de sortie - Dans la phase de sortie, nous avons un formateur
de sortie qui traduit les paires clé-valeur finales de la fonction
Reducer et les écrit dans un fichier à l'aide d'un enregistreur
d'enregistrement.
Procédure de traitement de données : Les
algorithmes de MapReduce
Pour traiter les données d’une entreprise utilisant MapReduce, les
algorithmes implémentés suivent la logique ci-après :
1. Choisir une manière de découper les données
2. Choisir la clé à utiliser pour le problème à resoudre
3. Ecrie le programme pour l’opération Map
4. Ecrie le programme pour l’opération Reduce
Exercice corrigé
On veut connaitre le nombre d’occurrence de chacun des mots dans
un fichier d’entrée textuel.
Celui qui croyait au ciel
Celui qui n’y croyait pas
❖Découpage : Fou qui fait le délicat
Fou qui songe à ses querelles
❖Celui qui croyait au ciel
❖ Celui qui n’y croyait pas
❖Fou qui fait le délicat
❖Fou qui songe à ses querelles
Exercice corrigé
❖ Opération Map:
❖Celui qui croyait au ciel (celui;1)(qui;1)(croyait:1)(au;1)(ciel;1)
❖ Celui qui n’y croyait pas (celui;1)(qui;1)(ny;1)(croyait:1)(au;1)(ciel;1)
❖Fou qui fait le délicat (fou;1)(qui;1)(fait;1)(le;1)(delicat;1)
❖Fou qui songe à ses querelles
(fou;1)(qui;1)(songe;1)(a;1)(ses;1)(querelles;1)
Exercice corrigé
❖ Opération de Shuffer c’est-à-dire le regroupement des clés
communes
❖fait;1)
❖(celui;1) (celui;1)
❖(le;1)
❖(qui;1) (qui;1) (qui;1) (qui;1)
❖(delicat;1)
❖(croyait:1) (croyait:1)
❖(songe;1)
❖(au;1)
❖(ciel;1)
❖(a;1)
❖(pas;1) ❖(ses;1)
❖(querelles;1)
❖(fou;1)(fou;1)
Exercice corrigé
❖ Opération Reducer :
❖Au : 1
❖ qui : 4
❖Ciel :1
❖Celui :2
❖Ny:1
❖Croyait : 2
❖Pas
❖Fou : 2
❖Fait:1
Les Prototypes des algorithmes MapReduce
Map(String key, String values) :
foreach word w in input_values:
EmitIntermediate( w, "1");
Reduce (String key, Iterator intermediate_values):
int result=0;
foreach v in intermediate_values:
result += ParseInt( v );
Emit( key, String(result));
L’algorithme Mapper
Implémentation de l’algorithme Map en python
L’algorithme Mapper
Dans cet algorithme nous remarquons avoir d’importer la librairie
système dans lequel nous utilisons la librairie syst.stdin qui est la
librairie gérant les entrées standard des données.
La fonction split() en python permet de decouper tout les mots dans
un text ou fichier.
Algorithme Reducer
Prenons un exercice pratique
Soit le contenu du fichier ci-dessous. Nous allons applique les
algorithmes de mappage et de réduction a cet fichier nommé
fichier.txt
Prenons un exercice pratique
Nous avons appliqués l’algorithme de mappage à ce fichier voilà le
résultat.
Prenons un exercice pratique
Nous allons appliqués l’algorithme de Reduction aussi au même
fichier voilà le résultat.
