分布式图计算系统的容错机制研究

发布时间：2017-08-15 01:30

  本文关键词：分布式图计算系统的容错机制研究

  更多相关文章： 图计算 容错 恢复 副本

【摘要】：现实世界中许多计算都涉及到大图,例如社交网络中朋友圈的分析工作。为了高效地分析图结构这类数据,谷歌公司提出了“像顶点一样思考”的图计算。图计算,凭借其强大的表达能力和高效的执行效率,逐渐被广泛用在网页搜索、自然语言处理、推荐系统等各个领域。为了应对现实世界中越来越复杂的算法和越来越大的数据集,现有的图计算系统大多设计为分布式系统。例如,谷歌公司已经用成百上千台机器来运行相关数据挖掘算法。由于运行在分布式环境下,图计算在运行过程中可能随时出现宕机、断电等异常情况,图计算系统需要提供机制来容忍这些异常的发生。本文的主要贡献如下:第一,通过实验详细分析了图计算现有的容错机制所存在的问题由于顶点上复杂的计算和顶点间复杂的依赖关系,现有的图计算系统主要采用为整个系统记录快照的方式进行容错。该机制存在两个问题:对于平时执行,它会引入很大的执行开销;对于故障恢复,它需要很长的恢复时间。采用该机制的系统,在平时执行过程中,需要定期地将当前计算的状态记录到分布式文件系统中。当有故障发生后,系统会从最近的快照中恢复出计算状态,然后重新开始计算。由于记录快照和从快照中恢复计算状态的过程涉及许多费时的网络请求,基于分布式快照的容错机制的执行开销比较大,恢复速度却比较慢。由于上述两个原因,在图计算真实运行中,即使系统提供了该容错机制,它也往往不被使用。第二,提出并实现了一个全新的利用顶点副本进行容错的机制分布式图计算系统会为一个顶点建立副本来服务其远端邻居的计算,这些副本拥有原顶点的许多的状态,可以很方便地被用来为系统提供容错支持。基于以上观察,本文提出了一个新的基于副本的容错机制Imitator。Imitator可以在引入很小执行开销的情况提供容错支持,同时它的恢复速度比较快。这是因为Imitator采用了如下设计:?Imitator尽可能地复用原有机制来降低执行开销,Imitator利用原有副本来备份顶点状态,同时它通过扩展已有同步机制来保证副本顶点与原顶点的状态是一致的;?Imitator利用整个集群的硬件资源进行并行恢复,Imitator通过选择副本位置,在恢复过程中,它尽可能地将恢复工作均分到各个机器上,充分利用整个集群的硬件资源进行恢复。测试表明,Imitator可以在引入很小执行开销的情况下(对于所有测试算法都小于5%)提供容错支持,同时它的恢复速度比较快,比基于分布式快照的容错机制快3.55～17.67倍。
【关键词】：图计算 容错 恢复 副本
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP302.8
【目录】：

• 摘要3-5
• abstract5-14
• 第一章 绪论14-20
• 1.1 研究背景14-15
• 1.2 研究目标15-16
• 1.3 本文工作16-17
• 1.4 全文结构17-20
• 第二章 背景介绍与相关研究工作20-32
• 2.1 图计算20-24
• 2.1.1 系统架构20-21
• 2.1.2 计算模型21-22
• 2.1.3 数据模型22
• 2.1.4 以顶点为中心的计算22-23
• 2.1.5 副本模型23-24
• 2.2 相关系统及其容错技术24-28
• 2.2.1 Map Reduce及其容错技术24-25
• 2.2.2 Spark及其容错技术25-27
• 2.2.3 数据库的容错技术27-28
• 2.2.4 基于副本的容错技术28
• 2.3 图计算现有的容错技术28-31
• 2.3.1 快照记录29-30
• 2.3.2 故障恢复30-31
• 2.4 小结31-32
• 第三章 图计算容错技术的问题分析32-40
• 3.1 Imitator-CKPT32
• 3.2 基于分布式快照容错机制所存在的问题32-35
• 3.2.1 执行开销32-34
• 3.2.2 故障恢复34-35
• 3.3 利用副本容错的机遇35-38
• 3.3.1 低执行开销36-37
• 3.3.2 快速恢复37-38
• 3.4 小结38-40
• 第四章 基于副本容错机制的设计40-54
• 4.1 利用副本容错的整体设计40-43
• 4.1.1 正常工作流程40-42
• 4.1.2 故障恢复流程42-43
• 4.2 副本管理43-46
• 4.2.1 容错副本43-44
• 4.2.2 镜像副本44-45
• 4.2.3 自私顶点的优化45-46
• 4.3 利用副本容错的恢复46-52
• 4.3.1 重生46-50
• 4.3.2 迁移50-52
• 4.4 更多故障模型52-53
• 4.4.1 多机故障52
• 4.4.2 其他故障52-53
• 4.5 小结53-54
• 第五章 基于副本容错机制的实现54-62
• 5.1 系统组织架构54-55
• 5.2 故障检测55-57
• 5.2.1 故障发现55-56
• 5.2.2 栅栏实现56-57
• 5.3 并行恢复57-58
• 5.4 Imitator基准系统58-60
• 5.5 小结60-62
• 第六章 实验与评测62-72
• 6.1 测试环境62-63
• 6.2 算法简介63-64
• 6.3 执行开销64-65
• 6.4 执行开销分析65
• 6.5 恢复情况65-66
• 6.6 恢复的可伸缩性66-67
• 6.7 划分算法的影响67-68
• 6.8 多机故障68-69
• 6.9 内存使用情况69-70
• 6.10案例分析70-71
• 6.11小结71-72
• 第七章 总结与展望72-74
• 7.1 工作总结72
• 7.2 工作展望72-74
• 参考文献74-82
• 致谢82-84
• 攻读学位期间发表的学术论文目录84-86

