Welche Probleme löst MapReduce?

61

Ich habe eine Weile über MapReduce gelesen - aber was ich nicht verstehe, ist, wie jemand eine Entscheidung treffen würde, MapReduce zu verwenden (oder nicht zu verwenden).

Ich meine, was sind die Problemmuster, die signalisieren, dass MapReduce verwendet werden könnte.

Baumkodierer
quelle

Antworten:

47

Grundsätzlich sind die Probleme riesig, aber nicht schwer. Ein reisender Verkäufer hängt entscheidend von der Entfernung zwischen einem bestimmten Städtepaar ab. Die Teilergebnisse können also nicht rekombiniert werden, obwohl sie in viele Teile zerlegt werden können, so dass die global optimale Lösung entsteht (na ja, wahrscheinlich nicht; wenn Sie einen Weg kennen, Bitte beantragen Sie jetzt Ihre Fields-Medaille.

Andererseits ist das Zählen der Häufigkeiten von Wörtern in einem riesigen Korpus trivial partitionierbar und trivial rekombinierbar (Sie addieren einfach die für die Segmente des Korpus berechneten Vektoren), sodass die Kartenreduzierung die naheliegende Lösung ist.

In der Praxis sind in der Regel mehr Probleme leicht zu rekombinieren als nicht, sodass die Entscheidung, ob eine Aufgabe parallelisiert werden soll oder nicht, mehr damit zu tun hat, wie umfangreich die Aufgabe ist und weniger damit, wie schwierig sie ist.

Kilian Foth
quelle
Wenn Sie eine ungefähre Antwort auf das Problem des Handlungsreisenden suchen, können Sie die Antwort mit dem Mindestabstand zum Zusammenführen einfach auswählen.
Dan_waterworth
Ich habe Ihre Erklärung nicht verstanden, warum MapReduce nicht für Travelling Salesman geeignet ist.
9
Es ist geeignet, um eine Lösung zu finden, vielleicht sogar eine sehr gute. Teilen Sie einfach die Menge der Städte in kleinere Mengen auf, z. B. 1-10, 11-20, 21-30 10-> 11, 20-> 21 und 30-> 1. Das Problem besteht jedoch darin, die optimale Route zu finden , und es gibt keine Garantie dafür, dass die optimale Route auf diese Weise aufgeteilt wird - möglicherweise beginnt sie tatsächlich mit 1-> 25! Mit anderen Worten, um die richtige Partitionierung zu finden, müssen Sie die Lösung im Grunde schon kennen! Das ist der Grund, warum das Finden der optimalen Route nicht für den Trick des Aufteilens und Zusammensetzens anfällig ist
Kilian Foth,
2
@KilianFoth, Sie können eine umfassende Suche durchführen, indem Sie den Lösungsraum in beginnend bei 1, beginnend bei 2, ... aufteilen und dann das Problem an jedem dieser Knoten lösen, indem Sie den Raum auf dieselbe Weise erneut partitionieren. Beim Zusammenführen an der Wurzel wird einfach die kürzeste Route gefunden. Beim Zusammenführen an einem anderen Zweig wird die kürzeste "untergeordnete Route + Route von Zweig zu Kind" gefunden.
Dan_waterworth
3
Wenn Sie die Lösung haben, denken Sie daran, dass Sie nur für Ihre Fields-Medaille berechtigt sind, wenn Sie unter 40 sind.
Francesco
28

Kann das Problem mit Distributed Computing effizient gelöst werden?

Wenn die Antwort auf diese Frage "Ja" lautet, liegt ein Kandidatenproblem für MapReduce vor. Dies liegt daran, dass sich das Problemmuster in kleinere isolierte Probleme aufteilen lässt.

Ihre Aufgabe: Analysieren Sie dieses Buch

Ein Beispiel kann dies gut veranschaulichen. Sie haben ein großes Dokument ( Moby Dick von Herman Melville ) und Ihre Aufgabe ist es, eine Häufigkeitsanalyse aller darin verwendeten Wörter durchzuführen.

Der sequentielle Ansatz

Sie können dies der Reihe nach tun, indem Sie Ihre schnellste Maschine (Sie haben viel herumliegen) und den Text von Anfang bis Ende durchgehen und jedes Mal eine Hash-Karte von jedem gefundenen Wort (dem Schlüssel) erstellen und die Häufigkeit (den Wert) erhöhen Sie analysieren ein Wort. Einfach, unkompliziert und langsam.

Der MapReduce-Ansatz

Wenn Sie dies aus einer anderen Perspektive betrachten, stellen Sie fest, dass all diese Ersatzmaschinen herumliegen und Sie diese Aufgabe in Teile aufteilen können. Geben Sie jeder Maschine einen 1-MB-Textblock, der in eine Hash-Map geparst werden soll, und fassen Sie dann alle Hash-Maps zu einem einzigen Ergebnis zusammen. Dies ist eine mehrschichtige MapReduce-Lösung.

Der Prozess des Lesens einer Textzeile und des Sammelns der Wörter ist die Kartenphase (Sie erstellen eine einfache Karte, die die Wörter in der Zeile mit der Häufigkeit 1,2,3 usw. darstellt). Die Reduzierungsphase ist dann, wenn jede Maschine ihre Zeile sortiert Karten in eine einzelne aggregierte Karte.

Die Gesamtlösung stammt aus einer weiteren Reduzierungsphase, in der alle aggregierten Karten (wieder dieses Wort) zu einer endgültigen Karte zusammengefasst werden. Etwas komplexer, massiv parallel und schnell.

Zusammenfassung

Zusammenfassend lässt sich sagen, dass Sie ein Kandidatenproblem für MapReduce haben, wenn Ihr Problem durch Schlüssel, Werte und Aggregatoperationen für diese Werte isoliert dargestellt werden kann.

Gary Rowe
quelle
2
Meh; Das ist eine Vereinfachung. Bei MapReduce geht es darum, die Daten zu partitionieren, eine Funktion parallel auf die Teile anzuwenden, ohne dass eine Kommunikation zwischen den Analysatoren stattfindet , und anschließend eine andere Funktion anzuwenden, um die Bits zu kombinieren. Nicht alle verteilbaren Probleme passen zu diesem Modell.
Donal Fellows
2
Fairer Punkt - aber es dient als nützliche Einführung und ermöglicht es jemandem, sein Problem zu "boxen".
Gary Rowe
13

Das MapReduce-Muster stammt aus der Welt der funktionalen Programmierung. Es ist ein Prozess, um etwas, das als Katamorphismus bezeichnet wird, parallel auf eine Datenstruktur anzuwenden. Funktionale Programmierer verwenden Katamorphismen für so ziemlich jede einfache Transformation oder Zusammenfassung.

Angenommen, Ihre Daten sind ein Baum, ist der entscheidende Faktor, ob Sie einen Wert für einen Knoten berechnen können, indem Sie nur die in diesem Knoten enthaltenen Daten und die berechneten Werte für seine untergeordneten Knoten verwenden.

Zum Beispiel können Sie die Größe eines Baumes unter Verwendung eines Katamorphismus berechnen. Sie würden die Summe der berechneten Werte für alle Kinder plus eins berechnen.

dan_waterworth
quelle
Gute Antwort, ich bin mir nicht sicher, ob @good_computer auf das von Google entwickelte MapReduce-Framework verweist. Und ich weiß nicht, ob MapReduce (wieder das Google-Framework) für etwas anderes gilt als für Typen, die isomorph zu Listen sind.
Scarfridge
1
@scarfridge, ich ging davon aus, dass sich das OP nicht auf das Google-spezifische Framework bezieht. Ich habe den Wikipedia-Artikel vor dem Posten daraufhin überprüft, ob er nur für Listen oder für Bäume im Allgemeinen verwendet wird. en.wikipedia.org/wiki/MapReduce#Overview
dan_waterworth
2
Wenn es nur MapFold heißen würde ; das wäre so viel einfacher zu verstehen.
Aditya
6

Diese WPI - Anwendungen von Map Reduce (ppt) könnten Sie interessieren. Es werden verschiedene MR-Anwendungen besprochen. Als einer der besprochenen Fälle wird gezeigt, wie die New York Times mithilfe von 100 EC2-Instanzen und 24 Stunden 4 TB gescannter Artikel in 1,5 TB PDF-Dokumente konvertieren konnte.

Eine weitere Reihe von Beispielen, bei denen MR zur Beschleunigung der Leistung beigetragen hat, ist: Aster - SQL Map Reduce zeigt einige Fallstudien der SQL-Map Reduce-Technologie, einschließlich Betrugserkennung, Transformationen und anderer.

Keine Chance
quelle
1
Wenn Sie ein PDF pro gescanntem Artikel erhalten, verwenden Sie nur eine verteilte Karte, nicht MapReduce. In Map-Reduce wenden Sie eine Reduzierung auf die Ergebnisse der Map an, um ein einzelnes Ergebnis zu erhalten.
Pete Kirkham
6

Map / Reduce ist eine bestimmte Form eines bestimmten Algorithmus. Sie verwenden es, um einen riesigen Datensatz in einen anderen Datensatz umzuwandeln. (Das Ergebnis-Dataset kann sehr groß sein oder auch nicht.) Wenn Sie keine statische Datenausgabe als Ergebnis einer statischen Dateneingabe wünschen, ist Map / Reduce nicht geeignet. Map / Reduce kann Ihnen leicht sagen, wie viele John Smiths im Manhattan-Telefonbuch vorhanden sind, eignet sich jedoch nicht zum Erstellen eines Webservers.

Die Funktionsweise von Map / Reduce ist:

  • Map nimmt Schlüsselpaare (k1) und Werte (v1) und ordnet sie einem neuen Satz von Schlüsseln (k2) und Werten (v2) zu.
  • Reduce nimmt alle v2-Werte mit demselben k2-Schlüssel und erzeugt einen neuen Wert (v3).

Das Ergebnis ist, dass eine Liste von (k1, v1) Paaren in eine Liste von (v3) s transformiert wird. (Natürlich kann der Wert "v3" eine Zusammensetzung sein, die k2 enthält, was definiert werden könnte, um gleich k1 zu sein.)

Also benutzt du es:

  1. Wenn Sie so viele Daten haben, um damit zu beginnen, würde es zu lange dauern, alle nacheinander über einen oder zwei Server zu laufen, und

  2. Sie können sich die Ausgabedaten als Liste von Werten oder Schlüsselwertpaaren vorstellen (im Allgemeinen nicht zu schwer, wenn Sie sich daran erinnern, dass "Schlüssel" nur "eindeutige Bezeichnung" bedeutet)

  3. Unabhängig von der Beziehung können Sie sicher sein, dass sich die einzelnen Eingabedaten nur auf den Ausgabewert eines Ausgabeschlüssels auswirken.

Wenn Ihre Daten alle nacheinander von einem einzigen Server verarbeitet werden können, verwenden Sie einen einzigen Server, da dies das vorherrschende Computerparadigma ist (die Server, für die Programmierer ausgebildet sind).

Die Kartenbühne muss alle Eingabedaten nach Ausgabeschlüssel aufteilen. Es muss nicht den Ausgabewert erzeugen, der dem Ausgabeschlüssel zugeordnet ist (dies wird von der Reduktionsstufe durchgeführt), sondern es muss jedes Eingabeschlüsselwertpaar eindeutig zugewiesen werden, um zu höchstens einem Ausgabeschlüsselwert beizutragen. Wenn die Daten zu stark miteinander verknüpft sind, kann Map Reduce das Problem möglicherweise nicht lösen. Auf der anderen Seite kann es sein, dass Sie mehrere Runden der Karte / Verkleinerung verwenden müssen.

Wenn Sie nicht herausfinden können, wie Sie Ihre Datenumwandlung in eine Karte / Reduzierung umwandeln, ist dies natürlich keine Lösung.

Es ist eine echte Kunst herauszufinden, ob ein Problem in etwas zerlegt werden kann, das Map / Reduce handhaben kann. Beispielsweise befinden sich v1 und v2 möglicherweise überhaupt nicht in den Eingabe- oder Ausgabedatensätzen. Wenn Sie nur einzelne Elemente in den Eingabedaten zählen möchten, ist k1 = k2 = ein Element und v1 = v2 = 1 oder 0 oder wirklich alles. Reduce ergibt nur v3 als die Summe der Anzahl von k2, die es gegeben hat.

Es ist daher schwer zu sagen, dass eine Datentransformation mit Map / Reduce nicht durchgeführt werden kann, aber das oben Gesagte gibt Ihnen einige Wegweiser.

Alter Pro
quelle
3

MapReduce bearbeitet jedes Problem, das auf einer bestimmten Abstraktionsebene aus genau zwei Funktionen besteht. Die erste Funktion wird auf jedes Element in der Eingabemenge angewendet, und die zweite Funktion aggregiert die Ergebnisse.

Wenn Sie also (1) Ergebnisse von (n) Eingaben erhalten möchten und alle Eingaben mit der Funktion (1) überprüft / verwendet werden können, können Sie MapReduce verwenden. Auch dies erfolgt auf einer bestimmten Abstraktionsebene. Die (1) -Funktion kann eine Gruppierungsfunktion sein, die die Eingabe überprüft und entscheidet, welche von mehreren anderen Funktionen verwendet wird.

Dies ist nützlich, wenn Sie nicht im Voraus wissen, wie viel Input Sie haben werden, wenn Sie diskrete "Arbeitseinheiten" aufteilen müssen oder wenn Sie möchten, dass eine einzige Rückgabe das gesamte Ergebnis darstellt (IE, das fünftausend Einheitentests durchführt) , und wenn weniger als x% fehlschlagen, wird der Erfolg zurückgegeben).

