MapReduce

Introduction

« Diviser pour mieux régner. »

Les choix architecturaux d’un cluster Hadoop ont une incidence très profonde. Pour assurer la scalabilité du cluster, gage nécessaire à la gestion des gros volumes de données générées dans le Numérique d’une part et d’autre part gage de son adoption en entreprise, il est indispensable que le mode de partage des ressources au sein du cluster soit le shared-nothing. Le problème avec le shared-nothing est qu’il exige que toutes les requêtes qui arrivent au cluster soient totalement parallèles. Par conséquent, tout problème dont l’exécution des tâches ne peut pas être totalement parallélisée ne peut pas utiliser un cluster Hadoop. Google s’est bien rendu compte de cela, c’est pourquoi il a qualifié le MapReduce, de modèle permettant de gérer les problèmes qui sont « embarrasingly parallel ». Contrairement à ce qu’on pourrait croire, « embarrasingly parallel » ne veut pas dire « embarrassant à paralléliser », mais plutôt « parallélisable à l’excès ». Cette expression a le même sens que « embarras de richesses » et ne signifie pas que le MapReduce...

MapReduce : un nouveau paradigme

Le MapReduce est d’abord et avant tout un modèle algorithmique, c’est-à-dire une façon de programmer, une manière de penser le découpage d’un problème en tâches. Le MapReduce représente un changement mental quant à la façon dont on a toujours écrit les algorithmes. C’est ce que nous appelons un paradigme. Un paradigme est une perception des choses, le rapport qu’un individu a vis-à-vis du monde, une manière de voir les choses, une vision du monde et de l’environnement, un schéma de pensée, une idéologie, qui produit automatiquement chez l’individu qui l’adopte une réponse, un comportement, une façon de faire précise. Dans le chapitre Transition numérique, nous donnons les détails de l’influence de la perception dans la façon dont un individu aborde le changement. Cela signifie que le MapReduce commence dans la tête, c’est une attitude mentale, un schéma de pensée que vous devez avoir quant au découpage d’un problème en tâches indépendantes. La question qui se pose alors est : en quoi consiste ce schéma de pensée ?

Le schéma de pensée algorithmique MapReduce consiste à découper le traitement d’un fichier de données...

Détails conceptuels des phases du MapReduce

Le modèle algorithmique MapReduce comporte trois phases : le Map, le Shuffle et le Reduce. Dans cette section, nous allons décrire le rôle et le fonctionnement de chacune de ces phases.

1. Phase Map

Dans cette phase, à chacune des tâches Map qui constituent le traitement, est assigné un bloc de données du fichier d’entrée stocké dans le système de fichiers distribué. Ces tâches Map transforment le bloc de données en séquences de paires de clé/valeur. La façon dont les données d’entrée sont transformées en clé/valeur est à la discrétion de l’utilisateur. Attention, pour ceux qui travaillent dans le développement des bases de données, le terme « clé » peut porter à confusion. Les clés générées ici ne sont pas les « clés » dans le sens de « clé primaire » des bases de données relationnelles. Elles ne sont pas uniques, ce sont juste des nombres, des identifiants arbitraires qui sont affectés aux valeurs des paires. La spécificité cependant est qu’à toutes les valeurs identiques du morceau de fichier est affectée la même clé. Pour que vous compreniez mieux cela, prenons l’exemple du comptage des mots dans une pile de trois documents. Chaque document dans la pile est un « morceau » stocké dans un nœud du cluster. La fonction Map avec pour argument (clé, valeur) est définie de la façon suivante : , avec k la clé, qui est ici le mot contenu dans le document, et v, la valeur, qui représente ici la référence du document dans lequel est située la clé. La figure suivante montre comment le traitement Map s’opère.

Figure...

Détails techniques de l’exécution du MapReduce dans un cluster

Considérons en détail la façon dont un programme écrit en MapReduce est exécuté. En faisant appel à une bibliothèque d’implémentation du MapReduce comme Hadoop, le système d’exploitation installé sur le cluster démarre deux types de processus sur le cluster : un processus appelé master sur le nœud de référence, et des processus appelés workers sur les nœuds de données.

Le master coordonne l’ensemble des tâches MapReduce qui s’exécutent sur le cluster, tandis que les workers sont assignés aux tâches Map (on parle alors de workers Map) d’une part et aux tâches Reduce (workers Reduce) d’autre part, mais pas aux deux en même temps (un nœud ne peut pas faire tourner pour le même traitement MapReduce un worker Map et un worker Reduce). Lorsqu’un programme utilisateur appelle la fonction MapReduce, la séquence des sept actions suivantes se produit :

Exemples d’application du MapReduce

