大规模图增量迭代处理技术的研究与实现

摘要

社交网络、生物信息网络和信息技术的快速发展，使图论及其相关算法的应用日益广泛。其中，利用云计算环境开发大规模图的增量迭代处理平台，已经成为当前学术界和工业界研究的热点。但是针对数据划分、磁盘管理和网络通信等方面的优化工作，相对较少，而这三个方面正是影响大图处理平台运行效率的至关重要的因素。由于大图的增量迭代处理，具有数据耦合性强、迭代频率高、数据访问局部性差等特点，因此对于上述三个方面的优化处理是一个十分具有挑战性的课题，这也是本文的主要工作内容。
　　本文在数据划分方面，首先分析了DFS生成图和BFS生成图的局部性，然后提出了连续划分策略。相比于现有的随机Hash划分，连续划分策略能够保留输入图的原始局部性，避免数据划分阶段的全局洗牌操作，均衡计算负载。同时，为提供迭代过程的消息路由寻址服务，本文提出了基于Hadoop的图顶点连续编码方案和基于DHT的Hybrid-MT连续编码方案，可以将图顶点字符串转换为数字连续编号。在磁盘管理方面，通过分析增量迭代过程，本文提出了图状态转换模型，并据此设计了基于列存储模型的静态Hash索引和基于Markov模型的动态可调Hash索引。前者可以提高消息数据与本地图数据之间连接操作的局部性，避免随机磁盘存取。后者在前者基础上，根据迭代状态的转换和Markov代价收益评估模型，可以动态调整Hash桶的分割粒度，最小化磁盘存取开销。在网络通信方面，通过扩展BSP模型(Bulk Synchronous Parallel)，提出了基于EBSP模型的Hybrid迭代机制，即图数据同步处理，而消息数据跨步处理。特别的，消息跨步剪枝(ASMP)和跨步合并(ASMC)是两种跨步处理方法，可以分别剪枝消息规模和加速消息传播速度。此外，在连续划分基础上，本文提出了VCCP(Vertex-Cut basedon the Continuous Partitioning)方法，利用BFS生成图的原始局部性，VCCP通过较低的预处理开销，能够显著改善总体运行效率。最后，设计了DiterGraph原型系统，通过大量实验验证了数据划分、磁盘管理和消息通信的性能。与现有系统对比，对于单源最短路径算法，DiterGraph的运行效率是Giraph的2倍，与Hadoop和Hama相比，最高可达21倍和43倍;对于PageRank算法，采用VCCP方法后，DiterGraph的运行效率最高可达Hadoop的20倍。

目录

声明

摘要

第1章 引言

1．1 研究背景

1．1．1 云计算与大数据

1．1．2 大规模图的增量迭代计算

1．2 研究意义

1．2．1 大图增量迭代计算的特点与挑战

1．2．2 国内外研究现状

1．3 本文主要贡献及组织结构

1．3．1 本文主要贡献

1．3．2 本文组织结构

第2章 大图迭代计算的相关工作

2．1 大图迭代计算的分布式框架

2．1．1 基于MapReduce模型的计算框架

2．1．2 基于BSP模型的计算框架

2．1．3 其它分布式计算框架

2．2 大图的分布式划分

2．2．1 随机Hash划分算法

2．2．2 启发式划分算法

2．3 大图的磁盘存储与索引技术

2．4 大图处理的消息优化方法

2．4．1 同步迭代处理

2．4．2 异步迭代处理

2．4．3 基于Combine的消息优化方法

2．4．4 基于切分的消息优化方法

2．5 本章小结

第3章 分布式图划分与顶点连续编码技术

3．1 大图的分布式划分

3．1．1 大图的局部性分析

3．1．2 连续划分方法

3．1．3 连续划分方法分析

3．2 图顶点连续编码技术

3．2．1 基于Hadoop的连续编码方法

3．2．2 基于DHT的Hybrid-MT连续编码技术

3．2．3 顶点编号替换的代价分析

3．3 实验结果与分析

3．3．1 实验设置

3．3．2 图划分性能评估

3．4 本章小结

第4章 基于状态转换与Markov模型的磁盘索引技术

4．1 大图的增量迭代特点分析

4．1．1 经典算法分析

4．1．2 增量迭代特征

4．1．3 增量迭代的状态转换模型

4．2 大图的磁盘存储管理技术

4．2．1 基于列存储模型的静态Hash索引策略

4．2．2 基于状态转换与Markov模型的动态Hash索引策略

4．3 实验结果与分析

4．3．1 实验设置

4．3．2 索引性能评估

4．3．3 数据处理能力与处理效率评估

4．4 本章小结

第5章 增量迭代的消息优化技术

5．1 基于EBSP模型的Hybrid迭代机制

5．1．1 同步与异步迭代机制分析

5．1．2 典型算法分析

5．1．3 基于EBSP模型的Hybrid迭代机制

5．1．4 消息优化示例分析

5．2 基于连续划分的图顶点切分方法(VCCP)

5．2．1 基于连续划分的VCCP方法

5．2．2 顶点备份比例分析

5．3 实验结果与分析

5．3．1 实验设置

5．3．2 基于EBSP模型的Hybrid方法性能测试

5．3．3 基于连续划分的VCCP方法性能测试

5．4 本章小结

第6章 DiterGraph原型系统

6．1 系统简介

6．2 系统部署及使用方法

6．2．1 系统部署

6．2．2 用户编程指导

6．2．3 可视化管理工具

6．3 本章小结

第7章 总结与展望

7．1 本文的主要贡献与结论

7．2 未来工作

参考文献

致谢

攻读硕士学位期间的论文项目情况