Pregel导读

Pregel论文发表在2010年ACM/SIGMOD( Special Interest Group on Management Of Data)上,其名字是欧拉七桥问题中那条河的名字。

Pregel志在构建通用图算法计算模型和引擎,基于网页库(链接关系),社交网络用户数据(社交关系),交通路线图(距离),新闻文章的相似性(聚类算法),疾病爆发路径,解决一些实际问题,如pagerank、社交发掘、交通推荐等问题。

在实际设计系统时,通常遵循如下的思路: 问题集合(如pagerank)-->问题模型抽象(矩阵迭代计算)-->计算范式(基于消息的并行计算,BSP计算模型)-->具体的系统(pregel)。

pregel的关键字:大规模(分布式),高效,通用,自动容错:

如果不是大规模,现在已经有较成熟的单机图算法库;BG,LEAD,NetworkX,JDSL,Standford GraphBase,FGL
如果不要求高效,MR计算可以解决问题
如果不要求通用,否则针对具体算法实现一套分布式系统肯定最match
如果不要求容错,一些专用的并行图计算系统可更高效地解决问题,如Parallel BGL和CGMgraph
 
为什么使用BSP计算模型?

Pregel计算系统的的核心是Valiant提出的BSP计算模型。V和S。S是序列执行的,故天生对异步系统中经常出现的死锁以及临界资源竞争免疫。同步性简化了算法实现。因为BSP模型在超级步之间需要数据同步,所以存在部分节点慢部分节点快的情况,可能你会觉得快节点因为空等而导致计算效率不高。但因为图计算的应用中顶点的数量要远远大于机器的数量,所以一台机器上会分布大量节点,上面既有慢节点又有快节点,当数量很大时就可以通过随机性实现负载均衡,使得实际的逻辑上的慢节点不存在)。

为什么使用消息通信的并行计算范式?

图计算一般具有比较差的内存访问局部性,适合消息传输的方式,如果使用MR的话,通常需要一个MR chain,序列化发序列化开销巨大;而基于消息通信的模型也能表达所有的图算法,且因为无需 remote reading,通过消息异步发送使得计算的实时性更高。

图的表示和计算:

Pregel计算模型使用非常直接的方式表示一张有向图:顶点(vertex)拥有一个ID一个值,每一条有向边(directed edge)包含源顶点ID、目标顶点ID以及一个值。计算运行在顶点上,边上无计算。
1.将顶点按顶点ID分配到不同的partition,每个worker处理一个或多个partition;
2.所有worker都知道the set of (partition) assignments for all workers,这就是路由信息;
3.每个worker可以当作vertex id到vertex state的map,state包括vertex value和出边集合及它们的值。
4.master除了作作业协调工作,还维护来整个作业的状态,包括自定义的聚合值
5.聚合值先在每个实例进行局部聚合,然后在master进行汇总,下一个超级步开始前,master会把聚合值同志给所有worker。可以使用aggregator来检测是否满足收敛条件。
 
API的特点:
1.提供了VertexValue,EdgeValue,MessageValue集中类型抽象,通过PB来实现灵活性、扩展性
2.有一个string类型的id(address)
3.通过iterator来实现批量操作
4.自定义combiner优化消息传输和存储的数据量(combiner作用在输出或输入队列)
5.自定义aggregator收集全局信息
 
容错:
1.通过checkpoint,每个超级步开始前持久化,master自己也会保存aggregator的值
2.master主动发送心跳(ping)给所有worker,如果worker很长一段时间没有收到心跳,则主动结束;如果master没有收到worker回复,则标记该worker失败,重新调度。
3.如果worker故障,master重新分配到可用的worker集合,加载checkpoint的数据重新计算
 
 
 

Pregel导读

上一篇:vue中使用高德地图


下一篇:Wi-FiR CC3000 模块