MapReduce

Traduction de l'article MapReduce du Wikipédia anglophone

MapReduce est un outil de programmation développé par Google en C++, dans lequel des calculs parallèles de données très grosses (> 1 terabyte) sont effectués.

Les terminologies de "Map" et "Reduce", et leur idée général, 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 logiciel actuel est implémenté par une fonction Map qui à une paire de valeur-clef associe un ensemble de nouvelles paires de valeur-clef et d'une fonction Reduce (réduction) qui associe toutes les valeurs-clef mappées partageant la même clef à une unique paire de valeur-clef.

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 de 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 est seulement une (grosse) entrée, et divise la somme totale par l'entrée originale d'élément pour avoir la moyenne).

MapReduce obtient sa fiabilité en partageant les opérations sur un ensemble de données à chaque nœud du réseau ; on s'attend à ce que chaque nœud rapporte périodiquement le travail complet et les mises à jour du statut. Si un nœud sombre dans le silence plus que cet intervalle, le nœud maître (similaire au serveur maître du Google File System) enregistre 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.

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é, sort 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.

Le projet Nutch a développé une implémentation expérimentale de MapReduce : (lien).