1/图形结构数据无处不在

字节跳动的所有产品的大部分业务数据，几乎都可以归入到以下三种：

-   用户信息、用户和用户的关系（关注、好友等）；
-   内容（视频、文章、广告等）；
-   用户和内容的联系（点赞、评论、转发、点击广告等）。

这三种数据关联在一起，形成图状（Graph）结构数据。

为了满足social graph 的在线增删改查场景，字节跳动自研了分布式图存储系统——ByteGraph。
针对上述图状结构数据，ByteGraph 支持有向属性图数据模型，支持 Gremlin 查询语言，支持灵活丰富的写入和查询接口，读写吞吐可扩展到千万 QPS，延迟毫秒级。
目前，ByteGraph 支持了头条、抖音、 TikTok、西瓜、火山等几乎字节跳动全部产品线，遍布全球机房。
在这篇文章中，将从适用场景、内部架构、关键问题分析几个方面作深入介绍。

ByteGraph 主要用于在线 OLTP 场景，而在离线场景下，图数据的分析和计算需求也逐渐显现。 
下面会从图数据库和图计算两个部分，分别来介绍字节跳动在这方面的一些工作。

2/ByteGraph的介绍

从数据模型角度看，图数据库内部数据是有向属性图，其基本元素是 Graph 中的点（Vertex）、边（Edge）以及其上附着的属性；作为一个工具，图数据对外提供的接口都是围绕这些元素展开。

图数据库本质也是一个存储系统，它和常见的 KV 存储系统、MySQL 存储系统的相比主要区别在于目标数据的逻辑关系不同和访问模式不同，对于数据内在关系是图模型以及在图上游走类和模式匹配类的查询，比如社交关系查询，图数据库会有更大的性能优势和更加简洁高效的接口。

2.1 为什么不选择开源图数据库

图数据库在 90 年代出现，直到最近几年在数据爆炸的大趋势下快速发展，百花齐放；但目前比较成熟的大部分都是面对传统行业较小的数据集和较低的访问吞吐场景，比如开源的 Neo4j 是单机架构；因此，在互联网场景下，通常都是基于已有的基础设施定制系统：比如 Facebook 基于 MySQL 系统封装了 Social Graph 系统 TAO，几乎承载了 Facebook 所有数据逻辑；Linkedln 在 KV 之上构建了 Social Graph 服务；微博是基于 Redis 构建了粉丝和关注关系。

字节跳动的 Graph 在线存储场景， 其需求也是有自身特点的，可以总结为：
- 海量数据存储：百亿点、万亿边的数据规模；并且图符合幂律分布，比如少量大 V 粉丝达到几千万；
- 海量吞吐：最大集群 QPS 达到数千万；
- 低延迟：要求访问延迟 pct99 需要限制在毫秒级；
- 读多写少：读流量是写流量的接近百倍之多；
- 轻量查询多，重量查询少：90%查询是图上二度以内查询；
- 容灾架构演进：要能支持字节跳动城域网、广域网、洲际网络之间主备容灾、异地多活等不同容灾部署方案。

事实上，我们调研过了很多业界系统， 这个主题可以再单独分享一篇文章。
但是，面对字节跳动世界级的海量数据和海量并发请求，用万亿级分布式存储、千万高并发、低延迟、稳定可控这三个条件一起去筛选，业界在线上被验证稳定可信赖的开源图存储系统基本没有满足的了；另外，对于一个承载公司核心数据的重要的基础设施，是值得长期投入并且深度掌控的。

因此，我们在 18 年 8 月份，开始从第一行代码开始踏上图数据库的漫漫征程，从解决一个最核心的抖音社交关系问题入手，逐渐演变为支持有向属性图数据模型、支持写入原子性、部分 Gremlin 图查询语言的通用图数据库系统，在公司所有产品体系落地，我们称之为 ByteGraph。下面，会从数据模型、系统架构等几个部分，由浅入深和大家分享我们的工作。

2.2 ByteGraph 的数据模型和 API

数据模型

就像我们在使用 SQL 数据库时，先要完成数据库 Schema 以及范式设计一样，ByteGraph 也需要用户完成类似的数据模型抽象，但图的数据抽象更加简单，基本上是把数据之间的关系“`翻译`”成有向属性图，我们称之为“构图”过程。

比如在前面提到的，如果想把用户关系存入 ByteGraph，第一步就是需要把用户抽象为点，第二步把"关注关系”、“好友关系”抽象为边就完全搞定了。下面，我们就从代码层面介绍下点边的数据类型。

• 点（Vertex） 点是图数据库的基本元素，通常反映的是静态信息。在 ByteGraph 中，点包含以下字段：

- 点的id(uint64_t): 比如用户id作为一个点
- 点的type(uint32_t): 比如appID作为点的type
- 点的属性（KV 对）：比如 'name': string，'age': int, 'gender': male，等自定义属性
- [id, type]唯一定义一个点

• 边（Edge） 一条边由两个点和点之间的边的类型组成，边可以描述点之间的关系，比如用户 A 关注了用户 B ，可以用以下字段来描述：

- 两个点（Vertex）: 比如用户A和用户B
- 边的类型(string): 比如“关注”
- 边的时间戳(uint64_t)：这个t值是业务自定义含义的，比如可以用于记录关注发生的时间戳
- 边属性（KV对）：比如'ts_us': int64 描述关系创建时间的属性，以及其他用户自定义属性

• 边的方向 在 ByteGraph 的数据模型中，边是有方向的，目前支持 3 种边的方向:

- 正向边：如 A 关注 B(A -> B)
- 反向边：如 B 被 A 关注(B <- A)
- 双向边：如 A 与 B 是好友(A <-> B)

场景使用伪码举例

构图完毕后，我们就可以把业务逻辑通过 Gremlin 查询语言来实现了；为便于大家理解，我们列举几种典型的场景为例。

• 场景一：记录关注关系 A 关注 B

// 创建用户A和B，可以使用 .property('name', 'Alice') 语句添加用户属性
g.addV().property("type", A.type).property("id", A.id)
g.addV().property("type", B.type).property("id", B.id)
// 创建关注关系 A -> B，其中addE("关注")中指定了边的类型信息，from和to分别指定起点和终点，
g.addE("关注").from(A.id, A.type).to(B.id, B.type).property("ts_us", now)

• 场景二：查询 A 关注的且关注了 C 的所有用户 用户 A 进入用户 C 的详情页面，想看看 A 和 C 之间的二度中间节点有哪些，比如 A->B,B->C，B 则为中间节点。

// where()表示对于上一个step的每个执行结果，执行子查询过滤条件，只保留关注了C的用户。
g.V().has("type", A.type).has("id", A.id).out("关注").where(out("关注").has("type", C.type).has("id", C.id).count().is(gte(1)))

• 场景三：查询 A 的好友的好友（二度关系）

// both("好友")相当于in("好友")和out("好友")的合集，
g.V().has("type", A.type).has("id", A.id).both("好友").both("好友").toSet()

2.3 系统架构

前面几个章节，从用户角度介绍了 ByteGraph 的适用场景和对外使用姿势。那 ByteGraph 架构是怎样的，内部是如何工作的呢，这一节就来从内部实现来作进一步介绍。

下面这张图展示了 ByteGraph 的内部架构，其中 bg 是 ByteGraph 的缩写。

就像 MySQL 通常可以分为 SQL 层和引擎层两层一样，ByteGraph 自上而下分为查询层 (bgdb)、存储/事务引擎层（bgkv）、磁盘存储层三层，每层都是由多个进程实例组成。其中 bgdb 层与 bgkv 层混合部署，磁盘存储层独立部署，我们详细介绍每一层的关键设计。

查询层(bgdb)

bgdb 层和 MySQL 的 SQL 层一样，主要工作是做读写请求的解析和处理；其中，所谓“处理”可以分为以下三个步骤：

1. 将客户端发来的 Gremlin 查询语句做语法解析，生成执行计划；
2. 并根据一定的路由规则（例如一致性哈希）找到目标数据所在的存储节点（bgkv），将执行计划中的读写请求发送给 多个 bgkv；
3. 将 bgkv 读写结果汇总以及过滤处理，得到最终结果，返回给客户端。

bgdb 层没有状态，可以水平扩容，用 Go 语言开发。

存储/事务引擎层（bgkv)

bgkv 层是由多个进程实例组成，每个实例管理整个集群数据的一个子集（shard / partition)。

bgkv 层的实现和功能有点类似内存数据库，提供高性能的数据读写功能，其特点是：

1. 接口不同：只提供点边读写接口；

2. 支持算子下推：通过把计算(算子)移动到存储（bgkv）上，能够有效提升读性能；

   1. 举例：比如某个大 V 最近一年一直在涨粉，bgkv 支持查询最近的 100 个粉丝，则不必读出所有的百万粉丝。

3. 缓存存储有机结合：其作为 KV store 的缓存层，提供缓存管理的功能，支持缓存加载、换出、缓存和磁盘同步异步 sync 等复杂功能。

从上述描述可以看出，bgkv 的性能和内存使用效率是非常关键的，因此采用 C++ 编写。

磁盘存储层(KV Cluster)

为了能够提供海量存储空间和较高的可靠性、可用性，数据必须最终落入磁盘，我们底层存储是选择了公司自研的分布式 KV store。

如何把图存储在 KV 数据库中

