© saicle/Shutterstock.com
PHP Magazin
Datenverarbeitung mit MapReduce

Datenverarbeitung mit MapReduce

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?

Carsten Harnisch


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...

PHP Magazin
Datenverarbeitung mit MapReduce

Datenverarbeitung mit MapReduce

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?

Carsten Harnisch


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...

Neugierig geworden?


    
Loading...

Angebote für Teams

Für Firmen haben wir individuelle Teamlizenzen. Wir erstellen Ihnen gerne ein passendes Angebot.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang