Explication Simple de MapReduce?

Lié à mon CouchDB question.

Quelqu'un peut-il expliquer MapReduce dans des termes un numbnuts pourrait comprendre?

C'est le Meilleur 🙂 http://ksat.me/map-reduce-a-really-simple-introduction-kloudo/
Et voici mon point de vue à elle: MapReduce pour et avec les enfants.
J'aime beaucoup ton exemple: facile à comprendre et amusant pour toute la famille.
Joel Spolsky a une bonne explication pour les débutants - joelonsoftware.com/items/2006/08/01.html

InformationsquelleAutor reefnet_alex | 2008-08-26

178

Aller tout le chemin jusqu'à la base de la Carte et de Réduire les.

Carte est une fonction qui "transforme" les éléments dans une sorte de liste à un autre type de point et de les replacer dans le même genre de liste.

supposons que j'ai une liste de nombres: [1,2,3] et je veux doubler chaque numéro, dans ce cas, la fonction de "double chaque nombre" est la fonction x = x * 2. Et sans mappages, je pourrais écrire une boucle simple, disons
```
A = [1, 2, 3]
foreach (item in A) A[item] = A[item] * 2
```
et j'aurais Un = [2, 4, 6] mais au lieu d'écrire des boucles, si j'ai une carte de fonction je pourrais écrire
```
A = [1, 2, 3].Map(x => x * 2)
```
x => x * 2 est une fonction qui doit être exécutée contre les éléments dans [1,2,3]. Ce qui se passe est que le programme prend chaque élément, exécuter (x => x * 2) contre elle en faisant x est égal à chaque élément, et de produire une liste de résultats.
```
1 : 1 => 1 * 2 : 2  
2 : 2 => 2 * 2 : 4  
3 : 3 => 3 * 2 : 6  
```
ainsi, après l'exécution de la fonction map avec (x => x * 2), vous avez de l' [2, 4, 6].

Réduire est une fonction qui "rassemble" les éléments de listes et d'effectuer quelques calculs sur tous d'entre eux, donc de la réduire à une seule valeur.

Trouver une somme ou trouver les moyennes sont toutes les instances d'une fonction de réduction. Comme si vous avez une liste de nombres, de dire [7, 8, 9] et vous voulez résumer, vous devez écrire une boucle comme ceci
```
A = [7, 8, 9]
sum = 0
foreach (item in A) sum = sum + A[item]
```
Mais, si vous avez accès à une fonction de réduction, vous pouvez l'écrire comme ceci
```
A = [7, 8, 9]
sum = A.reduce( 0, (x, y) => x + y )
```
Maintenant c'est un peu déroutant pourquoi il y a 2 arguments (0 et la fonction avec x et y) passé. Pour une fonction de réduction pour être utile, elle doit être en mesure de prendre 2 éléments, de calculer, de quelque chose et de le "réduire" que les 2 éléments à une seule valeur, ainsi que le programme pourrait réduire chaque paire jusqu'à ce que nous avons qu'une seule valeur.

l'exécution suit:
```
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 de tous les temps, de sorte que le premier argument est là pour vous permettre de spécifier une valeur de semences spécifiquement la valeur de la première result = ligne.

dites que vous voulez une somme de 2 listes, il 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 chances 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 une DB logiciel, parce que, avec la Carte\Réduire le soutien que vous pouvez travailler avec la base de données sans avoir besoin de savoir comment les données sont stockées dans une base de données pour l'utiliser, c'est ce que un moteur DB est pour.

Vous avez juste besoin d'être en mesure de "dire" le moteur de ce que vous voulez, par la fourniture de avec soit une Carte ou d'une fonction de réduction et puis le moteur DB pourrait trouver son chemin autour de la data, appliquer votre fonction, et de venir avec les résultats que vous voulez sans vous savoir comment il passe en boucle sur tous les enregistrements.

Il existe des index et clés et les jointures et les points de vue et beaucoup de choses d'une base de données unique pourrait tenir, donc, par le blindage contre la façon dont les données sont stockées, votre code plus facile à écrire et à maintenir.

En va de même pour la programmation parallèle, si vous ne spécifiez ce que vous voulez faire avec les données au lieu de réellement mettre en œuvre le code de boucle, puis de l'infrastructure sous-jacente pourrait "paralléliser" et l'exécution de votre fonction dans un parallèle simultanée boucle pour vous.
- Ok, je comprends la carte et de réduire les prises individuellement. Mais quelles sont les applications que je pourrais avoir de la réduire? Dans un Google scénario ils l'utilisent par exemple pour l'addition d'une série de paramètres qui leur donnent le classement d'une page pour un mot clé donné?
- var total = orderes.Somme(o => o les.Prix unitaire * o.La quantité)
- Il existe de nombreuses utilisations lorsque vous abstraire de la notion de boucle. Dans Google scénario qu'ils ont probablement 1000s de machines pour le calcul de pagerank, liens et autres joyeusetés. Que font-ils quand ils ont besoin d'ajouter un peu plus de serveurs? La modification de chaque code de boucle est probablement pas une option. Donc, ce qu'ils ont fait c'est qu'ils écrivent leur code de calcul à l'encontre d'un "Réduire" la fonction de la place... Et quand la liste des serveurs de changements, seules les "Réduire" la fonction qui doit être changé. Got it?
- comment réduire le calcul de la moyenne? de ce que je vois je devine que tu ne pouvais pas? peut-être que la carte du numérateur et du dénominateur et de diviser à la fin d'additionner les deux à la fois?
- Je suis peut être un peu trop générique, là. En fait Average() est censé être glaçage sur le dessus de Sum(). Mais j'en ai parlé pour expliquer pourquoi la fonction n'est appelée "Réduire"... Une fonction moyenne est quelque chose qui prend une liste de nombres et réduit un seul numéro (qui est la moyenne).
InformationsquelleAutor chakrit
55

MapReduce est une méthode pour traiter des sommes énormes de données en parallèle, sans obliger le développeur à écrire aucun code autre que le mappeur et de réduire les fonctions.

La carte fonction prend les données et produit un résultat, qui est détenu dans une barrière. Cette fonction peut s'exécuter en parallèle avec un grand nombre de la même carte tâche. Le jeu de données peut ensuite être réduit une valeur scalaire.

Donc, si vous pensez à elle comme une instruction SQL
```
SELECT SUM(salary)
FROM employees
WHERE salary > 1000
GROUP by deptname
```
Nous pouvons utiliser carte pour obtenir notre sous-ensemble d'employés avec un salaire > 1000
la carte émet de la barrière de la taille du groupe des seaux.

Réduire fera le bilan de chacun de ces groupes. Vous donner vos résultats.

juste pincées cela à partir de mon université étude des notes de google de papier

InformationsquelleAutor Johnno Nolan
32
1. Prendre un tas de données
2. Effectuer une sorte de transformation qui convertit chaque donnée à un autre type de donnée
3. De combiner ces nouvelles données dans encore plus simple de données
L'étape 2 est de la Carte. L'étape 3 est de Réduire les.

Par exemple,
1. Le temps entre deux impulsions sur une paire de pression de mètres sur la route
2. Carte de ces moments dans la vitesse en fonction de la distance des compteurs
3. Réduire les vitesses à la vitesse moyenne
La raison MapReduce est divisé entre la Carte et de Réduire la raison en est que les différentes parties peuvent facilement être réalisés en parallèle. (Surtout si Réduire a certaines propriétés mathématiques.)

Pour un complexe, mais une bonne description de MapReduce, voir: Google du Modèle de Programmation MapReduce -- Revisité (PDF).
- Je dirais que pour l'étape 3, "combiner" au lieu de "transformer"
- Première fois, les trois réponses combiné est la MEILLEURE réponse. A lire en premier Nasser lien de l'article (théorique hi-niveau) Puis chakrit réponse (explication individuelle de réduire la carte) Maintenant Frank réponse (Ce qui est le célèbre MapReduce idiom.) Merci à vous trois . 🙂
InformationsquelleAutor Frank Krueger
20

MAP et reduce sont anciennes fonctions Lisp, à partir du moment où l'homme a tué le dernier des dinosaures.

Imaginez que vous avez 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 avons d'abord créer une liste de noms de ville et de la densité de la population à l'aide de la CARTE:
```
(map 'list
     (lambda (city)
         (list (first city)
               (/(getf (rest city) :people)
                  (getf (rest city) :size))))
     *cities*)

