图数据库之Pregel

/* 版权声明：可以任意转载，转载时请务必标明文章原始出处和作者信息 .*/
            author: 张俊林                    

节选自《大数据日知录：架构与算法》十四章，书籍目录在此

   Pregel是Google提出的大规模分布式图计算平台，专门用来解决网页链接分析、社交数据挖掘等实际应用中涉及的大规模分布式图计算问题。

1．计算模型

    Pregel在概念模型上遵循BSP模型，整个计算过程由若干顺序执行的超级步（Super Step）组成，系统从一个“超级步”迈向下一个“超级步”，直到达到算法的终止条件（见图14-13）。

    Pregel在编程模型上遵循以图节点为中心的模式，在超级步S中，每个图节点可以汇总从超级步S-1中其他节点传递过来的消息，改变图节点自身的状态，并向其他节点发送消息，这些消息经过同步后，会在超级步S+1中被其他节点接收并做出处理。用户只需要自定义一个针对图节点的计算函数F(vertex)，用来实现上述的图节点计算功能，至于其他的任务，比如任务分配、任务管理、系统容错等都交由Pregel系统来实现。

典型的Pregel计算由图信息输入、图初始化操作，以及由全局同步点分割开的连续执行的超级步组成，最后可将计算结果进行输出。

       每个节点有两种状态：活跃与不活跃，刚开始计算的时候，每个节点都处于活跃状态，随着计算的进行，某些节点完成计算任务转为不活跃状态，如果处于不活跃状态的节点接收到新的消息，则再次转为活跃，如果图中所有的节点都处于不活跃状态，则计算任务完成，Pregel输出计算结果。

    下面以一个具体的计算任务来作为Pregel图计算模型的实例进行介绍，这个任务要求将图中节点的最大值传播给图中所有的其他节点，图14-14是其示意图，图中的实线箭头表明了图的链接关系，而图中节点内的数值代表了节点的当前数值，图中虚线代表了不同超级步之间的消息传递关系，同时，带有斜纹标记的图节点是不活跃节点。

     从图中可以看出，数值6是图中的最大值，在第0步超级步中，所有的节点都是活跃的，系统执行用户函数F(vertex)：节点将自身的数值通过链接关系传播出去，接收到消息的节点选择其中的最大值，并和自身的数值进行比较，如果比自身的数值大，则更新为新的数值，如果不比自身的数值大，则转为不活跃状态。

     在第0个超级步中，每个节点都将自身的数值通过链接传播出去，系统进入第1个超级步，执行F(vertex)函数，第一行和第四行的节点因为接收到了比自身数值大的数值，所以更新为新的数值6。第二行和第三行的节点没有接收到比自身数值大的数，所以转为不活跃状态。在执行完函数后，处于活跃状态的节点再次发出消息，系统进入第2个超级步，第二行节点本来处于不活跃状态，因为接收到新消息，所以更新数值到6，重新处于活跃状态，而其他节点都进入了不活跃状态。Pregel进入第3个超级步，所有的节点处于不活跃状态，所以计算任务结束，这样就完成了整个任务，最大数值通过4个超级步传递给图中所有其他的节点。算法14.1是体现这一过程的Pregel C++代码。

