algorithm - 分布式图搜索

Question

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

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

Answer 1

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

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

1. 您的图形数据库
2. 分布式键/值存储(例如 Cassandra)
3. map/reduce workers(例如 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

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

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