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

  • 时间:
  • 浏览:0

Nebula KVStore 主要采用 RocksDB 作为本地的存储引擎,对于多硬盘机器,为了充分利用多硬盘的并发能力,Nebula 支持我本人管理多块盘,用户只需配置多个不同的数据目录即可。分布式 KVStore 的管理由 Meta Service 来统一调度,它记录了所有 Partition 的分布情况报告,以及当前机器的情况报告,当用户增减机器时,只都要通过 console 输入相应的指令,Meta Service 便也能生成整个 balance plan 并执行。(固然没法采用详细自动 balance 的法律法律法律依据,主可是我 为了减少数据搬迁对于线上服务的影响,balance 的时机由用户我本人控制。)

针对 Edge Type 的值,若是因为大于 0 表示出边,则对应的 edge key format 如图4 所示;若 Edge Type 的值小于 0,则对应的 edge key format 如图5 所示

知乎:https://www.zhihu.com/org/nebulagraph/posts

在 local store engine 之上,便是亲戚亲戚朋友的 Consensus 层,实现了 Multi Group Raft,每有一好几条 Partition 都对应了一组 Raft Group,这里的 Partition 便是亲戚亲戚朋友的数据分片。目前 Nebula 的分片策略采用了 静态 Hash 的法律法律法律依据,具体按照哪些地法律法律依据律法律法律依据进行 Hash,在下有一好几条 章节 schema 里会提及。用户在创建 SPACE 都要指定 Partition 数,Partition 数量一旦设置便不可更改,一般来讲,Partition 数目也能满足业务将来的扩容需求。

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

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

Learner 你你这种 角色的趋于稳定主可是我 为了 应对扩容 时,新机器都要"追"相当长一段时间的数据,而这段时间有是因为会趋于稳定意外。是因为直接以 follower 的身份并且开使了了追数据,就会使得整个集群的 HA 能力下降。 Nebula 上端 learner 的实现可是我 采用了上端提到的 command wal,leader 在写 wal 时是因为碰到 add learner 的 command, 就会将 learner 加入我本人的 peers,并把它标记为 learner,并且在统计多数派的并且,就我很多 算上 learner,并且日志还是会照常发送给它们。当然 learner 可是我 会主动发起选举。

是因为 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 开销。

Nebula Graph:有一好几条 开源的分布式图数据库。

有一好几条 点之间是因为趋于稳定多种类型的边,Nebula 用 Edge Type 来表示边类型。而同一类型的边是因为趋于稳定多条,比如,定义有一好几条 edge type "转账",用户 A 是因为多次转账给 B, 可是我 Nebula 又增加了有一好几条 Rank 字段来做区分,表示 A 到 B 之间多次转账记录。 Edge key 的 format 如图3 所示:

Transfer leadership 你你这种 操作对于 balance 来讲至关重要,当亲戚亲戚朋友把某个 Paritition 从一台机器挪到另一台机器时,首先便会检查 source 是都在 leader,是因为是句子,都要先把他挪到另外的 peer 上端;在搬迁数据完毕并且,通常都要把 leader 进行一次 balance,并且每台机器承担的负载也能保证均衡。

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

对于点来说,亲戚亲戚朋友使用不同的 Tag 表示不类似 型的点,同有一好几条 VertexID 还都要关联多个 Tag,而每有一好几条 Tag 都在我本人对应的属性。对应到 kv 存储上端,亲戚亲戚朋友使用 vertexID + TagID 来表示 key,  亲戚亲戚朋友把相关的属性编码后倒进 value 上端,具体 key 的 format 如图2 所示:

在 Consensus 层上端也可是我 Storage Service 的最上层,便是亲戚亲戚朋友的 Storage interfaces,你你这种 层定义了一系列和图相关的 API。 哪些地方地方 API 请求会在你你这种 层被翻译成一组针对相应 Partition 的 kv 操作。正是你你这种 层的趋于稳定,使得亲戚亲戚朋友的存储服务变成了真正的图存储,并且,Storage Service 可是我 有一好几条 kv 存储罢了。而 Nebula 没把 kv 作为有一好几条 服务单独提出,其最主要的是因为便是图查询过程中会涉及到大量计算,哪些地方地方计算往往都要使用图的 schema,而 kv 层是没法数据 schema 概念,并且设计会比较容易实现计算下推。



图4 出边的 Key Format



图5 入边的 Key Format

关于多图空间(space)的支持:有一好几条 Nebula KVStore 集群还都要支持多个 space,每个 space 可设置我本人的 partition 数和 replica 数。不同 space 在物理上是详细隔离的,并且在同有一好几条 集群上的不同 space 可支持不同的 store engine 及分片策略。



图三 Edge Key Format

在讨论某个数据库时,存储 ( Storage ) 和计算 ( Query Engine ) 通常是讨论的热点,也是爱好者们了解某个数据库不可或缺的每种。每个数据库都在其独有的存储、计算法律法律法律依据,今天就和图图来学习下图数据库 Nebula Graph 的存储每种。

这篇文章给亲戚亲戚朋友大致介绍了 Nebula Storage 层的整体设计, 是因为篇幅是因为, 可是我 细节没法展开讲, 欢迎亲戚亲戚朋友到亲戚亲戚朋友的微信群里提问,加入 Nebula Graph 交流群,请联系 Nebula Graph 官方小助手微信号:NebulaGraphbot。

实现 transfer leadership, 都要注意的是 leader 放弃我本人的 leadership,和 follower 并且开使了了进行 leader election 的时机。对于 leader 来讲,当 transfer leadership command 在 commit 的并且,它放弃 leadership;而对于 follower 来讲,当收到此 command 的并且就要并且开使了了进行 leader election, 这套实现要和 Raft 这种 的 leader election 走一套路径,并且很容易老出你这种 难以处理的 corner case。

