Inkrementelle Neuberechnungen in MapReduce
- PDF / 707,491 Bytes
- 11 Pages / 595.276 x 790.866 pts Page_size
- 92 Downloads / 187 Views
S C H W E R P U N K T B E I T R AG
Inkrementelle Neuberechnungen in MapReduce Johannes Schildgen · Thomas Jörg · Stefan Deßloch
Eingegangen: 8. November 2012 / Angenommen: 10. Dezember 2012 / Online publiziert: 29. Dezember 2012 © Springer-Verlag Berlin Heidelberg 2012
Zusammenfassung Das MapReduce-Programmiermodell ermöglicht die skalierbare Analyse und Transformation großer Datenmengen. Wir stellen das auf MapReduce basierende Marimba-Framework zur einfachen Entwicklung von inkrementellen, selbstwartbaren Programmen vor, welche bei Änderung von Quelldaten eine vollständige Wiederholung des MapReduce-Jobs vermeiden. Marimba wird anhand mehrerer Anwendungen illustriert und durch Leistungsmessungen evaluiert. Schlüsselwörter MapReduce · Incremental
1 Einleitung MapReduce ist ein Programmiermodell für die Verarbeitung großer Datenmengen in Rechenclustern, das im Jahr 2004 von Google vorgestellt wurde [3]. Eine zentrale Eigenschaft des MapReduce-Programmiermodells ist es, dass MapReduce-Programme parallel, auf einer Vielzahl von Rechnern ausgeführt werden können. MapReduce eignet sich für verschiedenste Berechnungsprobleme. In diesem Artikel werden wir auf einige typische Anwendungsfälle J. Schildgen () · S. Deßloch AG Heterogene Informationssysteme, Technische Universität Kaiserslautern, P.O. Box 3049, 67663 Kaiserslautern, Deutschland e-mail: [email protected] S. Deßloch e-mail: [email protected] T. Jörg Google, Dienerstraße 12, 80331 München, Deutschland e-mail: [email protected]
näher eingehen. Wir werden die Berechnung von WortHistogrammen und invertierten Link-Graphen aus Sammlungen von Web-Seiten betrachten, die Berechnung von Freundesfreunden in sozialen Netzwerken, sowie die Berechnung der Auftrittswahrscheinlichkeit bestimmter Worte im Satzzusammenhang. Die Eingabedaten für MapReduce-Berechnungen liegen üblicherweise in verteilten Dateisystemen oder Key-ValueDatenbanken vor. In der Regel ändern sich die Eingabedaten kontinuierlich, beispielsweise wenn Seiten im Web aktualisiert werden oder neue Beziehungen in sozialen Netzwerken entstehen. Mit der Veränderung der Eingabedaten, die einer MapReduce-Berechnung zugrunde liegen, verliert das Berechnungsergebnis an Aktualität und muss daher regelmäßig aufgefrischt werden. Dies kann erreicht werden, indem das MapReduce-Programm von Zeit zu Zeit erneut ausgeführt und das Ergebnis vollständig neu berechnet wird. Da sich die Eingabedaten in der Regel nur langsam verändern, ist eine vollständige Neuberechnung häufig keine effiziente Lösung. Es kann erheblich günstiger sein, das zuvor berechnete Ergebnis entsprechend der Änderungen in den Eingabedaten anzupassen. Dieser Ansatz wird als inkrementelle Neuberechnung bezeichnet. In diesem Artikel schlagen wir einen Ansatz zur inkrementellen Neuberechnung in MapReduce vor, der von Konzepten zur inkrementellen Wartung materialisierter Sichten in relationalen Datenbanksystemen inspiriert wurde. Dieser wird in Abschn. 2 zunächst beispielhaft anhand zweier MapReduce-Anwendungsfälle erläutert. Anschließend werden Reg
Data Loading...
