UNIVERSITÄTSBIBLIOTHEK

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Johannes Schildgen
URN (permanent link):urn:nbn:de:hbz:386-kluedo-38169
Advisor:Stefan Deßloch, Thomas Jörg
Document Type:Master's Thesis
Language of publication:German
Publication Date:2014/06/29
Year of Publication:2012
Publishing Institute:Technische Universität Kaiserslautern
Granting Institute:Technische Universität Kaiserslautern
Date of the Publication (Server):2014/06/30
Number of page:XII, 60
Faculties / Organisational entities:Fachbereich Informatik
DDC-Cassification:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 10.09.2012