面向dag计算框架的增量计算关键技术研究

《面向dag计算框架的增量计算关键技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中文图书分类号：TP391密级：公开UDC：004学校代码：10005硕士学位论文MASTERALDISSERTATION论文题目：面向DAG计算框架的增量计算关键技术研究论文作者：阚京学科：计算机科学与技术指导教师：陈彩论文提交日期：2017年5月UDC：004学校代码：10005中文图书分类号：TP391学号：S201407002密级：公开北京工业大学工学硕士学位论文题目：面向DAG计算框架的增量计算关键技术研究英文题目：THERESEARCHOFKEYTECHNIQUESOFINCREMENTALCOM

2、PUTINGFORDAG-BASEDFRAMEWORK论文作者：阚京学科专业：计算机科学与技术研究方向：计算机软件与理论申请学位：工学硕士指导教师：陈彩副教授所在单位：信息学部答辩日期：2017年5月授予学位单位：北京工业大学独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在

3、论文中作了明确的说明并表示了谢意。签名：阚京日期：2017年5月16日关于论文使用授权的说明本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。(保密的论文在解密后应遵守此规定)签名：阚京日期：2017年5月16日导师签名：陈彩日期：2017年5月16日摘要摘要伴随信息时代的飞速发展，数据量的爆炸式增长以及计算机性能的飞越带领人们跨入到大数据的时代。面对种类庞杂且规模庞大的数据

4、集，必须使用分布式计算框架才能够有效地进行处理，而以有向无环图（DirectedAcyclicGraph，下简称DAG）模型作为作业逻辑关系编排方式的分布式计算框架就是目前最为流行的大数据计算解决方案之一。由于大数据通常以只增的方式进行数据集的更新，使得大数据在存储上通常都具备增量性。目前的DAG计算框架在对这样的数据集进行计算时仍存在诸多挑战。一是对欠缺增量的感知能力，使得数据增量后的重计算占用了过多的计算资源；二是缺少对可复用计算特别是相似计算的识别与复用。既有工作主要从应用算法层面和计算框架层面提出改进

5、。从应用算法层面的改进仅适用特定的计算管线，无法以用户透明地方式进行优化；从计算框架层面的改进方法对数据和计算逻辑的要求较为苛刻。本文针对现存问题，通过引入间接复用以及算子裁剪的方式来对相似计算进行识别和处理，通过构建CostModel实现了动态的缓存管理策略，从而在增加优化适用范围的同时，以用户透明的方式实现计算性能的提升。本文的主要贡献如下：(1)建立了DAG中直接复用与间接复用的识别模型。抽取了DAG计算框架中的可复用算子的特征，对直接复用与间接复用进行了分析与定义。通过该识别模型可以对DAG中的可复用

6、部分进行识别。(2)设计并实现了DAG框架中的增量计算复用框架。本文在该框架中设计了基于DAG节点预处理、可复用计算的匹配和增量计算处理三步的增量计算复用流程。通过DAG中Filter算子的处理策略实现了Filter算子的模糊匹配与拆分机制；基于FQ-Tree的DAG可复用片段的匹配机制和增量计算处理策略实现了基于Filter算子的间接复用机制。(3)设计并实现了缓存管理机制。设计了基于Alluxio的多介质缓存存储策略。实现了基于FQ-Tree的缓存信息的维护策略及相关算法，使得缓存系统可以为算子的匹配与识

7、别提供元信息。通过设计能够综合使用频次、复用类型以及时间相关度的CostModel，使缓存系统可以权衡缓存块的收益。(4)设计并执行了一系列性能测评实验。通过以合理的混合比例随机产生的计算负载进行系统性能测评，在同等计算环境及计算负载条件下，本文提出的DAG增量计算复用框架使计算任务的平均计算时间减少了32.49%.关键词：分布式计算；DAG计算；增量计算；计算复用-I-AbstractAbstractWiththerapiddevelopmentoftheinformationage,theexplosiv

8、egrowthofdatavolumeandtheboostofcomputerperformanceledpeopleintotheeraoflargedata.Inthefaceoflargedataset,thedistributedcomputingframeworkmustbeusedtodealwithiteffectively,andthedistrubutedcomputingfra