Search

Stream Processing Engines (SPEs) execute long-running queries on unbounded data streams. They follow an interpretation-based processing model and do not perform runtime optimizations. This limits the utilization of modern hardware and neglects changing data characteristics at runtime. In this paper, we present Grizzly, a novel adaptive query compilation-based SPE, to enable highly efficient query execution. We extend query compilation and task-based parallelization for the unique requirements of stream processing and apply adaptive compilation to enable runtime re-optimizations. The combination of light-weight statistic gathering with just-in-time compilation enables Grizzly to adjust to changing data-characteristics dynamically at runtime. Our experiments show that Grizzly outperforms state-of-the-art SPEs by up to an order of magnitude in throughput.

International audience; The Internet of Things (IoT) presents a novel computing architecture for data management: a distributed, highly dynamic, and heterogeneous environment of massive scale. Applications for the IoT introduce new challenges for integrating the concepts of fog and cloud computing as well as sensor networks in one unified environment. In this paper, we highlight these major challenges and outline how existing systems handle them. To address these challenges, we introduce the NebulaStream platform, a general purpose, end-to-end data management system for the IoT. NebulaStream addresses the heterogeneity and distribution of compute and data, supports diverse data and programming models going beyond relational algebra, deals with potentially unreliable communication, and enables constant evolution under continuous operation. In our evaluation, we demonstrate the effectiveness of our approach by providing early results on partial aspects.

Evaluating modern stream processing systems in a reproducible manner requires data streams with different data distributions, data rates, and real-world characteristics such as delayed and out-of-order tuples. In this paper, we present an open source stream generator which generates reproducible and deterministic out-of-order streams based on real data files, simulating arbitrary fractions of out-of-order tuples and their respective delays.

Window aggregation is a core operation in data stream processing. Existing aggregation techniques focus on reducing latency, eliminating redundant computations, and minimizing memory usage. However, each technique operates under different assumptions with respect to workload characteristics such as properties of aggregation functions (e.g., invertible, associative), window types (e.g., sliding, sessions), windowing measures (e.g., time- or count-based), and stream (dis)order. Violating the assumptions of a technique can deem it unusable or drastically reduce its performance. In this paper, we present the first general stream slicing technique for window aggregation. General stream slicing automatically adapts to workload characteristics to improve performance without sacrificing its general applicability. As a prerequisite, we identify workload characteristics which affect the performance and applicability of aggregation techniques. Our experiments show that general stream slicing outperforms alternative concepts by up to one order of magnitude.

Processor manufacturers build increasingly specialized processors to mitigate the effects of the power wall in order to deliver improved performance. Currently, database engines have to be manually optimized for each processor which is a costly and error prone process. In this paper, we provide a summary of our recent VLDB Journal publication, where we propose concepts to adapt to performance enhancements of modern processors and to exploit their capabilities automatically. Our key idea is to create processor-specific code variants and to learn a well-performing code variant for each processor. These code variants leverage various parallelization strategies and apply both generic and processor-specific code transformations. We observe that performance of code variants may diverge up to two orders of magnitude. Thus, we need to generate custom code for each processor for peak performance. Hawk automatically finds efficient code variants for CPUs, GPUs, and MICs.

Processor manufacturers build increasingly specialized processors to mitigate the effects of the power wall in order to deliver improved performance. Currently, database engines have to be manually optimized for each processor which is a costly and error prone process. In this paper, we provide a summary of our recent VLDB Journal publication, where we propose concepts to adapt to performance enhancements of modern processors and to exploit their capabilities automatically. Our key idea is to create processor-specific code variants and to learn a well-performing code variant for each processor. These code variants leverage various parallelization strategies and apply both generic and processor-specific code transformations. We observe that performance of code variants may diverge up to two orders of magnitude. Thus, we need to generate custom code for each processor for peak performance. Hawk automatically finds efficient code variants for CPUs, GPUs, and MICs.

Parallel dataflow systems have become a standard technology for large-scale data analytics. Complex data analysis programs in areas such as machine learning and graph analytics often involve control flow, i.e., iterations and branching. Therefore, systems for advanced analytics should include control flow constructs that are efficient and easy to use. A natural approach is to provide imperative control flow constructs similar to those of mainstream programming languages: while-loops, if-statements, and mutable variables, whose values can change between iteration steps. However, current parallel dataflow systems execute programs written using imperative control flow constructs by launching a separate dataflow job after every control flow decision (e.g., for every step of a loop). The performance of this approach is suboptimal, because (a) launching a dataflow job incurs scheduling overhead; and (b) it prevents certain optimizations across iteration steps. In this paper, we introduce Labyrinth, a method to compile programs written using imperative control flow constructs to a single dataflow job, which executes the whole program, including all iteration steps. This way, we achieve both efficiency and ease of use. We also conduct an experimental evaluation, which shows that Labyrinth has orders of magnitude smaller per-iteration-step overhead than launching new dataflow jobs, and also allows for significant optimizations across iteration steps.

Regular path queries (RPQs) have quickly become a staple to explore graph databases. SPARQL 1.1 includes prop- erty paths, and so now encompasses RPQs as a fragment. Despite the extreme utility of RPQs, it can be exceedingly difficult for even experts to formulate such queries. It is next to impossible for non-experts to formulate such path queries. As such, several visual query systems (VQSs) have been proposed which simplify the task of constructing path queries by directly manipulating visual objects representing the domain elements. The queries generated by VQSs may, however, have many commonalities that can be exploited to optimize globally. We introduce Tasweet, a framework for optimizing “disjunctive” path queries, which detects the commonalities among the queries to find a globally opti- mized execution plan over the plan spaces of the constituent RPQs. Our results show savings in edge-walks / time-to- completion of 59%.

With the rise in adoption of massive graph data, it be- comes increasingly important to design graph processing algorithms which have predictable behavior as the graph scales. This work presents an initial study of stability in the context of a schema-driven synthetic graph generation. Specifically, we study the design of algorithms which gener- ate high-quality sequences of graph instances. Some desir- able features of these sequences include monotonic contain- ment of graph instances as they grow in size and consistency of structural properties across the sequence. Such stabil- ity features are important in understanding and explaining the scalability of many graph algorithms which have cross- instance dependencies (e.g., solutions for role detection in dynamic networks and graph query processing). We imple- ment a preliminary approach in the recently proposed open- source synthetic graph generator gMark and demonstrate its viability in generating stable sequences of graphs.

With the recent resurgence of interest in graph data man- agement, there has been a flurry of research on the design and engineering of graph query languages. On the design side, there is a large body of theoretical results that have been obtained regarding graph languages. On the engineer- ing side, many sophisticated scalable solutions for graph query processing have been developed and put into practice. While both areas are focusing on the study of graph query languages, there has been relatively little work bridging the results on both sides. This tutorial will survey the state of the art in this landscape with a particular focus on uncovering and highlighting indicative research issues that are ripe for collaboration and cross-fertilization between the engineering and theoretical studies of graph database systems.

Processor manufacturers build increasingly specialized processors to mitigate the effects of the power wall to deliver improved performance. Currently, database engines are manually optimized for each processor: A costly and error prone process. In this paper, we propose concepts to enable the database engine to perform per-processor optimization automatically. Our core idea is to create variants of generated code and to learn a fast variant for each processor. We create variants by modifying parallelization strategies, specializing data structures, and applying different code transformations. Our experimental results show that the performance of variants may diverge up to two orders of magnitude. Therefore, we need to generate custom code for each processor to achieve peak performance. We show that our approach finds a fast custom variant for multi-core CPUs, GPUs, and MICs., Comment: 22 pages

