Wie funktioniert der MapReduce-Sortieralgorithmus?

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

Für mich bedeutet das Sortieren einfach, die relative Position eines Elements in Bezug auf alle anderen Elemente zu bestimmen. Beim Sortieren wird also "alles" mit "alles" verglichen. Ihr durchschnittlicher Sortieralgorithmus (schnell, Blase, ...) erledigt dies einfach auf intelligente Weise.

In meinen Augen bedeutet das Aufteilen des Datensatzes in viele Teile, dass Sie ein einzelnes Teil sortieren können und diese Teile dann noch in den vollständig sortierten Datensatz "vollständig" integrieren müssen. Angesichts des Terabyte-Datensatzes, der auf Tausende von Systemen verteilt ist, erwarte ich, dass dies eine große Aufgabe ist.

Wie wird das wirklich gemacht? Wie funktioniert dieser MapReduce-Sortieralgorithmus?

Danke, dass du mir geholfen hast zu verstehen.

Hier einige Details zur Implementierung von Hadoop für Terasort :

TeraSort ist eine Standard-Map / Reduce-Sortierung, mit Ausnahme eines benutzerdefinierten Partitionierers, der eine sortierte Liste von N - 1 abgetasteten Schlüsseln verwendet, die den Schlüsselbereich für jede Reduktion definieren. Insbesondere werden alle Schlüssel, so dass Probe [i - 1] <= Schlüssel <Probe [i] gesendet werden, um i zu reduzieren. Dies garantiert, dass die Ausgabe von Reduce i alle kleiner ist als die Ausgabe von Reduce i + 1. "

Ihr Trick liegt also in der Art und Weise, wie sie die Schlüssel während der Kartenphase bestimmen. Im Wesentlichen stellen sie sicher, dass jeder Wert in einem einzelnen Reduzierstück garantiert gegen alle anderen Reduzierstücke vorsortiert wird.

Ich fand die Papierreferenz in James Hamiltons Blog Post .

Google-Referenz: MapReduce: Vereinfachte Datenverarbeitung in großen Clustern

Erschienen in :
OSDI'04: Sechstes Symposium zum Entwurf und zur Implementierung von Betriebssystemen,
San Francisco, CA, Dezember 2004.

Dieser Link enthält eine PDF- und eine HTML-Folienreferenz.

Es gibt auch eine Wikipedia-Seite mit einer Beschreibung mit Implementierungsreferenzen.

Auch Kritik,

David DeWitt und Michael Stonebraker, wegweisende Experten für parallele Datenbanken und gemeinsame Architekturen, haben einige kontroverse Aussagen über die Breite der Probleme gemacht, für die MapReduce verwendet werden kann. Sie nannten seine Schnittstelle zu niedrig und fragten, ob es wirklich den Paradigmenwechsel darstellt, den seine Befürworter behauptet haben. Sie stellen die Neuheitsansprüche der MapReduce-Befürworter in Frage und führen Teradata als Beispiel für den Stand der Technik an, der seit über zwei Jahrzehnten besteht. Sie verglichen MapReduce-Programmierer mit Codasyl-Programmierern und stellten fest, dass beide "in einer Sprache auf niedriger Ebene schreiben und eine Manipulation von Aufzeichnungen auf niedriger Ebene durchführen". Die Verwendung von Eingabedateien durch MapReduce und die mangelnde Unterstützung von Schemata verhindern die Leistungsverbesserungen, die durch allgemeine Funktionen des Datenbanksystems wie B-Bäume und Hash-Partitionierung ermöglicht werden.

Ich hatte die gleiche Frage beim Lesen von Googles MapReduce-Artikel. @Yuval F ‚s Antwort gelöst ziemlich mein Rätsel.

Eine Sache, die mir beim Lesen der Zeitung aufgefallen ist, ist, dass die Magie in der Partitionierung geschieht (nach der Karte, vor dem Reduzieren).

Das Papier verwendet hash(key) mod Rals Partitionierungsbeispiel, aber dies ist nicht die einzige Möglichkeit, Zwischendaten auf verschiedene Reduzierungsaufgaben zu partitionieren.

Fügen Sie einfach Randbedingungen zur Antwort von @Yuval F hinzu , um sie zu vervollständigen: Angenommen, min (S) und max (S) sind der minimale und maximale Schlüssel unter den abgetasteten Schlüsseln; Alle Schlüssel <min (S) sind auf eine Reduzierungsaufgabe aufgeteilt. Umgekehrt werden alle Schlüssel> = max (S) auf eine Reduzierungsaufgabe aufgeteilt.

Es gibt keine feste Einschränkung für die abgetasteten Tasten, wie z. B. min oder max. Je gleichmäßiger diese R-Schlüssel auf alle Schlüssel verteilt sind, desto "paralleler" ist dieses verteilte System und es ist weniger wahrscheinlich, dass ein Reduzierungsoperator ein Problem mit dem Speicherüberlauf hat.

Einfach raten...

Bei einem riesigen Datensatz würden Sie die Daten in einige Blöcke aufteilen, die parallel verarbeitet werden sollen (möglicherweise nach Datensatznummer, dh Datensatz 1 - 1000 = Partition 1 usw.).

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

Jeder Clusterknoten unterteilt die Partition weiter in eine eigene Mini-Partition, möglicherweise in alphabetischer Reihenfolge. Holen Sie sich in Partition 1 alle Dinge, die mit A beginnen, und geben Sie sie in die Mini-Partition A von x aus. Erstellen Sie ein neues A (x), wenn derzeit bereits ein A (x) vorhanden ist. Ersetzen Sie x durch eine fortlaufende Nummer (möglicherweise ist dies der Scheduler-Job, um dies zu tun). Dh Gib mir die nächste A (x) eindeutige ID.

Übergeben (Planen) von Jobs, die vom Mapper ausgeführt wurden (vorheriger Schritt), an die "Reduzieren" -Clusterknoten. Durch das Reduzieren des Knotenclusters wird dann die Sortierung der einzelnen A (x) -Teile weiter verfeinert, die einsam auftreten, wenn alle Mapper-Aufgaben erledigt sind. (Es können nicht alle Wörter sortiert werden, die mit A beginnen, wenn noch die Möglichkeit besteht, dass noch vorhanden ist wird eine weitere A-Mini-Partition sein). Geben Sie das Ergebnis in der endgültig sortierten Partition aus (z. B. Sorted-A, Sorted-B usw.).

Kombinieren Sie anschließend die sortierte Partition erneut zu einem einzigen Datensatz. Zu diesem Zeitpunkt ist es nur eine einfache Verkettung von n Dateien (wobei n 26 sein könnte, wenn Sie nur von A bis Z arbeiten) usw.

Dazwischen könnten Zwischenschritte liegen ... Ich bin mir nicht sicher :). Dh nach dem anfänglichen Reduktionsschritt weiter abbilden und reduzieren.