MapReduce

Vor einigen Wochen habe ich Gearman vorgestellt. Dieses Framework verteilt Aufgaben auf eine definierte Anzahl Worker, die über einen Master gesteuert werden und arbeitet so – auch über ein Netzwerk verteilt – Jobs ab. Auf dieser Basis kann man MapReduce nutzen. Stellt sich aber zuerst die Frage, was das überhaupt ist.

MapReduce ist ein Framework oder ein Konzept, das Google vorgestellt hat, um große Mengen an Daten zu verarbeiten. Nicht jeder wird petabyteweise Daten verarbeiten müssen, aber dennoch ist das Konzept interessant und auch bei kleinen Datenmengen nutzbar.

MapReduce besteht im wesentlichen aus 2 Phasen. In der ersten Phase wird der Datenbestand mit einem sinnvollen Algorithmus zerteilt berechnet. Dies ist die Map-Phase und hat als Ergebnis eine Menge an Zwischenergebnissen. Da man mit den vielen Einzelergebnissen wieder wenig anfangen kann, werden diese dann in einer 2. Phase wieder zusammengeführt. Dies ist die Reduce-Phase.

Map und Reduce sollte dem PHP-Entwickler auf jeden Fall bekannt sein, denn genau diese Funktionen gibt es schon ab PHP 4. Bei PHP handelt es sich um die beiden Methoden array_map und array_reduce. Die arbeiten auf Arrays und verhalten sich ähnlich. Die array_map-Funktion wendet ein Callback auf jedes Element eines Arrays an und array_reduce verwendet ein Callback um die Werte eines Arrays auf einen Wert zu reduzieren. Wie das im Einzelnen aussieht, kann man in den Beispielen im PHP-Manual nachlesen.

Um zurück zum Gearman zu kommen: Wenn man einen Worker als Map-Worker programmiert und einen für die Reduce-Phase, so kann man das MapReduce Verfahren auf den Gearman abbilden. Wieviele Worker man für die Phasen nutzt, hängt vom dann nur noch von der Hardware ab. Das ganze System skaliert aber wie man es sich vorstellt. Neben den Worker-Knoten gibt es noch einen Master, der durch den gearmand repräsentiert wird. Visualisiert kann man sich das ganze dann so vorstellen:

In der Grafik ist noch die Anwendung zu sehen, die über der ganzen Parallelisierung steht und das ganze Framework triggert.

Ein Beispiel für MapReduce ist ein verteiltes Grep. Bspw will man sehr großes Volumen von Log-Dateien nach Fehlermeldungen durchsuchen. So werden in der Map Phase die Log-Dateien in handliche Größe gebracht und einzeln mit grep durchsucht. In der Reduce-Phase kann eine neue Datei erzeugt werden oder man gibt das Ergebnis einfach aus. Wenn man auf der Kommandozeile arbeitet, wäre dies ja durchaus möglich.