2．系统架构

    Pregel采用了“主从结构”来实现整体功能，图14-15是其架构图，其中一台服务器充当“主控服务器”，负责整个图结构的任务切分，采用“切边法”将其切割成子图（Hash(ID)=ID mod n ，n是工作服务器个数），并把任务分配给众多的“工作服务器”，“主控服务器”命令“工作服务器”进行每一个超级步的计算，并进行障碍点同步和收集计算结果。“主控服务器”只进行系统管理工作，不负责具体的图计算。

    每台“工作服务器”负责维护分配给自己的子图节点和边的状态信息，在运算的最初阶段，将所有的图节点状态置为活跃状态，对于目前处于活跃状态的节点依次调用用户定义函数F(Vertex)。需要说明的是，所有的数据都是加载到内存进行计算的。除此之外，“工作服务器”还管理本机子图和其他“工作服务器”所维护子图之间的通信工作。

    在后续的计算过程中，“主控服务器”通过命令通知“工作服务器”开始一轮超级步的运算，“工作服务器”依次对活跃节点调用F（Vertex），当所有的活跃节点运算完毕，“工作服务器”通知“主控服务器”本轮计算结束后剩余的活跃节点数，直到所有的图节点都处于非活跃状态为止，计算到此结束。

    Pregel采用“检查点”（CheckPoint）作为其容错机制。在超级步开始前，“主控服务器”可以命令“工作服务器”将其负责的数据分片内容写入存储点，内容包括节点值、边值以及节点对应的消息。

    “主控服务器”通过心跳监测的方式监控“工作服务器”的状态，当某台“工作服务器”发生故障时，“主控服务器”将其负责的对应数据分片重新分配给其他“工作服务器”，接收重新计算任务的“工作服务器”从存储点读出对应数据分片的最近“检查点”以恢复工作，“检查点”所处的超级步可能比现在系统所处的超级步慢若干步，此时，所有的“工作服务器”回退到与“检查点”一致的超级步重新开始计算。

     从上述描述可以看出，Pregel是一个消息驱动的、遵循以图节点为中心的编程模型的同步图计算框架。考虑到“主控服务器”的功能独特性和物理唯一性，很明显，Pregel存在单点失效的可能。

    请思考：在容错周期选择方面，每一轮超级步都可以进行一次，也可以选择相隔若干超级步进行一次，那么这两种做法各自有何优缺点？

    解答：如果选择较短周期的容错措施，在完成任务的过程中，需要的额外开销会较多，但是好处在于如果机器发生故障，整个系统回退历史较近，有利于任务尽快完成；较长周期的容错措施正好相反，因为频次低，所以平常开销小，但是如果机器发生故障，则需要回退较多的超级步，导致拉长任务的执行过程。所以这里也有一个总体的权衡。

3．Pregel应用

    本节通过若干常见的图计算应用，来说明Pregel框架下如何构造具体的应用程序。

（1）PageRank计算

   PageRank是搜索引擎排序中重要的参考因子，其基本思路和计算原理在本章前面有所说明，此处不再赘述。下面是利用Pregel进行PageRank计算的C++示例代码。

     Compute()函数即为前面介绍的针对S超级步中图节点的计算函数F（Vertex），用户通过继承接口类Vertex并改写Compute(MessageIterator* msgs)接口函数，即可快速完成应用开发，其中MessageIterator* msgs是S-1超级步传递给当前节点的消息队列。该计算函数首先累加消息队列中传递给当前节点的部分PageRank得分，之后根据计算公式得到图节点当前的PageRank得分，如果当前超级步未达循环终止条件30次，则继续将新的PageRank值通过边传递给邻接节点，否则发出结束通知，使得当前节点转为不活跃状态。

（2）单源最短路径

    在图中节点间查找最短的路径是非常常见的图算法。所谓“单源最短路径”，就是指给定初始节点StartV，计算图中其他任意节点到该节点的最短距离。下面是如何在Pregel平台下计算图节点的单源最短路径的C++代码示例。

    从代码中可看出，某个图节点v从之前的超级步中接收到的消息队列中查找目前看到的最短路径，如果这个值比节点v当前获得的最短路径小，说明找到更短的路径，则更新节点数值为新的最短路径，之后将新值通过邻接节点传播出去，否则将当前节点转换为不活跃状态。在计算完成后，如果某个节点的最短路径仍然标为INF，说明这个节点到源节点之间不存在可达通路。

（3）二部图最大匹配

   二部图最大匹配也是经典的图计算问题，下面给出Pregel利用随机匹配思想解决该问题的一个思路。

上面的Pregel程序采用随机匹配的方式来解决二部图最大匹配问题，每个图节点维护一个二元组：（‘L/R‘，匹配节点ID），‘L/R‘指明节点是二部图中的左端节点还是右端节点，以此作为身份识别标记。二元组的另一维记载匹配上的节点ID。

算法运行经过以下四个阶段。

   阶段一：对于二部图中左端尚未匹配的节点，向其邻接节点发出消息，要求进行匹配，之后转入非活跃状态。

   阶段二：对于二部图中右端尚未匹配的节点，从接收到的请求匹配消息中随机选择一个接收，并向接收请求的左端节点发出确认信息，之后主动转入非活跃状态。

   阶段三：左端尚未匹配的节点接收到确认信息后，从中选择一个节点接收，写入匹配节点ID以表明已经匹配，然后向右端对应的节点发送接收请求的消息。左端节点已经匹配的节点在本阶段不会有任何动作，因为这类节点在第一阶段中根本就没有发送任何消息。

   阶段四：右端尚未匹配的节点至多选择一个阶段三发过来的请求，然后写入匹配节点ID以表明已经匹配。

通过上述类似于两次握手的四个阶段的不断迭代，即可获得一个二部图最大匹配结果。