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’éxécution. (Continuer la lecture…)

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 consiédé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 for each, et pour chaque mot identifié, nous appellons la méthode EmitIntermediate qui placera dans une zone intérdémdaire le mot et la valeur  1 (correspondant une occurence).

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 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’occurences de ce mot. La liste des valeurs correspond à l’ensemble des paires (mot, count) mises en zones intérmé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’occurence et le resultat est renvoyé par la fonction EmitRsult.

Considérons l’exemple suivant :

Exemple MapReduce

Exemple MapReduce

 

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’éxé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 regrouppe toutes les lettres ainsi que leur compte à partir de tous les noeuds de traitempent.
  • L’étape Reduce : on effectue le comule de toutes les valeurs de chaque lettre.
  • L’étape result : on aggrège tous les résultats des différentes étapes Reduce et onretourne le résulat final

Exemples d’applications avec 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’occurence 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 parralé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 deuxprimitives 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)

 

12 Responses to “MapReduce – 2ème Partie”

  1. Merci beaucoup pour ces informations claires et organisé sur MapReduce, Bonne continuation :)

  2. Très bon article sur l’algo. Après lecture de 3 articles en anglais incluant celui du site officiel, j’ai trouvé celui-ci bien expliqué et surtout la reference qui manquait dans tous les autres articles c’est que cet algo est basé sur “Diviser pour règner” (pour les vieux informaticiens comme moi du siecle dernier ca parle bien).En effet apres avoir vu un code en python j’ai eu du mal a nommer l’algo que j’avias sur le bout de la langue et qui n’etait pas du tout une “découverte” de google.
    Petite remarque, je rajouterai aux tests sur les algos des valeurs sur des données réelles et je rajouterai les cas limites d’utilisation. Enfin a titre personnel j’aimerai bien voir la différence avec l’algo parallele classique (type PRAM…)

Leave a Reply to bob0