在社交网络关系挖掘、网页排序、推荐系统以及自然语言处理等大规模数据挖掘和机器学习应用的推动下,使用图数据结构来描述数据及数据之间关系的分布式图计算模型获得了日益广泛的应用。图算法由于需要多轮迭代,各顶点数据间存在复杂联系,计算过程依赖点对点通信,因此以MapReduce及其开源实现Hadoop为代表的传统面向数据并行(Data-parallel)的计算模型难以提供高效的支持。为解决对于图计算的迫切需要和现有的计算平台无法满足大规模图计算需求的问题,Google公司提出了基于整体同步模型(Bulk Synchronous Parallel)的Pregel。Pregel提出像顶点一样思考的编程模型,用户只需提供一个简单的compute函数,系统负责处理顶点调度和数据通信等。Pregel将图计算任务的执行抽象成一个超步(superstep,也称轮),每一个超步由顶点计算(computation),数据通信(communication)和全局同步(barrier)组成。用户提供的顶点计算函数在当前超步中只能访问该顶点自己的信息和来自(入边)邻接顶点在上一个超步发送的消息(message),而发送给(出边)邻接顶点的消息会在下一个超步到达。Pregel所提出的同步计算模型编程简单,计算具有确定性,易于调试。然而Pregel采用的纯消息传递(pure message passing)机制仅支持单向的数据推送(Push),因此对于需要主动获取邻接顶点信息的拉模型(Pull-mode)图算法,Pregel在整个执行过程中必须保持所有顶点处于活跃状态(执行计算和发送消息),导致大量针对已收敛顶点的重复计算和发送大量具有相同数据的消息,严重影响系统性能。本文提出使用备份顶点模拟分布式只读共享内存优化原有的纯数据通信机制,克服了原有模型消息量大、对于拉模型算法存在重复计算和重复消息的问题,并且针对日益普遍的多核集群提出了针对多核架构的支持,进一步优化了分布式图计算系统的性能。基于Hama (Pregel的Apache开源实现)的实现在一系列应用和数据集的测试显示新的通信机制能使系统的总体性能提升2.06倍到8.69倍。同步计算模型虽然调度简单,但是每轮计算都只能使用邻接顶点上一轮的数据进行计算,收敛较慢。与同步计算模型相对,卡耐基梅隆大学的研究人员开发的GraphLab率先提出了异步计算模型。在异步计算模型中,各顶点在更新自身数据后会立即通过消息发送更新,因而邻接顶点可以使用最新的数据进行计算,因而整体计算收敛较快。随后针对现实世界的图通常是符合幂律的不规则分布图(即少数的点可能拥有大多数的边),作者在GraphLab的基础上提出PowerGraph,通过vertex-cut(“顶点切分”)的划分方法将顶点计算分散到各个节点上并行执行,以解决各个节点计算和通信的不平衡问题。然而异步计算模型虽然计算收敛快,但是需要为所有未收敛顶点维护全局(分布式)的调度队列,并且要保证在异步访问的条件下各顶点数据的一致性,开销很大。同步和异步两种计算模型各有优缺点,为结合以上两种计算模型的优点,避免各自的缺点,本文提出了混合计算模型。混合计算模型使用同步的调度方法避免繁重的调度开销,同时采用异步的数据传输机制使得各顶点能够使用邻接顶点的最新数据计算,加快整体计算的收敛速度。基于PowerGraph平台实现的混合模型引擎在两个典型图算法和三组真实大规模图数据集上的评测显示,混合计算模型相对于同步模型平均可以减少30%的计算量,性能可以提升至其1.2倍到2.4倍,相对于异步模型由于调度开销的减少,性能最高可达到其4.6倍。