图数据库NebulaGraph_nebula图数据库

一、图数据库选型

1.1 什么是知识图谱

知识图谱本质上是语义网络，即一个由节点和边组成的有向图结构知识库。其中，图的节点代表现实世界中存在的"实体"，图的边则代表实体之间的"关系"。知识图谱可以有效、直观地表达实体之间的关系。

1.2 关系型数据库 or 图数据库

1.3 图数据库的选择

选型主要考虑以下 5 点：(A) 项目开源，暂不考虑需付费的图数据库；(B) 分布式架构设计，具备良好的可扩展性；(C) 毫秒级的多跳查询延迟；(D) 支持千亿量级点边存储；(E) 具备批量从数仓导入数据的能力。

第一类：Neo4j、ArangoDB、Virtuoso、TigerGraph、RedisGraph。 此类图数据库只有单机版本开源可用，性能优秀，但不能应对分布式场景中数据的规模增长，即不满足选型要求（B）、（D）。

第二类：JanusGraph、HugeGraph。 此类图数据库在现有存储系统之上新增了通用的图语义解释层，图语义层提供了图遍历的能力，但是受到存储层或者架构限制，不支持完整的计算下推，多跳遍历的性能较差，很难满足 OLTP 场景下对低延时的要求，即不满足选型要求（C）。

第三类：DGraph、NebulaGraph。 此类图数据库根据图数据的特点对数据存储模型、点边分布、执行引擎进行了全新设计，对图的多跳遍历进行了深度优化，基本满足我们的选型要求。

1.4 NebulaGraph 的适用场景

特点：开源、高性能、易扩展、易开发、高可靠访问控制、生态多样化等

欺诈检测：金融机构必须仔细研究大量的交易信息，才能检测出潜在的金融欺诈行为，并了解某个欺诈行为和设备的内在关联。这种场景可以通过图来建模，然后借助 NebulaGraph，可以很容易地检测出诈骗团伙或其他复杂诈骗行为。

实时推荐：NebulaGraph 能够及时处理访问者产生的实时信息，并且精准推送文章、视频、产品和服务。

知识图谱：自然语言可以转化为知识图谱，存储在 NebulaGraph 中。用自然语言组织的问题可以通过智能问答系统中的语义解析器进行解析并重新组织，然后从知识图谱中检索出问题的可能答案，提供给提问人。

社交网络：人际关系信息是典型的图数据，NebulaGraph 可以轻松处理数十亿人和数万亿人际关系的社交网络信息，并在海量并发的情况下，提供快速的好友推荐和工作岗位查询。

二、概念

2.1 数据模型

图空间（Space）

图空间用于隔离不同团队或者项目的数据。不同图空间的数据是相互隔离的，可以指定不同的存储副本数、权限、分片等。

点（Vertex）

点用来保存实体对象，特点如下：

点是用点标识符（VID）标识的。VID在同一图空间中唯一。VID 是一个 int64，或者 fixed_string(N)。

点可以有 0 到多个 Tag。

2.x 及以下版本中的点必须包含至少一个 Tag。

边（Edge）

边是用来连接点的，表示两个点之间的关系或行为，特点如下：

两点之间可以有多条边。

边是有方向的，不存在无向边。

四元组 <起点 VID、Edge type、边排序值 (rank)、终点 VID> 用于唯一标识一条边。边没有 EID。

一条边有且仅有一个 Edge type。

一条边有且仅有一个 Rank，类型为 int64，默认值为 0。

Rank 可以用来区分 Edge type、起始点、目的点都相同的边。该值完全由用户自己指定。 读取时必须自行取得全部的 Rank 值后排序过滤和拼接。 不支持诸如next(), pre(), head(), tail(), max(), min(), lessThan(), moreThan()等函数功能，也不能通过创建索引加速访问或者条件过滤。

标签（Tag）

Tag 由一组事先预定义的属性构成。

边类型（Edge type）

Edge type 由一组事先预定义的属性构成。

属性（Property）

属性是指以键值对（Key-value pair）形式表示的信息。

