每周学点大数据 | No.47 BSP 模型下的单源最短路径

No.47期

BSP 模型下的单源最短路径

我们先来举个例子吧。单源最短路径也是一种很典型的图论问题，前面我们提到过，就是求解从一个源点到各个节点的最短距离，有时带上求解最短路径。我们来看看如何“把自己想象成一个节点”。以下面这个图为例。

在这个图中，我们选取的源点是0 号节点。图中有一些有向边，每条有向边都有一个权值。

我们要求解的就是源点0 抵达其他4 个节点的最短距离。

在第一轮迭代中，每一个其他节点都向外发送自己的权值，节点的权值表示当前状态下源点0 到它的最短距离。此时其他节点到源点0 的最短距离都是∞。而源点向外发送其出度边的值，就像这样：

经过了第一轮迭代，图中的权值会变成这样：

源点0 右侧的两个节点的权值进行了更新，它们拥有当前状态下到源点的最短距离10 和5。

从第二轮开始，每一个节点向外发送的权值都略有变化，每一个节点向它每一个出度顶点，这条出度边的权值与其当前到源点的最短距离，也就是其顶点的权值。结果就是这样：

小可：哦，我懂了，接下来要比较每一个节点收到的值是不是比当前的最短距离要小，如果是，就要替换当前的节点权值。

Mr. 王：没错，经过这一轮替换，结果就是这样：

这样每一轮节点都继续执行如同第二步的工作，有些节点在某轮中既不发出消息，也不接收消息，这样这些节点就停摆了。一旦在某轮中所有的节点都停摆了，整个算法就结束了。每一个节点上的权值就是源点0 到该节点的最短距离。

Mr. 王：现在我们要想一想，这样做和MapReduce 的区别。在Pregel 平台上程序设计的最大特点就是从图中每一个节点出发，在执行计算的机器上保持顶点和边，用网状结构传输信息。

也就是说，每一个节点，或者说保存着这些节点的每一台机器不需要知道整个图的结构，只需要执行自己本轮应该执行的操作就可以了。这样做可以说是一种“真正的”分布式思想。

而MapReduce 则不然，虽然在解决图问题时我们可以设计一轮轮MapReduce 去进行图算法中的迭代，但是每一阶段都要利用整个图的全部状态，需要整合MapReduce 链。这意味着MapReduce 只是借助了分布式计算平台，让多台机器投入到图算法的求解中来，却不能在出现多轮迭代的图计算中实现“真正的”分布式。

小可兴奋地说：我很想尝试用Pregel 去写一个图算法，在实际使用中应用Pregel 是怎么做的呢？

Mr. 王打开电脑中的一段代码，说：这就是Pregel 的C++ API。其实Trinity 平台的API 和Pregel 的都是比较类似的，可以触类旁通。

在实际使用的过程中，需要定义的就是节点这个类。我们要重载节点的几个函数，也就是前面提到的执行操作（Compute 函数，其中的msgs 就是收到的来自其他节点的信息）、发送信息（SendMessageTo 函数），当然还有一个重要的VoteToHalt，这个函数用来确定整个系统是不是停摆，比如本轮中某节点没有动作，它就投票停机，如果所有的节点都投票停机了，那么就说明整个系统已经不再变化了。对于每一个节点来说，其各项值和送出信息的数据类型都是不同的，在实际的设计过程和使用过程中，可以借助模板类来确定。

小可好奇地说：我还想看看最短路径这个程序具体是怎么写的。

Mr. 王：我这里刚好有一份最短路径的代码。

我们一起来剖析一下这段代码。和前面的框架是相符的，继承了顶点类，派生出最短路径节点类，在派生类中重载了Compute 函数，程序在执行过程中我们要做的就是遵循前面提到的思想，接收所有节点向我发送的消息，然后判断这些消息中包含的路径权值是不是比我小，如果小就更新我的节点。同时我也要向其他节点发送包含我最短路径和出度边长之和的消息。最后，如果本轮没有任何动作和改变，我要执行投票停机这个操作。

小可：如果我想部署一个Pregel 平台，需要怎么做呢？

Mr. 王：一般来说，一个Pregel 平台都需要运行master 和worker 两种进程。其中master主要完成维护worker、恢复worker 产生的错误、提供一个以网页形式表现的用户界面来控制和监督worker 进程的执行情况；而worker 是工作的主要承担者，它负责在每一轮迭代中处理自己的任务并且与其他worker 进行消息传递。至于数据的存储，一般会选用GFS 和BigTable这样的分布式文件系统，一些临时产生的、内存存不下的大量中间结果，会相应地被存储在磁

盘中。

在实际的运行过程中，往往是多个程序的副本在服务器集群中执行，然后由master 进程分配划分内容作为每一个worker 的输入。每一个worker 会存储和执行多个图中的顶点并标记它们。

在master 的命令调度下，每一个worker 执行自己的Superstep。每一个worker 循环通过已标记的顶点计算每个顶点。整个网络中没有统一的时钟来标注什么时间去进行信息传递，而是采取信息异步传输，有需要的时候自行传递即可，但所有的信息传递都要在Superstep 结束前传送完毕。系统会不断地重复以上步骤，直到没有已标记顶点或信息传输，此时我们想要的结果就已经求解出来了。在程序运行停止后，master 会命令每一个worker 保存图的部分信息。

下期精彩预告：

经过学习，我们讨论了一种很典型的图论问题——单源最短路径。在下一期中，我们将学习计算子图同构问题。更多精彩内容，敬请关注灯塔大数据，每周五不见不散呦！

内容来源：灯塔大数据 文章编辑：柯一