Explication simple de MapReduce?

Relatif à ma question CouchDB .

Quelqu’un peut-il expliquer MapReduce dans des termes qu’un nombre pourrait comprendre?

Aller jusqu’aux bases de Map et Reduce.


Map est une fonction qui “transforme” des éléments d’une sorte de liste en un autre type d’élément et les replace dans le même type de liste.

supposons que j’ai une liste de nombres: [1,2,3] et je veux doubler tous les nombres, dans ce cas, la fonction “doubler tous les nombres” est la fonction x = x * 2. Et sans mappages, je pourrais écrire une simple boucle, disons

A = [1, 2, 3] foreach (item in A) A[item] = A[item] * 2 

et j’aurais A = [2, 4, 6] mais au lieu d’écrire des boucles, si j’ai une fonction de carte je pourrais écrire

 A = [1, 2, 3].Map(x => x * 2) 

le x => x * 2 est une fonction à exécuter contre les éléments de [1,2,3]. Ce qui se passe, c’est que le programme prend chaque élément, l’exécute (x => x * 2) en faisant en sorte que x soit égal à chaque élément et produise une liste des résultats.

 1 : 1 => 1 * 2 : 2 2 : 2 => 2 * 2 : 4 3 : 3 => 3 * 2 : 6 

donc après avoir exécuté la fonction de carte avec (x => x * 2), vous auriez [2, 4, 6].


Reduce est une fonction qui “collecte” les éléments dans les listes et effectue un calcul sur chacun d’eux, les réduisant ainsi à une valeur unique.

Trouver une sum ou trouver des moyennes sont toutes des instances d’une fonction de réduction. Comme si vous aviez une liste de numéros, disons [7, 8, 9] et que vous voulez les résumer, vous écririez une boucle comme celle-ci

 A = [7, 8, 9] sum = 0 foreach (item in A) sum = sum + A[item] 

Mais, si vous avez access à une fonction de réduction, vous pouvez l’écrire comme ceci

 A = [7, 8, 9] sum = A.reduce( 0, (x, y) => x + y ) 

Maintenant, il est un peu déroutant de savoir pourquoi il y a 2 arguments (0 et la fonction avec x et y) passés. Pour qu’une fonction de réduction soit utile, elle doit pouvoir prendre 2 éléments, calculer quelque chose et “réduire” ces 2 éléments à une seule valeur. Ainsi, le programme pourrait réduire chaque paire jusqu’à ce que nous ayons une seule valeur.

l’exécution suivrait:

 result = 0 7 : result = result + 7 = 0 + 7 = 7 8 : result = result + 8 = 7 + 8 = 15 9 : result = result + 9 = 15 + 9 = 24 

Mais vous ne voulez pas commencer avec des zéros tout le temps, donc le premier argument est là pour vous permettre de spécifier une valeur de départ spécifiquement la valeur dans le premier result = ligne.

disons que vous voulez résumer 2 listes, cela pourrait ressembler à ceci:

 A = [7, 8, 9] B = [1, 2, 3] sum = 0 sum = A.reduce( sum, (x, y) => x + y ) sum = B.reduce( sum, (x, y) => x + y ) 

ou une version que vous auriez plus de chance de trouver dans le monde réel:

 A = [7, 8, 9] B = [1, 2, 3] sum_func = (x, y) => x + y sum = A.reduce( B.reduce( 0, sum_func ), sum_func ) 

C’est une bonne chose dans un logiciel de firebase database car, avec le support de Map \ Reduce, vous pouvez travailler avec la firebase database sans avoir besoin de savoir comment les données sont stockées dans une firebase database.

Vous devez simplement être en mesure de dire au moteur ce que vous voulez en leur fournissant soit une fonction Map, soit une fonction Reduce, puis le moteur de firebase database peut contourner les données, appliquer votre fonction et obtenir les résultats que vous souhaitez. veulent tout sans que vous sachiez comment il boucle sur tous les disques.

Il existe des index, des clés, des jointures, des vues et de nombreux éléments qu’une même firebase database peut contenir. Ainsi, en vous protégeant de la manière dont les données sont réellement stockées, votre code est plus facile à écrire et à gérer.

Il en va de même pour la programmation parallèle, si vous spécifiez uniquement ce que vous voulez faire avec les données au lieu d’implémenter le code en boucle, l’infrastructure sous-jacente pourrait “paralléliser” et exécuter votre fonction dans une boucle parallèle simultanée.

MapReduce est une méthode permettant de traiter de vastes quantités de données en parallèle sans que le développeur ait à écrire d’autres codes que le mappeur et à réduire les fonctions.

La fonction de carte prend des données et génère un résultat, qui est contenu dans une barrière. Cette fonction peut s’exécuter en parallèle avec un grand nombre de la même tâche cartographique . Le jeu de données peut alors être réduit à une valeur scalaire.

