Home >Database >Mysql Tutorial >图数据库之Pregel

图数据库之Pregel

WBOY
WBOYOriginal
2016-06-07 15:23:391422browse

/* .*/ author:张俊林 节选自《大数据日知录:架构与算法》十四章,书籍目录在此 Pregel是Google提出的大规模分布式图计算平台,专门用来解决网页链接分析、社交数据挖掘等实际应用中涉及的大规模分布式图计算问题。 1.计算模型 Pregel在概念模型上遵循BSP

/*  .*/
            author: 张俊林                    



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


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

1.计算模型

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

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

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

图数据库之Pregel

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

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

   图数据库之Pregel

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

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

图数据库之Pregel

2.系统架构

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

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

   图数据库之Pregel

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

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

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

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

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

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

3.Pregel应用

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

(1)PageRank计算

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

图数据库之Pregel

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

(2)单源最短路径

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

图数据库之Pregel

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

(3)二部图最大匹配

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

图数据库之Pregel

图数据库之Pregel

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

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

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

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

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

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

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
















Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn