Was ist die Neuheit in MapReduce?

68

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 mapund reducein 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?


  1. US-Patent 7,650,331: "System und Verfahren zur effizienten Datenverarbeitung in großem Maßstab" (2010)
  2. Googles MapReduce-Programmiermodell - Überarbeitet von R. Lämmel (2007)
Raphael
quelle
7
Es gibt keine Neuheit. Ich werde dies nicht als Antwort geben, aber ich bin der festen Überzeugung, dass MapReduce nichts Neues in Bezug auf die Berechnung oder sogar das verteilte Rechnen entdeckt hat.
edA-qa mort-ora-y
@Aryabhata: Wenn es eine Neuheit gibt, hat diese Frage eine gute, konstruktive Antwort. Wenn dies nicht der Fall ist, kann nur wenig gesagt werden, um dies zu beweisen (es sei denn, MapReduce wird explizit auf eine ältere Technik reduziert). Aber wenn Sie so denken, stimmen Sie auf jeden Fall ab!
Raphael
@ edA-qamort-ora-y: In diesem Fall sollten wir MapReduce in älteren Begriffen ausdrücken können, und das wäre eine gute Antwort!
Raphael
1
@Raphael, ich stimme zu, aber ich bin nicht sicher, ob ich das kann. Allerdings kann ich beobachten, dass, wie hier beschrieben (erstes Zitat), beim Sortieren die exakte Methode des Abbildens / Verkleinerns verwendet wird. Es kann tatsächlich ohne Veränderung verteilt werden.
edA-qa mort-ora-y

Antworten:

47

Ich kann nicht anders als zu denken: das ist Teilen und Erobern, schlicht und einfach!

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.


Gibt es eine (konzeptionelle) Neuerung in MapReduce oder ist es nur eine Neuimplementierung alter Ideen, die in bestimmten Szenarien nützlich ist?

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

  1. Auswerten einer Pipeline von zwei bekannten orthogonalen Operatoren, die effizient und fehlertolerant auf ein bestimmtes Problem verteilt werden können: Erstellen eines Textindex eines großen Korpus
  2. Durch das Benchmarking von Map-Reduce für dieses Problem wird gezeigt, wie viel Daten zwischen Knoten übertragen werden und wie sich Latenzunterschiede in Stufen auf die Gesamtlatenz auswirken
  3. Zeigen, wie das System fehlertolerant gemacht werden kann, damit Maschinenfehler während der Berechnung automatisch ausgeglichen werden können
  4. Identifizieren spezifisch nützlicher Implementierungsoptionen und -optimierungen

Einige der Kritiken fallen in diese Klassen:

  1. "Map / Reduce geht in der Berechnungstheorie keine neuen Wege." Wahr. Der Beitrag des Originalpapiers bestand darin, dass diese gut verstandenen Operatoren mit einer Reihe von Optimierungen erfolgreich eingesetzt wurden, um echte Probleme einfacher und fehlertoleranter zu lösen als Einzellösungen.
  2. Msgstr "Diese verteilte Berechnung lässt sich nicht leicht in Karten - und Reduzierungsoperationen zerlegen". Fair genug, aber viele tun es.
  3. "Eine Pipeline mit n Abbildungs- / Reduzierungsstufen erfordert eine Latenz, die proportional zur Anzahl der Reduzierungsstufen der Pipeline ist, bevor Ergebnisse erzeugt werden." Möglicherweise wahr. Der Reduktionsoperator muss alle Eingaben empfangen, bevor er eine vollständige Ausgabe erzeugen kann.
  4. "Zuordnen / Verkleinern ist für diesen Anwendungsfall zu viel." Vielleicht. Wenn Ingenieure einen glänzenden neuen Hammer finden, neigen sie dazu, nach etwas Ausschau zu halten, das wie ein Nagel aussieht. Das heißt nicht, dass der Hammer kein gutes Werkzeug für eine bestimmte Nische ist.
  5. "Map / Reduce ist ein schlechter Ersatz für eine relationale Datenbank." Wahr. Wenn sich eine relationale Datenbank auf Ihren Datensatz skalieren lässt, dann sind Sie hier genau richtig.
