系列文章：
贝壳找房—【图数据库系列】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)，它们的关系如下：

索引跟数据一样，以 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 的单个对象，处理过程如下：

1. 查询 <pred_A, 0x1>、<pred_B, 0x1> 两个 key，分别获得一个值(或者值列表)和一个 uidlist。
2. 对于 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 的处理过程是：

1. term 分词器从"Julie Baker"字符串中获取到 Julie 和 Baker 两个 tokens。
2. 发出两个查询 <name, Julie> 和 <name, Baker>，获得两个 uidlist。由于使用了函数 anyofterms，所以求这两个 uidlist 的并集，得到一个更大的 uidlist。
3. 同查询 1 的遍历步骤。

过滤

过滤是查询语句的主要成分之一。过滤条件也是由函数组成的。

{  
  me(func: anyofterms(name, "Julie Baker"))@filter(eq(sex, "female")){
    pred_A  
    pred_B {  
      pred_B1  
      pred_B2  
    }  
  } 
}

给查询 2 添加过滤条件后得到查询 3，处理过程如下：

1. 同查询 2，由起始函数获得一个 uidlist。
2. 由过滤函数得到一个 uidlist，并与第 1 步中的 uidlist 求交，得到两者的一个子集。
3. 同查询 1 的遍历步骤。

四、关键设计

连接和遍历

图查询经常涉及连接和遍历，那么什么是连接、什么是遍历呢？举个例子。

查询 [people lives in SF who eat sushi] 涉及到一级连接，完成它需要三个步骤：

1. 查询住在洛杉矶的人。
2. 查询吃寿司的人。
3. 求两个集合的交集。

而查询 [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 月毕业于华中科技大学计算机学院，毕业后加入贝壳找房语言智能与搜索部，主要从事图数据库相关工作。