Map reduce

MapReduce

MapReduce est un framework de développement informatique, introduit par Google, dans lequel sont effectués des calculs parallèles, et souvent distribués, de données potentiellement très volumineuses (> 1 terabyte).

Les terminologies de "Map" et "Reduce", et leur idée générale, sont empruntées aux langages de programmation fonctionnelle utilisés pour leur construction (map et réduction de la programmation fonctionnelle et des langages de programmation tableau).

Le concept du framework MapReduce s'articule en deux étapes :

• Dans l'étape Map le nœud à qui est soumis un problème, le découpe en sous-problèmes, et les délègue à d'autre nœuds (qui peuvent en faire de même récursivement). Les sous-problèmes sont ensuite traités par les différents noeud à l'aide de la fonction Map qui à un couple (clé, valeur) associe un ensemble de nouveaux couples (clé, valeur).
• 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 correspondant à 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.

Il y a plusieurs implémentation de ce framework dans différents langages (c++, java, python, etc) et par de nombreux organismes (Google, Yahoo, etc).

Mapping et réduction

Une fonction map itère sur une liste d'éléments indépendants et accomplit une opération spécifique sur chaque élément. La liste des réponses est stockée séparément de la liste originale. Parce que chaque élément est calculé indépendamment et que la liste originale n'est pas modifiée, il est très facile de réaliser une opération map en parallèle. Sur du matériel approprié cela permet à des quantités extrêmement importantes de données d'être calculées en des temps très courts.

Par exemple, considérons une liste de notes d'examen, où chaque note est 1 point trop élevée. Une fonction map de s - 1 pourrait être appliquée sur chaque note s.

Une opération Reduce prend une liste et combine les éléments selon un algorithme particulier. Puisqu'un reduce se termine toujours par une seule réponse, elle n'est pas parallélisable par une fonction map, mais le grand nombre de calculs relativement indépendants permet que les fonctions reduce soient toujours utiles en environnements fortement parallèles.

Pour continuer avec l'exemple précédent, comment faire si l'on souhaite connaître la moyenne de la classe ? On peut définir une fonction de réduction qui diminue de moitié la liste par ajout d'une entrée dans la liste des voisins, récursivement, on continue jusqu'à ce qu'il y ait seulement une (grosse) entrée, et divise la somme totale par l'entrée originale d'éléments pour avoir la moyenne).

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; on s'attend à ce que chaque nœud retourne périodiquement le travail accompli et les modification de statut. Si un nœud ne retourne rien pendant cet intervalle, le nœud maître (similaire au serveur maître du Google File System) considère le nœud comme mort, et envoie les données assigné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 (permit pour les effets de bords).

Les opérations de réduction fonctionnent plus ou moins de la même manière, mais en raison de leurs propriétés inférieures concernant les opérations concurrentes, 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 conserve la bande passante, ce que leurs réseaux internes n'ont pas beaucoup.

Utilisations

D'après Google, ils utilisent MapReduce dans un large éventail d'applications, dont "distributed grep, distributed sort, web link-graph reversal, term-vector per host, web access log stats inverted index construction, document clustering, machine learning, statistical machine translation…" (grep distribué, tri distribué, inversion de lien-graphique web, vecteur de terme par hôte, statistiques d'accès au web, construction d'index inversé, clustering de document, apprentissage machine, traduction machine statistique…). De manière plus significative, quand MapReduce fut fini, il a été utilisé pour complètement regénérer les index Internet de Google, et remplacer les vieux programmes ad hoc par la mise à jour d'index. MapReduce génère un large nombre d'intermédiaire, de fichiers temporaires, qui sont généralement géré par, et accédé à travers du, Google File System pour de meilleures performances.

Implémentations

• Le framework de Google est codé en C++ avec des interfaces en Python et Java.
• Le projet Nutch a développé une implémentation expérimentale de MapReduce : [1].
• Le projet Hadoop est un projet libre développé en Java qui utilise une implémentation de MapReduce issu de Nutch

Références

• MapReduce du Wikipédia anglophone
• Dean, Jeffrey & Ghemawat, Sanjay (2004). "MapReduce: Simplified Data Processing on Large Clusters"
• Présentation des recherches de Google sur MapReduce pour l'OSDI 2004

Ce document provient de « MapReduce ».