Vor einigen Jahren wurde MapReduce als Revolution der verteilten Programmierung gefeiert. Es gab auch Kritiker, aber im Großen und Ganzen gab es einen begeisterten Hype. Es wurde sogar patentiert! [1]
Der Name erinnert an map
und reduce
in der funktionalen Programmierung, aber wenn ich lese (Wikipedia)
Zuordnungsschritt: Der Masterknoten nimmt die Eingabe auf, unterteilt sie in kleinere Unterprobleme und verteilt sie auf Arbeitsknoten. Ein Worker-Knoten kann dies wiederum tun, was zu einer mehrstufigen Baumstruktur führt. Der Arbeitsknoten verarbeitet das kleinere Problem und gibt die Antwort an seinen Hauptknoten zurück.
Schritt reduzieren: Der Hauptknoten sammelt dann die Antworten auf alle Unterprobleme und kombiniert sie auf irgendeine Weise, um die Ausgabe zu bilden - die Antwort auf das Problem, das er ursprünglich zu lösen versuchte.
oder [2]
Interna von MAP: [...] MAP teilt den Eingabewert in Wörter auf. [...] MAP soll jedes gegebene Schlüssel / Wert-Paar der Eingabe mit potentiell vielen Schlüssel / Wert-Zwischenpaaren verknüpfen.
Interna von REDUCE: [...] [REDUCE] führt eine imperative Aggregation durch (sagen wir Reduktion): Nimm viele Werte und reduziere sie auf einen einzigen Wert.
Ich kann nicht anders als zu denken: das ist Teilen & Erobern (im Sinne von Mergesort), schlicht und einfach! Gibt es eine (konzeptionelle) Neuerung in MapReduce oder ist es nur eine Neuimplementierung alter Ideen, die in bestimmten Szenarien nützlich ist?
Antworten:
M / R ist nicht teilen und erobern. Die wiederholte Anwendung eines Algorithmus auf eine kleinere Teilmenge der vorherigen Eingabe ist nicht erforderlich. Es handelt sich um eine Pipeline (eine Funktion, die als Komposition einfacherer Funktionen angegeben wird), bei der Pipeline-Phasen die Zuordnung abwechseln und Operationen reduzieren. Unterschiedliche Stufen können unterschiedliche Operationen ausführen.
MapReduce beschreitet keine neuen Wege in der Berechnungstheorie - es zeigt keine neue Möglichkeit, ein Problem in einfachere Operationen zu zerlegen. Es zeigt, dass besonders einfachere Operationen für eine bestimmte Klasse von Problemen praktisch sind.
Der Beitrag des MapReduce-Papiers war
Einige der Kritiken fallen in diese Klassen:
quelle
BEARBEITEN (März 2014) Ich sollte sagen, dass ich seitdem mehr an Algorithmen für MapReduce-Berechnungsmodelle gearbeitet habe, und ich habe das Gefühl, dass ich übermäßig negativ war. Die Divide-Compress-Conquer-Technik, über die ich weiter unten spreche, ist überraschend vielseitig und kann die Grundlage für Algorithmen sein, die ich für nicht trivial und interessant halte.
Lassen Sie mich eine Antwort anbieten, die Mikes in Bezug auf die Vollständigkeit, aber vom Standpunkt des Modells der Berechnung / algorithmischen Theorie weit unterlegen ist.
Nun, ich denke, dies ist tatsächlich eine interessante Wendung beim Teilen und Erobern. Die Wendung besteht darin, dass Sie nach dem Teilen Teilproblemlösungen komprimieren müssen, damit ein einzelner Prozessor siegen kann. Dies scheint jedoch die einzige Technik zu sein, die wir bisher entwickelt haben. Bei Problemen mit spärlichen Diagrammen, wie z. B. spärlicher Konnektivität, schlägt dies fehl. Vergleichen Sie dies mit dem Streaming-Modell, das zu einer Fülle neuer Ideen führte, wie dem ausgeklügelten Sampling-Algorithmus von Flajolet und Martin, dem deterministischen Pairing-Algorithmus von Misra und Gries, der Kraft einfacher Skizziertechniken usw.
Als Programmierparadigma war Map Reduce sehr erfolgreich. Meine Kommentare betrachten map reduction als ein interessantes Rechenmodell. Gute theoretische Modelle sind etwas seltsam. Wenn sie der Realität zu genau folgen, sind sie unhandlich, aber was noch wichtiger ist: (um einen Begriff aus dem maschinellen Lernen zu übernehmen) Theoreme, die für zu spezifische Modelle bewiesen wurden, verallgemeinern nicht, dh gelten nicht für andere Modelle. Aus diesem Grund möchten wir so viele Details wie möglich abstrahieren und dennoch genug Zeit lassen, um uns herauszufordern, neue Algorithmen zu entwickeln. Schließlich sollten diese neuen Ideen den Weg zurück in die reale Welt finden. PRAM ist ein unrealistisches Modell, das zu interessanten Ideen führte, aber diese Ideen erwiesen sich als selten anwendbar für reale Parallelberechnungen. Auf der anderen Seite ist Streaming auch unrealistisch, aber es inspirierte algorithmische Ideen, die tatsächlich in der realen Welt eingesetzt werden. SehenCount-Min-Skizze . Skizziertechniken werden in der Tat auch in Systemen verwendet, die auf Kartenreduzierung basieren.
quelle
Ich stimme dir voll und ganz zu. Aus konzeptioneller Sicht gibt es nichts wirklich Neues: Map / Reduce war ursprünglich in Parallel Computing als Datenfluss-Programmiermodell bekannt. Aus praktischer Sicht hat Map / Reduce, wie es von Google und den nachfolgenden Open-Source-Implementierungen vorgeschlagen wurde, jedoch auch das Cloud-Computing befeuert und ist jetzt für sehr einfache parallele Zerlegungen und Verarbeitungen sehr beliebt. Natürlich ist es für nichts anderes gut geeignet, das komplexe Domänen- oder funktionale Zerlegungen erfordert.
quelle
Ich denke, Sie haben mit Ihrem Kommentar den Nagel auf den Kopf getroffen.
Es ist nicht wahr, dass in jeder funktionalen Sprache Maps parallelisiert werden können - die Sprache muss rein sein . (Ich glaube, Haskell ist die einzige rein funktionale Standardsprache. Lisp, OCaml und Scala sind alle nicht rein.)
Wir kennen die Vorteile von reinem Code bereits vor dem Timesharing, als Ingenieure ihre Prozessoren zum ersten Mal in die Pipeline einbauten. Wie kommt es also, dass niemand eine reine Sprache benutzt?
Es ist wirklich sehr, sehr, sehr schwer. Das Programmieren in einer reinen Sprache fühlt sich oft an, als würde man mit beiden Händen hinter dem Rücken programmieren.
Was MR tut, ist, die Reinheitsbeschränkung etwas zu lockern und einen Rahmen für andere Teile (wie die Shuffle-Phase) bereitzustellen, was es ziemlich einfach macht, verteilbaren Code für einen großen Teil von Problemen zu schreiben.
quelle
count
eine gemeinsam genutzte Variable in Ihrem Pseudocode ist. Das Übergeben des aktuellen Werts ando_something
sollte funktionieren. Können Sie ein Beispiel für einen "echten" D & C-Algorithmus (Mergesort, Quicksort, ...) nennen, bei dem die rekursiven Aufrufe voneinander abhängen (nachdem der Aufruf ausgegeben wurde)?