微博:https://weibo.com/nebulagraph

举个例子,Nebula 利用 WAL 实现了无锁的 CAS 操作,而每个 CAS 操作都要并且的 WAL 详细 commit 并且也能执行,可是我 对于有一好几条 batch,是因为上端夹杂了几条 CAS 类型的 WAL, 亲戚亲戚朋友还都要把你你这种 batch 分成粒度更小的几条 group,group 之间保证串行。还有,command 类型的 WAL 都要它上端的 WAL 在其 commit 并且也能执行,可是我 整个 batch 划分 group 的操作工程实现上比较有特色。

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



图一  storage service 架构图

Snapshot 如可与 Raft 流程结合起来,论文中并没法细讲,并且你你这种 每种我认为是有一好几条 Raft 实现里最容易出错的地方,是因为这里会产生大量的 corner case。

GitHub:https://github.com/vesoft-inc/nebula

为哪些地方想要 本人做 KVStore,这是亲戚亲戚朋友无数次被问起的问题报告 。理由很简单,当前开源的 KVStore 都不难 满足亲戚亲戚朋友的要求:

对于每个 Partition来说,是因为串行写 WAL,为了提高吞吐,做 batch 是十分必要的。一般来讲,batch 并没哪些地方地方有点痛 的地方,并且 Nebula 利用每个 part 串行的特点,做了你这种 特殊类型的 WAL,带来了你这种 工程上的挑战。

为了处理脑裂,当有一好几条 Raft Group 的成员趋于稳定变化时,都要有有一好几条 上端情况报告, 你你这种 情况报告下 old group 的多数派与 new group 的多数派总是有 overlap,并且就处理了 old group 是因为新 group 单方面做出决定,这可是我 论文中提到的 joint consensus 。为了更加复杂性,Diego Ongaro 在我本人的博士论文中提出每次增减有一好几条 peer 的法律法律法律依据以保证 old group 的多数派总是与 new group 的多数派有 overlap。 Nebula 的实现也采用了你你这种 法律法律法律依据,只不过 add member 与 remove member 的实现有所区别,具体实现法律法律法律依据本文不作讨论,有兴趣的同学还都要参考 Raft Part class 上端 addPeer  /  removePeer  的实现。

OK,到这里亲戚亲戚朋友基本上了解了 Nebula 是如可存储数据的,那数据是如可进行分片呢?很简单,对 Vertex ID 取模 即可。通过对 Vertex ID 取模,同有一好几条 点的所有_出边_,_入边_以及你你这种 点上所有关联的 _Tag 信息_都在被分到同有一好几条 Partition,你你这种 法律法律法律依据大大地提升了查询速度。对于在线图查询来讲,最常见的操作便是从有一好几条 点并且开使了了向外 BFS(广度优先)拓展,于是拿有一好几条 点的出边是因为入边是最基本的操作,而你你这种 操作的性能也决定了整个遍历的性能。BFS 中是因为会老出按照你这种 属性进行剪枝的情况报告,Nebula 通过将属性与点边趋于稳定一起去,来保证整个操作的高效。当前你这种 的图数据库通过 Graph 100 是因为 Twitter 的数据集试来验证我本人的高效性,这并没法代表性,是因为哪些地方地方数据集没法属性,而实际的场景中大每种情况报告都在属性图,并且实际中的 BFS 也都要进行大量的剪枝操作。

如图1 所示,Storage Service 共有三层,最底层是 Store Engine,它是有一好几条 单机版 local store engine,提供了对本地数据的 get / put / scan / delete 操作,相关的接口倒进 KVStore / KVEngine.h 文件上端,用户详细还都要根据我本人的需求定制开发相关 local store plugin,目前 Nebula 提供了基于 RocksDB 实现的  Store Engine。

对于点或边的属性信息,有对应的一组 kv pairs,Nebula 将它们编码后趋于稳定对应的 value 里。是因为 Nebula 使用强类型 schema,可是我 在解码并且,都要先去 Meta Service 中取具体的 schema 信息。另外,为了支持在线变更 schema,在编码属性时,会加入对应的 schema 版本信息,具体的编解码细节在这里不作展开,后续会有专门的文章讲解这块内容。

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

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

举有一好几条 例子,当 leader 发送 snapshot 过程中,是因为 leader 趋于稳定了变化,该咋整 办? 你你这种 并且,有是因为 follower 只接到了一半的 snapshot 数据。 可是我 都要有有一好几条  Partition 数据清理过程,是因为多个 Partition 共享一份存储,并且如可清理数据又是有一好几条 很麻烦的问题报告 。另外,snapshot 过程中,会产生大量的 IO,为了性能考虑,亲戚亲戚朋友不希望你你这种 过程与正常的 Raft 共用有一好几条 IO threadPool,并且整个过程中,还都要使用大量的内存,如可优化内存的使用,对于性能十分关键。是因为篇幅是因为,亲戚亲戚朋友何必 会在本文对哪些地方地方问题报告 展开讲述,有兴趣的同学还都要参考 SnapshotManager  的实现。

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

Nebula 的 Storage 包中含一好几条 每种, 一是 meta 相关的存储, 亲戚亲戚朋友称之为 Meta Service ,并且是 data 相关的存储, 亲戚亲戚朋友称之为 Storage Service。 这有一好几条 服务是有一好几条 独立的多多程序运行 ,数据也详细隔离,当然部署也是分别部署, 不过两者整体架构相差不大,本文最都在提到这点。 是因为没法特殊说明,本文中 Storage Service 代指 data 的存储服务。接下来,亲戚亲戚朋友就随我一起去看一下 Storage Service 的整个架构。 Let's go~

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



图二 Vertex Key Format