Ein MapReduce-basiertes Programmiermodell für selbstwartbare Aggregatsichten
- Hadoop ist ein beliebtes Framework für verteilte Berechnungen über große
Datenmengen (Big Data) mittels MapReduce. Hadoop zu verwenden ist einfach: Der
Entwickler definiert die Eingabedatenquelle und implementiert die beiden
Methoden Map und Reduce. Über die verteilte Berechnung und Fehlerbehandlung muss
er sich dabei keine Gedanken machen, das erledigt das Hadoop-Framework.
Allerdings kann die Analyse von Big Data sehr lange dauern und da sich die
Eingabedaten jede Sekunde ändern, ist es vielleicht nicht immer die beste
Idee, die vollständige Berechnung jedes Mal aufs Neue auf die kompletten
Eingabedaten anzuwenden. Es wäre geschickter, sich das Ergebnis der
vorherigen Berechnung zu betrachten und nur die Deltas zu analysieren, also
Daten, die seit der letzten Berechnung hinzugefügt oder gelöscht wurden. In dem Gebiet der
selbstwartbaren materialisierten Sichten in relationalen Datenbanksystemen gibt
es bereits mehrere Ansätze, die sich mit der Lösung dieses Problems
beschäftigen. Eine Strategie liest nur die Deltas und inkrementiert oder
dekrementiert die Ergebnisse der vorherigen Berechnung. Allerdings ist diese
Inkrement-Operation sehr teuer, deshalb ist es manchmal besser, das komplette
alte Ergebnis zu lesen und es mit den Deltas der Eingabedaten zu kombinieren.
In dieser Masterarbeit wird ein neues Framework namens Marimba vorgestellt,
welches sich genau um diese Probleme der inkrementellen Berechnung kümmert. Einen
Map\-Re\-duce-Job in Marimba zu schreiben ist genau so einfach wie einen Hadoop-Job.
Allerdings werden hier keine Mapper- und Reducer-Klasse implementiert, sondern
eine Translator- und Serializer-Klasse. Der Translator ähnelt dem Mapper: Er
bestimmt, wie die Eingabedaten gelesen und daraus Zwischenwerte berechnet
werden. Der Serializer erzeugt die Ausgabe des Jobs. Wie diese Ausgabe berechnet
wird, gibt der Benutzer durch Implementierung einiger Methoden an, um Werte zu
aggregieren und invertieren.
Vier MapReduce-Jobs, darunter auch das Paradebeispiel für MapReduce WordCount,
wurden im Marimba-Framework implementiert. Das Entwickeln von inkrementellen
Map-Reduce-Jobs ist mit dem Framework extrem einfach geworden. Außerdem konnte
mit Performanztests gezeigt werden, dass die inkrementelle Berechnung deutlich
schneller ist als eine vollständige Neuberechnung.
Ein weiterer unter den vier implementierten Jobs berechnet
Wortauftrittswahrscheinlichkeiten in geschriebenen Sätzen. Dies kann
beispielsweise für Spracherkennung verwendet werden. Wenn ein Wort in einer
gesprochenen SMS nicht richtig verstanden wurde, hilft der Algorithmus zu raten,
welches Wort am wahrscheinlichsten an einer bestimmten Stelle stehen könnte,
abhängig von den vorherigen Wörtern im Satz. Damit dieser Algorithmus auch
brauchbare Ergebnisse liefert, ist die Menge und die Qualität der Eingabedaten
wichtig. Durchaus brauchbare Ergebnisse wurden durch die Verarbeitung von
Millionen von Twitter-Feeds, die deutsche Twitter-Nutzer in den letzten Monaten
geschrieben haben, erreicht.
- The Hadoop framework for MapReduce jobs is a very popular tool for distributed
calculations over big data. Working with Hadoop is simple: Define your input
data source and implement the two methods Map and Reduce. You don't need to care
about scheduling or fault tolerance. That's what the Hadoop framework does.
But analyzing big data can be very time-consuming and as data changes
every second, it's not the best idea to do the calculation over the whole input
data again and again. Why can't we just use the old result and simply analyze
the delta, so the inserted and deleted data since the last computation? There
are many approaches for solving this problem in the area of self-maintaining
materialized views in relational databases. There's one strategy which just
reads the delta and increments or decrements the values in the previous result.
As such increments can be very expensive, it's sometimes better to use another
strategy, which reads the complete old result and combines it with the delta.
In this thesis a new framework called Marimba is presented, which cares about
all these problems and how to achieve self-maintenance. Writing a MapReduce job
in Marimba is as simple as writing a Hadoop job. Instead of implementing a
Mapper and Reducer class, a Marimba developer writes a Translator and Serializer
class. The Translator is very similar to the Mapper, it defines how to read the
input data and how to generate intermediate values. The Serializer produces the
output of the job. And how this output is calculated, the user of the framework
can tell in some methods to aggregate and invert values.
Four MapReduce-Jobs, including WordCount - the textbook example for MapReduce -
were implemented in the Marimba framework. Incremental MapReduce jobs can be
implemented easily now, but that's not all. Performance tests show that it's
much faster to do an incremental instead of a full recomputation.
Another of the four implemented jobs calculates probabilities for words in a
written sentence. This can be used in voice recognition. If you dictate the text
of an SMS and a word could not be understood correctly, the algorithm helps
guessing the word depending on the previous words in the sentence. In order to
achive good results the amount and quality of input data is important, so we
analyzed millions of Twitter feeds which people wrote in the last months.