贝壳找房—【图数据库系列】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 的单个对象,处理过程如下:

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


本文地址:https://www.6aiq.com/article/1586914787766
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出