Automating Incremental and Asynchronous Evaluation for Recursive Aggregate Data Processing
Automating Incremental and Asynchronous Evaluation for Recursive Aggregate Data Processing
复制标题
DOI：
10.1145/3318464.3389712
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Qiange Wang;Yanfeng Zhang;Hao Wang;Liang Geng;Rubao Lee;Xiaodong Zhang;Ge Yu
中科院分区：
文献类型：
--
作者：
Qiange Wang;Yanfeng Zhang;Hao Wang;Liang Geng;Rubao Lee;Xiaodong Zhang;Ge Yu
在数据库和大规模数据分析中，递归聚合处理起着重要的作用，它通常在增量计算框架下实现，并以同步和/或异步方式执行。我们确定了现有递归聚合数据处理中的三个障碍。首先，处理范围很大程度上局限于单调程序。其次，检查异步处理的单调性和正确性的条件是复杂的，并且是手工完成的。第三，由于同步和异步执行的分离，执行引擎可能不是最优的。本文为检验单调甚至非单调的递归聚合程序是否可以增量异步执行并得到正确结果的条件奠定了分析基础。我们设计并实现了一个条件验证工具，可以自动检查给定程序是否满足条件。我们进一步提出了一个统一的同步-异步引擎来执行这些程序以获得高性能。为了将所有这些有效的方法集成在一起，我们开发了一个分布式数据记录系统，称为PowerLog。我们的评估表明，PowerLog在单调和非单调递归程序上都优于三个具有代表性的Datalog系统。
In database and large-scale data analytics, recursive aggregate processing plays an important role, which is generally implemented under a framework of incremental computing and executed synchronously and/or asynchronously. We identify three barriers in existing recursive aggregate data processing. First, the processing scope is largely limited to monotonic programs. Second, checking on conditions for monotonicity and correctness for async processing is sophisticated and manually done. Third, execution engines may be suboptimal due to separation of sync and async execution. In this paper, we lay an analytical foundation for conditions to check if a recursive aggregate program that is monotonic or even non-monotonic can be executed incrementally and asynchronously with its correct result. We design and implement a condition verification tool that can automatically check if a given program satisfies the conditions. We further propose a unified sync-async engine to execute these programs for high performance. To integrate all these effective methods together, we have developed a distributed Datalog system, called PowerLog. Our evaluation shows that PowerLog can outperform three representative Datalog systems on both monotonic and non-monotonic recursive programs.