MapReduce est un patron de conception de développement informatique, inventé par Googlehttp://www.google.com/patents/US7650331 Brevet octroyé, dans lequel sont effectués des calculs parallèles, et souvent distribués, de données potentiellement très volumineuses, typiquement supérieures en taille à un téraoctet.
Les termes « map » et « reduce », et les concepts sous-jacents, sont empruntés aux langages de programmation fonctionnelle utilisés pour leur construction (map et réduction de la programmation fonctionnelle et des langages de programmation tableau).
MapReduce permet de manipuler de grandes quantités de données en les distribuant dans un cluster de machines pour être traitées. Ce modèle connaît un vif succès auprès de sociétés possédant d'importants centres de traitement de données telles Amazon.com ou Facebook. Il commence aussi à être utilisé au sein du Cloud computing. De nombreux frameworks ont vu le jour afin d'implémenter le MapReduce. Le plus connu est Hadoop qui a été développé par Apache Software Foundation. Mais ce framework possède des inconvénients qui réduisent considérablement ses performances notamment en milieu hétérogène. Des frameworks permettant d'améliorer les performances de Hadoop ou les performances globales du MapReduce, tant en matière de vitesse de traitement qu'en consommation électrique, commencent à voir le jour.
Présentation Un modèle de programmation MapReduce est un modèle de programmation popularisé par Google. Il est principalement utilisé pour la manipulation et le traitement d’un nombre important de données au sein d’un cluster de nœuds.
MapReduce consiste en deux fonctions map() et reduce(). Dans l'étape Map, le nœud analyse un problème, le découpe en sous-problèmes, et le délègue à d'autres nœuds (qui peuvent en faire de même récursivement). Les sous-problèmes sont ensuite traités par les différents nœuds à l'aide de la fonction Map qui à un couple (clé, valeur) associe un ensemble de nouveaux couples (clé, valeur) : // En pseudo code cela donnerait Map(void * document) { int cles = 1; foreach mot in document calculIntermediaire(mot, cles); } Vient ensuite l'étape Reduce, où les nœuds les plus bas font remonter leurs résultats au nœud parent qui les avait sollicités. Celui-ci calcule un résultat partiel à l'aide de la fonction Reduce (réduction) qui associe toutes les valeurs correspondantes à la même clé à une unique paire (clé, valeur). Puis il remonte l'information à son tour. À la fin du processus, le nœud d'origine peut recomposer une réponse au problème qui lui avait été soumis : // En pseudo code cela donnerait Reduce(int cles, Iterator values) { int result = 0; foreach v in values result += v; } Un cluster MapReduce utilise une architecture de type Maître-esclave où un nœud maître dirige tous les nœuds esclaves.
MapReduce possède quelques caractéristiques : Le modèle de programmation du MapReduce est simple mais très expressif. Bien qu’il ne possède que deux fonctions, map() et reduce(), elles peuvent être utilisées pour de nombreux types de traitement des données, les fouilles de données, les graphes… Il est indépendant du système de stockage et peut manipuler de nombreux types de variable. Le système découpe automatiquement les données en entrée en bloc de données de même taille. Puis, il planifie l’exécution des tâches sur les nœuds disponibles. Il fournit une tolérance aux fautes à grain fin grâce à laquelle il peut redémarrer les nœuds ayant rencontré une erreur ou affecter la tâche à un autre nœud. La parallélisation est invisible à l'utilisateur afin de lui permettre de se concentrer sur le traitement des données
vignette|upright=2.25|centré|Schéma de fonctionnement du MapReduce
Une fois qu'un nœud a terminé une tâche, on lui affecte un nouveau bloc de données. Grâce à cela, un nœud rapide fera beaucoup plus de calculs qu'un nœud plus lent. Le nombre de tâches Map ne dépend pas du nombre de nœuds, mais du nombre de blocs de données en entrée. Chaque bloc se fait assigner une seule tâche Map. De plus, toutes les tâches Map n'ont pas besoin d'être exécutées en même temps en parallèle, les tâches Reduce suivent la même logique. Par exemple, si des données en entrée sont divisées en 400 blocs et qu'il y a 40 nœuds dans le cluster, le nombre de tâches Map sera de 400. Il faudra alors 10 vagues de Map pour réaliser le mapping des données.
Le MapReduce est apparu en 2004. La technologie est encore jeune. Elle souffre de quelques points faibles : Elle ne supporte pas les langages haut niveau comme le SQL Elle ne gère pas les index. Une tâche MapReduce peut travailler une fois les données en entrée stockées dans sa mémoire. Cependant, MapReduce a besoin d'analyser chaque donnée en entrée afin de la transformer en objet pour la traiter, ce qui provoque des baisses de performance. Elle utilise un seul flot de données. MapReduce est facile à utiliser avec une seule abstraction mais seulement avec un flot de donnée fixe. Par conséquent, certains algorithmes complexes sont difficiles à implémenter avec seulement les méthodes map() et reduce(). De plus, les algorithmes qui requièrent de multiples éléments en entrée ne sont pas bien supportés car le flot de données du MapReduce est prévu pour lire un seul élément en entrée et génère une seule donnée en sortie. Quelques points peuvent réduire les performances de MapReduce. Avec sa tolérance aux pannes et ses bonnes performances en passage à l'échelle, les opérations de MapReduce ne sont pas toujours optimisées pour les entrées/sorties. De plus, les méthodes map() et reduce() sont bloquantes. Cela signifie que pour passer à l'étape suivante, il faut attendre que toutes les tâches de l'étape courante soient terminées. MapReduce n'a pas de plan spécifique d'exécution et n'optimise pas le transfert de données entre ces nœuds.
Distribution et fiabilité MapReduce tire sa fiabilité de la répartition, sur chaque nœud du réseau, des opérations à appliquer au jeu de données ; le développeur s'attend à ce que chaque nœud retourne périodiquement le travail accompli et les modifications de statut. Si un nœud ne retourne rien pendant cet intervalle, le nœud maître (appelé NameNode en Hadoop) (similaire au serveur maître du Google File System) considère le nœud comme mort, et envoie les données affectées à ce nœud à d'autres nœuds. Les opérations individuelles utilisent des opérations atomiques pour les nommages des fichiers de sortie comme une vérification double pour s'assurer qu'il n'y a aucun conflit parallèle avec un thread en cours ; quand les fichiers sont renommés, il est aussi possible de les copier sous un autre nom en plus du nom de la tâche (permis pour les effets de bords).
Les opérations de réduction fonctionnent sensiblement de la même manière, mais en raison de leurs , le nœud maître tente de programmer les opérations de réductions sur le même nœud, ou aussi proche possible du nœud détenant les données qui doivent être traitées. Cette propriété est préférée par Google car elle ne nécessite pas de bande passante supplémentaire. Ceci est un avantage car la bande passante est souvent limitée dans les réseaux internes aux entreprises.
Les facteurs de performance D'après une étude de 2010 de l'Université nationale de Singapour, il existe cinq facteurs qui influent sur les performances du MapReduce.
Le modèle de programmation MapReduce a été conçu pour qu'il soit indépendant du système de stockage des données. Il lit les paires <clé, valeur> à l'aide d'un lecteur. Le lecteur récupère chaque enregistrement contenu dans le système de stockage, puis il les place dans une paire <clé, valeur> afin de pouvoir les traiter lors de MapReduce. Bien que MapReduce ne dépende pas d'un système de stockage particulier, il éprouve des difficultés lorsque le système de stockage est une base de données. Les systèmes de bases de données parallèles commerciaux utilisent un moteur pour exécuter les requêtes et un moteur de stockage. Pour exécuter une requête, le moteur de requêtes lit directement les données depuis le moteur de stockage. MapReduce doit d'abord lire la valeur, puis la stocker dans une paire à l'aide du lecteur, ce qui explique pourquoi MapReduce est moins performant dans les bases de données. En comparant MapReduce et les systèmes de bases de données parallèles, trois facteurs, pouvant affecter les performances de MapReduce, ont été mis en évidence : mode d'entrée/sortie : la façon dont le lecteur récupère les informations ; l'analyse des données : la façon dont le lecteur analyse les données ; l'indexation.
MapReduce utilise un système de planification afin d'affecter les blocs de données aux nœuds disponibles dans le cluster. Ce système provoque des coûts d'exécution et peut ralentir l'exécution de MapReduce. Deux facteurs peuvent influencer les performances de MapReduce : la taille des blocs de données distribués ; l'algorithme de planification.
Mode entrée/sortie Deux modes de lectures peuvent être utilisés par le lecteur afin de lire les données stockées dans un système de stockage. Le mode entrée/sortie direct avec lequel le lecteur lit directement les données stockées dans le disque local. Dans ce cas, les données sont transférées depuis la mémoire cache vers la mémoire du lecteur en utilisant l'accès direct à la mémoire. Le mode entrée/sortie streaming avec lequel le lecteur lit les données depuis un autre processus en cours d'exécution à l'aide de moyen de communication entre les processus comme TCP/IP ou JDBC.
D'après les tests réalisés dans cette étude, la différence de performance entre ces deux modes est faible (environ 10 %).
Le parsage des données Quand le lecteur récupère les données depuis le système de stockage, il doit convertir les données en paire <clé, valeur> pour continuer l'exécution (ce processus s'appelle l'analyse de données). L'analyse consiste à décoder les données depuis leur format natif de stockage afin de les transformer vers un format qui pourra être utilisé par un langage de programmation. Il existe deux types de décodage, le décodage immuable et le décodage mutable. Le décodage immuable consiste à transformer des données en objets immuables. Les objets immuables en programmation orientée objet sont des objets dont l'état ne peut être modifié après leur création contrairement aux objets mutables.
Lorsque l'on utilise le décodage immuable, chaque donnée sera alors placée dans un objet immuable. Par conséquent, si l'on décode 4 millions de données, 4 millions d'objets immuables seront créés. Par défaut, le MapReduce de Google utilise des objets immuables..
Une autre méthode consiste à utiliser le décodage mutable. Avec ce décodage, un objet mutable est réutilisé pour décoder toutes les données. Ainsi, le nombre de données n'est plus important car seulement un objet sera créé.
D'après les études, les faibles performances du parsage sont dues au décodage immuable. Le décodage immuable est plus lent que le décodage mutable car il produit un grand nombre d'objets immuables durant le processus de décodage. La création de tous ces objets immuables augmente la charge de travail des processeurs.
L'indexation Le MapReduce étant indépendant du système de stockage, il ne peut pas prendre en compte l'ensemble des données en entrée pour avoir un index disponible. MapReduce ne semble pas capable d'utiliser des index. Cependant, trois méthodes pour utiliser les index ont été trouvées afin d'augmenter la vitesse du processus du traitement des données. MapReduce offre une interface aux utilisateurs pour spécifier un algorithme pour la distribution des nœuds. Par conséquent, il est possible d'implémenter un algorithme qui utilise l'index pour réduire les blocs de données.