图数据技术调研以及业务实践

什么是图数据库以及应用范围？

图数据库是 NoSQL 的一种，一种将关联数据的实体作为顶点，关系作为边来存储的特殊类型数据库，能够高效地对这些点边结构进行存储、检索和查询。它的优点是可以很自然地表示现实世界。比如社交关系（可以清楚地看到共同好友）、股东关系甚至银行账户流动关系。

图片

图片

属性图

从数学角度来说，图论是研究建模对象之间关系结构的学科。但是从工业界使用的角度，通常会对基础的图模型进行扩展，称为属性图模型。属性图通常由以下几部分组成：

• 节点，即对象或实体。
• 节点之间的关系，通常简称为边（Edge）。通常边是有方向或者无方向的，以表示两个实体之间有持续的关系。

在属性图模型中，每个顶点包括:

• 唯一的标识符。
• 出边的集合。
• 入边的集合。
• 属性的集合 (键-值对)

每个边包括 :

• 唯一的标识符。
• 边开始的顶点(尾部顶点)
• 边结束的顶点(头部顶点)
• 描述两个顶点间关系类型的标签。
• 属性 的集合 (键-值对)。

很多数据可以建模为图。典型的例子包括 :

社交网络

顶点是人，边指示哪些人彼此认识 。

Web 图

顶点是网页，边表示与其他页面的 HTML 链接。

公路或铁路网

顶点是交叉路口，边表示他们之间的公路或铁路线。

公司股权关系

点的属性可以为股票代码、简称、市值、板块等；边的属性可以为股权。

有很多著名的算法可以在这些图上运行。例如，汽车导航系统搜索道路网中任意两点之间的最短路径，PageRank 可以计算 Web 图上网页的流行度，从而确定搜索排名。

在政采云，可以有很多使用的场景，比如：

1.项目图谱，项目、供应商、专家可以用图中的点来表示，项目的中标供应商、评标专家可以用边来表示。

图片

2.商品图谱，商品、协议可以作为顶点，商品的合规、交易可以作为边。

图片

3.安全风控： 业务部门有内容风控的需求，希望在专家、供应商、代理机构中通过多跳查询来识别围标、窜标等行为。

数据库关系和选择什么数据库？

数据模型可能是开发软件最重要的部分，它们不仅对软件的编写方式，而且还对如何思考待解决的问题都有深远的影响。

大多数应用程序是通过一层一层叠加数据模型来构建的 。每一层都面临的关键问题是:如何将其用下一层来表示?例如 :

这和我们通常说的 MVC 模型也有点相似，数据层、应用层、展示层都需要接受上一层的数据模型，通过封装和处理给下一层使用。

这里说到数据模型，主要是为了说明不同的数据关系是我们选择不同的数据库的原因，因为不同的数据模型对应了更适合哪种数据关系。

关系模型

现在最著名的数据模型可能是 SQL，它基于 Edgar Codd 于1970年提出的关系模型: 数据被组织成关系( relations)，在SQL中称为表( table)，其中每个关系者J)是元组(tuples)的无序集合 (在 SQL中称为行)。

多对多关系是不同数据模型之间的重要区别特征 。

如果数据大多是一对多关系(树结构数据)或者记录之间没有关系，那么文档模型是最合适的 。

但是，如果多对多的关系在数据中很常见呢 ?关系模型能够处理简单的多对多关系， 但是随着数据之间的关联越来越复杂，将数据建模转化为图模型会更加自然。

虽然关系型数据库与文档类型的数据库，都可以用来描述图结构的数据模型，但是，图（数据库）不仅可以描述图结构与存储数据本身，更着眼于处理数据之间的关联（拓扑）关系。具体来说，图（数据库）有这么几个优点：

• 图是一种更直观、更符合人脑思考直觉的知识表示方式。这使得我们在抽象业务问题时，可以着眼于“业务问题本身”，而不是“如何将问题描述为数据库的某种特定结构（例如表格结构）”。
• 图更容易展现数据的特征，例如转账的路径、近邻的社区。例如，如果要分析某个公司的股权关系，表的组织方式如下：

