乐趣区

关于nebula:解析-Nebula-Graph-子图设计及实践

jiezi

本文首发于 Nebula Graph 公众号 NebulaGraphCommunity，Follow 看大厂图数据库技术实际。

前言

在先前的 Query Engine 源码解析中，咱们介绍了 2.0 中 Query Engine 和 1.0 的次要变动和大体的构造：

大家能够大略理解到用户通过客户端发送一条查问语句，Query Engine 是如何解析语句、把语句构建为形象语法树，在形象语法树进行校验、生成执行打算的过程。本文会通过 2.0 中新增的子图算法模块持续解说 Query Engine 背地所做的内容，并着重介绍执行打算生成的过程，以便增强你对源码更好地了解。

子图的定义

子图是指节点汇合和边汇合别离是某一图的节点集的子集和边集的子集的图。直观地了解，就是从用户指定的终点开始登程沿着指定的边一步步拓展，直到达到用户所设定的步数为止，而后返回在拓展过程中遇到的所有点集和边集。

子图的语法​

GET SUBGRAPH [<step_count> STEPS] FROM {<vid>, <vid>...} [IN <edge_type>, <edge_type>...]
[OUT <edge_type>, <edge_type>...] [BOTH <edge_type>, <edge_type>...]
  • step_count：指定从起始点开始的跳数，返回从 0 到 step_count 跳的子图。必须是非负整数。默认值为 1
  • vid：指定起始点 ID
  • edge_type：指定边类型。能够用 IN、OUT 和 BOTH 来指定起始点上该边类型的方向。默认为 BOTH

子图的实现

当 Query Engine 接管到 GET SUBGRAPH 命令后，Parser 模块（由 flex 和 bison 实现）会依据曾经写好的规定（parser.yy 中 get_subgraph_sentence 规定）把所须要的内容从查问语句中提取进去，生成一个形象语法树，如下所示：

而后进入 Validate 阶段，此时对生成的形象语法树进行校验，目标是为了验证用户的输出是否非法（参考 Query Engine 的文章），当校验通过后，会把语法树中的内容提取进去，生成一个执行打算。
​
那么这个执行打算是如何生成的呢？对同一性能不同的数据库厂商可能会生成不同的执行打算，然而原理都是雷同的。那就是要看本身的算子有哪些和查问层和存储层是如何进行交互的。因为咱们的每一条查问语句到最初都是要从存储层取数据的。在 Nebula Graph 中 Query Engine 和存储层是通过 RPC 形式（fbthrift）进行交互的（接口定义在 common 仓中的 interface 目录下）。这里有两个十分要害的接口 getNeighbors 和 getProps 须要理解一下。

getNeighbors 其中 fbthrift 的定义格局如下：

struct GetNeighborsRequest {    
    1: common.GraphSpaceID                      space_id,
    2: list<binary>                             column_names,
    3: map<common.PartitionID, list<common.Row>>
        (cpp.template = "std::unordered_map")   parts,
    4: TraverseSpec                             traverse_spec
}

该构造中每个变量的具体定义能够参考 https://github.com/vesoft-inc/nebula-common/blob/master/src/common/interface/storage.thrift，外面有具体的正文。
​

