MapReduce

• Enseignant: Didier Donsez et Georges-Pierre Bonneau
• UE/Module: EAR en RICM5 option S&R
• Eleve: Mathieu Dewulf
• mail: Mathieu.Dewulf@e.ujf-grenoble.fr

Résumé

MapReduce est un canevas de calcul massivement parallèle et distribué sur d'importantes quantités de données. MapReduce a pour objectif de répartir la charge de calcul sur divers serveurs. MapReduce permet donc de traiter des tera-données en parallèle sur des clusters de plusieurs milliers de machines.

Google a été le premier à introduire le canevas MapReduce, qui a été depuis également utilisé par Yahoo, Facebook entre autres.

Abstract

MapReduce is a framework for massively parallel and distributed calculation of large amounts of data. MapReduce is designed to distribute the computational load on various servers. MapReduce can process the parallel tera data on clusters of several thousand machines.

Google was the first to introduce the MapReduce framework, which has since been also used by Yahoo, Facebook and more others companies.

Contexte

Pour comprendre l'utilité de l'utilisation de MapReduce, il faut comprendre l'importance de la parallélisation et de la distribution des calculs sur divers serveurs. En effet une machine unique ne peut effectuer qu'un nombre limité de calcul à la seconde. Donc dès lors qu'il s'agit de traiter d'importantes quantités de données cela peut prendre un temps conséquent, quelques minutes ou quelques heures qui dans le cas de calcul critique, ou de calcul ayant une fréquence élevée pose problème.

Pour ne pas surcharger une machine il est nécessaire de distribuer ces calculs et MapReduce permet justement d'effectuer une distribution et un parallélisme automatique, résistant aux pannes et respectant une structure pré-établie.

Principes

MapReduce se divise en deux parties majeurs qui sont le mapping et la réduction des données à calculer.

Mapping

Lors d'une opération de Mapping, qui est parallèle, le fichier en entrée est divisé en plusieurs morceaux. Cette décomposition ne tiens pas compte de la structure du fichier étant donné que la tâche de Mapping ne sait rien à propos de ces données.

Une fonction de mapping agit sur une liste d'éléments et applique une focntion spécifique sur chaque élément de cette liste. Ces données traitées sont stockées temporairement pour pouvoir être traitées ensuite. les différents éléments sont calculés séparément, permettant ainsi d'effectuer cette tâche de mapping en parallèle et ainsi faire des calculs massifs plus rapidement.

La fonction de mapping prend donc en entrée une fichier, ou un ensemble de données et retourne une liste d'élément en sortie.

Reduction

Suite à l'opération de mapping ayant décomposé et traité un ensemble de données, il est nécessaire d'effectuer une opération de réduction des données. Cette opération permet de récupérer l'ensemble des fragments de données mappés et de les rassembler dans un fichier de sortie unique. Ce résultat pourra ensuite être traité de la façon souhaitée.

la reduction s'effectue de la manière suivante. D'abord la réduction s'applique avec la graine fournie par le mapping, puis ensuite avec les valeurs intermédiaires générées par la réduction jusqu'à obtenir un élément final. Bien que la fonction de réduction se termine toujours par une unique réponse et donc à priori non parallélisable, un certain nombre de calculs indépendants peuvent être distribué pour permettre d'accroître les performances et ainsi gagner plus de temps.