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.

Caractéristiques

Distribution et parallélisme

La principale caractéristique et intérêt de MapReduce et le parallélisme des calculs effectués. Cela permet de traiter de manières simultanées des données pouvant aller de plusieurs giga-octets de données à plusieurs tera-octets de données. Ces opérations peuvent être effectuées en parallèle du moment qu'elle ne touche rien en commun, ce qui est correctement établi grâce à la fonction de mapping.

Résistance aux pannes

Le canevas MapReduce est distribué, ce qui assure une certaine résistance aux pannes et ainsi conserver un état global stable et fiable.

Si le serveur "maître" tombe en panne, alors les autres serveurs détectent cette panne au fait qu'ils ne peuvent plus remonter d'informations. Naturellement un nouveau serveur "maître" est élu et reprend les tâches à la dernière sauvegarde effectuée. ce qui signifie que les valeurs intermédiaires sont perdues et que les tâches correspondantes devront être recommencées.

Si un serveur de tâches, mapping ou réduction, tombe en panne, celui-ci sera détecté par le serveur "maître" qui effectue un détection périodique. Les tâche de mapping ou de réduction non terminées sont recommencées sur un nouveau serveur dans le but de finaliser leurs exécution et de stabiliser le système.

Utilisations

La librairie MapReduce de Google existe dans plusieurs langages de programmation dont C++, C#, Erlang, Java, Python, Ruby...

Le framework le plus connu utilisant MapReduce est Hadoop, qui permet de gérer des applications distribuées et des gérer d'importantes quantités de données.

La fonction de recherche de Yahoo est une application Hadoop utilisant plus de 10.000 noeuds Linux. Facebook utilise plusieurs grappe de serveurs utilisant Hadoop pour gérer près de 205 giga-octets de données au quotidien. MapReduce est également utilisé par Twitter, Amazon, Rackspace, LinkedIn, IBM, Veoh et Microsoft.

Oracle utilise à l'heure actuelle des fonctions MapReduce dans certains de ces systèmes de gestion de base de données.

Sources

• http://fr.wikipedia.org/wiki/MapReduce
• http://www.mapreduce.org/
• http://architectures-web.smile.fr/Repartition-de-charge/MapReduce-et-Hadoop
• http://code.google.com/intl/fr-FR/edu/parallel/mapreduce-tutorial.html