Tag 和 Edge type 的作用，类似于关系型数据库中“点表”和“边表”的表结构。

2.2 路径

分为三种：walk、trail、path。

walk： 路径由有限或无限的边序列构成。遍历时点和边可以重复。

trail：路径由有限的边序列构成。遍历时只有点可以重复，边不可以重复。

cycle 是封闭的路径，遍历时边不可以重复，起点和终点重复，并且没有其他点重复。

circuit 也是封闭的路径，遍历时边不可以重复，除起点和终点重复外，可能存在其他点重复。

path：路径由有限的边序列构成。遍历时点和边都不可以重复。

2.3 点VID

在一个图空间中，一个点由点的 ID 唯一标识，即 VID 或 Vertex ID。

2.3.1 特点:

VID 数据类型只可以为定长字符串FIXED_STRING(<N>)或INT64。一个图空间只能选用其中一种 VID 类型。

VID 在一个图空间中必须唯一，其作用类似于关系型数据库中的主键（索引+唯一约束）。但不同图空间中的 VID 是完全独立无关的。

点 VID 的生成方式必须由用户自行指定，系统不提供自增 ID 或者 UUID。

VID 相同的点，会被认为是同一个点。例如：

VID 相当于一个实体的唯一标号，例如一个人的身份证号。Tag 相当于实体所拥有的类型，例如"滴滴司机"和"老板"。不同的 Tag 又相应定义了两组不同的属性，例如"驾照号、驾龄、接单量、接单小号"和"工号、薪水、债务额度、商务电话"。

同时操作相同 VID 并且相同 Tag 的两条INSERT语句（均无IF NOT EXISTS参数），晚写入的INSERT会覆盖先写入的。

同时操作包含相同 VID 但是两个不同TAG A和TAG B的两条INSERT语句，对TAG A的操作不会影响TAG B。

VID 通常会被（LSM-tree 方式）索引并缓存在内存中，因此直接访问 VID 的性能最高。

2.3.2 使用建议:

1.x 只支持 VID 类型为INT64，从 2.x 开始支持INT64和FIXED_STRING(<N>)。在CREATE SPACE中通过参数vid_type可以指定 VID 类型。

可以使用id()函数，指定或引用该点的 VID。

可以使用LOOKUP或者MATCH语句，来通过属性索引查找对应的 VID。

性能上，直接通过 VID 找到点的语句性能最高，例如DELETE xxx WHERE id(xxx) == "player100"，或者GO FROM "player100"等语句。通过属性先查找 VID，再进行图操作的性能会变差，例如LOOKUP | GO FROM $-.ids等语句，相比前者多了一次内存或硬盘的随机读（LOOKUP）以及一次序列化（|）。

2.3.3 生成建议:

（最优）通过有唯一性的主键或者属性来直接作为 VID；属性访问依赖于 VID;

通过有唯一性的属性组合来生成 VID，属性访问依赖于属性索引。

通过 snowflake 等算法生成 VID，属性访问依赖于属性索引。

如果个别记录的主键特别长，但绝大多数记录的主键都很短的情况，不要将FIXED_STRING(<N>)的N设置成超大，这会浪费大量内存和硬盘，也会降低性能。此时可通过 BASE64，MD5，hash 编码加拼接的方式来生成。

如果用 hash 方式生成 int64 VID：在有 10 亿个点的情况下，发生 hash 冲突的概率大约是 1/10。边的数量与碰撞的概率无关。

三、架构

NebulaGraph 由三种服务构成：Meta 服务、Graph 服务和 Storage 服务，是一种存储与计算分离的架构。

1 Meta服务

Meta 服务： nebula-metad 进程基于 Raft 协议构成了集群，其中一个进程是 leader，其他进程都是 follower。

管理用户账号：Meta 服务中存储了用户的账号和权限信息，当客户端通过账号发送请求给 Meta 服务，Meta 服务会检查账号信息，以及该账号是否有对应的请求权限。

管理分片：Meta 服务负责存储和管理分片的位置信息，并且保证分片的负载均衡。

管理图空间：NebulaGraph 支持多个图空间，不同图空间内的数据是安全隔离的。Meta 服务存储所有图空间的元数据（非完整数据），并跟踪数据的变更，例如增加或删除图空间。

管理 Schema 信息：NebulaGraph 是强类型图数据库，它的 Schema 包括 Tag、Edge type、Tag 属性和 Edge type 属性。Meta 服务中存储了 Schema 信息，同时还负责 Schema 的添加、修改和删除，并记录它们的版本。

管理 TTL 信息：Meta 服务存储 TTL（Time To Live）定义信息，可以用于设置数据生命周期。数据过期后，会由 Storage 服务进行处理。

管理作业：Meta 服务中的作业管理模块负责作业的创建、排队、查询和删除。

2 Graph服务

Graph 服务：服务是由 nebula-graphd 进程提供，负责处理查询请求，包括解析查询语句、校验语句、生成执行计划以及按照执行计划执行四个大步骤。

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

例如：GO FROM "Tim" OVER like WHERE properties(edge).likeness > 8.0 YIELD dst(edge)语句转换的 AST 如下。

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

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

例如解析 OVER、WHERE和YIELD 语句时，会查找 Schema 校验 Edge type、Tag 的信息是否存在，或者插入数据时校验插入的数据类型和 Schema 中的是否一致。

校验上下文引用信息：校验引用的变量是否存在或者引用的属性是否属于变量。

例如语句$var = GO FROM "Tim" OVER like YIELD dst(edge) AS ID; GO FROM $var.ID OVER serve YIELD dst(edge)，Validator 模块首先会检查变量 var 是否定义，其次再检查属性 ID 是否属于变量 var。

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

例如 WHERE 子句要求结果是 bool、null 或者 empty。

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

例如语句GO FROM "Tim" OVER * YIELD dst(edge), properties(edge).likeness, dst(edge)，校验OVER子句时需要校验所有的 Edge type，如果 Edge type 包含 like和serve，该语句会展开为GO FROM "Tim" OVER like,serve YIELD dst(edge), properties(edge).likeness, dst(edge)。

校验输入输出：校验管道符（|）前后的一致性。

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

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

Planner：执行计划与优化器模块。

配置文件 nebula-graphd.conf 中 enable_optimizer 设置为 false，Planner 模块不会优化 Validator 模块生成的执行计划，而是直接交给 Executor 模块执行。如果设置为 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 一步步执行，最后一个算子的输出变量会作为最终结果返回给客户端。

3 Storage服务

Storage 服务：服务是由 nebula-storaged 进程提供，基于 Raft 协议的集群，整个服务架构可以分为三层，从上到下依次为：

Storage interface 层

Storage 服务的最上层，定义了一系列和图相关的 API。API 请求会在这一层被翻译成一组针对分片的 KV 操作，例如：

getNeighbors：查询一批点的出边或者入边，返回边以及对应的属性，并且支持条件过滤。

insert vertex/edge：插入一条点或者边及其属性。

getProps：获取一个点或者一条边的属性。

正是这一层的存在，使得 Storage 服务变成了真正的图存储，否则 Storage 服务只是一个 KV 存储服务。

Consensus 层

Storage 服务的中间层，实现了 Multi Group Raft，保证强一致性和高可用性。

Store Engine 层

Storage 服务的最底层，是一个单机版本地存储引擎，提供对本地数据的get、put、scan等操作。相关接口存储在KVStore.h和KVEngine.h文件，用户可以根据业务需求定制开发相关的本地存储插件。

图空间

 # 创建指定分片数量、副本数量和 VID 类型，并添加描述。
 CREATE SPACE IF NOT EXISTS my_space (partition_num=15, replica_factor=1, vid_type=FIXED_STRING(30)) comment="测试图空间";
 # 克隆图空间。
 CREATE SPACE IF NOT EXISTS my_space_1 as my_space;
 # 列出所有图空间
 SHOW SPACES;
 # 使用图空间
 USE my_space;
 # 描述
 DESC SPACE my_space;
 # 清空图空间中的点和边，但不会删除图空间本身以及其中的 Schema 信息。
 CLEAR SPACE my_space;
 # 删除
 DROP SPACE

