Dynamische Ressourcenallokation für verteilte Datenflüsse

Distributed dataflow systems enable users to process large datasets in parallel on clusters of commodity nodes. Users temporarily reserve resources for their batch processing jobs in shared clusters through containers. A container in this context is an abstraction of a specific amount of resources, typically a number of virtual cores and an amount of memory. For their production batch jobs, users often have specific runtime targets and need to allocate containers accordingly. However, estimating the performance of distributed dataflow jobs is inherently difficult due to the many factors the performance depends on such as programs, datasets, systems, and resources. Additionally, there is significant performance variance in the execution of distributed dataflows in shared large commodity clusters. For these reasons, users often over-provision resources considerably to ensure the runtime targets of their production jobs are met. This behavior leads to unnecessary low resource utilizations and thereby generates needless costs. This thesis presents novel methods for predicting the performance of distributed dataflow jobs and for allocating minimal sets of resources predicted to meet users’ runtime targets. The core question addressed by this thesis is how minimal resources can be allocated automatically for a given runtime target and a production batch job of a distributed dataflow framework. To this end, this thesis contributes (1) two models for capturing the scale-out behavior of distributed dataflow jobs, a simple parameterized model of distributed processing and a nonparametric model able to interpolate arbitrary scale-out behavior given dense training data, and a method for automatically choosing between these two models, (2) different measures of the similarity between job executions and methods for selecting similar previous executions of a job as a basis for accurate performance prediction, and (3) a method for continuously monitoring a running job’s progress towards its runtime target and dynamically adjusting resource allocations based on per-stage runtime predictions. The overall solution we present in this thesis supports multiple distributed dataflow systems through the use of black-box models and can be deployed on a per-application basis in existing cluster setups. The methods presented in this thesis have been implemented in prototypes, experimentally evaluated on a commodity cluster using exemplary distributed dataflow jobs, and peer-reviewed for publication at renowned international conferences. For the experiments, we used jobs from the domains of search, relational processing, machine learning, and graph processing. We further used different datasets of these domains, ranging from 1 to 745.5 gigabytes, and up to 60 cluster nodes.Verteilte Datenflusssysteme erlauben es Nutzern, große Datenmengen parallel auf Computerclustern zu verarbeiten. Nutzer reservieren für ihre Analyseprogramme Ressourcen mittels sogenannter Container. Diese Container repräsentieren eine bestimmte Menge an Ressourcen, zum Beispiel eine bestimmte Anzahl an Prozessorkernen und eine Menge Hauptspeicher. Für produktiv eingesetzte Analyseprogramme haben Nutzer oft spezifische Laufzeitvorgaben. Es ist jedoch schwierig, das Laufzeitverhalten von verteilten Datenflussprogrammen vorher abzuschätzen, weil dieses von sehr vielen Faktoren beeinflusst wird. Einen wesentlichen Einfluss auf das Laufzeitverhalten haben neben den Programmen dabei die Datensätze, die Systeme und die Ressourcen. Zudem variiert die Ausführungsgeschwindigkeit von verteilten Datenflussprogrammen erheblich in von vielen Nutzern gemeinsam verwendeten Commodity Clustern. Daher reservieren Nutzer häufig deutlich mehr Ressourcen als erforderlich, um sicherzustellen, dass Laufzeitanforderungen eingehalten werden. Diese Vorgehensweise führt allerdings zu unnötig niedriger Ressourcenauslastung und dadurch zu unnötigen Kosten. Diese Doktorarbeit präsentiert neue Methoden zur Vorhersage der Laufzeit von verteilten Datenflussprogrammen und zur Reservierung minimaler zur Einhaltung von Laufzeitvorgaben nötiger Ressourcen. Die Forschungsfrage dieser Doktorarbeit ist demnach, wie minimal nötige Ressourcen für gegebene Laufzeitanforderungen von produktiv eingesetzten verteilten Datenflussprogrammen automatisch ausgewählt werden können. Dazu leistet die Doktorarbeit die folgenden Beiträge. (1) Es werden zwei Modelle zur Beschreibung des Skalierungsverhaltens von verteilten Datenflussprogrammen vorgestellt sowie eine Methode, um automatisch zwischen den beiden Modellen zu wählen. (2) Es werden mehrere verschiedene Maße für die Ähnlichkeit zweier Ausführungen des gleichen Datenflussprogramms präsentiert, sowie Methoden um genau diejenigen ähnlichen vorangegangenen Ausführungen als Basis für die Laufzeitvorhersage von Programmen auszuwählen, die eine hohe Vorhersagegenauigkeit versprechen. (3) Es wird eine Methode vorgestellt, die mittels Laufzeitvorhersagen für die einzelnen Teilschritte von Datenflussprogrammen abschätzt, ob ein aktuell laufendes Programm die Laufzeitvorgabe ungefähr einhalten wird, und die Menge an reservierten Ressourcen ansonsten entsprechend dynamisch anpasst. Die Lösung, die in dieser Doktorarbeit präsentiert wird, unterstützt durch den Einsatz von Blackbox-Modellen verschiedene verteilte Datenflusssysteme und kann für einzelne Anwendungen in bestehenden Cluster-Aufbauten verwendet werden. Die vorgestellten Methoden wurden prototypisch implementiert, experimentell mit beispielhaften Datenflussprogrammen sowie großen Datensätzen auf einem Commodity Cluster evaluiert und im Rahmen von Publikationen auf mehreren renommierten internationalen Konferenzen begutachtet. Für die Experimente wurden unter anderem Programme aus den Domämen relationale Datenverarbeitung, maschinelles Lernen, und Graphanalyse verwendet. Außerdem wurden verschiedene bis zu 745,5 Gigabyte große Datensätze und bis zu 60 Commodity Server verwendet.DFG, FOR 1306, Stratosphere - Information Management on the CloudBMBF, 01IS14013A, BBDC - Berliner Kompetenzzentrum für Big Dat