在键值数据库上划分加权有向图

Question

在键值数据库上划分加权有向图

database-designgraphnosqlredisdistributed-computing

5

我们希望对一个加权有向图进行分片。用户可以动态添加节点和边，最初的数据库/图为空。我们将节点和边存储在键值数据库中（可能是Redis）：对于每个节点，我们将nodeId作为键，并使用排序集合存储引用节点的键，每个nodeId在排序集合中的得分是边的权重。（有关此问题，请参见Redis：实现加权有向图）。我们没有平衡约束，图上最常见的操作是Dijkstra算法，我们希望将I/O（在我们的情况下是网络）最小化。可能的解决方案是：每个DB服务器包含其他服务器的IP列表：key：server1，value：....250.1；key：server2，value：....250.2；key：server3，value：....250.3。每个nodeId都将是serverX.originalNodeId。哪种算法决定节点放在何处？我们应该支持重新定位节点吗？

我猜天真的方法是将节点A添加到serverX中，其中argmax（在server X中与节点A有边缘的节点数），只要serverX没有完全占满。

- DuduAlul

“Shard”? 我可能老了。这是什么意思？ - Ira Baxter

http://en.wikipedia.org/wiki/Shard_(database_architecture) - DuduAlul

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tom Clarkson · Accepted Answer

由于处理过程在客户端进行，因此这种图形数据的分片并不太困难 - 每个步骤所需的仅是一个单一的排序集，因此无论从哪个节点加载该集合都无关紧要。将实际数据与节点配对是最后一步 - 如果只有一个节点，则会是一个简单的MGET，而且很容易拆分到几个节点上。

为了确定键将存储在哪个节点上，您应该使用哈希而不是手动跟踪它们。我使用一个表将哈希范围映射到特定节点。它在 Redis 中用于长期持久性，但实际上是客户端的一部分。要访问特定键，您只需获取键的哈希值，在表中查找并连接到该节点。使用数千个插槽的表可轻松将数据移动到另一个节点 - 更新表并请求特定插槽，则会转到另一个节点。虽然不完全相同，但这与 Redis 集群中使用的方法非常相似。

话虽如此，我设置分片的原因并不是图形数据。仅包含 ID 的小型排序集不会占用太多内存 - 您应该能够处理一亿个边缘而不会有太大问题。