Quelle est la nouveauté de MapReduce?

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)

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.

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^\epsilon)$$o(\log n)$

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 suivante$O(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 ( $n$$O(\sqrt{n})$$\sqrt{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.

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.

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$