MapReduce

Ce matériel couvre le paradigme MapReduce, un modèle de programmation distribué destiné au traitement de grandes quantités de données. Il s'adresse aux étudiants et professionnels en informatique, particulièrement ceux intéressés par le Big Data, le calcul distribué et l'architecture Hadoop. Le document présente les principes fondamentaux de MapReduce, des exemples concrets, ainsi que l'évolution architecturale avec Hadoop et YARN.

Introduction à MapReduce

MapReduce est un paradigme de programmation permettant de traiter de très larges volumes de données de manière distribuée. Il repose sur la stratégie algorithmique « diviser pour régner » (divide and conquer), qui consiste à découper un problème complexe en sous-problèmes plus petits, traités en parallèle sur plusieurs machines d'un cluster.

Le modèle MapReduce généralise plusieurs approches existantes en un cadre unique applicable à divers problèmes. Il est notamment popularisé par Google en 2004, bien que ses concepts existaient déjà dans certains langages fonctionnels comme Lisp ou Scheme.

Fonctionnement de MapReduce

MapReduce se compose de deux opérations principales :

• MAP : transforme les données d'entrée en une série de couples (clef, valeur). Cette opération est parallélisable, chaque machine du cluster traitant un fragment distinct des données.
• REDUCE : agrège les valeurs associées à chaque clef distincte produite par l'opération MAP. Chaque machine traite une ou plusieurs clefs uniques et leurs listes de valeurs.

Le traitement MapReduce se déroule en quatre étapes :

1. Split : découpage des données d'entrée en fragments.
2. Map : génération des couples (clef, valeur) pour chaque fragment.
3. Shuffle : regroupement des couples par clef.
4. Reduce : réduction des groupes par clef en une valeur finale.

Cette organisation rend le traitement parallélisable, à l'exception du découpage initial.

Exemple concret : comptage des mots dans un texte

Considérons un texte en français dont on souhaite déterminer les mots les plus fréquents. Les étapes sont :

• Découpage : on divise le texte ligne par ligne, chaque ligne constituant un fragment.
• Prétraitement : suppression de la ponctuation, des accents, et conversion en minuscules.
• Opération MAP : pour chaque mot dans une ligne, générer le couple (mot ; 1).

Par exemple, pour la ligne « celui qui croyait au ciel », on obtient :

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

Après exécution de MAP sur tous les fragments, Hadoop regroupe les couples par clef (shuffle), par exemple :

(celui;1) (celui;1)
(fou;1) (fou;1)
(qui;1) (qui;1) (qui;1) (qui;1)
(croyait;1) (croyait;1)
…

L'opération REDUCE consiste à additionner les valeurs associées à chaque mot :

TOTAL = 0
POUR chaque occurrence dans le groupe :
    TOTAL = TOTAL + 1
RENVOYER TOTAL

Le résultat final indique le nombre d'occurrences par mot, par exemple :

• qui : 4
• celui : 2
• croyait : 2
• fou : 2
• …

Ce modèle, bien que trivial ici, peut s'appliquer à des corpus très volumineux, répartis sur plusieurs machines.

Exemple : statistiques web

On peut appliquer MapReduce pour compter le nombre de visiteurs par page web à partir des fichiers de logs. Ici :

• La clef est l'URL de la page.
• Les opérations MAP et REDUCE sont identiques à l'exemple précédent, comptant les occurrences de chaque URL.

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

Considérons un réseau social avec des millions d'utilisateurs. Pour chaque utilisateur, on connaît la liste de ses amis. On souhaite calculer, pour chaque paire d'utilisateurs, le nombre d'amis en commun.

Les données d'entrée sont sous la forme :

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

Le choix de la clef est la concaténation alphabétique des deux utilisateurs, par exemple « A-B ».

L'opération MAP génère pour chaque utilisateur toutes les paires possibles avec ses amis, associées à la liste complète d'amis :

POUR AMI dans liste_amis:
    SI UTILISATEUR < AMI:
        CLEF = UTILISATEUR + "-" + AMI
    SINON:
        CLEF = AMI + "-" + UTILISATEUR
    GENERER (CLEF; liste_amis)

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

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

Après regroupement (shuffle), chaque clef possède deux listes d'amis, une pour chaque utilisateur :

"A-B" : ["A C D E", "B C D"]
"A-C" : ["A B D E", "B C D"]
…

L'opération REDUCE calcule l'intersection des deux listes :

LISTE_AMIS_COMMUNS = []
SI longueur(VALEURS) != 2:
    RENVOYER ERREUR
SINON:
    POUR AMI dans VALEURS[0]:
        SI AMI dans VALEURS[1]:
            LISTE_AMIS_COMMUNS += AMI