Spencer Rathbun
quelle
3

Die meisten Antworten hier scheinen eine Variation zu sein, die erklärt, was Map Reduce macht, was gültig ist. Aber die Frage zu beantworten, welches Muster signalisieren würde, wo Sie die Kartenreduzierung verwenden könnten, wird dadurch nicht wirklich angesprochen.

Wenn die naive, nicht funktionierende Implementierung des betrachteten Problems darin besteht, eine Schleife über etwas zu erstellen und dann etwas außerhalb der Schleife mit einem Zustand innerhalb der Schleife zu aktualisieren, besteht die Möglichkeit, dass Sie etwas haben, das sich gut zuordnen lässt. Insbesondere, wenn Sie die Aktualisierung des zentralen Zustands auf eine Funktion verallgemeinern können, die mit nur zwei Parametern arbeitet und gewährleisten kann, dass diese Funktion kommutativ und assoziativ ist.

Der Grund, warum Sie Map Reduce verwenden möchten, ist zweifach: 1) Es ist möglicherweise ein bisschen übersichtlicher und einfacher zu testen und zu debuggen, wenn Sie die Map aufteilen und Funktionen reduzieren. 2) Funktionen zur Kartenreduzierung sind zustandslos und können gleichzeitig ausgeführt werden. Dies beschleunigt die Ausführung, wenn mehrere CPUs zur Verfügung stehen und so etwas wie Hadoop oder Spark, die davon Gebrauch machen, um Dinge in einem Cluster auszuführen.

