MapReduce – 2ème Partie

Ceci est la deuxième partie de l’article autour de MapReduce. La première partie peut être consultée ici.

Un mot à propos des ‘Workers’ MapReduce

Comme évoqué, un ‘Worker‘ correspond à une ‘unité de travail’. Cette unité possède trois états:

1. idle
2. in-progress
3. completed

• L’état idle indique qu’un worker est disponible pour une nouvelle planification de traitement.

• L’état completed indique la fin d’un traitement, le worker informe le Master de la taille, de la localisation de ses fichiers intermédiaires.

• L’état in-progress indique qu’un traitement est toujours en cours d’exécution.

Exemple de mise en oeuvre de MapReduce

Imaginons que l’on souhaite calculer le nombre de mots dans un document. Comme avec MapReduce, il faudra fournir deux fonctions, la fonction Map et la fonction Reduce, nous allons fournir deux fonctions. Voyons que contiendra chacune de ces fonctions.

Nous allons tout d’abord idenifer notre document avec une clé unique key et considérer que value correspond au contenu du document. en ce cas notre fonction Map sera de la forme:

mapFunc(String key, String value):
// key: id du document;
// value: contenu du document
for each word w in value
EmitIntermediate (w, 1)

Dans cet extrait, mapFunc est une méthode qui prend deux arguments, la clé (key) qui identifie le document pour lequel nous souhaitons faire l’opération de comptage des mots, et le contenu du document (value).
Ensuite l’ensemble des valeurs est parcouru par une boucle ‘foreach‘, et pour chaque mot identifié, nous appelons la méthode EmitIntermediate qui placera dans une zone intermédiaire le mot et la valeur  1 (correspondant une occurrence).

reduceFunc(Stringkey, Iterator values)
// key: un mot;
// values: une liste de valeurs
result = 0
for each count v in values
result += v
EmitResult(result)

La fonction reduceFunc quant à elle, c’est une fonction qui prend deux arguments, la clé (key) qui cette fois-ci correspond à un mot identifié par la fonction mapFunc, et une liste de valeurs contenant le nombre d’occurrences de ce mot. La liste des valeurs correspond à l’ensemble des paires (mot, count) mises en zones intermédiaires par la fonction mapFunc.

Comme nous souhaitons comptabiliser tous les mots du document, nous commençons par initialiser la variable result à 0, puis nous allons itérer sur l’ensemble des valeurs de la liste, puis chaque valeur est rajoutée à la variable result. A la fin de l’itération, la variable result contient le total du nombre d’occurrence et le résultat est renvoyé par la fonction EmitResult.
Considérons l’exemple suivant :

 

 

 

 

Dans cet exemple, nous avons un fichier en entrée contenant trois lignes dont chacune contient trois lettres (AAC,CBD,ACD).
La figure illustre les différentes étapes d’exécution de l’algorithme (de gauche à droite). Ces étapes sont :

1. File
2. Splitting
3. Map
4. Shuffling
5. Reduce
6. Result

• L’étape File : on lit le fichier en entrée et on initialise les différents ‘Workers’ MapReduce.
• L’étape Splitting : on distribue les données à traiter sur les différents noeuds du cluster de traitement.
• L’étape Map : on effectue le compte de chacune des lettres et ceci en local sur chaque noeud du cluster de traitement.
• L’étape Suffling : on regroupe toutes les lettres ainsi que leur compte à partir de tous les noeuds de traitement.
• L’étape Reduce : on effectue le cumule de toutes les valeurs de chaque lettre.
• L’étape result : on agrège tous les résultats des différentes étapes Reduce et on retourne le résultat final

Exemples d’applications de MapReduce

Plusieurs exemples d’applications peuvent être cités comme :  (bien sûr il ne s’agit en aucun cas d’une liste exhaustive)

• Calculer la taille de plusieurs milliers de documents
• Trouver le nombre d’occurrence d’un pattern dans un très grand volume de données
• Classifier de très grand volumes de données provenant des paniers d’achats de clients
• …

Avantages et inconvénients de MapReduce

MapReduce fournit une abstraction totale des mécanismes de parallélisations sous-jacents. D’un autre côté, lors des développements autour de MapReduce, peu de tests sont nécessaires étant donné que toutes les fonctions de Mapreduce ont déjà fait l’objet de tests et fonctionnent correctement.
Ceci sans oublier que le développeur se concentre sur son propre code et non pas à la gestion et la synchronisation des différents processus. Outre les environnement distribués de Grid Computing, MapReduce et très largement utilisé dans les environnements de Cloud Computing.

On peut reprocher toutefois à MapReduce qu’il possède une seule entrée pour les données et qu’il possède uniquement deux primitives de haut-niveau. Ceci a pour effet de rendre le flux de données très rigide. De même son système de fichiers distribués (HDFS) possède une bande passante limitée en entrée / sortie.
Dans l’implémentation Hadoop les opération de tris limitent les performances du framework.

Les différentes implémentations de MapReduce

Parmi les différentes implémentations du modèle de programmation MapReduce, nous pouvons citer : (liste non exhaustive)

• Hadoop de yahoo
• DryadLinq de Microsoft
• MapReduce-Merge, qui étend le modèle avec la possibilité de fusionner des résultat.s
• Elastic de Amazon
• …

20 mai 2020