Compiling and Optimizing Iterative Data Analysis Programs with Shared State on Evolving Datasets
Final Report Abstract
Am Fachgebiet DIMA wurde innerhalb des Stratosphere Projekts an der Optimierung und Parallelisierung von deklarativen Datenflussprogrammen auf einer massiv parallelen, ausfallsicheren und adaptiven Architektur gearbeitet. Hierbei wurde das PACT (Parallelization Contracts) Programmiermodell eingeführt, welches die Ideen des map-reduce Modells weiter führt. Im Gegensatz zu map-reduce, ist der Anwender nicht an ein statisches Ausführungsmodell gebunden sondern kann beliebige azyklische Datenflussgraphen erstellen. Hierfür steht ein erweitertes Sortiment an Operatoren, insbesondere Operatoren mit mehreren Eingängen, wie z.B.: dem match Operator, welcher die Semantik eines relationalen joins abbildet. Für die deklarative beschriebenen, logischen Operatoren, wird anhand von Kostenbasierter Optimierung ein entsprechender physikalischer Ausführungsplan erstellt. Hierbei wird auch über die konkreten Implementierungen entschieden (z.B.: Sort-merge join vs. Hash-join). Vom Anwender definierte Funktionen innerhalb bilden eine Optimierungsbarriere für das Verschieben von Operatoren, um z.B.: Daten möglichst früh innerhalb des Datenflusses zu filtern. Innerhalb der Forschung, wurde ein Verfahren zur Analyse des vom Benutzer geschrieben Quellcodes entwickelt, dass es ermöglicht die jeweiligen Typen der Eingehenden und Ausgehenden Elemente eines Operators zu bestimmen und damit Operator neu Ordnung auch über Anwender spezifischen Code zu ermöglichen. Durch die immer wichtiger werdende Anwendung von Datenflussprogrammen im Bereich der Graphen Analyse und des maschinellen Lernens, ist die effiziente Ausführung von iterativen Programmen von hoher Wichtigkeit. Durch die Unterstützung von Iterationen innerhalb der Ausführungsumgebung von Stratosphere, wird das wiederholte Ausrollen des Programmplans pro Iterationsschritt vermieden und es besteht die Möglichkeit , bestimmte Programme über Fixpunkt Berechnungen auszudrücken und damit eine abnehmende Komplexität innerhalb der fortschreitenden Iterationsschritten zu erreichen. Auf Grundlage der gesammelten Erfahrungen bei der Entwicklung des PACT Modells und von Erfahrungsberichten von Anwendern, wurde die deklarative domänenspezifische Programmiersprache für Datenfluss Systeme, genannt Emma, erforscht und entwickelt. Basierend auf der Programmiersprache Scala, welche umfangreichen Möglichkeiten zur Metaprogrammierung bietet, verbindet Emma Erkenntnisse aus den Bereichen des Übersetzerbaus und der Datenbanken. Über die Darstellung von Datenflussprogrammen über Transformationen von Listen mit sogenannten forcomprehensions, welche ein natives Konstrukt in Scala darstellen, lassen sich die Programme, ohne Änderung lokal testen, und danach direkt auf dem Datenflusssystem ausführen. Vor der Verteilten Ausführung wird das Programm hierbei in der Zwischenrepräsentation optimiert. Hierbei kommen Techniken aus dem Übersetzerbau, wie das Entfernen von nicht erreichbaren Codepfaden und traditionelle Datenbank Optimierungen, wie Caching und das Neuordnen von Operatoren und spezielle Techniken für Datenflusssysteme um die Netzwerklast zu minimieren, zum Einsatz. Die auf Emma aufbauende Matrix Abstraktion Lara, ermöglicht das deklarative spezifizieren von u.a. Algorithmen für das maschinelles Lernen. Durch die Möglichkeit zur holistischen Betrachtung von Programmen mit relationalem und linearer Algebra, ermöglicht Lara Optimierungen über deren Grenzen.
Publications
- "Massively parallel data analysis with pacts on nephele." Proceedings of the VLDB Endowment 3.1-2 (2010): 1625-1628
Alexandrov, Alexander, et al.
(See online at https://doi.org/10.14778/1920841.1921056) - "Nephele/PACTs: a programming model and execution framework for web-scale analytical processing." Proceedings of the 1st ACM symposium on Cloud computing. ACM, 2010
Battré, Dominic, et al.
(See online at https://doi.org/10.1145/1807128.1807148) - "MapReduce and PACT-Comparing Data Parallel Programming Models." BTW. 2011
Alexandrov, Alexander, et al.
- "Myriad: parallel data generation on shared-nothing architectures." Proceedings of the 1st Workshop on Architectures and Systems for Big Data. ACM, 2011
Alexandrov, Alexander, et al.
(See online at https://doi.org/10.1145/2377978.2377983) - "Opening the black boxes in data flow optimization." Proceedings of the VLDB Endowment 5.11 (2012): 1256-1267
Hueske, Fabian, et al.
(See online at https://doi.org/10.14778/2350229.2350244) - "Spinning fast iterative data flows." Proceedings of the VLDB Endowment 5.11 (2012): 1268-1279
Ewen, Stephan, et al.
(See online at https://doi.org/10.14778/2350229.2350245) - "All roads lead to Rome: optimistic recovery for distributed iterative data processing." Proceedings of the 22nd ACM international conference on Information & Knowledge Management. ACM, 2013
Schelter, Sebastian, et al.
(See online at https://doi.org/10.1145/2505515.2505753) - "Iterative parallel data processing with stratosphere: an inside look." Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. ACM, 2013
Ewen, Stephan, et al.
(See online at https://doi.org/10.1145/2463676.2463693) - "Runtime Analysis of Distributed Data Processing Programs.", PhD Workshop at VLDB. 2014
Leich, Marcus
(See online at https://doi.org/10.13140/2.1.3503.0402) - "The stratosphere platform for big data analytics." The VLDB Journal 23.6 (2014): 939-964
Alexandrov, Alexander, et al.
(See online at https://doi.org/10.1007/s00778-014-0357-y) - "Implicit parallelism through deep language embedding." Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 2015
Alexandrov, Alexander, et al.
(See online at https://doi.org/10.1145/2723372.2750543) - "Optimistic recovery for iterative dataflows in action." Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 2015
Dudoladov, Sergey, et al.
(See online at https://doi.org/10.1145/2723372.2735372) - "Bridging the gap: towards optimization across linear and relational algebra." Proceedings of the 3rd ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond. ACM, 2016
Kunft, Andreas, et al.
(See online at https://doi.org/10.1145/2926534.2926540) - "Emma in action: Declarative dataflows for scalable data analysis." Proceedings of the 2016 International Conference on Management of Data. ACM, 2016
Alexandrov, Alexander, et al.
(See online at https://doi.org/10.1145/2882903.2899396) - "BlockJoin: Efficient Matrix Partitioning Through Joins." Proceedings of the VLDB Endowment 10.13 (2017)
Kunft, Andreas, et al.
(See online at https://doi.org/10.14778/3151106.3151110)
