Paarweise

Ein Mapper verarbeitet den Inhalt eines Blocks zeilenweise, wobei er jede Zeile als ein Schlüssel-Wert-Paar interpretiert. Die eigentliche Map-Funktion wird für jedes dieser Paare einzeln aufgerufen und erzeugt daraus eine beliebig große Liste an neuen Schlüssel-Wert-Paaren:

map: (key, value)  list(key', value')

Die Shuffle-Phase sortiert die Ergebnis-Paare der Map-Phase zunächst lokal nach ihren Schlüsseln. Anschließend ordnet Map-Reduce sie abhängig von ihrem Schlüssel einem so genannten Reducer zu. Dabei stellt das Framework sicher, dass alle Paare mit dem gleichen Schlüssel auch denselben Reducer zugeordnet bekommen.

Jetzt gibt's Traffic

Da die Ausgabe der Map-Phase beliebig über den Cluster verteilt sein kann, muss das System in der Shuffle-Phase die Ausgaben der Map-Phase größtenteils über das Netzwerk zu dem entsprechenden Reducer übertragen. Daher gehen bei diesem Schritt häufig große Datenmengen übers Netzwerk. Der Reducer fasst schließlich alle Paare mit gleichem Schlüssel zusammen und bildet aus den Werten eine sortierte Liste. Der Schlüssel zusammen mit der sortierten Liste der Werte bildet dann die Eingabe für die Reduce-Funktion.

Die Reduce-Funktion verdichtet typischerweise die Liste der Werte zu einer kürzeren Liste, beispielsweise indem sie die Werte aggregiert. Nicht selten liefert sie daher auch nur einen einzelnen Wert als Ausgabe. Allgemein betrachtet erzeugt die Reduce-Funktion jedoch genau wie die Map-Funktion eine beliebig große Liste an Schlüssel-Wert-Paaren:

reduce: (key, List(values))list(key', value')

Die Ausgabe der Reduce-Phase lässt sich bei Bedarf wiederum als Eingabe für eine weitere Map-Reduce-Iteration verwenden.

Als passendes Anschauungsbeispiel für den Map-Reduce-Einsatz eignet sich eine Websuchmaschine. Für ein solches System ist es besonders wichtig, die Relevanz einer Seite im Netz möglichst gut einschätzen zu können.