分布式图搜索

Question

给定一个跨多个节点分区的巨大图。每个节点包含顶点集的一些分区和全局邻接信息。

给定源顶点及其所在节点的地址，在此分布式图上实现 BFS 的最佳方法是什么。该解决方案应该可靠且快速。

Answer 1

有很多种方法可以完成这项工作。这是一个简单的方法，它利用 https://en.wikipedia.org/wiki/MapReduce.

我假设您可以使用三个机器池。

您的图形数据库
分布式 key/value 存储（例如 Cassandra）
map/reduce 工人（例如 Hadoop）

然后算法进行如下：

Insert into your kv store the fact that you reached the starting vertex at `(0, Null)` where the pair is `(generation, from)`:
while not finished and last generation found new stuff:
     Do a mapreduce from your k/v store:
       map gets (vertex, (found_generation, from_vertex):
         - sends:
            if found_generation is current_generation:
                foreach new_vertex adjacent to vertex (lookup in graph db):
                    send: new_vertex: (current_generation + 1, vertex)
            else:
                send: vertex: (found_generation, from_vertex)
       reduce gets (vertex, (found1, v1), (found2, v2), ...)
           search list for sample record with minimum found
               store minimum found back in k/v store
if found target:
   recursively walk k/v store to reconstruct the path
clear k/v store of working set
return answer

关键是所有查找 to/from 图形和 k/v 存储都是分布式的，并且 map/reduce 内的所有工作也是分布式的。每一代的同步是最小的。因此，这将以分布式方式完成大部分工作。

还有性能说明。一般来说，从单机上的简单实现到分布式机器，成本和资源会增加一个数量级，随之而来的是巨大的可扩展性。从一个简单的实现到一个优化良好的实现往往会在性能上有 1-2 个数量级的改进，但你受限于一台机器可以做什么。仔细选择要采用的方法。仅在您确实需要时才分发。

分布式图搜索

Distributed Graph Search

algorithm

graph-theory

distributed-computing

breadth-first-search

distributed-system