时间戳

首页 > 解决方案 > 分布式图搜索

algorithm - 分布式图搜索

问题描述

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

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

标签： algorithmgraph-theorydistributed-computingbreadth-first-searchdistributed-system

解决方案

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

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

  1. 您的图形数据库
  2. 分布式键/值存储（例如 Cassandra）
  3. 映射/减少工作者（例如 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 个数量级，但您仅限于一台机器可以做的事情。仔细选择采取哪种方法。仅在您确实需要时才分发。

推荐阅读