张奕裕(1997-), 男, 博士生, 主要研究领域为系统软件, 编译优化
王归航(1997-), 男, 硕士生, 主要研究领域为系统软件, 程序语言
左志强(1986-), 男, 博士, 副研究员, CCF专业会员, 主要研究领域为系统软件, 软件工程, 程序语言
李宣东(1963-), 男, 博士, 教授, 博士生导师, CCF会士, 主要研究领域为软件工程, 形式化方法
随着新兴技术的迅速发展, 领域软件对开发效率提出了新的要求. Datalog语言作为一门具有简洁语法和良好语义的声明式编程语言, 能帮助开发人员快速开发和解决问题, 近年来越来越受到重视与欢迎. 但解决真实场景问题时, 现有的单机Datalog引擎计算规模往往受限于内存容量大小, 不具有可扩展性. 为解决上述问题, 设计并实现基于核外计算的Datalog引擎. 方法首先设计一系列计算Datalog程序所需的支持核外计算的操作算子, 然后将Datalog程序转换合成带核外计算算子的C++程序, 接着方法设计基于Hash的分区策略和基于搜索树剪枝的最少置换调度策略, 将相应的分区文件调度执行计算并得到最终结果. 基于该方法, 实现原型工具DDL (disk-based Datalog engine), 并选取广泛应用的真实Datalog程序, 在合成数据集以及真实数据集上进行实验, 实验结果体现了DDL良好性能以及高可扩展性.
As emerging technologies develop rapidly, domain software puts forward new requirements for development efficiency. In addition, as a declarative programming language with concise syntax and well-defined semantics, Datalog can help developers solve complex problems rapidly and achieve smooth development and thus has attracted wide attention in recent years. However, when solving real-world problems, the existing single-machine Datalog engines are often limited by the size of memory capacity and possess no scalability. To solve these problems, this study designs and implements a Datalog engine based on out-of-core computing. Firstly, a series of operators supporting out-of-core computing are designed to compute the Datalog program, and then the program is converted into a C++ program with the operators. Next, the study designs a partition strategy based on Hash and a minimum replacement scheduling strategy based on search tree pruning. After that, the corresponding partition files are scheduled and computed to generate the final results. Based on this method, the study establishes the prototype tool DDL (disk-based Datalog engine) and selects widely used real-world Datalog programs to conduct experiments on both synthetic and real-world datasets. The experimental results show that DDL has positive performance and high scalability.
近年来, 软件的快速发展对国民经济和社会发展起着积极的促进作用. 随着区块链, 云计算, 人工智能等新兴技术迅速发展, 这些特定领域对软件应用的需求显得尤为迫切, 而这也对领域软件开发的效率和执行性能提出了新的要求. 随着技术间的进一步融合, 领域软件面临着开发周期长, 设计复杂和开发效率低等挑战. 领域软件开发人员越来越需要编程语言提供高级抽象来帮助逻辑推理和应用的快速开发, 以此来满足日益增长的软件开发需求.
Datalog作为一门声明式编程语言, 近年来在智能合约分析[
现有Datalog引擎被广泛应用于解决真实场景问题, 常常需要面对解决计算性能差和可扩展性低的问题. 在解决实际真实的问题时, Datalog引擎往往需要处理上百条的Datalog程序, 以及包含上百万甚至千万条元组数据的输入文件. 特别地, 对于一些递归的程序(如Transitive Closure), 即使只有少量的输入数据, 但产生的中间结果或者最终结果却是扩大了上百倍[
现有的前沿工作在不同领域都设计提出了各自的Datalog引擎来解决实际的领域问题. 他们有基于单机实现的BDDBDDB[
因而基于上述的讨论, 为了能够享受单机引擎的简便以省去分布式引擎的繁琐同时使得单机引擎具有高可扩展性, 本文设计提出了基于核外计算的Datalog引擎DDL (disk-based Datalog engine). 在Datalog程序运行时, 并不是全部数据存放在内存中计算, 而只有部分数据被调入内存并执行计算, 同时在适当时候写回外存, 通过内外存的数据交换来完成整个计算[
总而言之, 本文做出了如下创新贡献.
● 设计了基于核外计算的Datalog引擎并实现了相应的原型工具DDL, 解决了单机环境下Datalog引擎面对真实场景时受限于内存大小的局限性.
● 设计实现了完成Datalog程序计算所需的核外计算的操作算子, 并提出了基于谓词属性的Hash分区策略和基于搜索树剪枝的最少置换调度策略等优化手段, 来实现DDL引擎高效的核外计算.
● 在合成的和真实的数据集上与现有先进单机Datalog引擎进行了对比实验, 表明了DDL良好的性能以及高可扩展性. 特别地, 对于小规模数据能够在内存中完成计算的, DDL引擎并没有引入过多的额外开销, 甚至在某些例子上性能更优; 而对于大规模数据发生内存溢出情况的, DDL引擎能够完成计算, 具有高可扩展性, 且性能在可接受范围内.
本文第1节介绍本文工作的相关背景知识. 第2节介绍所提出的基于核外计算的算子. 第3节介绍为提升DDL引擎性能提出的优化策略. 第4节介绍DDL引擎的设计实现. 第5节通过实验展示DDL引擎的可扩展性和性能. 第6节回顾相关工作. 第 7节对本文工作进行总结, 并提出未来工作展望.
一个Datalog程序是由有限条数量的Datalog规则以及数据事实组成. 每一条Datalog规则由3个部分构成, 分别是规则头, 连接符(:–)和规则体, 形如公式(1)所示.
其中,
下列公式(2)–公式(5)展示了一个Datalog示例程序. 该程序用来计算图中所有存在可达路径的两点.
该程序中的公式(2)和公式(3)表示的是给定数据事实, 即图中存在
Datalog引擎根据给定的数据事实和Datalog规则, 计算得到目的谓词结果. 现有的Datalog执行方法按照搜索策略可以分为两类, 一类是自底向上执行, 另一类是自顶向下执行[
给定输入的数据事实和Datalog规则, Datalog引擎递归应用Datalog规则以及数据事实以派生出更多的元组, 直到达到计算的不动点(即没有更多新的元组派生出来)停止. 自底向上执行的方法通过将Datalog程序中所有规则应用于给定的数据事实进行计算, 把满足规则的元组派生为规则头的谓词. 具体来说, 结合Datalog不动点语义进行求值, 即从只包含有给定数据事实谓词的Datalog规则开始应用, 进行迭代求值; 在每次迭代中, 所有Datalog规则都被求值, 并计算派生得到满足规则的头部谓词; 当没有更多新的头部谓词派生时, 计算达到不动点, 执行停止. 该种方法被称作为朴素法. 但显然的是, 朴素法在执行过程当中许多谓词元组进行了多次派生, 例如公式(2)–公式(5)所示的Datalog程序, 其中
为了在计算的时候尽量避免重复之前迭代中已经完成的结果, 一种更优的自底向上执行方法被提出, 叫作半朴素法[
虽然自底向上执行的半朴素法在程序的迭代计算中最小化了冗余计算的产生, 但是它并没有最小化在产生目标谓词元组结果时不相关的谓词元组派生. 例如在公式(2)–公式(5)的Datalog程序中, 需要产生以
在过去, 不少研究工作设计实现基于自顶向下计算方法的Datalog引擎[
Datalog语言可以看作是对关系代数的一种递归式扩展[
操作算子对应的Datalog规则表示与关系代数表示
操作算子 | Datalog规则表示 | 关系代数表示 |
JOIN |
|
|
Diff |
|
|
Union |
|
|
Intersection |
|
|
Projection |
|
|
Selection |
|
|
Product |
|
|
类似地, 对于完整的Datalog程序而言, 它就可以被转换为由一系列操作算子表示的关系代数. 因而一般来说, 对于Datalog引擎的实现, 只需要支持对一系列操作算子的关系代数运算就可以完成Datalog程序的计算. 即Datalog引擎先通过对Datalog程序的解析, 将其转化为由一系列操作算子表示的关系代数, 接着通过实现一系列算子操作, 完成对相关谓词的代数运算, 最后实现对Datalog程序的计算. 在DDL引擎中, 也采用了上述Datalog引擎实现的思想. 不同的是, DDL进一步通过实现了一系列支持核外计算的操作算子来实现Datalog程序的核外计算. 同时核外计算的操作算子并没有改变原先算子的计算语义, 只进行了支持核外计算的实现, 所以Datalog程序与转换后的一系列核外计算算子表示两者逻辑上是等价的, 因而对于DDL计算结果的正确性是可以得到保证的.
观察发现, 在现有的Datalog引擎计算过程中, 发生内存溢出的地方在于两两谓词之间做JOIN计算的时候产生大量的中间结果数据, 这些数据占用了大量的内存资源而导致内存溢出. 因而方法重点通过实现支持核外计算的JOIN操作来支持引擎的整体核外计算. 同时对于Datalog程序中的规则而言, 一般可以分成两类[
核外计算的JOIN算子, 其基础的设计想法是将过大的输入数据事实文件, 或者过大的临时中间文件分区, 分成多块小分区文件, 然后将其读入内存中进行JOIN计算, 并将JOIN结果写回到硬盘上存储. 以第5.3节中的Program1为例展示核外计算的JOIN操作流程图, 如
以Program1为例, 核外计算的JOIN算子操作流程图
Program1在实现上可以看作是
核外计算的SetDiff算子, 其基础的设计想法与JOIN算子是类似的, 通过将大文件分区成小文件, 然后逐一遍历组合进行SetDiff处理. 但与JOIN算子不同的是, SetDiff算子只能同时处理两个谓词关系的求差计算, 且对于同一被减分区谓词文件, 需要求其结果的交集, 同时最终结果需要将多个被减分区谓词文件的结果进行相并. 以
以
核外计算的SetDiff算子首先将
因而SetDiff算子在计算出每种组合求差集结果后, 需要将作为被减分区谓词文件
核外计算的Aggregation算子, 其基础的设计想法启发于RStream[
为了能够进一步提升DDL引擎执行核外计算的性能, 本文还提出了3点优化策略.
将大文件分区成多个小文件, 是核外计算中的关键一步. 因为无论是计算开始执行前数据事实文件过大导致无法读入内存中计算, 还是在计算执行过程中临时中间结果文件过大导致内存溢出, 都是文件过大而导致的内存溢出异常. 而如果将输入数据事实文件或者中间结果文件分成多个独立的小文件, 能够读入内存中, 那么后续的计算则可以继续进行下去. 方法支持用户自定义分区的个数大小. 在执行过程中, 方法将按照自定义的分区数量对输入文件进行均分. 而分区的个数大小影响着Datalog引擎执行的性能. 若分区的文件粒度太粗, 导致分成的文件数目虽然少, 但是每个文件依然较大, 即使在初始轮次能够参与计算, 但很快就在后续轮次中导致内存溢出, 使得引擎需要花费更多额外的开销对文件进行再分区计算; 若分区的粒度太细, 导致虽然每个文件较小, 能够轻易读入内存中并完成后续计算, 但是分区的文件数目多, 引擎需要频繁读写这些分区文件, 导致IO开销增大. 且每个分区文件太小不能充分利用内存资源. 然而在未执行计算前, 有效准确衡量分区粒度是否合适较为困难, 因为无法准确知道输入数据事实文件中数据的分布情况也不知道计算过程中临时中间结果的产生情况, 而这些只有具体执行过后, 才能得知其中所花费IO的开销. 因而不方便直接从分区粒度角度出发设计合理的分区优化策略.
分区优化策略的目的是尽可能降低因分区文件而带来的IO开销, 同时较充分利用内存资源. 方法从另一个角度进行考虑, 提出基于谓词属性的Hash分区优化策略来达到上述目的. 方法基于JOIN操作的特性, 每次选取在规则体中被谓词包含数目最多的属性值作为被Hash分区的键值(若有多个候选属性值则随机选取其中一个), 然后将其中包含该属性值的谓词数据文件进行Hash分区的优化操作. 对于每一轮参与JOIN计算的表项, 采用除留余数法, 将谓词中的元组Hash到对应的分区中, 使得后续计算只用考虑相同Hash分区中的情况, 而无需计算所有的分区文件, 降低了IO开销. 同时根据输入数据事实文件之间大小的最简比值, 作为各自期望分区的个数大小. 方法同时兼顾内存资源利用大小的影响. 但显然对于真实情况中数据分布情况, 可能会出现一次分区完成后, 导致该轮次读入内存计算的分区文件依然太大的情况. 方法会对分区文件进行再分区操作, 再分区操作与上述分区操作的区别在于, 再分区操作中将上一轮分区个数的下一个相邻的递增质数作为本轮次的分区个数, 如果依然无法读入内存, 将继续重复上述操作, 直到能够读入内存中进行计算为止. 而对于其他未涉及属性值的谓词元组, 仍然根据用户自定义的分区数量进行均分的操作.
在JOIN以及SetDiff操作前都需要一个合理的调度策略, 选择将合适的分区文件读入内存进行计算. 如果随意选择某一分区组合进入内存中进行计算, 会使得下一次分区调度需要调换的分区数量随机, 导致IO的开销额外增加, 而调度策略的目的就是在分区组合数固定的情况下尽可能减少因分区调换而导致IO次数的增加.
为了实现上述目的, 方法提出了基于搜索树剪枝的最少置换策略. 所有的分区文件按照Datalog规则中声明的谓词顺序排序, 可以形成分区组合的搜索树. 树的根节点是规则头部谓词, 树的子节点是规则体谓词. 每个谓词子节点的数目是子节点分区文件的数目. 并定义规则顺序在前谓词是在后谓词的父节点, 相反地, 在后谓词是在前谓词的子节点. 如
由于每次计算都需要加载3个谓词文件的分区文件, 例如
优化后的分区组合搜索树
因为对
观察发现要实现上述最小置换策略, 只需在常规的DFS遍历逻辑上引入一个 isIncreased 数组(bool类型)记录遍历的方向信息即可实现. 并在此基础上进一步考虑基于Hash的分区优化后, 引入hashDepth参数, 用来记录当前数据集的前hashDepth个数据集是基于Hash分区得到的, 即实现了基于搜索树剪枝的最少置换调度策略. 具体的基于搜索树剪枝的最少置换调度策略, 如算法1所示.
算法
1.
2.
3.
4.
5.
6. // do the computation
7.
8.
9.
10. partitionIndex[depth] =
11.
12.
13. isIncreased[depth] = false;
14.
15.
16. partitionIndex[depth] =
17.
18.
19. isIncreased[depth] = true;
20. }
算法从第2行开始的if语句块中首先通过遍历搜索树的前hashDepth层, 即那些经过Hash分区的分区文件, 通过在前hashDepth层的过程中保证只组合Hash地址值相同的分区文件, 而不考虑其他不相同Hash地址值的分区组合, 从而达到剪枝的目的. 算法第3行的if语句块对已经遍历到的各层进行校验, 需要保证 partitionIndex[0, depth) 范围内的序列都相等. 因为基于Hash 分区的性质, 如果范围序列不完全相同, 说明不存在JOIN的结果值, check函数返回false, 然后直接return. 当depth与maxDepth相等时(算法第5行), 说明已经得到了一个从根到叶子节点的完整路径, 就可以处理depth个数据分区的相关计算, 计算结束后返回. 若depth与maxDepth不相等, 则需要继续遍历. 如果isIncreased[depth]为true (算法第8行), 则对于第depth个数据集, 对其partition做增序遍历(算法第9行), 对第depth层的谓词, 选取其第
核外计算需要涉及大量的文件读写操作, 而文件格式上的不同表示会影响文件读写操作的性能[
基于核外计算的Datalog引擎DDL主要分为前端解析合成模块和后端核外计算模块. DDL引擎的框架流程图如
DDL引擎框架流程图
在前端解析合成模块, 方法集成Souffle工具[
对于前端Datalog程序的解析与优化模块, 方法使用现成工具Souffle生成前端分析结果. Souffle工具中对前端解析进行了大量的优化, 例如对Datalog程序规则间进行常量传播, 对最终输出结果没有贡献的谓词或者规则进行消除等, 使得后端执行的时候可以省去冗余的计算. 同时Souffle还考虑到计算硬件资源上Cache缓存和多核并行化等优势, 生成了高度优化后的RAM用来进一步合成最终的C++程序.
在前端模块, 通过设计一系列的核外计算的操作算子, 只需使得最终待编译的C++程序中是由核外计算的操作算子所表示的Datalog程序计算逻辑即可, 后续就可以交给后端部分通过编译执行实现对Datalog程序的核外计算. 而同时为了能够充分利用已有的前端分析优化结果, 且使得最终C++程序符合Datalog程序计算逻辑, 方法在利用Souffle工具生成的RAM阶段抽取满足核外计算算子操作所需的操作数, 接着采用程序合成的方法从RAM阶段合成带有核外计算算子的C++程序. 方法先通过人工观察JOIN操作, SetDiff操作以及Aggregation等操作在Souffle的RAM阶段的表示形式, 接着手动抽取出其中每种操作RAM表示形式的特点(例如, RAM中两个for 语句构成一个JOIN操作等), 然后在Souffle的RAM合成C++程序阶段时, 方法根据上述提取的特点识别每种操作对应的语句模式, 利用Souffle 提供的函数接口获取语句的操作数, 最后按照既定的模板生成核外计算算子的表示形式. 如
Datalog规则公式(5)经过Souffle转换得到的RAM表示
如
Datalog规则公式(5)用核外计算算子的表示
在编译链接得到二进制可执行文件后, 结合给定的输入数据事实文件, 即可执行后端核外计算. 考虑到方法对Datalog程序处理的通用性, 以递归的Datalog规则进行举例, 展示后端核外计算的执行流程. 如
Datalog程序公式(5)后端核外计算流程图
方法首先根据分区策略, 将参与计算的谓词文件分区, 例如将edge文件分成E1, E2等多个分区, 类似地, 对path文件(根据Datalog公式(4)知, 初始path文件由edge文件派生得到)分成P1, P2等多个分区. 因为分区后的每个分区文件大小已经能够保证被一轮执行所读入内存中进行计算, 然后通过调度策略, 从中选取合适的分区组合读入内存中, 与Delta文件(初始Delta文件由path文件派生得到)执行谓词之间的JOIN计算, 并将产生的中间结果同样按照分区策略写回到硬盘中, 即NP1, NP2 (NP 表示new_path的缩写)等, 接着将new_path 分区文件和path分区文件根据调度策略, 选择合适的分区组合读入内存中进行SetDiff的计算, 如果本轮计算中有Delta文件产生, 则将产生的Delta文件根据分区策略写回到硬盘上, 即图中的D1, D2等多个分区, 同时将其追加到path的分区文件中. 再循环到JOIN操作计算中, 调度合适的Delta分区文件和edge分区文件进入内存中进行下一轮的计算, 以此往复; 如果本轮计算中没有Delta文件产生, 则认为执行达到不动点, 计算停止, 同时输出结果文件Res_path. 值得一提的是, 由于基于Datalog程序计算逻辑, 在SetDiff操作计算后, Delta文件需要将结果追加到path文件中, 而这会导致path文件中某个分区增大导致下一轮计算中无法调入内存中进行计算, 因而方法在SetDiff操作前会对该种情况进行判断, 若存在过大的path分区文件, 则会将该path分区文件根据再分区策略进行再分区以使得其能够被加载入内存进行计算.
在前端模块, 方法复用了Souffle解析优化技术的同时, 修改了Souffle中RAM到C++的合成代码模块, 使之能够生成符合后端计算的带有核外计算算子的程序. 在后端模块, 基于上述的方法实现了核外计算算子的操作以及分区和调度的策略, 使之能够高效完成核外计算.
对Datalog引擎DDL的实验评估主要试图回答以下两个问题.
RQ1: DDL引擎可扩展性怎么样?
RQ2: DDL引擎计算性能怎么样?
所有实验都是在一台配备Intel i7-8700 3.20 GHz CPU, 16 GB内存, 1 TB SSD硬盘的计算机上进行的. 并且将DDL与目前性能先进的单机Datalog引擎Souffle[
为了更全面评估Datalog引擎的性能和可扩展性, 方法基准输入的选择借鉴了Shkapsky等人[
基准输入数据集信息
数据集类型 | 数据集名称 | Vertices | Edges |
合成数据集 | Tree11[ |
71391 | 71390 |
Grid150[ |
22801 | 45300 | |
Gnp10K[ |
10000 | 1000185 | |
真实数据集 | Wiki-Talk[ |
2394385 | 5021410 |
Cit-Patents[ |
3774768 | 16518948 | |
LiveJournal[ |
3997962 | 34681189 |
● 合成数据集部分: Tree11数据集是高度为11的树, 非叶子节点的度数是2到6之间的随机数. Grid150数据集是151×151的网格状数据. Gnp10K数据集是由采用ER模型[
● 真实数据集部分: Wiki-Talk 数据集使用了维基百科用户Talk界面的编辑历史记录, 提取了从2001年1月维基百科创建到2008年1月的所有用户及其编辑讨论的数据, 创建了一个网络. 网络中的节点表示维基百科用户, 节点
为了展示引擎计算Datalog程序的通用性, 实验选取了非递归的Datalog规则1个, 递归的Datalog规则1个和包含有MIN聚合操作的Datalog规则1个. 其中非递归的Datalog规则, 选取的是在学术界被广泛讨论应用且在领域软件例如大数据分析中被作为基础算法[
Triangle Counting Datalog规则
Transitive Closure Datalog规则
Connected Components Datalog规则
为了评估DDL引擎可扩展的能力, 实验选择了Program2 这个Datalog递归规则在3个真实数据集上进行了对比实验. 相比于非递归规则, 递归规则在计算过程中会产生更多的中间数据以及计算结果, 更能反映引擎可扩展的能力. 实验分别统计了引擎在1/6, 1/5, 1/4, 1/3, 1/2和1的输入数据集时执行的总时间, 其中OOD (out of disk)表示的是DDL引擎计算过程中耗光了所有硬盘资源仍未完成计算的情况(例如某一次计算产生的中间结果过大占用了所有硬盘资源), OOM (out of memory)表示引擎计算过程中内存发生了溢出的情况.
DDL, Souffle, μZ和BDDBDDB在不同规模的数据集下执行Program2程序的总时间
由
对于RQ1, DDL能够处理1/2的Wiki-Talk数据集, 完整的Cit-Patents数据集和1/3的LiveJournal数据集. 且对于更大规模的问题, DDL可以通过简单扩增硬盘容量的方式加以解决. 实验结果表明, DDL比现有先进的单机Datalog引擎具有更高的可扩展能力, 至少能够解决2–20倍于现有先进的单机Datalog引擎处理的问题规模, 且性能在可接受范围内.
为了评估DDL引擎的计算性能, 实验分别在3个Datalog 规则上应用了上述6个输入数据集进行了对比. 对于Program2和Program3只需要一个输入数据事实文件即可, 而对于Program1需要
DDL, Souffle, μZ和BDDBDDB在Program1, Program2和Program3上的性能表现
而对于递归程序Program2的计算性能, 由于递归计算的特性使得其与非递归计算的结果大相径庭, 即使对于3个小的合成数据集上, DDL, Souffle, μZ和BDDBDDB也出现了较大的性能差异. 特别是在Grid150数据集上DDL性能要远差于其他引擎, 而在Gnp10K数据集上DDL却要更快于Souffle和BDDBDDB, 与μZ性能接近. DDL, Souffle, μZ和BDDBDDB在Tree11上执行的时间都不到3 s, 因而在讨论中忽略不计. 在3个真实数据集上, DDL在Wiki-Talk数据集上表现要快于Souffle和BDDBDDB, 而在Cit-Patents数据集上DDL则慢于Souffle但快于BDDBDDB, 在LiveJournal数据集上DDL也要慢于Souffle. μZ引擎在3个真实数据集下均未完成计算. 同时从
Program2在不同数据集上计算的迭代轮数
数据集名称 | 迭代轮数 |
Tree11 | 12 |
Grid150 | 300 |
Gnp10K | 7 |
Wiki-Talk | 8 |
Cit-Patents | 15 |
LiveJournal | 23 |
对于含有聚合操作的Datalog程序Program3的计算性能, 可以从
对于RQ2, DDL在非递归Datalog程序小规模数据集上计算性能与Souffle, μZ和BDDBDDB相近, 在大规模数据集上更要优于其他引擎. 对于递归程序无论在什么规模数据集上, DDL性能更受限于数据集的迭代计算轮数, 对于迭代轮数少的数据集, DDL性能更优, 而对于迭代轮数多的数据集, DDL受限于IO开销导致计算性能下降. 而对于含有聚合操作的Datalog程序, DDL得益于流数据处理的核外计算方式, 使得无论在小规模合成数据集还是大规模真实数据集上性能表现都要优于Souffle.
随着Datalog在不同领域中得到广泛的应用, 研究人员在不同领域设计了特定的Datalog引擎帮助完成计算. 在单机Datalog引擎研究中, Whaley等人提出了BDDBDDB引擎[
在分布式Datalog引擎研究中, Seo等人提出了Distributed Socialite[
单机环境下的Datalog引擎, 受限于内存, 并不具备很强的可扩展性, 在面对真实场景下的问题时往往因内存溢出而无法解决. 而分布式环境下的Datalog引擎, 集群环境维护困难, 代码调试也是个很大的挑战, 同时需要花费大量的时间设计合适的分布式并行算法, 并且执行也难以找到性能瓶颈. 而本文提出的基于核外计算的Datalog引擎DDL, 享受单机环境的优点, 同时提供很高的可扩展性, 并且性能依然表现良好.
Kyrola等人提出GraphChi[
本文设计并实现了基于核外计算的Datalog引擎DDL. DDL解决现有先进的单机Datalog引擎计算规模受限于内存大小的问题, 通过核外计算手段利用硬盘大幅提升单机Datalog引擎处理计算规模. DDL将Datalog程序转换为一系列核外计算算子的表示来实现核外计算, 同时提出基于Hash的分区策略和基于搜索树剪枝的最少置换调度策略等优化手段提升引擎性能. 本文还实验评估了DDL良好的性能和高可扩展性.
本文方法和原型工具仍存在一些不足: 目前对于更复杂的Datalog程序, DDL引擎前端解析模块并不能很好处理, 存在着无法从RAM中抽取得到带有核外计算算子的表示情况. 并且对于递归规则计算上较多的中间结果存储在硬盘上仍会导致OOD情况发生而终止计算. 在未来计划进一步完善DDL引擎前端解析模块以支持更复杂的Datalog程序, 并扩展DDL使得其能支持更丰富的Datalog语法(如仿函数, 谓词组合等), 以及对暂存硬盘的中间结果作进一步的优化尽量避免OOD情况出现.
Wang K, Hussain A, Zuo ZQ, Xu GQ, Amiri Sani A. Graspan: A single-machine disk-based graph system for interprocedural static analyses of large-scale systems code. ACM SIGPLAN Notices, 2017, 52(4): 389–404. [doi: 10.1145/3093336.3037744]
Seo J, Park J, Shin J, Lam MS. Distributed socialite: A datalog-based language for large-scale graph analysis. Proceedings of the VLDB Endowment, 2013, 6(14): 1906–1917. [doi: 10.14778/2556549.2556572]
唐剑琪, 方滨兴, 胡铭曾, 王威. 核外计算中的几种I/O优化方法. 计算机研究与发展, 2005, 42(10): 1820–1825.
Tang JQ, Fang BX, Hu MZ, Wang W. Research on I/O optimizations in out-of-core computation. Journal of Computer Research and Development, 2005, 42(10): 1820–1825 (in Chinese with English abstract).
Balbin I, Ramamohanarao K. A generalization of the differential approach to recursive query evaluation. The Journal of Logic Programming, 1987, 4(3): 259–262. [doi: 10.1016/0743-1066(87)90004-5]
http://www.jos.org.cn/jos/article/abstract/19970901?st=search]]>
http://www.jos.org.cn/jos/article/abstract/19970901?st=search]]>
Ganguly S, Silberschatz A, Tsur S. A framework for the parallel processing of Datalog queries. ACM SIGMOD Record, 1990, 19(2): 143–152. [doi: 10.1145/93605.98724]
Fan ZW, Zhu JQ, Zhang ZY, Albarghouthi A, Koutris P, Patel JM. Scaling-up in-memory datalog processing: Observations and techniques. Proceedings of the VLDB Endowment, 2019, 12(6): 695–708. [doi: 10.14778/3311880.3311886]
Houtsma MAW, Apers PMG. Algebraic optimization of recursive queries. Data & Knowledge Engineering, 1992, 7(4): 299–325. [doi: 10.1016/0169-023X(92)90029-B]
https://souffle-lang.github.io/]]>
Leskovec J, Sosič R. SNAP: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology, 2017, 8(1): 1. [doi: 10.1145/2898361]