Welche Probleme löst MapReduce?

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.

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.

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.

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.

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.

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.

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).

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.

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).

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).

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.

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.

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.