MapReduce : tout comprendre sur le calcul parallèle

MapReduce est un patron d'architecture de programmation utilisé pour paralléliser des calculs dans un contexte Big Data. Imaginé et développé par Jeff Dean chez Google, il a été repris dans plusieurs projet, dont le très populaire framework Hadoop qui utilise MapReduce.

Au fil des ans, ce modèle est devenu incontournable pour traiter de très grandes quantités de données. Son modèle, particulièrement robuste, permet d'adapter les calculs à n'importe quelle volumétrie de données, de quelques giga-octets jusqu'à des dizaines de tera-octets de données. En bref, il n'y a pas de limite (si ce n'est le temps de calcul) aux applications de MapReduce.

C'est quoi MapReduce ?

Puisqu'il s'agit d'une architecture de programmation, MapReduce peut être utilisée dans de nombreux langages de programmation : Java, Scala, R, Python, C++, etc.

Il est principalement utilisé avec le framework Hadoop, car ce dernier gère le fonctionnement de clusters. À l'intérieur de celui-ci, on retrouve des noeuds.

• Le nœud principal (main node) qui va administrer l'ensemble des ressources du serveurs, gérer la réussite de chaque job et manager les nœuds de travail.
• Les nœuds de travail (workers nodes) qui vont exécuter les calculs demandées sur des portions de données.

C'est en effet très important, puisque la particularité de MapReduce est de pouvoir traiter des données en parallèle. Lorsque le traitement est effectué, les données en provenance des multiples serveurs du cluster sont récupérés et agrégés pour obtenir un résultat final.

Profitant également de l'écosystème Hadoop, MapReduce utilise le système de fichiers distribués HDFS, ce qui permet à chaque serveur du cluster de lire et écrire des données basés sur des disques. Chaque fichier est donc accessible par n'importe quel noeud du cluster, ce qui permet d'exécuter un job indépendamment des autres.

Ainsi, par son fonctionnement, MapReduce va avoir la capacité de traiter une volumétrie importante, à la fois parce qu'il dispose de plusieurs serveurs dans un cluster, et que chacun de ces serveur utilise un même système de fichiers.

Comment fonctionne MapReduce ?

Comme son nom l'indique, MapReduce est constituée de deux étapes : une première appelée Map, et une seconde appelée Reduce. Ces deux étapes sont importantes, car elles permettent de transposer de nombreux opérations dans un cadre distribué.

Étape Map

L'étape Map va projeter les éléments d’une liste dans une nouvelle liste par l’intermédiaire d’une fonction \(f\) que l'on définit nous-même. Les données en entrée (input) vont être décomposées sous forme de plusieurs blocs de même tailles et envoyés vers différents workers (noeud du cluster qui exécute les calculs).

Chaque donnée des blocs est « mappé » à partir de la fonction \(f\) : son objectif est d'ajouter des informations supplémentaires de sorte à pouvoir créer des groupes de données, bien que celles-ci soient dispersées sur plusieurs serveurs.

Supposons que l'on ait des valeurs v1, v2, v3, v4 et que l'on souhaite regrouper des valeurs entre-elles. Par exemple, on peut supposer que v1, v4 appartiennent à un premier groupe, et v2, v3 à un deuxième groupe. Nous allons alors mapper chaque valeur initiale des blocs vers une paire clé-valeur : la clé indique le groupe auquel la valeur appartient. On obtiendrait alors (k1, v1), (k1, v4) et (k2, v2), (k2, v3).

Le principal avantage de cette représentation est de pouvoir dire que des valeurs appartiennent au même groupe, même si elles se retrouvent dans des blocs différents, et donc sur des serveurs différents.

Étape Reduce

Maintenant que l'on dispose de paires clé-valeur, l'étape Reduce cherche à agréger les valeurs qui possèdent la même clé.

Dans cette étape, nous définissons une stratégie d'agrégation, c'est-à-dire une manière dont nous allons agréger toutes les valeurs pour une même clé. MapReduce va se charger lui-même de déterminer quelles sont les clés identiques et quelles sont les valeurs qui appartiennent au même groupe.

Si l'on reprends les paires précédentes, alors le regroupement des paires donnerait (k1, [v1, v4]) et (k2, [v2, v3]). À partir de là, il est très facile d'agréger chaque liste : on peut faire une somme, un opération mathématique ou tout autre fonctions, libre à nous de la définir.

C'est notamment ce procédé qui permet de créer un lien entre des données situées sur des serveurs différents, alors même que ces derniers sont indépendants. Nous sommes ainsi capable de regrouper des données en utilisant les clés des paires.

Ce qui est crucial dans MapReduce, c'est de choisir les bonnes fonctions Mapper et Reducer à utiliser pour répondre précisément au besoin.

Un exemple de MapReduce

Pour bien comprendre comment fonctionne MapReduce, essayons de dérouler le fonctionnement de l'algorithme sur un exemple de comptage de mots, notamment dans un environnement Hadoop.

On dispose d'un corpus de mots, c'est-à-dire que chaque valeur des données d'entrée est une chaîne de caractères (un mot). Comment allons-nous appliquer MapReduce sur ce cas précis ?

Étape Map (InputSplitter et Mapper)

Premièrement, un InputSplitter va se charger de décomposer le corpus sous forme d'une liste de mots. Ainsi, nous appliquerons le Mapper sur chaque mot.

Pour ce Mapper, nous choisissons la fonction \(w \mapsto (w, 1)\), c'est-à-dire que l'on considère le mot comme étant la clé, et la valeur comme étant le comptage. Cette opération attribue 1 ici puisqu'en appliquant le Mapper, on parcourt une et une seule fois tous les mots du corpus : nous observons donc chaque mot une fois.

Potentiellement, chaque paire clé-valeur se trouve sur un serveur, et il peut très bien y avoir plusieurs fois la paire clé-valeur (chat, 1) sur des serveurs différents.

Étape Reduce (Combiner et Shuffling)

C'est à partir de là que l'on regroupe les paires. Le Combiner a pour rôle de regrouper toutes les valeurs d'une seule et même clé. Ainsi, dans le premier bloc (pointillé noir), il y a eu 5 fois la paire (chat, 1) .

En regroupant les valeurs, le Combiner produit une paire unique (chat, [1, 1, 1, 1, 1]) .

Ensuite, c'est le Shuffling qui va rapatrier chaque paire unique clé-valeur des blocs et agréger toutes les valeurs. C'est à nous de définir cette agrégation : doit-on prendre la somme, le minimum, le maximum ? Puisque l'on souhaite compter le nombre mots, en prenant la somme, on dénombre les valeurs qui appartiennent à cette clé.

Autrement dit, nous allons calculer combien de fois le mot chat est apparu. Au final, nous avons un résultat agrégé, où chaque clé est un mot unique, et chaque valeur son nombre d'occurrences.

Quels sont les avantages de MapReduce ?

MapReduce possède de nombreux avantages, car il s'adapte à des situations différentes.

• Il est adapté pour le fonctionnement par clusters. Par définition, les étapes de Map et Reduce sont effectués sous forme de groupes isolés les uns des autres, ce qui est le cas dans un cluster de serveurs, où chaque serveur est indépendant des autres.
• La volumétrie des données n'impacte pas les transformations appliquées. Contrairement à d'autres systèmes (SQL par exemple) où il faut adapter le calcul à la taille des données, il n'y a pas besoin de changer les calculs. Cette flexibilité permet donc d'écrire des scripts qui pourront s'exécuter quelle que soit la taille des données.
• La vitesse d'exécution est optimisée. En effet, grâce au système de fichiers distribués HDFS, les données sont fragmentées sur les différents serveurs. Les transformations sont décomposées sous forme d'étapes, ce qui permet de traiter en parallèle des briques d'opérations sur chaque serveur du cluster.
• Il s'intègre parfaitement dans l'écosystème Hadoop. De nombreux outils tels que Hive, HBase ou encore Pig utilisent MapReduce pour chaque traitement distribué.

Néanmoins, pour certains cas d'usage, notamment lorsque les données sont hétérogènes, ce processus peut s'avérer particulièrement long à s'exécuter. Aujourd'hui, on utilise majoritairement Apache Spark, qui est à la fois plus rapide en terme d'exécution et plus facile à manipuler grâce à ses API proposées.

Apprendre à utiliser MapReduce

L'architecture MapReduce est très souvent employée par les Data Engineers qui souhaitent paralléliser des calculs. Bien que des API dites haut-niveau permettent d'effectuer des opérations de type SQL sur des données structurées, MapReduce reste un paradigme puissant qui peut s'avérer nécessaire dans certaines situations, notamment en présence de données non structurées.

La formation Data Engineer de Blent propose de nombreux cas d'usage pour maîtriser l'utilisation de MapReduce sous Hadoop dans des contextes variées, que ce soit sur des données non structurées ou pour du Data Mining. MapReduce sert également d'introduction aux modèles d'architecture plus simples d'utilisation.

Ce parcours de formation aborde également de nombreuses notions liées au traitement Big Data d'Hadoop avec l'utilisation de clusters Spark, la diffusion de données en temps réel avec Apache Kafka, l'automatisation de workflows et de pipelines avec Airflow ou encore le déploiement de modèles de Machine Learning.