13.3.3　Google Pregel

Google Pregel用于图模型迭代计算，图中的每个节点对应一个任务，每个图节点会产生输出消息给图中与它关联的后续节点，而每个节点会对从其他节点传入的输入消息进行处理。

Pregel中将计算组织成“超步”（superstep）。在每个超步中，每个节点在上一步收到的所有消息将被处理，并且将处理完后的结果传递给后续节点。

Pregel采用了BSP（Bulk Sychronous Parallel，整体同步并行计算）模型。每个“超步”分为三个步骤：每个节点首先执行本地计算，接着将本地计算的结果发送给图中相邻的节点，最后执行一次栅栏同步，等待所有节点的前两步操作结束。Pregel模型会在每个超步做一次迭代运算，当某次迭代生成的结果没有比上一次更好，说明结果已经收敛，可以终止迭代。

图　13-4　Pregel BSP计算模型

假设有一个带边权重的图，我们的目标是对图中的每个节点计算到其他任一节点的最短路径长度。一开始，每个图节点a都保存了诸如（b,w）对的集合，这表示a到b的边权重为w。

（1）超步

每个节点会将（a,b,w）传递给图中与它关联的后续节点。当节点c收到三元组（a,b,w）时，它会重新计算c到b的最短距离，如果w+v＜u（假设当前已知的c到a的最短距离为v,c到b的最短距离为u），那么，更新c到b的最短距离为w+v。最后，消息（c,b,w+v）会传递给后续节点。

（2）终止条件

当所有节点在执行某个超步时都没有更新到其他节点的最短距离时，说明已经计算出想要的结果，整个迭代过程可以结束。

Pregel通过检查点（checkpoint）的方式进行容错处理。它在每执行完一个超步之后会记录整个计算的现场，即记录检查点情况。检查点中记录了这一轮迭代中每个任务的全部状态信息，一旦后续某个计算节点失效，Pregel将从最近的检查点重启整个超步。尽管上述的容错策略会重做很多并未失效的任务，但是实现简单。考虑到服务器故障的概率不高，这种方法在大多数时候还是令人满意的。