其次要性能就是 Query Engine 依据定义好的构造传入起始点和要拓展的边类型信息，而后存储层会找到起始点，而后把该点的属性和以该点的出边的边属性找进去组装成一个表格返回给 Query Engine，其中返回的表格的格局参考 https://github.com/vesoft-inc/nebula-common/blob/master/src/common/interface/storage.thrift 中 GetNeighborsResponse 的定义，而后在 Query Engine 中咱们就能够通过这个表格提取到咱们想要的内容。
​
例如在 basketba l l 数据集中，当起始点为 Tim Duncan、Manu Ginobili 沿着 like 边双向拓展。想要取得 $^.[player.name](http://player.name/)、like._dst、$$.[player.name](http://player.name/) 和 like.likeness 这四个属性。其返回的数据大抵如下所示：

表格 1

因为是双向拓展第四列的 + like 代表出边，第五列的 - like 代表入边。

在 Nebula Graph 的存储层中边是和起始点在一起寄存的，所以通过 getNeighbor 接口就能够取得终点和出边的所有属性信息，然而如果想要在拓展过程中拿到目标点的属性信息则须要应用 getProps 接口，当然如果我只想通过 fetch 语句拿到某个点或者边的属性也须要调用这个接口。你能够自行理解 https://github.com/vesoft-inc/nebula-common/blob/master/src/common/interface/storage.thrift 下 getPropRequest 的定义，加深了解。

执行打算

有了下面的接口定义咱们就能够开始执行打算了，首先须要的算子有 start、getNeighbor、subgraph、loop、datacollect。

  • start 算子：相当于执行打算中叶子节点，不做任何事件。目标是通知调度器，之后没有能够依赖的算子，或者能够了解为递归算法中的终止条件。
  • loop 算子：相当于 C 语言中的 while 语法，该算子有三个成员 depend、condition 和 loopBody，depend 在多语句和 PIPE 中会应用以后暂且不表，condition 相当于终止条件。loopBody 相当于 while 中的循环体。
  • subgraph 算子：负责把 getNeighbor 算子后果中的 _dst（目标点）属性提出来而后过滤掉曾经拜访过的目标点（防止反复从存储层拿数据），而后把它们当作 getNeighbor 算子下一次拓展时的输出。
  • datacollect 算子：负责在最初把拓展过程中取得的点和边属性收集起来组装为 vertex 和 edge 类型。

其中各个算子的详细信息，可参考源码 https://github.com/vesoft-inc/nebula-graph/tree/master/src/executor。
上面通过图 1 举例，咱们是如何构建子图的


图 1

拓展一步的状况

当从 A 点开始沿着 like 边只获取一步的所有点和边的信息，则很容易。只须要 getNeighbor 和 dataCollect 这两个算子就能够了。执行打算如下图所示：

拓展多步的状况

一步场景其实是多步的场景的非凡状况。所以能够将一步的场景合入到多步场景中。当从 A 点开始，沿着 like 边拓展三步的话，依据现有的算子，能够在 getNeighbor 拓展后把目标点提取进去，而后将这些目标点当作终点从新调用 getNeighbor 接口，这个循环两次就能够了（loop 算子的终止条件设置为以后步数），因而执行打算如下图所示：

输出和输入

个别状况下，每个算子的输出就是所依赖算子的输入，这时候依据执行打算的依赖关系就能够直观地确定每个算子的输出和输入。然而在某些状况下，比方：子图，在多步场景中每一次 getNeighbor 算子的输出都应该是上一次拓展边的目标点，也就是 subgraph 算子的输入，因而 subgraph 算子的输入应该就是 getNeighbor 算子的输出。这时就和上图的执行打算依赖不统一，这时就须要自行设置每个算子的输出和输入。在 Query Engine 2.0 中咱们曾经介绍了每个算子的输出和输入是寄存在哈希表中的，其中 value 是 vector 类型。如下表 ResultMap 所示：

  • 起始点寄存在 ResultMap[“StartVid”] 中
  • getNeighbor 算子的输出是 ResultMap[“StartVid”], 输入寄存在 ResultMap[“GN_1”]
  • subgraph 算子的输出是 ResultMap[“GN_1”], 输入寄存在 ResultMap[“StartVid”]
  • loop 算子不产生数据，当作逻辑循环应用，因而不须要设置输入输出
  • dataCollect 算子的输出是 ResultMap[“GN_1”], 输入寄存在 ResultMap[“DATACOLLECT_2”]

这时 getNeighbor 算子会把每一次的后果放在 ResultMap[“GN_1”] 中的 vector 中的开端，而后 subgraph 算子从 ResultMap[“GN_1”] 中的 vector 中的开端取值，通过计算再把下一次要拓展的起始点寄存在 ResultMap[“StartVid”] 中。

当拓展第一步后，ResultMap 的后果如下：
​

为了不便显示，GetNeighbor 的后果只写了 _dst 的属性，实际上会带上边上所有的属性和起始点的所有属性，相似于表格 1。

subgraph 算子接管 ”GN_1″ 的输出，提取 _dst 属性，而后将后果放入 ”StartVid” 中。当拓展第二步后，ResultMap 的后果如下：

当拓展第三步后，ResultMap 的后果如下：

最初 dataCollect 算子从 ResultMap[“GN_1”] 中取出拓展过程中遇到的所有点集和边集，组装成最终的后果返回给用户。

实例

上面执行一个子图的实例看看在 Nebula Graph 中执行打算的具体构造，关上 nebula-console, 切换 space 到 basketball，输出 EXPLAIN format="dot" GET SUBGRAPH 2 STEPS FROM 'Tim Duncan' IN like, serve，这时候 nebula-console 会生成 dot 格局的数据，而后关上 Graphviz Online 这个网站，将生成的 dot 数据粘贴下来，就能够看到如下构造：

其中 Start_0 算子是 loop 算子中 depend 的依赖，因为没有多语句或 PIPE 语句，因而不做任何解决。
​
以上为本次子图的解说，如果你在应用子图或者其余 Nebula 过程中遇到问题，欢送来论坛和咱们交换：https://discuss.nebula-graph.com.cn/

想要和其余大厂交换图数据库技术吗？NUC 2021 大会等你来交换：NUC 2021 报名传送门

退出移动版