分布式图形搜索

Question

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

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

Answer 1

有很多方法可以做到这一点。这是一种利用 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 存储之间的查找都是分布式的，并且映射/归约中的所有工作也是分布式的。 每代的同步是最小的。 因此，这将以分布式方式完成大部分工作。

以及性能说明。 一般来说，从单台机器上的简单实现到分布式机器的成本和资源增加一个数量级，然后是巨大的可扩展性。 从简单的实现到优化的实现往往性能提高了 1-2 个数量级，但仅限于一台机器可以做的事情。 仔细选择要采取的方法。 只有在您确实需要时才分发。

Answer 2

尝试 GraphScope 中内置的 BFS 算法，它完全适合您的需求。

GraphScope是一个分布式图形平台，具有许多现成的算法。

回到您的问题，可以通过3个步骤完成：

1. 启动 GraphScope 集群
2. 加载图形
3. 在其上运行 BFS 并检索结果。

这是代码

import graphscope
sess = graphscope.session(num_workers=4)
graph = sess.g()
graph = graph.add_edges('/path/to/dataset')
result = graphscope.bfs(graph, src=0)
print(result.to_dataframe(selector={'id': 'v.id', 'distance': 'r'})
sess.close()

您可以参考本文来了解如何部署 graphscope，并参考本文来学习如何通过 helm 进行部署。