INTRODUCTION AU BIG DATA
Instructrice : Dr Abir KHALDI 2021-2022
Dr Abir KHALDI
1
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
2
MapReduce : Présentation
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (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. 3
Dr Abir KHALDI
Mapreduce : Principe
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (cid:1)Lab
(cid:2)L’ancien 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
4
Mapreduce : Programmation Fonctionnelle
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (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)[x0, ..., xn] = [f(x0, ...,f(xn)] map(*4)[2, 3, 6] = [8, 12, 24] 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)[x0, ..., xn] = 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
5
MapReduce : Application sur des paires(clé, valeur)
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (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
6
Publicité
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)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (cid:1)Lab
Dr Abir KHALDI
7
MapReduce :Application sur des paires(clé, valeur)
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (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 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
8
MapReduce :Application sur des paires(clé, valeur)
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (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 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
9
MapReduce :Application sur des paires(clé, valeur)
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (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
10
MapReduce :Application sur des paires(clé, valeur)
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (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
11
MapReduce :Application sur des paires(clé, valeur)
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
Publicité
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (cid:1)Lab
un
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.
de
(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
12
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)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (cid:1)Lab
Dr Abir KHALDI
13
Mapreduce : Fonctionnalités
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (cid:1)Lab
du
fonctions
paradigme
conception
généralisation
(cid:3)La de 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 (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
14
Mapreduce : Architecture
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (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
15
Mapreduce : Architecture
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
Publicité
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (cid:1)Lab
Dr Abir KHALDI
16
Mapreduce : Avantages
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (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 d’erreurs. de la surveillance de tâches ou de la gestion d’erreurs
(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 d’un cluster n’a pas d’impact sur le traitement des données. De fait, les tâches peuvent etre réparties sur n’importe quelle quantité de serveurs.
Dr Abir KHALDI
17
Mapreduce : Avantages
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (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 nœuds.
(cid:2)Le principal avantage de ce framework est sa tolérance aux erreurs. Une tâche est transférée d’un nœud à l’autre, et si le nœud principal remarque qu’un nœud a été silencieux pendant un intervalle de temps plus long que prévu, le nœud principal assigne à nouveau la tâche à un autre nœud. Ceci crée une résilience et facilite le lancement de cette structure logicielle sur des serveurs peu coûteux.
Dr Abir KHALDI
18
Mapreduce : Critiques
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (cid:1)Lab
(cid:2)MapReduce ne permet de résoudre qu’un 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 l’augmentation des performances proposées par la plupart des bases de des performances proposées par la plupart des bases de données les plus communes.
Dr Abir KHALDI
19
Mapreduce : Lab
(cid:2) Voir Lab1 . Hadoop – MapReduce (cid:2) Voir Lab1 Hadoop – MapReduce
Dr Abir KHALDI
20
(cid:1)Présentation (cid:1)Présentation
(cid:1)Principe (cid:1)Principe
(cid:1)Programmation (cid:1)Programmation Fonctionnelle Fonctionnelle
(cid:1)Application sur (cid:1)Application sur (cid:1)Application sur (cid:1)Application sur des paires(clé, des paires(clé, valeur) valeur)
(cid:1)Fonctionnalité (cid:1)Fonctionnalité
(cid:1)Architecture (cid:1)Architecture
(cid:1)Avantages (cid:1)Avantages
(cid:1)Critiques (cid:1)Critiques
(cid:1)Lab (cid:1)Lab
Questions ?
Dr Abir KHALDI
21