基于启发式规则大图数据分布式划分的研究与实现

摘要

近年来，由于社交网络等发展，图数据规模变的越来越大。在如此大图上进行的计算超出了传统集中式计算系统的能力，因此应用程序部署已经从少量的HPC服务器或超级计算机转移到了云环境下的商业集群。为了支持复杂的图处理计算（如，Pagerank，最短路径等），需要将图数据进行分布式并行处理，以BSP模型为基础的图计算系统变应运而生。而图数据划分是基于BSP编程模型的大规模图处理系统需要解决的重要问题之一。特别在云环境下，由于数据规模过大，更需要将图数据划分为多个分区，交由集群中的计算节点并行处理。对于某个特定的社交网络数据，用户数据往往呈阶段性递增的方式产生，而图计算系统在每次计算都进行一次在线的图划分并不是一种高效的方式，因为在每次计算的过程中，计算系统都要重新的加载图数据并进行数据划分和分发，消耗了不必要的时间，并且在线的图划分难以达到很好的划分效果，即保证分区的负载均衡和分区间的交互边数尽可能少。 为此，在项目组基于BSP模型开发了可进行大图计算的图处理系统BC-BSP的基础上，本文主要基于LDG启发式规则设计和实现了适用于基于BSP模型系统的离线图划分算法。本文的主要贡献如下:(1)本文引入了顶点收益模型，将LDG启发式规则应用在数据划分上，保证了各个分区的负载均衡性，减少了分区间的交互边，保留了图的局部拓扑性。(2)分析并发现了LDG启发式规则在顶点随机输入时性能波动较大的缺陷，提出了基于影响力的两阶段划分流程，即先划分影响力较大的顶点，然后再划分影响力较小的顶点，这样可以在划分过程中维护图的拓扑结构。(3)应用LDG启发式规则进行图划分需要维护一个全局的顶点映射信息，因此难以在大图上进行扩展，本文为了提高LDG处理顶点的量级，设计了两种方案，一种是基于分布式内存的分布式LDG划分算法，将全局的顶点信息分布映射到不同的计算节点上，来解决集中式映射表内存占用的瓶颈。另一种是先将原图进行浓缩，然后对浓缩图进行处理。因此，本文提出了以基于高介数边删除的子图浓缩算法，该算法能够使得浓缩图极大地维护图的拓扑结构。基于浓缩图，本文提供了两种划分策略，一种是基于顶点迁移的划分算法，另一种是利用基于分布式内存的策略划分浓缩图。对于基于分布式内存策略划分浓缩图的方案，能够极大的扩展图顶点划分的量级。 本文将提出的数据划分算法和一次划分多次使用的思想应用于BC-BSP系统，通过实验证明，其完成了BC-BSP系统中图划分模块的功能，具有良好的可扩展性和稳定性。

目录

声明

摘要

第1章绪论

1．1研究背景

1．2国内外研究现状

1．3本文主要工作

1．4本文组织结构

第2章相关技术概述

2．1 Hadoop简介

2．1．1分布式文件系统HDFS

2．1．2 MapReduce编程模型

2．1．3 Zookeeper

2．2 BSP模型

2．3图划分技术概述

2．3．1图的基本概念

2．3．2图划分问题描述

2．3．3典型的图划分算法及负载均衡算法介绍

2．3．4大图处理系统中图划分技术介绍

2．4本章小结

第3章BC-BSP系统及数据划分模块简介

3．1系统体系结构

3．2系统处理流程

3．3数据划分子模块

3．4离线划分结果与BC-BSP系统的耦合

3．5本章小结

第4章基于分布式内存的启发式划分算法的实现

4．1 LDG启发式规则的改进

4．1．1顶点放置收益模型

4．1．2 LDG启发式规则的局限性

4．1．3顶点输入顺序的控制

4．2 LDG划分算法的分布式设计

4．2．1全局顶点路由信息以及全局分区信息的设计

4．2．2分布式内存的设计

4．3基于分布式内存LDG划分算法的实现

4．3．1划分处理流程设计

4．3．2基于分布式内存的启发式划分的实现

4．4．4本章小结

第5章基于子图浓缩的启发式划分算法

5．2．1现有子图浓缩算法的分析

5．2．2边的介数中心性的估计

5．2．3基于高介数边删除的子图浓缩算法

5．3浓缩顶点的划分及整图还原

5．3．1集中式浓缩顶点划分

5．3．2分布式浓缩顶点划分

5．3．3浓缩图还原实现

5．5本章小结

第6章划分效果性能评估

6．1实验环境

6．2划分性能测试

6．2．1测试数据

6．2．2分区间耦合度测试

6．2．3负载均衡测试

6．2．4划分时间测试

6．2．4子图浓缩测试

6．2．5扩展性测试

6．3 PageRank测试算法

6．4系统集成测试

6．5本章小结

第7章总结与展望

7．1本文工作总结

7．2未来工作展望

参考文献

致谢

攻硕期间参加的项目