随着网页检索技术、社交网络、生物信息科学的快速发展和人脑计划实施,图论知识和算法得到了广泛应用和发展。图领域数据规模正以前所未有的速度急剧增加,云计算技术的飞速发展,分布式图计算已成为已经成为学术界与工业界的研究热点。提升海量图数据划分效率,降低内存存储开销,减少机器间的通信量等等,已经成为分布式的图计算平台性能优化的关键性问题。GraphA是本文作者基于Spark分布式平台实现了一个简单的图分布式处理平台,本文通过研究GraphA的数据划分和内存存储管理效率探讨了分布式图计算性能优化技术,重点围绕自适应的分区算法和基于ART索引的存储方式展开了深入研究。本文的主要研究内容和贡献包括:一、深入研究并分析了分布式图计算的基本原理和特点,包括MapReduce、BSP、GAS三种基本的分布式计算框架,这些是本文优化方案的基础支撑技术;另外,重点论述了已有的图数据划分算法及相关存储技术,总结前人研究成果的优点和应用价值,并结合“自然图”的幂率分布特点和应用实际,指出其各自的局限性。二、针对海量图数据的划分问题,提出了自适应的图分割算法。无论是社交网络数据还是网页数据都是服从幂率分布的特征,即数据中存在高维度的点和低维度点,相比现有的点分割,边分割和混合分割的划分算法相比,自适应的分区算法不区分高维度点和低维度点,提供一种统一的划分方案,通过设计一系列序号递增的哈希函数,配合使用全局的分布式分区表记录所有点的分区情况,实现图数据的高效分区。实验结果证明,自适应分区算法能够均衡计算负载,同时能够保留输入的图数据原始的局部性,减少每次迭代过程中分区之间的通信量,避免在数据划分阶段出现全局的shuffle情况,从而满足图计算在数据划分问题上的性能优化需求。三、针对图的内存存储管理效率问题,提出了基于ART索引的图存储模型。图算法具有增量更新的特点,并不是每一轮迭代都更新图中所有点的属性或所有边的属性。Spark RDD(弹性分布式数据集)具有Immutable特性,当初设计为了保证数据一致性,对于图计算增量更新的特点,Spark RDD会从原数据做一次拷贝,所以一次RDD迭代更新的代价很大。GraphA引入一种细粒度更新的RDD存储结构,该结构采用ART索引,在保证数据一致性的同时,实现图数据细粒度的更新操作,加快图的查询更新速度,降低内存开销。本文对大规模图数据划分算法和图数据存储技术的优化进行了探索,研究成果对于分布式图计算平台的性能提升有一定的理论价值和指导意义。最后,本文通过大量实验验证了GraphA的性能。