Map reduce : utilisation et conception

hadoop

Cet article reprend la suite de la semaine 1 du MOOC «Cloud Computing Concepts» sur Coursera et s'intéressera à Map reduce. D'abord en tant qu'utilisateur, puis en explorant la conception interne d'un tel système, en particulier l'ordonnanceur.

Qu'est-ce que Map reduce et comment l'utiliser

Map reduce est un algorithme qui permet de traiter une grande quantité de données et est composé de deux composants de calculs :

  • La partie Map qui applique une fonction à chaque élément séquentiellement et indépendamment (par exemple, calculer le carré de tous les éléments d'une liste)
  • La partie Reduce qui applique un traitement en batch à tous les éléments. La partie Reduce permet de fusionner les résultats.

Pour paralléliser le traitement des réductions, on extrait une clé à partir de la sortie des maps et on répartie sur les différents reduce à partir de cette clé.

Il est possible de chaîner les Map reduce afin de produire des résultats complexes. De même, la partie Reduce peut agir en plusieurs passes.

La programmation en map reduce nécessite les étapes suivantes :

  1. Implémenter un programme de Mapping et un programme de Reduce.
  2. Il faut ensuite spécifier le nombre de Map et Reduce à utiliser en fonction du problème.
  3. Enfin, on soumet un Job et il ne reste qu'à attendre le résultat.

Il n'est pas nécessaire pour l'utilisateur de connaître la programmation parallèle ou distribuée.

Les internes de Map Reduce

Les problématiques d'architecture à résoudre sont les suivantes :

  1. Comment paralléliser le Mapping
  2. Comment transformer les données de Map au Reduce
  3. Comment paralléliser le Reduce
  4. Comment implémenter le stockage des entrées et sorties du Map et du Reduce

Il faut enfin s'assurer que le Reduce ne soit pas exécuter avant que tous les Maps ne soient terminés. Cette barrière n'est pas obligatoire dans le cas où l'on garde un résultat partiel pour les clefs utilisées.

Comment résoudre ces problématiques ?

  1. Vu que le Map est indépendant, aucune difficulté à ce niveau
  2. Pour transférer les données des Maps aux Reduce, on utilise une fonction de hachage qui associe à chaque clef un unique Reduce.
  3. Paralléliser les Reduce ne pose pas de difficulté non plus étant donné qu'ils sont indépendants
  4. Niveau stockage, l'entrée du mapping et la sortie du reduce doivent se faire via un système de fichier distribué étant donné que ces composants sont distribués et les accès aux données doivent se faire parallèlement. La sortie du mapping peut se faire localement et chaque reduce ira y chercher les résultats à distance.

La question à laquelle il nous reste à répondre est celle de l'ordonnancement.

L'ordonnancement

Nous allons prendre comme exemple Hadoop YARN (Yet Another Resource Negociator).

YARN est composé de 3 composants :

  • Le Resource Manager, un composant global au réseau qui est responsable d'informer les Application Manager des nœuds libres pour exécuter les tâches en attente
  • Les Node Manager, implantés dans chaque serveur, sont responsables de l'exécution des jobs et informent le Resource Manager lorsqu'ils sont libres pour accueillir de nouveaux jobs
  • Les Application Manager, un par job, qui demandent au Resource Manager sur quels nœuds exécuter leurs tâches, puis, une fois la réponse reçue, envoyer la dite tâche au nœud reçu.

La gestion d'erreurs est assurée de la façon suivante :

Un système de heartbeat informe le Resource Manager que chaque Node Manager est accessible. Si un Node Manager ne donne pas signe de vie, le Resource Manager informe chaque Application Manager dont une tâche était exécutée par le nœud inaccessible afin qu'il négocie la réaffectation de la tâche à un autre nœud.

Chaque Node Manager garde une trace de toutes les tâches qu'il exécute. En cas d'échec d'une tâche, le nœud passe en état idle et redémarre la tâche.

Le Resource Manager reçoit aussi un heartbeat de chaque Application Manager. En cas d'échec, le Resource Manager redémarre l'Application Manager en erreur qui se resynchronise avec ses tâches en cours au près des différents Node Manager.

En cas de défaillance de Resource Manager, un nouveau Resource Manager est démarré et utilise un vieux checkpoint pour que l'état du système soit cohérent.

En cas de lenteur, si un timeout survient sur un job, il est répliqué. Le premier à terminer sera considéré comme étant le résultat à garder. Il s'agit une exécution spéculative.

Post a Comment

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*