Donc, si vous pensez à cela comme une requête SQL

 SELECT SUM(salary) FROM employees WHERE salary > 1000 GROUP by deptname 

Nous pouvons utiliser map pour obtenir notre sous-ensemble d’employés avec un salaire> 1000 dont la carte émet sur la barrière dans des compartiments de taille de groupe.

Réduire va additionner chacun de ces groupes. Vous donnant votre ensemble de résultats.

vient de cueillir cela de mes notes d’études universitaires du papier google

  1. Prendre un tas de données
  2. Effectuer une sorte de transformation qui convertit chaque donnée en un autre type de donnée
  3. Combinez ces nouvelles données dans des données encore plus simples

L’étape 2 est la carte. L’étape 3 est la réduction.

Par exemple,

  1. Prenez le temps entre deux impulsions sur une paire de compteurs de pression sur la route
  2. Mappez ces temps en vitesses en fonction de la distance des mètres
  3. Réduire ces vitesses à une vitesse moyenne

La raison pour laquelle MapReduce est divisé entre Map et Reduce est que différentes parties peuvent facilement être réalisées en parallèle. (Surtout si Réduire a certaines propriétés mathématiques.)

Pour une description complexe mais efficace de MapReduce, voir: le modèle de programmation MapReduce de Google – revisité (PDF) .

MAP et REDUCE sont d’anciennes fonctions Lisp à partir du moment où l’homme a tué les derniers dinosaures.

