MapReduce – 1ère Partie

Qu’est ce que c’est ?

MapReduce est un framework de calcul distribué sur de gros volumes de données. Il s’agit d’un modèle de programmation parallèle dont les combinators Map et Reduce sont inspirés du langage fonctionnel Lisp.

MapReduce a été développé dans Google comme mécanisme pour traiter des gros volumes de données en environnement distribué. Il permet de répartir la charge sur un grand nombre de serveurs et gère entièrement, d’une manière transparente, le cluster, la distribution de données, la répartition de la charge et la tolérance aux pannes.

MapReduce apporte une abstraction quasi-totale de la couche matérielle de l’infrastructure. La librairie MapReduce de Google existe dans plusieurs langages de programmation dont C++, C#, Erlang, Java, Python, Ruby…D’autres librairies implémentent bien ce concept : par exemple Hadoop de la fondation Apache et Elastic de chez Amazon …

Ces mécanismes dont je présente les principes, dans cette conférence, peuvent être appliqués pour exécuter les algorithmes de fouille de données en mode PaaS (Platform as a Service) dans un Cloud privé.

Qui utilise MapReduce ?

Plusieurs grands acteurs du monde web comme Google, Yahoo, Facebook et bien d’autres utilisent MapReduce. En effet, parmi les diiféentes utilisation de Mapreduce par ces grands acteurs on trouve que Google l’utilise pour construire les index de Google Search, Yahoo l’utilise pour la detection de spam, facebook l’utilise à des fins de Data Mining.

Egalement, MapReduce est utilisé par les laboratoires de Recherches à travers le monde pour faire par exemple de l’analyse d’images astronomique, de la bioinformatique, de la simulation métrologique, de l’Apprentissage Machine (Machine Learning), pour des statistiques, etc…(Continuer la lecture…)

Avant MapReduce

Le traitement de gros volumes de données et la gestion de milliers de processeurs dans un systèmes distribués reste une tâche relativement difficile et n’est pas à la portée des d’un développeur débutant. Alors comment cette tâche deviendra-t-elle si en plus nous devons considérer la parallélisation et la distribution des traitements ? Sans oublier que dans un environnement distribué il faut aussi gérer les entrées / sorties et également prévoir unmécasinme de tolérance aux pannes. C’est là exactement où MapReduce vient au secours des développeurs en fournissant une infrastructure fournissant toutes ces fonctionnalités facilement !

MapReduce pour quelle problématique ?

Souvent lorsqu’on manipule des données nous effectuons les mêmes opérations, à savoir :

  1. Itérer sur un grand nombre d’enregistrements
  2. Extraire quelque chose ayant un intérêt de chacun de ces enregistrements

  3. Regrouper et trier les résultats intermediaires
  4. Agréger tous ces résultats ensemble
  5. Générer le résultat final

Pour faire l’analogie entre ces différentes opérations et le modèle de programmaption MapReduce, nous pouvons dire que les opérations 1 et 2 correspondent à la fonction MAP tandis que les opérations 3, 4 et 5 correspodent à la fonction REDUCE.

L’algorithme MapReduce

MapReduce peut être vu comme un framework middleware qui trouve sa place entre les données en entrée et le résultat en sortie. Son fonctionnement reste relativement simple. Une tâche est divisée en deux ou plusieurs sous-tâche dont chacune est traitée indépendamment, puis leurs résultat sont combinés. On disingue 3 opérations majeures : Split, Compute et Join. Split correspond à une opération de découpage, Compute correspond à une opération de calcul puis Join correspond à l’opération de regroupement du résultat.

MapReduce comme MiddleWare

Dans le modèle de programation MapReduce, le développeur implémente deux fonctions : la fonction Map et la fonction Reduce. La fonction Map prend en entrée un ensemble de “Clé, Valuers”, et retourne une liste intermédiaire de “Clé1, Valeur1”.

Map(key,value) -> list(key1,value1)

La fonction Reduce quant à elle, elle prend en entrée une liste intermédaire de “Clé1, Valeur1” et fournit en sortie une ensemble de “Clé1, Valeur2”.

Reduce(key1,list(value1)) -> value2

La fonction Reduce quant à elle, elle prend en entrée une liste intermédaire de “Clé1, Valeur1” et fournit en sortie une ensemble de “Clé1, Valeur2”.

Une fois lancé, l’algorithme MapReduce s’exécute en cinq phases :

  1. La phase Initialisation
  2. La phase Map
  3. La phase regroupement (Shuffle)
  4. La phase de tri
  5. La phase Reduce

Fonctionnement de MapReduce

L’utilisateur (ou le développeur) lance son application MapReduce qui comence par créer le composant Master. Celui-ci est responsable de la coordination de l’éxécution des différentes “unités de travail” appellées “Workers“. Ensuite, le Master attribue aux unités de travail les tâches “map” et “reduce“.

Egalement, le Master est responsable de la distribution des données. Durant son cycle d’éxécution, le Master gère la synchronisation, la réorganisation, le tri et le regrouppement des données. Lorsqu’un worker de type “map” a fini son traitement, il informe le Master qui regroupe, tri en renvoie le résulat à un worker de type “reduce”.

 

Suite dans MapReduce – 2ème Partie

Leave a Reply