将图形数据库分片

Question

我想知道像Dgraph和TigerGraph这样的数据库如何进行分片以支持水平扩展，同时又不会破坏节点之间的连接，并支持许多有趣的算法。
他们声称自己是一种本地图形解决方案，因此类似Facebook或Twitter的方法在这里不适用。
我所能想到的唯一解决方案就是将图形分散在许多小型数据库中，这会导致许多节点重复以维护关系。
有什么好的想法吗？
提前感谢。

- Rawhi

Answer 1

从技术上讲，关于图形分片需要遵循两个原则。第一个是Edge-Cut，它将边缘切割成两部分（入向和出向），并将它们分别存储在不同的服务器上。与该边缘相关联的每个顶点分布在集群中的特定服务器上。分布式图形数据库Nebula Graph就采用了此方法。第二个原则是Vertex-Cut，它将顶点切割成N部分（取决于顶点具有的边数），并将它们存储在不同的服务器上。然后，与该顶点相关联的每个边都会被分配到集群中的特定服务器上。GraphX也是这样做的。

然而，图形分片本身就是一个NP问题，比SQL分片要更加困难。因此，一些供应商可能会采用不同于仅Cut-Edge或Cut-Vertex的方式进行分片。例如，你提到的子图扩散算法有些类似于Neo4j Fabric。一些供应商将整个图形结构（不包括属性）放入单个主机内存中，以便快速获取子图。而一些供应商则采用邻接表来将图形中的节点和边分开，而不太考虑局部性。

- venegr

Answer 2

这是一个关键问题，也是大型图形数据库的一个弱点。它们大多使用只读副本或在网络中跨度太大时存在问题。

但你问的是Dgraph，它实际上完全不同，不会将图形分解为不同服务器上的不相连或甚至重叠的子图。相反，它将整个谓词存储在单独的服务器上，这允许给定查询在少量的网络跳数内执行。

在这里查看“使用vim的sf开发人员”示例：https://dgraph.io/blog/post/db-sharding/。

- Damon