Das ist schön, wenn Sie eine Menge Dinge durchlaufen, aber Ihre Laufleistung kann variieren, je nachdem, wie komplex Ihre Karte / Verkleinerung ist. Es ist durchaus üblich, eine sequentielle Kette oder einen Baum von Kartenreduktionen zu haben, bei denen am Ende der Kette immer noch ein komplexer Reduktionsschritt vorliegt. Beispielsweise ist es schwierig, viele Grafikalgorithmen mit nur einer Kartenverkleinerung effizient zu skalieren.

Das einfachste Beispiel, das gut mit Kartenreduzierung funktioniert, ist das Zählen von Dingen, was eine sehr billige Reduzierung ist. Aus diesem Grund ist die Wortanzahl ein häufig verwendetes Beispiel für die Kartenreduzierung. In diesem Fall können Sie eine lineare Skalierbarkeit der Leistung erwarten: Jede hinzugefügte CPU beschleunigt diese.

Jilles van Gurp
quelle
2

Wenn Sie viel funktionales Programmieren ausführen, stoßen Sie auf Situationen, die eine allgemeine Karte erfordern und reduzieren. Sie sehen sie wahrscheinlich sogar in der Imperativprogrammierung, aber Sie erkennen sie nicht hinter der Maske der Schleifen und Akkumulatoren.