【共引文献】

中国期刊全文数据库 前10条

1 张德军;何发智;;基于建模历史一致性的协同CAD并发控制方法[J];东南大学学报(自然科学版);2015年05期

2 罗军;王宏;李文生;;基于向量时钟模型的NoSQL最终一致性的研究[J];计算机工程与应用;2013年23期

3 张晶;潘有顺;;嵌入式系统同步进程的竞态条件分析与推理学习方法[J];计算机科学;2014年02期

4 刘恒;李美安;苏萌;;基于重复数的最短循环请求集生成算法[J];计算机应用;2014年05期

5 张展;左德承;黄友富;何辉;;一种基于准同步检查点的虚拟机卷回恢复算法[J];计算机科学;2014年05期

6 林菲;孙勇;丁宏;任一支;;自稳定的分布式事务内存模型及算法[J];计算机研究与发展;2014年09期

7 周欢;樊秋实;胡华梁;;OceanBase一致性与可用性分析[J];华东师范大学学报(自然科学版);2014年05期

8 刘雨辰;王佳;陈云霁;焦帅;;计算机系统模拟器研究综述[J];计算机研究与发展;2015年01期

9 禹振;苏小红;王甜甜;马培军;;虚拟时间及其在数据竞争检测中的应用[J];哈尔滨工业大学学报;2015年01期

10 曾珊;文杰;;分布式系统一致性研究与案例分析[J];计算机与数字工程;2015年07期

中国重要会议论文全文数据库 前1条

1 张宇辉;褚庆昕;李迪;;基于时间误差的网络控制系统的稳定性分析[A];2015年第五届全国地方机械工程学会学术年会暨中国制造2025发展论坛论文集[C];2015年

中国博士学位论文全文数据库 前7条

1 朱素霞;面向多核处理器确定性重演的内存竞争记录机制研究[D];哈尔滨工业大学;2013年

2 毛华坚;云环境中的移动文件存储和时空数据分析关键技术研究[D];国防科学技术大学;2013年

3 刘光辉;高效处理器容错技术研究与实现[D];国防科学技术大学;2013年

4 杨哲a\;Java语言的程序漏洞检测与诊断技术[D];复旦大学;2012年

5 王涛;任务关键系统的软件行为建模与检测技术研究[D];燕山大学;2014年

6 陈艳文;分布式系统的时间化通信行为模型[D];华东师范大学;2014年

7 张扬;基于操作语义的弱内存模型描述及程序逻辑研究[D];中国科学技术大学;2015年

中国硕士学位论文全文数据库 前10条

1 顾飞;基于SPARC架构面向确定性重演的多核访存竞争记录方法的研究[D];哈尔滨工业大学;2013年

2 王勇;动态可重构的DSM语义研究[D];哈尔滨工业大学;2012年

3 王文苑;分布式缓存可用性相关问题研究[D];华中科技大学;2013年

4 孙建良;分布式存储系统可用性与一致性研究[D];华中科技大学;2013年

5 曹粟;基于非即停调试模式的嵌入式应用级调试系统[D];华中科技大学;2013年

6 林岚;基于银行家算法的分布式互斥请求集生成算法研究[D];内蒙古农业大学;2012年

7 陈志党;对分布式互斥请求集生成算法的进一步探索[D];内蒙古农业大学;2012年

8 林浩泓;云平台下可扩展分布式协调服务研究[D];华中科技大学;2013年

9 王君君;网络文件的分布式存储设计与实现[D];山东大学;2014年

10 王丁贤;一个大规模数据下的语义实体挖掘与语义实体关系归并的新框架[D];华东师范大学;2014年

，

本文编号：675704