跳转至

Storage服务

Nebula Graph的存储包含两个部分,一个是Meta相关的存储,称为Meta服务,在前文已有介绍。

另一个是具体数据相关的存储,称为Storage服务。其运行在nebula-storaged进程中。本文仅介绍Storage服务的架构设计。

优势

  • 高性能(自研KVStore)
  • 易水平扩展(Shared-nothing架构,不依赖NAS等硬件设备)
  • 强一致性(Raft)
  • 高可用性(Raft)
  • 支持向第三方系统进行同步(例如全文索引

Storage服务架构

image

Storage服务是由nebula-storaged进程提供的,用户可以根据场景配置nebula-storaged进程数量,例如测试环境1个,生产环境3个。

所有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服务的最底层,是一个单机版本地存储引擎,提供对本地数据的getputscan等操作。相关接口存储在KVStore.hKVEngine.h文件,用户可以根据业务需求定制开发相关的本地存储插件。

下文将基于架构介绍Storage服务的部分特性。

KVStore

Nebula Graph使用自行开发的KVStore,而不是其他开源KVStore,原因如下:

  • 需要高性能KVStore。
  • 需要以库的形式提供,实现高效计算下推。对于强Schema的Nebula Graph来说,计算下推时如何提供Schema信息,是高效的关键。
  • 需要数据强一致性。

基于上述原因,Nebula Graph使用RocksDB作为本地存储引擎,实现了自己的KVStore,有如下优势:

  • 对于多硬盘机器,Nebula Graph只需配置多个不同的数据目录即可充分利用多硬盘的并发能力。
  • 由Meta服务统一管理所有Storage服务,可以根据所有分片的分布情况和状态,手动进行负载均衡。

    Note

    不支持自动负载均衡是为了防止自动数据搬迁影响线上业务。

  • 定制预写日志(WAL),每个分片都有自己的WAL。
  • 支持多个图空间,不同图空间相互隔离,每个图空间可以设置自己的分片数和副本数。

数据存储格式

图存储的主要数据是点和边,Nebula Graph将点和边的信息存储为key,同时将点和边的属性信息存储在value中,以便更高效地使用属性过滤。

由于Nebula Graph 2.0的数据存储格式在1.x的基础上做了修改,下文将在介绍数据存储格式时同时介绍不同版本的差异。

  • 点数据存储格式

    The vertex format of storage service

    字段 说明
    Type key类型。长度为1个字节。
    PartID 数据分片编号。长度为3个字节。此字段主要用于Storage负载均衡(balance)时方便根据前缀扫描整个分片的数据。
    VertexID 点ID。当点ID类型为int时,长度为8个字节;当点ID类型为string时,长度为创建图空间时指定的fixed_string长度。
    TagID 点关联的Tag ID。长度为4个字节。
  • 边数据存储格式

    The edge format of storage service

    字段 说明
    Type key类型。长度为1个字节。
    PartID 数据分片编号。长度为3个字节。此字段主要用于Storage负载均衡(balance)时方便根据前缀扫描整个分片的数据。
    VertexID 点ID。前一个VertexID在出边里表示起始点ID,在"入边"里表示目的点ID;后一个VertexID"出边"里表示目的点ID,在"入边"里表示起始点ID。
    Edge type 边的类型。大于0表示"出边",小于0表示"入边"。长度为4个字节。
    Rank 用来处理两点之间有多个同类型边的情况。用户可以根据自己的需求进行设置,例如存放交易时间、交易流水号等。长度为8个字节,
    PlaceHolder 预留。长度为1个字节。

历史版本兼容性

2.0和1.x的差异如下:

  • 1.x中,点和边的Type值相同,而在2.0中进行了区分,即在物理上分离了点和边,方便快速查询某个点的所有Tag。
  • 1.x中,VertexID仅支持int类型,而在2.0中新增了string类型。
  • 2.0中取消了1.x中的保留字段Timestamp
  • 2.0中边数据新增字段PlaceHolder
  • 2.0中修改了索引的格式,以便支持范围查询。

属性说明

Nebula Graph使用强类型Schema。

对于点或边的属性信息,Nebula Graph会将属性信息编码后按顺序存储。由于属性的长度是固定的,查询时可以根据偏移量快速查询。在解码之前,需要先从Meta服务中查询具体的Schema信息(并缓存)。同时为了支持在线变更Schema,在编码属性时,会加入对应的Schema版本信息。

数据分片

由于超大规模关系网络的节点数量高达百亿到千亿,而边的数量更会高达万亿,即使仅存储点和边两者也远大于一般服务器的容量。因此需要有方法将图元素切割,并存储在不同逻辑分片(Partition)上。Nebula Graph 采用边分割的方式。

data partitioning

切边与存储放大

Nebula Graph中逻辑上的一条边对应着硬盘上的两个键值对(key-value pair),在边的数量和属性较多时,存储放大现象较明显。边的存储方式如下图所示。

edge storage

上图以最简单的两个点和一条边为例,起点SrcVertex通过边EdgeA连接目的点DstVertex,形成路径(SrcVertex)-[EdgeA]->(DstVertex)。这两个点和一条边会以4个键值对的形式保存在存储层的两个不同分片,即Partition x和Partition y中,详细说明如下:

  • 点SrcVertex的键值保存在Partition x中。Key的字段有Type、PartID(x),VID(Src)和TagID。SerializedValue即Value,是序列化的点属性。
  • 点EdgeA的第一份键值,这里用EdgeA_Out表示,与SrcVertex一同保存在Partition x中。Key的字段有Type、PartID(x)、VID(Src,即点SrcVertex的ID)、EdgeType(符号为正,代表边方向为出)、Rank(0)、VID(Dst,即点DstVertex的ID)和PlaceHolder。SerializedValue即Value,是序列化的边属性。
  • 点DstVertex的键值保存在Partition y中。Key的字段有Type、PartID(y),VID(Dst)和TagID。SerializedValue即Value,是序列化的点属性。
  • 点EdgeA的第二份键值,这里用EdgeA_In表示,与DstVertex一同保存在Partition y中。Key的字段有Type、PartID(y)、VID(Dst,即点DstVertex的ID)、EdgeType(符号为负,代表边方向为入)、Rank(0)、VID(Src,即点SrcVertex的ID)和PlaceHolder。SerializedValue即Value,是序列化的边属性,与EdgeA_Out中该部分的完全相同。

EdgeA_Out和EdgeA_In以方向相反的两条边的形式存在于存储层,二者组合成了逻辑上的一条边EdgeA。EdgeA_Out用于从起点开始的遍历请求,例如(a)-[]->();EdgeA_In用于指向目的点的遍历请求,或者说从目的点开始,沿着边的方向逆序进行的遍历请求,例如例如()-[]->(a)

如EdgeA_Out和EdgeA_In一样,Nebula Graph冗余了存储每条边的信息,导致存储边所需的实际空间翻倍。因为边对应的Key占用的硬盘空间较小,但Value占用的空间与属性值的长度和数量成正比,所以,当边的属性值较大或数量较多时候,硬盘空间占用量会比较大。

分片算法

分片策略采用静态 Hash的方式,即对点VID进行取模操作,同一个点的所有Tag、出边和入边信息都会存储到同一个分片,这种方式极大地提升了查询效率。

Note

创建图空间时需指定分片数量,分片数量设置后无法修改,建议设置时提前满足业务将来的扩容需求。

点和边分布在不同的分片,分片分布在不同的机器。分片数量在 CREATE SPACE 语句中指定,此后不可更改。

如果需要将某些点放置在相同的分片(例如在一台机器上),可以参考公式或代码

下文用简单代码说明VID和分片的关系。

// 如果ID长度为8,为了兼容1.0,将数据类型视为int64。
uint64_t vid = 0;
if (id.size() == 8) {
    memcpy(static_cast<void*>(&vid), id.data(), 8);
} else {
    MurmurHash2 hash;
    vid = hash(id.data());
}
PartitionID pId = vid % numParts + 1;

简单来说,上述代码是将一个固定的字符串进行哈希计算,转换成数据类型为int64的数字(int64数字的哈希计算结果是数字本身),将数字取模,然后加1,即:

pId = vid % numParts + 1;

示例的部分参数说明如下。

参数 说明
% 取模运算。
numParts VID所在图空间的分片数,即CREATE SPACE语句中的partition_num值。
pId VID所在分片的ID。

例如有100个分片,VID为1、101和1001的三个点将会存储在相同的分片。分片ID和机器地址之间的映射是随机的,所以不能假定任何两个分片位于同一台机器上。

Raft

关于 Raft 的简单介绍

分布式系统中,同一份数据通常会有多个副本,这样即使少数副本发生故障,系统仍可正常运行。这就需要一定的技术手段来保证多个副本之间的一致性。

基本原理:Raft 就是一种用于保证多副本一致性的协议。Raft 采用多个副本之间竞选的方式,赢得”超过半数”副本投票的(候选)副本成为 Leader,由 Leader 代表所有副本对外提供服务;其他 Follower 作为备份。当该 Leader 出现异常后(通信故障、运维命令等),其余 Follower 进行新一轮选举,投票出一个新的 Leader。Leader 和 Follower 之间通过心跳的方式相互探测是否存活,并以 Raft-wal 的方式写入硬盘,超过多个心跳仍无响应的副本会认为发生故障。

Note

因为 Raft-wal 需要定期写硬盘,如果硬盘写能力瓶颈会导致 Raft 心跳失败,导致重新发起选举。硬盘IO严重堵塞情况下,会导致长期无法选举出Leader。

读写流程:对于客户端的每个写入请求,Leader 会将该写入以 Raft-wal 的方式,将该条同步给其他 Follower,并只有在“超过半数”副本都成功收到 Raft-wal 后,才会返回客户端该写入成功。对于客户端的每个读取请求,都直接访问 Leader,而 Follower 并不参与读请求服务。

故障流程:场景1:考虑一个配置为单副本(图空间)的集群;如果系统只有一个副本时,其自身就是 Leader;如果其发生故障,系统将完全不可用。场景2:考虑一个配置为3副本(图空间)的集群;如果系统有 3 个副本,其中一个副本是 Leader,其他 2 个副本是 Follower;即使原 Leader 发生故障,剩下两个副本仍可投票出一个新的Leader(以及一个Follower),此时系统仍可使用;但是当这2个副本中任一者再次发生故障后,由于投票人数不足,系统将完全不可用。

Note

Raft 多副本的方式与 HDFS 多副本的方式是不同的,Raft 基于“多数派”投票,因此副本数量不能是偶数。

Multi Group Raft

由于Storage服务需要支持集群分布式架构,所以基于Raft协议实现了Multi Group Raft,即每个分片的所有副本共同组成一个Raft group,其中一个副本是leader,其他副本是follower,从而实现强一致性和高可用性。Raft的部分实现如下。

由于Raft日志不允许空洞,Nebula Graph使用Multi Group Raft缓解此问题,分片数量较多时,可以有效提高Nebula Graph的性能。但是分片数量太多会增加开销,例如Raft group内部存储的状态信息、WAL文件,或者负载过低时的批量操作。

实现Multi Group Raft有2个关键点:

  • 共享Transport层

    每一个Raft group内部都需要向对应的peer发送消息,如果不能共享Transport层,会导致连接的开销巨大。

  • 共享线程池

    如果不共享一组线程池,会造成系统的线程数过多,导致大量的上下文切换开销。

批量(Batch)操作

Nebula Graph中,每个分片都是串行写日志,为了提高吞吐,写日志时需要做批量操作,但是由于Nebula Graph利用WAL实现一些特殊功能,需要对批量操作进行分组,这是Nebula Graph的特色。

例如无锁CAS操作需要之前的WAL全部提交后才能执行,如果一个批量写入的WAL里包含了CAS类型的WAL,就需要拆分成粒度更小的几个组,还要保证这几组WAL串行提交。

leader切换(Transfer Leadership)

leader切换对于负载均衡至关重要,当把某个分片从一台机器迁移到另一台机器时,首先会检查分片是不是leader,如果是的话,需要先切换leader,数据迁移完毕之后,通常还要重新均衡leader分布

对于leader来说,提交leader切换命令时,就会放弃自己的leader身份,当follower收到leader切换命令时,就会发起选举。

成员变更

为了避免脑裂,当一个Raft group的成员发生变化时,需要有一个中间状态,该状态下新旧group的多数派需要有重叠的部分,这样就防止了新的group或旧的group单方面做出决定。为了更加简化,Diego Ongaro 在自己的博士论文中提出每次只增减一个peer的方式,以保证新旧group的多数派总是有重叠。Nebula Graph也采用了这个方式,只不过增加成员和移除成员的实现有所区别。具体实现方式请参见Raft Part class里addPeer/removePeer的实现。

与HDFS的区别

Storage服务基于Raft协议实现的分布式架构,与HDFS的分布式架构有一些区别。例如:

  • Storage服务本身通过Raft协议保证一致性,副本数量通常为奇数,方便进行选举leader,而HDFS存储具体数据的DataNode需要通过NameNode保证一致性,对副本数量没有要求。
  • Storage服务只有leader副本提供读写服务,而HDFS的所有副本都可以提供读写服务。
  • Storage服务无法修改副本数量,只能在创建图空间时指定副本数量,而HDFS可以调整副本数量。
  • Storage服务是直接访问文件系统,而HDFS的上层(例如HBase)需要先访问HDFS,再访问到文件系统,远程过程调用(RPC)次数更多。

总而言之,Storage服务更加轻量级,精简了一些功能,架构没有HDFS复杂,可以有效提高小块存储的读写性能。

视频

用户也可以通过视频全方位了解 Nebula Graph 的存储设计。


最后更新: September 10, 2021
Back to top