异步大规模图处理框架Maiter的负载均衡技术及累积迭代算法的研究

摘要

随着电子商务、社交网络的发展，大规模分布式图处理的作用越来越重要，被广泛的应用在链接分析、产品推荐等应用中。Maiter框架作为完全异步的大规模分布式图处理框架，采用DAIC计算模型，避免了同步开销，提升了收敛速度，极大的提高了大规模图处理的效率。为了进一步的提高Maiter框架可用性和通用性，本文的工作在两个方面展开。 在Maiter框架可用性方面，本文采用集中式动态负载均衡机制解决了Maiter框架的负载均衡问题。在负载均衡机制实现的过程，解决了诸多难题。1）提出了基于Hash数据块的数据管理方式和消息分桶标记定位机制，极大的方便了负载均衡处理过程中的数据迁移和迁移数据重定位。2）从理论上证明了Maiter框架在算法计算的过程中进行数据迁移，对整个集群的影响并不会改变最终的计算结果，从理论上保证了计算过程中数据迁移的正确性。3）提出了基于缓存的错位消息中转机制，来处理数据迁移的过程中产生的错位消息。并从理论上证明了该机制的正确性。4）在以上工作的基础之上，在Maite框架上实现了基于数据块的集中式动态负载均衡机制。实验结果显示，该机制在集群不存在负载倾斜时，几乎不会增加系统的开销。存在负载倾斜时，可有效的处理负载问题，并提升框架整体的计算效率。 在Maiter框架的通用性方面，本文采用了DAIC计算模型的思想，改进了传统的SimRank算法，1）本文提出Asyn-SimRank算法，该算法采用迭代-累积的方式完成迭代计算，异步执行SimRank的核心迭代过程，避免了大规模分布式计算中的大量同步开销，同时有效降低计算量并减少通信开销;2）提出关键点优先调度计算，提升了Asyn-SimRank算法的全局收敛速度。3）证明了Asyn-SimRank算法的正确性和收敛性以及关键点优先调度计算的有效性。4）在支持异步迭代的分布式框架Maiter上实现了Asyn-SimRank算法。实验结果显示，相比较于Hadoop，Spark上实现的SimRank算法和Delta-SimRank算法，Asyn-SimRank算法大大提升了算法的计算效率，加速了算法收敛。 经过本文的一系列工作，Maiter框架的通用性和可用性进一步提升，为Maiter框架的实际应用创造了有利的条件。

目录

声明

摘要

第1章绪论

1．1研究背景

1．1．1分布式计算

1．1．2分布式算法

1．2目的和意义

1．3国内外研究现状

1．4主要研究内容

1．4．1 Maiter框架的负载均衡处理问题的研究

1．4．2异步累积迭代算法的研究

1．5论文章节安排

第2章DAIC模型及Maiter框架

2．1传统同步迭代计算

2．2传统异步迭代计算

2．3 DAIC计算模型

2．3．1 DAIC计算模型的前提条件

2．3．2 DAIC计算模型的推导

2．3．3 DAIC计算模型的优先级迭代

2．4 Maiter框架

2．4．1 Maiter框架的实现

2．4．2 Maiter框架的优先级迭代的实现

2．4．3 Maiter框架的API

2．5本章小结

第3章Maiter框架的负载均衡技术

3．1负载不均衡的原因

3．1．1同步框架负载不均衡的原因

3．1．2 Maiter框架负载不均衡的原因

3．2负载均衡方案的选择

3．3负载均衡处理决策算法

3．3．1决策算法设计思路

3．3．2负载均衡决策算法

3．4数据迁移

3．4．1数据迁移产生的问题

3．4．2对Maiter框架数据管理方式的改进

3．4．3数据迁移的正确性保证

3．5迁移数据重定位

3．6错位消息处理

3．6．1错位消息的产生及影响

3．6．2基于缓存的消息中转解决方案

3．6．3基于缓存的消息中转机制正确性证明

3．7负载均衡处理详细过程

3．8本章总结

第4章异步累积迭代算法

4．1研究内容介绍

4．2 SimRank算法原理与Hadoop实现

4．2．1 SimRank算法原理

4．2．2 Hadoop框架上的实现

4．3 Asyn-SimRank算法

4．3．1同步迭代-累积形式一Delta-SimRank

4．3．2异步迭代-累积形式一Asyn-SimRank

4．3．3收敛性与正确性证明

4．4关键点优先调度

4．4．1基本思想

4．4．2理论证明

4．5 Asyn-SimRank算法的分布式实现

4．．5．1输入图的预处理

4．5．2分布式环境上的实现

4．6本章小结

第5章性能实验与评价

5．1负载均衡性能验证

5．1．1实验数据集及分布式环境

5．1．2负载均衡机制的有效性

5．1．3负载均衡机制的开销

5．1．4数据分块数量对系统的影响

5．2 Asyn-SimRank性能验证

5．2．1实验数据集及实验环境

5．2．2总体运行时间对比

5．2．3收敛速度对比

5．2．4通信量对比

5．2．5算法与分布式环境规模的关系

5．3本章小结

第6章总结与展望

6．1总结

6．2展望

参考文献

致谢

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