Dunkelstern Mobile Blog

Ein schönes Beispiel hierfür ist der so hoch gelobte "MapReduce" Algorithmus zur massiven Parallelisierung von komplexen Aufgaben (z.B. um massiven Datendurchsatz zu erzielen). Um kurz zu erklären was MapReduce eigentlich ist hole ich mal ein wenig aus hier. Wer MapReduce kennt kann also den nächsten Absatz überspringen.

MapReduce ist eine Möglichkeit wie man aus einer komplexen Aufgabe eine massiv parallel verarbeitete Aufgabe machen kann. Als Beispiel nehme ich hier jetzt mal eine einfache Suche nach einem bestimmten Wort in einer Textdatenmenge - von sagen wir 30 Terabyte - an. Ein Einzelner Rechner würde hierfür wahrscheinlich Jahre benötigen, mal abgesehen davon, dass ich die Storage Lösung für diese Menge Daten gerne mal sehen würde :)

Verteilt man diese Aufgabe allerdings auf viele - sagen wir mal 2000 - Rechner, so wird die Aufgabe schon sehr viel übersichtlicher. Jeder Rechner muss dann "nur" noch 15 Gigabyte durchsuchen. Diese Aufgabe ist in einem angemessenen Zeitrahmen zu erledigen und die Datenmenge verteilt sich angenehm auf die 2000 Festplatten der Rechner. Doch wie schaffe ich es jetzt diese Suche einfach programmierbar zu halten? Hier kommt nun MapReduce zum Einsatz. Als Programmierer muss ich nun lediglich die Aufgabe splitten und die Infrastruktur von MapReduce verteilt die Aufgaben automatisch auf die Rechner, ich gebe also sozusagen nicht mehr eine Aufgabe "Durchsuche die 30 Terabyte Daten" sondern viele kleine Aufgaben "Durchsuche mir das Datenfragment X (mit der Größe von 500MB meinetwegen) nach Y". Eine Art Loadbalancer verteilt die Aufgaben nun auf den Cluster und wartet auf die Ergebnisse. Die Ergebnisse, so sie denn überhaupt eintreffen werden an die sogenannte Reduce-funktion weitergegeben und diese wertet die Ergebnissdaten schon mal aus während weiterhin Rechenaufgaben verteilt werden. Theoretisch wird jeder Rechner im Cluster also 30 Aufgaben (je 500MB) zugeteilt bekommen. Der Clou an der Sache ist jedoch der, dass alles komplett Asynchron läuft, d.h. kommt nach einem bestimmten Timeout kein Ergebniss von einem Node zurück wird die Aufgabe neu vergeben (Seti at Home macht das ja ähnlich :) ) bis alle Ergebnisse eingesammelt worden sind. 

Hier kann nun entweder eine Reduce Kaskade die Zwischenergebnisse der Reduce Nodes weiterverarbeiten (weiteres Ausfiltern der Ergebnisse oder zusammenfassen und doppelte Ergebnisse rauswerfen) oder die Ergebnisse landen direkt wieder beim Master. Durch die asynchrone Verarbeitung ist vollkommen egal was für Nodes im Cluster sind, bzw. wie schnell diese sind, ist eine Node mit der Aufgabe überfordert oder fällt aus, so wird die Aufgabe neu vergeben.

Doch warum ist das nicht innovativ? - Ganz einfach deswegen, weil das eine absolute Grundlage der Parallelverarbeitung ist! Jeder einigermaßen intelligente Programmierer kommt früher oder später selbst auf die Idee genau so eine Lösung zu implementieren wenn es um große Datenmengen oder Zeitintensive Aufgaben geht. Außerdem wird MapReduce immer mehr auch auf "normalen" PCs zum Einsatz kommen, einfach deswegen weil man heute mehrere CPU-Kerne zur Verfügung hat und diese auch ausnutzen möchte.

Ein Beispiel hierzu: Ich möchte Daten komprimieren, es sind viele in kurzer Zeit, unkomprimiert packt meine Festplatte den Datenstrom nicht, daher benötige ich Echtzeitkomprimierung. Das kommt z.B. bei uns in der Firma vor wenn ich eine OpenGL Anwendung mit X-POSE-X-Record aufzeichen will, Unreal Tournament 2004 verursacht z.B. ca  250 MiB OpenGL Daten pro Sekunde, das packt keine Platte!

Was mache ich also als Programmierer: Ich versuche die 3 unbelasteten CPU Kerne die sich hier gerade langweilen mit zu nutzen. Wie mache ich das am besten? - Die einfache Methode ist direkt ein MapReduce Derivat. Ich versuche den Datenstrom in kleine Pakete einzuteilen, packe diese Pakete als einzelne Aufgaben in eine Queue und lasse X Threads nen Encoder starten die sich dann die Daten aus der Queue pulen und sie verarbeiten. Das Ergebnis landet mit richtiger Sequenznummer in einer Ergebnis Queue. Diese Ergebnisse werden von einem weiteren Thread sortiert (die Encoder sind nicht bei jeder Datenmenge gleich schnell, daher das Chaos :) ) und schließlich auf die Platte geschrieben. Ich mappe also Aufgaben auf meine Encoder Threads und ein weiterer Thread (der, der auf die Platte schreibt) reduziert meine Ergebnisse (Reduce Aufgabe läuft hier also auch parallel).

Das ist eigentlich ganz einfach oder? Doch warum wird das Gedöns nun Google zugeschrieben, und vor allem warum kommt darauf erst 2004 jemand? - Erstens, weil Google nen Namen dafür gefunden hat und diese Methode durch ihren ungleichförmigen Rechencluster im großen Maßstab anwendet und an zweiter Stelle wohl auch deswegen, weil sich niemand über solches Basiswissen groß Gedanken gemacht hat. Ich mein nichts gegen Google... die haben schließlich den größten Superrechner der Welt, auch wenn er nicht unter den Top500 Auftauchen wird, weil seine Rechenleistung nicht gemessen werden kann.

Ich sollte auch mal Papers schreiben über so grundlegende Sachen, aber lesen wird sie wahrscheinlich eh niemand ;)