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. Le but est d'utiliser un nombre de machines suffisant dans l'optique d'optimiser le temps de calcul et assurer une fiabilité du système.

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. The goal is to use a sufficient number of machines in order to optimize the computation time and ensure system reliability.

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.

On note donc plusieurs choses intéressantes sur ce schéma. Tout d'abord il y un serveur primaire ayant pour but de répartir les travail entre les autres serveurs. Ce serveur "maître" détermine la quantité optimale de serveur nécessaire pour l'opération de mapping et fait de même pour l'opération de réduction. Ce serveur "maître" permet également de gérer les pannes dans les différents serveurs et de réattribuer le travail à d'autres machines.

On voit également qu'il y a plus de serveurs de mapping que de réduction, ce qui est dû à complexité du mapping et au fait qu'il est plus simple à distribuer.