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).

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 nœuds à 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émentations 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 aux fonctions reduce d'être 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 modifications 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 (permis 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

MapReduce peut être utilisé pour un grand nombre d'applications^[1], dont grep distribué, tri distribué, inversion du graphe des liens web, vecteur de terme par hôte, statistiques d'accès au web, construction d'index inversé, classification automatique de documents, apprentissage automatique^[2], traduction automatique statistique (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). De manière plus significative, quand MapReduce fut terminé, il a été utilisé pour régénérer entièrement les index Internet de Google, et a remplacé les vieux programmes ad hoc utilisés pour la mise à jour de ces index et pour les différentes analyses de ces index^[3].

MapReduce génère un large nombre d'intermédiaires et de fichiers temporaires, qui sont généralement gérés et accédés via le Google File System pour de meilleures performances.

Implémentations

• Le framework de Google est codé en C++ avec des interfaces en Python, Java et depuis peu le Go.
• Le projet Hadoop est un projet libre développé en Java qui utilise une implémentation de MapReduce issu de Nutch

Brevet

Google a obtenu un brevet sur la fonction MapReduce, mais la validité de ce brevet est contestée^[4],[5].

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « MapReduce » (voir la liste des auteurs)

Voir aussi

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

• Portail de l’informatique