在 ArangoDb 中缩放图遍历

Question

我有一个树状结构，其实就是一个有向无环图。下面显示了一个小版本。

在任何父级，我想对子树的一些属性求和。今天，我在 AQL 中使用 TRAVERSAL 和基于起始节点的 COLLECT 执行此操作：

for c in traversal(nodes,nodeTree,ch,'inbound',{uniqueness:{vertices:'global'}})
    collect child = ch._id into group

然后我可以在组上使用聚合。（对于 ArangoDB 2.8，我相信现在可以直接在 collect 语句中完成。）唯一性选项解决了重复问题。

缩放

当树（图）增长到相当大（10-20k 个节点）时，这个规模将如何？我需要它很快，因为用户将等待响应（不是很长的运行工作）。

我正在考虑在节点中缓存值并使用 dirty 标志。然后在节点 1 中可以只对 2 和 3 求和，如果它们都是 clean。问题是 5 包含在 2 和 3 的总和中。

我该如何解决这个问题？或者这不是问题 - 遍历真的那么快吗？

到目前为止，我已经想出了让每个节点都包含其子树重复列表的想法，在 1 的情况下，这意味着信息“5 被包含了两次”。这可以用来从 1 的总数中减去它。但是我如何找到这些信息呢？我考虑过找到所有具有 >1 个父节点的节点，然后向上遍历（这很快）然后 以某种方式 计算此信息。

Answer 1

遍历的运行时间受进程中实际接触的顶点和边的数量限制。因此遍历的运行时间取决于路径的深度和分支因子（预计有多少个具有多个父节点的顶点）。

你所描述的构造的问题是遍历将选择从 1 到 5 的一条路径（比如左边的那条）并对所有值求和，最终 returns to 1 选择正确的路径。现在它再次到达 5 但这次搜索深度低于上次看到 5 时，因此它实际上必须再次遍历 5 上的子树，因为它现在可能获得更大的距离在这个路径中（它不知道这个子树上的所有顶点已经可以在更短的距离内到达）。此路径上的顶点不会再次调用访问者，但仍会遍历和跟踪，这会花费时间。

我尝试优化遍历以验证缩放。首先我注册了一个新的优化访客：

require("@arangodb/aql/functions").register("test::counter", "function (config, result, vertex) {result[0] = result[0] || {value: 0}; result[0].value += vertex.value}");

此访问者将顶点的值相加并直接 returns 它们，因此我可以摆脱 COLLECT 语句。我可以用我的 AQL:

FOR x IN TRAVERSAL(TestVertices, TestEdges, 'TestVertices/0', 'outbound', {uniqueness:{vertices:'global'}, visitor: 'test::counter', maxDepth: 5012})
  RETURN x.value

这里注意：我在选项中给了一个maxDepth来实际进行高深度搜索，默认是256。

我的测试树基本上是一个 20.000 顶点链，其中每三个顶点都有一个附加边到链中后面的随机顶点（模拟你描述的多父问题）

通过这次遍历，我设法从 ~5 secs 中的根搜索了 5012 的深度。使用更高的深度它呈指数增长。

我假设你的图有更少的多父级，所以我希望你的图运行时间更少。

如果您希望读取次数多于写入次数，您还可以考虑计算每次写入的总和。这会减慢写入速度，但会立即进行所有读取。

例如，您可以在更新值时另外使用以下 AQL：

LET i = (FOR x IN 1..5012 INBOUND @start TestEdges
           RETURN DISTINCT x) 
  FOR x IN i UPDATE x WITH {sum: x.sum + @add} IN TestVertices

使用绑定参数 @add 表示要添加的值，@start 表示要更新的顶点。使用这种技术，您的读取查询很简单：

FOR x IN TestVertices FILTER x._id == @start 
  RETURN x.sum

希望这对您有所帮助。

在 ArangoDb 中缩放图遍历

Scaling graph traversals in ArangoDb

graph

graph-databases

arangodb