Als ein Beispiel für eines, das mir kürzlich einfiel, habe ich in Haskell an einem Parser gearbeitet. Um meinen Parser zu testen, pumpe ich eine Liste von Zeichenfolgenfragmenten durch den Parser und möchte dann eine einzelne Zeichenfolge erhalten, die ich aus meinen Ergebnissen ausgeben kann, um zu sehen, ob sie richtig analysiert wurde. Das sieht also so aus:

--my initial set of test data, a list
tests = ["string1", "string2", "string3", ...]

--Map Step: turn strings into parsed results
--note the type, which demonstrates the map
applyParser :: [String] -> [Token]
--The actual function
applyParser input = map parser input

--Second map, turn tokens into output
showTokens :: [Token] -> [String]
showTokens t = map show t

--Reduce step, concat the results
combineResults :: [String] -> String
--In haskell, reduce is the foldl function, which takes an operation to fold with, a starting element, and a list to fold on
combineResults strings = foldl concat "" strings

--Finished program
testParser = print (combineResults(showTokens(applyParser tests)))

Das ist natürlich nur pädagogisch. Mein eigentlicher Code sieht ein bisschen anders, und verwendet mehr internen Funktionen (wie fold concatnicht erforderlich ist , da Haskell enthält bereits unlinesdas tut [String]->String). Mein Hauptpunkt war, dass ich nicht damit gerechnet habe, eine Karte / Verkleinerung zu verwenden, als ich anfing, sie war nur auf meine Bedürfnisse ausgerichtet. Ich wollte ein paar Sachen mit Listen machen und dann meine Liste in ein einzelnes Ausgabeelement verwandeln. Die Verwendung von Map / Reduce ist auf natürliche Weise entstanden.