Imaginez que vous ayez une liste de villes avec des informations sur le nom, le nombre de personnes qui y vivent et la taille de la ville:

 (defparameter *cities* '((a :people 100000 :size 200) (b :people 200000 :size 300) (c :people 150000 :size 210))) 

Maintenant, vous voudrez peut-être trouver la ville avec la plus forte densité de population.

Nous commençons par créer une liste de noms de villes et de densités de population en utilisant MAP:

 (map 'list (lambda (city) (list (first city) (/ (getf (rest city) :people) (getf (rest city) :size)))) *cities*) => ((A 500) (B 2000/3) (C 5000/7)) 

En utilisant REDUCE, nous pouvons maintenant trouver la ville avec la plus grande densité de population.

 (reduce (lambda (ab) (if (> (second a) (second b)) a b)) '((A 500) (B 2000/3) (C 5000/7))) => (C 5000/7) 

En combinant les deux parties, on obtient le code suivant:

 (reduce (lambda (ab) (if (> (second a) (second b)) a b)) (map 'list (lambda (city) (list (first city) (/ (getf (rest city) :people) (getf (rest city) :size)))) *cities*)) 

Introduisons des fonctions:

 (defun density (city) (list (first city) (/ (getf (rest city) :people) (getf (rest city) :size)))) (defun max-density (ab) (if (> (second a) (second b)) a b)) 

Ensuite, nous pouvons écrire notre code MAP REDUCE en tant que:

 (reduce 'max-density (map 'list 'density *cities*)) => (C 5000/7) 

Il appelle MAP et REDUCE (évaluation est à l’envers), il est donc appelé carte réduire .

C’est l’explication la plus simple de MapReduce que j’ai trouvée.

entrer la description de l'image ici

Le moins que j’explique l’image, le plus simple rest.

Prenons l’exemple du papier de Google . Le but de MapReduce est d’être capable d’utiliser efficacement une charge d’unités de traitement travaillant en parallèle pour certains types d’algorithmes. L’exemple est le suivant: vous voulez extraire tous les mots et leur nombre dans un ensemble de documents.

Implémentation typique:

 for each document for each word in the document get the counter associated to the word for the document increment that counter end for end for 

Implémentation MapReduce:

 Map phase (input: document key, document) for each word in the document emit an event with the word as the key and the value "1" end for Reduce phase (input: key (a word), an iterator going through the emitted values) for each value in the iterator sum up the value in a counter end for 

Autour de cela, vous aurez un programme maître qui partitionnera l’ensemble des documents en “splits” qui seront traités en parallèle pour la phase Map. Les valeurs émises sont écrites par le travailleur dans un tampon spécifique au travailleur. Le programme maître délègue alors les autres travailleurs pour effectuer la phase Réduire dès qu’il est averti que le tampon est prêt à être traité.

Chaque résultat de travail (en tant que travailleur Map ou Reduce) est en fait un fichier stocké sur le système de fichiers dissortingbué (GFS pour Google) ou dans la firebase database dissortingbuée pour CouchDB.

Une introduction très facile , rapide et “pour les nuls” de MapReduce est disponible sur: http://www.marcolotz.com/?p=67

Publier une partie de son contenu:

Tout d’abord, pourquoi MapReduce a-t-il été créé à l’origine?

Fondamentalement, Google avait besoin d’une solution pour rendre les gros travaux de calcul facilement parallélisables, permettant ainsi de dissortingbuer les données sur un certain nombre de machines connectées via un réseau. En plus de cela, il a dû gérer la défaillance de la machine de manière transparente et gérer les problèmes d’équilibrage de la charge.

Que sont les véritables atouts de MapReduce?

On peut dire que MapReduce magic est basé sur l’application Map et Reduce. Je dois avouer que je ne suis absolument pas d’accord. La principale caractéristique qui a rendu MapReduce si populaire est sa capacité de parallélisation et de dissortingbution automatiques, associée à une interface simple. Ces facteurs, combinés à la gestion transparente des défaillances pour la plupart des erreurs, ont rendu ce cadre si populaire.

Un peu plus de profondeur sur le papier:

MapReduce a été initialement mentionné dans un article de Google (Dean & Ghemawat, 2004 – lien ici) en tant que solution pour effectuer des calculs dans le Big Data en utilisant une approche parallèle et des grappes de produits de base. Contrairement à Hadoop, écrit en Java, le framework de Google est écrit en C ++. Le document décrit comment un cadre parallèle se comporterait en utilisant les fonctions Map et Reduce de la functional programming sur des ensembles de données volumineux.

Dans cette solution, il y aurait deux étapes principales – appelées Map et Reduce -, avec une étape facultative entre le premier et le second – appelé Combine. L’étape Map est exécutée en premier, effectue des calculs dans la paire clé-valeur en entrée et génère une nouvelle valeur-clé de sortie. Il ne faut pas oublier que le format des paires clé-valeur en entrée ne doit pas nécessairement correspondre à la paire de format de sortie. L’étape Réduire assemblerait toutes les valeurs de la même clé, effectuant ainsi d’autres calculs. Par conséquent, cette dernière étape produirait des paires clé-valeur. L’une des applications les plus sortingviales de MapReduce consiste à implémenter le nombre de mots.

Le pseudo-code pour cette application est donné ci-dessous:

 map(Ssortingng key, Ssortingng value): // key: document name // value: document contents for each word w in value: EmitIntermediate(w, “1”); reduce(Ssortingng key, Iterator values): // key: a word // values: a list of counts int result = 0; for each v in values: result += ParseInt(v); Emit(AsSsortingng(result)); 

Comme on peut le constater, la carte lit tous les mots d’un enregistrement (dans ce cas, un enregistrement peut être une ligne) et émet le mot en tant que clé et le numéro 1 en tant que valeur. Plus tard, le groupe regroupera toutes les valeurs de la même clé. Donnons un exemple: imaginez que le mot “maison” apparaisse trois fois dans le dossier. L’entrée du réducteur serait [house, [1,1,1]]. Dans le réducteur, la sum de toutes les valeurs de la maison de clés et la sortie de la valeur de clé suivante: [house, [3]].

Voici une image de ce à quoi cela ressemblerait dans un framework MapReduce:

Image du document Google MapReduce original

Comme quelques exemples classiques d’applications MapReduce, on peut dire:

• Nombre de fréquences d’access aux URL

• Graphique de lien Web inversé

• Grep dissortingbué

• Vecteur de terme par hôte

Afin d’éviter un trafic réseau trop important, le document décrit comment le framework doit essayer de conserver la localité des données. Cela signifie qu’il doit toujours essayer de s’assurer qu’une machine exécutant des travaux Map a les données dans sa mémoire / son stockage local, évitant de les extraire du réseau. Dans le but de réduire le réseau à l’aide d’un mappeur, l’étape de combinaison facultative décrite précédemment est utilisée. Le Combiner effectue des calculs sur la sortie des mappeurs d’une machine donnée avant de l’envoyer aux Réducteurs – qui peuvent se trouver sur une autre machine.

Le document décrit également comment les éléments du framework doivent se comporter en cas de défaut. Ces éléments, dans le papier, sont appelés ouvrier et maître. Ils seront divisés en éléments plus spécifiques dans les implémentations open-source. Étant donné que Google n’a décrit que l’approche décrite dans le document et n’a pas publié son logiciel propriétaire, de nombreux frameworks open source ont été créés pour implémenter le modèle. Comme exemples, on peut dire Hadoop ou la fonctionnalité limitée de MapReduce dans MongoDB.

L’exécution doit prendre en charge les détails des programmeurs non experts, tels que le partitionnement des données d’entrée, la planification de l’exécution du programme sur le grand ensemble de machines, la gestion des pannes des machines (bien sûr) et la gestion des communications inter-machines. . Un utilisateur expérimenté peut régler ces parameters, comme la manière dont les données d’entrée seront partitionnées entre les travailleurs.

Concepts clés:

Tolérance aux pannes: elle doit tolérer les pannes de l’ordinateur avec grâce. Pour ce faire, le maître envoie les travailleurs périodiquement. Si le maître ne reçoit pas les réponses d’un employé donné dans un laps de temps défini, le maître définira le travail comme ayant échoué dans ce travailleur. Dans ce cas, toutes les tâches de carte effectuées par le travailleur défaillant sont jetées et sont confiées à un autre travailleur disponible. Il en va de même si le travailleur traite encore une carte ou une tâche réduite. Notez que si le travailleur a déjà terminé sa partie réduction, tous les calculs sont déjà terminés au moment où ils ont échoué et n’ont pas besoin d’être réinitialisés. En tant que principal point d’échec, si le maître échoue, tout le travail échoue. Pour cette raison, on peut définir des points de contrôle périodiques pour le maître afin de sauvegarder sa structure de données. Tous les calculs qui se produisent entre le dernier sharepoint contrôle et la défaillance principale sont perdus.

Localité: afin d’éviter le trafic réseau, le framework essaie de s’assurer que toutes les données en entrée sont localement disponibles sur les machines qui effectueront des calculs sur celles-ci. Dans la description d’origine, il utilise le système de fichiers Google (GFS) avec un facteur de réplication défini sur 3 et des tailles de bloc de 64 Mo. Cela signifie que le même bloc de 64 Mo (qui compose un fichier dans le système de fichiers) aura des copies identiques dans trois machines différentes. Le maître sait où sont les blocs et essaie de planifier les travaux de carte dans cette machine. En cas d’échec, le maître tente d’allouer une machine à proximité d’une réplique des données d’entrée des tâches (par exemple, une machine de travail dans le même rack de la machine de données).

Granularité des tâches: en supposant que chaque phase de la carte est divisée en M pièces et que chaque phase Réduite soit divisée en pièces R, l’idéal serait que M et R soient beaucoup plus volumineux que le nombre de machines ouvrières. Cela est dû au fait qu’un opérateur effectuant de nombreuses tâches différentes améliore l’équilibrage de charge dynamic. En outre, il augmente la vitesse de récupération en cas d’échec de l’opérateur (car les nombreuses tâches qu’il a accomplies peuvent être réparties sur toutes les autres machines).

Tâches de sauvegarde: Parfois, un employé de carte ou de réducteur peut se comporter beaucoup plus lentement que les autres dans le cluster. Cela peut contenir le temps de traitement total et le rendre égal au temps de traitement de cette seule machine lente. Le document original décrit une alternative appelée tâches de sauvegarde, planifiées par le maître lorsqu’une opération MapReduce est presque terminée. Ce sont des tâches planifiées par le maître des tâches en cours. Ainsi, l’opération MapReduce se termine lorsque la sauvegarde principale ou la sauvegarde est terminée.

Compteurs: Parfois, on peut vouloir compter les événements. Pour cette raison, les comptes ont été créés. Les valeurs de compteur dans chaque travailleur sont régulièrement transmises au maître. Le maître agrège ensuite (Yep. On dirait que les agrégateurs de Pregel proviennent de cet endroit) les valeurs de compteur d’une carte réussie et réduisent la tâche et les renvoient au code utilisateur lorsque l’opération MapReduce est terminée. Il existe également une valeur de compteur actuelle dans le statut maître, de sorte qu’un utilisateur qui regarde le processus peut suivre le comportement.

Eh bien, avec tous les concepts ci-dessus, Hadoop sera un jeu d’enfant pour vous. Si vous avez des questions sur l’article original de MapReduce ou sur tout autre sujet, merci de me le faire savoir.

Je ne veux pas paraître banal, mais cela m’a beaucoup aidé et c’est assez simple:

 cat input | map | reduce > output 

Si vous connaissez bien Python, voici l’explication la plus simple possible de MapReduce:

 In [2]: data = [1, 2, 3, 4, 5, 6] In [3]: mapped_result = map(lambda x: x*2, data) In [4]: mapped_result Out[4]: [2, 4, 6, 8, 10, 12] In [10]: final_result = reduce(lambda x, y: x+y, mapped_result) In [11]: final_result Out[11]: 42 

Voir comment chaque segment de données brutes a été traité individuellement, dans ce cas, multiplié par 2 (la partie carte de MapReduce). Basé sur le mapped_result , nous avons conclu que le résultat serait 42 (la partie réduire de MapReduce).

Une conclusion importante de cet exemple est le fait que chaque morceau de traitement ne dépend pas d’un autre morceau. Par exemple, si thread_1 mappe [1, 2, 3] et thread_2 mappe [4, 5, 6] , le résultat final des deux threads serait toujours [2, 4, 6, 8, 10, 12] mais nous ont réduit de moitié le temps de traitement pour cela. On peut dire la même chose pour l’opération de réduction et c’est l’essence même du fonctionnement de MapReduce en informatique parallèle.