Google nutzt für die Verarbeitung der gigantischen Daten ein Verfahren mit dem Namen MapReduce. Wenn man das gesamte Internet downloaden und dann mit diesen Datenmengen arbeiten möchte, wie stellt man so etwas an, und vor allem, wie können wir als PHP-Entwickler hier mitmischen?

Was steckt nun hinter diesem MapReduce? Zunächst einmal ist MapReduce ein Programmierparadigma, das im Wesentlichen die Verteilung einer Aufgabe auf mehreren Maschinen erlaubt. Das Verfahren an sich ist kein klassischer Algorithmus, wie man vermuten könnte, auch löst MapReduce selbst keine Rechenaufgaben. Das Grundkonzept ist im Grunde sehr einfach: Ein MapReduce-Framework stellt zunächst einmal nur einen koordinierenden Prozess zur Verfügung. Der Entwickler erstellt in seiner Programmiersprache zwei Funktionen: Eine für den Map-Schritt, eine weitere für den Reduce-Schritt. Der Koordinator ruft nun die Map-Funktion jeweils einmal je Einheit auf. Dabei sind diese Einheiten etwa Dokumente, HTML-Seiten unter einem bestimmten URL oder vielleicht auch Datensätze in einer Datenbank. Das Konzept von MapReduce ist ja gerade auch auf die Nutzung auf einem Cluster ausgerichtet. Innerhalb des Clusters existiert zunächst nur ein Prozess, der die Gesamtaufgabe aufteilt. Dabei erhalten alle hierbei entstehenden Worker-Prozesse eine Kopie der Map-Funktion. Die Worker können dabei auf unterschiedlichen Maschinen innerhalb des Clusters arbeiten. Sie wenden dabei die Map-Funktion auf allen ihnen zugeteilten Dokumenten an. Der zentrale Mutterprozess sammelt die Ergebnisse aller Worker und bildet hieraus zunächst ein Zwischenergebnis. Dieses bildet dann das Argument, das an die Reduce-Funktion übergeben wird. Die „Reduktion“ kann nun eine Summierung vornehmen oder das Ergebnis anderweitig aggregieren.

Einmal das Internet durchzählen, bitte!

Wie so oft ist die Nutzung eines konkreten Beispiels sicherlich der einfachste Weg, um den Ablauf zu verstehen. Ein Klassiker ist das Zählen der Vorkommnisse eines Worts in einem Dokument. Das Ergebnis soll uns eine Liste von Wörtern mit der Anzahl der Vorkommnisse liefern, am besten bereits absteigend sortiert nach der Anzahl.

Zur Lösung des Problems geht man vielleicht so vor, dass zunächst der Text in Wörter zerlegt wird. Dann bildet man ein Array, dessen Indices die Wörter bilden und final die Werte, die Vorkommnisse enthalten sollen. Die Liste der zerlegten Wörter wird nun durchwandert, und die Array-Einträge werden jeweils hochgezählt. Das Ergebnis ist dann eine Menge von Key-Value-Paaren, wobei jeweils in Key das gezählte Wort und in Value die Anzahl der gefundenen Vorkommnisse abgelegt wird.

Bei der Nutzung von MapReduce sind die Zerlegung und der Zählvorgang die Aufgabe der Map-Funktion. Grundsätzlich ist nicht genau definiert, wie die Daten der Map-Funktion zurückgegeben werden. Wird hier ein Rückgabewert genutzt, sollte dies dann ein Array bestehend aus Key-Value-Paaren sein. Andere Implementierungen nutzen eine globale so genannte Emit-Funktion, die einzelne Paare sammelt. Ein weiteres Verfahren ist das Schreiben in eine Datei – jeweils ein Key-Value-Paar pro Zeile. Letztlich ist es bei allen Verfahren aber gleichgültig, ob ein Schlüssel nur einmal oder mehrfach in den Ergebnissen auftaucht. In englischen Texten ist sicherlich der Artikel „the“ das mit Abstand am meisten vorkommende Wort. Somit könnte unsere Map-Funktion bei hundert Vorkommnissen nur einmal ein Paar wie (the, 100) emitten, oder aber hundertmal (the, 1) oder auch vierzigmal (the, 2) und zweimal (the, 10). Die Ergebnisse müssen ja schließlich zurück an das Mutterschiff transportiert werden, daher ist es in Bezug auf die Datenmenge günstiger, bereits voraggregierte Werte zu übertragen. Allerdings kostet das Sammeln Speicher- und Bearbeitungszeit. An dieser Stelle können wir auch eine gewisse Dynamik in unserer Map-Funktion implementieren, wenn uns die Rahmenparameter bereits bekannt sind und wir bereits wissen, dass unsere Texte extrem groß oder unsere Ressourcen extrem klein sind.

Nachdem die einzelnen Map-Funktionen ihre Ergebnisse ausgegeben...