上一小节，只是介绍了 ByteGraph 内部三层的关系，细心的读者可能已经发现，ByteGraph 外部是图接口，底层是依赖 KV 存储，那么问题来了：如何把动辄百万粉丝的图数据存储在一个 KV 系统上呢？

在字节跳动的业务场景中，存在很多访问热度和“数据密度”极高的场景，比如抖音的大 V、热门的文章等，其粉丝数或者点赞数会超过千万级别；但作为 KV store，希望业务方的 KV 对的大小（Byte 数）是控制在 KB 量级的，且最好是大小均匀的：对于太大的 value，是会瞬间打满 I/O 路径的，无法保证线上稳定性；对于特别小的 value，则存储效率比较低。事实上，数据大小不均匀这个问题困扰了很多业务团队，在线上也会经常爆出事故。

对于一个有千万粉丝的抖音大 V，相当于图中的某个点有千万条边的出度，不仅要能存储下来，而且要能满足线上毫秒级的增删查改，那么 ByteGraph 是如何解决这个问题的呢？

思路其实很简单，总结来说，就是采用灵活的边聚合方式，使得 KV store 中的 value 大小是均匀的，具体可以用以下四条来描述：

1. 一个点（Vertex）和其所有相连的边组成了一数据组（Group）；不同的起点和及其终点是属于不同的 Group，是存储在不同的 KV 对的；比如用户 A 的粉丝和用户 B 的粉丝，就是分成不同 KV 存储；
2. 对于某一个点的及其出边，当出度数量比较小（KB 级别），将其所有出度即所有终点序列化为一个 KV 对，我们称之为一级存储方式（后面会展开描述）；
3. 当一个点的出度逐渐增多，比如一个普通用户逐渐成长为抖音大 V，我们则采用分布式 B-Tree 组织这百万粉丝，我们称之为二级存储；
4. 一级存储和二级存储之间可以在线并发安全的互相切换；

• 一级存储格式

一级存储格式中，只有一个 KV 对，key 和 value 的编码：

-  key: 某个起点 id + 起点 type + 边 type
-  value: 此起点的所有出边（Edge）及其边上属性聚合作为 value，但不包括终点的属性
复制代码

• 二级存储（点的出度大于阈值）

如果一个大 V 疯狂涨粉，则存储粉丝的 value 就会越来越大，解决这个问题的思路也很朴素：拆成多个 KV 对。

但如何拆呢？ ByteGraph 的方式就是把所有出度和终点拆成多个 KV 对，所有 KV 对形成一棵逻辑上的分布式 B-Tree，之所以说“逻辑上的”，是因为树中的节点关系是靠 KV 中 key 来指向的，并非内存指针； B-Tree 是分布式的，是指构成这棵树的各级节点是分布在集群多个实例上的，并不是单机索引关系。具体关系如下图所示：

其中，整棵 B-Tree 由多组 KV 对组成，按照关系可以分为三种数据：

• 根节点：根节点本质是一个 KV 系统中的一个 key，其编码方式和一级存储中的 key 相同

• Meta 数据：

  • Meta 数据本质是一个 KV 中的 value，和根节点组成了 KV 对；
  • Meta 内部存储了多个 PartKey，其中每个 PartKey 都是一个 KV 对中的 key，其对应的 value 数据就是下面介绍的 Part 数据；

• Part 数据

  • 对于二级存储格式，存在多个 Part，每个 Part 存储部分出边的属性和终点 ID
  • 每个 Part 都是一个 KV 对的 value，其对应的 key 存储在 Meta 中。

从上述描述可以看出，对于一个出度很多的点和其边的数据（比如大 V 和其粉丝），在 ByteGraph 中，是存储为多个 KV 的，面对增删查改的需求，都需要在 B-Tree 上做二分查找。相比于一条边一个 KV 对或者所有边存储成一个 KV 对的方式，B-Tree 的组织方式能够有效的在读放大和写放大之间做一些动态调整。

但在实际业务场景下，粉丝会处于动态变化之中：新诞生的大 V 会快速新增粉丝，有些大 V 会持续掉粉；因此，存储方式会在一级存储和二级存储之间转换，并且 B-Tree 会持续的分裂或者合并；这就会引发分布式的并发增删查改以及分裂合并等复杂的问题，有机会可以再单独分享下这个有趣的设计。

ByteGraph 和 KV store 的关系，类似文件系统和块设备的关系，块设备负责将存储资源池化并提供 Low Level 的读写接口，文件系统在块设备上把元数据和数据组织成各种树的索引结构，并封装丰富的 POSIX 接口，便于外部使用。

2.4 一些问题深入探讨

