Verschachtelte Parallelität und Kontrollfluss in Big-Data-Analysesystemen

Over the last 15 years, numerous distributed dataflow systems appeared for large-scale data analytics, such as Apache Flink and Apache Spark. Users of such systems write data analysis programs in a (more or less) high-level API, while the systems take care of the low-level details of executing the programs in a scalable way on a cluster of machines. The systems' APIs consist of distributed collection types (or distributed matrix, graph, etc. types), and corresponding parallel operations. Distributed dataflow systems work well for simple programs, which are straightforward to express by just a few of the system-provided parallel operations. However, modern data analytics often demands the composition of larger programs, where 1) parallel operations are surrounded by control flow statements (e.g., in iterative algorithms, such as PageRank or K-means clustering), and/or 2) parallel operations are nested into each other. In such cases, an unpleasant trade-off appears: we lose either performance or ease-of-use: If users compose these complex programs in a straightforward way, they run into performance issues. Expert users might be able to solve the performance issues, albeit at the cost of a significant effort of delving into low-level execution details. In this thesis, we solve this trade-off for the case of control flow statements as follows: Our system allows users to express control flow with easy-to-use, standard, imperative control flow constructs, and it compiles the program into a single dataflow job. Having a single job eliminates the job launch overhead from iteration steps, and enables several loop optimizations. We compile through an intermediate representation based on static single assignment form, which allows us to handle all the standard imperative control flow statements in a uniform way. A run-time component of our system coordinates the distributed execution of control flow statements, using a novel coordination algorithm, which leverages our intermediate representation to handle any imperative control flow. Furthermore, for handling nested parallel operations, we propose a compilation technique that flattens a nested program, i.e., creates an equivalent flat program where there is no nesting of parallel operations. The flattened program can then be executed on a standard distributed dataflow system. Our main design goal was to enable users to nest any data analysis program inside a parallel operation without changes, i.e., to not introduce significant restrictions on how the system's API can be used at inner nesting levels. An important example is that, contrary to previous systems that perform flattening, we can even handle programs where there is an iterative algorithm at inner nesting levels. We also show three optimizations, which solve performance problems that arise when applying the flattening technique in the context of distributed dataflow systems.In den letzten 15 Jahren sind zahlreiche verteilte Datenflusssysteme für die groß angelegte Datenanalyse entstanden, wie Apache Flink und Spark. Die Benutzer solcher Systeme schreiben Datenanalyseprogramme in einer (mehr oder weniger) hochrangigen API, und die Systeme kümmern sich um die Low-Level-Details der Ausführung der Programme in einer skalierbaren Weise auf einem Cluster von Maschinen. Die APIs der Systeme bestehen aus verteilten Sammlungstypen (oder verteilten Matrix-, Graphen- usw. Typen) und dazugehörigen parallelen Operationen. Verteilte Datenflusssysteme eignen sich gut für einfache Programme, die sich leicht durch einige wenige der vom System angebotenen parallelen Operationen ausdrücken lassen. Die moderne Datenanalyse erfordert jedoch häufig die Komposition größerer Programme, in denen 1) parallele Operationen von Kontrollflussanweisungen umgeben sind (z.B. in iterativen Algorithmen wie PageRank oder K-means-Clustering), und/oder 2) parallele Operationen ineinander verschachtelt sind. In solchen Fällen kommt es zu einem unangenehmen Trade-off: Wir verlieren entweder Leistung oder Benutzerfreundlichkeit: Wenn Benutzer diese komplexen Programme auf einfache Art und Weise komponieren, stoßen sie auf Leistungsprobleme. Erfahrene Benutzer können die Leistungsprobleme lösen, wenn auch um den Preis, dass sie sich mit den Details der Ausführung auf niedriger Ebene befassen müssen. In dieser Arbeit lösen wir diesen Trade-off für den Fall von Kontrollflussanweisungen wie folgt: Unser System ermöglicht es den Benutzern, den Kontrollfluss mit einfach verwendbaren, standardmäßigen, imperativen Kontrollflusskonstrukten auszudrücken, und es kompiliert das Programm in einen einzelnen Datenflussjob. Dieser Einzelne Job eliminiert den Job-Start-Overhead von Iterationsschritten und ermöglicht verschiedene Schleifenoptimierungen. Wir kompilieren über eine Zwischenrepräsentation, die auf der Static-Single-Assignment-Darstellung basiert, und es uns ermöglicht alle standardmäßigen imperativen Kontrollflussanweisungen auf eine Weise zu behandeln. Eine Laufzeitkomponente unseres Systems koordiniert die verteilte Ausführung des Kontrollflusses mit Hilfe eines neuartigen Koordinationsalgorithmus, der unsere Zwischenrepräsentation nutzt, um beliebigen imperativen Kontrollfluss zu verarbeiten. Darüber hinaus schlagen wir für den Umgang mit verschachtelten parallelen Operationen eine Kompilierungstechnik vor, die ein verschachteltes Programm abflacht, d.h. ein äquivalentes flaches Programm erzeugt, in dem es keine Verschachtelung von parallelen Operationen gibt. Das abflachte Programm kann dann auf einem standardmäßigen verteilten Datenflusssystem ausgeführt werden. Unser Hauptziel bei der Entwicklung war es, den Benutzern die Möglichkeit zu geben, jedes beliebige Datenanalyseprogramm ohne Änderungen innerhalb einer parallelen Operation zu verschachteln, d.h. keine wesentlichen Einschränkungen bei der Verwendung der API des Systems auf den inneren Verschachtelungsebenen einzuführen. Ein wichtiges Beispiel ist, dass wir sogar Programme mit einem iterativen Algorithmus auf inneren Verschachtelungsebenen handhaben können, im Gegensatz zu früheren Systemen mit Abflachung. Wir zeigen auch drei Optimierungen, die Leistungsprobleme lösen, die bei der Anwendung der Abflachungstechnik im Kontext von verteilten Datenflusssystemen auftreten