Un programme MapReduce se compose d'une méthode Map () qui effectue le filtrage et le tri (comme le tri des étudiants par prénom en files d'attente, une file d'attente pour chaque nom) et une méthode Reduce () qui effectue une opération récapitulative Compter le nombre d'élèves dans chaque file d'attente, ce qui donne des fréquences de noms). Le «système MapReduce» (également appelé «infrastructure» ou «framework») orchestre le traitement en répartissant les serveurs répartis, en exécutant les différentes tâches en parallèle, en gérant toutes les communications et les transferts de données entre les différentes parties du système et en assurant la redondance Et la tolérance aux pannes.
Le modèle est inspiré par la carte et réduit les fonctions couramment utilisées dans la programmation fonctionnelle, bien que leur but dans le cadre de MapReduce n'est pas le même que dans leurs formes originales. Les principales contributions du cadre MapReduce ne sont pas les fonctions de carte et de réduction réelles (qui, par exemple, ressemblent aux opérations de l'interface de transmission de messages 1995 reduce and scatter ), mais l'évolutivité et la tolérance aux pannes Atteint pour une variété d'applications en optimisant le moteur d'exécution. En tant que tel, une implémentation unique de MapReduce ne sera généralement pas plus rapide qu'une implémentation traditionnelle (non-MapReduce); Les gains ne sont généralement observés que dans les implémentations multi-thread. L'utilisation de ce modèle est bénéfique seulement lorsque le fonctionnement optimisé de la distribution aléatoire (qui réduit le coût de communication réseau) et la tolérance aux pannes du framework MapReduce entrent en jeu. Optimiser les coûts de communication est essentiel à un bon algorithme MapReduce.
MapReduce est un framework pour traiter des problèmes parallélisables à travers de grands ensembles de données utilisant un grand nombre d'ordinateurs (nœuds), collectivement appelés cluster (si tous les noeuds sont sur le même réseau local et utilisent du matériel similaire) ou grid (si les noeuds sont Partagés entre les systèmes géographiquement et administrativement distribués, et utilisent un matériel plus hétérogène). Le traitement peut se faire sur des données stockées dans un système de fichiers (non structuré) ou dans une base de données (structurée). MapReduce peut profiter de la localité des données, en la traitant près de l'endroit où elle est stockée afin de réduire la distance sur laquelle il doit être transmis.
Étape "Map": Chaque noeud de travail applique la fonction "map ()" aux données locales et écrit la sortie dans un stockage temporaire. Un noeud maître assure que seule une copie des données d'entrée redondantes est traitée.
Étape "Shuffle": Les noeuds de travail redistribuent les données en fonction des touches de sortie (produites par la fonction "map ()"), de sorte que toutes les données appartenant à une clé soient situées sur le même noeud de travail.
Étape «Réduire»: Les nœuds de travail traitent maintenant chaque groupe de données de sortie, par clé, en parallèle.
Vue logique
Les fonctions Map et Reduce de MapReduce sont toutes deux définies en fonction des données structurées en paires (clés, valeurs). Map prend une paire de données avec un type dans un domaine de données et renvoie une liste de paires dans un domaine différent:Map(k1, v1) → liste (k2, v2)
La fonction Map est appliquée en parallèle à chaque paire (keyed by k1) dans le dataset d'entrée. Ceci produit une liste de paires (keyed by k2) pour chaque appel. Ensuite, le framework MapReduce collecte toutes les paires avec la même clé (k2) de toutes les listes et les regroupe en créant un groupe pour chaque clé.
La fonction de réduction est alors appliquée en parallèle à chaque groupe, qui à son tour produit une collection de valeurs dans le même domaine:
Reduce(k2, liste (v2)) → liste (v3)
Chaque appel Réduire produit typiquement une valeur v3 ou un retour vide, bien qu'un appel puisse renvoyer plus d'une valeur. Les retours de tous les appels sont recueillis en tant que liste de résultats souhaitée.
Ainsi, le framework MapReduce transforme une liste de paires (clés, valeurs) en une liste de valeurs. Ce comportement est différent de la combinaison typique de programmation fonctionnelle et de réduction, qui accepte une liste de valeurs arbitraires et renvoie une seule valeur qui combine toutes les valeurs renvoyées par la carte.
Il est nécessaire, mais pas suffisant, d'avoir des implémentations de la carte et de réduire les abstractions afin de mettre en œuvre MapReduce. Les implémentations distribuées de MapReduce nécessitent un moyen de connecter les processus exécutant les phases Map et Reduce. Il peut s'agir d'un système de fichiers distribué. D'autres options sont possibles, telles que le streaming direct des mappeurs aux réducteurs, ou pour les processeurs de cartographie de servir leurs résultats aux réducteurs qui les interroge.
0 commentaires: