Quelle est la nouveauté de MapReduce?

68

Il y a quelques années, MapReduce a été salué comme une révolution de la programmation distribuée. Il y a eu aussi des critiques, mais dans l'ensemble, il y a eu un battage médiatique enthousiaste. Il a même été breveté! [1]

Le nom rappelle mapet reducedans la programmation fonctionnelle, mais quand je lis (Wikipedia)

Étape de mappage: le nœud maître prend les entrées, les divise en sous-problèmes plus petits et les distribue aux nœuds de travail. Un nœud travailleur peut effectuer cette opération à son tour, ce qui conduit à une arborescence à plusieurs niveaux. Le nœud travailleur traite le problème le moins grave et renvoie la réponse à son nœud maître.

Étape de réduction: le nœud maître collecte ensuite les réponses à tous les sous-problèmes et les combine d’une manière ou d’une autre pour former la sortie - la réponse au problème qu’il tentait à l’origine de résoudre.

ou [2]

Composants internes de MAP: [...] MAP divise la valeur d'entrée en mots. [...] MAP est destiné à associer chaque paire clé / valeur donnée de l'entrée à potentiellement de nombreuses paires clé / valeur intermédiaires.

Les composants internes de REDUCE: [...] [REDUCE] effectue une agrégation impérative (par exemple, réduction): prend plusieurs valeurs et les réduit à une seule valeur.

Je ne peux pas m'empêcher de penser: ceci est diviser et conquérir (au sens de Mergesort), tout simplement! Alors, y a-t-il une nouveauté (conceptuelle) dans MapReduce quelque part, ou s'agit-il simplement d'une nouvelle implémentation d'anciennes idées utiles dans certains scénarios?


  1. Brevet US 7.650.331: "Système et procédé pour un traitement de données efficace à grande échelle" (2010)
  2. Modèle de programmation MapReduce de Google - Revisité par R. Lämmel (2007)
Raphaël
la source
7
Il n'y a pas de nouveauté. Je n'en ferai pas une réponse, mais je suis fermement convaincu que rien de nouveau en calcul, ni même en calcul distribué, n'a été découvert par MapReduce.
EdA-Qa mort-ora-y
@Aryabhata: S'il y a nouveauté, cette question a une bonne réponse constructive. S'il n'y en a pas, on peut dire que peu de choses le prouvent (sauf peut-être réduire explicitement MapReduce à une technique plus ancienne), true. Mais si vous vous sentez de cette façon, votez!
Raphaël
@ edA-qamort-ora-y: Dans ce cas, nous devrions être en mesure d'exprimer MapReduce en termes plus anciens, ce qui serait une bonne réponse!
Raphaël
1
@ Raphaël, je suis d'accord, mais je ne suis pas sûr de pouvoir le faire. Cependant, je peux observer que, comme décrit ici (première citation), le tri par fusion utilise la méthode exacte de mappage / réduction. Il peut, en effet, être distribué avec aucune modification.
edA-qa mort-ora-y

Réponses:

47

Je ne peux pas m'empêcher de penser: c'est diviser et conquérir, tout simplement!

M / R n'est pas diviser et conquérir. Cela n'implique pas l'application répétée d'un algorithme à un sous-ensemble plus petit de l'entrée précédente. C'est un pipeline (une fonction spécifiée comme une composition de fonctions plus simples) où les étapes du pipeline alternent carte et opérations réduites. Différentes étapes peuvent effectuer différentes opérations.


Alors, y a-t-il une nouveauté (conceptuelle) dans MapReduce quelque part, ou s'agit-il simplement d'une nouvelle implémentation d'anciennes idées utiles dans certains scénarios?

MapReduce ne constitue pas une innovation dans la théorie du calcul - il ne montre pas une nouvelle façon de décomposer un problème en opérations plus simples. Cela montre que des opérations plus simples sont pratiques pour une classe de problèmes particulière.


La contribution du papier MapReduce a été

  1. évaluer un pipeline de deux opérateurs orthogonaux bien compris qui peuvent être répartis efficacement et tolérants aux fautes sur un problème particulier: la création d'un index de texte de gros corpus
  2. analyse comparative: réduisez ce problème pour indiquer la quantité de données transférée entre les nœuds et l'incidence des différences de latence entre les stades sur la latence globale
  3. montrer comment rendre le système tolérant aux pannes afin que les pannes de la machine pendant le calcul puissent être compensées automatiquement
  4. l'identification de choix et d'optimisations utiles et spécifiques

Certaines des critiques tombent dans ces classes:

  1. "Cartographier / réduire ne constitue pas une innovation en théorie du calcul." Vrai. La contribution du document original était que ces opérateurs bien compris avec un ensemble spécifique d’optimisations avaient été utilisés avec succès pour résoudre des problèmes réels plus facilement et avec une tolérance aux pannes que des solutions ponctuelles.
  2. "Ce calcul distribué ne se décompose pas facilement en carte et ne réduit pas les opérations". Assez bien, mais beaucoup le font.
  3. "Un pipeline de n étapes / réduction nécessite une latence proportionnelle au nombre d’étapes de réduction du pipeline avant que des résultats ne soient générés." Probablement vrai. L'opérateur de réduction doit recevoir toutes ses entrées avant de pouvoir produire une sortie complète.
  4. "Mappage / réduction est excessif pour ce cas d'utilisation." Peut être. Lorsque les ingénieurs trouvent un nouveau marteau brillant, ils ont tendance à rechercher tout ce qui ressemble à un clou. Cela ne signifie pas que le marteau n'est pas un outil bien conçu pour un certain créneau.
  5. "Mapper / réduire remplace peu une base de données relationnelle." Vrai. Si une base de données relationnelle s'adapte à votre ensemble de données, alors c'est merveilleux pour vous - vous avez des options.
Mike Samuel
la source
Eh bien, ils appellent le document original "séminal", alors je m'attends à quelque chose de nouveau. Je ne comprends pas votre premier paragraphe: il existe clairement de nombreuses techniques algorithmiques qui ne sont pas diviser pour régner . Si MapReduce n’est "que" une implémentation efficace de d & c pour un ensemble de problèmes spécifique, il n’ya certainement rien de fondamental ni de brevetable en algorithmique (imho). Cela ne veut pas dire que ce n'est pas un bon système. Notez que ma critique est moins liée à MapReduce elle-même (je suppose que c'est bien pour son utilité) qu'à sa réception par la communauté.
Raphaël
1
@Raphael, je ne pense pas que M / R soit une division et une conquête dans le sens où vous vous connectez. Cela n'implique pas l'application répétée d'un algorithme à un sous-ensemble plus petit de l'entrée d'origine. C'est un pipeline où les étapes du pipeline alternent carte et réduisent les opérations.
Mike Samuel
Hein, c'est vrai. J'ai interprété "Un nœud travailleur peut le faire à son tour, ce qui conduit à une arborescence à plusieurs niveaux". De cette façon, mais cela n'implique bien sûr pas que la même chose se passe à tous les niveaux.
Raphaël
1
@ ex0du5, je pense que vous pourriez le condamner pour des allégations qu'il ne fait pas. "De nombreux systèmes ont fourni des modèles de programmation restreints et ont utilisé ces restrictions pour paralléliser automatiquement les calculs. MapReduce peut être considéré comme une simplification et une distillation de certains de ces modèles, basés sur notre expérience des grands calculs du monde réel. ... En revanche, , la plupart des systèmes de traitement parallèle n’ont été mis en œuvre qu’à des échelles plus petites et laissent les détails de la gestion des pannes de la machine au programmeur. " Il cite des articles de Rabin et de Valiant à ce sujet, mais pas celui de Liskov.
Mike Samuel
1
@ ex0du5, assez bien. Je pensais que "" Mapper / Réduire ne constitue pas une innovation en théorie du calcul. "Vrai." était assez clair mais j'ai réécrit la liste des contributions.
Mike Samuel
21

EDIT (mars 2014) Je dois dire que depuis, j'ai davantage travaillé sur les algorithmes pour les modèles de calcul de type MapReduce, et j'ai l'impression d'être trop négatif. La technique Divide-Compress-Conquer dont je parle ci-dessous est étonnamment polyvalente et peut constituer la base d'algorithmes qui, à mon avis, sont non triviaux et intéressants.


Permettez-moi de donner une réponse qui sera bien inférieure à celle de Mike en termes d’exhaustivité, mais d’un point de vue modèle / théorie algorithmique.

Pourquoi il y a de l'excitation : MapReduce entrelace des calculs parallèles et séquentiels; chaque processeur a accès à un bloc non trivial (par exemple, ) de l'entrée et peut effectuer une opération non triviale sur celle-ci; Cela est très différent des modèles PRAM et semble être une idée intéressante qui pourrait conduire à de nouvelles techniques algorithmiques. En particulier, certains problèmes peuvent être résolus en peu de tours de calcul (de taille d'entrée constante), alors qu'aucun problème non trivial ne peut être résolu dans PRAM en un temps .o ( log n )O(nϵ)o(logn)

Pourquoi le modèle devient légèrement frustrant pour moi : la seule technique algorithmique qui semble fonctionner pour obtenir des algorithmes de tours et qui est quelque peu nouvelle est la suivanteO(1)

  • Partitionner l'instance de problème (souvent au hasard)
  • Effectuer des calculs sur chaque partition en parallèle et représenter le résultat du calcul de manière compacte
  • Combinez toutes les solutions de sous-projet représentées de manière compacte sur un seul processeur et terminez le calcul là-bas

Exemple très simple de technique: calculez la somme de nombres. Chaque processeur a du tableau et calcule la somme de cette partie. Ensuite, toutes les sommes peuvent être combinées sur un seul processeur pour calculer la somme totale. Un exercice légèrement plus intéressant consiste à calculer toutes les sommes de préfixes de cette façon (bien entendu, dans ce cas, la sortie doit être représentée de manière distribuée). Ou calculez un arbre couvrant d'un graphe dense.O ( nO(n)n

Maintenant, je pense qu’il s’agit en fait d’une solution intéressante à la division et à la conquête, la solution étant qu’après la phase de division, vous devez compresser les solutions de sous-problèmes afin qu’un seul processeur puisse conquérir. Cependant, cela semble vraiment être la seule technique que nous ayons mise au point jusqu'à présent. Il échoue lors de problèmes avec des graphes clairsemés, comme une connectivité clairsemée par exemple. Cela contraste avec le modèle de transmission en continu, qui a débouché sur une multitude de nouvelles idées, telles que l'algorithme d'échantillonnage ingénieux de Flajolet et Martin, l'algorithme d'appariement déterministe de Misra et Gries, la puissance de techniques de dessin simples, etc.

En tant que paradigme de programmation, la réduction de la carte a eu beaucoup de succès. Mes commentaires considèrent la carte réduire comme un modèle de calcul intéressant. Les bons modèles théoriques sont un peu bizarres. S'ils suivent la réalité de trop près, ils sont difficiles à manier, mais plus important encore (pour emprunter un terme à l'apprentissage automatique), les théorèmes prouvés pour les modèles trop spécifiques ne se généralisent pas, c'est-à-dire qu'ils ne sont pas valables dans d'autres modèles. C'est pourquoi nous souhaitons faire abstraction le plus de détails possible tout en laissant suffisamment de place pour nous mettre au défi de proposer de nouveaux algorithmes. Enfin, ces nouvelles idées devraient pouvoir retrouver leur chemin dans le monde réel. La PRAM est un modèle irréaliste qui a conduit à des idées intéressantes, mais ces idées se sont révélées être rarement applicables au calcul parallèle dans le monde réel. D'autre part, le streaming est également irréaliste, mais il a inspiré des idées algorithmiques qui sont réellement utilisées dans le monde réel. Voirsketch comte-min . Les techniques d'esquisse sont en fait également utilisées dans les systèmes basés sur la réduction de carte.

Sasho Nikolov
la source
On peut soutenir que M / R est un modèle plus réaliste (utile) que PRAM ou les flux. (
Du
"vous devez compresser les solutions de sous-problèmes de sorte qu'un seul processeur puisse vaincre" - Vous semblez dire que l'ensemble des problèmes pouvant être résolus par M / R est un sous-ensemble de ceux pour lesquels il existe une mémoire cache ou une mémoire cache traitable. des solutions inconscientes. Si cela est vrai, il me semble que cette affirmation s’applique également aux schémas de calcul les plus distribués.
Mike Samuel
1
@Xodarap qui pourrait bien être. Ici, j'utilise un point de vue purement théorique d'algorithmes: un modèle est utile s'il conduit à de nouvelles perspectives algorithmiques. De ce fait, la diffusion en continu n’est pas tout à fait réaliste, mais a conduit à de nombreuses nouvelles techniques qui sont réellement utiles dans la pratique. le problème est de savoir quelle est la bonne abstraction qui mène à une nouvelle pensée. les abstractions IRM actuelles ont un succès mitigé (mais un certain succès, je suppose)
Sasho Nikolov
1
@MikeSamuel le "besoin" dans cette phrase signifie que c'est ce que la technique nécessite pour fonctionner, mais pas que c'est la seule chose possible à faire. il n'y a pas de résultats théoriquement négatifs pour l'IRM que je connaisse. Ma plainte n’est pas que MR soit strictement moins puissant que CO. c’est que nous n’avons pas vu beaucoup de pensée algorithmique nouvelle inspirée par le modèle (ce qui est bien pour un système, mais décevant pour un modèle de calcul). de l'autre côté cache l'oubli lui-même est une idée étonnante imo
Sasho Nikolov
@SashoNikolov, compris. Merci de m'avoir expliqué.
Mike Samuel
6

Je suis entièrement d'accord avec vous. D'un point de vue conceptuel, il n'y a rien de vraiment nouveau: Map / Reduce était connu à l'origine dans Parallel Computing en tant que modèle de programmation de flux de données. Toutefois, d’un point de vue pratique, Map / Reduce, tel que proposé par Google et avec les implémentations à code source libre ultérieures, a également alimenté le Cloud Computing et est maintenant très populaire pour les décompositions et traitements parallèles très simples. Bien sûr, il ne convient pas à autre chose nécessitant des décompositions fonctionnelles ou dans des domaines complexes.

Massimo Cafaro
la source
3

Je pense que vous avez mis le doigt sur le clou avec votre commentaire.

Ce n'est pas vrai que dans n'importe quel langage fonctionnel, les cartes puissent être parallélisées - le langage doit être pur . (Je crois que Haskell est le seul langage purement fonctionnel à être vaguement traditionnel. Lisp, OCaml et Scala sont tous non purs.)

Nous connaissions les avantages du code pur depuis même avant la multipropriété, lorsque les ingénieurs ont développé leurs processeurs pour la première fois. Alors, comment se fait-il que personne n'utilise un langage pur?

C'est vraiment, vraiment, vraiment difficile. Programmer dans un langage pur ressemble souvent à de la programmation avec les deux mains attachées derrière le dos.

M. MR assouplit quelque peu la contrainte de pureté et fournit un cadre pour d’autres éléments (comme la phase de lecture aléatoire), ce qui facilite la rédaction de code distribuable pour une grande partie des problèmes.

Je pense que vous espériez une réponse du type "Cela prouve cet important sous-lemme de " et je ne pense pas que cela produise quoi que ce soit. Cela montre bien qu’une classe de problèmes réputés distributables sont "facilement" distribuables - que ce soit une "révolution" à votre avis dépend probablement du temps que vous avez passé à déboguer du code distribué dans un processus de pré-carte / réduction monde.NC=P

Xodarap
la source
Je ne connais pas bien MapReduce, mais votre présentation n’est pas différente de ce que je me souviens avoir présenté comme le cas idéal dans Parallelism 101 au siècle précédent.
Gilles 'SO- arrête d'être méchant'
@Gilles: Mon intention était de montrer que "diviser pour régner" = " distribuables Divide & Conquer." M / R est moins trivial, bien que sans doute encore non original.
Xodarap
En programmation fonctionnelle, toutes les cartes peuvent être mises en parallèle (avec embarras), alors pourquoi ne pas s'en tenir à ce paradigme? Je ne vois pas en quoi countune variable partagée est dans votre pseudo-code; tout simplement en passant sa valeur actuelle à do_somethingdevrait fonctionner. Pouvez-vous donner un exemple d'un "vrai" algorithme d & c (Mergesort, Quicksort, ...) pour lequel les appels récursifs dépendent les uns des autres (après que l'appel ait été émis)?
Raphaël
@Raphael: J'ai réécrit ma réponse pour mieux répondre à votre commentaire. Je peux ajouter un exemple de cas où la pureté est agaçante, si vous le souhaitez toujours.
Xodarap
1
@Raphael: Je conviens que ma réponse serait bien meilleure si je pouvais citer un papier montrant que le temps de programmation passe de X heure à Y en utilisant M / R, ou augmente de A à B en appliquant la pureté, mais je pense que tout ce que je peux Je salue furieusement les mains en insistant sur le fait que les différences ne sont pas négligeables.
Xodarap