Die Verarbeitung von Zeichenfolgen (wie das Parsen) ist eine sehr offensichtliche Verwendung der Kartenverkleinerung. Bei der Zuordnung werden verschiedene Transformationen auf den Eingabetext angewendet und der Ergebnistext als Ausgabe wieder zusammengesetzt. Ebenso könnte ein Compiler ähnlich sein und Falten verwenden, um einen Strom von abstrakten Syntaxbaumelementen in eine bessere Form zu verwandeln (Optimieren).

CodexArcanum
quelle
1

Ist es parallelisierbar?

Jedes parallelisierbare Problem ist im Wesentlichen map and fold. Umgekehrt ist der Kartenschritt von Natur aus parallelisierbar (und der Faltschritt kann abhängig von der Struktur, über die er gefaltet wird, eine bidirektionale Eigenschaft sein).

Peter Taylor
quelle
3
Dies ist nur bei peinlich parallelen Problemen der Fall . Es gibt viele Probleme, die in hohem Maße parallelisierbar sind, die jedoch genügend Interaktion zwischen Elementen enthalten, so dass ein einfaches MapReduce nicht effizient wäre.
Mark Booth
danke für den link, ich wusste nichts über den peinlichen paralell begriff. Sind nicht alle Karten lösbare Probleme auf peinliche Weise parallel zu reduzieren?
Paul Sanwald
1
Es gibt viele peinlich parallele Probleme, von denen nicht alle den Reduktionsteil benötigen.
Donal Fellows
1

Angenommen, Sie suchen in einem Cluster von Servern und einer kann in diesem Moment nicht antworten. Was mapReduce tun wird, ist, da es nicht auf diesen Baumknoten der größeren Karte zugreifen konnte, es wird es für später neu terminiert und dann entweder die Karte oder die Verkleinerung durchgeführt. Im Wesentlichen wird versucht sicherzustellen, dass alle Informationen in Umgebungen mit unvorhersehbarer Software und Hardware verfügbar sind.


quelle
1

Hier sind die wichtigsten Fragen, die ich verwende, um eine Entscheidung zu treffen, MapReduce zu verwenden (oder nicht zu verwenden).

  • Ist es für ein bestimmtes Problem wichtig, eine angemessene Leistung bei der parallelen Ausführung mit minimalem Programmieraufwand zu erzielen?
  • Habe ich eine große Anzahl (Hunderte) paralleler Ausführungselemente zur Verfügung?
  • Gibt es unter den parallelen Ausführungselementen eine hervorragende Kommunikationsbandbreite / -durchsatz?
  • Muss ich eine große Datenmenge (TB) verarbeiten?
  • Zerfällt das Problem, das ich lösen möchte, in Map and Reduce-Vorgänge?

    • Map: Führen Sie den gleichen Vorgang für alle Daten aus.
    • Reduzieren: Führen Sie für jede von Map erzeugte Datengruppe den gleichen Vorgang aus.
David Pointer
quelle
1

Tatsächlich handelt es sich um ein generisches "Teilen und Erobern" -Muster, sodass Lösungen für die Verteilung der Berechnung generisch geschrieben werden können.

Ein einfaches Beispiel ist wie ein großes Dokument. Das Problem ist, dass Sie die Anzahl der Buchstaben in diesem Dokument zählen möchten. Anstatt auf einem einzelnen Computer ausgeführt zu werden, können Sie ihn in ein Array aller Wörter im Dokument aufteilen. dann können Sie jedes Wort einzeln verarbeiten und die Ergebnisse wieder zusammenfügen.

Das Muster ist nützlich, da Sie, sobald Sie eine allgemeine Map / Reduction-Implementierung erstellt haben, jedes Problem mithilfe derselben Softwareschicht lösen können. Sie müssen Ihr Problem lediglich in diesem Sinne ausdrücken.

ianpojman
quelle