Aug 13, 2019

初识图数据库与图计算

图数据存储与计算通常应用在大数据领域，解决数据本身及其之间关联信息的存储及挖掘问题。我们的生活场景中充满了图结构的数据和信息形式，图数据与图计算也已经应用到其中如金融风控、物联网及人工智能等领域。

图数据库与图计算的应用

这篇文章主要整理介绍了图计算及图数据库的基本概念，其中包括架构分类、挑战，最后罗列了几篇相关的论文及两个开源项目。

图计算

图计算是在图的数据组织模型下采用如最小连通图、最短路径等图论相关的算法挖掘大规模数据之间的关联性与潜在价值，比如社交网络关系、公司债务关系的挖掘等。图计算与图存储是两个比较相关的方向，数据使用图的结构组织存储起来是为了方便上层的快速查找( OLTP 相关)与分析计算( OLAP 相关)。比如图的分布式存储中需要将图划分，这是为了便于后续计算的存储方式。其中的图划分也用到了图计算中的算法，也就是用图计算设计存储方式，最终服务于上层图计算。当然，基于遍历算法的实时数据库查询也是一种图计算。

分布式图计算模型

由于图计算主要应用于大数据分析领域，其中的图数据具有量大、关联结构复杂的特点，因此往往需要设计大规模高效图计算框架来处理图数据，主要为了解决以下问题：

  • 图计算频繁迭代带来的读写数据等待和通信开销大的问题；
  • 图算法对节点和边对邻居信息依赖问题；
  • 图数据的复杂结构使得图算法难以实现在分布不均匀的分块上并行计算的问题。

谷歌在2010年基于 BSP(Bulk synchronous parallel) 计算框架提出了最早的同步节点图计算模型，并应用到图计算系统 Pregel 中；同年，为了解决全局同步带来的等待开销问题，卡耐基梅隆大学 Select 实验室提出了异步图计算框架并应用到图计算系统 GraphLab 中。虽然异步节点计算模型节省了数据更新时候的时间等待开销，但增加了维护数据一致性的开销，于是 Select 针对这个问题提出了混合节点中心计算模型 GAS，并应用于图计算系统 PowerGraph 中。

BSP

BSP 将计算过程拆分为多个串行执行的 super step，并基于一个 Master 协调，所有 worker 同步执行，在一个 super step 中所有 worker 并行执行，然后进入全局通信同步数据，最后等待所有进程同步完成进入下一个 super step。

BSP

BSP 计算模型可以有效避免死锁，但是其同步等待的时间开销较大。

GAS

PowerGraph 将基于顶点的图计算抽象成为了 GAS 通用计算模型，模型计算主要分为以下三个步骤：

  • Gather：节点收集所有邻居节点的信息
  • Apply：节点使用邻居信息更新计算
  • Scatter：将计算后的值分发到所有邻居节点

这里有一个简单的 GAS 计算模型应用到 PageRank 算法中的一轮迭代例子：

GAS-PageRank

为了简单，图中的边都为无向边，具体步骤为：

  1. 因为有5个节点，在每个节点上的概率初始化为1/5
  2. Gather 阶段收集所有邻居的信息，这里是从邻居转移到本节点的概率
  3. Apply 阶段将所有从邻居那里获得的转移概率相加获得新的 rank 值
  4. Scatter 阶段又将每个节点出边的转移概率分发到邻居节点

图数据库

图数据库也是一种在线的数据管理系统，其最大特点是其存储模型是图（这里指 API 下能够调用的数据结构），主要优势是关联数据的查询速度快且能够管理大规模的数据。以下介绍图数据的基本分类与 Neo4j 原生图存储模型。

现有的图数据库可以参考 DB-Engines 。

图数据库架构

图数据库主要分为原生存储与多模存储两类。原生图存储数据库是指其底层存储模型已经是图，比如 Neo4j；多模数据库往往依赖已有的数据库引擎，在其上面封装一层图抽象模型并提供图数据操作的 API，如 Agens Graph 基于 PostgreSQL，JanusGraph 底层可以配置HBase、Cassandra 和 BerkeleyDB。

原生存储与非原生存储

免索引邻接是原生图数据库的一大特点，每个节点包括了它所有边的指针列表，因此在查找与一个节点相关联的节点变得相对容易，只需要通过边的指针直接能访问到目标节点。

免索引邻接与索引查询的对比

但是，免索引邻接往往只是在单机情况下比较有效，在分布式图存储中节点可能分布在不同的服务器上，通过一条边去跨服务器访问需要网络 I/O，这种情况下免索引邻接对于图查找的优化相对于网路 I/O 来说是相当有限的。

需求、挑战与研究点

图数据库与其他数据库一样都是在线的系统，都需要处理数据查询、数据一致性、大规模数据处理等问题，只是图数据面向的数据模型是图，可以利用图的结构优化相关的处理过程。但是问题往往都是无法获得最优解的，采用图存储和计算模型会带来其他诸如图遍历及图查询过程转换、分布式图划分、图数据查询语言体系构建等问题。大规模图数据存储与计算带来的挑战主要有：

  • 低延时：由于需要处理大量的关联数据，数据的关联性往往会带来严重的随机访问。如非原生存储在图数据查询落到数据引擎的时候会转化成为大量的 join 操作从而拉低效率、分布式场景下网络开销大等。
  • 数据一致性：图数据库才兴起的时候往往作为二级索引来提高数据查询效率，现在考虑将数据直接存储到图数据库中，这就要求图数据库具有较高的数据一致性保障能力，并且在支持大规模数据访问的情况下能实现高可用。
  • 复杂分析与查询：由于图数据库针对大规模关联数据进行存储，避免不了需要实现如排序及数据过滤等复杂分析与查询，但这些查询如何落到实际数据系统上是一个重要的问题。
  • 缺少通用查询语言标准：相比与成熟的关系性数据库查询语言 SQL，目前主流的图数据库查询语言就有 Cypher、Gremlin、Sparql 及 GSQL 几种，其余还有很多厂商在开发自己数据库对应的查询语言。缺乏查询语言标准阻碍了图数据库的应用落地，从而无法有效推动图数据库体系持续发展。

因此，图数据库与图计算中涉及了大量的研究方向，主要有：

  • 数据库架构研究
  • 图遍历与查询处理
  • 索引
  • 数据一致性与容灾
  • 图计算模型
  • 分布式图划分
  • 图数据挖掘算法

相关论文

图数据库

图计算

开源项目

参考