The Internet of Things (IoT) consists of billions of devices which form a cloud of network-connected sensor nodes. These sensor nodes supply a vast number of data streams with massive amounts of sensor data. Real-time sensor data enables diverse applications including traffic-aware navigation, machine monitoring, and home automation. Current stream processing pipelines are demand-oblivious, which means that they gather, transmit, and process as much data as possible. In contrast, a demand-based processing pipeline uses requirement specifications of data consumers, such as failure tolerances and latency limitations, to save resources. In this thesis, we present an end-to-end architecture for demand-based data stream gathering, processing, and transmission. Our solution unifies the way applications express their data demands, i.e., their requirements with respect to their input streams. This unification allows for multiplexing the data demands of all concurrently running applications. On sensor nodes, we schedule sensor reads based on the data demands of all applications, which saves up to 87% in sensor reads and data transfers in our experiments with real-world sensor data. Our demand-based control layer optimizes the data acquisition from thousands of sensors. We introduce time coherence as a fundamental data characteristic, which is the delay between the first and the last sensor read that contribute values to a tuple. A large scale parameter exploration shows that our solution scales to large numbers of sensors and operates reliably under varying latency and coherence constraints. On stream analysis systems, we tackle the problem of efficient window aggregation. We contribute a general aggregation technique, which adapts to four key workload characteristics: Stream (dis)order, aggregation types, window types, and window measures. Our experiments show that our solution outperforms alternative solutions by an order of magnitude in throughput, which prevents expensive system scale-out. We further derive data demands from visualization needs of applications and make these data demands available to streaming systems such as Apache Flink. This enables streaming systems to preprocess data with respect to changing visualization needs. Experiments show that our solution reliably prevents overloads when data rates increase. Im Internet der Dinge (engl. Internet of Things/IoT) fungieren Milliarden von Geräten als Sensorknoten und formen eine Datenwolke (engl. Cloud). Diese Sensorknoten produzieren in Echtzeit eine Vielzahl von Datenströmen mit enormen Datenmengen und ermöglichen somit verschiedenste Anwendungen, wie die Automation von Gebäuden, die Überwachung von Maschinen und eine Navigation auf Basis aktueller Verkehrsdaten. Momentan werden in der Regel bedarfsunabhängig so viele Sensordaten wie möglich erhoben. Im Gegensatz dazu steht ein bedarfsorientiertes System, welches Anforderungsspezifikationen von Datennutzern, wie zum Beispiel Fehlertoleranzen und zulässige Latenzen, verwendet, um Ressourcen zu sparen. Die vorliegende Arbeit stellt eine Ende-zu-Ende Architektur vor, mit der Sensordaten bedarfsabhängig erhoben, übertragen und verarbeitet werden können. Der Datenbedarf einer Anwendung ergibt sich aus den Anforderungen an die Eingabedatenstöme. Die vorgestellte Lösung vereinheitlicht die Spezifikation des Datenbedarfs, sodass der Bedarf aller laufenden Anwendungen gebündelt werden kann. An Sensorknoten können so Lesevorgänge abhängig vom gemeinsamen Bedarf aller Anwendungen ausgeführt werden. In Experimenten ergab sich dadurch eine Einsparung von bis zu 87% des Datenverkehrs. Ein neuartiges Sensorkontrollsystem optimiert die Datenerhebung von einer Vielzahl von Sensorknoten und etabliert die zeitliche Kohärenz als essentielle Eigenschaft von Datentupeln. Die zeitliche Kohärenz beschreibt die Verzögerung zwischen dem ersten und letzten Lesevorgang, der Sensorwerte zu einem Tupel beisteuert. Eine umfassende Untersuchung zeigt, dass das System zu tausenden Sensorknoten skaliert und auch bei variierenden Rahmenbedingungen effizient ist. Zur Optimierung der Performanz von Systemen zur Datenstromenanalyse wird eine allgemeine Aggregationstechnik vorgestellt. Diese passt sich automatisch an die zeitliche Sortierung von Datenströmen, die Art der Aggregationsfunktionen, die Art der Fenster und die Dimensionen, in denen Fenster definiert sind, an. In Experimenten verzehnfachte dieser adaptive Ansatz den Datendurchsatz im Vergleich zu alternativen Techniken. Abschließend betrachtet die vorliegende Arbeit den Datenbedarf von Anwendungen, die Datenstöme in Echtzeit visualisieren. Dabei wird der Datenbedarf von Visualisierungseinstellungen abgeleitet, welche von Benutzern jederzeit interaktiv verändert werden können, und dann Systemen zur Datenstromanalyse, wie zum Beispiel Apache Flink, bereitgestellt. So können diese Systeme große Datenmengen bedarfsorientiert und in Echtzeit vorverabeiten. Experimete zeigen, dass die gezeigte Lösung auch bei steigenden Datenraten eine Systemüberlastung verhindert.

Correlated failures in large-scale clusters have significant effects onsystems’ availability, especially for streaming data applications thatrun continuously and require low processing latency. Most stateof-the-art distributed stream processing engines (DSPEs) adopt ablocking recovery paradigm, which, upon correlated failure, wouldblock the progress of recovery until sufficient new resources forrecovery are available. As the arrival of new resources is usuallyprogressive, a blocking paradigm fails to minimize the recoverylatency. To address this problem, we propose a progressive andquery-centric recovery paradigm where the recovery of the failedoperators would be carefully scheduled to progressively recover theoutputs of queries as early as possible based on the current availabilityof resources. In this work, we propose and implement afault-tolerance framework which supports progressive recovery aftercorrelated failures with minimum overhead during the system’snormal execution. We also formulate the new problem of recoveryscheduling under correlated failures and design effective algorithmsto optimize the recovery latency. The proposed methods areimplemented on Apache Storm and preliminary experiments areconducted to verify their validity