基于核外计算的Datalog引擎设计与实现.pdf
《基于核外计算的Datalog引擎设计与实现.pdf》由会员分享,可在线阅读,更多相关《基于核外计算的Datalog引擎设计与实现.pdf(18页珍藏版)》请在咨信网上搜索。
1、基于核外计算的 Datalog 引擎设计与实现*张奕裕1,2,王归航1,2,左志强1,2,李宣东1,21(南京大学计算机科学与技术系,江苏南京210023)2(计算机软件新技术国家重点实验室(南京大学),江苏南京210023)通信作者:左志强,E-mail:摘要:随着新兴技术的迅速发展,领域软件对开发效率提出了新的要求.Datalog 语言作为一门具有简洁语法和良好语义的声明式编程语言,能帮助开发人员快速开发和解决问题,近年来越来越受到重视与欢迎.但解决真实场景问题时,现有的单机 Datalog 引擎计算规模往往受限于内存容量大小,不具有可扩展性.为解决上述问题,设计并实现基于核外计算的 Da
2、talog 引擎.方法首先设计一系列计算 Datalog 程序所需的支持核外计算的操作算子,然后将 Datalog 程序转换合成带核外计算算子的 C+程序,接着方法设计基于 Hash 的分区策略和基于搜索树剪枝的最少置换调度策略,将相应的分区文件调度执行计算并得到最终结果.基于该方法,实现原型工具 DDL(disk-basedDatalogengine),并选取广泛应用的真实 Datalog 程序,在合成数据集以及真实数据集上进行实验,实验结果体现了DDL 良好性能以及高可扩展性.关键词:Datalog 引擎;核外计算;操作算子;分区策略;调度策略中图法分类号:TP311中文引用格式:张奕裕,
3、王归航,左志强,李宣东.基于核外计算的Datalog引擎设计与实现.软件学报,2023,34(8):35873604.http:/ and Implementation of Datalog Engine Based on Out-of-core ComputingZHANGYi-Yu1,2,WANGGui-Hang1,2,ZUOZhi-Qiang1,2,LIXuan-Dong1,21(DepartmentofComputerScienceandTechnology,NanjingUniversity,Nanjing210023,China)2(StateKeyLaboratoryforNov
4、elSoftwareTechnology(NanjingUniversity),Nanjing210023,China)Abstract:As emerging technologies develop rapidly,domain software puts forward new requirements for development efficiency.Inaddition,as a declarative programming language with concise syntax and well-defined semantics,Datalog can help deve
5、lopers solvecomplexproblemsrapidlyandachievesmoothdevelopmentandthushasattractedwideattentioninrecentyears.However,whensolvingreal-world problems,the existing single-machine Datalog engines are often limited by the size of memory capacity and possess noscalability.Tosolvetheseproblems,thisstudydesig
6、nsandimplementsaDatalogenginebasedonout-of-corecomputing.Firstly,aseriesof operators supporting out-of-core computing are designed to compute the Datalog program,and then the program is converted into aC+program with the operators.Next,the study designs a partition strategy based on Hash and a minim
7、um replacement schedulingstrategybasedonsearchtreepruning.Afterthat,thecorrespondingpartitionfilesarescheduledandcomputedtogeneratethefinalresults.Based on this method,the study establishes the prototype tool DDL(disk-based Datalog engine)and selects widely used real-worldDatalogprogramstoconductexp
8、erimentsonbothsyntheticandreal-worlddatasets.TheexperimentalresultsshowthatDDLhaspositiveperformanceandhighscalability.Key words:Datalogengine;out-of-corecomputation;operators;partitionstrategy;schedulingstrategy*基金项目:国家自然科学基金(61802168);江苏省自然科学基金(BK20191247)本文由“领域软件工程”专题特约编辑汤恩义副教授、江贺教授、陈俊洁副教授、李必信教授以
9、及唐滨副教授推荐.收稿时间:2021-08-09;修改时间:2021-10-09;采用时间:2022-01-10;jos 在线出版时间:2022-01-28CNKI 网络首发时间:2023-01-19软件学报ISSN1000-9825,CODENRUXUEWE-mail:Journal of Software,2023,34(8):35873604doi:10.13328/ki.jos.006552http:/中国科学院软件研究所版权所有.Tel:+86-10-62562563近年来,软件的快速发展对国民经济和社会发展起着积极的促进作用.随着区块链,云计算,人工智能等新兴技术迅速发展,这些特定
10、领域对软件应用的需求显得尤为迫切,而这也对领域软件开发的效率和执行性能提出了新的要求.随着技术间的进一步融合,领域软件面临着开发周期长,设计复杂和开发效率低等挑战.领域软件开发人员越来越需要编程语言提供高级抽象来帮助逻辑推理和应用的快速开发,以此来满足日益增长的软件开发需求.Datalog 作为一门声明式编程语言,近年来在智能合约分析1,2,程序分析35,网络验证6,7,大数据分析810,反汇编11等领域得到广泛的应用,越来越受到重视与欢迎.归因于 Datalog 语言其声明式的特性,Datalog 语言天生具备简洁的语法和良好的语义等优势,从而使用 Datalog 语言编写程序能够带来项目开
11、发效率的提升,同时软件开发人员只需要关注任务是什么以及任务处理的逻辑,而无需考虑底层具体实现的细节.与命令式编程语言(例如 C/C+,Java)命令式地一步步计算步骤不同,Datalog 程序以一种声明式的方式预先指定期望的计算结果,所需的计算由 Datalog 引擎自动地完成.而 Datalog 引擎设计实现的优劣直接决定解决问题规模的大小以及执行性能的快慢.现有 Datalog 引擎被广泛应用于解决真实场景问题,常常需要面对解决计算性能差和可扩展性低的问题.在解决实际真实的问题时,Datalog 引擎往往需要处理上百条的 Datalog 程序,以及包含上百万甚至千万条元组数据的输入文件.特
12、别地,对于一些递归的程序(如 TransitiveClosure),即使只有少量的输入数据,但产生的中间结果或者最终结果却是扩大了上百倍8.这些真实场景下需要面临的问题对 Datalog 引擎的可扩展性提出了很高的要求,需要 Datalog 引擎能够处理大量数据,同时执行的性能在可以接受范围之内.现有的前沿工作在不同领域都设计提出了各自的 Datalog 引擎来解决实际的领域问题.他们有基于单机实现的 BDDBDDB12,Z13,LogicBlox14和 Souffle3等,还有基于分布式系统实现的 Distributedsocialite15和BigDatalog8等.基于分布式系统实现的
13、Datalog 引擎具有显著的可扩展性,Datalog 引擎处理的问题规模可以随着集群的扩大而增大,且通过对算法的分布式并行化实现使得 Datalog 引擎执行性能表现良好.但基于分布式系统实现的 Datalog 引擎问题在于,一是在集群上的代码调试将更加困难,二是扩大集群以处理更大规模问题的成本将显著增加,三是通常开发人员的开发环境并不普遍具备分布式集群的条件.基于单机实现的 Datalog 引擎对使用人员更加友好,开发人员能够简单方便易操作地通过在单机开发环境下对 Datalog 程序进行调试或执行计算,而无需分布式环境下繁琐的调试部署,且现有工作通过对 Datalog 引擎中数据结构的优
14、化以及执行策略的改进,使得其执行性能表现在可接受范围之内.但基于单机实现的 Datalog 引擎问题在于,一是处理问题的规模受限于单机内存容量的大小,Datalog 引擎常因为执行过程中的内存溢出而直接终止计算,例如 BDDBDDB,Z 和 SQLite引擎在面对真实的 OpenJDK7 数据集计算上下文敏感的指向分析时因内存溢出而无法完成计算3;二是为了处理更大规模问题而扩大内存容量的成本也相对较为昂贵.因而基于上述的讨论,为了能够享受单机引擎的简便以省去分布式引擎的繁琐同时使得单机引擎具有高可扩展性,本文设计提出了基于核外计算的 Datalog 引擎 DDL(disk-basedDatal
15、ogengine).在 Datalog 程序运行时,并不是全部数据存放在内存中计算,而只有部分数据被调入内存并执行计算,同时在适当时候写回外存,通过内外存的数据交换来完成整个计算16.由于 Datalog 引擎的实现可以视作一系列关系代数操作算子的具体实现(第 1.3节),DDL 通过设计实现了一系列完成 Datalog 程序计算所需的支持核外计算的操作算子.同时 DDL 在 Souffle 基础上将 Datalog 程序转换合成为由这些核外计算算子表示的 C+程序,实现了完整的支持核外计算的 Datalog 引擎.DDL 还通过设计实现基于谓词属性的 Hash 分区策略以及基于搜索树剪枝的最
16、少置换分区调度策略等优化手段降低 I/O 开销以提升引擎执行性能.DDL 引擎工作在单机环境下,具备基于单机实现的 Datalog 引擎的优点,同时使得问题处理的规模不再受限于内存的大小,相反可以通过扩增相对便宜的硬盘容量来处理更大规模的问题.总而言之,本文做出了如下创新贡献.设计了基于核外计算的 Datalog 引擎并实现了相应的原型工具 DDL,解决了单机环境下 Datalog 引擎面对真实场景时受限于内存大小的局限性.设计实现了完成 Datalog 程序计算所需的核外计算的操作算子,并提出了基于谓词属性的 Hash 分区策略和基于搜索树剪枝的最少置换调度策略等优化手段,来实现 DDL 引
17、擎高效的核外计算.3588软件学报2023 年第 34 卷第 8 期在合成的和真实的数据集上与现有先进单机 Datalog 引擎进行了对比实验,表明了 DDL 良好的性能以及高可扩展性.特别地,对于小规模数据能够在内存中完成计算的,DDL 引擎并没有引入过多的额外开销,甚至在某些例子上性能更优;而对于大规模数据发生内存溢出情况的,DDL 引擎能够完成计算,具有高可扩展性,且性能在可接受范围内.本文第 1 节介绍本文工作的相关背景知识.第 2 节介绍所提出的基于核外计算的算子.第 3 节介绍为提升DDL 引擎性能提出的优化策略.第 4 节介绍 DDL 引擎的设计实现.第 5 节通过实验展示 DD
18、L 引擎的可扩展性和性能.第 6 节回顾相关工作.第7 节对本文工作进行总结,并提出未来工作展望.1 背景知识 1.1 Datalog 程序一个 Datalog 程序是由有限条数量的 Datalog 规则以及数据事实组成.每一条 Datalog 规则由 3 个部分构成,分别是规则头,连接符(:)和规则体,形如公式(1)所示.H:B0,.,Bi,.,Bn.(1)BiB0,.,Bi,.,BnB(A1,A2,.,Ak)Ait=其中,H 和代表 Datalog 程序中的谓词,的合取构成规则体,其结果构成规则头 H.一个谓词可以实现成一个有 k 列的二维表格,其中被叫作属性.在表格中的每行元素被视作一个
19、元组.本文把输入的元组叫作数据事实.下列公式(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 点之间存在
20、一条边,那么就意味着 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自底向上执行给定输入的数据事实和 Data
21、log 规则,Datalog 引擎递归应用 Datalog 规则以及数据事实以派生出更多的元组,直到达到计算的不动点(即没有更多新的元组派生出来)停止.自底向上执行的方法通过将 Datalog 程序中所有规则应用于给定的数据事实进行计算,把满足规则的元组派生为规则头的谓词.具体来说,结合 Datalog 不动点语义进行求值,即从只包含有给定数据事实谓词的 Datalog 规则开始应用,进行迭代求值;在每次迭代中,所有 Datalog规则都被求值,并计算派生得到满足规则的头部谓词;当没有更多新的头部谓词派生时,计算达到不动点,执行停止.该种方法被称作为朴素法.但显然的是,朴素法在执行过程当中许多
22、谓词元组进行了多次派生,例如公式(2)公式(5)所示的 Datalog 程序,其中 path(a,b),path(b,c)谓词元组在执行过程中就派生了两次,造成了冗余的结果,导致执行性能的低下.产生这种冗余结果的原因在于,朴素法在计算过程中每次迭代时都应用的是当前已知的所有事实(包括输入数据事实和派生元组事实),不管这些谓词是否会再额外产生新的谓词.为了在计算的时候尽量避免重复之前迭代中已经完成的结果,一种更优的自底向上执行方法被提出,叫作半朴素法18,19.半朴素法基于这样的观察,只有在前一次迭代计算中产生的新元组才能在本次迭代计算中产生更多张奕裕等:基于核外计算的 Datalog 引擎设计
23、与实现3589的新元组.因而半朴素法与朴素法不同的地方在于半朴素法在每次迭代计算都只应用在前一次迭代计算中新产生的元组,从而减少冗余的计算.1.2.2自顶向下执行虽然自底向上执行的半朴素法在程序的迭代计算中最小化了冗余计算的产生,但是它并没有最小化在产生目标谓词元组结果时不相关的谓词元组派生.例如在公式(2)公式(5)的 Datalog 程序中,需要产生以 b 为起始节点所能到达的所有节点集合,而显然 path(a,b)这个谓词不会也不需要参与到计算中,但自底向上执行方法依然会在迭代计算过程产生该谓词.而自顶向下执行的方法17则不会造成这种计算的冗余,它会将条件从想要的规则向下推入可能回答该查
24、询的规则中,从而这些规则会创建更多子规则,子规则依次类似的方法向下推入,直到下推到输入的数据事实中判断是否存在满足条件的某个元组.其中最具代表性的自顶向下执行方法是 QSQ 方法20.在过去,不少研究工作设计实现基于自顶向下计算方法的 Datalog 引擎21,22.虽然自顶向下的方法更加直接产生目标谓词元组结果,且计算过程中不会产生跟目标结果无关的冗余中间结果,但在实际实现中较繁琐,无法直接投入真实问题场景中开展计算,且可优化空间小,执行性能并不比自底向上执行更优.相反,自底向上的方法实现简单,能适用真实场景问题,存在优化空间.现在业界主流 Datalog 引擎3,8,14执行方法选取大都选
25、择了自底向上执行,且提供丰富的优化手段,提高执行性能.类似地,本文方法也基于自底向上执行的半朴素方法设计基于核外计算的 Datalog 引擎.1.3 Datalog 引擎实现S(X,Y):R(X,Y),!T(X,Y)R(X,Y)T(X,Y)Datalog 语言可以看作是对关系代数的一种递归式扩展23.Datalog 语言中多种语法表示能够与关系代数进行相互转换24,例如表 1 所示.在表 1 中,展示了 7 种操作算子对应的 Datalog 规则与能进行相应转换的关系代数表示.例如对 Diff 操作算子而言,.Datalog 规则就可以由关系代数进行表示计算.表1操作算子对应的 Datalog
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 计算 Datalog 引擎 设计 实现
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。