2023, Vol. 34
2. 计算机软件新技术国家重点实验室(南京大学), 江苏 南京 210023
2. State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210023, China
近年来, 软件的快速发展对国民经济和社会发展起着积极的促进作用. 随着区块链, 云计算, 人工智能等新兴技术迅速发展, 这些特定领域对软件应用的需求显得尤为迫切, 而这也对领域软件开发的效率和执行性能提出了新的要求. 随着技术间的进一步融合, 领域软件面临着开发周期长, 设计复杂和开发效率低等挑战. 领域软件开发人员越来越需要编程语言提供高级抽象来帮助逻辑推理和应用的快速开发, 以此来满足日益增长的软件开发需求.
Datalog作为一门声明式编程语言, 近年来在智能合约分析[1, 2], 程序分析[3–5], 网络验证[6, 7], 大数据分析[8–10], 反汇编[11]等领域得到广泛的应用, 越来越受到重视与欢迎. 归因于Datalog语言其声明式的特性, Datalog语言天生具备简洁的语法和良好的语义等优势, 从而使用Datalog语言编写程序能够带来项目开发效率的提升, 同时软件开发人员只需要关注任务是什么以及任务处理的逻辑, 而无需考虑底层具体实现的细节. 与命令式编程语言(例如C/C++, Java)命令式地一步步计算步骤不同, Datalog程序以一种声明式的方式预先指定期望的计算结果, 所需的计算由Datalog引擎自动地完成. 而Datalog引擎设计实现的优劣直接决定解决问题规模的大小以及执行性能的快慢.
现有Datalog引擎被广泛应用于解决真实场景问题, 常常需要面对解决计算性能差和可扩展性低的问题. 在解决实际真实的问题时, Datalog引擎往往需要处理上百条的Datalog程序, 以及包含上百万甚至千万条元组数据的输入文件. 特别地, 对于一些递归的程序(如Transitive Closure), 即使只有少量的输入数据, 但产生的中间结果或者最终结果却是扩大了上百倍[8]. 这些真实场景下需要面临的问题对Datalog引擎的可扩展性提出了很高的要求, 需要Datalog引擎能够处理大量数据, 同时执行的性能在可以接受范围之内.
现有的前沿工作在不同领域都设计提出了各自的Datalog引擎来解决实际的领域问题. 他们有基于单机实现的BDDBDDB[12], μZ[13], LogicBlox[14]和Souffle[3]等, 还有基于分布式系统实现的Distributed socialite[15]和BigDatalog[8]等. 基于分布式系统实现的Datalog引擎具有显著的可扩展性, Datalog引擎处理的问题规模可以随着集群的扩大而增大, 且通过对算法的分布式并行化实现使得Datalog引擎执行性能表现良好. 但基于分布式系统实现的Datalog引擎问题在于, 一是在集群上的代码调试将更加困难, 二是扩大集群以处理更大规模问题的成本将显著增加, 三是通常开发人员的开发环境并不普遍具备分布式集群的条件. 基于单机实现的Datalog引擎对使用人员更加友好, 开发人员能够简单方便易操作地通过在单机开发环境下对Datalog程序进行调试或执行计算, 而无需分布式环境下繁琐的调试部署, 且现有工作通过对Datalog引擎中数据结构的优化以及执行策略的改进, 使得其执行性能表现在可接受范围之内. 但基于单机实现的Datalog引擎问题在于, 一是处理问题的规模受限于单机内存容量的大小, Datalog引擎常因为执行过程中的内存溢出而直接终止计算, 例如BDDBDDB, μZ和SQLite引擎在面对真实的OpenJDK7数据集计算上下文敏感的指向分析时因内存溢出而无法完成计算[3]; 二是为了处理更大规模问题而扩大内存容量的成本也相对较为昂贵.
因而基于上述的讨论, 为了能够享受单机引擎的简便以省去分布式引擎的繁琐同时使得单机引擎具有高可扩展性, 本文设计提出了基于核外计算的Datalog引擎DDL (disk-based Datalog engine). 在Datalog程序运行时, 并不是全部数据存放在内存中计算, 而只有部分数据被调入内存并执行计算, 同时在适当时候写回外存, 通过内外存的数据交换来完成整个计算[16]. 由于Datalog引擎的实现可以视作一系列关系代数操作算子的具体实现(第1.3节), DDL通过设计实现了一系列完成Datalog程序计算所需的支持核外计算的操作算子. 同时DDL在Souffle基础上将Datalog程序转换合成为由这些核外计算算子表示的C++程序, 实现了完整的支持核外计算的Datalog引擎. DDL还通过设计实现基于谓词属性的Hash分区策略以及基于搜索树剪枝的最少置换分区调度策略等优化手段降低I/O开销以提升引擎执行性能. DDL引擎工作在单机环境下, 具备基于单机实现的Datalog引擎的优点, 同时使得问题处理的规模不再受限于内存的大小, 相反可以通过扩增相对便宜的硬盘容量来处理更大规模的问题.
总而言之, 本文做出了如下创新贡献.
● 设计了基于核外计算的Datalog引擎并实现了相应的原型工具DDL, 解决了单机环境下Datalog引擎面对真实场景时受限于内存大小的局限性.
● 设计实现了完成Datalog程序计算所需的核外计算的操作算子, 并提出了基于谓词属性的Hash分区策略和基于搜索树剪枝的最少置换调度策略等优化手段, 来实现DDL引擎高效的核外计算.
● 在合成的和真实的数据集上与现有先进单机Datalog引擎进行了对比实验, 表明了DDL良好的性能以及高可扩展性. 特别地, 对于小规模数据能够在内存中完成计算的, DDL引擎并没有引入过多的额外开销, 甚至在某些例子上性能更优; 而对于大规模数据发生内存溢出情况的, DDL引擎能够完成计算, 具有高可扩展性, 且性能在可接受范围内.
本文第1节介绍本文工作的相关背景知识. 第2节介绍所提出的基于核外计算的算子. 第3节介绍为提升DDL引擎性能提出的优化策略. 第4节介绍DDL引擎的设计实现. 第5节通过实验展示DDL引擎的可扩展性和性能. 第6节回顾相关工作. 第 7节对本文工作进行总结, 并提出未来工作展望.
1 背景知识 1.1 Datalog程序一个Datalog程序是由有限条数量的Datalog规则以及数据事实组成. 每一条Datalog规则由3个部分构成, 分别是规则头, 连接符(:–)和规则体, 形如公式(1)所示.
| $ H : - {B_0}, \ldots, {B_i}, \ldots, {B_n}. $ | (1) |
其中, H和
下列公式(2)–公式(5)展示了一个Datalog示例程序. 该程序用来计算图中所有存在可达路径的两点.
| ${{ edge(a, b)}}. $ | (2) |
| $ {{edge(b, c)}}. $ | (3) |
| $ {{path(X, Y) : - edge(X, Y)}}. $ | (4) |
| $ {{path(X, Y) : - path(X, Z), edge(Z, Y)}}. $ | (5) |
该程序中的公式(2)和公式(3)表示的是给定数据事实, 即图中存在a点到b点的一条边和b点到c点的一条边. 程序中的公式(4)和公式(5)表示的是Datalog规则, 存在着两个谓词关系, 即edge谓词和path谓词. 其中公式(4)规则表示的是如果X点到Y点之间存在一条边, 那么就意味着X点到Y点之间就存在着一条路径, 即该条规则通过edge谓词派生出新的path谓词; 公式(5)规则表示如果X点到Z点之间存在一条路径, 并且Z点到Y点之间存在一条边, 那么就意味着X点到Y点之间存在着一条路径, 从而该条规则就派生出新的path谓词元组path(X, Y).
1.2 Datalog执行Datalog引擎根据给定的数据事实和Datalog规则, 计算得到目的谓词结果. 现有的Datalog执行方法按照搜索策略可以分为两类, 一类是自底向上执行, 另一类是自顶向下执行[17].
1.2.1 自底向上执行给定输入的数据事实和Datalog规则, Datalog引擎递归应用Datalog规则以及数据事实以派生出更多的元组, 直到达到计算的不动点(即没有更多新的元组派生出来)停止. 自底向上执行的方法通过将Datalog程序中所有规则应用于给定的数据事实进行计算, 把满足规则的元组派生为规则头的谓词. 具体来说, 结合Datalog不动点语义进行求值, 即从只包含有给定数据事实谓词的Datalog规则开始应用, 进行迭代求值; 在每次迭代中, 所有Datalog规则都被求值, 并计算派生得到满足规则的头部谓词; 当没有更多新的头部谓词派生时, 计算达到不动点, 执行停止. 该种方法被称作为朴素法. 但显然的是, 朴素法在执行过程当中许多谓词元组进行了多次派生, 例如公式(2)–公式(5)所示的Datalog程序, 其中path(a, b), path(b, c)谓词元组在执行过程中就派生了两次, 造成了冗余的结果, 导致执行性能的低下. 产生这种冗余结果的原因在于, 朴素法在计算过程中每次迭代时都应用的是当前已知的所有事实(包括输入数据事实和派生元组事实), 不管这些谓词是否会再额外产生新的谓词.
为了在计算的时候尽量避免重复之前迭代中已经完成的结果, 一种更优的自底向上执行方法被提出, 叫作半朴素法[18, 19]. 半朴素法基于这样的观察, 只有在前一次迭代计算中产生的新元组才能在本次迭代计算中产生更多的新元组. 因而半朴素法与朴素法不同的地方在于半朴素法在每次迭代计算都只应用在前一次迭代计算中新产生的元组, 从而减少冗余的计算.
1.2.2 自顶向下执行虽然自底向上执行的半朴素法在程序的迭代计算中最小化了冗余计算的产生, 但是它并没有最小化在产生目标谓词元组结果时不相关的谓词元组派生. 例如在公式(2)–公式(5)的Datalog程序中, 需要产生以b为起始节点所能到达的所有节点集合, 而显然path(a, b)这个谓词不会也不需要参与到计算中, 但自底向上执行方法依然会在迭代计算过程产生该谓词. 而自顶向下执行的方法[17]则不会造成这种计算的冗余, 它会将条件从想要的规则向下推入可能回答该查询的规则中, 从而这些规则会创建更多子规则, 子规则依次类似的方法向下推入, 直到下推到输入的数据事实中判断是否存在满足条件的某个元组. 其中最具代表性的自顶向下执行方法是QSQ方法[20].
在过去, 不少研究工作设计实现基于自顶向下计算方法的Datalog引擎[21, 22]. 虽然自顶向下的方法更加直接产生目标谓词元组结果, 且计算过程中不会产生跟目标结果无关的冗余中间结果, 但在实际实现中较繁琐, 无法直接投入真实问题场景中开展计算, 且可优化空间小, 执行性能并不比自底向上执行更优. 相反, 自底向上的方法实现简单, 能适用真实场景问题, 存在优化空间. 现在业界主流Datalog引擎[3, 8, 14]执行方法选取大都选择了自底向上执行, 且提供丰富的优化手段, 提高执行性能. 类似地, 本文方法也基于自底向上执行的半朴素方法设计基于核外计算的Datalog引擎.
1.3 Datalog引擎实现Datalog语言可以看作是对关系代数的一种递归式扩展[23]. Datalog语言中多种语法表示能够与关系代数进行相互转换[24], 例如表1所示. 在表1中, 展示了7种操作算子对应的Datalog规则与能进行相应转换的关系代数表示. 例如对Diff操作算子而言,
|
表 1 操作算子对应的Datalog规则表示与关系代数表示 |
类似地, 对于完整的Datalog程序而言, 它就可以被转换为由一系列操作算子表示的关系代数. 因而一般来说, 对于Datalog引擎的实现, 只需要支持对一系列操作算子的关系代数运算就可以完成Datalog程序的计算. 即Datalog引擎先通过对Datalog程序的解析, 将其转化为由一系列操作算子表示的关系代数, 接着通过实现一系列算子操作, 完成对相关谓词的代数运算, 最后实现对Datalog程序的计算. 在DDL引擎中, 也采用了上述Datalog引擎实现的思想. 不同的是, DDL进一步通过实现了一系列支持核外计算的操作算子来实现Datalog程序的核外计算. 同时核外计算的操作算子并没有改变原先算子的计算语义, 只进行了支持核外计算的实现, 所以Datalog程序与转换后的一系列核外计算算子表示两者逻辑上是等价的, 因而对于DDL计算结果的正确性是可以得到保证的.
2 基于核外计算的算子设计观察发现, 在现有的Datalog引擎计算过程中, 发生内存溢出的地方在于两两谓词之间做JOIN计算的时候产生大量的中间结果数据, 这些数据占用了大量的内存资源而导致内存溢出. 因而方法重点通过实现支持核外计算的JOIN操作来支持引擎的整体核外计算. 同时对于Datalog程序中的规则而言, 一般可以分成两类[13], 一类是递归规则, 即规则递归地依赖于它自身或者依赖于它的另一条规则; 另一类是非递归规则, 即规则之间没有递归依赖关系. 递归规则的执行通常采用半朴素法进行高效计算, 其中关键的操作除了谓词之间的JOIN操作还有SetDiff操作. SetDiff操作的目的是将本轮次计算出的结果与上轮次计算出的结果求差, 用来获得每一轮次计算中新派生出的谓词元组. 而非递归规则的执行, 通常视作是谓词之间的JOIN操作. 为了支持Datalog程序规则递归和非递归的特性, 方法设计并实现了JOIN和SetDiff操作的核外计算的算子. 同时当Datalog被应用于数据分析或图计算分析等领域时, 其程序常会涉及聚合操作(例如MIN, MAX, SUM等). 为了Datalog引擎适用范围的通用性, 方法也为聚合操作设计了相应的支持核外计算的操作算子. 下面将主要描述JOIN, SetDiff以及聚合操作算子的核外计算设计. 其余操作算子或者不会进一步消耗内存空间(如Intersection, Selection等), 或者在前述算子基础上进行相同的核外计算操作(如Union, Product), 因而不再展开阐述.
2.1 JOIN核外计算的JOIN算子, 其基础的设计想法是将过大的输入数据事实文件, 或者过大的临时中间文件分区, 分成多块小分区文件, 然后将其读入内存中进行JOIN计算, 并将JOIN结果写回到硬盘上存储. 以第5.3节中的Program1为例展示核外计算的JOIN操作流程图, 如图1所示(假设R, S和T谓词的输入数据事实文件都被分成了两个分区文件).
|
图 1 以Program1为例, 核外计算的JOIN算子操作流程图 |
Program1在实现上可以看作是R, S, T表项之间JOIN操作, 找到存在三角关系的集合. 核外计算的JOIN算子首先将R, S和T谓词的输入数据事实文件按照分区策略各分成两个分区文件, 接着通过调度策略选择相应的分区文件从硬盘上读取入内存中进行JOIN计算. 调度策略显然需要依次遍历所有可能的8种组合才能不遗漏计算. 最终将每种组合的JOIN结果相并得到完整结果, 并将其写回硬盘.
2.2 SetDiff核外计算的SetDiff算子, 其基础的设计想法与JOIN算子是类似的, 通过将大文件分区成小文件, 然后逐一遍历组合进行SetDiff处理. 但与JOIN算子不同的是, SetDiff算子只能同时处理两个谓词关系的求差计算, 且对于同一被减分区谓词文件, 需要求其结果的交集, 同时最终结果需要将多个被减分区谓词文件的结果进行相并. 以
|
图 2 以
|
核外计算的SetDiff算子首先将R和T谓词的输入数据事实文件按照分区策略各分成两个分区文件, 接着通过调度策略选择相应的分区文件从硬盘上读入内存中进行SetDiff计算, 显然需要依次遍历所有可能的4种组合才能完成R和T谓词整体的SetDiff计算. 因为R谓词文件可以看成是
| $ ({R_1} \cup {R_2}) - ({T_1} \cup {T_2}) = [({R_1} - {T_1}) \cap ({R_1} - {T_2})] \cup [({R_2} - {T_1}) \cap ({R_2} - {T_2})].$ |
因而SetDiff算子在计算出每种组合求差集结果后, 需要将作为被减分区谓词文件R1和R2各自的差集相交得到结果
核外计算的Aggregation算子, 其基础的设计想法启发于RStream[10]与XStream[25]的研究工作, 通过将分区后的文件逐一采用流数据处理的方式去记录所需的聚合操作结果. 方法在内存中维护一个固定大小的流数据缓冲区, 从硬盘上读取相应的谓词分区文件到流数据缓冲区内, 并根据具体的Datalog规则记录和维护该缓冲区内相应谓词分区文件的Aggregation算子数据. 通过流数据处理方式连续读取硬盘上的所有分区文件进入缓冲区内, 从而得到完整谓词文件的Aggregation算子数据. 目前DDL引擎主要考虑的Aggregation算子包括MIN, MAX和SUM. 这3种算子在设计上是一致的, 在具体实现时根据各自算子语义的不同进行相应的计算.
3 优化策略为了能够进一步提升DDL引擎执行核外计算的性能, 本文还提出了3点优化策略.
3.1 分区策略将大文件分区成多个小文件, 是核外计算中的关键一步. 因为无论是计算开始执行前数据事实文件过大导致无法读入内存中计算, 还是在计算执行过程中临时中间结果文件过大导致内存溢出, 都是文件过大而导致的内存溢出异常. 而如果将输入数据事实文件或者中间结果文件分成多个独立的小文件, 能够读入内存中, 那么后续的计算则可以继续进行下去. 方法支持用户自定义分区的个数大小. 在执行过程中, 方法将按照自定义的分区数量对输入文件进行均分. 而分区的个数大小影响着Datalog引擎执行的性能. 若分区的文件粒度太粗, 导致分成的文件数目虽然少, 但是每个文件依然较大, 即使在初始轮次能够参与计算, 但很快就在后续轮次中导致内存溢出, 使得引擎需要花费更多额外的开销对文件进行再分区计算; 若分区的粒度太细, 导致虽然每个文件较小, 能够轻易读入内存中并完成后续计算, 但是分区的文件数目多, 引擎需要频繁读写这些分区文件, 导致IO开销增大. 且每个分区文件太小不能充分利用内存资源. 然而在未执行计算前, 有效准确衡量分区粒度是否合适较为困难, 因为无法准确知道输入数据事实文件中数据的分布情况也不知道计算过程中临时中间结果的产生情况, 而这些只有具体执行过后, 才能得知其中所花费IO的开销. 因而不方便直接从分区粒度角度出发设计合理的分区优化策略.
分区优化策略的目的是尽可能降低因分区文件而带来的IO开销, 同时较充分利用内存资源. 方法从另一个角度进行考虑, 提出基于谓词属性的Hash分区优化策略来达到上述目的. 方法基于JOIN操作的特性, 每次选取在规则体中被谓词包含数目最多的属性值作为被Hash分区的键值(若有多个候选属性值则随机选取其中一个), 然后将其中包含该属性值的谓词数据文件进行Hash分区的优化操作. 对于每一轮参与JOIN计算的表项, 采用除留余数法, 将谓词中的元组Hash到对应的分区中, 使得后续计算只用考虑相同Hash分区中的情况, 而无需计算所有的分区文件, 降低了IO开销. 同时根据输入数据事实文件之间大小的最简比值, 作为各自期望分区的个数大小. 方法同时兼顾内存资源利用大小的影响. 但显然对于真实情况中数据分布情况, 可能会出现一次分区完成后, 导致该轮次读入内存计算的分区文件依然太大的情况. 方法会对分区文件进行再分区操作, 再分区操作与上述分区操作的区别在于, 再分区操作中将上一轮分区个数的下一个相邻的递增质数作为本轮次的分区个数, 如果依然无法读入内存, 将继续重复上述操作, 直到能够读入内存中进行计算为止. 而对于其他未涉及属性值的谓词元组, 仍然根据用户自定义的分区数量进行均分的操作.
3.2 调度策略在JOIN以及SetDiff操作前都需要一个合理的调度策略, 选择将合适的分区文件读入内存进行计算. 如果随意选择某一分区组合进入内存中进行计算, 会使得下一次分区调度需要调换的分区数量随机, 导致IO的开销额外增加, 而调度策略的目的就是在分区组合数固定的情况下尽可能减少因分区调换而导致IO次数的增加.
为了实现上述目的, 方法提出了基于搜索树剪枝的最少置换策略. 所有的分区文件按照Datalog规则中声明的谓词顺序排序, 可以形成分区组合的搜索树. 树的根节点是规则头部谓词, 树的子节点是规则体谓词. 每个谓词子节点的数目是子节点分区文件的数目. 并定义规则顺序在前谓词是在后谓词的父节点, 相反地, 在后谓词是在前谓词的子节点. 如图3, 展示了第5.3节Program1中R, S和T谓词一种可能的分区组合搜索树(假设其中每个谓词都产生了两个分区文件, 并对R和S谓词进行了Hash分区操作).
|
图 3 R, S和T谓词一种可能的分区组合搜索树 |
由于每次计算都需要加载3个谓词文件的分区文件, 例如R0S0T0, 而基于深度优先的遍历会导致下一次调度的时候需要调度两个分区才能完成计算, 例如完成R0S0T1后需要计算R0S1T0, 这就导致需要置换S谓词和T谓词两个分区的文件, 而导致了IO的开销增大. 而完成所有的分区计算则需要在计算中一共调度的分区次数(不包括起始3个分区文件的调度) C1=1+2+1+3+1+2+1=11. 而使用最少置换策略, 即在每次计算时只调换其中一个分区文件即可, 完成所有分区计算所需的调度分区次数为C2= 1+1+1+1+1+1+1=7. 而基于搜索树剪枝的最少置换策略只用考虑与Hash地址相匹配的分区文件, 因而可以对搜索树进行剪枝. 在剪完枝的搜索树上, 方法选择一个最小的分区组合数作为起始点, 然后依照该起始点从叶子节点开始进行置换不同分区, 并从下往上选择节点对应的分区文件进行置换, 每次置换都保证只选择最少次数的分区进行, 如图4所示.
|
图 4 优化后的分区组合搜索树 |
因为对R谓词和S谓词进行Hash分区操作, 因而对于R和S谓词的分区文件计算只需要计算R0与S0分区和R1和S1分区, 而R0和S1以及R1和S0分支将不会产生JOIN结果, 因而可以对其剪枝. 同时在计算R0S0T0后, 基于最少置换的原则, 下一步选择T1进行置换, 而后选择R和S谓词进行置换, 以此类推. 最终基于搜索树剪枝的最少置换策略完成所有分区计算所需的调度分区次数为C3 =1+2+1=4. 通过调度分区次数就可以得知(C3 < C2 < C1 ), 在IO开销上, 基于搜索树剪枝的最少置换策略交换分区数最小, 所需IO开销最少.
观察发现要实现上述最小置换策略, 只需在常规的DFS遍历逻辑上引入一个 isIncreased 数组(bool类型)记录遍历的方向信息即可实现. 并在此基础上进一步考虑基于Hash的分区优化后, 引入hashDepth参数, 用来记录当前数据集的前hashDepth个数据集是基于Hash分区得到的, 即实现了基于搜索树剪枝的最少置换调度策略. 具体的基于搜索树剪枝的最少置换调度策略, 如算法1所示.
算法1. 基于搜索树剪枝的最少置换调度算法.
1. Schedule(depth, maxDepth, hashDepth, partitionIndex, partitionSize, isIncreased){
2. if depth ≤ hashDepth then //只组合数据集相同的index
3. if !check(partitionIndex, depth) then //保证待计算的分区序列相同
4. return;
5. if depth==maxDepth then //得到从根到叶子的路径, 执行计算
6. // do the computation
7. return;
8. if isIncreased[depth] then
9. for i = 0 to partitionSize[depth]–1 do //增序遍历
10. partitionIndex[depth] = i; //对第depth个数据集, 选择第i个分区
11. Schedule(depth+1, maxDepth, hashDepth, partitionIndex, partitionSize, isIncreased);
12. if i==partitionSize[depth]–1 then //到最大下标处, 下一次做降序遍历
13. isIncreased[depth] = false;
14. else
15. for i = partitionSize[depth]–1to 0 do //降序遍历
16. partitionIndex[depth] = i;
17. Schedule(depth+1, maxDepth, hashDepth, partitionIndex, partitionSize, isIncreased);
18. if i==0 then //到最小下标处, 下一次做增序遍历
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层的谓词, 选取其第i个partition (算法第10行), 然后继续调用Schedule函数进行递归遍历处理第depth+1层谓词(算法第11行). 当已经遍历到最大下标时, 将该数据集所对应的isIncreased置为false, 在下一次处理该数据集时, 会对index做降序遍历(算法第12和13行). 如果isIncreased[depth]为false (算法第14行), 则对于第depth个数据集对其partition做降序遍历(算法第15行), 同样地, 对第depth层的谓词, 选取其第i个partition (算法第16行), 然后继续调用Schedule函数进行递归遍历处理第depth+1层谓词(算法第17行). 当已经遍历到最小下标时, 将该数据集所对应的isIncreased置为true, 在下一次处理该数据集时, 会对index做增序遍历(算法第18和19行).
3.3 二进制格式文件读写核外计算需要涉及大量的文件读写操作, 而文件格式上的不同表示会影响文件读写操作的性能[26]. 文本格式表示便于编辑, 而二进制表示存储的是值的内部表示. 以二进制格式保存数据的速度更快, 因为不需要转换, 并且可以大块地存储数据. 且二进制格式通常占用的空间较小. 在实际的Datalog程序中谓词的属性通常由数字进行表示且数据事实文件通常较大, 因而为了能够进一步提升文件读写的性能, 方法采用二进制的格式来表示文件.
4 DDL引擎实现 4.1 DDL引擎框架基于核外计算的Datalog引擎DDL主要分为前端解析合成模块和后端核外计算模块. DDL引擎的框架流程图如图5所示.
|
图 5 DDL引擎框架流程图 |
在前端解析合成模块, 方法集成Souffle工具[27], 用于前端Datalog程序的解析和优化, 以及用于产生优化后的RAM (relational algebra machine, 关系代数机)结果. 然后方法基于RAM利用程序合成的方法实现合成自定义的带有支持核外计算的算子操作的C++代码. 在后端核外计算模块, 方法将上述C++代码结合支持核外计算的依赖库函数OOC-Lib, 编译链接得到二进制可执行文件BIN, 接着通过给定输入数据事实文件Facts, 执行上述二进制文件BIN, 运行后端核外计算并得到最终的计算结果.
4.2 前端合成模块对于前端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 提供的函数接口获取语句的操作数, 最后按照既定的模板生成核外计算算子的表示形式. 如图6所示是Datalog规则公式(5)经过Souffle转换后得到的部分RAM表示, 其中delta_path和edge已由path赋值得到. RAM中用QUERY关键字表示Datalog程序逻辑执行的开始, 首先判断delta_path和edge谓词是否为空, 在存在delta_path和edge谓词情况下, 通过两个for循环依次分别循环遍历其中delta_path 和edge谓词中的每个元组t0和t1, 然后判断t0元组中的第2个属性值是否和t1元组中的第1个属性值相同, 若相等, 则将t0元组的第1个属性值和t1元组的第2个属性值组成一个新的元组, 并判断该元组是否已经存在于path谓词中, 若不存在则将其追加到new_path元组中.
|
图 6 Datalog规则公式(5)经过Souffle转换得到的RAM表示 |
如图7所示是在图6 RAM表示上期望抽取得到的含有JOIN和SetDiff算子的表示. 首先, 将edge谓词和delta_path谓词基于edge谓词的第2个属性值和delta_path谓词的第1个属性值进行JOIN操作, 并将JOIN的结果join_res写回到new_path中, 然后将new_path谓词和path谓词进行SetDiff的操作, 并将SetDiff操作的结果setdiff_res写回到delta_path中.
|
图 7 Datalog规则公式(5)用核外计算算子的表示 |
4.3 后端核外计算模块
在编译链接得到二进制可执行文件后, 结合给定的输入数据事实文件, 即可执行后端核外计算. 考虑到方法对Datalog程序处理的通用性, 以递归的Datalog规则进行举例, 展示后端核外计算的执行流程. 如图8所示, 展示了递归的Datalog公式(5)后端核外计算执行的流程图.
|
图 8 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分区文件根据再分区策略进行再分区以使得其能够被加载入内存进行计算.
5 实验评估在前端模块, 方法复用了Souffle解析优化技术的同时, 修改了Souffle中RAM到C++的合成代码模块, 使之能够生成符合后端计算的带有核外计算算子的程序. 在后端模块, 基于上述的方法实现了核外计算算子的操作以及分区和调度的策略, 使之能够高效完成核外计算.
5.1 实验设置对Datalog引擎DDL的实验评估主要试图回答以下两个问题.
RQ1: DDL引擎可扩展性怎么样?
RQ2: DDL引擎计算性能怎么样?
所有实验都是在一台配备Intel i7-8700 3.20 GHz CPU, 16 GB内存, 1 TB SSD硬盘的计算机上进行的. 并且将DDL与目前性能先进的单机Datalog引擎Souffle[3], μZ (4.8.13版本)[13]和BDDBDDB (1.2版本)[12]进行了对比实验.
5.2 基准输入选取为了更全面评估Datalog引擎的性能和可扩展性, 方法基准输入的选择借鉴了Shkapsky等人[8]的研究工作, 类似地采用了合成数据集和真实数据集的组合. 合成数据集和真实数据集信息汇总在表2中, 表中Vertices列表示了顶点的数量, Edges列表示了边的数量. 其中合成数据集是选取自Shkapsky等人[8]的研究工作, 真实数据集是选取自Leskovec等人[28]的研究工作. 特别地, 对于3个真实数据集, 分别将其按照1–6的基数均分了每个数据集, 并各取其中一份用来后续引擎可扩展性部分的实验评估.
|
|
表 2 基准输入数据集信息 |
● 合成数据集部分: Tree11数据集是高度为11的树, 非叶子节点的度数是2到6之间的随机数. Grid150数据集是151×151的网格状数据. Gnp10K数据集是由采用ER模型[29]随机连接10000个顶点生成的图, 其中每两个顶点连接存在边的概率为0.001.
● 真实数据集部分: Wiki-Talk 数据集使用了维基百科用户Talk界面的编辑历史记录, 提取了从2001年1月维基百科创建到2008年1月的所有用户及其编辑讨论的数据, 创建了一个网络. 网络中的节点表示维基百科用户, 节点i到节点j的有向边表示用户i至少编辑过用户j的Talk界面. Cit-Patents数据集是1975–1999年之间美国专利局授予所有实用专利的引用网络. 网络中的节点表示专利, 节点i到节点j的有向边表示专利i引用了专利j的内容. LiveJournal数据集是从在线博客社区LiveJournal中的用户好友关系构建而来. 节点表示用户, 节点i和节点j存在边意味着用户i和用户j之间是好友关系.
5.3 基准Datalog规则选取为了展示引擎计算Datalog程序的通用性, 实验选取了非递归的Datalog规则1个, 递归的Datalog规则1个和包含有MIN聚合操作的Datalog规则1个. 其中非递归的Datalog规则, 选取的是在学术界被广泛讨论应用且在领域软件例如大数据分析中被作为基础算法[10, 29–31]的Triangle Counting例子, 如图9的Program1所示; 递归的Datalog规则, 选取的是具有代表性的例子Transitive Closure[8], 该程序也是区块链智能合约分析和程序分析可达性算法的基础算法, 如图10的Program2所示; 含MIN聚合操作的Datalog规则, 选取的是在图分析计算领域中被广泛使用[8, 23]的Connected Components例子, 如图11的Program3所示. Triangle Counting是用来计算图上存在三角形关系的元组, Transitive Closure是用来计算图上的传递闭包关系, Connected Components是用来计算图中存在的连通分量.
|
图 9 Triangle Counting Datalog规则 |
|
图 10 Transitive Closure Datalog规则 |
|
图 11 Connected Components Datalog规则 |
5.4 可扩展性
为了评估DDL引擎可扩展的能力, 实验选择了Program2 这个Datalog递归规则在3个真实数据集上进行了对比实验. 相比于非递归规则, 递归规则在计算过程中会产生更多的中间数据以及计算结果, 更能反映引擎可扩展的能力. 实验分别统计了引擎在1/6, 1/5, 1/4, 1/3, 1/2和1的输入数据集时执行的总时间, 其中OOD (out of disk)表示的是DDL引擎计算过程中耗光了所有硬盘资源仍未完成计算的情况(例如某一次计算产生的中间结果过大占用了所有硬盘资源), OOM (out of memory)表示引擎计算过程中内存发生了溢出的情况.
图12展示了在Program2程序下, DDL, Souffle, μZ和BDDBDDB在不同规模的数据集下总执行计算时间.
|
图 12 DDL, Souffle, μZ和BDDBDDB在不同规模的数据集下执行Program2程序的总时间 |
由图12可见, 通过在不同规模数据集下的执行情况, 来反映出DDL, Souffle, μZ和BDDBDDB之间计算的可扩展能力差异. 在Wiki-Talk数据集下, Souffle, μZ和BDDBDDB在1/6处的计算就已经OOM, 而DDL在1/2处仍然能够完成计算, 但在计算完整数据集时发生了OOD, 且执行时间也都在24小时的基准线以下. 在Cit-Patents数据集下, Souffle在1/2, BDDBDDB在1/3, μZ在1/4处数据集能够完成计算, 而DDL能够完成完整数据集的计算, 并且完成完整数据集的计算只需要不到7个小时的时间. 在更大的LiveJournal数据集下, Souffle, μZ和BDDBDDB与在Wiki-Talk数据集下表现相同, 在1/6处的计算就已经OOM, 而DDL在直到1/3处才发生了OOD. 但比较遗憾的是, 即使在1/6处DDL所需计算时间已经远超过了24小时. 同时为了能够量化评估DDL的可扩展能力, 实验对Wiki-Talk和LiveJournal数据集进行了更细粒度的划分, 最终实验得到在Wiki-Talk数据集下Souffle在1/7, μZ在1/15, BDDBDDB在1/12处能够完成计算, 在LiveJournal数据集下Souffle在1/36, μZ在1/60, BDDBDDB在1/48处能够完成计算, 从而在本文的实验环境下DDL相较于Souffle, μZ和BDDBDDB能够处理其2–20倍规模的问题. 值得注意的是, 对于上述DDL发生OOD的情况, 方法可以通过简单地扩增硬盘的容量来帮助完成后续的计算. 相比较扩增内存容量来说, DDL方法更加方便和实惠.
对于RQ1, DDL能够处理1/2的Wiki-Talk数据集, 完整的Cit-Patents数据集和1/3的LiveJournal数据集. 且对于更大规模的问题, DDL可以通过简单扩增硬盘容量的方式加以解决. 实验结果表明, DDL比现有先进的单机Datalog引擎具有更高的可扩展能力, 至少能够解决2–20倍于现有先进的单机Datalog引擎处理的问题规模, 且性能在可接受范围内.
5.5 性 能为了评估DDL引擎的计算性能, 实验分别在3个Datalog 规则上应用了上述6个输入数据集进行了对比. 对于Program2和Program3只需要一个输入数据事实文件即可, 而对于Program1需要R, S, T这3个输入数据事实文件. 为了能够在每个数据集上进行实验评估, 实验将每个数据集复制了3份, 然后将其分别命名为R, S和T用于计算. 同时为了能较全面评估对比性能, 对于真实数据集下的Program2和规则Program3, 选取了Wiki-Talk数据集的1/7, Cit-Patents数据集的1/3 (对Program3而言为Cit-Patents数据集的1/2)和LiveJournal数据集的1/36进行了实验, 而对于Program1则使用了完整的数据集进行实验. 需要注意的是, μZ和BDDBDDB引擎并不支持Aggregation语义(do not support, DNS), 因而无法完成Program3的计算. 实验记录了Datalog引擎执行计算的总时间, 和执行Datalog程序逻辑的时间(ExeTime)以及引擎执行计算前预处理的时间(PreTime). 同时还记录了递归程序在不同数据集上计算的迭代轮数.
图13展示了DDL, Souffle, μZ和BDDBDDB在Program1, Program2和Program3 Datalog程序上的执行总时间, 执行Datalog程序逻辑时间和预处理时间, 从而表现出DDL, Souffle, μZ和BDDBDDB四者性能上的差异. 从中可以看出, 对于非递归程序Program1的计算性能, 在3个合成的小数据集上, DDL, Souffle, μZ和BDDBDDB几乎没有差别, 但随着数据集的增大, 性能差异开始显现. 在3个真实数据集上, DDL都要快于Souffle的执行, 而μZ和BDDBDDB都发生了OOM导致计算未完成. 从图13(a)可以看出在执行Datalog规则逻辑上所花费的时间上较接近, 但Souffle在预处理阶段花费了较多的时间去读取加载文件以及构建相应的数据结构, 相比之下DDL采用较简单的数据结构并基于Hash分区策略在预处理时花费时间较少, 同时得益于基于搜索树剪枝的最少置换调度策略, 使得DDL在执行JOIN和SetDiff运算时也能省掉较多不必要的计算.
|
图 13 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个真实数据集下均未完成计算. 同时从图13(b)可以看出Datalog程序执行逻辑的时间直接影响了最终执行性能.
表3展示了Program2在不同数据集上计算的迭代轮数. 结合表3的结果, 分析发现, 在DDL所需计算迭代轮数多的数据集上性能都较差(例如Grid150, Cit-Patents, LiveJournal), 而在所需计算迭代轮数少的数据集上性能较优(例如Gnp10K, Wiki-Talk). 原因在于DDL需要在每一轮迭代计算中需要进行固定次数的分区调度来完成计算(若过程中需要再分区则会进一步增多分区的调度次数), 对于迭代轮数多的数据集会导致整体执行过程需要总分区调度次数增加, 进而在IO上花费更多的时间. 而IO开销过多就会导致将优化策略所带来的性能收益抵消甚至拖累整体性能, 从而导致DDL计算性能下降.
|
|
表 3 Program2在不同数据集上计算的迭代轮数 |
对于含有聚合操作的Datalog程序Program3的计算性能, 可以从图13(c)明显看出无论是在小规模合成数据集上还是在大规模真实数据集上, DDL的执行时间要远小于Souffle (在Tree11数据集上执行时间相近且都小于3 s, 因而在讨论中忽略不计), 反映出DDL对于含有聚合操作的Datalog程序计算的性能表现要更优于Souffle. 得益于DDL采用流数据处理的方式计算聚合操作算子, 对于所有分区文件都只需遍历一遍即可求得聚合操作的结果, 是O(N)的时间复杂度. 而对于Souffle则需要在内存中更新维护每一轮计算谓词的数据结构(在Souffle中用B树表示谓词数据), 同时在其中进行聚合操作的计算得到结果, 是O(NlogN)的时间复杂度.
对于RQ2, DDL在非递归Datalog程序小规模数据集上计算性能与Souffle, μZ和BDDBDDB相近, 在大规模数据集上更要优于其他引擎. 对于递归程序无论在什么规模数据集上, DDL性能更受限于数据集的迭代计算轮数, 对于迭代轮数少的数据集, DDL性能更优, 而对于迭代轮数多的数据集, DDL受限于IO开销导致计算性能下降. 而对于含有聚合操作的Datalog程序, DDL得益于流数据处理的核外计算方式, 使得无论在小规模合成数据集还是大规模真实数据集上性能表现都要优于Souffle.
6 相关工作 6.1 前沿的Datalog引擎研究随着Datalog在不同领域中得到广泛的应用, 研究人员在不同领域设计了特定的Datalog引擎帮助完成计算. 在单机Datalog引擎研究中, Whaley等人提出了BDDBDDB引擎[12], 将Datalog应用于程序分析领域, 并提出使用BDD的数据结构来表示Datalog中的谓词关系. 通过为设计巧妙的BDD操作以及有效的优化手段, 引擎性能比手工调优的代码还要快上两倍, 并且能够对大型程序进行上下文敏感的指针分析. Hoder等人提出了μZ引擎[13], 将Datalog程序转换为一阶逻辑谓词命题, 并利用SMT求解器Z3进行求解, 实现了引擎的高可扩展性和灵活性以及高效的性能. Aref等人提出了 LogicBlox系统[14], 第1个商业化的Datalog引擎. 他们旨在利用Datalog语言简洁的优势, 为现代应用程序减少软件开发的复杂性. 他们创新性地在Datalog语言上扩展了Datalog语法, 提出了LogiQL 语言. 不同于传统的基于pair的表项JOIN进行计算, LogicBlox使用Leapfrog Triejoin 作为底层进行JOIN计算的核心算法, 并设计相应的数据结构, 进行了特定的优化. Scholz等人提出了Souffle[3], 用于大规模程序分析的Datalog引擎. 得益于Datalog语法的简洁性与引擎的优越性能, 使得普通开发人员无需专业的程序分析领域知识, 也能方便快速且高效地完成程序分析任务. Souffle将Datalog程序经过多层次优化转换合成为C++程序, 并最终得到对应的可执行文件. 除了通过前端分析优化以及选择合理的执行策略, Souffle选择使用Trie和B树等数据结构表示谓词, 以及充分利用硬件并行化以及缓存等特性, 使得执行性能表现优异.
在分布式Datalog引擎研究中, Seo等人提出了Distributed Socialite[15], 基于Datalog的大规模图分析引擎. Distributed Socialite基于分布式并行环境实现, 程序员只需简单标注数据是如何分布的, 引擎就会自动化产生适用于集群上并行执行的程序. Distributed Socialite提出增量步进技术, 以优化递归单调聚合函数的并行执行, 并且它支持近似计算, 允许程序员用更少的时间和空间来权衡数值计算结果的准确性. Shkapsky等人提出了BigDatalog[8], 基于Spark分布式系统的Datalog引擎. Spark分布式系统被广泛用于大规模的机器学习任务以及图分析. BigDatalog利用Datalog的语法简洁以及表达能力强的优势, 同时结合Spark优势高效处理大规模数据任务. BigDatalog设计SetRDD数据结构优化并行化的半朴素法. BigDatalog提出了限制Shuffle操作的分区策略, 提高执行效率, 同时也利用缓存输入和Spark广播变量的结构来优化线性递归的JOIN操作.
单机环境下的Datalog引擎, 受限于内存, 并不具备很强的可扩展性, 在面对真实场景下的问题时往往因内存溢出而无法解决. 而分布式环境下的Datalog引擎, 集群环境维护困难, 代码调试也是个很大的挑战, 同时需要花费大量的时间设计合适的分布式并行算法, 并且执行也难以找到性能瓶颈. 而本文提出的基于核外计算的Datalog引擎DDL, 享受单机环境的优点, 同时提供很高的可扩展性, 并且性能依然表现良好.
6.2 基于硬盘的计算系统Kyrola等人提出GraphChi[32], 基于硬盘的单机图计算系统. 通过将大图分解成多个小图分区的方式, GraphChi创新性地提出使用并行滑动窗口方法处理小图分区, 使得其能够在普通PC上对大规模的图实现数据挖掘, 图挖掘等功能. 同时进一步扩展GraphChi, 能够支持随时间演化的图计算, 使得在普通PC上可以每秒同时执行超过10万个图计算任务. Wang等人提出Graspan[5], 基于硬盘并行计算的图计算系统. Graspan可用于大规模程序的过程间程序分析. 将传统的程序分析算法, 从大数据处理角度进行看待, 基于硬盘实现, 将程序表示成边表的文件形式存储在硬盘上, 采用以边对为中心的计算方法, 设计相应的并行化算法以及优化的调度策略和相应的数据结构, 使得在普通PC机上也能高效完成大规模程序的分析. Wang等人提出RStream[10], 基于硬盘的大规模图挖掘计算系统. RStream基于硬盘顺序访问速率要比随机访问速率更快的思路, 对硬盘上完全无序的边列表形式表示的图文件采用流分区技术进行分区, 将硬盘上的大图文件分成多个流分区, 接着使用流处理的技术逐一处理每个流分区的计算, 以此减少分区IO开销. 同时RStream使用生产者-消费者的多线程模式, 通过创建线程本地缓冲区, 并行处理从硬盘读入的数据以及并行写回硬盘存储中间数据. 本文的方法受上述基于硬盘的图计算系统启发, 提出基于核外计算的Datalog引擎DDL, 设计一系列核外计算的算子以及对应的分区策略和调度策略, 使得Datalog引擎在单机环境下高效执行计算同时不受内存容量制约.
7 总 结本文设计并实现了基于核外计算的Datalog引擎DDL. DDL解决现有先进的单机Datalog引擎计算规模受限于内存大小的问题, 通过核外计算手段利用硬盘大幅提升单机Datalog引擎处理计算规模. DDL将Datalog程序转换为一系列核外计算算子的表示来实现核外计算, 同时提出基于Hash的分区策略和基于搜索树剪枝的最少置换调度策略等优化手段提升引擎性能. 本文还实验评估了DDL良好的性能和高可扩展性.
本文方法和原型工具仍存在一些不足: 目前对于更复杂的Datalog程序, DDL引擎前端解析模块并不能很好处理, 存在着无法从RAM中抽取得到带有核外计算算子的表示情况. 并且对于递归规则计算上较多的中间结果存储在硬盘上仍会导致OOD情况发生而终止计算. 在未来计划进一步完善DDL引擎前端解析模块以支持更复杂的Datalog程序, 并扩展DDL使得其能支持更丰富的Datalog语法(如仿函数, 谓词组合等), 以及对暂存硬盘的中间结果作进一步的优化尽量避免OOD情况出现.
| [1] |
Brent L, Grech N, Lagouvardos S, Scholz B, Smaragdakis Y. Ethainter: A smart contract security analyzer for composite vulnerabilities. In: Proc. of the 41st ACM SIGPLAN Conf. on Programming Language Design and Implementation. London: ACM, 2020. 454–469.
|
| [2] |
Grech N, Brent L, Scholz B, Smaragdakis Y. Gigahorse: Thorough, declarative decompilation of smart contracts. In: Proc. of the 41st Int’l Conf. on Software Engineering. Montreal: IEEE, 2019. 1176–1186.
|
| [3] |
Scholz B, Jordan H, Subotić P, Westmann T. On fast large-scale program analysis in Datalog. In: Proc. of the 25th Int’l Conf. on Compiler Construction. Barcelona: ACM, 2016. 196–206.
|
| [4] |
Bravenboer M, Smaragdakis Y. Strictly declarative specification of sophisticated points-to analyses. In: Proc. of the 24th ACM SIGPLAN Conf. on Object Oriented Programming Systems Languages and Applications. Auckland: ACM, 2009. 243–262.
|
| [5] |
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] |
| [6] |
Fogel A, Fung S, Pedrosa L, Walraed-Sullivan M, Govindan R, Mahajan R, Millstein T. A general approach to network configuration analysis. In: Proc. of the 12th USENIX Conf. on Networked Systems Design and Implementation (NSDI). Oakland: USENIX Association, 2015. 469–483.
|
| [7] |
Zhang P, Huang YH, Gember-Jacobson A, Shi WB, Liu X, Yang HK, Zuo ZQ. Incremental network configuration verification. In: Proc. of the 19th ACM Workshop on Hot Topics in Networks. ACM, 2020. 81–87.
|
| [8] |
Shkapsky A, Yang MH, Interlandi M, Chiu H, Condie T, Zaniolo C. Big data analytics with Datalog queries on spark. In: Proc. of the 2016 Int’l Conf. on Management of Data. San Francisco: ACM, 2016. 1135–1149.
|
| [9] |
Moustafa WE, Papavasileiou V, Yocum K, Deutsch A. Datalography: Scaling Datalog graph analytics on graph processing systems. In: Proc. of the 2016 IEEE Int’l Conf. on Big Data. Washington: IEEE, 2016. 56–65.
|
| [10] |
Wang K, Zuo ZQ, Thorpe J, Nguyen TQ, Xu GH. RStream: Marrying relational algebra with streaming for efficient graph mining on a single machine. In: Proc. of the 13th USENIX Symp. on Operating Systems Design and Implementation (OSDI). Carlsbad: USENIX Association, 2018. 763–782.
|
| [11] |
Flores-Montoya A, Schulte E. Datalog disassembly. In: Proc. of the 29th USENIX Conf. on Security Symp. (Security). Berkeley: USENIX Association, 2020. 61.
|
| [12] |
Whaley J, Avots D, Carbin M, Lam MS. Using Datalog with binary decision diagrams for program analysis. In: Proc. of the 3rd Asian Symp. on Programming Languages and Systems. Tsukuba: Springer, 2005. 97–118.
|
| [13] |
Hoder K, Bjørner N, de Moura L. μZ—An efficient engine for fixed points with constraints. In: Proc. of the 23rd Int’l Conf. on Computer Aided Verification (CAV). Snowbird: Springer, 2011. 457–462.
|
| [14] |
Aref M, ten Cate B, Green TJ, Kimelfeld B, Olteanu D, Pasalic E, Veldhuizen TL, Washburn G. Design and implementation of the LogicBlox system. In: Proc. of the 2015 ACM SIGMOD Int’l Conf. on Management of Data. Melbourne: ACM, 2015. 1371–1382.
|
| [15] |
Seo J, Park J, Shin J, Lam MS. Distributed socialite: A Datalog-based language for large-scale graph analysis. Proc. of the VLDB Endowment, 2013, 6(14): 1906-1917.
[doi:10.14778/2556549.2556572] |
| [16] |
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).
[doi:10.1360/crad20051028] |
| [17] |
Green TJ, Huang SS, Loo BT, Zhou WC. Datalog and Recursive Query Processing. Boston: Now Publishers, 2013.
|
| [18] |
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] |
| [19] |
Wang YM, Shi BL. The group of DATALOG programs and its applications. Ruan Jian Xue Bao/Journal of Software, 1997, 8(9): 641–646 (in Chinese with English abstract). http://www.jos.org.cn/jos/article/abstract/19970901?st=search
|
| [20] |
Abiteboul S, Hull R, Vianu V. Foundations of Databases. Reading: Addison-Wesley, 1995. 8.
|
| [21] |
Hulin G. Parallel processing of recursive queries in distributed architectures. In: Proc. of the 15th Int’l Conf. on Very Large Data Bases. Amsterdam: Morgan Kaufmann Publishers Inc., 1989. 87–96.
|
| [22] |
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] |
| [23] |
Fan ZW, Zhu JQ, Zhang ZY, Albarghouthi A, Koutris P, Patel JM. Scaling-up in-memory Datalog processing: Observations and techniques. Proc. of the VLDB Endowment, 2019, 12(6): 695-708.
[doi:10.14778/3311880.3311886] |
| [24] |
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] |
| [25] |
Roy A, Mihailovic I, Zwaenepoel W. X-stream: Edge-centric graph processing using streaming partitions. In: Proc. of the 24th ACM Symp. on Operating Systems Principles. Pennsylvania: ACM, 2013. 472–488.
|
| [26] |
Prata S. C++ Primer Plus. 6th ed., Upper Saddle River: Addison-Wesley Professional, 2011.
|
| [27] |
The souffle datalog engine. 2020. https://souffle-lang.github.io/
|
| [28] |
Leskovec J, Sosič R. SNAP: A general-purpose network analysis and graph-mining library. ACM Trans. on Intelligent Systems and Technology, 2017, 8(1): 1.
[doi:10.1145/2898361] |
| [29] |
Azad A, Buluç A, Gilbert J. Parallel triangle counting and enumeration using matrix algebra. In: Proc. of the 2015 IEEE Int’l Parallel and Distributed Processing Symp. Workshop. Hyderaba: IEEE, 2015. 804–811.
|
| [30] |
Mawhirter D, Wu B. AutoMine: Harmonizing high-level abstraction and high performance for graph mining. In: Proc. of the 27th ACM Symp. on Operating Systems Principles. Huntsville: ACM, 2019. 509–523.
|
| [31] |
Becchetti L, Boldi P, Castillo C, Gionis A. Efficient semi-streaming algorithms for local triangle counting in massive graphs. In: Proc. of the 14th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Las Vegas: ACM, 2008. 16–24.
|
| [32] |
Kyrola A, Blelloch GE, Guestrin C. GraphChi: Large-scale graph computation on just a PC. In: Proc. of the 10th USENIX Symp. on Operating Systems Design and Implementation (OSDI). Hollywood: USENIX Association, 2012. 31–46.
|
| [16] |
唐剑琪, 方滨兴, 胡铭曾, 王威. 核外计算中的几种I/O优化方法. 计算机研究与发展, 2005, 42(10): 1820-1825.
[doi:10.1360/crad20051028] |
| [19] |
王云明, 施伯乐. DATALOG程序的组及其应用. 软件学报, 1997, 8(9): 641–646. http://www.jos.org.cn/jos/article/abstract/19970901?st=search
|