RENVOYER LISTE_AMIS_COMMUNS

Le résultat donne les amis en commun par paire d'utilisateurs :

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

Cette méthode permet d'effectuer un calcul complexe de manière distribuée et efficace.

Architecture Hadoop pour MapReduce

Hadoop est un framework qui implémente MapReduce sur un cluster. 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 TaskTracker.
• TaskTracker : présent sur chaque machine du cluster, il exécute les opérations MAP et REDUCE sur les blocs de données locaux et communique régulièrement avec le JobTracker via des « heartbeats ».

Le JobTracker attribue les tâches aux TaskTracker proches des données pour optimiser les performances. En cas d'échec d'une tâche, il peut la relancer sur un autre TaskTracker ou blacklister un nœud défaillant.

Le JobTracker et le NameNode sont généralement placés sur une machine puissante appelée nœud maître, tandis que les autres machines sont des nœuds esclaves.

Évolution avec YARN (MapReduce 2)

YARN (Yet-Another-Resource-Negotiator) est une évolution majeure de MapReduce, visant à améliorer la scalabilité et la gestion des ressources. Il décompose les responsabilités du JobTracker en plusieurs composants :

• ResourceManager : gère les ressources globales du cluster et l'allocation des conteneurs (containers).
• ApplicationMaster : gère l'exécution des jobs spécifiques, négocie les ressources auprès du ResourceManager, supervise l'état des tâches.
• NodeManager : agent sur chaque nœud, il exécute les tâches dans les conteneurs et informe le ResourceManager de l'état des ressources.

Cette architecture permet de gérer plusieurs applications simultanément, avec une meilleure répartition des responsabilités et une meilleure tolérance aux pannes.

Déroulement d'une tâche MapReduce sous YARN

1. Le client soumet un job (archive .jar Java) au ResourceManager.
2. Le ResourceManager alloue un container pour l'ApplicationMaster du job.
3. L'ApplicationMaster démarre et confirme son démarrage au ResourceManager.
4. Pour chaque fragment de données, l'ApplicationMaster demande au ResourceManager d'allouer un container pour exécuter la tâche MAP ou REDUCE.
5. L'ApplicationMaster lance le code sur les containers alloués et supervise leur exécution.
6. Les NodeManagers communiquent leur état au ResourceManager, tandis que les tâches rapportent leur progression à l'ApplicationMaster.
7. Le client peut interagir directement avec l'ApplicationMaster pour obtenir des informations sur l'avancement.
8. À la fin, l'ApplicationMaster libère les containers et s'arrête.

Glossaire des termes clés

• MapReduce : Paradigme de programmation distribué basé sur deux opérations principales, MAP et REDUCE, pour traiter de grandes quantités de données.
• MAP : Opération qui transforme les données d'entrée en couples (clef, valeur) parallélisable sur plusieurs machines.
• REDUCE : Opération 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 après l'opération MAP.
• JobTracker : Composant Hadoop chargé de gérer la répartition des tâches dans la version classique de MapReduce.
• TaskTracker : Composant Hadoop présent sur chaque machine, exécutant les tâches MAP et REDUCE.
• ResourceManager : Composant YARN responsable de la gestion globale des ressources du cluster.
• ApplicationMaster : Composant YARN gérant l'exécution d'un job spécifique.
• NodeManager : Agent YARN sur chaque nœud, responsable de l'exécution des tâches et du reporting des ressources.
• Container : Ensemble de ressources (CPU, mémoire, disque, réseau) allouées pour exécuter une tâche.
• NameNode : Composant HDFS qui gère les métadonnées du système de fichiers distribué.
• HDFS : Hadoop Distributed File System, système de fichiers distribué utilisé par Hadoop.

Points clés à retenir

• MapReduce permet de traiter efficacement de très grandes quantités de données en les divisant en sous-tâches parallélisables.
• Les opérations MAP et REDUCE sont les deux seules à programmer, Hadoop gérant la distribution, le regroupement et la parallélisation.
• Hadoop utilise une architecture maître-esclave avec JobTracker et TaskTracker dans sa version classique.
• YARN améliore Hadoop en séparant la gestion des ressources (ResourceManager) de la gestion des jobs (ApplicationMaster), augmentant la scalabilité.
• Les exemples concrets (comptage de mots, statistiques web, calcul d'amis en commun) illustrent la puissance et la simplicité du modèle MapReduce.
• La tolérance aux pannes est assurée par la redondance des tâches et la surveillance via des messages heartbeat.
• Le découpage des données et le choix des clefs sont essentiels pour la parallélisation et l'efficacité du traitement.