Graph服务

Graph服务

Graph服务主要负责处理查询请求，包括解析查询语句、校验语句、生成执行计划以及按照执行计划执行四个大步骤，本文将基于这些步骤介绍Graph服务。

Graph服务架构

查询请求发送到Graph服务后，会由如下模块依次处理：

Parser：词法语法解析模块。
Validator：语义分析模块。
Planner：执行计划与优化器模块。
Executor：执行引擎模块。

Parser

Parser模块收到请求后，通过Flex（词法分析工具）和Bison（语法分析工具）生成的词法语法解析器，将语句转换为抽象语法树（AST），在语法解析阶段会拦截不符合语法规则的语句。

例如GO FROM "Tim" OVER like WHERE like.likeness > 8.0 YIELD like._dst语句转换的AST如下。

Validator

Validator模块对生成的AST进行语义校验，主要包括：

校验元数据信息

校验语句中的元数据信息是否正确。

例如解析OVER、WHERE和YIELD语句时，会查找Schema校验边类型、标签的信息是否存在，或者插入数据时校验插入的数据类型和Schema中的是否一致。
校验上下文引用信息

校验引用的变量是否存在或者引用的属性是否属于变量。

例如语句$var = GO FROM "Tim" OVER like YIELD like._dst AS ID; GO FROM $var.ID OVER serve YIELD serve._dst，Validator模块首先会检查变量var是否定义，其次再检查属性ID是否属于变量var。
校验类型推断

推断表达式的结果类型，并根据子句校验类型是否正确。

例如WHERE子句要求结果是bool、null或者empty。
校验*代表的信息

查询语句中包含*时，校验子句时需要将*涉及的Schema都进行校验。

例如语句GO FROM "Tim" OVER * YIELD like._dst, like.likeness, serve._dst，校验OVER子句时需要校验所有的边类型，如果边类型包含like和serve，该语句会展开为GO FROM "Tim" OVER like,serve YIELD like._dst, like.likeness, serve._dst。
校验输入输出

校验管道符（|）前后的一致性。

例如语句GO FROM "Tim" OVER like YIELD like._dst AS ID | GO FROM $-.ID OVER serve YIELD serve._dst，Validator模块会校验$-.ID在管道符左侧是否已经定义。

校验完成后，Validator模块还会生成一个默认可执行，但是未进行优化的执行计划，存储在目录src/planner内。

Planner

如果配置文件nebula-graphd.conf中enable_optimizer设置为false，Planner模块不会优化Validator模块生成的执行计划，而是直接交给Executor模块执行。

如果配置文件nebula-graphd.conf中enable_optimizer设置为true，Planner模块会对Validator模块生成的执行计划进行优化。如下图所示。

优化前

如上图右侧未优化的执行计划，每个节点依赖另一个节点，例如根节点Project依赖Filter、Filter依赖GetNeighbor，最终找到叶子节点Start，才能开始执行（并非真正执行）。

在这个过程中，每个节点会有对应的输入变量和输出变量，这些变量存储在一个哈希表中。由于执行计划不是真正执行，所以哈希表中每个key的value值都为空（除了Start节点，起始数据会存储在该节点的输入变量中）。哈希表定义在仓库nebula-graph内的src/context/ExecutionContext.cpp中。

例如哈希表的名称为ResultMap，在建立Filter这个节点时，定义该节点从ResultMap["GN1"]中读取数据，然后将结果存储在ResultMap["Filter2"]中，依次类推，将每个节点的输入输出都确定好。
优化过程

Planner模块目前的优化方式是RBO（rule-based optimization），即预定义优化规则，然后对Validator模块生成的默认执行计划进行优化。新的优化规则CBO（cost-based optimization）正在开发中。优化代码存储在仓库nebula-graph的目录src/optimizer/内。

RBO是一个自底向上的探索过程，即对于每个规则而言，都会由执行计划的根节点（示例是Project）开始，一步步向下探索到最底层的节点，在过程中查看是否可以匹配规则。

如上图所示，探索到节点Filter时，发现依赖的节点是GetNeighbor，匹配预先定义的规则，就会将Filter融入到GetNeighbor中，然后移除节点Filter，继续匹配下一个规则。在执行阶段，当算子GetNeighbor调用Storage服务的接口获取一个点的邻边时，Storage服务内部会直接将不符合条件的边过滤掉，这样可以极大地减少传输的数据量，该优化称为过滤下推。

Executor

Executor模块包含调度器（Scheduler）和执行器（Executor），通过调度器调度执行计划，让执行器根据执行计划生成对应的执行算子，从叶子节点开始执行，直到根节点结束。如下图所示。

每一个执行计划节点都一一对应一个执行算子，节点的输入输出在优化执行计划时已经确定，每个算子只需要拿到输入变量中的值进行计算，最后将计算结果放入对应的输出变量中即可，所以只需要从节点Start一步步执行，最后一个算子的输出变量会作为最终结果返回给客户端。

代码结构

Nebula Graph的代码层次结构如下：

|--src
   |--context    //校验期和执行期上下文
   |--daemons
   |--executor   //执行算子
   |--mock
   |--optimizer  //优化规则
   |--parser     //词法语法分析
   |--planner    //执行计划结构
   |--scheduler  //调度器
   |--service
   |--util       //基础组件
   |--validator  //语句校验
   |--visitor