图片

这显然没有图数据库直观：

图片

我们都知道关系型数据库和 NoSQL 数据库，目前最广泛使用的关系型数据库有 Mysql、Oracle 和 Postgre。NoSQL 数据库其实不是一个合适的词，因为它其实并不代表具体的某些技术。

NoSQL 可以分为以下几种数据库：

1.文档数据库，比如 MongoDB 和 Elasticsearch;

2.键值数据库，比如 Redis。

3.列式存储，比如 HBase、Cassandra、HadoopDB

4.最后一种就是今天要说的图数据库，图数据库以点、边、属性的形式存储数据。其优点在于灵活性高，支持复杂的图形算法，可用于构建复杂的关系图谱。常见的图数据库有：NebulaGraph、Neo4j、OrientDB、 DGraph等。

图数据库的类型和选型

在图数据库的选型上我们主要考虑遗下四点：

• 项目开源，暂不考虑需付费的图数据库；
• 分布式架构设计，具备良好的可扩展性；
• 毫秒级的多跳查询延迟；
• 支持千亿量级点边存储；

现在有图数据库产品

我们将图数据库分为三类：

• 第一类：Neo4j[3]、ArangoDB[4]、Virtuoso[5]、TigerGraph[6]、RedisGraph[7]。 此类图数据库只有单机版本开源可用，性能优秀，但不能应对分布式场景中数据的规模增长，即不满足选型要求
• 第二类：JanusGraph[8]、HugeGraph[9]。 此类图数据库在现有存储系统之上新增了通用的图语义解释层，图语义层提供了图遍历的能力，但是受到存储层或者架构限制，不支持完整的计算下推，多跳遍历的性能较差，很难满足 OLTP 场景下对低延时的要求，即不满足选型要求。
• 第三类：DGraph[10]、NebulaGraph[11]。 此类图数据库根据图数据的特点对数据存储模型、点边分布、执行引擎进行了全新设计，对图的多跳遍历进行了深度优化，基本满足我们的选型要求。

DGraph 是由前 Google员工 Manish Rai Jain 离职创业后，在 2016 年推出的图数据库产品，底层数据模型是 RDF（实际上也是属性图差不多），基于 Go 语言编写，存储引擎基于 BadgerDB 改造，使用 RAFT 保证数据读写的强一致性。

NebulaGraph 是由前 Facebook 员工叶小萌离职创业后，在 2019 年推出的图数据库产品，底层数据模型是属性图，基于 C++ 语言编写，存储引擎基于 RocksDB 改造，使用 RAFT 保证数据读写的强一致性。

实时写入性能

图片

查询性能

图片

在查询和插入的性能测试方面，两个数据库各有优劣，都能满足我们的需求，我们最后选择了 Dgraph 作为我们使用的图数据库，因为两个原因：

• NebulaGraph 不支持模糊查询，需要依赖 ElasticSearch，运维成本较高，
• Dgraph 是使用RDF通用数据类型，遵守 w3c 查询语句规范，而 NebulaGraph 的查询是 nGQL，自己开发的一套语言，不具有通用性

Dgraph

一、架构模型

图片

dgraph可以分为三个部分：ratel、alpha、zero。

ratel：提供用户界面来执行数据查询，数据修改及元数据管理。

alpha：用于管理数据（谓词和索引），外部用户主要都是和 alpha 进行数据交互。

zero：用于管理集群，并在 group 之间按照指定频率去均衡数据。alpha 节点分成若干个 group，每个 group 存储若干个数据分片。由于分片的大小是不均匀的，因此不同 group 也是不均匀的。zero 节点的任务之一就是平衡 group 之间的数据大小。具体方法是，每个 group 周期性地向 zero 报告各个数据分片的大小。zero 根据这个信息在 group 之间移动分片，使得每个 group 的磁盘利用率接近。

