顶点中心模型

在单机环境下，开发者可以轻松实现图分析算法，因为他们能全局查看图结构并自由遍历所有顶点和边。当图数据规模超过单机内存容量时，图数据必须被分区存储到分布式内存中，从而导致整个图结构的不可分割性。

为了让开发者能在这种环境下简洁地表达图分析算法，人们开发了以顶点为中心的编程模型，其核心理念是"像顶点一样思考"。具体而言，图分析算法会在图的顶点上迭代执行用户定义的程序。用户定义的顶点程序通常会以其他顶点的数据作为输入，并将顶点的计算结果发送给其他顶点。顶点程序会迭代执行若干轮次，直到满足收敛条件为止。与图的全局视角不同，以顶点为中心的模型采用局部、面向顶点的视角。

以顶点为中心的模型理念催生了许多编程模型，包括谷歌提出的Pregel模型和GAS模型。这些编程模型已广泛应用于各类图处理系统，如Giraph、GraphX和PowerGraph。

Pregel 模型

Pregel最初由谷歌在2010年发表的SIGMOD论文中提出。基于Pregel模型的图分析算法由一系列迭代（称为超步）组成。

"在超步(superstep)过程中，框架会为每个顶点并行调用用户自定义的函数。该函数定义了单个顶点V在单个超步S中的行为。它可以读取在超步S − 1中发送给V的消息，向其他顶点发送将在超步S + 1接收的消息，并修改V及其出边的状态。消息通常沿着出边发送，但也可以发送给任何已知标识符的顶点。"

Pregel模型。

如下图所示，在每次迭代中，如果一个顶点没有收到任何消息，其状态将变为非活跃。一旦接收到消息，其状态将再次变为活跃。
当没有任何顶点发送消息时，迭代终止，表示达到停止状态。

顶点函数可以在每个顶点并行调用，因为各个顶点通过消息传递进行通信。

通过Pregel模型，单源最短路径(SSSP)的顶点程序可以表示为以下形式，其中当顶点从其他顶点接收到消息时，会执行Compute函数，并在计算后向其他顶点发送更新。

void Compute(MessageIterator* msgs) {
    int mindist = IsSource(vertex_id()) ? 0 : INF;
    for (; !msgs->Done(); msgs->Next())
        mindist = min(mindist, msgs->Value());
    if (mindist < GetValue()) {
        *MutableValue() = mindist;
        OutEdgeIterator iter = GetOutEdgeIterator();
        for (; !iter.Done(); iter.Next())
            SendMessageTo(iter.Target(), mindist + iter.GetValue());
}
    VoteToHalt();
}

GAS模型

然而，当面对遵循幂律分布的自然图时，Pregel的性能会急剧下降。为解决这个问题，PowerGraph提出了针对顶点切割图分区策略的GAS（Gather-Apply-Scatter）编程模型。Gather函数在每个分区本地运行，然后每个镜像向主节点发送一个累加器。主节点运行Apply函数后将更新后的顶点数据发送给所有镜像。最后，Scatter阶段在镜像上并行运行以更新相邻边上的数据。

GAS模型。

在分析引擎中模拟Pregel模型

正如我们在论文中所证明的，GraphScope的分析引擎能够模拟以顶点为中心的模型。我们已在分析引擎中实现了对Pregel模型的支持，您可以使用Pregel API编写自己的算法。此外，如果您已有基于Giraph或GraphX实现的图应用，可以直接在GraphScope上运行它们。更棒的是，该分析引擎的性能表现优于Giraph和GraphX。

请参考相关教程。

• 教程：在GraphScope上运行Giraph应用

• 教程：在GraphScope上运行GraphX应用