分布式批同步BSP

Pregel、GraphLab、GraphX都是基于BSP（Bulk Synchronous Parallel）模式，即整体同步并行。一次计算过程由一系列全局超步组成，每一个超步由并发计算、通信和同步三个步骤组成。从垂直上看,一个程序由一系列串行的超步组成。从水平上看，在一个超步中，所有的进程并行执行局部计算。BSP最大的好处是编程简单，但在某些情况下BSP运算的性能非常差，系统速度取决于最慢的计算任务，即木桶原理。Spark Graphx中也实现了Pregel的API。

Pregel

Pregel采用迭代的计算模型：在每一轮，每个顶点处理上一轮收到的消息，并发出消息给其它顶点，并更新自身状态和拓扑结构等。算法是否能够结束取决于是否所有的顶点都已经vote标识其自身已经达到halt状态了。顶点通过将其自身的状态设置成halt来表示它已经不再active。

Pregel框架的缺点：这个模型虽然简单，那就是对于邻居数很多的顶点，它需要处理的消息非常庞大，所以对于符合幂律分布的自然图，这种计算模型下很容易发生假死或者崩溃。

GraphLab

GraphLab将数据抽象成Graph结构，将基于顶点切分的算法的执行过程抽象成Gather、Apply、Scatter三个步骤。如下：需要完成对V0邻接顶点的求和计算，将顶点V0进行切分，边关系以及邻接点部署在两台处理器上，各台机器上并行进行求和运算，然后通过master（蓝色）顶点和mirror（橘红色）顶点的通信完成最终的计算。

1.Gather阶段，工作顶点的边从连接顶点和自身收集数据。

2.Apply阶段，mirror将gather阶段计算的结果发送给master顶点，master进行汇总并结合上一步的顶点数据，进行进一步的计算，然后更新master的顶点数据，并同步给mirror。

3.Scatter阶段，工作顶点更新完成之后，更新边上的数据，并通知对其有依赖的邻结顶点更新状态。

由于gather/scatter函数是以单条边为操作粒度，所以对于一个顶点的众多邻边，可以分别由相应的节点独立调用gather/scatter函数，从而避免Pregel模型的问题。

GraphX

GraphX公开了类似Pregel的操作，是Pregel和GraphLab抽象的一个融合。在GraphX中，操作者执行一系列的超步，在这些超步中，顶点从之前的超步中接收进入消息，为顶点属性计算一个新的值，然后在以后的超步中发送消息到邻居顶点。不像Pregel而更像GraphLab，消息通过边triplet的一个函数被并行计算，消息的计算既会访问源顶点特征也会访问目的顶点特征。

此外，GraphX的优点还包括：

1.允许用户把数据当做一个图和一个集合(RDD)，而不需要数据移动或者复制。

2.Spark GraphX可以无缝与Spark SQL、MLLib等结合，方便且高效地完成图计算整套流水作业。