=>   ((A 500) (B 2000/3) (C 5000/7))
```
Aide à RÉDUIRE nous pouvons maintenant trouver de la ville avec la plus forte densité de population.
```
(reduce (lambda (a b)
          (if (> (second a) (second b))
             a
             b))
        '((A 500) (B 2000/3) (C 5000/7)))

 =>   (C 5000/7)
```
Combinant les deux parties nous obtenons le code suivant:
```
(reduce (lambda (a b)
          (if (> (second a) (second b))
             a
             b))
        (map 'list
             (lambda (city)
                (list (first city)
                   (/(getf (rest city) :people)
                      (getf (rest city) :size))))
             *cities*))
```
Nous allons introduire des fonctions:
```
(defun density (city)
   (list (first city)
         (/(getf (rest city) :people)
            (getf (rest city) :size))))

(defun max-density (a b)
   (if (> (second a) (second b))
          a
          b))
```
Alors nous pouvons écrire notre CARTE de RÉDUIRE code:
```
(reduce 'max-density
        (map 'list 'density *cities*))

 =>   (C 5000/7)
```
Il appelle MAP et REDUCE (évaluation est à l'intérieur), il est appelé carte de réduire.
- la fonction MAX qui existe déjà et fait quelque chose de légèrement différent. Aussi: on ne doit redéfinir MAX.
- max-density compare le deuxième élément du passé args, droit? Désolé pour le ridicule modifier.
- oui, c'est le deuxième élément et qui est seulement utile dans le contexte de cet exemple. Le code est également sur le but écrite dans un peu de style ancien Lisp avec des listes, comme les structures de données...
InformationsquelleAutor Rainer Joswig
15

Prenons l'exemple de la Google livre. L'objectif de MapReduce est d'être en mesure d'utiliser efficacement une charge de traitement des unités de travail dans parallels pour certains types d'algorithmes. L'exemple est le suivant: vous voulez extraire tous les mots et leur nombre dans un ensemble de documents.

Typique de mise en œuvre:
```
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
```
MapReduce mise en œuvre:
```
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 de master qui sera la partition de l'ensemble des documents dans les "splits", qui seront traitées en parallèle pour le plan de phase. Les émissions de valeurs sont écrites par le travailleur dans un tampon spécifique pour le travailleur. Le programme de master puis les délégués d'autres travailleurs pour effectuer la réduction de la phase dès qu'il est informé que le tampon est prêt à être manipulé.

Chaque travailleur de sortie (être une Carte ou d'un travailleur) est en fait un fichier stocké sur le système de fichiers distribués (GFS pour Google) ou dans la base de données distribuée pour CouchDB.

InformationsquelleAutor Damien B
10

Vraiment facile, rapide et "pour les nuls" introduction à MapReduce est disponible à: http://www.marcolotz.com/?p=67

Affichage de certains de ses contenus:

Tout d'abord, pourquoi était-MapReduce créé à l'origine?

Fondamentalement, Google avait besoin d'une solution pour faire de grandes calcul des emplois facilement parallélisables, permettant aux données d'être distribués dans un certain nombre de machines connectées par l'intermédiaire d'un réseau. A côté de cela, il a dû gérer la défaillance de la machine d'une manière transparente et gérer les questions d'équilibrage.

Quels sont MapReduce vrais atouts?

On peut dire que MapReduce magie est basée sur la Carte et de Réduire les fonctions de l'application. Je dois avouer compagnon, que je suis en total désaccord. La principale caractéristique qui fait MapReduce si populaire, c'est sa capacité de parallélisation automatique et de la distribution, combinée à la simplicité de l'interface. Ces facteur résumé avec la transparence de l'échec de la manipulation pour la plupart des erreurs de ce cadre si populaire.

Un peu plus en profondeur sur le papier:

MapReduce a été mentionné dans un Google document (Dean & Ghemawat, 2004 – lien ici) comme une solution pour faire des calculs dans le Big Data à l'aide d'une approche parallèle et des grappes d'ordinateurs. Contrairement à Hadoop, qui est écrit en Java, le Google du cadre est écrit en C++. Le document décrit la façon dont un cadre parallèle allait se comporter à l'aide de la Carte et de Réduire les fonctions de programmation fonctionnelle sur de grands ensembles de données.

Dans cette solution, il y aurait deux étapes principales – disant Map et reduce –, avec une étape facultative entre le premier et le deuxième appelé Combiner. La Carte de l'étape serait exécuté en premier, effectuer des calculs dans l'entrée de paires clé-valeur et de générer une nouvelle clé de sortie-valeur. Il faut garder à l'esprit que le format de l'entrée de paires clé-valeur ne doit pas nécessairement correspondre au format de sortie de la paire. L'Réduire étape assembler toutes les valeurs de la même clé, d'effectuer d'autres calculs sur elle. En conséquence, cette dernière étape serait sortie de paires clé-valeur. L'un des plus triviales applications MapReduce est de mettre en œuvre nombre de mots.

Le pseudo-code de cette application, est donnée ci-dessous:
```
map(String key, String value):

//key: document name
//value: document contents
for each word w in value:
EmitIntermediate(w, “1”);

reduce(String key, Iterator values):

//key: a word
//values: a list of counts
int result = 0;
for each v in values:
    result += ParseInt(v);
Emit(AsString(result));
```
Comme on peut le remarquer, la carte lit tous les mots dans un dossier (dans ce cas, un dossier peut être une ligne) et émet le mot clé et le numéro 1 en tant que valeur.
Plus tard, le réduire regroupera toutes les valeurs de la même clé. Donnons un exemple: imaginez que le mot "maison" apparaît trois fois dans le dossier. L'entrée du réducteur serait [de la maison,[1,1,1]]. Dans le réducteur, il sera la somme de toutes les valeurs pour la clé de la maison et donne en sortie la clé suivante de la valeur: [maison,[3]].

Voici une image de la façon dont cela pourrait ressembler à un MapReduce:

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

•Nombre d'URL de la fréquence d'accès

•Reverse Web-lien Graphique

•Distribué Grep

•Terme de Vecteur par hôte

Afin d'éviter trop de trafic réseau, le document décrit la façon dont le cadre doit essayer de conserver la localité des données. Cela signifie qu'il faut toujours essayer de faire en sorte qu'une machine en cours d'exécution de la Carte des emplois a données dans sa mémoire/stockage local, en évitant de chercher à partir du réseau. Visant à réduire le réseau par le biais de un mappeur, l'option combiner étape, décrite précédemment, est utilisé. Le Combineur effectue des calculs sur la sortie de la mappeurs dans une machine avant de l'envoyer à la Réducteurs – peut-être dans une autre machine.

Le document décrit également la manière dont les éléments du cadre doit comporter en cas de défauts. Ces éléments, dans le papier, sont appelés en tant que travailleur et le maître. Ils seront divisés en éléments plus spécifiques dans les implémentations open source.
Depuis que Google a seulement décrit l'approche adoptée dans le document et a pas publié de son logiciel propriétaire, de nombreux open-source cadres ont été créés afin de mettre en œuvre le modèle. Comme exemples on peut dire Hadoop ou le peu de MapReduce fonctionnalité dans MongoDB.

L'exécution doit prendre soin de non-programmeurs experts détails, comme le partitionnement de l'entrée de données, la programmation de l'exécution du programme à travers le grand nombre de machines, des machines de traitement d'échecs (de manière transparente, bien sûr) et de la gestion de l'inter-machine de la communication. Un utilisateur expérimenté peut se régler ces paramètres, comme la façon dont les données d'entrée seront partagés entre les travailleurs.

Concepts Clés:

•De Tolérance de panne: Il doit tolérer la défaillance de la machine normalement. Pour ce faire, le maître des requêtes de ping les travailleurs périodiquement. Si le maître ne reçoit pas de réponses à partir d'un travailleur dans un certain laps de temps, le maître va définir le travail comme échoué dans ce travailleur. Dans ce cas, tous les carte tâches accomplies par les défauts des travailleurs sont jetés et sont donnés à un autre travailleur. De même si le salarié est toujours en cours de traitement d'une carte ou d'une réduction de la tâche. Notez que si le travailleur a déjà terminé son de réduire la partie, tout le calcul était déjà terminée au moment où il a échoué et n'a pas besoin d'être réinitialisé. En tant que principal point de l'échec, si le maître échoue, tout le travail échoue. Pour cette raison, on peut définir des points de contrôle périodique pour le maître, afin de sauver sa structure de données. Tous les calculs qui se produisent entre le dernier point de contrôle et la défaillance du maître sont perdus.

•Localité: afin d'éviter le trafic réseau, le cadre vise à s'assurer que toutes les données d'entrée sont disponibles localement pour les machines qui vont effectuer des calculs sur eux. Dans la description originale, il utilise Google File System (GFS) avec facteur de réplication fixé à 3 et la taille des blocs de 64 MO. Cela signifie que le même bloc de 64 MO (qui composent un fichier dans le système de fichiers) aura des copies à l'identique dans les trois machines différentes. Le maître sait où sont les blocs et essayer de programmer la carte des emplois dans la machine. Si cela échoue, le maître tente d'allouer une machine près d'une réplique des tâches de saisie de données (c'est à dire un travailleur de la machine dans le même rack de données de la machine).

•Tâche de Granularité: en Supposant que chaque carte de phase est divisée en M pièces et que chacun de Réduire phase est divisée en R morceaux, l'idéal serait que M et R sont beaucoup plus grande que le nombre de travailleurs machines. Cela est dû au fait qu'un travailleur d'effectuer de nombreuses tâches différentes améliore l'équilibrage de charge dynamique. A côté de cela, il augmente la vitesse de récupération dans le cas des travailleurs de l'échec (car le nombre de carte tâches qu'il a accompli peut être réparti dans tous les autres machines).

•Tâches de sauvegarde: Parfois, une Carte ou un Réducteur travailleur peut avoir un comportement beaucoup plus lent que les autres dans le cluster. Cela peut tenir le temps total de traitement et de la rendre égale à la durée de traitement que seule machine lente. L'original du document décrit une alternative appelée Tâches de Sauvegarde, qui sont prévues par le maître lorsqu'un MapReduce opération est en cours d'achèvement. Ce sont des tâches qui sont planifiées par le Maître de l'avancement des tâches. Ainsi, le MapReduce opération est terminée lorsque le primaire ou la sauvegarde est terminée.

•Compteurs: Parfois on peut le désir de compter les occurrences des événements. Pour cette raison, les chiffres ont été créés. Les valeurs du compteur dans chaque travailleurs sont régulièrement propagées vers le maître. Le capitaine des agrégats (Pej. Ressemble Pregel agrégateurs est venu de ce lieu ) les valeurs de compteur de réussite d'une carte et de réduire la tâche et de le retourner à l'utilisateur du code lors de la MapReduce opération est terminée. Il y a également une valeur actuelle du compteur disponible dans la base de statut, de sorte qu'un homme de regarder le processus peut garder une trace de la façon dont il se comporte.

Bien, je suppose que tous les concepts ci-dessus, Hadoop sera un morceau de gâteau pour vous. Si vous avez une question à propos de l'origine MapReduce l'article ou quoi que ce soit lié, s'il vous plaît laissez-moi savoir.

InformationsquelleAutor Prometheus
4

Je ne veux pas paraître banal, mais cela m'a aidé beaucoup, et c'est assez simple:
```
cat input | map | reduce > output
```
InformationsquelleAutor Mike Dewar
4

Si vous êtes familier avec le langage Python, voici la plus simple explication 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 sont traitées individuellement, dans ce cas, multiplié par 2 (le carte partie de MapReduce). Basé sur le mapped_result, nous avons conclu que le résultat serait 42 (le réduire partie de MapReduce).

Une conclusion importante de cet exemple est le fait que chaque bloc de traitement ne dépend pas d'un autre bloc. Par exemple, si thread_1 cartes [1, 2, 3], et thread_2 cartes [4, 5, 6], le résultat final des deux fils serait encore [2, 4, 6, 8, 10, 12] mais nous avons réduit de moitié le temps de traitement pour cela. La même chose peut être dit pour la réduire son fonctionnement et qui est l'essence même de la façon dont MapReduce travaille dans l'informatique parallèle.

InformationsquelleAutor Rafay

Vous devez vous connecter pour publier un commentaire.