从 Vertex 到 Subgraph 再到 PIE: 并行图计算编程模型概览

对于图计算来说，一个基础性的问题是如何选取合适的编程模型。它不仅决定了用户上手的难易程度，还对系统的整体性能有很大的影响。在本篇文章中，我们将介绍三种常见的并行图计算编程模型，并分析各种编程模型的优缺点。

作为一种重要的大数据来源，图（Graph）数据包含一组对象（顶点）及其关系（边），可以直观、自然地表示现实世界中各种实体对象以及它们之间的关系。为了挖掘蕴含在图数据中丰富的信息，各种各样的图分析算法不断涌现，常用的算法包括 PageRank、社区检测、最短路和可达性（reachability）分析、中心度分析等。

在单机环境下，用户拥有完整的图结构信息，可以很方便地对图中的点和边进行访问，因而可以比较顺利地开发出图分析算法。在真实的工业场景中，图数据规模十分巨大，一张大图可能包含数十亿个点和数千亿条边，远远超过了单机的处理能力，因而必须将图数据在分布式的环境下存储并利用并行计算技术进行处理。为了方便用户在分布式/并行环境下开发出图分析算法，学术界和工业界提出了各种各样的并行图计算编程模型。

Think like a vertex

点中心（vertex-centric）编程模型最早由 Google 的研究人员提出，并在 Google 图计算系统 Pregel 中得到应用。点中心编程模型遵循 “think like a vertex（像图中的节点一样进行思考）” 的编程思想，图中的每个节点可以访问其直接邻居，并与这些邻居节点交换信息。在点中心模型中，一个图分析算法的计算过程被分为多个迭代轮次（superstep）。在每个迭代中，图中的每个节点都会执行一个类似 VertexProgram 的用户自定义函数。如下图所示，Vertex Program 定义了一个节点在接收到其他节点发送的消息之后如何利用这些消息更新自己的状态，以及一个节点在自己的状态更新后如何向其他节点发送消息以激活其他节点的计算。当所有的节点都不再发送消息时，点中心模型认为计算达到收敛的状态，算法执行结束。

在点中心编程模型下，单源最短路径的 Vertex Program 可以用如下代码表达。

def VertexProgramForSSSP():
  # receive and merge incoming messages
  incoming_msgs = ReceiveMessages()
  merged_msg = Reduce(incoming_msgs, MIN)
    
  # update vertex property
  if dist > merged_msg:
    dist = merged_msg
    
  # send messages to neighbors
  for neighbor in neighbors:
    if dist + edge_weight < neighbor_dist:
      SendMessage(neighbor, dist + edge_weight)

点中心模型创新性地提出了一种分布式图算法编程思想，相对于 MapReduce 等无法支持迭代式图计算的模型是一大进步，但是它也有一定的局限性。现实世界中的很多图数据遵循着“幂律(power-law)分布”，即图中少部分的节点会拥有大部分的边。实验发现，点中心编程模型在存在幂律分布的图数据上会发生计算负载不均衡的现象，性能受到大幅影响。为了解决这个问题，来自 CMU 的研究者在点切割（vertex-cut）图分区算法的基础上，提出了一个名为 GAS（Gather-Apply-Scatter） 的编程模型。在点切割中，图中的每个节点可能会在多个图分区出现，其中一个分区的点被称为 master 节点，而在其他分区出现时被称为 mirror 节点。GAS 编程模型包含 Gather、Apply 和 Scatter 三个阶段，对于图中的每个节点，首先 Gather 函数根据每个分区的本地信息计算出一个中间结果，然后所有的 mirror 节点将中间结果发送给 master 节点，由 master 节点执行 Apply 函数，并将执行结果同步给 mirror 节点，最后所有的 master 和 mirror 节点执行 Scatter 函数将相应的更新结果发送给本分区中的邻居节点。

在 GAS 编程模型下，单源最短路径算法如下代码所示。

def GASForSSSP():