Mike Samuel
quelle
Nun, sie nennen das Originalpapier "bahnbrechend", also erwarte ich etwas Neues. Ich verstehe Ihren ersten Absatz nicht: Natürlich gibt es viele algorithmische Techniken, die sich nicht teilen und erobern lassen . Wenn MapReduce "nur" eine effiziente Implementierung von d & c für ein bestimmtes Problem ist, ist es in der Algorithmik (imho) mit Sicherheit nicht wegweisend oder patentwürdig. Das heißt nicht, dass es kein gutes System ist. Beachten Sie, dass MapReduce selbst weniger kritisch ist (ich denke, es ist gut für das, wofür es gemacht ist) als die Community.
Raphael
1
@Raphael, ich glaube nicht, dass M / R in dem Sinne geteilt und erobert wird, zu dem Sie einen Link haben. Die wiederholte Anwendung eines Algorithmus auf eine kleinere Teilmenge der ursprünglichen Eingabe ist nicht erforderlich. Es handelt sich um eine Pipeline, bei der Pipeline-Phasen die Zuordnung abwechseln und Vorgänge reduzieren.
Mike Samuel
Huh, stimmt. Ich interpretierte "Ein Worker-Knoten kann dies wiederum tun, was zu einer mehrstufigen Baumstruktur führt." auf diese Weise, aber das bedeutet natürlich nicht, dass auf jeder Ebene dasselbe passiert.
Raphael
1
@ ex0du5, ich denke, Sie verurteilen es möglicherweise für Behauptungen, die es nicht macht. "Viele Systeme haben eingeschränkte Programmiermodelle bereitgestellt und die Einschränkungen verwendet, um die Berechnung automatisch zu parallelisieren. ... MapReduce kann als Vereinfachung und Destillation einiger dieser Modelle angesehen werden, basierend auf unserer Erfahrung mit großen realen Berechnungen. ... Im Gegensatz dazu Die meisten Parallelverarbeitungssysteme wurden nur in kleineren Maßstäben implementiert und überlassen die Einzelheiten der Behandlung von Maschinenfehlern dem Programmierer. " Darin werden Arbeiten von Rabin und Valiant zitiert, nicht jedoch die von Liskov.
Mike Samuel
1
@ ex0du5, fair genug. Ich dachte, "" Map / Reduce betritt in der Theorie der Berechnung keine neuen Wege. "Richtig." war klar genug, aber ich habe die Liste der Beiträge umgeschrieben.
Mike Samuel
21

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.

O(nϵ)o(logn)

O(1)

  • Partitionieren Sie die Probleminstanz (oft nach dem Zufallsprinzip)
  • Führen Sie eine parallele Berechnung für jede Partition durch und stellen Sie das Ergebnis der Berechnung kompakt dar
  • Kombinieren Sie alle kompakt dargestellten Teilproblemlösungen auf einem Prozessor und beenden Sie die Berechnung dort

nO(n)n

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.

Sasho Nikolov
quelle
Vermutlich ist M / R ein realistischeres (nützliches) Modell als PRAM oder Streams. (Zumindest für einige einigermaßen große Probleme.)
Xodarap
"Sie müssen Subproblem-Lösungen komprimieren, damit ein einzelner Prozessor siegen kann" - Sie scheinen zu sagen, dass die Menge der Probleme, die von M / R gelöst werden können, eine Teilmenge derer ist, für die es tractable Cache-Aware oder Cache gibt Lösungen. Wenn das stimmt, dann scheint es mir, dass diese Aussage für die meisten verteilten Berechnungsschemata gleich gut gilt.
Mike Samuel
1
@Xodarap das kann gut sein. hier verwende ich eine rein algorithmische theoretische Sichtweise: Ein Modell ist nützlich, wenn es zu neuen algorithmischen Perspektiven führt. durch diese maßnahme ist streaming nicht ganz realistisch, sondern hat zu zahlreichen neuen techniken geführt, die in der praxis tatsächlich nützlich sind. Der Punkt ist, was ist die richtige Abstraktion, die zu neuem Denken führt. Aktuelle MR-Abstraktionen haben gemischten Erfolg (aber einige Erfolge, denke ich)
Sasho Nikolov
1
@MikeSamuel das "Bedürfnis" in diesem Satz bedeutet, dass dies das ist, was die Technik erfordert, um zu arbeiten, nicht dass es das einzig mögliche ist, was zu tun ist. Es gibt keine theoretisch negativen Ergebnisse für MR, die ich kenne. Meine Beschwerde ist nicht, dass MR strikt weniger leistungsfähig ist als CO. Es ist, dass wir nicht viel neues algorithmisches Denken gesehen haben, das von dem Modell inspiriert ist (was für ein System in Ordnung ist, für ein Rechenmodell jedoch enttäuschend). auf der anderen Seite Cache Vergesslichkeit selbst ist eine erstaunliche Idee imo
Sasho Nikolov
@SashoNikolov, verstanden. Danke fürs Erklären.
Mike Samuel
6

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.

Massimo Cafaro
quelle
3

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.

NC=P

Xodarap
quelle
Ich kenne MapReduce nicht, aber Ihre Darstellung unterscheidet sich nicht von der Darstellung, die ich im vorigen Jahrhundert in Parallelism 101 als Idealfall vorgestellt habe.
Gilles
@Gilles: Ich wollte nur zeigen, dass "dividieren & erobern"! = " Verteilbar dividieren & erobern". M / R ist weniger trivial, obwohl es wohl immer noch nicht originell ist.
Xodarap
In der funktionalen Programmierung können alle Maps (peinlich) parallelisiert werden. Warum also nicht an diesem Paradigma festhalten? Ich verstehe nicht, wie counteine gemeinsam genutzte Variable in Ihrem Pseudocode ist. Das Übergeben des aktuellen Werts an do_somethingsollte 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)?
Raphael
@Raphael: Ich habe meine Antwort umgeschrieben, um besser auf Ihren Kommentar zu antworten. Ich kann ein Beispiel hinzufügen, wenn Reinheit ärgerlich ist, wenn Sie immer noch wollen.
Xodarap,
1
@Raphael: Ich stimme zu, dass meine Antwort viel besser wäre, wenn ich ein Papier zitieren könnte, aus dem hervorgeht, dass die Programmierzeit mit M / R von X Stunden auf Y Stunden sinkt oder mit Reinheit von A auf B steigt, aber ich denke, alles, was ich kann Sie winken wütend mit den Händen und bestehen darauf, dass die Unterschiede nicht trivial sind.
Xodarap