Pregel：基于图分割的图结构数据并行处理

jopen 11年前

Pregel设计在google的计算机集群结构之上。一个计算机集群（cluster）就是通用PC按rack（一组PC机）构成，Rack之间具有较高的数据传输速度。集群中通常包含一个域名服务器（namenode），采用分布式文件系统，例如：GFS（google 分布式文件系统），HDFS（Hadroop 分布式文件系统），TFS（淘宝分布式文件系统）等。域名服务器包含了分布式文件系统中文件名与文件地址之间的键值对索引（index）。

Pregel库首先分割图结构的数据，每一个分割包含一组顶点以及由这组顶点向外的边，每个顶点由一个编号（vertex_ID）唯一确定。库默认的N份分割函数是哈希函数（hash(vertex_ID) mod N），当然用户可以自己编写分割函数以代替它。

将各顶点分配给计算机的方法在Pregel中对用户并不是很透明。某些应用采用默认的分配方式性能还好，但是有时需要用户定义分配函数以更好的利用本地数据。例如，对于web graph（网页图），通常将顶点分配给其对应网页所在站点。

Pregel程序运行流程：

  1. 用户程序的多份拷贝开始在集群上运行。其中一份拷贝作为master（负责者），只负责协调其余worker（工作者）的活动。

  2. master决定图结构数据的分割，并将一份或多份分割分配给worker。分割数量可以由用户控制，更大的分割数量通常具有更好的并行性，与均衡性，因此能提高性能。每个worker负责维护它所分配的那部分图的分割的状态，执行用户定义的compute()方法，以及管理消息的接收与发送。每个worker都具有图分割的所有信息。

  3. master发送给各worker相应的用户输入信息。

  4. 待所有worker都就绪后，master发送指令启动一次迭代（superstep）。一个分割对应一个进程，并为分割中的每个顶点执行compute()方法，接受消息，发送消息。当worker结束迭代之前，会给master发送尚活跃的顶点数。循环该步，直到所有顶点都终止（non-active）。

  5. 计算结束，master发送指令，worker保存graph计算结果。