Funktionale Programmierung (3): Das MapReduce-Framework

Die Grundidee von MapReduce ist schnell skizziert: Man verwende die funktionalen Bausteine Map und Reduce (siehe Teil 1 dieser Artikelreihe) und bilde um diese herum ein Framework mit folgenden Eigenschaften:

• automatische Parallelisierung, Koordinierung und Verteilung von Berechnungen (Jobs)
• Fehlertoleranz gegenüber Hardware- und Softwareausfällen
• automatische Lastverteilung
• Optimierung von Netzwerk und Datentransfer
• Überblick durch Status- und Monitoringnachrichten

So entsteht eine Anwendung, die für viele Einsatzgebiete geeignet ist. Dies zeigen zum Einen die zahlreichen Implementierungen von MapReduce, die seit 2003 entstanden sind, und zum Anderen die vielen Anwendungsbereiche, in denen MapReduce zum Einsatz kommt:

• Indizierung großer Datenmengen für die Suchaufbereitung
• Maschinelles Lernen zur künstlichen Erzeugung von Wissen aus Erfahrung
• Verteiltes Suchen von Pattern, Sortieren von Daten
• Auswertung von großen Logdateien
• Kategorisierung von Daten zur Nachrichtenaufbereitung
• Datenaufbereitung für häufige Anfragen
• Erzeugung von Graph über die Aufrufhäufigkeit, über die Verlinkung von Webseiten
• Extrahieren von Daten aus Webseiten um neue Einsichten zu erlangen

Gemeinsam ist diesen Anwendungen, dass sie mit sehr großen Datenmengen arbeiten müssen - typischerweise im Tera- bis Petabyte-Bereich - und somit von einem einzelnen Rechner nicht in vertretbarer Zeit gelöst werden können.

Zu verdanken ist der weite Einsatzbereich von MapReduce insbesondere der Trennung von Framework- und Anwendungslogik. Die komplexen Details der Berechnung bleiben im Framework verborgen, der Anwender braucht lediglich die Funktionen Map und Reduce für seine Zwecke zu definieren.

Angesichts der Mächtigkeit dieses Konzepts stört es da wenig, dass die Map- und Reduce-Funktionen im MapReduce Framework sich von ihren funktionalen Namensgebern deutlich unterscheiden. Die Unterschiede beschreibt beispielsweise der Microsoft-Entwickler Ralf Lämmel in seinem Aufsatz "Google's MapReduce Programming Model -- Revisited (PDF)". Ein natürlicher Zugang zu dem MapReduce Protokoll ist es, den Datenfluss während der Berechnung genauer zu betrachten (Abbildung 1).

Protokoll

Das Framework verteilt die Eingabedatei auf mehrere Map-Prozesse. Diese Map-Prozesse berechnen in der Map-Phase parallel die Zwischenergebnisse. Ist diese Phase vorbei, beginnt die Reduce-Phase, in der die Reduce-Prozesse mit den passenden Zwischenergebnissen gefüttert werden und jeder dieser Prozesse seine Ergebnisdatei im Dateisystem speichert. Ist die Reduce-Phase absolviert, ist auch die MapReduce-Berechnung abgeschlossen.

Abbildung 1: Datenfluss MapReduce

Der Anwender hingegen definiert seine Anwendungslogik in Form der Map- und Reduce-Funktionen, die in den entsprechenden Phasen angewandt werden. Die Map Funktion (Mapper) nimmt ein Paar "(Schlüssel,Wert)" an und erzeugt aus diesem eine Liste von Paaren in der Form "(Schlüssel,Wert)". Diese dienen als Eingabe für die Reduce-Funktion (Reducer), die alle Werte zu einem Schlüssel als Liste erhält und aus diesen Werten das Ergebnis berechnet und es in das verteilte Dateisystem schreibt.

Wie sehen die konkreten Mapper und Reducer aus? Ein klassische Anwendung für MapReduce besteht darin, die Worthäufigkeit in einer Eingabedatei zu bestimmen. Dazu erhält der Mapper die Liste aller Paare im Format"(Zeilennummer,Zeileninhalt)" und erzeugt für jedes Wort der Zeile ein Paar in der Form "(Wort,1)". Die Reduce-Funktion erhält alle Werte zu dem Schlüsselwort in der Form "(Wort,[1,..,1])" als Eingabe. Diese addiert in der Reduce-Phase die Werte zusammen und schreibt sie in das Dateisystem. Als Ergebnis des MapReduce-Vorgangs steht die Liste "[(Wort,Häufigkeit des Wortes)]" aller Wörter der Eingabedatei zu Verfügung.

Die folgende Tabelle fasst alle an der Datenverarbeitung beteiligten Komponenten zusammen:

Architektur

Nun ist es Zeit, auf die Architektur des Frameworks einzugehen. Abbildung 2 zeigt die Einzelschritte der MapReduce-Berechnung.

Die MapReduce-Architektur

1. Das MapReduce Framework teilt die Eingabe in m Teile auf, startet den Master und die Worker Prozesse auf dem Rechencluster.
2. Der Master weist die m Map-Aufgaben und r Reduce-Aufgaben den entsprechenden Rechnern zu.
3. Der Map-Prozess liest die Eingabedaten als Paare in der Form "(Schlüssel,Wert)" ein, verarbeitet sie mit der Map- Funktion und schreibt die Zwischenergebnisse in den Speicher.
4. Der Map-Prozess schreibt die Zwischenergebnisse periodisch in r Dateien auf seine Festplatte und teilt die Namen der Dateien dem Master mit.
5. Der Reduce-Prozess bekommt vom Master die Adressen der Zwischenergebnisse mitgeteilt, liest alle für ihn bestimmten "(Schlüssel,Wert)"-Paare ein und sortiert die "(Schlüssel,Wert)"-Paare nach deren Schlüsseln.
6. Der Reduce-Prozess iteriert über die "(Schlüssel,Liste von Werten)"-Paare für jeden Schlüssel, übergibt die "(Schlüssel,Liste von Werten)"-Paare an die Reduce-Funktion, die die Liste von Werten zu einem Ausgabewert akkumuliert.
7. Das MapReduce-Framework wartet, bis alle Map- und Reduce Prozesse durchlaufen sind und übergibt die Kontrolle wieder an die Applikation.

Was für das Gesamtverständnis nun noch fehlt, ist, sich einzelne Komponenten der Architektur genauer anzuschauen.