Pregel简介
谷歌公司在到公布了GFS、MapReduce和BigTable谷歌在后Hadoop时代的新“三驾马车” Caffeine,Dremel和PregelPregel是一种基于BSP模型实现的并行图处理系统为了解决大型图的分布式计算问题,Pregel搭建了一套可扩展的、有容错机制的平台,该平台提供了一套非常灵活的API,可以描述各种各样的图计算Pregel作为分布式图计算的计算框架,主要用于图遍历、最短路径、PageRank计算等等问题
如图所示,从0到各个顶点的单源最短路径是多少?
Pregrel求解流程
实现代码
class ShortestPathVertex: public Vertex<int, int, int> {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();}};
顶点值变化
s0代表第一个超步,依次类推
各超步产生的消息队列
格式(target_id,edge_value)
s0: (1,100) (2,30) (4,10)s1: (1,90) (3,90) (3,60)s2: (1,70)
s2后没有消息队列产生,程序执行完毕
结果
节点0到各个顶点的单源最短路径: