SlickDeque: High Throughput and Low Latency Incremental Sliding-Window Aggregation
SlickDeque: High Throughput and Low Latency Incremental Sliding-Window Aggregation
复制标题
SlickDeque：高吞吐量和低延迟增量滑动窗口聚合
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Alexandros Labrinidis
中科院分区：
文献类型：
--
作者：
Anatoli U. Shein;Panos K. Chrysanthis;Alexandros Labrinidis
在最先进的科学和商业应用程序中，在线分析在很大程度上依赖于大量聚合连续查询（ACQ）的高效执行。最先进的 ACQ 处理算法（FlatFIT、TwoStacks 和 DABA）中使用增量滑动窗口计算，以避免每次更新时从头开始重新评估窗口的聚合值。 FlatFIT 和 TwoStacks 旨在提高吞吐量，DABA 旨在最大限度地减少延迟，同时所有进程可逆和不可逆聚合统一。在本文中，我们提出了一种新颖的算法 SlickDeque，它区分可逆和不可逆聚合之间的执行，并为这两种类型提供更好的吞吐量和延迟。此外，我们的方法需要更少的内存并有效地支持多 ACQ 处理。我们从理论上展示了 SlickDeque 的时间和空间复杂度优势，并使用实际工作负载进行实验验证。具体来说，与最先进的方法相比，我们的方法平均延迟峰值降低了 283%，同时在单个查询环境中实现了高达 19% 的吞吐量改进，在多查询环境中实现了高达 345% 的改进，同时所需的内存最多减少了 5 倍。
Online analytics, in most advanced scientific and business applications, rely heavily on the efficient execution of large numbers of Aggregate Continuous Queries (ACQs). Incremental slidingwindow computation is used in the state-of-the-art ACQ processing algorithms (FlatFIT, TwoStacks, and DABA) to avoid the reevaluation of the aggregate value of the window from scratch on every update. FlatFIT and TwoStacks aim to increase throughput, and DABA to minimize latency, while all process invertible and non-invertible aggregates uniformly. In this paper, we propose a novel algorithm, SlickDeque, that distinguishes the execution between invertible and non-invertible aggregates and offers better throughput and latency for both types. In addition, our method requires less memory and efficiently supports multi-ACQ processing. We theoretically show the time and space complexity advantages of SlickDeque and experimentally validate them using a real workload. Specifically, our approach maintains 283% lower latency spikes on average while achieving up to 19% throughput improvement in a single query environment and up to 345% improvement in amulti-query environment over the state-of-the-art approaches along with requiring up to 5 times less memory.