第三节介绍了 ByteGraph 的内在架构，现在我们更进一步，来看看一个分布式存储系统，在面对字节跳动万亿数据上亿并发的业务场景下两个问题的分析。

热点数据读写解决

热点数据在字节跳动的线上业务中广泛存在：热点视频、热点文章、大 V 用户、热点广告等等；热点数据可能会出现瞬时出现大量读写。ByteGraph 在线上业务的实践中，打磨出一整套应对性方案。

• 热点读

热点读的场景随处可见，比如线上实际场景：某个热点视频被频繁刷新，查看点赞数量等。在这种场景下，意味着访问有很强的数据局部性，缓存命中率会很高，因此，我们设计实现了多级的 Query Cache 机制以及热点请求转发机制；在 bgdb 查询层缓存查询结果， bgdb 单节点缓存命中读性能 20w QPS 以上，而且多个 bgdb 可以并发处理同一个热点的读请求，则系统整体应对热点度的“弹性”是非常充足的。

• 热点写

热点读和热点写通常是相伴而生的，热点写的例子也是随处可见，比如：热点新闻被疯狂转发， 热点视频被疯狂点赞等等。对于数据库而言，热点写入导致的性能退化的背后原因通常有两个：行锁冲突高或者磁盘写入 IOPS 被打满，我们分别来分析：

• 行锁冲突高：目前 ByteGraph 是单行事务模型，只有内存结构锁，这个锁的并发量是每秒千万级，基本不会构成写入瓶颈；

• 磁盘 IOPS 被打满：

  • IOPS（I/O Count Per Second）的概念：磁盘每秒的写入请求数量是有上限的，不同型号的固态硬盘的 IOPS 各异，但都有一个上限，当上游写入流量超过这个阈值时候，请求就会排队，造成整个数据通路堵塞，延迟就会呈现指数上涨最终服务变成不可用。
  • Group Commit 解决方案：Group Commit 是数据库中的一个成熟的技术方案，简单来讲，就是多个写请求在 bgkv 内存中汇聚起来，聚成一个 Batch 写入 KV store，则对外体现的写入速率就是 BatchSize * IOPS。

对于某个独立数据源来说，一般热点写的请求比热点读会少很多，一般不会超过 10K QPS，目前 ByteGraph 线上还没有出现过热点写问题问题。

图的索引

就像关系型数据库一样，图数据库也可以构建索引。默认情况下，对于同一个起点，我们会采用边上的属性（时间戳）作为主键索引；但为了加速查询，我们也支持其他元素（终点、其他属性）来构建二级的聚簇索引，这样很多查找就从全部遍历优化成了二分查找，使得查询速度大幅提升。

ByteGraph 默认按照边上的时间戳（ts）来排序存储，因此对于以下请求，查询效率很高：

• 查询最近的若干个点赞
• 查询某个指定时间范围窗口内加的好友

方向的索引可能有些费解，举个例子说明下：给定两个用户来查询是否存在粉丝关系，其中一个用户是大 V，另一个是普通用户，大 V 的粉丝可达千万，但普通用户的关注者一般不会很多；因此，如果用普通用户作为起点大 V 作为终点，查询代价就会低很多。其实，很多场景下，我们还需要用户能够根据任意一个属性来构建索引，这个也是我们正在支持的重要功能之一。

2.5 未来探索

过去的一年半时间里，ByteGraph 都是在有限的人力情况下，优先满足业务需求，在系统能力构建方面还是有些薄弱的，有大量问题都需要在未来突破解决：

• 从图存储到图数据库：对于一个数据库系统，是否支持 ACID 的事务，是一个核心问题，目前 ByteGraph 只解决了原子性和一致性，对于最复杂的隔离性还完全没有触碰，这是一个非常复杂的问题；另外，中国信通院发布了国内图数据库功能白皮书，以此标准，如果想做好一个功能完备的“数据库”系统，我们面对的还是星辰大海；
• 标准的图查询语言：目前，图数据库的查询语言业界还未形成标准（GQL 即将在 2020 年发布），ByteGraph 选择 Apache、AWS 、阿里云的 Gremlin 语言体系，但目前也只是支持了一个子集，更多的语法支持、更深入的查询优化还未开展；
• Cloud Native 存储架构演进：现在 ByteGraph 还是构建与 KV 存储之上，独占物理机全部资源；从资源弹性部署、运维托管等角度是否有其他架构演进的探索可能，从查询到事务再到磁盘存储是否有深度垂直整合优化的空间，也是一个没有被回答的问题；
• 现在 ByteGraph 是在 OLTP 场景下承载了大量线上数据，这些数据同时也会应用到推荐、风控等复杂分析和图计算场景，如何把 TP 和轻量 AP 查询融合在一起，具备部分 HTAP 能力，也是一个空间广阔的蓝海领域。