Dud*_*lul 5 database-design graph distributed-computing nosql redis
我们想对加权有向图进行分片,
用户可以动态添加节点和边,首先DB/Graph为空.
我们将节点和边缘保存在一个键/值数据库(可能是Redis)中:对于每个节点,我们将nodeId作为键,并将引用节点的键的一组排序,sortedSet中每个nodeId的得分是边缘.
(请参阅此处的问题:Redis:实施加权有向图)
我们没有平衡约束,图中最常见的操作是Dijkstra,我们希望最小化I/O(在我们的例子中是网络)
可能的解决方案:每个数据库服务器都包含其他具有IP的服务器列表:
key:server1,value:.... 250.1
key:server2,value:.... 250.2
key:server3,value:.... 250.3
每个nodeId都是serverX.originalNodeId
什么算法决定哪个节点在哪里？我们应该支持重新定位节点吗？
我猜这个天真的方法是,将节点A添加到serverX,其中argmax(服务器X中具有节点A的边缘的节点数),只要serverX没有被完全占用.
由于处理发生在客户端，因此这种图形数据不太难分片 - 每一步所需的只是单个排序集，因此从哪个节点加载该集并不重要。最后一步是获取与节点相关的实际数据 - 如果您只有一个节点，那么这将是一个简单的 MGET，并且很容易拆分到多个节点。
要确定密钥将存储在哪个节点上，您应该使用哈希而不是尝试手动跟踪它们。我使用一个表将一系列哈希值映射到特定节点。它存储在 Redis 中以实现长期持久性，但实际上是客户端的一部分。要访问特定密钥，您只需获取该密钥的哈希值，在表中查找它，然后连接到该节点。使用具有数千个槽的表可以轻松地将数据移动到另一个节点 - 更新表并且对特定槽的请求将发送到不同的节点。这与 Redis 集群中使用的方法非常相似，但不完全相同。
也就是说，我设置分片的原因不是图形数据。仅包含 ID 的小型排序集不会占用太多内存 - 您应该能够在单个节点上处理 1 亿条边，而不会遇到太多麻烦。