MapReduce in Big Data

Ce matériel couvre le paradigme mapreduce-6e20911580">MapReduce, un modèle de programmation essentiel pour le traitement distribué de grandes quantités de données. Destiné aux étudiants et professionnels en informatique et Big Data, il présente les concepts fondamentaux, des exemples concrets, ainsi que l’architecture Hadoop et son évolution vers YARN.

Introduction à MapReduce

MapReduce est un paradigme de programmation permettant de traiter efficacement de très grands ensembles de données en les divisant en sous-tâches distribuées sur un cluster de machines. Le modèle s’appuie sur deux opérations principales : MAP et REDUCE.

Exemple simple : une chaîne de magasins souhaite calculer le total des ventes par magasin à partir d’un grand fichier listant les ventes (date, ville, produit, prix). Une méthode traditionnelle consisterait à parcourir séquentiellement les données et à regrouper les ventes par ville, ce qui devient inefficace à très grande échelle (ex. 1 To de données).

MapReduce permet de paralléliser ce traitement en découpant les données et en répartissant les calculs sur plusieurs machines.

Fonctionnement du paradigme MapReduce

MapReduce repose sur quatre étapes :

• Split (découpage) : les données d’entrée sont divisées en fragments.
• Map : chaque fragment est traité pour générer des couples (clef, valeur) pertinents pour le problème.
• Shuffle (regroupement) : les couples sont regroupés par clef commune.
• Reduce : pour chaque clef, les valeurs associées sont agrégées pour produire un résultat final.

Cette organisation permet une exécution distribuée et parallèle, accélérant considérablement le traitement.

Exemple concret : comptage des mots dans un texte

Objectif : déterminer la fréquence d’apparition des mots dans un texte en français.

Données d’entrée : un texte découpé en lignes (fragments).

Prétraitement : suppression de la ponctuation, des accents, passage en minuscules.

Exemple de texte traité :

celui qui croyait au ciel
celui qui ny croyait pas
fou qui fait le delicat
fou qui songe a ses querelles

Opération MAP : pour chaque mot dans une ligne, générer le couple (mot, 1).

POUR MOT dans LIGNE, FAIRE :
  GENERER COUPLE (MOT; 1)

Exemple de couples générés pour la première ligne :

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

Opération SHUFFLE : Hadoop regroupe automatiquement tous les couples par clef, par exemple :

(celui;1) (celui;1)
(fou;1) (fou;1)
(qui;1) (qui;1) (qui;1) (qui;1)
...

Opération REDUCE : pour chaque clef, additionner les valeurs associées :

TOTAL = 0
POUR COUPLE dans GROUPE, FAIRE :
  TOTAL = TOTAL + 1
RENVOYER TOTAL

Résultat final :

• qui : 4
• celui : 2
• croyait : 2
• fou : 2
• au : 1
• ciel : 1
• ny : 1
• pas : 1
• fait : 1
• …

Ce modèle permet d’appliquer le même traitement à des volumes de données très importants, en répartissant la charge sur plusieurs machines.

Autre exemple : statistiques web

Objectif : compter le nombre de visiteurs par page web à partir des fichiers de logs.

Les clefs sont les URLs des pages, et les opérations MAP et REDUCE sont similaires à l’exemple précédent :

• MAP : générer (URL, 1) pour chaque visite.
• REDUCE : additionner les visites par URL.

Exercice avancé : calcul des amis en commun dans un réseau social

Contexte : un réseau social avec des millions d’utilisateurs. Pour chaque utilisateur, on connaît la liste de ses amis.

Objectif : calculer pour chaque paire d’utilisateurs le nombre d’amis communs, afin d’afficher « Vous avez N amis en commun » lors de la visite d’une page utilisateur.

Données d’entrée (exemple) :

A => B, C, D
B => A, C, D, E
C => A, B, D, E
D => A, B, C, E
E => B, C, D

Définition de la clef :

La clef est la concaténation ordonnée alphabétiquement des deux utilisateurs, par exemple « A-B » pour la paire A et B.

Opération MAP :

Pour chaque utilisateur et sa liste d’amis, générer tous les couples possibles (clef; liste d’amis) pour chaque ami, en s’assurant que la clef est toujours triée :

UTILISATEUR = [première 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])

Exemple pour la ligne « A => B, C, D » :

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

Opération SHUFFLE :

Hadoop regroupe les couples par clef, par exemple pour « A-B » :

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

On obtient ainsi deux listes d’amis associées à chaque clef.

Opération REDUCE :

Pour chaque clef, déterminer les amis communs en intersectant les deux listes :

LISTE_AMIS_COMMUNS = []
SI LONGUEUR(VALEURS) != 2 ALORS
  RENVOYER ERREUR
SINON
  POUR AMI DANS VALEURS[0], FAIRE
    SI AMI DANS VALEURS[1], ALORS
      LISTE_AMIS_COMMUNS += AMI
RENVOYER LISTE_AMIS_COMMUNS

Résultat exemple :

• "A-B" : "C, D"
• "A-C" : "B, D"
• "B-C" : "A, D, E"
• …

Ce traitement, exécuté régulièrement en batch, permet d’éviter des requêtes SQL lourdes en temps réel.

Architecture Hadoop pour MapReduce