Souvenez-vous, le MapReduce est un paradigme, une attitude mentale consistant à décomposer un problème en tâches qui vont s’exécuter parallèlement en deux phases : le Map et le Reduce. Il faut vraiment garder cela à l’esprit. Le MapReduce n’est pas une bibliothèque d’algorithmes déjà préparés un peu comme les fonctions Excel, que vous pouvez utiliser pour résoudre vos problèmes. Par exemple, vous ne trouverez pas de fonctions basiques comme les fonctions de tri ou de changement de la casse d’un texte. Ce n’est pas non plus un patron de conception, c’est-à-dire un ensemble de modèles d’algorithmes que vous pouvez enrichir pour résoudre un problème particulier. Le MapReduce n’est rien de concret. Vous devez vous-même écrire l’algorithme dans le traitement MapReduce, mais pas de la façon dont vous avez toujours écrit les algorithmes, plutôt avec une logique mentale en deux étapes : une étape qui va transformer les données en paires de clé/valeur et une étape qui va agréger ces paires. Donc, l’algorithme MapReduce n’est ni une bibliothèque de fonctions, ni quelque chose de palpable, c’est un concept, une perception, une idéologie, en somme un paradigme !

Nous allons illustrer le changement mental que représente le MapReduce avec un exemple basique. Supposons que vous vouliez calculer la somme de dix nombres consécutifs entre 1 et 10. Dans le raisonnement classique, vous développerez un algorithme qui comportera à peu près les étapes suivantes :

Dans un langage informatique comme le Python, le programme donnerait à peu près ceci :

x = 0 
for i = 1 to 10: 
   x = x + i 
   i = i + 1
 

Ce raisonnement en cinq étapes que vous auriez utilisé par défaut s’appelle le raisonnement algorithmique séquentiel. Vous vous êtes intuitivement posé la question : « comment...

Modèles alternatifs au MapReduce

Dans l’économie numérique, un modèle de traitement de données devient le standard, c’est le modèle dans lequel les calculs des données sont exécutés de façon parallèle dans des clusters de machines commodes par des couches logicielles qui gèrent automatiquement la planification des tâches, la gestion des pannes et la répartition des charges entre les machines du cluster.

Ces couches logicielles atteignent la scalabilité et la tolérance en implémentant un modèle algorithmique dans lequel les utilisateurs créent des graphes de flux de données cycliques ou acycliques auxquels sont passées les données au travers d’un jeu d’opérateurs (nous allons expliquer la notion de graphes de flux cycliques/acycliques dans ce qui suit). Ceci permet aux couches logicielles de gérer la planification des tâches définies dans les graphes, et de réagir aux interruptions susceptibles de survenir lors du traitement sans intervention de l’utilisateur. MapReduce est l’un de ces modèles algorithmiques et en est aujourd’hui le pionnier. Bien que le modèle de programmation du MapReduce soit utile pour une large classe d’applications, certaines applications ne peuvent pas s’exprimer efficacement sous forme de flux acyclique. Il s’agit de trois catégories d’applications :

Conclusion

Le président Abraham Lincoln disait : « Les dogmes du passé tranquille sont inadéquats pour le présent orageux actuel. » « The dogmas of the quiet past are inadequate to the stormy present. »

En d’autres termes, les défis que nous rencontrons actuellement ne peuvent pas se résoudre avec des solutions qui ont marché dans les challenges du passé. Dans l’ère précédente, la croissance des données était relativement calme et contrôlée, mais dans l’ère numérique, ce n’est plus le cas. Pour résoudre les challenges de l’explosion des données du Numérique, un changement de paradigme infrastructurel est nécessaire : il s’agit de passer une approche centralisée de traitement à une approche distribuée. Le deuxième changement qui est nécessaire et induit par le premier est le changement de paradigme de programmation : il s’agit de passer l’approche séquentielle du développement d’application à l’approche parallèle. Google a été parmi les premiers à ressentir ce besoin de changement et a mis au point un modèle algorithmique parallèle simple, baptisé le MapReduce. À ce stade, vous êtes prêt à étudier...

Guide d’étude du chapitre

Question 1 : Pourquoi dit-on que le MapReduce est un paradigme ?

Question 2 : Expliquez l’expression suivante : « Le calcul des index inversés est un problème "embarrasingly parallel". »

Question 3 : En quoi consiste le MapReduce ?

Question 4 : Qu’est-ce qu’un traitement parallèle ? 

Question 5 : Quelle est la différence entre un traitement parallèle et un traitement asynchrone ? 

Question 6 : Par défaut, à combien est égal le nombre de tâches Map qui sont exécutées lors d’un job MapReduce ? 

Question 7 : Pour un traitement précis, un nœud peut-il faire tourner à la fois un worker Map et un worker Reduce ? Justifiez votre réponse.

Question 8 : Supposons que l’analyste de données, dans un traitement MapReduce, spécifie le nombre de processus Reduce r = 0. Quelle sera l’incidence de cette valeur sur le traitement MapReduce ?

Question 9 : Quelle est l’entrée d’une fonction map () ?

Question 10 : Quelle est l’entrée d’une fonction reduce () ?

Question 11 : Vous souhaitez avoir le vecteur de fréquence des termes des tweets suivants :

Tweet1 (« je mange la banane »)

Tweet2 (« je...

À retenir