Typisierung und Skalierung von MapReduce
Zusammenfassung der Projektergebnisse
Folgende Projektziele wurden erreicht: • Ein präzises, funktionales Modell des MapReduce-Vorgangs wurde erstellt und in Haskell prototypisch implementiert. Ein wesentlicher Beitrag ist hier die präzise Typisierung der einzelnen Phasen von MapReduce. • Mit dem Modell wurde eine formale Basis fur ein Kostenmodell geschaffen, in dem die Laufzeit eines MapReduce-Vorgangs in Abhängigkeit von der Eingabegroße vorhergesagt werden kann. • Innerhalb des funktionalen Modells wurden exemplarisch vier breit anwendbare Programmtransformationen zur Optimierung des MapReduce-Vorgangs entwickelt. Davon betreffen zwei Transformationen ungeordnete und zwei geordnete Eingabedatensatze. Die Transformationen bedienen sich der in den 90er Jahren entstandenen und auf das erst später entwickelte MapReduce anwendbaren Theorie der Listenhomomorphismen. • Es wurde eine Implementierung des funktionalen Modells in Hadoop Java entwickelt. Hadoop ist die am weitesten verbreitete frei zugängliche Version von MapReduce. • In zwei Fallstudien wurden Laufzeitmessungen vorgenommen, die die Vorhersagen des Kostenmodells bestätigten. Die betrachtete Anwendung war eine Maximumsbestimmung: das Maximum eines ungeordneten Datensatzes, und die maximale Segmentsumme eines geordneten Datensatzes. Mit diesen Ergebnissen wurde das Ziel erreicht, einen präziseren Umgang mit der Entwicklung von MapReduce-Programmen zu demonstrieren und zu propagieren. Wir können uns folgende Weiterentwicklungen des Projektes vorstellen: • eine weitergehende experimentelle Evaluierung unserer Fallstudien, • eine Weiterentwicklung –und möglicherweise Vereinfachung– des Kostenmodells, • eine Implementierung der Transformationen in einem automatischen Optimierer.
Projektbezogene Publikationen (Auswahl)
-
Static Type Checking of Hadoop MapReduce Programs. In Proceedings of the International Workshop on MapReduce and its Applications (MapReduce), pages 17–24. ACM Press, June 2011
Jens Dörre, Sven Apel, and Christian Lengauer
-
Scalable Analysis of Variable Software. In Proceedings of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE), pages 81–91. ACM Press, August 2013
Jörg Liebig, Alexander von Rhein, Christian Kastner, Sven Apel, Jens Dörre, and Christian Lengauer
-
Modeling and Optimizing MapReduce Programs. Concurrency and Computation: Practice and Experience, Vol 27 Issue 7, May 2015, Pages 1734-1766. First published: 12 July 2014
Jens Dörre, Sven Apel, and Christian Lengauer
