论文部分内容阅读
随着电子商务、社交网络的发展,大规模分布式图处理的作用越来越重要,被广泛的应用在链接分析、产品推荐等应用中。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框架的实际应用创造了有利的条件。