MapReduce

MapReduce wurde 2004 von Google Inc. entwickelt, erhielt 2010 ein US-Patent und ist ein Framework für Datenbanken. Es ist für nebenläufige Berechnungen auf großen Datenmengen (mehrere Petabyte) gedacht.

Bei diesem Verfahren werden die Daten in den drei Phasen "Map", "Shuffle" und "Reduce" verarbeitet. Die Phasen "Map" und "Reduce" gestaltet der Anwender selbst. Die Berechnungen werden parallelisiert, das heißt sie können neben allen anderen Berechnungen zur selben Zeit laufen.

Zudem werden sie auf mehrere Rechner verteilt. Bei sehr großen Datenmengen ist sowohl die Verteilung als auch die Parallelisierung unbedingt erforderlich, da ein einzelner Prozess und eventuell auch der einzelne Rechner mit der Berechnung überfordert sein könnte.

MapReduce-Implementierungen gibt es unter anderem für die Programmiersprachen Java, Erlang, Python und C++.

Wie funktioniert das MapReduce Verfahren in Datenbanken?

Das MapReduce-Verfahren soll eine große Menge (M1), bestehend aus Key/Value-Paaren des gleichen Typs (T1) so reduzieren, dass eine kleinere Menge (M2) von Key/Value-Paaren eines anderen Typs (T2) entsteht.

Dazu startet der Programmierer einen MapReduce-Vorgang unter Angabe aller Dateien, die die Menge M1 bilden. Dann definiert er die Methoden Map und Reduce für die Menge M1.

Die Methode Map mit dem Wert X vom Typ T1 zerlegt oder extrahiert die Daten in Werte vom Typ T2. Die Methode Reduce macht aus den Paaren T2 in der Menge M3, die eine Teilmenge von M2 darstellt und alle denselben Key (k) enthalten, jeweils ein Paar vom Typ T2. Diese Map- und Reduce-Aufrufe werden auf möglichst viele Rechner verteilt und somit parallel zueinander abgearbeitet. Zudem sorgt die Methode dafür, dass der Aufruf auf einem Rechner stattfindet, welcher den Rechnern, die M3 oder X verwalten, geographisch nah ist.

Der Programmierer entscheidet selbst, welche Mengen (M3) als Zwischenergebnisse entstehen sollen. Auch über den Rechner im Gesamtverbund, auf dem gespeichert werden soll, entscheidet er eigenmächtig. Ebenfalls obliegt dem Programmierer die Zusammenführung aller Ergebnisse und die Reduce-Aufrufe der Menge M2.

Vorteile des MapReduce-Verfahrens

MapReduce ist kostengünstig

Das Verfahren kann auf handelsübliche Standard-Software verteilt werden. High-End-Server sind nicht notwendig. Somit kann ein Cluster (Verbund von Rechnern) auch ohne spezielle Server aufgebaut und genutzt werden. Dies spart immense Kosten ein.

MapReduce ist skalierbar

Aus dem ersten Vorteil ergibt sich direkt der Zweite: Die Skalierbarkeit. Das Verfahren kann auf so viele Rechner wie gewünscht aufgeteilt werden, es gibt dabei keinerlei Begrenzung.

MapReduce ist schnell

Im Terabyte-Bereich dauert das Verfahren oft nur Minuten, im Petabyte-Bereich Stunden. Das ist sehr viel schneller als bei anderen Verfahren.

Nachteile des MapReduce-Verfahrens

Langsamer Datenzugriff

Während die Berechnungen schnell gehen, dauert der Datenzugriff länger als bei anderen Methoden. Die Daten müssen erst über das Netzwerk gestreamt werden. Dabei ist die Netzanbindung der Flaschenhals - vor allem im Hinblick auf die sehr unterschiedlichen Rechner innerhalb des Clusters und deren unterschiedliche schnelle Netzanbindung.

Hohe Kosten, wenn ausschließlich High-End-Server genutzt werden

Um die Geschwindigkeit zu erhöhen, kann ein Cluster ausschließlich aus High-End-Servern bestehen. In diesem Fall sind die Kosten für das MapReduce-Verfahren immens hoch.