图空间如何做物理隔离？Nebula 底层如何存储数据？数据校验怎么做？除了存储架构讲解同数据格式变更之外，本文还解答 10 多个关于 Nebula 存储的问题。…

一文带你了解 Nebula 的存储设计和思考

![data-migration](https://www-cdn.nebula-graph.com.cn/nebula-blog/Balance01.png)

在文章[《Nebula 架构剖析系列（一）图数据库的存储设计》](https://zhuanlan.zhihu.com/p/86811459)中，我们提过分布式图存储的管理由 Meta Service 来统一调度，它记录了所有 partition 的分布情况，以及当前机器的状态。当 DBA 增减机器时，只需要通过 console 输入相应的指令，Meta Service 便能够生成整个 Balance 计划并执行。而之所以没有采用完全自动 Balance 的方式，主要是为了减少数据搬迁对于线上服务的影响，Balance 的时机由用户自己控制。

在本文中我们将着重讲解在存储层如何实现数据和服务的负载平衡。

简单回顾一下，**NebulaGraph** 的服务可分为 graph，storage，meta。本文主要描述对于存储层（storage）的数据和服务的 balance。这些都是通过 Balance 命令来实现的：Balance 命令有两种，一种需要迁移数据，命令为 `BALANCE DATA` ；另一种不需要迁移数据，只改变 partition 的 raft-leader 分布（负载均衡），命令为 `BALANCE LEADER` 。

# 本文目录

- Balance 机制浅析
- 集群数据迁移
  - Step 1：准备工作
    - Step 1.1 查看现有集群状态
    - Step 1.2 创建图空间
  - Step 2 加入新实例
  - Step 3 迁移数据
  - Step 4 假如要中途停止 balance data
  - Step 5 查看数据迁移结果
  - Step 6 Balance leader
- 批量缩容
- 示例数据迁移

# Balance 机制浅析

在图数据库 NebulaGraph 中， Balance 主要用来 balance leader 和 partition，**只涉及 leader 和 partition 在机器之间转移，不会增加或者减少 leader 和 partition 的数量**。

上线新机器并启动相应的 Nebula 服务后，storage 会自动向 meta 注册。Meta 会计算出一个新的 partition 分布，然后通过 **remove partition** 和 **add partition** 逐步将数据从老机器搬迁到新的机器上。这个过程所对应的命令是 `BALANCE DATA` ，通常数据搬迁是个比较漫长的过程。

但 BALANCE DATA 仅改变了数据和副本在机器之间的均衡分布，leader（和对应的负载） 是不会改变的，因此还需要通过命令`BALANCE LEADER`来实现负载的均衡。这个过程也是通过 meta 实现的。

# 集群数据迁移

以下举例说明 `BALANCE DATA` 的使用方式。本例将从 3 个实例（进程）扩展到 8 个实例（进程）：

## Step 1：准备工作

部署一个 3 副本的集群，1个 graphd，1个 metad，3 个 storaged（具体部署方式请参考集群部署文：[https://zhuanlan.zhihu.com/p/80335605](https://zhuanlan.zhihu.com/p/80335605)），通过 `SHOW HOSTS`  命令可以看到集群的状态信息：

### Step 1.1 查看现有集群状态
按照集群部署文档部署好 3 副本集群之后，用 `SHOW HOSTS` 命令查看下现在集群情况：
```bash
nebula> SHOW HOSTS
================================================================================================
| Ip            | Port  | Status | Leader count | Leader distribution | Partition distribution |
================================================================================================
| 192.168.8.210 | 34600 | online | 0            | No valid partition  | No valid partition     |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34700 | online | 0            | No valid partition  | No valid partition     |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34500 | online | 0            | No valid partition  | No valid partition     |
------------------------------------------------------------------------------------------------
Got 3 rows (Time spent: 5886/6835 us)
```

`SHOW HOSTS` 返回结果解释：

- _**IP**_，_**Port**_ 表示当前的 storage 实例。这个集群启动了 3 个 storaged 服务，并且还没有任何数据。(192.168.8.210:34600，192.168.8.210:34700，192.168.8.210:34500)
- _**Status**_ 表示当前实例的状态，目前有 online/offline 两种。当机器下线以后（metad 在一段间隔内收不到其心跳），将把其更改为 offline。 这个时间间隔可以在启动 metad 的时候通过设置 `expired_threshold_sec` 来修改，当前默认值是 10 分钟。
- _**Leader count**_：表示当前实例 Raft leader 数目。
- _**Leader distribution**_：表示当前 leader 在每个 space 上的分布，目前尚未创建任何 space。( space 可以理解为一个独立的数据空间，类似 MySQL 的 Database）
- _**Partition distribution**_：不同 space 中 partition 的数目。

![cluster](https://www-cdn.nebula-graph.com.cn/nebula-blog/Balance02.png)

可以看到  _Leader distribution_ 和 _Partition distribution_ 暂时都没有数据。

### Step 1.2 创建图空间

创建一个名为 test 的图空间，包含 100 个 partition，每个 partition 有 3 个副本。

```shell
nebula> CREATE SPACE test (PARTITION_NUM=100, REPLICA_FACTOR=3)
```

片刻后，使用 `SHOW HOSTS` 命令显示集群的分布。

```bash
nebula> SHOW HOSTS
================================================================================================
| Ip            | Port  | Status | Leader count | Leader distribution | Partition distribution |
================================================================================================
| 192.168.8.210 | 34600 | online | 0            | test: 0             | test: 100              |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34700 | online | 52           | test: 52            | test: 100              |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34500 | online | 48           | test: 48            | test: 100              |
------------------------------------------------------------------------------------------------
```

![cluster](https://www-cdn.nebula-graph.com.cn/nebula-blog/Balance03.png)

如上，创建包含 100 个 _partitio_n 和 3 个 _replica_ 图空间之后，3 个实例的 _Leader distribution_ 和 _Partition distribution _有了对应的数值，对应的 _Partition distribution _都为 100。当然，这样的 learder 分布还不均匀。

## Step 2 加入新实例

启动 5 个新 storaged 实例进行扩容。启动完毕后，使用 `SHOW HOSTS` 命令查看新的状态：

```bash
nebula> SHOW HOSTS
================================================================================================
| Ip            | Port  | Status | Leader count | Leader distribution | Partition distribution |
================================================================================================
| 192.168.8.210 | 34600 | online | 0            | test: 0             | test: 100              |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34900 | online | 0            | No valid partition  | No valid partition     |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 35940 | online | 0            | No valid partition  | No valid partition     |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34920 | online | 0            | No valid partition  | No valid partition     |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 44920 | online | 0            | No valid partition  | No valid partition     |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34700 | online | 52           | test: 52            | test: 100              |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34500 | online | 48           | test: 48            | test: 100              |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34800 | online | 0            | No valid partition  | No valid partition     |
------------------------------------------------------------------------------------------------
```

![add-hosts-cluster](https://www-cdn.nebula-graph.com.cn/nebula-blog/Balance04.png)

上新实例之后，集群由原来 3 个实例变成了 8 个实例。上图数据库 icon 为蓝色的图示为新增的 5 个实例，此时由于仅仅加入了集群，新实例的状态为 Online，但此时 _Leader distribution_ 和 _Partition distribution _并没有数值，说明还不会参与服务。

## Step 3 迁移数据

运行 `BALANCE DATA` 命令。

```bash
nebula> BALANCE DATA
==============
| ID         |
==============
| 1570761786 |
--------------
```

如果当前集群有新机器加入，则会生成一个新的计划 ID。对于已经平衡的集群，重复运行 `BALANCE DATA` 不会有任何新操作。如果当前有正在执行的计划，那会显示当前计划的 ID。

也可通过 `BALANCE DATA $id` 查看这个 balance 的具体执行进度。

```bash
nebula> BALANCE DATA 1570761786
===============================================================================
| balanceId, spaceId:partId, src->dst                           | status      |
===============================================================================
| [1570761786, 1:1, 192.168.8.210:34600->192.168.8.210:44920]   | succeeded   |
-------------------------------------------------------------------------------
| [1570761786, 1:1, 192.168.8.210:34700->192.168.8.210:34920]   | succeeded   |
-------------------------------------------------------------------------------
| [1570761786, 1:1, 192.168.8.210:34500->192.168.8.210:34800]   | succeeded   |
-------------------------------------------------------------------------------
...//这里省略一些。以下一行为例
-------------------------------------------------------------------------------
| [1570761786, 1:88, 192.168.8.210:34700->192.168.8.210:35940]  | succeeded   |
-------------------------------------------------------------------------------
| Total:189, Succeeded:170, Failed:0, In Progress:19, Invalid:0 | 89.947090%  |
-------------------------------------------------------------------------------
Got 190 rows (Time spent: 5454/11095 us)
```

`BALANCE DATA $id` 返回结果说明：

- 第一列 balanceId，spaceId:partId，src->dst 表示一个具体的 balance task。<br />
以 `1570761786, 1:88, 192.168.8.210:34700->192.168.8.210:35940` 为例：
  - 1570761786 为 balance ID
  - 1:88，1 表示当前的 spaceId（也就是 space test 的 ID），88 表示迁移的 partitionId
  - 192.168.8.210:34700->192.168.8.210:35940，表示数据从 _192.168.8.210:34700_ 搬迁至 _192.168.8.210:35940_。而原先 _192.168.8.210:34700_ 中的数据将会在**迁移完成后再 GC 删除**
- 第二列表示当前 task 的运行状态，有 4 种状态
  - Succeeded：运行成功
  - Failed：运行失败
  - In progress：运行中
  - Invalid：无效的 task

最后对所有 task 运行状态的统计，部分 partition 尚未完成迁移。

## Step 4 假如要中途停止 balance data
`BALANCE DATA STOP` 命令用于停止已经开始执行的 balance data 计划。如果没有正在运行的 balance 计划，则会返回错误提示。如果有正在运行的 balance 计划，则会返回计划对应的 ID。

> 由于每个 balance 计划对应若干个 balance task，`BALANCE DATA STOP` 不会停止已经开始执行的 balance task，只会取消后续的 task，已经开始的 task 将继续执行直至完成。


用户可以在 `BALANCE DATA STOP` 之后输入 `BALANCE DATA $id` 来查看已经停止的 balance 计划状态。

所有已经开始执行的 task 完成后，可以再次执行 `BALANCE DATA`，重新开始 balance。如果之前停止的计划中有失败的 task，则会继续执行之前的计划，如果之前停止的计划中所有 task 都成功了，则会新建一个 balance 计划并开始执行。

## Step 5 查看数据迁移结果

大多数情况下，搬迁数据是个比较漫长的过程。但是搬迁过程不会影响已有服务。现在可以通过 `SHOW HOSTS` 查看运行后的 partition 分布。

```bash
nebula> SHOW HOSTS
================================================================================================
| Ip            | Port  | Status | Leader count | Leader distribution | Partition distribution |
================================================================================================
| 192.168.8.210 | 34600 | online | 3            | test: 3             | test: 37               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34900 | online | 0            | test: 0             | test: 38               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 35940 | online | 0            | test: 0             | test: 37               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34920 | online | 0            | test: 0             | test: 38               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 44920 | online | 0            | test: 0             | test: 38               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34700 | online | 35           | test: 35            | test: 37               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34500 | online | 24           | test: 24            | test: 37               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34800 | online | 38           | test: 38            | test: 38               |
------------------------------------------------------------------------------------------------
Got 8 rows (Time spent: 5074/6488 us)
```

![partition-distribution](https://www-cdn.nebula-graph.com.cn/nebula-blog/Balance05.png)

_Partition distribution_ 相近，partition 总数 300 不变且 partition 已均衡的分布至各个实例。

如果有运行失败的 task，可再次运行 `BALANCE DATA` 命令进行修复。如果多次运行仍无法修复，请与社区联系 [GitHub](https://github.com/vesoft-inc/nebula/issues)。

## Step 6 Balance leader

`BALANCE DATA` 仅能 balance partition，但是 leader 分布仍然不均衡，这意味着**旧实例的服务较重，而新实例的服务能力未得到充分使用**。运行 `BALANCE LEADER` 重新分布 Raft leader：

```bash
nebula> BALANCE LEADER
```

片刻后，使用 `SHOW HOSTS` 命令查看，此时 Raft leader 已均匀分布至所有的实例。

```bash
nebula> SHOW HOSTS
================================================================================================
| Ip            | Port  | Status | Leader count | Leader distribution | Partition distribution |
================================================================================================
| 192.168.8.210 | 34600 | online | 13           | test: 13            | test: 37               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34900 | online | 12           | test: 12            | test: 38               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 35940 | online | 12           | test: 12            | test: 37               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34920 | online | 12           | test: 12            | test: 38               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 44920 | online | 13           | test: 13            | test: 38               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34700 | online | 12           | test: 12            | test: 37               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34500 | online | 13           | test: 13            | test: 37               |
------------------------------------------------------------------------------------------------
| 192.168.8.210 | 34800 | online | 13           | test: 13            | test: 38               |
------------------------------------------------------------------------------------------------
Got 8 rows (Time spent: 5039/6346 us)
```

![balance-leader-result](https://www-cdn.nebula-graph.com.cn/nebula-blog/Balance06.png)

如上， `BALANCE LEADER` 成功执行后，新增的实例和原来的实例（对应上图 icon 蓝色和黑色图示）的 _Leader distribution _相近， 所有实例已均衡，此外，也可以看到 **Balance 命令只涉及 leader 和 partition 在物理机器上的转移，并没有增加或者减少 leader 和 partition。**

# 批量缩容

**NebulaGraph** 支持指定需要下线的机器进行批量缩容。语法为 `BALANCE DATA REMOVE $host_list`，例如：`BALANCE DATA REMOVE 192.168.0.1:50000,192.168.0.2:50000`，将指定移除 192.168.0.1:50000，192.168.0.2:50000 两台机器。

> 如果移除指定机器后，不满足副本数要求（例如剩余机器数小于副本数），NebulaGraph 将拒绝本次 balance 请求，并返回相关错误码。

# 示例数据迁移

上面讲了如何从 3 个实例变成 8个实例的集群，如果你对上文有疑问，记得在本文的评论区留言哈。我们现在看看上面迁移的过程，_192.168.8.210:34600_ 这个实例的状态变化。

![image](https://www-cdn.nebula-graph.com.cn/nebula-blog/Balance07.png)

说明：有颜色为红色说明对应的数值发生变化，如果数值不变，则为黑色。

# 附录

最后是 Nebula 的 GitHub 地址，欢迎大家试用，有什么问题可以向我们提 issue。GitHub 地址：[https://github.com/vesoft-inc/nebula](https://0x7.me/zhihu2github)


在本文中我们将着重讲解在存储层如何实现数据和服务的负载平衡。

NebulaGraph 图数据库设计实践 | 存储服务的负载均衡和数据迁移


![architecture](https://www-cdn.nebula-graph.com.cn/nebula-blog/Architecture0201.png)

# 摘要
上文（存储篇）说到数据库重要的两部分为存储和计算，本篇内容为你解读图数据库 Nebula 在查询引擎 Query Engine 方面的设计实践。

在 Nebula 中，Query Engine 是用来处理 Nebula 查询语言语句（nGQL）。本篇文章将带你了解 Nebula Query Engine 的架构。

![query-engine-architecture](https://www-cdn.nebula-graph.com.cn/nebula-blog/Architecture0202.png)

上图为查询引擎的架构图，如果你对 SQL 的执行引擎比较熟悉，那么对上图一定不会陌生。Nebula 的 Query Engine 架构图和现代 SQL 的执行引擎类似，只是在查询语言解析器和具体的执行计划有所区别。

# Session Manager

Nebula 权限管理采用基于角色的权限控制（Role Based Access Control）。客户端第一次连接到 Query Engine 时需作认证，当认证成功之后 Query Engine 会创建一个新 session，并将该 session ID 返回给客户端。所有的 session 统一由 Session Manger 管理。session 会记录当前 graph space 信息及对该 space 的权限。此外，session 还会记录一些会话相关的配置信息，并临时保存同一 session 内的跨多个请求的一些信息。

客户端连接结束之后 session 会关闭，或者如果长时间没通信会切为空闲状态。这个空闲时长是可以配置的。

客户端的每个请求都必须带上此 session ID，否则 Query Engine 会拒绝此请求。

Storage Engine 不管理 session，Query Engine 在访问存储引擎时，会带上 session 信息。

## Parser

![parser](https://www-cdn.nebula-graph.com.cn/nebula-blog/Architecture0203.png)

Query Engine 解析来自客户端的 nGQL 语句，分析器(parser)主要基于著名的 flex / bison 工具集。字典文件（lexicon）和语法规则（grammar）在 Nebula 源代码的 `src/parser`  目录下。设计上，nGQL 的语法非常接近 SQL，目的是降低学习成本。 图数据库目前没有统一的查询语言国际标准，一旦 ISO/IEC 的图查询语言（GQL）委员会发布 GQL 国际标准，nGQL 会尽快去实现兼容。<br />Parser 构建产出的抽象语法树（Abstrac Syntax Tree，简称 AST）会交给下一模块：Execution Planner。

## Execution Planner

![execution-planner](https://www-cdn.nebula-graph.com.cn/nebula-blog/Architecture0204.png)

执行计划器（Execution Planner）负责将抽象树 AST 解析成一系列执行动作 action（可执行计划）。action 为最小可执行单元。例如，典型的 action 可以是获取某个节点的所有邻节点，或者获得某条边的属性，或基于特定过滤条件筛选节点或边。当抽象树 AST 被转换成执行计划时，所有 ID 信息会被抽取出来以便执行计划的复用。这些 ID 信息会放置在当前请求 context 中，context 也会保存变量和中间结果。

## Optimization

![execution-optimization](https://www-cdn.nebula-graph.com.cn/nebula-blog/Architecture0205.png)

经由 Execution Planner 产生的执行计划会交给执行优化框架 Optimization，优化框架中注册有多个 Optimizer。Optimizer 会依次被调用对执行计划进行优化，这样每个 Optimizer都有机会修改（优化）执行计划。最后，优化过的执行计划可能和原始执行计划完全不一样，但是优化后的执行结果必须和原始执行计划的结果一样的。

## Execution

![execution](https://www-cdn.nebula-graph.com.cn/nebula-blog/Architecture0206.png)

Query Engine 最后一步是去执行优化后的执行计划，这步是执行框架（Execution Framework）完成的。执行层的每个执行器一次只处理一个执行计划，计划中的 action 会挨个一一执行。执行器也会一些有针对性的局部优化，比如：决定是否并发执行。针对不同的 action所需数据和信息，执行器需要经由 meta service 与storage engine的客户端与他们通信。

最后，如果你想尝试编译一下 Nebula 源代码可参考如下方式：

![build](https://www-cdn.nebula-graph.com.cn/nebula-blog/Architecture0207.png)

有问题请在 GitHub（GitHub 地址：[https://github.com/vesoft-inc/nebula](https://github.com/vesoft-inc/nebula)）

# 推荐阅读

- [Nebula 架构剖析系列（零）图数据库的整体架构设计](https://nebula-graph.com.cn/posts/nebula-graph-architecture-overview/)
- [Nebula 架构剖析系列（一）图数据库的存储设计](https://nebula-graph.com.cn/posts/nebula-graph-storage-engine-overview/)



本篇文章将带你了解 Nebula Query Engine 的架构。

Nebula 架构剖析系列（二）图数据库的查询引擎设计


![image](https://user-images.githubusercontent.com/57335825/87172263-cf734400-c288-11ea-96d0-1bb800700d16.png)

# 摘要

在讨论某个数据库时，存储（Storage）和计算（Query Engine）通常是讨论的热点，也是爱好者们了解某个数据库不可或缺的部分。每个数据库都有其独有的存储、计算方式，今天就和图图来学习下图数据库 NebulaGraph 的存储部分。

Nebula 的 Storage 包含两个部分， 一是 meta 相关的存储，我们称之为 `Meta Service`，另一个是 data 相关的存储，我们称之为 `Storage Service`。 这两个服务是两个独立的进程，数据也完全隔离，当然部署也是分别部署， 不过两者整体架构相差不大，本文最后会提到这点。如果没有特殊说明，本文中 Storage Service 代指 data 的存储服务。接下来，大家就随我一起看一下 Storage Service 的整个架构。 Let's go~

# Architecture

![storage service ](https://www-cdn.nebula-graph.com.cn/nebula-blog/Architecture0102.png)

图一 storage service 架构图

如图1 所示，Storage Service 共有三层，最底层是 Store Engine，它是一个单机版 local store engine，提供了对本地数据的 `get` / `put` / `scan` / `delete` 操作，相关的接口放在 KVStore / KVEngine.h 文件里面，用户完全可以根据自己的需求定制开发相关 local store plugin，目前 Nebula 提供了基于 RocksDB 实现的 Store Engine。

在 local store engine 之上，便是我们的 Consensus 层，实现了 Multi Group Raft，每一个 Partition 都对应了一组 Raft Group，这里的 Partition 便是我们的数据分片。目前 Nebula 的分片策略采用了 `静态 Hash` 的方式，具体按照什么方式进行 Hash，在下一个章节 schema 里会提及。用户在创建 SPACE 时需指定 Partition 数，Partition 数量一旦设置便不可更改，一般来讲，Partition 数目要能满足业务将来的扩容需求。

在 Consensus 层上面也就是 Storage Service 的最上层，便是我们的 Storage interfaces，这一层定义了一系列和图相关的 API。 这些 API 请求会在这一层被翻译成一组针对相应 Partition 的 kv 操作。正是这一层的存在，使得我们的存储服务变成了真正的图存储，否则，Storage Service 只是一个 kv 存储罢了。而 Nebula 没把 kv 作为一个服务单独提出，其最主要的原因便是图查询过程中会涉及到大量计算，这些计算往往需要使用图的 schema，而 kv 层是没有数据 schema 概念，这样设计会比较容易实现计算下推。

# Schema & Partition

图存储的主要数据是点和边，但 Nebula 存储的数据是一张属性图，也就是说除了点和边以外，Nebula 还存储了它们对应的属性，以便更高效地使用属性过滤。

对于点来说，我们使用不同的 Tag 表示不同类型的点，同一个 VertexID 可以关联多个 Tag，而每一个 Tag 都有自己对应的属性。对应到 kv 存储里面，我们使用 vertexID + TagID 来表示 key，我们把相关的属性编码后放在 value 里面，具体 key 的 format 如图2 所示：

![Vertex Key Format](https://www-cdn.nebula-graph.com.cn/nebula-blog/Architecture0103.png)
图二 Vertex Key Format

- `Type`：1 个字节，用来表示 key 类型，当前的类型有 data, index, system 等
- `Part ID`：3 个字节，用来表示数据分片 Partition，此字段主要用于 **Partition 重新分布(balance) 时方便根据前缀扫描整个 Partition 数据**
- `Vertex ID`：8 个字节， 用来表示点的 ID
- `Tag ID`：4 个字节, 用来表示关联的某个 tag
- `Timestamp`：8 个字节，对用户不可见，未来实现分布式事务（MVCC）时使用

在一个图中，每一条逻辑意义上的边，在 Nebula Graph 中会建模成两个独立的 key-value，分别称为 out-key 和in-key。out-key 与这条边所对应的起点存储在同一个 partition 上，in-key 与这条边所对应的终点存储在同一个partition 上。通常来说，out-key 和 in-key 会分布在两个不同的 Partition 中。

两个点之间可能存在多种类型的边，Nebula 用 Edge Type 来表示边类型。而同一类型的边可能存在多条，比如，定义一个 edge type "转账"，用户 A 可能多次转账给 B， 所以 Nebula 又增加了一个 Rank 字段来做区分，表示 A 到 B 之间多次转账记录。Edge key 的 format 如图3 所示：

![image](https://www-cdn.nebula-graph.com.cn/nebula-blog/Architecture0104.png)

图三 Edge Key Format

- `Type`：1 个字节，用来表示 key 的类型，当前的类型有 data, index, system 等。
- `Part ID`：3 个字节，用来表示数据分片 Partition，此字段主要用于 **Partition 重新分布（通过 BALANCE 命令）时方便根据前缀扫描整个 Partition 数据**
- `Vertex ID`：8 个字节， 出边里面用来表示源点的 ID， 入边里面表示目标点的 ID。
- `Edge Type`：4 个字节, 用来表示这条边的类型，如果大于 0 表示出边，小于 0 表示入边。
- `Rank`：8 个字节，用来处理同一种类型的边存在多条的情况。用户可以根据自己的需求进行设置，这个字段可_存放交易时间_、_交易流水号_、或_某个排序权重_
- `Vertex ID`：8 个字节，出边里面用来表示目标点的 ID， 入边里面表示源点的 ID。
- `Timestamp`：8 个字节，对用户不可见，未来实现分布式做事务的时候使用。

针对 Edge Type 的值，若如果大于 0 表示出边，则对应的 edge key format 如图4 所示；若 Edge Type 的值小于 0，则对应的 edge key format 如图5 所示

![image](https://www-cdn.nebula-graph.com.cn/nebula-blog/Architecture0105.png)

图4 出边的 Key Format

![image](https://www-cdn.nebula-graph.com.cn/nebula-blog/Architecture0106.png)

图5 入边的 Key Format

对于点或边的属性信息，有对应的一组 kv pairs，Nebula 将它们编码后存在对应的 value 里。由于 Nebula 使用强类型 schema，所以在解码之前，需要先去 Meta Service 中取具体的 schema 信息。另外，为了支持在线变更 schema，在编码属性时，会加入对应的 schema 版本信息，具体的编解码细节在这里不作展开，后续会有专门的文章讲解这块内容。

OK，到这里我们基本上了解了 Nebula 是如何存储数据的，那数据是如何进行分片呢？很简单，对 Vertex ID `取模` 即可。通过对 Vertex ID 取模，同一个点的所有_出边_，_入边_以及这个点上所有关联的 _Tag 信息_都会被分到同一个 Partition，这种方式大大地提升了查询效率。对于在线图查询来讲，最常见的操作便是从一个点开始向外 BFS（广度优先）拓展，于是拿一个点的出边或者入边是最基本的操作，而这个操作的性能也决定了整个遍历的性能。BFS 中可能会出现按照某些属性进行剪枝的情况，Nebula 通过将属性与点边存在一起，来保证整个操作的高效。当前许多的图数据库通过 Graph 500 或者 Twitter 的数据集试来验证自己的高效性，这并没有代表性，因为这些数据集没有属性，而实际的场景中大部分情况都是属性图，并且实际中的 BFS 也需要进行大量的剪枝操作。

# KVStore

为什么要自己做 KVStore，这是我们无数次被问起的问题。理由很简单，当前开源的 KVStore 都很难满足我们的要求：

- **性能**，**性能**，**性能**：Nebula 的需求很直接：高性能 pure kv；
- **以 library 的形式提供**：对于强 schema 的 Nebula 来讲，计算下推需要 schema 信息，而计算下推实现的好坏，是 Nebula 是否高效的关键；
- **数据强一致**：这是分布式系统决定的；
- **使用 C++实现**：这由团队的技术特点决定；

基于上述要求，Nebula 实现了自己的 KVStore。当然，对于性能完全不敏感且不太希望搬迁数据的用户来说，Nebula 也提供了整个KVStore 层的 plugin，直接将 Storage Service 搭建在第三方的 KVStore 上面，目前官方提供的是 HBase 的 plugin。

Nebula KVStore 主要采用 RocksDB 作为本地的存储引擎，对于多硬盘机器，为了充分利用多硬盘的并发能力，Nebula 支持自己管理多块盘，用户只需配置多个不同的数据目录即可。分布式 KVStore 的管理由 Meta Service 来统一调度，它记录了所有 Partition 的分布情况，以及当前机器的状态，当用户增减机器时，只需要通过 console 输入相应的指令，Meta Service 便能够生成整个 balance plan 并执行。（之所以没有采用完全自动 balance 的方式，主要是为了减少数据搬迁对于线上服务的影响，balance 的时机由用户自己控制。）

为了方便对于 WAL 进行定制，Nebula KVStore 实现了自己的 WAL 模块，每个 partition 都有自己的 WAL，这样在追数据时，不需要进行 wal split 操作， 更加高效。 另外，为了实现一些特殊的操作，专门定义了 Command Log 这个类别，这些 log 只为了使用 Raft 来通知所有 replica 执行某一个特定操作，并没有真正的数据。除了 Command Log 外，Nebula 还提供了一类日志来实现针对某个 Partition 的 atomic operation，例如 CAS，read-modify-write，它充分利用了Raft 串行的特性。

关于多图空间（space）的支持：一个 Nebula KVStore 集群可以支持多个 space，每个 space 可设置自己的 partition 数和 replica 数。不同 space 在物理上是完全隔离的，而且在同一个集群上的不同 space 可支持不同的 store engine 及分片策略。

# Raft

作为一个分布式系统，KVStore 的 replication，scale out 等功能需 Raft 的支持。当前，市面上讲 Raft 的文章非常多，具体原理性的内容，这里不再赘述，本文主要说一些 Nebula Raft 的一些特点以及工程实现。

## Multi Raft Group

由于 Raft 的日志不允许空洞，几乎所有的实现都会采用 Multi Raft Group 来缓解这个问题，因此 partition 的数目几乎决定了整个 Raft Group 的性能。但这也并不是说 Partition 的数目越多越好：每一个 Raft Group 内部都要存储一系列的状态信息，并且每一个 Raft Group 有自己的 WAL 文件，因此 Partition 数目太多会增加开销。此外，当 Partition 太多时， 如果负载没有足够高，batch 操作是没有意义的。比如，一个有 1w tps 的线上系统单机，它的单机 partition 的数目超过 1w，可能每个 Partition 每秒的 tps 只有 1，这样 batch 操作就失去了意义，还增加了 CPU 开销。
实现 Multi Raft Group 的最关键之处有两点，**第一是共享 Transport 层**，因为每一个 Raft Group 内部都需要向对应的 peer  发送消息，如果不能共享 Transport 层，连接的开销巨大；**第二是线程模型**，Mutli Raft Group 一定要共享一组线程池，否则会造成系统的线程数目过多，导致大量的 context switch 开销。

## Batch

对于每个 Partition来说，由于串行写 WAL，为了提高吞吐，做 batch 是十分必要的。一般来讲，batch 并没有什么特别的地方，但是 Nebula 利用每个 part 串行的特点，做了一些特殊类型的 WAL，带来了一些工程上的挑战。

举个例子，Nebula 利用 WAL 实现了无锁的 CAS 操作，而每个 CAS 操作需要之前的 WAL 全部 commit 之后才能执行，所以对于一个 batch，如果中间夹杂了几条 CAS 类型的 WAL, 我们还需要把这个 batch 分成粒度更小的几个 group，group 之间保证串行。还有，command 类型的 WAL 需要它后面的 WAL 在其 commit 之后才能执行，所以整个 batch 划分 group 的操作工程实现上比较有特色。

## Learner

Learner 这个角色的存在主要是为了`应对扩容`时，新机器需要"追"相当长一段时间的数据，而这段时间有可能会发生意外。如果直接以 follower 的身份开始追数据，就会使得整个集群的 HA 能力下降。 Nebula 里面 learner 的实现就是采用了上面提到的 command wal，leader 在写 wal 时如果碰到 add learner 的 command， 就会将 learner 加入自己的 peers，并把它标记为 learner，这样在统计多数派的时候，就不会算上 learner，但是日志还是会照常发送给它们。当然 learner 也不会主动发起选举。

## Transfer Leadership

Transfer leadership 这个操作对于 balance 来讲至关重要，当我们把某个 Paritition 从一台机器挪到另一台机器时，首先便会检查 source 是不是 leader，如果是的话，需要先把他挪到另外的 peer 上面；在搬迁数据完毕之后，通常还要把 leader 进行一次 balance，这样每台机器承担的负载也能保证均衡。

实现 transfer leadership， 需要注意的是 leader 放弃自己的 leadership，和 follower 开始进行 leader election 的时机。对于 leader 来讲，当 transfer leadership command 在 commit 的时候，它放弃 leadership；而对于 follower 来讲，当收到此 command 的时候就要开始进行 leader election，这套实现要和 Raft 本身的 leader election 走一套路径，否则很容易出现一些难以处理的 corner case。

## Membership change

为了避免脑裂，当一个 Raft Group 的成员发生变化时，需要有一个中间状态， 这个状态下 old group 的多数派与 new group 的多数派总是有 overlap，这样就防止了 old group 或者新 group 单方面做出决定，这就是[论文](https://raft.github.io/raft.pdf)中提到的 `joint consensus` 。为了更加简化，Diego Ongaro 在自己的博士论文中提出**每次增减一个 peer 的方式**，**以保证 old group 的多数派总是与 new group 的多数派有 overlap**。Nebula 的实现也采用了这个方式，只不过 add member 与 remove member 的实现有所区别，具体实现方式本文不作讨论，有兴趣的同学可以参考 Raft Part class 里面 `addPeer`  /  `removePeer`  的实现。

## Snapshot

Snapshot 如何与 Raft 流程结合起来，[论文](https://raft.github.io/raft.pdf)中并没有细讲，但是这一部分我认为是一个 Raft 实现里最容易出错的地方，因为这里会产生大量的 corner case。

举一个例子，当 leader 发送 snapshot 过程中，如果 leader 发生了变化，该怎么办？ 这个时候，有可能 follower 只接到了一半的 snapshot 数据。 所以需要有一个 Partition 数据清理过程，由于多个 Partition 共享一份存储，因此如何清理数据又是一个很麻烦的问题。另外，snapshot 过程中，会产生大量的 IO，为了性能考虑，我们不希望这个过程与正常的 Raft 共用一个 IO threadPool，并且整个过程中，还需要使用大量的内存，如何优化内存的使用，对于性能十分关键。由于篇幅原因，我们并不会在本文对这些问题展开讲述，有兴趣的同学可以参考 `SnapshotManager`  的实现。

# Storage Service

在 KVStore 的接口之上，Nebula 封装有图语义接口，主要的接口如下：

- `getNeighbors`：查询一批点的出边或者入边，返回边以及对应的属性，并且需要支持条件过滤；
- `Insert vertex/edge`：插入一条点或者边及其属性；
- `getProps`：获取一个点或者一条边的属性；

这一层会将图语义的接口转化成 kv 操作。为了提高遍历的性能，还要做并发操作。

# Meta Service

在 KVStore 的接口上，Nebula 也同时封装了一套 meta 相关的接口。Meta Service 不但提供了图 schema 的增删查改的功能，还提供了集群的管理功能以及用户鉴权相关的功能。Meta Service 支持单独部署，也支持使用多副本来保证数据的安全。

# 总结

这篇文章给大家大致介绍了 Nebula Storage 层的整体设计，由于篇幅原因， 很多细节没有展开讲， 欢迎大家到我们的微信群里提问，交流图数据库技术？加入 Nebula 交流群请先[填写下你的 Nebula 名片](https://wj.qq.com/s2/8321168/8e2f/)，Nebula 小助手会拉你进群~~。

# 推荐阅读

- [Nebula 架构剖析系列（零）图数据库的整体架构设计](https://nebula-graph.com.cn/posts/nebula-graph-architecture-overview/)
- [Nebula 架构剖析系列（二）图数据库的查询引擎设计](https://nebula-graph.com.cn/posts/nebula-graph-query-engine-overview/)

在讨论某个数据库时，存储和计算通常是讨论的热点，也是爱好者们了解某个数据库不可或缺的部分，本文主要讲述了存储部分的设计。

Nebula 架构剖析系列（一）图数据库的存储设计


![nebula-architecture](https://user-images.githubusercontent.com/57335825/87115631-a8852580-c228-11ea-877a-b48ba92fbb8b.png)

NebulaGraph 是一个高性能的分布式开源图数据库，本文为大家介绍 NebulaGraph 的整体架构。

![nebula-architecture-overview](https://www-cdn.nebula-graph.com.cn/nebula-blog/Architecture0002.png)

一个完整的 Nebula 部署集群包含三个服务，即 Query Service，Storage Service 和 Meta Service。每个服务都有其各自的可执行二进制文件，这些二进制文件既可以部署在同一组节点上，也可以部署在不同的节点上。

# Meta Service
上图为 NebulaGraph 的架构图，其右侧为 Meta Service 集群，它采用 leader / follower 架构。Leader 由集群中所有的 Meta Service 节点选出，然后对外提供服务。Followers 处于待命状态并从 leader 复制更新的数据。一旦 leader 节点 down 掉，会再选举其中一个 follower 成为新的 leader。

Meta Service 不仅负责存储和提供图数据的 meta 信息，如 schema、partition 信息等，还同时负责指挥数据迁移及 leader 的变更等运维操作。

# 存储计算分离

在架构图中 Meta Service 的左侧，为 NebulaGraph 的主要服务，Nebula 采用存储与计算分离的架构，虚线以上为计算，以下为存储。

存储计算分离有诸多优势，最直接的优势就是，计算层和存储层可以根据各自的情况弹性扩容、缩容。

存储计算分离还带来的另一个优势：使水平扩展成为可能。

此外，存储计算分离使得 Storage Service 可以为多种类型的计算层或者计算引擎提供服务。当前 Query Service 是一个高优先级的计算层，而各种迭代计算框架会是另外一个计算层。

# 无状态计算层

现在我们来看下计算层，每个计算节点都运行着一个无状态的查询计算引擎，而节点彼此间无任何通信关系。计算节点仅从 Meta Service 读取 meta 信息，以及和 Storage Service 进行交互。这样设计使得计算层集群更容易使用 K8s 管理或部署在云上。

计算层的负载均衡有两种形式，最常见的方式是在计算层上加一个负载均衡，第二种方法是将计算层所有节点的 IP 地址配置在客户端中，这样客户端可以随机选取计算节点进行连接。

每个查询计算引擎都能接收客户端的请求，解析查询语句，生成抽象语法树（AST）并将 AST 传递给执行计划器和优化器，最后再交由执行器执行。

# Shared-nothing 分布式存储层

Storage Service 采用 shared-nothing 的分布式架构设计，每个存储节点都有多个本地 KV 存储实例作为物理存储。Nebula 采用多数派协议 Raft 来保证这些 KV 存储之间的一致性（由于 Raft 比 Paxo 更简洁，我们选用了 Raft）。在 KVStore 之上是图语义层，用于将图操作转换为下层 KV 操作。

图数据（点和边）是通过 Hash 的方式存储在不同 Partition 中。这里用的 Hash 函数实现很直接，即 vertex_id 取余 Partition 数。在 NebulaGraph 中，Partition 表示一个虚拟的数据集，这些 Partition 分布在所有的存储节点，分布信息存储在 Meta Service 中（因此所有的存储节点和计算节点都能获取到这个分布信息）。

# 推荐阅读

- [Nebula 架构剖析系列（一）图数据库的存储设计](https://nebula-graph.com.cn/posts/nebula-graph-storage-engine-overview/)
- [Nebula 架构剖析系列（二）图数据库的查询引擎设计](https://nebula-graph.com.cn/posts/nebula-graph-query-engine-overview/)

---

交流图数据库技术？加入 Nebula 交流群请先[填写下你的 Nebula 名片](https://wj.qq.com/s2/8321168/8e2f/)，Nebula 小助手会拉你进群~~


本文为大家介绍图数据库 NebulaGraph 的整体架构。

Nebula 架构剖析系列（零）图数据库的整体架构设计


> [NebulaGraph](https://0x7.me/osc2github)：一个开源的分布式图数据库。作为唯一能够存储万亿个带属性的节点和边的在线图数据库，NebulaGraph 不仅能够在高并发场景下满足毫秒级的低时延查询要求，还能够实现服务高可用且保障数据安全性。

本篇主要介绍 NebulaGraph 的数据模型和系统架构设计。

# 有向属性图 DirectedPropertyGraph

NebulaGraph 采用易理解的有向属性图来建模，也就是说，在逻辑上，图由两种图元素构成：顶点和边。

![model](https://www-cdn.nebula-graph.com.cn/nebula-blog/DataModel01.png)

## 顶点 Vertex

在 NebulaGraph 中顶点由标签 `tag` 和对应 `tag` 的属性组构成， `tag` 代表顶点的类型，属性组代表 `tag` 拥有的一种或多种属性。一个顶点必须至少有一种类型，即标签，也可以有多种类型。每种标签有一组相对应的属性，我们称之为 `schema` 。

如上图所示，有两种 `tag` 顶点：player 和 team。player 的 `schema` 有三种属性 `ID` （vid），`Name` （sting）和 `Age` （int）；team 的 `schema` 有两种属性 `ID` （vid）和 `Name` （string）。

和 Mysql 一样，NebulaGraph 是一种强 schema 的数据库，属性的名称和数据类型都是在数据写入前确定的。


## 边 Edge

在 NebulaGraph 中边由类型和边属性构成，而 NebulaGraph 中边均是有向边，有向边表明一个顶点（ 起点 `src` ）指向另一个顶点（ 终点 `dst` ）的**关联关系**。此外，在 NebulaGraph 中我们将边类型称为 `edgetype` ，每一条边**只有一种**`edgetype` ，每种 `edgetype` 相应定义了这种边上属性的 `schema` 。

回到上面的图例，图中有两种类型的边，一种为 player 指向 player 的 **like** 关系，属性为 **likeness** (double)；另一种为 player 指向 team 的 **serve** 关系，两个属性分别为 start_year (int) 和 end_year (int)。

> 需要说明的是，起点1 和终点2 之间，可以同时存在多条相同或者不同类型的边。

# 图分割 GraphPartition

由于超大规模关系网络的节点数量高达百亿到千亿，而边的数量更会高达万亿，即使仅存储点和边两者也远大于一般服务器的容量。因此需要有方法将图元素切割，并存储在不同逻辑分片 `partition` 上。NebulaGraph 采用边分割的方式，默认的分片策略为**哈希散列**，partition 数量为静态设置并不可更改。

![partition](https://www-cdn.nebula-graph.com.cn/nebula-blog/DataModel02.png)

# 数据模型 DataModel

在 NebulaGraph 中，每个顶点被建模为一个 `key-value` ，根据其 vertexID（或简称 vid）哈希散列后，存储到对应的 partition 上。

![format](https://www-cdn.nebula-graph.com.cn/nebula-blog/DataModel03.png)

一条逻辑意义上的边，在 NebulaGraph 中将会被建模为两个独立的 `key-value` ，分别称为 `out-key` 和 `in-key` 。out-key 与这条边所对应的起点存储在同一个 partition 上，in-key 与这条边所对应的终点存储在同一个 partition 上。

![format](https://www-cdn.nebula-graph.com.cn/nebula-blog/DataModel04.png)

关于数据模型的详细设计会在后续的系列文章中介绍。

# 系统架构 Architecture

NebulaGraph 包括四个主要的功能模块，分别是**存储层**、**元数据服务**、**计算层**和**客户端**。

![nebula-architecture](https://www-cdn.nebula-graph.com.cn/nebula-blog/DataModel05.png)

## 存储层 Storage

在 NebulaGraph 中存储层对应进程是 `nebula-storaged` ，其核心为基于 Raft（用来管理日志复制的一致性算法） 协议的分布式 `Key-valueStorage` 。目前支持的主要存储引擎为「Rocksdb」和「HBase」。Raft 协议通过 `leader/follower` 的方式，来保持数据之间的一致性。Nebula Storage 主要增加了以下功能和优化：

1. Parallel Raft：允许多台机器上的相同 partiton-id 组成一个 `Raft group` 。通过多组 Raft group 实现并发操作。
1. Write Path & batch：Raft 协议的多机器间同步依赖于日志 id 顺序性，这样的吞吐量 `throughput` 较低。通过批量和乱序提交的方式可以实现更高的吞吐量。
1. Learner：基于异步复制的 learner。当集群中增加新的机器时，可以将其先标记为 learner，并异步从 `leader/follower` 拉取数据。当该 learner 追上 leader 后，再标记为 follower，参与 Raft 协议。
1. Load-balance：对于部分访问压力较大的机器，将其所服务的 partition 迁移到较冷的机器上，以实现更好的负载均衡。

![kv-storage](https://www-cdn.nebula-graph.com.cn/nebula-blog/DataModel06.png)

## 元数据服务层 Metaservice

Metaservice 对应的进程是 `nebula-metad` ，其主要的功能有：

1. 用户管理：NebulaGraph 的用户体系包括 `Goduser` ， `Admin` ， `User` ， `Guest`  四种。每种用户的操作权限不一。
1. 集群配置管理：支持上线、下线新的服务器。
1. 图空间管理：增持增加、删除图空间，修改图空间配置（Raft副本数）
1. Schema 管理：NebulaGraph 为强 schema 设计。
  - 通过 Metaservice 记录 Tag 和 Edge 的属性的各字段的类型。支持的类型有：整型 int, 双精度类型 double, 时间数据类型 timestamp, 列表类型 list等；
  - 多版本管理，支持增加、修改和删除 schema，并记录其版本号
  - TTL 管理，通过标识到期回收 `time-to-live` 字段，支持数据的自动删除和空间回收

MetaService 层为有状态的服务，其状态持久化方法与 Storage 层一样通过 `KVStore` 方式存储。

![meta-service](https://www-cdn.nebula-graph.com.cn/nebula-blog/DataModel07.png)

## 计算层 Query Engine & Query Language(nGQL)

计算层对应的进程是 `nebula-graphd` ，它由完全对等无状态无关联的计算节点组成，计算节点之间相互无通信。**Query Engine** 层的主要功能，是解析客户端发送 nGQL 文本，通过词法解析 `Lexer` 和语法解析 `Parser` 生成执行计划，并通过优化后将执行计划交由执行引擎，执行引擎通过 MetaService 获取图点和边的 schema，并通过存储引擎层获取点和边的数据。**Query Engine** 层的主要优化有：

1. 异步和并发执行：由于 IO 和网络均为长时延操作，需采用异步及并发操作。此外，为避免单个长 query 影响后续 query，Query Engine 为每个 query 设置单独的资源池以保证服务质量 QoS。
1. 计算下沉：为避免存储层将过多数据回传到计算层占用宝贵的带宽，条件过滤 `where` 等算子会随查询条件一同下发到存储层节点。
1. 执行计划优化：虽然在关系数据库 SQL 中执行计划优化已经经历了长时间的发展，但业界对图查询语言的优化研究较少。NebulaGraph 对图查询的执行计划优化进行了一定的探索，包括**执行计划缓存**和**上下文无关语句并发执行**。

![query-engine](https://www-cdn.nebula-graph.com.cn/nebula-blog/DataModel08.png)

## 客户端 API & Console

NebulaGraph 提供 C++、Java、Golang 三种语言的客户端，与服务器之间的通信方式为 RPC，采用的通信协议为 Facebook-Thrift。用户也可通过 Linux 上 console 实现对 NebulaGraph 操作。Web 访问方式目前在开发过程中。



在本文中我们将讲述图数据库 NebulaGraph 的常用概念及系统架构模型