Den Einstieg in die Welt der großen Datenmenge macht schwierig, dass man es nicht nachvollziehen kann, indem man es einfach mal daheim ausprobiert. Das ist ja schließlich der Witz an Big Data – dass man nicht einfach mal ein Terabyte Daten durchlaufen lässt um zu sehen was daran schwierig ist.
Und das hat es mir früher auch schwierig gemacht, das Prinzip von MapReduce zu verstehen. Nicht das was, sondern das warum. Und deswegen will ich trotzdem mit dem allseits beliebten, immer wieder gesehenen Beispiel für MapReduce beginnen, aber wenigstens versuchen, einige Sätze einzustreuen warum man das jetzt so machen muss.
Umgebung
Ich arbeite ausschließlich in Linux, und daher werden meine Beispiele auch ausschließlich für Ubuntu 12.04 oder 12.10 geschrieben sein. Aber auch in Windows kann man mit Cygwin eine Linux-Umgebung bekommen, oder mit Wubi gar stressfrei ein Ubuntu von Windows aus testen.
Ebenso programmiere ich in Python, und spezialisiere meine Beispiel darauf. Vielleicht kommt irgendwann ein bisschen Java dazu, sicher aber uch noch etwas Shell Scripting und eventuell Pig.
Für den ersten Teil brauchen wir noch kein Hadoop, wir kommen ohne große Daten oder parallel laufende Jobs aus und simulieren nur die prinzipiellen Schritte des Map und Reduce.
Map/Reduce
Im Kern ist MapReduce nur ein Konzept der Programmierung, benannt nach der Google-Implementation. Wobei der Name durch map und reduce Funktionen in Lisp inspiriert ist. Das Prinzip besteht darin, das Problem in kleine Unterprobleme einzuteilen, die mit einem wirklich kleinen Teil der Daten gelöst werden können, sodass man nie einen wirklich großen Datensatz im Speicher halten muss. Der Mapper schreibt dann seine Lösung als einfaches Schlüssel-Wertpaar. Der wichtige Unterschied zu klassischer Multiprozessor-Parallelisierung ist (neben einfacherer Skalierbarkeit), dass das auch mit ungeordneten Daten sehr gut funktioniert, da der Mapper quasi sehr, sehr einfache Zwischenresultate herausgeben kann, die dann neu verteilt werden (Shuffling oder Partitioning, wichtiger Schritt) und vom einem weiteren Code im Reduce-Schritt zusammengefasst werden.
Man kann es so sehen, als ob der Mapper eine Kernaussage der Daten pro Datensatz extrahiert, und dadurch die Datenmenge reduziert. Man kann daher sehr viele Mapper gleichzeitig laufen lassen, da sie unabhängig voneinander sind. Da man aber pro Schlüssel (quasi pro Typ an Daten, z.B. im unteren Beispiel jedes Wort) ein Ergebnis haben will, muss man dann die Zwischenergebnisse neu verteilen und vom Reducer pro Schlüssel zusammenfassen lassen.
Beispiel – Word Count
Die Aufgabe ist, eine Liste aufzustellen, die zählt, wie oft jedes Wort in einem Text vorkommt. Für die Datenmenge die wir in den Beispielen haben werden, mag MapReduce wieder überkompliziert aussehen, aber denkt einfach mal wie ihr dieses Problem mit allen Büchern der Welt (Google Books) lösen würdet. Wenn ihr auch noch jeden Tag neu zählen müsstet.
Um die Lösung im MapReduce-Denken zu verstehen, speichern wir dazu zwei kleine Skripte:
import sys
def mapper():
for line in sys.stdin:
pp = line.strip().split()
for p in pp:
print p, 1
if __name__ == '__main__':
mapper()
Speichert dieses als map.py und das folgende als reduce.py:
import sys
def reducer():
counter = {}
for line in sys.stdin:
pp = line.strip().split()
if len(pp):
counter[pp[0]] = counter.get(pp[0], 0) + int(pp[1])
for word, count in sorted(counter.items(), key=lambda x:x[1]):
print word, count
if __name__ == '__main__':
reducer()
Jetzt brauchen wir noch einen (kleinen) Datensatz, und können nachvollziehen wie MapReduce das Problem angeht. Speichert folgenden Text als input.txt ab:
Im ersten Teil dieses Blogposts werde ich zeigen, wie ein einfaches Beispiel funktioniert.
Im zweiten Teil dieses Blogposts werde ich eine einfache Hadoop-Variante davon vorstellen.
Lassen wir doch mal diesen Text durch map.py laufen und sehen, was in der Funktion passiert und was die Schlüssel-Wert-Ausgabe ist, das Zwischenergebnis. Schickt dazu den Text mit cat durch das Programm. In der Shell, startet
Kommentare (2)