Please note: This master’s thesis presentation will be given online.
Omar Farhat, Master’s candidate
David R. Cheriton School of Computer Science
Modern stream processing engines (SPEs) process large volumes of events propagated at high velocity through multiple queries. By continuously receiving watermarks, which are marker events injected into the stream to signify that no further events are expected beyond a designated timestamp, SPEs can infer stream progress to correctly process window operators. While stream progress is useful information for query execution, it is only utilized to ensure input completion. We argue that to improve performance, stream progress should be leveraged in the design of SPE subsystems. In this thesis, we demonstrate the significant advantages of leveraging stream progress to solve two important SPE problems: query scheduling, and query sample processing.
First, existing SPE schedulers generally aim to minimize query output latency by minimizing, in turn, the mean propagation delay of events in query pipelines. However, for queries containing commonly used blocking operators such as windows, we show that a superior approach would be to prioritize the queries based on stream progress. Through the design and development of Klink, we leverage stream progress to unblock window operators and to rapidly propagate the events to output operators.
Secondly, sample query processing limits input to only a subset of events such that the sample is statistically representative of the input while ensuring output accuracy guarantees. However, output latency can be significantly increased because relevant watermarks can suffer from large ingestion delay due to long or bursty network latencies. Window computations that account for stragglers can add significant latency while providing inconsequential accuracy improvement. We propose Aion, an algorithm that utilizes sampling to provide approximate answers with low latency by minimizing the effect of stragglers through leveraging control over stream progress.
We integrate Klink and Aion into the popular open-source SPE Apache Flink. We demonstrate that Klink delivers hefty performance gains on benchmark workloads, reducing mean and tail query latencies by up to 60% over existing scheduling policies. Similarly, using different benchmark workloads, we demonstrate that Aion reduces stream output latency by up to 85% while providing 95% accuracy guarantees.
200 University Avenue West
Waterloo, ON N2L 3G1