检查分片情况：

 # 检查分片情况
 SHOW HOSTS;
 # 如果 Leader distribution 分布不均，需要重新分配
 BALANCE LEADER;

TAG 和 Edge TYPE

 # 创建标签 Tag:player和team
 CREATE TAG team(name string);
 CREATE TAG player(name string, age int);
 # 创建边类型
 CREATE EDGE follow(degree int);
 CREATE EDGE serve(start_year int, end_year int);

索引

 # 为 name 属性创建索引 player_index_1。
 CREATE TAG INDEX IF NOT EXISTS player_index_1 ON player(name(20));
 # 重建索引确保能对已存在数据生效。
 REBUILD TAG INDEX player_index_1;
 # 查询已创建的索引： SHOW {TAG | EDGE} INDEXES;
 SHOW TAG INDEXES;
 # 展示索引创建的 nGQL 语句
 SHOW CREATE TAG INDEX player_index_1;
 # 删除索引
 DROP TAG INDEX player_index_1;

CRUD

插入

 # 插入点数据
 INSERT VERTEX player(name, age) VALUES "player100":("Tim Duncan", 42);
 INSERT VERTEX player(name, age) VALUES "player101":("Tony Parker", 36);
 INSERT VERTEX player(name, age) VALUES "player102":("LaMarcus Aldridge", 33);
 INSERT VERTEX team(name) VALUES "team203":("Trail Blazers"), "team204":("Spurs");
 ​
 # 插入边数据
 INSERT EDGE follow(degree) VALUES "player101" -> "player100":(95);
 INSERT EDGE follow(degree) VALUES "player101" -> "player102":(90);
 INSERT EDGE follow(degree) VALUES "player102" -> "player100":(75);
 INSERT EDGE serve(start_year, end_year) VALUES "player101" -> "team204":(1999, 2018),"player102" -> "team203":(2006,  2015);

查询

 # 从 VID 为player101的球员开始，沿着边follow找到连接的球员。
 GO FROM "player101" OVER follow YIELD id($$);
 # 从 VID 为player101的球员开始，沿着边follow查找年龄大于或等于 35 岁的球员，并返回他们的姓名和年龄，同时重命名对应的列。
 GO FROM "player101" OVER follow WHERE properties($$).age >= 35 \
  YIELD properties($$).name AS Teammate, properties($$).age AS Age;
 # 从 VID 为player101的球员开始，沿着边follow查找连接的球员，然后检索这些球员的球队。为了合并这两个查询请求，可以使用管道符或临时变量。
 GO FROM "player101" OVER follow YIELD dst(edge) AS id | \
  GO FROM $-.id OVER serve YIELD properties($$).name AS Team, \
  properties($^).name AS Player;
 
 # 查询 VID 为player100的球员的属性。
 FETCH PROP ON player "player100" YIELD properties(vertex);
 ​
 # 使用 LOOKUP 语句检索点的属性。
 LOOKUP ON player WHERE player.name == "Tony Parker" \
         YIELD properties(vertex).name AS name, properties(vertex).age AS age;
 # 使用 MATCH 语句检索点的属性。
 MATCH (v:player{name:"Tony Parker"}) RETURN v;

修改

 # 用UPDATE修改 VID 为player100的球员的name属性。
 UPDATE VERTEX "player100" SET player.name = "Tim";
 # 用UPDATE修改某条边的degree属性，
 UPDATE EDGE "player101" -> "player100" OF follow SET degree = 96;
 # 用UPSERT更新数据
 UPSERT VERTEX "player111" SET player.name = "David", player.age = $^.player.age + 11 \
         WHEN $^.player.name == "David West" AND $^.player.age > 20 \
         YIELD $^.player.name AS Name, $^.player.age AS Age;

删除

 # 删除点
 DELETE VERTEX "player111", "team203";
 # 删除边
 DELETE EDGE follow "player101" -> "team204";