如今,很多数据是以图的结构展现的,但是分析这种类型的数据一直没有一个高效的可扩展的分布式系统。于是Google又坐不住了,开发出了一个叫做Pregel的可拓展,分布式,能处理大规模图数据的系统
计算模型
送入Pregel的数据是一个有向图(directed graph),每一个顶点(vertex)用一个字符串标注。我们可以在每一个顶点和边(edge)上定义一个可修改的数值。每一条边还记录了指向的顶点字符标注。
数据送入之后,图在系统中建好(initialization),之后各个节点开始运行算法处理数据。当一个节点结束计算之后,该节点停止运行,如果有新任务分配,则又重新开始运行,然后再次停止。当所有节点全部停止运行,并且没有新任务分配的时候,整个算法停止。下面举一个例子来解释上述概念:
在第一行我们有一个有向图,每一各节点有一个数字,当节点收到了一个比自己的数字更大的数字,该节点将数字修改成这个较大值,然后将这个值发送给相连的节点,当所有节点的数字都是最大的时候,算法停止。