Wie funktioniert der MapReduce-Sortieralgorithmus?

Question

Eines der wichtigsten Beispiele für die Leistungsfähigkeit von MapReduce ist die Terasort benchmark. Ich habe Probleme, die Grundlagen des in der MapReduce-Umgebung verwendeten Sortieralgorithmus zu verstehen.

Für mich bedeutet Sortieren einfach die relative Position eines Elements in Beziehung zu allen anderen Elementen zu bestimmen. Sortieren bedeutet also, "alles" mit "alles" zu vergleichen. Ihr durchschnittlicher Sortieralgorithmus (schnell, bubble, ...) macht das einfach auf intelligente Weise.

Wenn ich den Datensatz in viele Teile aufspalte, bedeutet das, dass man ein einzelnes Stück sortieren kann und dann diese Teile in den "vollständigen" vollständig sortierten Datensatz integrieren muss. Angesichts des Terabyte-Datensatzes, der auf Tausende von Systemen verteilt ist, erwarte ich, dass dies eine große Aufgabe ist.

Also, wie ist das wirklich gemacht? Wie funktioniert dieser MapReduce-Sortieralgorithmus?

Vielen Dank für Ihr Verständnis.

Answer 1

Hier sind einige Details zu Hadoop's implementation for Terasort:

TeraSort ist eine Standard-Map/Reduce Art, mit Ausnahme eines benutzerdefinierten Partitionierer, die eine sortierte Liste von N verwendet - 1 abgetastet Tasten, die den Schlüsselbereich für jede definieren reduzieren . Insbesondere werden alle Schlüssel so gesendet, dass sample [i - 1] < = key < sample [i] gesendet wird, um i zu reduzieren. Damit ist gewährleistet, dass die Ausgabe reduzieren i sind alle weniger als die Ausgabe von verringern i + 1“.

So ihr Trick ist, in der Art, wie sie die Schlüssel während der Kartenphase bestimmen. Im Wesentlichen, dass sie sicherstellen, jeder Wert in eine einzige Minderer gewährleistet ‚vorsortiert‘ gegen alle anderen Reduzierungen werden.

ich das Papier Referenz durch James Hamilton's Blog Post gefunden.

Answer 2

Google Referenz: MapReduce: Simplified Data Processing on Large Clusters

in Erscheint:
OSDI'04: Sechstes Symposium on Operating System Design und Implementierung,
San Francisco, CA, Dezember 2004.

Dieser Link hat eine PDF- und HTML-Slide-Referenz.

Es gibt auch eine Wikipedia page with description mit Implementierungsreferenzen.

auch Kritik,

David DeWitt und Michael Stonebraker, Pionier Experten parallel Datenbanken und Shared-Nothing-Architekturen, haben einige kontroverse Aussagen über die Breite der Probleme gemacht, die MapReduce kann verwendet werden. Sie nannten ihre Schnittstelle zu niedrig und stellten in Frage, ob sie wirklich den Paradigmenwechsel darstellt, den ihre Befürworter behauptet haben. Sie stellen die Ansprüche der MapReduce-Befürworter auf Neuheit in Frage und berufen sich auf Teradata als ein Beispiel für den Stand der Technik, der seit über zwei Jahrzehnten besteht; Sie verglichen MapReduce-Programmierer mit Codasyl-Programmierern und stellten dabei fest, dass beide "in einer Low-Level-Sprache schreiben und eine Low-Level-Datensatzmanipulation durchführen". Die Verwendung von Eingabedateien durch MapReduce und die fehlende Unterstützung von Schemata verhindert Leistungsverbesserungen, die durch gängige Datenbanksystemfunktionen wie B-Bäume und Hash-Partitionierung ermöglicht werden, obwohl Projekte wie PigLatin und Sawzall damit beginnen, diese Probleme anzugehen.

Answer 3

nur raten ...

eine große Menge von Daten gegeben, würden Sie die Daten in einige Stücke aufzuteilen, um parallel verarbeitet werden (vielleicht durch Datensatznummer aufsprechen 1-1000 = Partition 1 und bald).

Weisen Sie jede Partition einem bestimmten Knoten im Cluster zu/planen Sie sie an.

Jeder Cluster-Knoten wird die Partition weiter in eine eigene Mini-Partition aufteilen (mappen), vielleicht durch die alphabetische Reihenfolge der Schlüssel. Also, in Partition 1, besorge mir all die Dinge, die mit A beginnen und gib sie in die Mini-Partition A von x aus. Erstelle ein neues A (x) wenn es bereits ein A (x) gibt. Ersetzen Sie x durch die laufende Nummer (vielleicht ist dies der Scheduler-Auftrag). I.e.Gib mir die nächste A (x) eindeutige ID.

Übergabe von Jobs, die vom Mapper (vorheriger Schritt) an die Clusterknoten "reduce" (Vervollständigen) abgeschlossen wurden. Reduce Node Cluster verfeinert dann die Sortierung der einzelnen A (x) Parts, die nach Beendigung der Mapper-Tasks immer wieder vorkommen (Kann nicht alle Wörter beginnen, die mit A beginnen, wenn noch die Möglichkeit besteht, dass sie noch vorhanden sind) wird eine andere Eine Mini-Partition in der Herstellung sein. Geben Sie das Ergebnis in der endgültigen Sortierpartition (d. H. Sortiert-A, Sortiert-B usw.) aus.

Anschließend kombinieren Sie die sortierte Partition erneut zu einem einzelnen Dataset. An dieser Stelle ist es nur eine einfache Verkettung von n Dateien (wobei n 26 sein könnte, wenn Sie nur A - Z machen), etc.

Es könnte Zwischenschritte dazwischen geben ... Ich bin mir nicht sicher:). I.e. Weitere Abbildung und Reduzierung nach dem anfänglichen Reduzierungsschritt.

Answer 4

ich die gleiche Frage beim Lesen von Google MapReduce Papier hatte. @Yuval Fanswer hat mein Rätsel ziemlich gelöst.

Eine Sache, die ich beim Lesen der Zeitung bemerkt habe, ist, dass die Magie in der Partitionierung passiert (nach der Karte, vor dem Reduzieren).

Das Papier verwendet hash(key) mod R als das Partitionierungsbeispiel, aber dies ist nicht die einzige Möglichkeit, Zwischendaten in andere Reduzierungsaufgaben zu partitionieren.

Fügen Sie einfach Randbedingungen @Yuval F ‚s answer, um es komplett zu machen: suppose min (S) und max (S) ist der Mindestschlüssel und maximale Schlüssel unter den abgetasteten Tasten; Alle Schlüssel < min (S) sind auf eine Reduzierungsaufgabe aufgeteilt; Umgekehrt sind alle Schlüssel> = max (S) auf eine Reduzierungsaufgabe aufgeteilt.

Es gibt keine feste Begrenzung für die gesampelten Tasten, wie min oder max. Nur, gleichmäßiger sind diese R-Tasten verteilt auf alle Schlüssel, "paralleler" ist dieses verteilte System, und es ist weniger wahrscheinlich, dass ein Reduzierungsoperator ein Speicherüberlaufproblem hat.