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