贝壳找房—【图数据库系列】Dgraph 原理篇
系列文章：
贝壳找房—【图数据库系列】Dgraph 简介篇
贝壳找房—【图数据库系列】之 JanusGraph VS Dgraph：贝壳分布式图数据库技术选型之路
通过上一篇的 Dgraph 简介 ，相信大家已经了解了 Dgraph 的一些基本概念和用法，本篇文章继续介绍 Dgraph 的一些底层实现原理。作为一个分布式图数据库，Dgraph 不仅支持水平扩展，还提供集群范围的 ACID 事务、同步复制、高可用等诸多特性。为了应对 OLTP 场景的高并发查询，Dgraph 用一种新颖的方式划分和存储图数据，最小化连接(join)和遍历(traversal)操作的网络开销，从而提升查询性能。本文将从数据组织、索引构建、查询处理、关键设计四个方面介绍其原理。
一、数据组织
数据格式
Dgraph 的输入数据可以是三元组格式或者 JSON 格式。在 Dgraph 内部，JSON 格式的数据会被转化为等价的三元组格式。
数据存储
在 Dgraph 中，数据的最小单位是一个三元组。三元组既可以表示一个属性(subject-predicate-value)，也可以表示一条边(subject-predicate-object)。Dgraph 为每个对象分配一个全局唯一的 id，称为 uid。Uid 是一个 64 位无符号整数，从 1 开始单调递增。
Dgraph 基于 predicate 进行数据分片，即所有相同 predicate 的三元组形成一个分片。在分片内部，根据 subject-predicate 将三元组进一步分组，每一组数据压缩成一个 key-value 对。其中 key 是 <subject, predicate>，value 是一个称为 posting list 的数据结构。
Posting list 是一个有序列表。对于指向值的 predicate(如 name)，posting list 是一个值列表；对于指向对象的 predicate，posting list 是一个 uid 列表，Dgraph 对其做了整数压缩优化。每 256 个 uids 组成一个 block，block 拥有一个基数(base)。Block 不存储 uid 本身，而是存储当前 uid 和上一个 uid 的差值。这个方法产生的压缩比是 10。
Dgraph 的存储方式非常有利于连接和遍历，一个边遍历只需要一个 KV 查询。例如，找到 X 的所有粉丝，只需要用 <follower，X> 当做 key 进行查询，就能获得一个 posting list，包含了所有粉丝的 uid；寻找 X 和 Y 的公共粉丝，只需要查询 <follower, X> 和 <follower, Y> 的 posting lists，然后求两者的交集。
如果有太多的三元组共享相同的 <subject，predicate>，posting list 就变得过大。Dgraph 的解决方法是，每当 posting list 的大小超过一个阈值，就把它分成两份，这样一个分割的 posting list 就会对应多个 keys。这些存储细节都是对用户透明的。(注：当前版本未支持 predicate 分割)
Dgraph 的存储后端是一个嵌入式的 key-value 存储，叫做 Badger。Badger 基于常见的 LSM-tree 数据结构而设计，但不同之处是，它可以把 key 和 value 分开存储，LSM-tree 只包含了 key 和 value 的地址，这样产生的 LSM-tree 占用空间更小，从而减小了读写放大。关于 Badger 的细节这里不展开讨论。
数据均衡
首先回顾一下 Dgraph 的架构：Dgraph 由 zero 节点和 alpha 节点组成。zero 是管理节点，alpha 是数据节点。alpha 节点分成若干个 group，每个 group 存储若干个数据分片。
由于分片的大小是不均匀的，因此不同 group 也是不均匀的。zero 节点的任务之一就是平衡 group 之间的数据大小。具体方法是，每个 group 周期性地向 zero 报告各个数据分片的大小。zero 根据这个信息在 group 之间移动分片，使得每个 group 的磁盘利用率接近。
二、索引构建
Dgraph 支持大部分索引需求。对于 string 类型，支持正则表达式、fulltext、term、exact 和 hash 索引；对于 datetime 类型，支持按年、月、日、小时索引；对于 geo 类型，支持 nearby、within 等索引。
查询语句通过函数来使用索引，每个索引有相应的分词器(tokenizer)，它们的关系如下：
| 字符串函数 | 索引/分词器 |
|---|---|
| eq | hash，exact，term，fulltext |
| le，ge，lt，gt | exact |
| allofterms，anyofterms | term |
| alloftext，anyoftext | fulltext |
| regexp | trigram |
索引跟数据一样，以 key-value 的形式存储，区别是 key 有所不同。数据的 key 是 <predicate, uid>，而索引的 key 是 <predicate, token>。Token 是索引的分词器从 value 中获取的，例如 hash 索引生成的 token 就是 hash 函数所计算的 hash 值。
在定义 schema 的时候，可以给 predicate 创建一个或多个索引。对该 predicate 的每次更新会调用一个或多个分词器来产生 tokens。更新的时候，首先从旧值的 tokens 的 posting lists 中删除相应的 uid，然后把 uid 添加到新产生的 tokens 的 posting lists 里。
以上图为例，说明索引构建过程。Schema 定义了三个 predicates 和它们的数据类型、索引类型。Mutation 以 JSON 格式写入一个对象。由于 key1 建立了 fulltext 索引，所以会调用 fulltext 分词器由 key1 的值"running fast"得到 run 和 fast 两个 tokens。它们分别和 key1 组成两个 badger key，然后把 uid 0x0a 添加到各自的 posting lists 里。这样，一个值的索引就转化为后端存储的 KVs。
三、查询处理
遍历
Dgraph 的查询通常从一个 uidlist 开始，沿着边进行遍历。
{
me(func: uid(0x1)){
pred_A
pred_B {
pred_B1
pred_B2
}
}
}
查询 1 的起点是 uid 为 0x1 的单个对象，处理过程如下：
- 查询 <pred_A, 0x1>、<pred_B, 0x1> 两个 key，分别获得一个值(或者值列表)和一个 uidlist。
- 对于 uidlist 中的每一个 UID，查询 <pred_B1, UID>、<pred_B2, UID>，获取相应的值。
函数
通常情况下，我们并不知道起始对象的 uid，所以需要用函数把全局 uid 空间削减为一个小的集合(甚至单个 uid)。如前所述，使用任何函数，都要在 schema 里创建相应的索引。
{
me(func: anyofterms(name, "Julie Baker"){
pred_A
pred_B {
pred_B1
pred_B2
}
}
}
查询 2 的处理过程是：
- term 分词器从"Julie Baker"字符串中获取到 Julie 和 Baker 两个 tokens。
- 发出两个查询 <name, Julie> 和 <name, Baker>，获得两个 uidlist。由于使用了函数 anyofterms，所以求这两个 uidlist 的并集，得到一个更大的 uidlist。
- 同查询 1 的遍历步骤。
过滤
过滤是查询语句的主要成分之一。过滤条件也是由函数组成的。
{
me(func: anyofterms(name, "Julie Baker"))@filter(eq(sex, "female")){
pred_A
pred_B {
pred_B1
pred_B2
}
}
}
给查询 2 添加过滤条件后得到查询 3，处理过程如下：
- 同查询 2，由起始函数获得一个 uidlist。
- 由过滤函数得到一个 uidlist，并与第 1 步中的 uidlist 求交，得到两者的一个子集。
- 同查询 1 的遍历步骤。
四、关键设计
连接和遍历
图查询经常涉及连接和遍历，那么什么是连接、什么是遍历呢？举个例子。
查询 [people lives in SF who eat sushi] 涉及到一级连接，完成它需要三个步骤：
- 查询住在洛杉矶的人。
- 查询吃寿司的人。
- 求两个集合的交集。
而查询 [people who are my friends of friends] 主要涉及遍历。
可以注意到，无论连接还是遍历都是关系(relation)查询。我们知道，图数据库比关系数据库更适合关系查询，因为关系数据库需要通过多表连接推断关系，而图数据库直接存储关系。
尽管如此，当连接(或者遍历)深度增加时，大部分图数据库依然效率不高。
连接深度问题
大多数分布式图数据库采用基于实体的数据分片策略，即实体伴随它的所有边和属性，随机(或者启发式)分布在集群的服务器上。该策略导致了连接深度问题。
以查询 [people lives in SF who eat sushi] 为例，people 伴随它的 lives-in 和 eat 边，随机分布在集群的服务器上。
最简单的想法是，第 1 步广播一个子查询 [people in SF] ；对第 1 步的每个结果，产生一个子查询，找出其饮食习惯，挑出吃寿司的人。显然，如果第 1 步有上百万的结果(洛杉矶的人数)，第 2 步就产生上百万个子查询。解决方法是，聚集第 1 步的查询结果，根据数据分片函数打包，然后再广播子查询。改进后的查询过程如图所示：
观察上述过程，可以发现两个问题：
第一，查询需要不断地聚集和发送中间结果集，增加了网络开销。
第二，查询产生了大量广播子查询，随着集群规模变大，查询由于意外产生延迟的可能性增加。
低延迟深度连接
为了优化分布式连接，Dgraph 采用基于 predicate 的数据分片策略，使得每个连接都可以完全由一台机器执行。
以查询 [people lives in SF who eat sushi] 为例，数据有两个分片 lives-in 和 eat，在最坏的情况下，这两个分片存储在不同的服务器上。查询过程是，第 1 步通过一个网络调用找到所有居住在洛杉矶的人；第 2 步通过一个网络调用，发送第 1 步的结果集并与所有吃寿司的人求交集。
通过独特的分片机制，Dgraph 可以通过两次网络调用完成了上述查询，并且每增加一度连接仅增加一次网络调用。
一个复杂的例子
为了说明 Dgraph 如何最小化网络开销，考虑一个更复杂的查询：
[Find all posts liked by friends of friends of mine over the last year, written by a popular author X.]。
在分布式 SQL/NoSQL 数据库中，一般用以下步骤来执行：
- 查询所有的朋友(~338 个朋友)，
result set 1。 - 查询朋友的朋友(~338*338 = 40000 人)，
result set 2。 - 查询他们过去一年中喜欢的 posts(可能上百万结果)，
result set 3. - 求 X 所写得 posts 与
result set 3的交集。
上述步骤导致大量数据往返于应用程序和数据库之间，降低了执行速度。
而在 Dgraph 中，查询的执行过程如下：
- 假设节点 X 存储 predicate
friends。 - 查询所有的朋友(1 个 RPC)，在本机上查找朋友的朋友，
result set 1。 - 假设节点 Y 存储 predicate
posts_liked。 - 发送
result set 1到节点 Y(1 个 RPC)，查询result set 1所喜欢的 posts，result set 2。 - 假设节点 Z 存储 predicate
author。 - 发送
result set 2到节点 Z(1 个 RPC)，查找作者 X 所写得 posts，result set 3。 - 求
result set 2和result set 3的交集，result set 4。 - 假设节点 N 存储 predicate
name。 - 发送
result set 4到节点 N(1 个 RPC)，查询他们的名字，result set 5。
可以看到，Dgraph 只用 4 个 RPCs 就获得了最终查询结果。这个设计不仅允许强大的扩展能力，还对那些需要深度连接的复杂查询保持产品级的延迟。
五、总结
本文对 Dgraph 的数据存储结构、索引构建、查询流程，以及为了减少网络开销而做的关键设计等进行了具体的介绍，但 Dgraph 的原理远不止这些，还有多版本控制、事务管理、一致性模型等都有待进一步探索。我们后续会继续发布相关文章，欢迎感兴趣的同学关注。
六、参考文献
[1]https://github.com/dgraph-io/dgraph/blob/master/paper/dgraph.pdf
[2]https://dgraph.io/blog/post/why-google-needed-graph-serving-system/
[3]https://dgraph.io/docs/design-concepts/
[4]https://cloud.tencent.com/developer/news/206999
作者介绍
赵祥，2019 年 6 月毕业于华中科技大学计算机学院，毕业后加入贝壳找房语言智能与搜索部，主要从事图数据库相关工作。