group：多个 alpha 组成一个 group，group 中的多个 alpha 通过 raft 协议保证数据一致性。

二、扩展、复制和分片

每个集群将至少有一个 Dgraph 零节点和一个 Dgraph Alpha 节点。然后以两种方式扩展数据库。

高可用性复制

为了实现高可用性，Dgraph 使用三个零和三个 alpha 运行，而不是每个一个。

对于大多数生产应用程序所需的规模和可靠性，建议使用此配置。

拥有三台服务器既可以使整个集群的容量增加三倍，也可以提供冗余。

分片

当数据大小接近或超过 1 TB 时，Dgraph 数据库通常会被分片，这样完整的数据副本就不会保留在任何单个 alpha 节点上。

通过分片，数据分布在许多节点（或节点组）中以实现更高的规模。

当需要提供大规模和理想的可靠性时，分片和高可用性相结合。

自我修复

在 Dgraph 的云产品中，Kubernetes 用于自动检测、重启和修复任何集群（HA、分片、两者或两者都不），以保持事物平稳运行并满负荷运行。

三、数据存储

在 Dgraph 中，数据的最小单位是一个三元组。三元组既可以表示一个属性(subject-predicate-value)，也可以表示一条边(subject-predicate-object)。Dgraph 为每个对象分配一个全局唯一的 id，称为 uid。Uid 是一个 64 位无符号整数，从 1 开始单调递增。

Dgraph 基于 predicate 进行数据分片，即所有相同 predicate 的三元组形成一个分片。在分片内部，根据 subject-predicate 将三元组进一步分组，每一组数据压缩成一个 key-value 对。其中 key 是 ，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 的所有粉丝，只需要用 当做 key 进行查询，就能获得一个 posting list，包含了所有粉丝的 uid；寻找 X 和 Y 的公共粉丝，只需要查询 和 的 posting lists，然后求两者的交集。

如果有太多的三元组共享相同的 ，posting list 就变得过大。Dgraph 的解决方法是，每当 posting list 的大小超过一个阈值，就把它分成两份，这样一个分割的 posting list 就会对应多个 keys。这些存储细节都是对用户透明的。

四、索引

当通过应用函数进行过滤时，Dgraph 使用索引来高效地搜索潜在的大型数据集。 所有标量类型都可以被索引。

类型int、float、bool、geo只有一个默认索引，他们都只有自己的分词器。

对于 string 类型，支持正则表达式、fulltext、term、exact 和 hash 索引；

对于 datetime 类型，支持按年、月、日、小时索引；

对于 geo 类型，支持 nearby、within 等索引。

索引跟数据一样，以 key-value 的形式存储，区别是 key 有所不同。数据的 key 是 ，而索引的 key 是 。Token 是索引的分词器从 value 中获取的，例如 hash 索引生成的 token 就是 hash 函数所计算的 hash 值。

在定义 schema 的时候，可以给 predicate 创建一个或多个索引。对该 predicate 的每次更新会调用一个或多个分词器来产生 tokens。更新的时候，首先从旧值的 tokens 的 posting lists 中删除相应的 uid，然后把 uid 添加到新产生的 tokens 的 posting lists 里。

五、查询

遍历

Dgraph 的查询通常从一个 uidlist 开始，沿着边进行遍历。

{
  movies(func: uid（0xb5849, 0x394c)) {
    uid
     m_name     
     code
     star{
         s_name
     }
  }
}

查询的起点是 uid 为0xb5849 的单个对象，处理过程如下：

函数

通常我们不知道 uid，需要根据名称查询

//查询示例：具有dog，dogs，bark，barks，barking等的所有名称。停止词the which 会被删除掉。
{
  movie(func:alloftext(name@en, "the dog which barks")) {
    name@en
  }
}

查询 的处理过程是：

过滤

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

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

深度查询

这是一个查询 4 度关注的语句。通过 A 的 uid 可以查询到 E 的 name

A