Hadoop est un framework open source qui implémente MapReduce et un système de fichiers distribué (HDFS). Son architecture repose sur deux types de serveurs :

• JobTracker : serveur unique qui reçoit les tâches à exécuter, connaît la localisation des données via le NameNode HDFS, et répartit les sous-tâches aux TaskTrackers.
• TaskTracker : présent sur chaque machine du cluster, il exécute les tâches MAP et REDUCE sur les fragments de données locaux.

Le JobTracker attribue les tâches aux TaskTrackers en privilégiant la localisation des données pour minimiser les transferts réseau.

Déroulement d’une tâche Hadoop

1. Le client soumet un fichier .jar Java contenant les programmes MAP et REDUCE, les fichiers d’entrée et le répertoire de sortie au JobTracker.
2. Le JobTracker interroge le NameNode pour localiser les blocs de données.
3. Le JobTracker assigne les tâches aux TaskTrackers proches des données.
4. Les TaskTrackers exécutent les opérations MAP/REDUCE et envoient des messages de progression (« heartbeats ») au JobTracker.
5. En cas d’échec, le JobTracker relance les tâches sur d’autres TaskTrackers ou prend des mesures correctives.
6. Une fois toutes les tâches terminées, le JobTracker marque la tâche comme complétée.

Fonctionnement des TaskTrackers

• Chaque TaskTracker dispose d’un nombre configurable de « slots » pour exécuter plusieurs tâches en parallèle.
• Il lance une instance Java pour chaque tâche reçue, exécute le code MAP ou REDUCE, et informe régulièrement le JobTracker de son état.

Limitations et évolutions

Le JobTracker est un point unique de gestion des tâches et peut devenir un goulot d’étranglement (SPOF). Pour pallier cela, Hadoop 2 introduit YARN (Yet Another Resource Negotiator), une évolution majeure.

YARN : évolution de MapReduce (MapReduce 2)

YARN découple la gestion des ressources du cluster de la coordination des tâches, améliorant la scalabilité et la flexibilité.

Architecture YARN

• ResourceManager : remplace le JobTracker, gère uniquement les ressources du cluster (allocation, ordonnancement).
• ApplicationMaster : une instance par application (job), responsable de la gestion des tâches spécifiques, du lancement et du suivi.
• NodeManager : agent sur chaque nœud, exécute les tâches dans des containers et informe le ResourceManager de l’état des ressources.

Fonctionnement

1. Le client soumet un job au ResourceManager avec le fichier .jar et la classe driver.
2. Le ResourceManager alloue un container pour lancer l’ApplicationMaster.
3. L’ApplicationMaster négocie avec le ResourceManager les containers nécessaires pour exécuter les tâches MAP et REDUCE.
4. Les NodeManagers exécutent les tâches dans les containers alloués.
5. Les tâches communiquent directement avec l’ApplicationMaster pour le suivi.
6. Le client peut interagir directement avec l’ApplicationMaster pendant l’exécution.
7. À la fin, l’ApplicationMaster termine et libère ses containers.

Avantages de YARN

• Meilleure scalabilité (gestion de milliers de nœuds et dizaines de milliers de tâches simultanées).
• Gestion fine des ressources (CPU, mémoire, réseau).
• Support d’autres frameworks que MapReduce sur Hadoop.

Glossaire des termes clés

• MapReduce : Modèle de programmation pour le traitement distribué de données volumineuses, basé sur les opérations MAP et REDUCE.
• MAP : Fonction qui transforme les données d’entrée en couples (clef, valeur) et peut être parallélisée.
• REDUCE : Fonction qui agrège les valeurs associées à chaque clef pour produire un résultat final.
• Split : Découpage des données d’entrée en fragments pour traitement parallèle.
• Shuffle : Regroupement des couples (clef, valeur) par clef commune entre MAP et REDUCE.
• JobTracker : Composant Hadoop 1 responsable de la gestion des tâches et de la répartition sur le cluster.
• TaskTracker : Composant Hadoop 1 exécutant les tâches MAP/REDUCE sur chaque nœud.
• ResourceManager : Composant YARN gérant les ressources du cluster.
• ApplicationMaster : Composant YARN gérant l’exécution d’une application (job) spécifique.
• NodeManager : Composant YARN sur chaque nœud, responsable de l’exécution des containers.
• Container : Ensemble de ressources (CPU, mémoire, disque, réseau) allouées pour exécuter une tâche.
• HDFS : Hadoop Distributed File System, système de fichiers distribué utilisé pour stocker les données dans Hadoop.
• SPOF (Single Point Of Failure) : Point unique de défaillance pouvant faire tomber tout le système.

Points clés à retenir

• MapReduce permet de traiter de très grandes quantités de données en divisant le travail en tâches parallèles MAP et REDUCE.
• Le découpage des données (split) et le regroupement (shuffle) sont essentiels pour la parallélisation.
• Hadoop implémente MapReduce avec une architecture maître-esclave (JobTracker/TaskTracker).
• YARN améliore Hadoop en séparant la gestion des ressources (ResourceManager) de la gestion des applications (ApplicationMaster).
• Le modèle MapReduce est applicable à de nombreux problèmes, du comptage de mots à l’analyse de réseaux sociaux.
• La scalabilité et la tolérance aux pannes sont des caractéristiques clés de Hadoop et YARN.